declare isl_tab_get_ctx in isl_tab.h
[isl.git] / isl_ast_build.c
blobfe14b50bc8d34a2c067545ad2aba7e934fe1b2f8
1 /*
2 * Copyright 2012 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
8 */
10 #include <isl/map.h>
11 #include <isl/aff.h>
12 #include <isl/map.h>
13 #include <isl_ast_build_private.h>
14 #include <isl_ast_private.h>
16 /* Construct a map that isolates the current dimension.
18 * Essentially, the current dimension of "set" is moved to the single output
19 * dimension in the result, with the current dimension in the domain replaced
20 * by an unconstrained variable.
22 __isl_give isl_map *isl_ast_build_map_to_iterator(
23 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
25 isl_map *map;
27 map = isl_map_from_domain(set);
28 map = isl_map_add_dims(map, isl_dim_out, 1);
30 if (!build)
31 return isl_map_free(map);
33 map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
34 map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
36 return map;
39 /* Initialize the information derived during the AST generation to default
40 * values for a schedule domain in "space".
42 * We also check that the remaining fields are not NULL so that
43 * the calling functions don't have to perform this test.
45 static __isl_give isl_ast_build *isl_ast_build_init_derived(
46 __isl_take isl_ast_build *build, __isl_take isl_space *space)
48 isl_ctx *ctx;
49 isl_vec *strides;
51 build = isl_ast_build_cow(build);
52 if (!build || !build->domain)
53 goto error;
55 ctx = isl_ast_build_get_ctx(build);
56 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
57 strides = isl_vec_set_si(strides, 1);
59 isl_vec_free(build->strides);
60 build->strides = strides;
62 space = isl_space_map_from_set(space);
63 isl_multi_aff_free(build->offsets);
64 build->offsets = isl_multi_aff_zero(isl_space_copy(space));
65 isl_multi_aff_free(build->values);
66 build->values = isl_multi_aff_identity(space);
68 if (!build->iterators || !build->domain || !build->generated ||
69 !build->pending || !build->values ||
70 !build->strides || !build->offsets || !build->options)
71 return isl_ast_build_free(build);
73 return build;
74 error:
75 isl_space_free(space);
76 return isl_ast_build_free(build);
79 /* Return an isl_id called "c%d", with "%d" set to "i".
80 * If an isl_id with such a name already appears among the parameters
81 * in build->domain, then adjust the name to "c%d_%d".
83 static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
84 __isl_keep isl_ast_build *build)
86 int j;
87 char name[16];
88 isl_set *dom = build->domain;
90 snprintf(name, sizeof(name), "c%d", i);
91 j = 0;
92 while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
93 snprintf(name, sizeof(name), "c%d_%d", i, j++);
94 return isl_id_alloc(ctx, name, NULL);
97 /* Create an isl_ast_build with "set" as domain.
99 * The input set is usually a parameter domain, but we currently allow it to
100 * be any kind of set. We set the domain of the returned isl_ast_build
101 * to "set" and initialize all the other field to default values.
103 __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
105 int i, n;
106 isl_ctx *ctx;
107 isl_space *space;
108 isl_ast_build *build;
110 set = isl_set_compute_divs(set);
111 if (!set)
112 return NULL;
114 ctx = isl_set_get_ctx(set);
116 build = isl_calloc_type(ctx, isl_ast_build);
117 if (!build)
118 goto error;
120 build->ref = 1;
121 build->domain = set;
122 build->generated = isl_set_copy(build->domain);
123 build->pending = isl_set_universe(isl_set_get_space(build->domain));
124 build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
125 n = isl_set_dim(set, isl_dim_set);
126 build->depth = n;
127 build->iterators = isl_id_list_alloc(ctx, n);
128 for (i = 0; i < n; ++i) {
129 isl_id *id;
130 if (isl_set_has_dim_id(set, isl_dim_set, i))
131 id = isl_set_get_dim_id(set, isl_dim_set, i);
132 else
133 id = generate_name(ctx, i, build);
134 build->iterators = isl_id_list_add(build->iterators, id);
136 space = isl_set_get_space(set);
137 if (isl_space_is_params(space))
138 space = isl_space_set_from_params(space);
140 return isl_ast_build_init_derived(build, space);
141 error:
142 isl_set_free(set);
143 return NULL;
146 __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
148 if (!build)
149 return NULL;
151 build->ref++;
152 return build;
155 __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
157 isl_ctx *ctx;
158 isl_ast_build *dup;
160 if (!build)
161 return NULL;
163 ctx = isl_ast_build_get_ctx(build);
164 dup = isl_calloc_type(ctx, isl_ast_build);
165 if (!dup)
166 return NULL;
168 dup->ref = 1;
169 dup->outer_pos = build->outer_pos;
170 dup->depth = build->depth;
171 dup->iterators = isl_id_list_copy(build->iterators);
172 dup->domain = isl_set_copy(build->domain);
173 dup->generated = isl_set_copy(build->generated);
174 dup->pending = isl_set_copy(build->pending);
175 dup->values = isl_multi_aff_copy(build->values);
176 dup->value = isl_pw_aff_copy(build->value);
177 dup->strides = isl_vec_copy(build->strides);
178 dup->offsets = isl_multi_aff_copy(build->offsets);
179 dup->executed = isl_union_map_copy(build->executed);
180 dup->single_valued = build->single_valued;
181 dup->options = isl_union_map_copy(build->options);
182 dup->at_each_domain = build->at_each_domain;
183 dup->at_each_domain_user = build->at_each_domain_user;
184 dup->before_each_for = build->before_each_for;
185 dup->before_each_for_user = build->before_each_for_user;
186 dup->after_each_for = build->after_each_for;
187 dup->after_each_for_user = build->after_each_for_user;
188 dup->create_leaf = build->create_leaf;
189 dup->create_leaf_user = build->create_leaf_user;
191 if (!dup->iterators || !dup->domain || !dup->generated ||
192 !dup->pending || !dup->values ||
193 !dup->strides || !dup->offsets || !dup->options ||
194 (build->executed && !dup->executed) ||
195 (build->value && !dup->value))
196 return isl_ast_build_free(dup);
198 return dup;
201 /* Align the parameters of "build" to those of "model", introducing
202 * additional parameters if needed.
204 __isl_give isl_ast_build *isl_ast_build_align_params(
205 __isl_take isl_ast_build *build, __isl_take isl_space *model)
207 build = isl_ast_build_cow(build);
208 if (!build)
209 goto error;
211 build->domain = isl_set_align_params(build->domain,
212 isl_space_copy(model));
213 build->generated = isl_set_align_params(build->generated,
214 isl_space_copy(model));
215 build->pending = isl_set_align_params(build->pending,
216 isl_space_copy(model));
217 build->values = isl_multi_aff_align_params(build->values,
218 isl_space_copy(model));
219 build->offsets = isl_multi_aff_align_params(build->offsets,
220 isl_space_copy(model));
221 build->options = isl_union_map_align_params(build->options,
222 isl_space_copy(model));
223 isl_space_free(model);
225 if (!build->domain || !build->values || !build->offsets ||
226 !build->options)
227 return isl_ast_build_free(build);
229 return build;
230 error:
231 isl_space_free(model);
232 return NULL;
235 __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
237 if (!build)
238 return NULL;
240 if (build->ref == 1)
241 return build;
242 build->ref--;
243 return isl_ast_build_dup(build);
246 void *isl_ast_build_free(__isl_take isl_ast_build *build)
248 if (!build)
249 return NULL;
251 if (--build->ref > 0)
252 return NULL;
254 isl_id_list_free(build->iterators);
255 isl_set_free(build->domain);
256 isl_set_free(build->generated);
257 isl_set_free(build->pending);
258 isl_multi_aff_free(build->values);
259 isl_pw_aff_free(build->value);
260 isl_vec_free(build->strides);
261 isl_multi_aff_free(build->offsets);
262 isl_multi_aff_free(build->schedule_map);
263 isl_union_map_free(build->executed);
264 isl_union_map_free(build->options);
266 free(build);
268 return NULL;
271 isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
273 return build ? isl_set_get_ctx(build->domain) : NULL;
276 /* Replace build->options by "options".
278 __isl_give isl_ast_build *isl_ast_build_set_options(
279 __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
281 build = isl_ast_build_cow(build);
283 if (!build || !options)
284 goto error;
286 isl_union_map_free(build->options);
287 build->options = options;
289 return build;
290 error:
291 isl_union_map_free(options);
292 return isl_ast_build_free(build);
295 /* Set the iterators for the next code generation.
297 * If we still have some iterators left from the previous code generation
298 * (if any) or if iterators have already been set by a previous
299 * call to this function, then we remove them first.
301 __isl_give isl_ast_build *isl_ast_build_set_iterators(
302 __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
304 int dim, n_it;
306 build = isl_ast_build_cow(build);
307 if (!build)
308 goto error;
310 dim = isl_set_dim(build->domain, isl_dim_set);
311 n_it = isl_id_list_n_id(build->iterators);
312 if (n_it < dim)
313 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
314 "isl_ast_build in inconsistent state", goto error);
315 if (n_it > dim)
316 build->iterators = isl_id_list_drop(build->iterators,
317 dim, n_it - dim);
318 build->iterators = isl_id_list_concat(build->iterators, iterators);
319 if (!build->iterators)
320 return isl_ast_build_free(build);
322 return build;
323 error:
324 isl_id_list_free(iterators);
325 return isl_ast_build_free(build);
328 /* Set the "at_each_domain" callback of "build" to "fn".
330 __isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
331 __isl_take isl_ast_build *build,
332 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
333 __isl_keep isl_ast_build *build, void *user), void *user)
335 build = isl_ast_build_cow(build);
337 if (!build)
338 return NULL;
340 build->at_each_domain = fn;
341 build->at_each_domain_user = user;
343 return build;
346 /* Set the "before_each_for" callback of "build" to "fn".
348 __isl_give isl_ast_build *isl_ast_build_set_before_each_for(
349 __isl_take isl_ast_build *build,
350 __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
351 void *user), void *user)
353 build = isl_ast_build_cow(build);
355 if (!build)
356 return NULL;
358 build->before_each_for = fn;
359 build->before_each_for_user = user;
361 return build;
364 /* Set the "after_each_for" callback of "build" to "fn".
366 __isl_give isl_ast_build *isl_ast_build_set_after_each_for(
367 __isl_take isl_ast_build *build,
368 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
369 __isl_keep isl_ast_build *build, void *user), void *user)
371 build = isl_ast_build_cow(build);
373 if (!build)
374 return NULL;
376 build->after_each_for = fn;
377 build->after_each_for_user = user;
379 return build;
382 /* Set the "create_leaf" callback of "build" to "fn".
384 __isl_give isl_ast_build *isl_ast_build_set_create_leaf(
385 __isl_take isl_ast_build *build,
386 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
387 void *user), void *user)
389 build = isl_ast_build_cow(build);
391 if (!build)
392 return NULL;
394 build->create_leaf = fn;
395 build->create_leaf_user = user;
397 return build;
400 /* Clear all information that is specific to this code generation
401 * and that is (probably) not meaningful to any nested code generation.
403 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
404 __isl_take isl_ast_build *build)
406 isl_space *space;
408 build = isl_ast_build_cow(build);
409 if (!build)
410 return NULL;
412 space = isl_union_map_get_space(build->options);
413 isl_union_map_free(build->options);
414 build->options = isl_union_map_empty(space);
416 build->at_each_domain = NULL;
417 build->at_each_domain_user = NULL;
418 build->before_each_for = NULL;
419 build->before_each_for_user = NULL;
420 build->after_each_for = NULL;
421 build->after_each_for_user = NULL;
422 build->create_leaf = NULL;
423 build->create_leaf_user = NULL;
425 if (!build->options)
426 return isl_ast_build_free(build);
428 return build;
431 /* Have any loops been eliminated?
432 * That is, do any of the original schedule dimensions have a fixed
433 * value that has been substituted?
435 static int any_eliminated(isl_ast_build *build)
437 int i;
439 for (i = 0; i < build->depth; ++i)
440 if (isl_ast_build_has_affine_value(build, i))
441 return 1;
443 return 0;
446 /* Clear build->schedule_map.
447 * This function should be called whenever anything that might affect
448 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
449 * In particular, it should be called when the depth is changed or
450 * when an iterator is determined to have a fixed value.
452 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
454 if (!build)
455 return;
456 isl_multi_aff_free(build->schedule_map);
457 build->schedule_map = NULL;
460 /* Do we need a (non-trivial) schedule map?
461 * That is, is the internal schedule space different from
462 * the external schedule space?
464 * The internal and external schedule spaces are only the same
465 * if code has been generated for the entire schedule and if none
466 * of the loops have been eliminated.
468 __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
470 int dim;
472 if (!build)
473 return -1;
475 dim = isl_set_dim(build->domain, isl_dim_set);
476 return build->depth != dim || any_eliminated(build);
479 /* Return a mapping from the internal schedule space to the external
480 * schedule space in the form of an isl_multi_aff.
481 * The internal schedule space originally corresponds to that of the
482 * input schedule. This may change during the code generation if
483 * if isl_ast_build_insert_dim is ever called.
484 * The external schedule space corresponds to the
485 * loops that have been generated.
487 * Currently, the only difference between the internal schedule domain
488 * and the external schedule domain is that some dimensions are projected
489 * out in the external schedule domain. In particular, the dimensions
490 * for which no code has been generated yet and the dimensions that correspond
491 * to eliminated loops.
493 * We cache a copy of the schedule_map in build->schedule_map.
494 * The cache is cleared through isl_ast_build_reset_schedule_map
495 * whenever anything changes that might affect the result of this function.
497 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
498 __isl_keep isl_ast_build *build)
500 isl_space *space;
501 isl_multi_aff *ma;
503 if (!build)
504 return NULL;
505 if (build->schedule_map)
506 return isl_multi_aff_copy(build->schedule_map);
508 space = isl_ast_build_get_space(build, 1);
509 space = isl_space_map_from_set(space);
510 ma = isl_multi_aff_identity(space);
511 if (isl_ast_build_need_schedule_map(build)) {
512 int i;
513 int dim = isl_set_dim(build->domain, isl_dim_set);
514 ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
515 build->depth, dim - build->depth);
516 for (i = build->depth - 1; i >= 0; --i)
517 if (isl_ast_build_has_affine_value(build, i))
518 ma = isl_multi_aff_drop_dims(ma,
519 isl_dim_out, i, 1);
522 build->schedule_map = ma;
523 return isl_multi_aff_copy(build->schedule_map);
526 /* Return a mapping from the internal schedule space to the external
527 * schedule space in the form of an isl_map.
529 __isl_give isl_map *isl_ast_build_get_schedule_map(
530 __isl_keep isl_ast_build *build)
532 isl_multi_aff *ma;
534 ma = isl_ast_build_get_schedule_map_multi_aff(build);
535 return isl_map_from_multi_aff(ma);
538 /* Return the position of the dimension in build->domain for which
539 * an AST node is currently being generated.
541 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
543 return build ? build->depth : -1;
546 /* Prepare for generating code for the next level.
547 * In particular, increase the depth and reset any information
548 * that is local to the current depth.
550 __isl_give isl_ast_build *isl_ast_build_increase_depth(
551 __isl_take isl_ast_build *build)
553 build = isl_ast_build_cow(build);
554 if (!build)
555 return NULL;
556 build->depth++;
557 isl_ast_build_reset_schedule_map(build);
558 build->value = isl_pw_aff_free(build->value);
559 return build;
562 void isl_ast_build_dump(__isl_keep isl_ast_build *build)
564 if (!build)
565 return;
567 fprintf(stderr, "domain: ");
568 isl_set_dump(build->domain);
569 fprintf(stderr, "generated: ");
570 isl_set_dump(build->generated);
571 fprintf(stderr, "pending: ");
572 isl_set_dump(build->pending);
573 fprintf(stderr, "iterators: ");
574 isl_id_list_dump(build->iterators);
575 fprintf(stderr, "values: ");
576 isl_multi_aff_dump(build->values);
577 if (build->value) {
578 fprintf(stderr, "value: ");
579 isl_pw_aff_dump(build->value);
581 fprintf(stderr, "strides: ");
582 isl_vec_dump(build->strides);
583 fprintf(stderr, "offsets: ");
584 isl_multi_aff_dump(build->offsets);
587 /* Initialize "build" for AST construction in schedule space "space"
588 * in the case that build->domain is a parameter set.
590 * build->iterators is assumed to have been updated already.
592 static __isl_give isl_ast_build *isl_ast_build_init(
593 __isl_take isl_ast_build *build, __isl_take isl_space *space)
595 isl_set *set;
597 build = isl_ast_build_cow(build);
598 if (!build)
599 goto error;
601 set = isl_set_universe(isl_space_copy(space));
602 build->domain = isl_set_intersect_params(isl_set_copy(set),
603 build->domain);
604 build->pending = isl_set_intersect_params(isl_set_copy(set),
605 build->pending);
606 build->generated = isl_set_intersect_params(set, build->generated);
608 return isl_ast_build_init_derived(build, space);
609 error:
610 isl_ast_build_free(build);
611 isl_space_free(space);
612 return NULL;
615 /* Assign "aff" to *user and return -1, effectively extracting
616 * the first (and presumably only) affine expression in the isl_pw_aff
617 * on which this function is used.
619 static int extract_single_piece(__isl_take isl_set *set,
620 __isl_take isl_aff *aff, void *user)
622 isl_aff **p = user;
624 *p = aff;
625 isl_set_free(set);
627 return -1;
630 /* Check if the given bounds on the current dimension imply that
631 * this current dimension attains only a single value (in terms of
632 * parameters and outer dimensions).
633 * If so, we record it in build->value.
634 * If, moreover, this value can be represented as a single affine expression,
635 * then we also update build->values, effectively marking the current
636 * dimension as "eliminated".
638 * When computing the gist of the fixed value that can be represented
639 * as a single affine expression, it is important to only take into
640 * account the domain constraints in the original AST build and
641 * not the domain of the affine expression itself.
642 * Otherwise, a [i/3] is changed into a i/3 because we know that i
643 * is a multiple of 3, but then we end up not expressing anywhere
644 * in the context that i is a multiple of 3.
646 static __isl_give isl_ast_build *update_values(
647 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
649 int sv;
650 isl_pw_multi_aff *pma;
651 isl_aff *aff = NULL;
652 isl_map *it_map;
653 isl_set *set;
655 set = isl_set_from_basic_set(bounds);
656 set = isl_set_intersect(set, isl_set_copy(build->domain));
657 it_map = isl_ast_build_map_to_iterator(build, set);
659 sv = isl_map_is_single_valued(it_map);
660 if (sv < 0)
661 build = isl_ast_build_free(build);
662 if (!build || !sv) {
663 isl_map_free(it_map);
664 return build;
667 pma = isl_pw_multi_aff_from_map(it_map);
668 build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
669 build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
670 build->value = isl_pw_aff_coalesce(build->value);
671 isl_pw_multi_aff_free(pma);
673 if (!build->value)
674 return isl_ast_build_free(build);
676 if (isl_pw_aff_n_piece(build->value) != 1)
677 return build;
679 isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
681 build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
682 if (!build->values)
683 return isl_ast_build_free(build);
684 isl_ast_build_reset_schedule_map(build);
685 return build;
688 /* Update the AST build based on the given loop bounds for
689 * the current dimension.
691 * We first make sure that the bounds do not refer to any iterators
692 * that have already been eliminated.
693 * Then, we check if the bounds imply that the current iterator
694 * has a fixed value.
695 * If they do and if this fixed value can be expressed as a single
696 * affine expression, we eliminate the iterators from the bounds.
697 * Note that we cannot simply plug in this single value using
698 * isl_basic_set_preimage_multi_aff as the single value may only
699 * be defined on a subset of the domain. Plugging in the value
700 * would restrict the build domain to this subset, while this
701 * restriction may not be reflected in the generated code.
702 * build->domain may, however, already refer to the current dimension
703 * due an earlier call to isl_ast_build_include_stride. If so, we need
704 * to eliminate the dimension so that we do not introduce it in any other sets.
705 * Finally, we intersect build->domain with the updated bounds.
707 * Note that the check for a fixed value in update_values requires
708 * us to intersect the bounds with the current build domain.
709 * When we intersect build->domain with the updated bounds in
710 * the final step, we make sure that these updated bounds have
711 * not been intersected with the old build->domain.
712 * Otherwise, we would indirectly intersect the build domain with itself,
713 * which can lead to inefficiencies, in particular if the build domain
714 * contains any unknown divs.
716 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
717 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
719 isl_set *set;
721 build = isl_ast_build_cow(build);
722 if (!build)
723 goto error;
725 bounds = isl_basic_set_preimage_multi_aff(bounds,
726 isl_multi_aff_copy(build->values));
727 build = update_values(build, isl_basic_set_copy(bounds));
728 if (!build)
729 goto error;
730 set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
731 if (isl_ast_build_has_affine_value(build, build->depth)) {
732 set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
733 set = isl_set_compute_divs(set);
734 build->pending = isl_set_intersect(build->pending,
735 isl_set_copy(set));
736 if (isl_ast_build_has_stride(build, build->depth)) {
737 build->domain = isl_set_eliminate(build->domain,
738 isl_dim_set, build->depth, 1);
739 build->domain = isl_set_compute_divs(build->domain);
741 } else {
742 isl_basic_set *generated, *pending;
744 pending = isl_basic_set_copy(bounds);
745 pending = isl_basic_set_drop_constraints_involving_dims(pending,
746 isl_dim_set, build->depth, 1);
747 build->pending = isl_set_intersect(build->pending,
748 isl_set_from_basic_set(pending));
749 generated = isl_basic_set_copy(bounds);
750 generated = isl_basic_set_drop_constraints_not_involving_dims(
751 generated, isl_dim_set, build->depth, 1);
752 build->generated = isl_set_intersect(build->generated,
753 isl_set_from_basic_set(generated));
755 isl_basic_set_free(bounds);
757 build->domain = isl_set_intersect(build->domain, set);
758 if (!build->domain || !build->pending || !build->generated)
759 return isl_ast_build_free(build);
761 return build;
762 error:
763 isl_ast_build_free(build);
764 isl_basic_set_free(bounds);
765 return NULL;
768 /* Update build->domain based on the constraints enforced by inner loops.
770 * The constraints in build->pending may end up not getting generated
771 * if they are implied by "enforced". We therefore reconstruct
772 * build->domain from build->generated and build->pending, dropping
773 * those constraint in build->pending that may not get generated.
775 __isl_give isl_ast_build *isl_ast_build_set_enforced(
776 __isl_take isl_ast_build *build, __isl_take isl_basic_set *enforced)
778 isl_set *set;
780 build = isl_ast_build_cow(build);
781 if (!build)
782 goto error;
784 set = isl_set_from_basic_set(enforced);
785 set = isl_set_gist(isl_set_copy(build->pending), set);
786 set = isl_set_intersect(isl_set_copy(build->generated), set);
788 isl_set_free(build->domain);
789 build->domain = set;
791 if (!build->domain)
792 return isl_ast_build_free(build);
794 return build;
795 error:
796 isl_basic_set_free(enforced);
797 return isl_ast_build_free(build);
800 /* Intersect build->domain with "set", where "set" is specified
801 * in terms of the internal schedule domain.
803 static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
804 __isl_take isl_ast_build *build, __isl_take isl_set *set)
806 build = isl_ast_build_cow(build);
807 if (!build)
808 goto error;
810 set = isl_set_compute_divs(set);
811 build->domain = isl_set_intersect(build->domain, set);
812 build->domain = isl_set_coalesce(build->domain);
814 if (!build->domain)
815 return isl_ast_build_free(build);
817 return build;
818 error:
819 isl_ast_build_free(build);
820 isl_set_free(set);
821 return NULL;
824 /* Intersect build->generated and build->domain with "set",
825 * where "set" is specified in terms of the internal schedule domain.
827 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
828 __isl_take isl_ast_build *build, __isl_take isl_set *set)
830 set = isl_set_compute_divs(set);
831 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
832 build = isl_ast_build_cow(build);
833 if (!build)
834 goto error;
836 build->generated = isl_set_intersect(build->generated, set);
837 build->generated = isl_set_coalesce(build->generated);
839 if (!build->generated)
840 return isl_ast_build_free(build);
842 return build;
843 error:
844 isl_ast_build_free(build);
845 isl_set_free(set);
846 return NULL;
849 /* Intersect build->pending and build->domain with "set",
850 * where "set" is specified in terms of the internal schedule domain.
852 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
853 __isl_take isl_ast_build *build, __isl_take isl_set *set)
855 set = isl_set_compute_divs(set);
856 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
857 build = isl_ast_build_cow(build);
858 if (!build)
859 goto error;
861 build->pending = isl_set_intersect(build->pending, set);
862 build->pending = isl_set_coalesce(build->pending);
864 if (!build->pending)
865 return isl_ast_build_free(build);
867 return build;
868 error:
869 isl_ast_build_free(build);
870 isl_set_free(set);
871 return NULL;
874 /* Intersect build->domain with "set", where "set" is specified
875 * in terms of the external schedule domain.
877 __isl_give isl_ast_build *isl_ast_build_restrict(
878 __isl_take isl_ast_build *build, __isl_take isl_set *set)
880 if (isl_set_is_params(set))
881 return isl_ast_build_restrict_generated(build, set);
883 if (isl_ast_build_need_schedule_map(build)) {
884 isl_multi_aff *ma;
885 ma = isl_ast_build_get_schedule_map_multi_aff(build);
886 set = isl_set_preimage_multi_aff(set, ma);
888 return isl_ast_build_restrict_generated(build, set);
891 /* Replace build->executed by "executed".
893 __isl_give isl_ast_build *isl_ast_build_set_executed(
894 __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
896 build = isl_ast_build_cow(build);
897 if (!build)
898 goto error;
900 isl_union_map_free(build->executed);
901 build->executed = executed;
903 return build;
904 error:
905 isl_ast_build_free(build);
906 isl_union_map_free(executed);
907 return NULL;
910 /* Return a copy of the current schedule domain.
912 __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
914 return build ? isl_set_copy(build->domain) : NULL;
917 /* Return the (schedule) space of "build".
919 * If "internal" is set, then this space is the space of the internal
920 * representation of the entire schedule, including those parts for
921 * which no code has been generated yet.
923 * If "internal" is not set, then this space is the external representation
924 * of the loops generated so far.
926 __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
927 int internal)
929 int i;
930 int dim;
931 isl_space *space;
933 if (!build)
934 return NULL;
936 space = isl_set_get_space(build->domain);
937 if (internal)
938 return space;
940 if (!isl_ast_build_need_schedule_map(build))
941 return space;
943 dim = isl_set_dim(build->domain, isl_dim_set);
944 space = isl_space_drop_dims(space, isl_dim_set,
945 build->depth, dim - build->depth);
946 for (i = build->depth - 1; i >= 0; --i)
947 if (isl_ast_build_has_affine_value(build, i))
948 space = isl_space_drop_dims(space, isl_dim_set, i, 1);
950 return space;
953 /* Return the external representation of the schedule space of "build",
954 * i.e., a space with a dimension for each loop generated so far,
955 * with the names of the dimensions set to the loop iterators.
957 __isl_give isl_space *isl_ast_build_get_schedule_space(
958 __isl_keep isl_ast_build *build)
960 isl_space *space;
961 int i, skip;
963 if (!build)
964 return NULL;
966 space = isl_ast_build_get_space(build, 0);
968 skip = 0;
969 for (i = 0; i < build->depth; ++i) {
970 isl_id *id;
972 if (isl_ast_build_has_affine_value(build, i)) {
973 skip++;
974 continue;
977 id = isl_ast_build_get_iterator_id(build, i);
978 space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
981 return space;
984 /* Return the current schedule, as stored in build->executed, in terms
985 * of the external schedule domain.
987 __isl_give isl_union_map *isl_ast_build_get_schedule(
988 __isl_keep isl_ast_build *build)
990 isl_union_map *executed;
991 isl_union_map *schedule;
993 if (!build)
994 return NULL;
996 executed = isl_union_map_copy(build->executed);
997 if (isl_ast_build_need_schedule_map(build)) {
998 isl_map *proj = isl_ast_build_get_schedule_map(build);
999 executed = isl_union_map_apply_domain(executed,
1000 isl_union_map_from_map(proj));
1002 schedule = isl_union_map_reverse(executed);
1004 return schedule;
1007 /* Return the iterator attached to the internal schedule dimension "pos".
1009 __isl_give isl_id *isl_ast_build_get_iterator_id(
1010 __isl_keep isl_ast_build *build, int pos)
1012 if (!build)
1013 return NULL;
1015 return isl_id_list_get_id(build->iterators, pos);
1018 /* Set the stride and offset of the current dimension to the given
1019 * value and expression.
1021 * If we had already found a stride before, then the two strides
1022 * are combined into a single stride.
1024 * In particular, if the new stride information is of the form
1026 * i = f + s (...)
1028 * and the old stride information is of the form
1030 * i = f2 + s2 (...)
1032 * then we compute the extended gcd of s and s2
1034 * a s + b s2 = g,
1036 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1037 * and the second with t2 = a s1/g.
1038 * This results in
1040 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1042 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1043 * is the combined stride.
1045 static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1046 isl_int stride, __isl_take isl_aff *offset)
1048 int pos;
1050 build = isl_ast_build_cow(build);
1051 if (!build || !offset)
1052 goto error;
1054 pos = build->depth;
1056 if (isl_ast_build_has_stride(build, pos)) {
1057 isl_int stride2, a, b, g;
1058 isl_aff *offset2;
1060 isl_int_init(stride2);
1061 isl_int_init(a);
1062 isl_int_init(b);
1063 isl_int_init(g);
1065 isl_vec_get_element(build->strides, pos, &stride2);
1066 isl_int_gcdext(g, a, b, stride, stride2);
1067 isl_int_mul(a, a, stride);
1068 isl_int_divexact(a, a, g);
1069 isl_int_divexact(stride2, stride2, g);
1070 isl_int_mul(b, b, stride2);
1071 isl_int_mul(stride, stride, stride2);
1073 offset2 = isl_multi_aff_get_aff(build->offsets, pos);
1074 offset2 = isl_aff_scale(offset2, a);
1075 offset = isl_aff_scale(offset, b);
1076 offset = isl_aff_add(offset, offset2);
1078 isl_int_clear(stride2);
1079 isl_int_clear(a);
1080 isl_int_clear(b);
1081 isl_int_clear(g);
1084 build->strides = isl_vec_set_element(build->strides, pos, stride);
1085 build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1086 if (!build->strides || !build->offsets)
1087 return isl_ast_build_free(build);
1089 return build;
1090 error:
1091 isl_aff_free(offset);
1092 return isl_ast_build_free(build);
1095 /* Return a set expressing the stride constraint at the current depth.
1097 * In particular, if the current iterator (i) is known to attain values
1099 * f + s a
1101 * where f is the offset and s is the stride, then the returned set
1102 * expresses the constraint
1104 * (f - i) mod s = 0
1106 __isl_give isl_set *isl_ast_build_get_stride_constraint(
1107 __isl_keep isl_ast_build *build)
1109 isl_aff *aff;
1110 isl_set *set;
1111 isl_int stride;
1112 int pos;
1114 if (!build)
1115 return NULL;
1117 pos = build->depth;
1119 if (!isl_ast_build_has_stride(build, pos))
1120 return isl_set_universe(isl_ast_build_get_space(build, 1));
1122 isl_int_init(stride);
1124 isl_ast_build_get_stride(build, pos, &stride);
1125 aff = isl_ast_build_get_offset(build, pos);
1126 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1127 aff = isl_aff_mod(aff, stride);
1128 set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1130 isl_int_clear(stride);
1132 return set;
1135 /* Return the expansion implied by the stride and offset at the current
1136 * depth.
1138 * That is, return the mapping
1140 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1141 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1143 * where s is the stride at the current depth d and offset(i) is
1144 * the corresponding offset.
1146 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1147 __isl_keep isl_ast_build *build)
1149 isl_space *space;
1150 isl_multi_aff *ma;
1151 int pos;
1152 isl_aff *aff, *offset;
1153 isl_int stride;
1155 if (!build)
1156 return NULL;
1158 pos = isl_ast_build_get_depth(build);
1159 space = isl_ast_build_get_space(build, 1);
1160 space = isl_space_map_from_set(space);
1161 ma = isl_multi_aff_identity(space);
1163 if (!isl_ast_build_has_stride(build, pos))
1164 return ma;
1166 isl_int_init(stride);
1167 offset = isl_ast_build_get_offset(build, pos);
1168 isl_ast_build_get_stride(build, pos, &stride);
1169 aff = isl_multi_aff_get_aff(ma, pos);
1170 aff = isl_aff_scale(aff, stride);
1171 aff = isl_aff_add(aff, offset);
1172 ma = isl_multi_aff_set_aff(ma, pos, aff);
1173 isl_int_clear(stride);
1175 return ma;
1178 /* Add constraints corresponding to any previously detected
1179 * stride on the current dimension to build->domain.
1181 __isl_give isl_ast_build *isl_ast_build_include_stride(
1182 __isl_take isl_ast_build *build)
1184 isl_set *set;
1186 if (!build)
1187 return NULL;
1188 if (!isl_ast_build_has_stride(build, build->depth))
1189 return build;
1190 build = isl_ast_build_cow(build);
1191 if (!build)
1192 return NULL;
1194 set = isl_ast_build_get_stride_constraint(build);
1196 build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1197 build->generated = isl_set_intersect(build->generated, set);
1198 if (!build->domain || !build->generated)
1199 return isl_ast_build_free(build);
1201 return build;
1204 /* Information used inside detect_stride.
1206 * "build" may be updated by detect_stride to include stride information.
1207 * "pos" is equal to build->depth.
1209 struct isl_detect_stride_data {
1210 isl_ast_build *build;
1211 int pos;
1214 /* Check if constraint "c" imposes any stride on dimension data->pos
1215 * and, if so, update the stride information in data->build.
1217 * In order to impose a stride on the dimension, "c" needs to be an equality
1218 * and it needs to involve the dimension. Note that "c" may also be
1219 * a div constraint and thus an inequality that we cannot use.
1221 * Let c be of the form
1223 * h(p) + g * v * i + g * stride * f(alpha) = 0
1225 * with h(p) an expression in terms of the parameters and outer dimensions
1226 * and f(alpha) an expression in terms of the existentially quantified
1227 * variables. Note that the inner dimensions have been eliminated so
1228 * they do not appear in "c".
1230 * If "stride" is not zero and not one, then it represents a non-trivial stride
1231 * on "i". We compute a and b such that
1233 * a v + b stride = 1
1235 * We have
1237 * g v i = -h(p) + g stride f(alpha)
1239 * a g v i = -a h(p) + g stride f(alpha)
1241 * a g v i + b g stride i = -a h(p) + g stride * (...)
1243 * g i = -a h(p) + g stride * (...)
1245 * i = -a h(p)/g + stride * (...)
1247 * The expression "-a h(p)/g" can therefore be used as offset.
1249 static int detect_stride(__isl_take isl_constraint *c, void *user)
1251 struct isl_detect_stride_data *data = user;
1252 int i, n_div;
1253 isl_int v, gcd, stride, a, b, m;
1255 if (!isl_constraint_is_equality(c) ||
1256 !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
1257 isl_constraint_free(c);
1258 return 0;
1261 isl_int_init(a);
1262 isl_int_init(b);
1263 isl_int_init(v);
1264 isl_int_init(m);
1265 isl_int_init(gcd);
1266 isl_int_init(stride);
1268 isl_int_set_si(gcd, 0);
1269 n_div = isl_constraint_dim(c, isl_dim_div);
1270 for (i = 0; i < n_div; ++i) {
1271 isl_constraint_get_coefficient(c, isl_dim_div, i, &v);
1272 isl_int_gcd(gcd, gcd, v);
1275 isl_constraint_get_coefficient(c, isl_dim_set, data->pos, &v);
1276 isl_int_gcd(m, v, gcd);
1277 isl_int_divexact(stride, gcd, m);
1278 isl_int_divexact(v, v, m);
1280 if (!isl_int_is_zero(stride) && !isl_int_is_one(stride)) {
1281 isl_aff *aff;
1283 isl_int_gcdext(gcd, a, b, v, stride);
1285 aff = isl_constraint_get_aff(c);
1286 for (i = 0; i < n_div; ++i)
1287 aff = isl_aff_set_coefficient_si(aff,
1288 isl_dim_div, i, 0);
1289 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
1290 isl_int_neg(a, a);
1291 aff = isl_aff_scale(aff, a);
1292 aff = isl_aff_scale_down(aff, m);
1293 data->build = set_stride(data->build, stride, aff);
1296 isl_int_clear(stride);
1297 isl_int_clear(gcd);
1298 isl_int_clear(m);
1299 isl_int_clear(v);
1300 isl_int_clear(b);
1301 isl_int_clear(a);
1303 isl_constraint_free(c);
1304 return 0;
1307 /* Check if the constraints in "set" imply any stride on the current
1308 * dimension and, if so, record the stride information in "build"
1309 * and return the updated "build".
1311 * We compute the affine hull and then check if any of the constraints
1312 * in the hull imposes any stride on the current dimension.
1314 * We assume that inner dimensions have been eliminated from "set"
1315 * by the caller. This is needed because the common stride
1316 * may be imposed by different inner dimensions on different parts of
1317 * the domain.
1319 __isl_give isl_ast_build *isl_ast_build_detect_strides(
1320 __isl_take isl_ast_build *build, __isl_take isl_set *set)
1322 isl_basic_set *hull;
1323 struct isl_detect_stride_data data;
1325 if (!build)
1326 goto error;
1328 data.build = build;
1329 data.pos = isl_ast_build_get_depth(build);
1330 hull = isl_set_affine_hull(set);
1332 if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1333 data.build = isl_ast_build_free(data.build);
1335 isl_basic_set_free(hull);
1336 return data.build;
1337 error:
1338 isl_set_free(set);
1339 return NULL;
1342 struct isl_ast_build_involves_data {
1343 int depth;
1344 int involves;
1347 /* Check if "map" involves the input dimension data->depth.
1349 static int involves_depth(__isl_take isl_map *map, void *user)
1351 struct isl_ast_build_involves_data *data = user;
1353 data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1354 isl_map_free(map);
1356 if (data->involves < 0 || data->involves)
1357 return -1;
1358 return 0;
1361 /* Do any options depend on the value of the dimension at the current depth?
1363 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1365 struct isl_ast_build_involves_data data;
1367 if (!build)
1368 return -1;
1370 data.depth = build->depth;
1371 data.involves = 0;
1373 if (isl_union_map_foreach_map(build->options,
1374 &involves_depth, &data) < 0) {
1375 if (data.involves < 0 || !data.involves)
1376 return -1;
1379 return data.involves;
1382 /* Construct the map
1384 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1386 * with "space" the parameter space of the constructed map.
1388 static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1389 int pos)
1391 isl_constraint *c;
1392 isl_basic_map *bmap1, *bmap2;
1394 space = isl_space_set_from_params(space);
1395 space = isl_space_add_dims(space, isl_dim_set, 1);
1396 space = isl_space_map_from_set(space);
1397 c = isl_equality_alloc(isl_local_space_from_space(space));
1398 c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1399 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1400 bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1401 c = isl_constraint_set_constant_si(c, 1);
1402 bmap2 = isl_basic_map_from_constraint(c);
1404 bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1405 bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1407 return isl_basic_map_union(bmap1, bmap2);
1410 static const char *option_str[] = {
1411 [atomic] = "atomic",
1412 [unroll] = "unroll",
1413 [separate] = "separate"
1416 /* Update the "options" to reflect the insertion of a dimension
1417 * at position "pos" in the schedule domain space.
1418 * "space" is the original domain space before the insertion and
1419 * may be named and/or structured.
1421 * The (relevant) input options all have "space" as domain, which
1422 * has to be mapped to the extended space.
1423 * The values of the ranges also refer to the schedule domain positions
1424 * and they therefore also need to be adjusted. In particular, values
1425 * smaller than pos do not need to change, while values greater than or
1426 * equal to pos need to be incremented.
1427 * That is, we need to apply the following map.
1429 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1430 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1431 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1432 * separation_class[[i] -> [c]]
1433 * -> separation_class[[i] -> [c]] : i < pos;
1434 * separation_class[[i] -> [c]]
1435 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1437 static __isl_give isl_union_map *options_insert_dim(
1438 __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1440 isl_map *map;
1441 isl_union_map *insertion;
1442 enum isl_ast_build_domain_type type;
1443 const char *name = "separation_class";
1445 space = isl_space_map_from_set(space);
1446 map = isl_map_identity(space);
1447 map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1448 options = isl_union_map_apply_domain(options,
1449 isl_union_map_from_map(map));
1451 if (!options)
1452 return NULL;
1454 map = construct_insertion_map(isl_union_map_get_space(options), pos);
1456 insertion = isl_union_map_empty(isl_union_map_get_space(options));
1458 for (type = atomic; type <= separate; ++type) {
1459 isl_map *map_type = isl_map_copy(map);
1460 const char *name = option_str[type];
1461 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1462 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1463 insertion = isl_union_map_add_map(insertion, map_type);
1466 map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1467 map = isl_map_set_tuple_name(map, isl_dim_in, name);
1468 map = isl_map_set_tuple_name(map, isl_dim_out, name);
1469 insertion = isl_union_map_add_map(insertion, map);
1471 options = isl_union_map_apply_range(options, insertion);
1473 return options;
1476 /* Insert a single dimension in the schedule domain at position "pos".
1477 * The new dimension is given an isl_id with the empty string as name.
1479 * The main difficulty is updating build->options to reflect the
1480 * extra dimension. This is handled in options_insert_dim.
1482 * Note that because of the dimension manipulations, the resulting
1483 * schedule domain space will always be unnamed and unstructured.
1484 * However, the original schedule domain space may be named and/or
1485 * structured, so we have to take this possibility into account
1486 * while performing the transformations.
1488 __isl_give isl_ast_build *isl_ast_build_insert_dim(
1489 __isl_take isl_ast_build *build, int pos)
1491 isl_ctx *ctx;
1492 isl_space *space, *ma_space;
1493 isl_id *id;
1494 isl_multi_aff *ma;
1496 build = isl_ast_build_cow(build);
1497 if (!build)
1498 return NULL;
1500 ctx = isl_ast_build_get_ctx(build);
1501 id = isl_id_alloc(ctx, "", NULL);
1502 space = isl_ast_build_get_space(build, 1);
1503 build->iterators = isl_id_list_insert(build->iterators, pos, id);
1504 build->domain = isl_set_insert_dims(build->domain,
1505 isl_dim_set, pos, 1);
1506 build->generated = isl_set_insert_dims(build->generated,
1507 isl_dim_set, pos, 1);
1508 build->pending = isl_set_insert_dims(build->pending,
1509 isl_dim_set, pos, 1);
1510 build->strides = isl_vec_insert_els(build->strides, pos, 1);
1511 build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1512 ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1513 ma_space = isl_space_set_from_params(ma_space);
1514 ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1515 ma_space = isl_space_map_from_set(ma_space);
1516 ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1517 build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1518 ma = isl_multi_aff_identity(ma_space);
1519 build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1520 build->options = options_insert_dim(build->options, space, pos);
1522 if (!build->iterators || !build->domain || !build->generated ||
1523 !build->pending || !build->values ||
1524 !build->strides || !build->offsets || !build->options)
1525 return isl_ast_build_free(build);
1527 return build;
1530 /* Scale down the current dimension by a factor of "m".
1531 * "umap" is an isl_union_map that implements the scaling down.
1532 * That is, it is of the form
1534 * { [.... i ....] -> [.... i' ....] : i = m i' }
1536 * This function is called right after the strides have been
1537 * detected, but before any constraints on the current dimension
1538 * have been included in build->domain.
1539 * We therefore only need to update stride, offset and the options.
1541 __isl_give isl_ast_build *isl_ast_build_scale_down(
1542 __isl_take isl_ast_build *build, isl_int m,
1543 __isl_take isl_union_map *umap)
1545 isl_aff *aff;
1546 isl_int v;
1547 int depth;
1549 build = isl_ast_build_cow(build);
1550 if (!build || !umap)
1551 goto error;
1553 depth = build->depth;
1555 isl_int_init(v);
1556 if (isl_vec_get_element(build->strides, depth, &v) < 0)
1557 build->strides = isl_vec_free(build->strides);
1558 isl_int_divexact(v, v, m);
1559 build->strides = isl_vec_set_element(build->strides, depth, v);
1560 isl_int_clear(v);
1562 aff = isl_multi_aff_get_aff(build->offsets, depth);
1563 aff = isl_aff_scale_down(aff, m);
1564 build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1565 build->options = isl_union_map_apply_domain(build->options, umap);
1566 if (!build->strides || !build->offsets || !build->options)
1567 return isl_ast_build_free(build);
1569 return build;
1570 error:
1571 isl_union_map_free(umap);
1572 return isl_ast_build_free(build);
1575 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1576 * If an isl_id with such a name already appears among the parameters
1577 * in build->domain, then adjust the name to "c%d_%d".
1579 static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1580 __isl_keep isl_ast_build *build)
1582 int i;
1583 isl_id_list *names;
1585 names = isl_id_list_alloc(ctx, n);
1586 for (i = 0; i < n; ++i) {
1587 isl_id *id;
1589 id = generate_name(ctx, first + i, build);
1590 names = isl_id_list_add(names, id);
1593 return names;
1596 /* Embed "options" into the given isl_ast_build space.
1598 * This function is called from within a nested call to
1599 * isl_ast_build_ast_from_schedule.
1600 * "options" refers to the additional schedule,
1601 * while space refers to both the space of the outer isl_ast_build and
1602 * that of the additional schedule.
1603 * Specifically, space is of the form
1605 * [I -> S]
1607 * while options lives in the space(s)
1609 * S -> *
1611 * We compute
1613 * [I -> S] -> S
1615 * and compose this with options, to obtain the new options
1616 * living in the space(s)
1618 * [I -> S] -> *
1620 static __isl_give isl_union_map *embed_options(
1621 __isl_take isl_union_map *options, __isl_take isl_space *space)
1623 isl_map *map;
1625 map = isl_map_universe(isl_space_unwrap(space));
1626 map = isl_map_range_map(map);
1628 options = isl_union_map_apply_range(
1629 isl_union_map_from_map(map), options);
1631 return options;
1634 /* Update "build" for use in a (possibly nested) code generation. That is,
1635 * extend "build" from an AST build on some domain O to an AST build
1636 * on domain [O -> S], with S corresponding to "space".
1637 * If the original domain is a parameter domain, then the new domain is
1638 * simply S.
1639 * "iterators" is a list of iterators for S, but the number of elements
1640 * may be smaller or greater than the number of set dimensions of S.
1641 * If "keep_iterators" is set, then any extra ids in build->iterators
1642 * are reused for S. Otherwise, these extra ids are dropped.
1644 * We first update build->outer_pos to the current depth.
1645 * This depth is zero in case this is the outermost code generation.
1647 * We then add additional ids such that the number of iterators is at least
1648 * equal to the dimension of the new build domain.
1650 * If the original domain is parametric, then we are constructing
1651 * an isl_ast_build for the outer code generation and we pass control
1652 * to isl_ast_build_init.
1654 * Otherwise, we adjust the fields of "build" to include "space".
1656 __isl_give isl_ast_build *isl_ast_build_product(
1657 __isl_take isl_ast_build *build, __isl_take isl_space *space)
1659 isl_ctx *ctx;
1660 isl_vec *strides;
1661 isl_set *set;
1662 isl_multi_aff *embedding;
1663 int dim, n_it;
1665 build = isl_ast_build_cow(build);
1666 if (!build)
1667 goto error;
1669 build->outer_pos = build->depth;
1671 ctx = isl_ast_build_get_ctx(build);
1672 dim = isl_set_dim(build->domain, isl_dim_set);
1673 dim += isl_space_dim(space, isl_dim_set);
1674 n_it = isl_id_list_n_id(build->iterators);
1675 if (n_it < dim) {
1676 isl_id_list *l;
1677 l = generate_names(ctx, dim - n_it, n_it, build);
1678 build->iterators = isl_id_list_concat(build->iterators, l);
1681 if (isl_set_is_params(build->domain))
1682 return isl_ast_build_init(build, space);
1684 set = isl_set_universe(isl_space_copy(space));
1685 build->domain = isl_set_product(build->domain, isl_set_copy(set));
1686 build->pending = isl_set_product(build->pending, isl_set_copy(set));
1687 build->generated = isl_set_product(build->generated, set);
1689 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1690 strides = isl_vec_set_si(strides, 1);
1691 build->strides = isl_vec_concat(build->strides, strides);
1693 space = isl_space_map_from_set(space);
1694 build->offsets = isl_multi_aff_align_params(build->offsets,
1695 isl_space_copy(space));
1696 build->offsets = isl_multi_aff_product(build->offsets,
1697 isl_multi_aff_zero(isl_space_copy(space)));
1698 build->values = isl_multi_aff_align_params(build->values,
1699 isl_space_copy(space));
1700 embedding = isl_multi_aff_identity(space);
1701 build->values = isl_multi_aff_product(build->values, embedding);
1703 space = isl_ast_build_get_space(build, 1);
1704 build->options = embed_options(build->options, space);
1706 if (!build->iterators || !build->domain || !build->generated ||
1707 !build->pending || !build->values ||
1708 !build->strides || !build->offsets || !build->options)
1709 return isl_ast_build_free(build);
1711 return build;
1712 error:
1713 isl_ast_build_free(build);
1714 isl_space_free(space);
1715 return NULL;
1718 /* Does "aff" only attain non-negative values over build->domain?
1719 * That is, does it not attain any negative values?
1721 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
1722 __isl_keep isl_aff *aff)
1724 isl_set *test;
1725 int empty;
1727 if (!build)
1728 return -1;
1730 aff = isl_aff_copy(aff);
1731 test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
1732 test = isl_set_intersect(test, isl_set_copy(build->domain));
1733 empty = isl_set_is_empty(test);
1734 isl_set_free(test);
1736 return empty;
1739 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1741 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
1743 isl_int v;
1744 int has_stride;
1746 if (!build)
1747 return -1;
1749 isl_int_init(v);
1750 isl_vec_get_element(build->strides, pos, &v);
1751 has_stride = !isl_int_is_one(v);
1752 isl_int_clear(v);
1754 return has_stride;
1757 /* Given that the dimension at position "pos" takes on values
1759 * f + s a
1761 * with a an integer, return s through *stride.
1763 int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
1764 isl_int *stride)
1766 if (!build)
1767 return -1;
1769 isl_vec_get_element(build->strides, pos, stride);
1771 return 0;
1774 /* Given that the dimension at position "pos" takes on values
1776 * f + s a
1778 * with a an integer, return f.
1780 __isl_give isl_aff *isl_ast_build_get_offset(
1781 __isl_keep isl_ast_build *build, int pos)
1783 if (!build)
1784 return NULL;
1786 return isl_multi_aff_get_aff(build->offsets, pos);
1789 /* Is the dimension at position "pos" known to attain only a single
1790 * value that, moreover, can be described by a single affine expression
1791 * in terms of the outer dimensions and parameters?
1793 * If not, then the correponding affine expression in build->values
1794 * is set to be equal to the same input dimension.
1795 * Otherwise, it is set to the requested expression in terms of
1796 * outer dimensions and parameters.
1798 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
1799 int pos)
1801 isl_aff *aff;
1802 int involves;
1804 if (!build)
1805 return -1;
1807 aff = isl_multi_aff_get_aff(build->values, pos);
1808 involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
1809 isl_aff_free(aff);
1811 if (involves < 0)
1812 return -1;
1814 return !involves;
1817 /* Plug in the known values (fixed affine expressions in terms of
1818 * parameters and outer loop iterators) of all loop iterators
1819 * in the domain of "umap".
1821 * We simply precompose "umap" with build->values.
1823 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
1824 __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
1826 isl_multi_aff *values;
1828 if (!build)
1829 return isl_union_map_free(umap);
1831 values = isl_multi_aff_copy(build->values);
1832 umap = isl_union_map_preimage_domain_multi_aff(umap, values);
1834 return umap;
1837 /* Is the current dimension known to attain only a single value?
1839 int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
1841 if (!build)
1842 return -1;
1844 return build->value != NULL;
1847 /* Simplify the basic set "bset" based on what we know about
1848 * the iterators of already generated loops.
1850 * "bset" is assumed to live in the (internal) schedule domain.
1852 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
1853 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1855 if (!build)
1856 goto error;
1858 bset = isl_basic_set_preimage_multi_aff(bset,
1859 isl_multi_aff_copy(build->values));
1860 bset = isl_basic_set_gist(bset,
1861 isl_set_simple_hull(isl_set_copy(build->domain)));
1863 return bset;
1864 error:
1865 isl_basic_set_free(bset);
1866 return NULL;
1869 /* Simplify the set "set" based on what we know about
1870 * the iterators of already generated loops.
1872 * "set" is assumed to live in the (internal) schedule domain.
1874 __isl_give isl_set *isl_ast_build_compute_gist(
1875 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1877 if (!build)
1878 goto error;
1880 set = isl_set_preimage_multi_aff(set,
1881 isl_multi_aff_copy(build->values));
1882 set = isl_set_gist(set, isl_set_copy(build->domain));
1884 return set;
1885 error:
1886 isl_set_free(set);
1887 return NULL;
1890 /* Simplify the map "map" based on what we know about
1891 * the iterators of already generated loops.
1893 * The domain of "map" is assumed to live in the (internal) schedule domain.
1895 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
1896 __isl_keep isl_ast_build *build, __isl_take isl_map *map)
1898 if (!build)
1899 goto error;
1901 map = isl_map_gist_domain(map, isl_set_copy(build->domain));
1903 return map;
1904 error:
1905 isl_map_free(map);
1906 return NULL;
1909 /* Simplify the affine expression "aff" based on what we know about
1910 * the iterators of already generated loops.
1912 * The domain of "aff" is assumed to live in the (internal) schedule domain.
1914 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
1915 __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
1917 if (!build)
1918 goto error;
1920 aff = isl_aff_gist(aff, isl_set_copy(build->domain));
1922 return aff;
1923 error:
1924 isl_aff_free(aff);
1925 return NULL;
1928 /* Simplify the piecewise affine expression "aff" based on what we know about
1929 * the iterators of already generated loops.
1931 * The domain of "pa" is assumed to live in the (internal) schedule domain.
1933 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
1934 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1936 if (!build)
1937 goto error;
1939 pa = isl_pw_aff_pullback_multi_aff(pa,
1940 isl_multi_aff_copy(build->values));
1941 pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
1943 return pa;
1944 error:
1945 isl_pw_aff_free(pa);
1946 return NULL;
1949 /* Simplify the piecewise multi-affine expression "aff" based on what
1950 * we know about the iterators of already generated loops.
1952 * The domain of "pma" is assumed to live in the (internal) schedule domain.
1954 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
1955 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1957 if (!build)
1958 goto error;
1960 pma = isl_pw_multi_aff_pullback_multi_aff(pma,
1961 isl_multi_aff_copy(build->values));
1962 pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
1964 return pma;
1965 error:
1966 isl_pw_multi_aff_free(pma);
1967 return NULL;
1970 /* Extract the schedule domain of the given type from build->options
1971 * at the current depth.
1973 * In particular, find the subset of build->options that is of
1974 * the following form
1976 * schedule_domain -> type[depth]
1978 * and return the corresponding domain, after eliminating inner dimensions
1979 * and divs that depend on the current dimension.
1981 * Note that the domain of build->options has been reformulated
1982 * in terms of the internal build space in embed_options,
1983 * but the position is still that within the current code generation.
1985 __isl_give isl_set *isl_ast_build_get_option_domain(
1986 __isl_keep isl_ast_build *build,
1987 enum isl_ast_build_domain_type type)
1989 const char *name;
1990 isl_space *space;
1991 isl_map *option;
1992 isl_set *domain;
1993 int local_pos;
1995 if (!build)
1996 return NULL;
1998 name = option_str[type];
1999 local_pos = build->depth - build->outer_pos;
2001 space = isl_ast_build_get_space(build, 1);
2002 space = isl_space_from_domain(space);
2003 space = isl_space_add_dims(space, isl_dim_out, 1);
2004 space = isl_space_set_tuple_name(space, isl_dim_out, name);
2006 option = isl_union_map_extract_map(build->options, space);
2007 option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2009 domain = isl_map_domain(option);
2010 domain = isl_ast_build_eliminate(build, domain);
2012 return domain;
2015 /* Extract the separation class mapping at the current depth.
2017 * In particular, find and return the subset of build->options that is of
2018 * the following form
2020 * schedule_domain -> separation_class[[depth] -> [class]]
2022 * The caller is expected to eliminate inner dimensions from the domain.
2024 * Note that the domain of build->options has been reformulated
2025 * in terms of the internal build space in embed_options,
2026 * but the position is still that within the current code generation.
2028 __isl_give isl_map *isl_ast_build_get_separation_class(
2029 __isl_keep isl_ast_build *build)
2031 isl_ctx *ctx;
2032 isl_space *space_sep, *space;
2033 isl_map *res;
2034 int local_pos;
2036 if (!build)
2037 return NULL;
2039 local_pos = build->depth - build->outer_pos;
2040 ctx = isl_ast_build_get_ctx(build);
2041 space_sep = isl_space_alloc(ctx, 0, 1, 1);
2042 space_sep = isl_space_wrap(space_sep);
2043 space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2044 "separation_class");
2045 space = isl_ast_build_get_space(build, 1);
2046 space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2047 space = isl_space_map_from_domain_and_range(space, space_sep);
2049 res = isl_union_map_extract_map(build->options, space);
2050 res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2051 res = isl_map_coalesce(res);
2053 return res;
2056 /* Eliminate dimensions inner to the current dimension.
2058 __isl_give isl_set *isl_ast_build_eliminate_inner(
2059 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2061 int dim;
2062 int depth;
2064 if (!build)
2065 return isl_set_free(set);
2067 dim = isl_set_dim(set, isl_dim_set);
2068 depth = build->depth;
2069 set = isl_set_detect_equalities(set);
2070 set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2072 return set;
2075 /* Eliminate unknown divs and divs that depend on the current dimension.
2077 * Note that during the elimination of unknown divs, we may discover
2078 * an explicit representation of some other unknown divs, which may
2079 * depend on the current dimension. We therefore need to eliminate
2080 * unknown divs first.
2082 __isl_give isl_set *isl_ast_build_eliminate_divs(
2083 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2085 int depth;
2087 if (!build)
2088 return isl_set_free(set);
2090 set = isl_set_remove_unknown_divs(set);
2091 depth = build->depth;
2092 set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2094 return set;
2097 /* Eliminate dimensions inner to the current dimension as well as
2098 * unknown divs and divs that depend on the current dimension.
2099 * The result then consists only of constraints that are independent
2100 * of the current dimension and upper and lower bounds on the current
2101 * dimension.
2103 __isl_give isl_set *isl_ast_build_eliminate(
2104 __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2106 domain = isl_ast_build_eliminate_inner(build, domain);
2107 domain = isl_ast_build_eliminate_divs(build, domain);
2108 return domain;
2111 /* Replace build->single_valued by "sv".
2113 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2114 __isl_take isl_ast_build *build, int sv)
2116 if (!build)
2117 return build;
2118 if (build->single_valued == sv)
2119 return build;
2120 build = isl_ast_build_cow(build);
2121 if (!build)
2122 return build;
2123 build->single_valued = sv;
2125 return build;