isl_space_*_factor_*: fix typo in code
[isl.git] / isl_ast_codegen.c
blob2a61baa8b82e2a9a9b11df3365ff3d813da5984c
1 /*
2 * Copyright 2012-2014 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 <limits.h>
14 #include <isl/aff.h>
15 #include <isl/set.h>
16 #include <isl/ilp.h>
17 #include <isl/union_map.h>
18 #include <isl_sort.h>
19 #include <isl_tarjan.h>
20 #include <isl_ast_private.h>
21 #include <isl_ast_build_expr.h>
22 #include <isl_ast_build_private.h>
23 #include <isl_ast_graft_private.h>
25 /* Data used in generate_domain.
27 * "build" is the input build.
28 * "list" collects the results.
30 struct isl_generate_domain_data {
31 isl_ast_build *build;
33 isl_ast_graft_list *list;
36 static __isl_give isl_ast_graft_list *generate_next_level(
37 __isl_take isl_union_map *executed,
38 __isl_take isl_ast_build *build);
39 static __isl_give isl_ast_graft_list *generate_code(
40 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
41 int internal);
43 /* Generate an AST for a single domain based on
44 * the (non single valued) inverse schedule "executed".
46 * We extend the schedule with the iteration domain
47 * and continue generating through a call to generate_code.
49 * In particular, if executed has the form
51 * S -> D
53 * then we continue generating code on
55 * [S -> D] -> D
57 * The extended inverse schedule is clearly single valued
58 * ensuring that the nested generate_code will not reach this function,
59 * but will instead create calls to all elements of D that need
60 * to be executed from the current schedule domain.
62 static int generate_non_single_valued(__isl_take isl_map *executed,
63 struct isl_generate_domain_data *data)
65 isl_map *identity;
66 isl_ast_build *build;
67 isl_ast_graft_list *list;
69 build = isl_ast_build_copy(data->build);
71 identity = isl_set_identity(isl_map_range(isl_map_copy(executed)));
72 executed = isl_map_domain_product(executed, identity);
73 build = isl_ast_build_set_single_valued(build, 1);
75 list = generate_code(isl_union_map_from_map(executed), build, 1);
77 data->list = isl_ast_graft_list_concat(data->list, list);
79 return 0;
82 /* Call the at_each_domain callback, if requested by the user,
83 * after recording the current inverse schedule in the build.
85 static __isl_give isl_ast_graft *at_each_domain(__isl_take isl_ast_graft *graft,
86 __isl_keep isl_map *executed, __isl_keep isl_ast_build *build)
88 if (!graft || !build)
89 return isl_ast_graft_free(graft);
90 if (!build->at_each_domain)
91 return graft;
93 build = isl_ast_build_copy(build);
94 build = isl_ast_build_set_executed(build,
95 isl_union_map_from_map(isl_map_copy(executed)));
96 if (!build)
97 return isl_ast_graft_free(graft);
99 graft->node = build->at_each_domain(graft->node,
100 build, build->at_each_domain_user);
101 isl_ast_build_free(build);
103 if (!graft->node)
104 graft = isl_ast_graft_free(graft);
106 return graft;
109 /* Generate an AST for a single domain based on
110 * the inverse schedule "executed" and add it to data->list.
112 * If there is more than one domain element associated to the current
113 * schedule "time", then we need to continue the generation process
114 * in generate_non_single_valued.
115 * Note that the inverse schedule being single-valued may depend
116 * on constraints that are only available in the original context
117 * domain specified by the user. We therefore first introduce
118 * some of the constraints of data->build->domain. In particular,
119 * we intersect with a single-disjunct approximation of this set.
120 * We perform this approximation to avoid further splitting up
121 * the executed relation, possibly introducing a disjunctive guard
122 * on the statement.
124 * On the other hand, we only perform the test after having taken the gist
125 * of the domain as the resulting map is the one from which the call
126 * expression is constructed. Using this map to construct the call
127 * expression usually yields simpler results.
128 * Because we perform the single-valuedness test on the gisted map,
129 * we may in rare cases fail to recognize that the inverse schedule
130 * is single-valued. This becomes problematic if this happens
131 * from the recursive call through generate_non_single_valued
132 * as we would then end up in an infinite recursion.
133 * We therefore check if we are inside a call to generate_non_single_valued
134 * and revert to the ungisted map if the gisted map turns out not to be
135 * single-valued.
137 * Otherwise, we generate a call expression for the single executed
138 * domain element and put a guard around it based on the (simplified)
139 * domain of "executed".
141 * At this stage, any pending constraints in the build can no longer
142 * be simplified with respect to any enforced constraints since
143 * the call node does not have any enforced constraints.
144 * We therefore turn all pending constraints into guards
145 * (after simplifying them with respect to the already generated
146 * constraints) and add them to both the generated constraints
147 * and the guard of the constructed graft. This guard will ensure
148 * that the constraints are effectively generated.
150 * If the user has set an at_each_domain callback, it is called
151 * on the constructed call expression node.
153 static int generate_domain(__isl_take isl_map *executed, void *user)
155 struct isl_generate_domain_data *data = user;
156 isl_ast_build *build;
157 isl_ast_graft *graft;
158 isl_ast_graft_list *list;
159 isl_set *guard, *domain;
160 isl_map *map = NULL;
161 int empty, sv;
163 domain = isl_ast_build_get_domain(data->build);
164 domain = isl_set_from_basic_set(isl_set_simple_hull(domain));
165 executed = isl_map_intersect_domain(executed, domain);
166 empty = isl_map_is_empty(executed);
167 if (empty < 0)
168 goto error;
169 if (empty) {
170 isl_map_free(executed);
171 return 0;
174 executed = isl_map_coalesce(executed);
175 map = isl_map_copy(executed);
176 map = isl_ast_build_compute_gist_map_domain(data->build, map);
177 sv = isl_map_is_single_valued(map);
178 if (sv < 0)
179 goto error;
180 if (!sv) {
181 isl_map_free(map);
182 if (data->build->single_valued)
183 map = isl_map_copy(executed);
184 else
185 return generate_non_single_valued(executed, data);
187 guard = isl_map_domain(isl_map_copy(map));
188 guard = isl_set_compute_divs(guard);
189 guard = isl_set_intersect(guard,
190 isl_ast_build_get_pending(data->build));
191 guard = isl_set_coalesce(guard);
192 guard = isl_ast_build_specialize(data->build, guard);
193 guard = isl_set_gist(guard, isl_ast_build_get_generated(data->build));
195 build = isl_ast_build_copy(data->build);
196 build = isl_ast_build_replace_pending_by_guard(build,
197 isl_set_copy(guard));
198 graft = isl_ast_graft_alloc_domain(map, build);
199 graft = at_each_domain(graft, executed, build);
200 isl_ast_build_free(build);
201 isl_map_free(executed);
202 graft = isl_ast_graft_add_guard(graft, guard, data->build);
204 list = isl_ast_graft_list_from_ast_graft(graft);
205 data->list = isl_ast_graft_list_concat(data->list, list);
207 return 0;
208 error:
209 isl_map_free(map);
210 isl_map_free(executed);
211 return -1;
214 /* Call build->create_leaf to a create "leaf" node in the AST,
215 * encapsulate the result in an isl_ast_graft and return the result
216 * as a 1-element list.
218 * Note that the node returned by the user may be an entire tree.
220 * Since the node itself cannot enforce any constraints, we turn
221 * all pending constraints into guards and add them to the resulting
222 * graft to ensure that they will be generated.
224 * Before we pass control to the user, we first clear some information
225 * from the build that is (presumbably) only meaningful
226 * for the current code generation.
227 * This includes the create_leaf callback itself, so we make a copy
228 * of the build first.
230 static __isl_give isl_ast_graft_list *call_create_leaf(
231 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
233 isl_set *guard;
234 isl_ast_node *node;
235 isl_ast_graft *graft;
236 isl_ast_build *user_build;
238 guard = isl_ast_build_get_pending(build);
239 user_build = isl_ast_build_copy(build);
240 user_build = isl_ast_build_replace_pending_by_guard(user_build,
241 isl_set_copy(guard));
242 user_build = isl_ast_build_set_executed(user_build, executed);
243 user_build = isl_ast_build_clear_local_info(user_build);
244 if (!user_build)
245 node = NULL;
246 else
247 node = build->create_leaf(user_build, build->create_leaf_user);
248 graft = isl_ast_graft_alloc(node, build);
249 graft = isl_ast_graft_add_guard(graft, guard, build);
250 isl_ast_build_free(build);
251 return isl_ast_graft_list_from_ast_graft(graft);
254 /* Generate an AST after having handled the complete schedule
255 * of this call to the code generator.
257 * If the user has specified a create_leaf callback, control
258 * is passed to the user in call_create_leaf.
260 * Otherwise, we generate one or more calls for each individual
261 * domain in generate_domain.
263 static __isl_give isl_ast_graft_list *generate_inner_level(
264 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
266 isl_ctx *ctx;
267 struct isl_generate_domain_data data = { build };
269 if (!build || !executed)
270 goto error;
272 if (build->create_leaf)
273 return call_create_leaf(executed, build);
275 ctx = isl_union_map_get_ctx(executed);
276 data.list = isl_ast_graft_list_alloc(ctx, 0);
277 if (isl_union_map_foreach_map(executed, &generate_domain, &data) < 0)
278 data.list = isl_ast_graft_list_free(data.list);
280 if (0)
281 error: data.list = NULL;
282 isl_ast_build_free(build);
283 isl_union_map_free(executed);
284 return data.list;
287 /* Call the before_each_for callback, if requested by the user.
289 static __isl_give isl_ast_node *before_each_for(__isl_take isl_ast_node *node,
290 __isl_keep isl_ast_build *build)
292 isl_id *id;
294 if (!node || !build)
295 return isl_ast_node_free(node);
296 if (!build->before_each_for)
297 return node;
298 id = build->before_each_for(build, build->before_each_for_user);
299 node = isl_ast_node_set_annotation(node, id);
300 return node;
303 /* Call the after_each_for callback, if requested by the user.
305 static __isl_give isl_ast_graft *after_each_for(__isl_take isl_ast_graft *graft,
306 __isl_keep isl_ast_build *build)
308 if (!graft || !build)
309 return isl_ast_graft_free(graft);
310 if (!build->after_each_for)
311 return graft;
312 graft->node = build->after_each_for(graft->node, build,
313 build->after_each_for_user);
314 if (!graft->node)
315 return isl_ast_graft_free(graft);
316 return graft;
319 /* Plug in all the know values of the current and outer dimensions
320 * in the domain of "executed". In principle, we only need to plug
321 * in the known value of the current dimension since the values of
322 * outer dimensions have been plugged in already.
323 * However, it turns out to be easier to just plug in all known values.
325 static __isl_give isl_union_map *plug_in_values(
326 __isl_take isl_union_map *executed, __isl_keep isl_ast_build *build)
328 return isl_ast_build_substitute_values_union_map_domain(build,
329 executed);
332 /* Check if the constraint "c" is a lower bound on dimension "pos",
333 * an upper bound, or independent of dimension "pos".
335 static int constraint_type(isl_constraint *c, int pos)
337 if (isl_constraint_is_lower_bound(c, isl_dim_set, pos))
338 return 1;
339 if (isl_constraint_is_upper_bound(c, isl_dim_set, pos))
340 return 2;
341 return 0;
344 /* Compare the types of the constraints "a" and "b",
345 * resulting in constraints that are independent of "depth"
346 * to be sorted before the lower bounds on "depth", which in
347 * turn are sorted before the upper bounds on "depth".
349 static int cmp_constraint(__isl_keep isl_constraint *a,
350 __isl_keep isl_constraint *b, void *user)
352 int *depth = user;
353 int t1 = constraint_type(a, *depth);
354 int t2 = constraint_type(b, *depth);
356 return t1 - t2;
359 /* Extract a lower bound on dimension "pos" from constraint "c".
361 * If the constraint is of the form
363 * a x + f(...) >= 0
365 * then we essentially return
367 * l = ceil(-f(...)/a)
369 * However, if the current dimension is strided, then we need to make
370 * sure that the lower bound we construct is of the form
372 * f + s a
374 * with f the offset and s the stride.
375 * We therefore compute
377 * f + s * ceil((l - f)/s)
379 static __isl_give isl_aff *lower_bound(__isl_keep isl_constraint *c,
380 int pos, __isl_keep isl_ast_build *build)
382 isl_aff *aff;
384 aff = isl_constraint_get_bound(c, isl_dim_set, pos);
385 aff = isl_aff_ceil(aff);
387 if (isl_ast_build_has_stride(build, pos)) {
388 isl_aff *offset;
389 isl_val *stride;
391 offset = isl_ast_build_get_offset(build, pos);
392 stride = isl_ast_build_get_stride(build, pos);
394 aff = isl_aff_sub(aff, isl_aff_copy(offset));
395 aff = isl_aff_scale_down_val(aff, isl_val_copy(stride));
396 aff = isl_aff_ceil(aff);
397 aff = isl_aff_scale_val(aff, stride);
398 aff = isl_aff_add(aff, offset);
401 aff = isl_ast_build_compute_gist_aff(build, aff);
403 return aff;
406 /* Return the exact lower bound (or upper bound if "upper" is set)
407 * of "domain" as a piecewise affine expression.
409 * If we are computing a lower bound (of a strided dimension), then
410 * we need to make sure it is of the form
412 * f + s a
414 * where f is the offset and s is the stride.
415 * We therefore need to include the stride constraint before computing
416 * the minimum.
418 static __isl_give isl_pw_aff *exact_bound(__isl_keep isl_set *domain,
419 __isl_keep isl_ast_build *build, int upper)
421 isl_set *stride;
422 isl_map *it_map;
423 isl_pw_aff *pa;
424 isl_pw_multi_aff *pma;
426 domain = isl_set_copy(domain);
427 if (!upper) {
428 stride = isl_ast_build_get_stride_constraint(build);
429 domain = isl_set_intersect(domain, stride);
431 it_map = isl_ast_build_map_to_iterator(build, domain);
432 if (upper)
433 pma = isl_map_lexmax_pw_multi_aff(it_map);
434 else
435 pma = isl_map_lexmin_pw_multi_aff(it_map);
436 pa = isl_pw_multi_aff_get_pw_aff(pma, 0);
437 isl_pw_multi_aff_free(pma);
438 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
439 pa = isl_pw_aff_coalesce(pa);
441 return pa;
444 /* Callback for sorting the isl_pw_aff_list passed to reduce_list and
445 * remove_redundant_lower_bounds.
447 static int reduce_list_cmp(__isl_keep isl_pw_aff *a, __isl_keep isl_pw_aff *b,
448 void *user)
450 return isl_pw_aff_plain_cmp(a, b);
453 /* Given a list of lower bounds "list", remove those that are redundant
454 * with respect to the other bounds in "list" and the domain of "build".
456 * We first sort the bounds in the same way as they would be sorted
457 * by set_for_node_expressions so that we can try and remove the last
458 * bounds first.
460 * For a lower bound to be effective, there needs to be at least
461 * one domain element for which it is larger than all other lower bounds.
462 * For each lower bound we therefore intersect the domain with
463 * the conditions that it is larger than all other bounds and
464 * check whether the result is empty. If so, the bound can be removed.
466 static __isl_give isl_pw_aff_list *remove_redundant_lower_bounds(
467 __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
469 int i, j, n;
470 isl_set *domain;
472 list = isl_pw_aff_list_sort(list, &reduce_list_cmp, NULL);
473 if (!list)
474 return NULL;
476 n = isl_pw_aff_list_n_pw_aff(list);
477 if (n <= 1)
478 return list;
480 domain = isl_ast_build_get_domain(build);
482 for (i = n - 1; i >= 0; --i) {
483 isl_pw_aff *pa_i;
484 isl_set *domain_i;
485 int empty;
487 domain_i = isl_set_copy(domain);
488 pa_i = isl_pw_aff_list_get_pw_aff(list, i);
490 for (j = 0; j < n; ++j) {
491 isl_pw_aff *pa_j;
492 isl_set *better;
494 if (j == i)
495 continue;
497 pa_j = isl_pw_aff_list_get_pw_aff(list, j);
498 better = isl_pw_aff_gt_set(isl_pw_aff_copy(pa_i), pa_j);
499 domain_i = isl_set_intersect(domain_i, better);
502 empty = isl_set_is_empty(domain_i);
504 isl_set_free(domain_i);
505 isl_pw_aff_free(pa_i);
507 if (empty < 0)
508 goto error;
509 if (!empty)
510 continue;
511 list = isl_pw_aff_list_drop(list, i, 1);
512 n--;
515 isl_set_free(domain);
517 return list;
518 error:
519 isl_set_free(domain);
520 return isl_pw_aff_list_free(list);
523 /* Extract a lower bound on dimension "pos" from each constraint
524 * in "constraints" and return the list of lower bounds.
525 * If "constraints" has zero elements, then we extract a lower bound
526 * from "domain" instead.
528 * If the current dimension is strided, then the lower bound
529 * is adjusted by lower_bound to match the stride information.
530 * This modification may make one or more lower bounds redundant
531 * with respect to the other lower bounds. We therefore check
532 * for this condition and remove the redundant lower bounds.
534 static __isl_give isl_pw_aff_list *lower_bounds(
535 __isl_keep isl_constraint_list *constraints, int pos,
536 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
538 isl_ctx *ctx;
539 isl_pw_aff_list *list;
540 int i, n;
542 if (!build)
543 return NULL;
545 n = isl_constraint_list_n_constraint(constraints);
546 if (n == 0) {
547 isl_pw_aff *pa;
548 pa = exact_bound(domain, build, 0);
549 return isl_pw_aff_list_from_pw_aff(pa);
552 ctx = isl_ast_build_get_ctx(build);
553 list = isl_pw_aff_list_alloc(ctx,n);
555 for (i = 0; i < n; ++i) {
556 isl_aff *aff;
557 isl_constraint *c;
559 c = isl_constraint_list_get_constraint(constraints, i);
560 aff = lower_bound(c, pos, build);
561 isl_constraint_free(c);
562 list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
565 if (isl_ast_build_has_stride(build, pos))
566 list = remove_redundant_lower_bounds(list, build);
568 return list;
571 /* Extract an upper bound on dimension "pos" from each constraint
572 * in "constraints" and return the list of upper bounds.
573 * If "constraints" has zero elements, then we extract an upper bound
574 * from "domain" instead.
576 static __isl_give isl_pw_aff_list *upper_bounds(
577 __isl_keep isl_constraint_list *constraints, int pos,
578 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
580 isl_ctx *ctx;
581 isl_pw_aff_list *list;
582 int i, n;
584 n = isl_constraint_list_n_constraint(constraints);
585 if (n == 0) {
586 isl_pw_aff *pa;
587 pa = exact_bound(domain, build, 1);
588 return isl_pw_aff_list_from_pw_aff(pa);
591 ctx = isl_ast_build_get_ctx(build);
592 list = isl_pw_aff_list_alloc(ctx,n);
594 for (i = 0; i < n; ++i) {
595 isl_aff *aff;
596 isl_constraint *c;
598 c = isl_constraint_list_get_constraint(constraints, i);
599 aff = isl_constraint_get_bound(c, isl_dim_set, pos);
600 isl_constraint_free(c);
601 aff = isl_aff_floor(aff);
602 list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
605 return list;
608 /* Return an isl_ast_expr that performs the reduction of type "type"
609 * on AST expressions corresponding to the elements in "list".
611 * The list is assumed to contain at least one element.
612 * If the list contains exactly one element, then the returned isl_ast_expr
613 * simply computes that affine expression.
614 * If the list contains more than one element, then we sort it
615 * using a fairly abitrary but hopefully reasonably stable order.
617 static __isl_give isl_ast_expr *reduce_list(enum isl_ast_op_type type,
618 __isl_keep isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
620 int i, n;
621 isl_ctx *ctx;
622 isl_ast_expr *expr;
624 if (!list)
625 return NULL;
627 n = isl_pw_aff_list_n_pw_aff(list);
629 if (n == 1)
630 return isl_ast_build_expr_from_pw_aff_internal(build,
631 isl_pw_aff_list_get_pw_aff(list, 0));
633 ctx = isl_pw_aff_list_get_ctx(list);
634 expr = isl_ast_expr_alloc_op(ctx, type, n);
635 if (!expr)
636 return NULL;
638 list = isl_pw_aff_list_copy(list);
639 list = isl_pw_aff_list_sort(list, &reduce_list_cmp, NULL);
640 if (!list)
641 return isl_ast_expr_free(expr);
643 for (i = 0; i < n; ++i) {
644 isl_ast_expr *expr_i;
646 expr_i = isl_ast_build_expr_from_pw_aff_internal(build,
647 isl_pw_aff_list_get_pw_aff(list, i));
648 if (!expr_i)
649 goto error;
650 expr->u.op.args[i] = expr_i;
653 isl_pw_aff_list_free(list);
654 return expr;
655 error:
656 isl_pw_aff_list_free(list);
657 isl_ast_expr_free(expr);
658 return NULL;
661 /* Add guards implied by the "generated constraints",
662 * but not (necessarily) enforced by the generated AST to "guard".
663 * In particular, if there is any stride constraints,
664 * then add the guard implied by those constraints.
665 * If we have generated a degenerate loop, then add the guard
666 * implied by "bounds" on the outer dimensions, i.e., the guard
667 * that ensures that the single value actually exists.
668 * Since there may also be guards implied by a combination
669 * of these constraints, we first combine them before
670 * deriving the implied constraints.
672 static __isl_give isl_set *add_implied_guards(__isl_take isl_set *guard,
673 int degenerate, __isl_keep isl_basic_set *bounds,
674 __isl_keep isl_ast_build *build)
676 int depth, has_stride;
677 isl_space *space;
678 isl_set *dom, *set;
680 depth = isl_ast_build_get_depth(build);
681 has_stride = isl_ast_build_has_stride(build, depth);
682 if (!has_stride && !degenerate)
683 return guard;
685 space = isl_basic_set_get_space(bounds);
686 dom = isl_set_universe(space);
688 if (degenerate) {
689 bounds = isl_basic_set_copy(bounds);
690 bounds = isl_basic_set_drop_constraints_not_involving_dims(
691 bounds, isl_dim_set, depth, 1);
692 set = isl_set_from_basic_set(bounds);
693 dom = isl_set_intersect(dom, set);
696 if (has_stride) {
697 set = isl_ast_build_get_stride_constraint(build);
698 dom = isl_set_intersect(dom, set);
701 dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
702 dom = isl_ast_build_compute_gist(build, dom);
703 guard = isl_set_intersect(guard, dom);
705 return guard;
708 /* Update "graft" based on "sub_build" for the degenerate case.
710 * "build" is the build in which graft->node was created
711 * "sub_build" contains information about the current level itself,
712 * including the single value attained.
714 * We set the initialization part of the for loop to the single
715 * value attained by the current dimension.
716 * The increment and condition are not strictly needed as the are known
717 * to be "1" and "iterator <= value" respectively.
719 static __isl_give isl_ast_graft *refine_degenerate(
720 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build,
721 __isl_keep isl_ast_build *sub_build)
723 isl_pw_aff *value;
725 if (!graft || !sub_build)
726 return isl_ast_graft_free(graft);
728 value = isl_pw_aff_copy(sub_build->value);
730 graft->node->u.f.init = isl_ast_build_expr_from_pw_aff_internal(build,
731 value);
732 if (!graft->node->u.f.init)
733 return isl_ast_graft_free(graft);
735 return graft;
738 /* Return the intersection of constraints in "list" as a set.
740 static __isl_give isl_set *intersect_constraints(
741 __isl_keep isl_constraint_list *list)
743 int i, n;
744 isl_basic_set *bset;
746 n = isl_constraint_list_n_constraint(list);
747 if (n < 1)
748 isl_die(isl_constraint_list_get_ctx(list), isl_error_internal,
749 "expecting at least one constraint", return NULL);
751 bset = isl_basic_set_from_constraint(
752 isl_constraint_list_get_constraint(list, 0));
753 for (i = 1; i < n; ++i) {
754 isl_basic_set *bset_i;
756 bset_i = isl_basic_set_from_constraint(
757 isl_constraint_list_get_constraint(list, i));
758 bset = isl_basic_set_intersect(bset, bset_i);
761 return isl_set_from_basic_set(bset);
764 /* Compute the constraints on the outer dimensions enforced by
765 * graft->node and add those constraints to graft->enforced,
766 * in case the upper bound is expressed as a set "upper".
768 * In particular, if l(...) is a lower bound in "lower", and
770 * -a i + f(...) >= 0 or a i <= f(...)
772 * is an upper bound ocnstraint on the current dimension i,
773 * then the for loop enforces the constraint
775 * -a l(...) + f(...) >= 0 or a l(...) <= f(...)
777 * We therefore simply take each lower bound in turn, plug it into
778 * the upper bounds and compute the intersection over all lower bounds.
780 * If a lower bound is a rational expression, then
781 * isl_basic_set_preimage_multi_aff will force this rational
782 * expression to have only integer values. However, the loop
783 * itself does not enforce this integrality constraint. We therefore
784 * use the ceil of the lower bounds instead of the lower bounds themselves.
785 * Other constraints will make sure that the for loop is only executed
786 * when each of the lower bounds attains an integral value.
787 * In particular, potentially rational values only occur in
788 * lower_bound if the offset is a (seemingly) rational expression,
789 * but then outer conditions will make sure that this rational expression
790 * only attains integer values.
792 static __isl_give isl_ast_graft *set_enforced_from_set(
793 __isl_take isl_ast_graft *graft,
794 __isl_keep isl_pw_aff_list *lower, int pos, __isl_keep isl_set *upper)
796 isl_space *space;
797 isl_basic_set *enforced;
798 isl_pw_multi_aff *pma;
799 int i, n;
801 if (!graft || !lower)
802 return isl_ast_graft_free(graft);
804 space = isl_set_get_space(upper);
805 enforced = isl_basic_set_universe(isl_space_copy(space));
807 space = isl_space_map_from_set(space);
808 pma = isl_pw_multi_aff_identity(space);
810 n = isl_pw_aff_list_n_pw_aff(lower);
811 for (i = 0; i < n; ++i) {
812 isl_pw_aff *pa;
813 isl_set *enforced_i;
814 isl_basic_set *hull;
815 isl_pw_multi_aff *pma_i;
817 pa = isl_pw_aff_list_get_pw_aff(lower, i);
818 pa = isl_pw_aff_ceil(pa);
819 pma_i = isl_pw_multi_aff_copy(pma);
820 pma_i = isl_pw_multi_aff_set_pw_aff(pma_i, pos, pa);
821 enforced_i = isl_set_copy(upper);
822 enforced_i = isl_set_preimage_pw_multi_aff(enforced_i, pma_i);
823 hull = isl_set_simple_hull(enforced_i);
824 enforced = isl_basic_set_intersect(enforced, hull);
827 isl_pw_multi_aff_free(pma);
829 graft = isl_ast_graft_enforce(graft, enforced);
831 return graft;
834 /* Compute the constraints on the outer dimensions enforced by
835 * graft->node and add those constraints to graft->enforced,
836 * in case the upper bound is expressed as
837 * a list of affine expressions "upper".
839 * The enforced condition is that each lower bound expression is less
840 * than or equal to each upper bound expression.
842 static __isl_give isl_ast_graft *set_enforced_from_list(
843 __isl_take isl_ast_graft *graft,
844 __isl_keep isl_pw_aff_list *lower, __isl_keep isl_pw_aff_list *upper)
846 isl_set *cond;
847 isl_basic_set *enforced;
849 lower = isl_pw_aff_list_copy(lower);
850 upper = isl_pw_aff_list_copy(upper);
851 cond = isl_pw_aff_list_le_set(lower, upper);
852 enforced = isl_set_simple_hull(cond);
853 graft = isl_ast_graft_enforce(graft, enforced);
855 return graft;
858 /* Does "aff" have a negative constant term?
860 static int aff_constant_is_negative(__isl_take isl_set *set,
861 __isl_take isl_aff *aff, void *user)
863 int *neg = user;
864 isl_val *v;
866 v = isl_aff_get_constant_val(aff);
867 *neg = isl_val_is_neg(v);
868 isl_val_free(v);
869 isl_set_free(set);
870 isl_aff_free(aff);
872 return *neg ? 0 : -1;
875 /* Does "pa" have a negative constant term over its entire domain?
877 static int pw_aff_constant_is_negative(__isl_take isl_pw_aff *pa, void *user)
879 int r;
880 int *neg = user;
882 r = isl_pw_aff_foreach_piece(pa, &aff_constant_is_negative, user);
883 isl_pw_aff_free(pa);
885 return (*neg && r >= 0) ? 0 : -1;
888 /* Does each element in "list" have a negative constant term?
890 * The callback terminates the iteration as soon an element has been
891 * found that does not have a negative constant term.
893 static int list_constant_is_negative(__isl_keep isl_pw_aff_list *list)
895 int neg = 1;
897 if (isl_pw_aff_list_foreach(list,
898 &pw_aff_constant_is_negative, &neg) < 0 && neg)
899 return -1;
901 return neg;
904 /* Add 1 to each of the elements in "list", where each of these elements
905 * is defined over the internal schedule space of "build".
907 static __isl_give isl_pw_aff_list *list_add_one(
908 __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
910 int i, n;
911 isl_space *space;
912 isl_aff *aff;
913 isl_pw_aff *one;
915 space = isl_ast_build_get_space(build, 1);
916 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
917 aff = isl_aff_add_constant_si(aff, 1);
918 one = isl_pw_aff_from_aff(aff);
920 n = isl_pw_aff_list_n_pw_aff(list);
921 for (i = 0; i < n; ++i) {
922 isl_pw_aff *pa;
923 pa = isl_pw_aff_list_get_pw_aff(list, i);
924 pa = isl_pw_aff_add(pa, isl_pw_aff_copy(one));
925 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
928 isl_pw_aff_free(one);
930 return list;
933 /* Set the condition part of the for node graft->node in case
934 * the upper bound is represented as a list of piecewise affine expressions.
936 * In particular, set the condition to
938 * iterator <= min(list of upper bounds)
940 * If each of the upper bounds has a negative constant term, then
941 * set the condition to
943 * iterator < min(list of (upper bound + 1)s)
946 static __isl_give isl_ast_graft *set_for_cond_from_list(
947 __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *list,
948 __isl_keep isl_ast_build *build)
950 int neg;
951 isl_ast_expr *bound, *iterator, *cond;
952 enum isl_ast_op_type type = isl_ast_op_le;
954 if (!graft || !list)
955 return isl_ast_graft_free(graft);
957 neg = list_constant_is_negative(list);
958 if (neg < 0)
959 return isl_ast_graft_free(graft);
960 list = isl_pw_aff_list_copy(list);
961 if (neg) {
962 list = list_add_one(list, build);
963 type = isl_ast_op_lt;
966 bound = reduce_list(isl_ast_op_min, list, build);
967 iterator = isl_ast_expr_copy(graft->node->u.f.iterator);
968 cond = isl_ast_expr_alloc_binary(type, iterator, bound);
969 graft->node->u.f.cond = cond;
971 isl_pw_aff_list_free(list);
972 if (!graft->node->u.f.cond)
973 return isl_ast_graft_free(graft);
974 return graft;
977 /* Set the condition part of the for node graft->node in case
978 * the upper bound is represented as a set.
980 static __isl_give isl_ast_graft *set_for_cond_from_set(
981 __isl_take isl_ast_graft *graft, __isl_keep isl_set *set,
982 __isl_keep isl_ast_build *build)
984 isl_ast_expr *cond;
986 if (!graft)
987 return NULL;
989 cond = isl_ast_build_expr_from_set(build, isl_set_copy(set));
990 graft->node->u.f.cond = cond;
991 if (!graft->node->u.f.cond)
992 return isl_ast_graft_free(graft);
993 return graft;
996 /* Construct an isl_ast_expr for the increment (i.e., stride) of
997 * the current dimension.
999 static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
1001 int depth;
1002 isl_val *v;
1003 isl_ctx *ctx;
1005 if (!build)
1006 return NULL;
1007 ctx = isl_ast_build_get_ctx(build);
1008 depth = isl_ast_build_get_depth(build);
1010 if (!isl_ast_build_has_stride(build, depth))
1011 return isl_ast_expr_alloc_int_si(ctx, 1);
1013 v = isl_ast_build_get_stride(build, depth);
1014 return isl_ast_expr_from_val(v);
1017 /* Should we express the loop condition as
1019 * iterator <= min(list of upper bounds)
1021 * or as a conjunction of constraints?
1023 * The first is constructed from a list of upper bounds.
1024 * The second is constructed from a set.
1026 * If there are no upper bounds in "constraints", then this could mean
1027 * that "domain" simply doesn't have an upper bound or that we didn't
1028 * pick any upper bound. In the first case, we want to generate the
1029 * loop condition as a(n empty) conjunction of constraints
1030 * In the second case, we will compute
1031 * a single upper bound from "domain" and so we use the list form.
1033 * If there are upper bounds in "constraints",
1034 * then we use the list form iff the atomic_upper_bound option is set.
1036 static int use_upper_bound_list(isl_ctx *ctx, int n_upper,
1037 __isl_keep isl_set *domain, int depth)
1039 if (n_upper > 0)
1040 return isl_options_get_ast_build_atomic_upper_bound(ctx);
1041 else
1042 return isl_set_dim_has_upper_bound(domain, isl_dim_set, depth);
1045 /* Fill in the expressions of the for node in graft->node.
1047 * In particular,
1048 * - set the initialization part of the loop to the maximum of the lower bounds
1049 * - extract the increment from the stride of the current dimension
1050 * - construct the for condition either based on a list of upper bounds
1051 * or on a set of upper bound constraints.
1053 static __isl_give isl_ast_graft *set_for_node_expressions(
1054 __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *lower,
1055 int use_list, __isl_keep isl_pw_aff_list *upper_list,
1056 __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build)
1058 isl_ast_node *node;
1060 if (!graft)
1061 return NULL;
1063 build = isl_ast_build_copy(build);
1065 node = graft->node;
1066 node->u.f.init = reduce_list(isl_ast_op_max, lower, build);
1067 node->u.f.inc = for_inc(build);
1069 if (use_list)
1070 graft = set_for_cond_from_list(graft, upper_list, build);
1071 else
1072 graft = set_for_cond_from_set(graft, upper_set, build);
1074 isl_ast_build_free(build);
1076 if (!node->u.f.iterator || !node->u.f.init ||
1077 !node->u.f.cond || !node->u.f.inc)
1078 return isl_ast_graft_free(graft);
1080 return graft;
1083 /* Update "graft" based on "bounds" and "domain" for the generic,
1084 * non-degenerate, case.
1086 * "c_lower" and "c_upper" contain the lower and upper bounds
1087 * that the loop node should express.
1088 * "domain" is the subset of the intersection of the constraints
1089 * for which some code is executed.
1091 * There may be zero lower bounds or zero upper bounds in "constraints"
1092 * in case the list of constraints was created
1093 * based on the atomic option or based on separation with explicit bounds.
1094 * In that case, we use "domain" to derive lower and/or upper bounds.
1096 * We first compute a list of one or more lower bounds.
1098 * Then we decide if we want to express the condition as
1100 * iterator <= min(list of upper bounds)
1102 * or as a conjunction of constraints.
1104 * The set of enforced constraints is then computed either based on
1105 * a list of upper bounds or on a set of upper bound constraints.
1106 * We do not compute any enforced constraints if we were forced
1107 * to compute a lower or upper bound using exact_bound. The domains
1108 * of the resulting expressions may imply some bounds on outer dimensions
1109 * that we do not want to appear in the enforced constraints since
1110 * they are not actually enforced by the corresponding code.
1112 * Finally, we fill in the expressions of the for node.
1114 static __isl_give isl_ast_graft *refine_generic_bounds(
1115 __isl_take isl_ast_graft *graft,
1116 __isl_take isl_constraint_list *c_lower,
1117 __isl_take isl_constraint_list *c_upper,
1118 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1120 int depth;
1121 isl_ctx *ctx;
1122 isl_pw_aff_list *lower;
1123 int use_list;
1124 isl_set *upper_set = NULL;
1125 isl_pw_aff_list *upper_list = NULL;
1126 int n_lower, n_upper;
1128 if (!graft || !c_lower || !c_upper || !build)
1129 goto error;
1131 depth = isl_ast_build_get_depth(build);
1132 ctx = isl_ast_graft_get_ctx(graft);
1134 n_lower = isl_constraint_list_n_constraint(c_lower);
1135 n_upper = isl_constraint_list_n_constraint(c_upper);
1137 use_list = use_upper_bound_list(ctx, n_upper, domain, depth);
1139 lower = lower_bounds(c_lower, depth, domain, build);
1141 if (use_list)
1142 upper_list = upper_bounds(c_upper, depth, domain, build);
1143 else if (n_upper > 0)
1144 upper_set = intersect_constraints(c_upper);
1145 else
1146 upper_set = isl_set_universe(isl_set_get_space(domain));
1148 if (n_lower == 0 || n_upper == 0)
1150 else if (use_list)
1151 graft = set_enforced_from_list(graft, lower, upper_list);
1152 else
1153 graft = set_enforced_from_set(graft, lower, depth, upper_set);
1155 graft = set_for_node_expressions(graft, lower, use_list, upper_list,
1156 upper_set, build);
1158 isl_pw_aff_list_free(lower);
1159 isl_pw_aff_list_free(upper_list);
1160 isl_set_free(upper_set);
1161 isl_constraint_list_free(c_lower);
1162 isl_constraint_list_free(c_upper);
1164 return graft;
1165 error:
1166 isl_constraint_list_free(c_lower);
1167 isl_constraint_list_free(c_upper);
1168 return isl_ast_graft_free(graft);
1171 /* Internal data structure used inside count_constraints to keep
1172 * track of the number of constraints that are independent of dimension "pos",
1173 * the lower bounds in "pos" and the upper bounds in "pos".
1175 struct isl_ast_count_constraints_data {
1176 int pos;
1178 int n_indep;
1179 int n_lower;
1180 int n_upper;
1183 /* Increment data->n_indep, data->lower or data->upper depending
1184 * on whether "c" is independenct of dimensions data->pos,
1185 * a lower bound or an upper bound.
1187 static int count_constraints(__isl_take isl_constraint *c, void *user)
1189 struct isl_ast_count_constraints_data *data = user;
1191 if (isl_constraint_is_lower_bound(c, isl_dim_set, data->pos))
1192 data->n_lower++;
1193 else if (isl_constraint_is_upper_bound(c, isl_dim_set, data->pos))
1194 data->n_upper++;
1195 else
1196 data->n_indep++;
1198 isl_constraint_free(c);
1200 return 0;
1203 /* Update "graft" based on "bounds" and "domain" for the generic,
1204 * non-degenerate, case.
1206 * "list" respresent the list of bounds that need to be encoded by
1207 * the for loop. Only the constraints that involve the iterator
1208 * are relevant here. The other constraints are taken care of by
1209 * the caller and are included in the generated constraints of "build".
1210 * "domain" is the subset of the intersection of the constraints
1211 * for which some code is executed.
1212 * "build" is the build in which graft->node was created.
1214 * We separate lower bounds, upper bounds and constraints that
1215 * are independent of the loop iterator.
1217 * The actual for loop bounds are generated in refine_generic_bounds.
1219 static __isl_give isl_ast_graft *refine_generic_split(
1220 __isl_take isl_ast_graft *graft, __isl_take isl_constraint_list *list,
1221 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1223 struct isl_ast_count_constraints_data data;
1224 isl_constraint_list *lower;
1225 isl_constraint_list *upper;
1227 if (!list)
1228 return isl_ast_graft_free(graft);
1230 data.pos = isl_ast_build_get_depth(build);
1232 list = isl_constraint_list_sort(list, &cmp_constraint, &data.pos);
1233 if (!list)
1234 return isl_ast_graft_free(graft);
1236 data.n_indep = data.n_lower = data.n_upper = 0;
1237 if (isl_constraint_list_foreach(list, &count_constraints, &data) < 0) {
1238 isl_constraint_list_free(list);
1239 return isl_ast_graft_free(graft);
1242 lower = isl_constraint_list_drop(list, 0, data.n_indep);
1243 upper = isl_constraint_list_copy(lower);
1244 lower = isl_constraint_list_drop(lower, data.n_lower, data.n_upper);
1245 upper = isl_constraint_list_drop(upper, 0, data.n_lower);
1247 return refine_generic_bounds(graft, lower, upper, domain, build);
1250 /* Update "graft" based on "bounds" and "domain" for the generic,
1251 * non-degenerate, case.
1253 * "bounds" respresent the bounds that need to be encoded by
1254 * the for loop (or a guard around the for loop).
1255 * "domain" is the subset of "bounds" for which some code is executed.
1256 * "build" is the build in which graft->node was created.
1258 * We break up "bounds" into a list of constraints and continue with
1259 * refine_generic_split.
1261 static __isl_give isl_ast_graft *refine_generic(
1262 __isl_take isl_ast_graft *graft,
1263 __isl_keep isl_basic_set *bounds, __isl_keep isl_set *domain,
1264 __isl_keep isl_ast_build *build)
1266 isl_constraint_list *list;
1268 if (!build || !graft)
1269 return isl_ast_graft_free(graft);
1271 list = isl_basic_set_get_constraint_list(bounds);
1273 graft = refine_generic_split(graft, list, domain, build);
1275 return graft;
1278 /* Create a for node for the current level.
1280 * Mark the for node degenerate if "degenerate" is set.
1282 static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build,
1283 int degenerate)
1285 int depth;
1286 isl_id *id;
1287 isl_ast_node *node;
1289 if (!build)
1290 return NULL;
1292 depth = isl_ast_build_get_depth(build);
1293 id = isl_ast_build_get_iterator_id(build, depth);
1294 node = isl_ast_node_alloc_for(id);
1295 if (degenerate)
1296 node = isl_ast_node_for_mark_degenerate(node);
1298 return node;
1301 /* If the ast_build_exploit_nested_bounds option is set, then return
1302 * the constraints enforced by all elements in "list".
1303 * Otherwise, return the universe.
1305 static __isl_give isl_basic_set *extract_shared_enforced(
1306 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
1308 isl_ctx *ctx;
1309 isl_space *space;
1311 if (!list)
1312 return NULL;
1314 ctx = isl_ast_graft_list_get_ctx(list);
1315 if (isl_options_get_ast_build_exploit_nested_bounds(ctx))
1316 return isl_ast_graft_list_extract_shared_enforced(list, build);
1318 space = isl_ast_build_get_space(build, 1);
1319 return isl_basic_set_universe(space);
1322 /* Return the pending constraints of "build" that are not already taken
1323 * care of (by a combination of "enforced" and the generated constraints
1324 * of "build").
1326 static __isl_give isl_set *extract_pending(__isl_keep isl_ast_build *build,
1327 __isl_keep isl_basic_set *enforced)
1329 isl_set *guard, *context;
1331 guard = isl_ast_build_get_pending(build);
1332 context = isl_set_from_basic_set(isl_basic_set_copy(enforced));
1333 context = isl_set_intersect(context,
1334 isl_ast_build_get_generated(build));
1335 return isl_set_gist(guard, context);
1338 /* Create an AST node for the current dimension based on
1339 * the schedule domain "bounds" and return the node encapsulated
1340 * in an isl_ast_graft.
1342 * "executed" is the current inverse schedule, taking into account
1343 * the bounds in "bounds"
1344 * "domain" is the domain of "executed", with inner dimensions projected out.
1345 * It may be a strict subset of "bounds" in case "bounds" was created
1346 * based on the atomic option or based on separation with explicit bounds.
1348 * "domain" may satisfy additional equalities that result
1349 * from intersecting "executed" with "bounds" in add_node.
1350 * It may also satisfy some global constraints that were dropped out because
1351 * we performed separation with explicit bounds.
1352 * The very first step is then to copy these constraints to "bounds".
1354 * Since we may be calling before_each_for and after_each_for
1355 * callbacks, we record the current inverse schedule in the build.
1357 * We consider three builds,
1358 * "build" is the one in which the current level is created,
1359 * "body_build" is the build in which the next level is created,
1360 * "sub_build" is essentially the same as "body_build", except that
1361 * the depth has not been increased yet.
1363 * "build" already contains information (in strides and offsets)
1364 * about the strides at the current level, but this information is not
1365 * reflected in the build->domain.
1366 * We first add this information and the "bounds" to the sub_build->domain.
1367 * isl_ast_build_set_loop_bounds adds the stride information and
1368 * checks whether the current dimension attains
1369 * only a single value and whether this single value can be represented using
1370 * a single affine expression.
1371 * In the first case, the current level is considered "degenerate".
1372 * In the second, sub-case, the current level is considered "eliminated".
1373 * Eliminated levels don't need to be reflected in the AST since we can
1374 * simply plug in the affine expression. For degenerate, but non-eliminated,
1375 * levels, we do introduce a for node, but mark is as degenerate so that
1376 * it can be printed as an assignment of the single value to the loop
1377 * "iterator".
1379 * If the current level is eliminated, we explicitly plug in the value
1380 * for the current level found by isl_ast_build_set_loop_bounds in the
1381 * inverse schedule. This ensures that if we are working on a slice
1382 * of the domain based on information available in the inverse schedule
1383 * and the build domain, that then this information is also reflected
1384 * in the inverse schedule. This operation also eliminates the current
1385 * dimension from the inverse schedule making sure no inner dimensions depend
1386 * on the current dimension. Otherwise, we create a for node, marking
1387 * it degenerate if appropriate. The initial for node is still incomplete
1388 * and will be completed in either refine_degenerate or refine_generic.
1390 * We then generate a sequence of grafts for the next level,
1391 * create a surrounding graft for the current level and insert
1392 * the for node we created (if the current level is not eliminated).
1393 * Before creating a graft for the current level, we first extract
1394 * hoistable constraints from the child guards and combine them
1395 * with the pending constraints in the build. These constraints
1396 * are used to simplify the child guards and then added to the guard
1397 * of the current graft to ensure that they will be generated.
1398 * If the hoisted guard is a disjunction, then we use it directly
1399 * to gist the guards on the children before intersect it with the
1400 * pending constraints. We do so because this disjunction is typically
1401 * identical to the guards on the children such that these guards
1402 * can be effectively removed completely. After the intersection,
1403 * the gist operation would have a harder time figuring this out.
1405 * Finally, we set the bounds of the for loop in either
1406 * refine_degenerate or refine_generic.
1407 * We do so in a context where the pending constraints of the build
1408 * have been replaced by the guard of the current graft.
1410 static __isl_give isl_ast_graft *create_node_scaled(
1411 __isl_take isl_union_map *executed,
1412 __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1413 __isl_take isl_ast_build *build)
1415 int depth;
1416 int degenerate, eliminated;
1417 isl_basic_set *hull;
1418 isl_basic_set *enforced;
1419 isl_set *guard, *hoisted;
1420 isl_ast_node *node = NULL;
1421 isl_ast_graft *graft;
1422 isl_ast_graft_list *children;
1423 isl_ast_build *sub_build;
1424 isl_ast_build *body_build;
1426 domain = isl_ast_build_eliminate_divs(build, domain);
1427 domain = isl_set_detect_equalities(domain);
1428 hull = isl_set_unshifted_simple_hull(isl_set_copy(domain));
1429 bounds = isl_basic_set_intersect(bounds, hull);
1430 build = isl_ast_build_set_executed(build, isl_union_map_copy(executed));
1432 depth = isl_ast_build_get_depth(build);
1433 sub_build = isl_ast_build_copy(build);
1434 sub_build = isl_ast_build_set_loop_bounds(sub_build,
1435 isl_basic_set_copy(bounds));
1436 degenerate = isl_ast_build_has_value(sub_build);
1437 eliminated = isl_ast_build_has_affine_value(sub_build, depth);
1438 if (degenerate < 0 || eliminated < 0)
1439 executed = isl_union_map_free(executed);
1440 if (eliminated)
1441 executed = plug_in_values(executed, sub_build);
1442 else
1443 node = create_for(build, degenerate);
1445 body_build = isl_ast_build_copy(sub_build);
1446 body_build = isl_ast_build_increase_depth(body_build);
1447 if (!eliminated)
1448 node = before_each_for(node, body_build);
1449 children = generate_next_level(executed,
1450 isl_ast_build_copy(body_build));
1452 enforced = extract_shared_enforced(children, build);
1453 guard = extract_pending(sub_build, enforced);
1454 hoisted = isl_ast_graft_list_extract_hoistable_guard(children, build);
1455 if (isl_set_n_basic_set(hoisted) > 1)
1456 children = isl_ast_graft_list_gist_guards(children,
1457 isl_set_copy(hoisted));
1458 guard = isl_set_intersect(guard, hoisted);
1459 if (!eliminated)
1460 guard = add_implied_guards(guard, degenerate, bounds, build);
1462 graft = isl_ast_graft_alloc_from_children(children,
1463 isl_set_copy(guard), enforced, build, sub_build);
1465 if (!degenerate)
1466 bounds = isl_ast_build_compute_gist_basic_set(build, bounds);
1467 if (!eliminated) {
1468 isl_ast_build *for_build;
1470 graft = isl_ast_graft_insert_for(graft, node);
1471 for_build = isl_ast_build_copy(build);
1472 for_build = isl_ast_build_replace_pending_by_guard(for_build,
1473 isl_set_copy(guard));
1474 if (degenerate)
1475 graft = refine_degenerate(graft, for_build, sub_build);
1476 else
1477 graft = refine_generic(graft, bounds,
1478 domain, for_build);
1479 isl_ast_build_free(for_build);
1481 isl_set_free(guard);
1482 if (!eliminated)
1483 graft = after_each_for(graft, body_build);
1485 isl_ast_build_free(body_build);
1486 isl_ast_build_free(sub_build);
1487 isl_ast_build_free(build);
1488 isl_basic_set_free(bounds);
1489 isl_set_free(domain);
1491 return graft;
1494 /* Internal data structure for checking if all constraints involving
1495 * the input dimension "depth" are such that the other coefficients
1496 * are multiples of "m", reducing "m" if they are not.
1497 * If "m" is reduced all the way down to "1", then the check has failed
1498 * and we break out of the iteration.
1500 struct isl_check_scaled_data {
1501 int depth;
1502 isl_val *m;
1505 /* If constraint "c" involves the input dimension data->depth,
1506 * then make sure that all the other coefficients are multiples of data->m,
1507 * reducing data->m if needed.
1508 * Break out of the iteration if data->m has become equal to "1".
1510 static int constraint_check_scaled(__isl_take isl_constraint *c, void *user)
1512 struct isl_check_scaled_data *data = user;
1513 int i, j, n;
1514 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_out,
1515 isl_dim_div };
1517 if (!isl_constraint_involves_dims(c, isl_dim_in, data->depth, 1)) {
1518 isl_constraint_free(c);
1519 return 0;
1522 for (i = 0; i < 4; ++i) {
1523 n = isl_constraint_dim(c, t[i]);
1524 for (j = 0; j < n; ++j) {
1525 isl_val *d;
1527 if (t[i] == isl_dim_in && j == data->depth)
1528 continue;
1529 if (!isl_constraint_involves_dims(c, t[i], j, 1))
1530 continue;
1531 d = isl_constraint_get_coefficient_val(c, t[i], j);
1532 data->m = isl_val_gcd(data->m, d);
1533 if (isl_val_is_one(data->m))
1534 break;
1536 if (j < n)
1537 break;
1540 isl_constraint_free(c);
1542 return i < 4 ? -1 : 0;
1545 /* For each constraint of "bmap" that involves the input dimension data->depth,
1546 * make sure that all the other coefficients are multiples of data->m,
1547 * reducing data->m if needed.
1548 * Break out of the iteration if data->m has become equal to "1".
1550 static int basic_map_check_scaled(__isl_take isl_basic_map *bmap, void *user)
1552 int r;
1554 r = isl_basic_map_foreach_constraint(bmap,
1555 &constraint_check_scaled, user);
1556 isl_basic_map_free(bmap);
1558 return r;
1561 /* For each constraint of "map" that involves the input dimension data->depth,
1562 * make sure that all the other coefficients are multiples of data->m,
1563 * reducing data->m if needed.
1564 * Break out of the iteration if data->m has become equal to "1".
1566 static int map_check_scaled(__isl_take isl_map *map, void *user)
1568 int r;
1570 r = isl_map_foreach_basic_map(map, &basic_map_check_scaled, user);
1571 isl_map_free(map);
1573 return r;
1576 /* Create an AST node for the current dimension based on
1577 * the schedule domain "bounds" and return the node encapsulated
1578 * in an isl_ast_graft.
1580 * "executed" is the current inverse schedule, taking into account
1581 * the bounds in "bounds"
1582 * "domain" is the domain of "executed", with inner dimensions projected out.
1585 * Before moving on to the actual AST node construction in create_node_scaled,
1586 * we first check if the current dimension is strided and if we can scale
1587 * down this stride. Note that we only do this if the ast_build_scale_strides
1588 * option is set.
1590 * In particular, let the current dimension take on values
1592 * f + s a
1594 * with a an integer. We check if we can find an integer m that (obviously)
1595 * divides both f and s.
1597 * If so, we check if the current dimension only appears in constraints
1598 * where the coefficients of the other variables are multiples of m.
1599 * We perform this extra check to avoid the risk of introducing
1600 * divisions by scaling down the current dimension.
1602 * If so, we scale the current dimension down by a factor of m.
1603 * That is, we plug in
1605 * i = m i' (1)
1607 * Note that in principle we could always scale down strided loops
1608 * by plugging in
1610 * i = f + s i'
1612 * but this may result in i' taking on larger values than the original i,
1613 * due to the shift by "f".
1614 * By constrast, the scaling in (1) can only reduce the (absolute) value "i".
1616 static __isl_give isl_ast_graft *create_node(__isl_take isl_union_map *executed,
1617 __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1618 __isl_take isl_ast_build *build)
1620 struct isl_check_scaled_data data;
1621 isl_ctx *ctx;
1622 isl_aff *offset;
1623 isl_val *d;
1625 ctx = isl_ast_build_get_ctx(build);
1626 if (!isl_options_get_ast_build_scale_strides(ctx))
1627 return create_node_scaled(executed, bounds, domain, build);
1629 data.depth = isl_ast_build_get_depth(build);
1630 if (!isl_ast_build_has_stride(build, data.depth))
1631 return create_node_scaled(executed, bounds, domain, build);
1633 offset = isl_ast_build_get_offset(build, data.depth);
1634 data.m = isl_ast_build_get_stride(build, data.depth);
1635 if (!data.m)
1636 offset = isl_aff_free(offset);
1637 offset = isl_aff_scale_down_val(offset, isl_val_copy(data.m));
1638 d = isl_aff_get_denominator_val(offset);
1639 if (!d)
1640 executed = isl_union_map_free(executed);
1642 if (executed && isl_val_is_divisible_by(data.m, d))
1643 data.m = isl_val_div(data.m, d);
1644 else {
1645 data.m = isl_val_set_si(data.m, 1);
1646 isl_val_free(d);
1649 if (!isl_val_is_one(data.m)) {
1650 if (isl_union_map_foreach_map(executed, &map_check_scaled,
1651 &data) < 0 &&
1652 !isl_val_is_one(data.m))
1653 executed = isl_union_map_free(executed);
1656 if (!isl_val_is_one(data.m)) {
1657 isl_space *space;
1658 isl_multi_aff *ma;
1659 isl_aff *aff;
1660 isl_map *map;
1661 isl_union_map *umap;
1663 space = isl_ast_build_get_space(build, 1);
1664 space = isl_space_map_from_set(space);
1665 ma = isl_multi_aff_identity(space);
1666 aff = isl_multi_aff_get_aff(ma, data.depth);
1667 aff = isl_aff_scale_val(aff, isl_val_copy(data.m));
1668 ma = isl_multi_aff_set_aff(ma, data.depth, aff);
1670 bounds = isl_basic_set_preimage_multi_aff(bounds,
1671 isl_multi_aff_copy(ma));
1672 domain = isl_set_preimage_multi_aff(domain,
1673 isl_multi_aff_copy(ma));
1674 map = isl_map_reverse(isl_map_from_multi_aff(ma));
1675 umap = isl_union_map_from_map(map);
1676 executed = isl_union_map_apply_domain(executed,
1677 isl_union_map_copy(umap));
1678 build = isl_ast_build_scale_down(build, isl_val_copy(data.m),
1679 umap);
1681 isl_aff_free(offset);
1682 isl_val_free(data.m);
1684 return create_node_scaled(executed, bounds, domain, build);
1687 /* Add the basic set to the list that "user" points to.
1689 static int collect_basic_set(__isl_take isl_basic_set *bset, void *user)
1691 isl_basic_set_list **list = user;
1693 *list = isl_basic_set_list_add(*list, bset);
1695 return 0;
1698 /* Extract the basic sets of "set" and collect them in an isl_basic_set_list.
1700 static __isl_give isl_basic_set_list *isl_basic_set_list_from_set(
1701 __isl_take isl_set *set)
1703 int n;
1704 isl_ctx *ctx;
1705 isl_basic_set_list *list;
1707 if (!set)
1708 return NULL;
1710 ctx = isl_set_get_ctx(set);
1712 n = isl_set_n_basic_set(set);
1713 list = isl_basic_set_list_alloc(ctx, n);
1714 if (isl_set_foreach_basic_set(set, &collect_basic_set, &list) < 0)
1715 list = isl_basic_set_list_free(list);
1717 isl_set_free(set);
1718 return list;
1721 /* Generate code for the schedule domain "bounds"
1722 * and add the result to "list".
1724 * We mainly detect strides here and check if the bounds do not
1725 * conflict with the current build domain
1726 * and then pass over control to create_node.
1728 * "bounds" reflects the bounds on the current dimension and possibly
1729 * some extra conditions on outer dimensions.
1730 * It does not, however, include any divs involving the current dimension,
1731 * so it does not capture any stride constraints.
1732 * We therefore need to compute that part of the schedule domain that
1733 * intersects with "bounds" and derive the strides from the result.
1735 static __isl_give isl_ast_graft_list *add_node(
1736 __isl_take isl_ast_graft_list *list, __isl_take isl_union_map *executed,
1737 __isl_take isl_basic_set *bounds, __isl_take isl_ast_build *build)
1739 isl_ast_graft *graft;
1740 isl_set *domain = NULL;
1741 isl_union_set *uset;
1742 int empty, disjoint;
1744 uset = isl_union_set_from_basic_set(isl_basic_set_copy(bounds));
1745 executed = isl_union_map_intersect_domain(executed, uset);
1746 empty = isl_union_map_is_empty(executed);
1747 if (empty < 0)
1748 goto error;
1749 if (empty)
1750 goto done;
1752 uset = isl_union_map_domain(isl_union_map_copy(executed));
1753 domain = isl_set_from_union_set(uset);
1754 domain = isl_ast_build_specialize(build, domain);
1756 domain = isl_set_compute_divs(domain);
1757 domain = isl_ast_build_eliminate_inner(build, domain);
1758 disjoint = isl_set_is_disjoint(domain, build->domain);
1759 if (disjoint < 0)
1760 goto error;
1761 if (disjoint)
1762 goto done;
1764 build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
1766 graft = create_node(executed, bounds, domain,
1767 isl_ast_build_copy(build));
1768 list = isl_ast_graft_list_add(list, graft);
1769 isl_ast_build_free(build);
1770 return list;
1771 error:
1772 list = isl_ast_graft_list_free(list);
1773 done:
1774 isl_set_free(domain);
1775 isl_basic_set_free(bounds);
1776 isl_union_map_free(executed);
1777 isl_ast_build_free(build);
1778 return list;
1781 /* Does any element of i follow or coincide with any element of j
1782 * at the current depth for equal values of the outer dimensions?
1784 static int domain_follows_at_depth(__isl_keep isl_basic_set *i,
1785 __isl_keep isl_basic_set *j, void *user)
1787 int depth = *(int *) user;
1788 isl_basic_map *test;
1789 int empty;
1790 int l;
1792 test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1793 isl_basic_set_copy(j));
1794 for (l = 0; l < depth; ++l)
1795 test = isl_basic_map_equate(test, isl_dim_in, l,
1796 isl_dim_out, l);
1797 test = isl_basic_map_order_ge(test, isl_dim_in, depth,
1798 isl_dim_out, depth);
1799 empty = isl_basic_map_is_empty(test);
1800 isl_basic_map_free(test);
1802 return empty < 0 ? -1 : !empty;
1805 /* Split up each element of "list" into a part that is related to "bset"
1806 * according to "gt" and a part that is not.
1807 * Return a list that consist of "bset" and all the pieces.
1809 static __isl_give isl_basic_set_list *add_split_on(
1810 __isl_take isl_basic_set_list *list, __isl_take isl_basic_set *bset,
1811 __isl_keep isl_basic_map *gt)
1813 int i, n;
1814 isl_basic_set_list *res;
1816 if (!list)
1817 bset = isl_basic_set_free(bset);
1819 gt = isl_basic_map_copy(gt);
1820 gt = isl_basic_map_intersect_domain(gt, isl_basic_set_copy(bset));
1821 n = isl_basic_set_list_n_basic_set(list);
1822 res = isl_basic_set_list_from_basic_set(bset);
1823 for (i = 0; res && i < n; ++i) {
1824 isl_basic_set *bset;
1825 isl_set *set1, *set2;
1826 isl_basic_map *bmap;
1827 int empty;
1829 bset = isl_basic_set_list_get_basic_set(list, i);
1830 bmap = isl_basic_map_copy(gt);
1831 bmap = isl_basic_map_intersect_range(bmap, bset);
1832 bset = isl_basic_map_range(bmap);
1833 empty = isl_basic_set_is_empty(bset);
1834 if (empty < 0)
1835 res = isl_basic_set_list_free(res);
1836 if (empty) {
1837 isl_basic_set_free(bset);
1838 bset = isl_basic_set_list_get_basic_set(list, i);
1839 res = isl_basic_set_list_add(res, bset);
1840 continue;
1843 res = isl_basic_set_list_add(res, isl_basic_set_copy(bset));
1844 set1 = isl_set_from_basic_set(bset);
1845 bset = isl_basic_set_list_get_basic_set(list, i);
1846 set2 = isl_set_from_basic_set(bset);
1847 set1 = isl_set_subtract(set2, set1);
1848 set1 = isl_set_make_disjoint(set1);
1850 res = isl_basic_set_list_concat(res,
1851 isl_basic_set_list_from_set(set1));
1853 isl_basic_map_free(gt);
1854 isl_basic_set_list_free(list);
1855 return res;
1858 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1859 __isl_keep isl_basic_set_list *domain_list,
1860 __isl_keep isl_union_map *executed,
1861 __isl_keep isl_ast_build *build);
1863 /* Internal data structure for add_nodes.
1865 * "executed" and "build" are extra arguments to be passed to add_node.
1866 * "list" collects the results.
1868 struct isl_add_nodes_data {
1869 isl_union_map *executed;
1870 isl_ast_build *build;
1872 isl_ast_graft_list *list;
1875 /* Generate code for the schedule domains in "scc"
1876 * and add the results to "list".
1878 * The domains in "scc" form a strongly connected component in the ordering.
1879 * If the number of domains in "scc" is larger than 1, then this means
1880 * that we cannot determine a valid ordering for the domains in the component.
1881 * This should be fairly rare because the individual domains
1882 * have been made disjoint first.
1883 * The problem is that the domains may be integrally disjoint but not
1884 * rationally disjoint. For example, we may have domains
1886 * { [i,i] : 0 <= i <= 1 } and { [i,1-i] : 0 <= i <= 1 }
1888 * These two domains have an empty intersection, but their rational
1889 * relaxations do intersect. It is impossible to order these domains
1890 * in the second dimension because the first should be ordered before
1891 * the second for outer dimension equal to 0, while it should be ordered
1892 * after for outer dimension equal to 1.
1894 * This may happen in particular in case of unrolling since the domain
1895 * of each slice is replaced by its simple hull.
1897 * For each basic set i in "scc" and for each of the following basic sets j,
1898 * we split off that part of the basic set i that shares the outer dimensions
1899 * with j and lies before j in the current dimension.
1900 * We collect all the pieces in a new list that replaces "scc".
1902 * While the elements in "scc" should be disjoint, we double-check
1903 * this property to avoid running into an infinite recursion in case
1904 * they intersect due to some internal error.
1906 static int add_nodes(__isl_take isl_basic_set_list *scc, void *user)
1908 struct isl_add_nodes_data *data = user;
1909 int i, n, depth;
1910 isl_basic_set *bset, *first;
1911 isl_basic_set_list *list;
1912 isl_space *space;
1913 isl_basic_map *gt;
1915 n = isl_basic_set_list_n_basic_set(scc);
1916 bset = isl_basic_set_list_get_basic_set(scc, 0);
1917 if (n == 1) {
1918 isl_basic_set_list_free(scc);
1919 data->list = add_node(data->list,
1920 isl_union_map_copy(data->executed), bset,
1921 isl_ast_build_copy(data->build));
1922 return data->list ? 0 : -1;
1925 depth = isl_ast_build_get_depth(data->build);
1926 space = isl_basic_set_get_space(bset);
1927 space = isl_space_map_from_set(space);
1928 gt = isl_basic_map_universe(space);
1929 for (i = 0; i < depth; ++i)
1930 gt = isl_basic_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
1931 gt = isl_basic_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
1933 first = isl_basic_set_copy(bset);
1934 list = isl_basic_set_list_from_basic_set(bset);
1935 for (i = 1; i < n; ++i) {
1936 int disjoint;
1938 bset = isl_basic_set_list_get_basic_set(scc, i);
1940 disjoint = isl_basic_set_is_disjoint(bset, first);
1941 if (disjoint < 0)
1942 list = isl_basic_set_list_free(list);
1943 else if (!disjoint)
1944 isl_die(isl_basic_set_list_get_ctx(scc),
1945 isl_error_internal,
1946 "basic sets in scc are assumed to be disjoint",
1947 list = isl_basic_set_list_free(list));
1949 list = add_split_on(list, bset, gt);
1951 isl_basic_set_free(first);
1952 isl_basic_map_free(gt);
1953 isl_basic_set_list_free(scc);
1954 scc = list;
1955 data->list = isl_ast_graft_list_concat(data->list,
1956 generate_sorted_domains(scc, data->executed, data->build));
1957 isl_basic_set_list_free(scc);
1959 return data->list ? 0 : -1;
1962 /* Sort the domains in "domain_list" according to the execution order
1963 * at the current depth (for equal values of the outer dimensions),
1964 * generate code for each of them, collecting the results in a list.
1965 * If no code is generated (because the intersection of the inverse schedule
1966 * with the domains turns out to be empty), then an empty list is returned.
1968 * The caller is responsible for ensuring that the basic sets in "domain_list"
1969 * are pair-wise disjoint. It can, however, in principle happen that
1970 * two basic sets should be ordered one way for one value of the outer
1971 * dimensions and the other way for some other value of the outer dimensions.
1972 * We therefore play safe and look for strongly connected components.
1973 * The function add_nodes takes care of handling non-trivial components.
1975 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1976 __isl_keep isl_basic_set_list *domain_list,
1977 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
1979 isl_ctx *ctx;
1980 struct isl_add_nodes_data data;
1981 int depth;
1982 int n;
1984 if (!domain_list)
1985 return NULL;
1987 ctx = isl_basic_set_list_get_ctx(domain_list);
1988 n = isl_basic_set_list_n_basic_set(domain_list);
1989 data.list = isl_ast_graft_list_alloc(ctx, n);
1990 if (n == 0)
1991 return data.list;
1992 if (n == 1)
1993 return add_node(data.list, isl_union_map_copy(executed),
1994 isl_basic_set_list_get_basic_set(domain_list, 0),
1995 isl_ast_build_copy(build));
1997 depth = isl_ast_build_get_depth(build);
1998 data.executed = executed;
1999 data.build = build;
2000 if (isl_basic_set_list_foreach_scc(domain_list,
2001 &domain_follows_at_depth, &depth,
2002 &add_nodes, &data) < 0)
2003 data.list = isl_ast_graft_list_free(data.list);
2005 return data.list;
2008 /* Do i and j share any values for the outer dimensions?
2010 static int shared_outer(__isl_keep isl_basic_set *i,
2011 __isl_keep isl_basic_set *j, void *user)
2013 int depth = *(int *) user;
2014 isl_basic_map *test;
2015 int empty;
2016 int l;
2018 test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
2019 isl_basic_set_copy(j));
2020 for (l = 0; l < depth; ++l)
2021 test = isl_basic_map_equate(test, isl_dim_in, l,
2022 isl_dim_out, l);
2023 empty = isl_basic_map_is_empty(test);
2024 isl_basic_map_free(test);
2026 return empty < 0 ? -1 : !empty;
2029 /* Internal data structure for generate_sorted_domains_wrap.
2031 * "n" is the total number of basic sets
2032 * "executed" and "build" are extra arguments to be passed
2033 * to generate_sorted_domains.
2035 * "single" is set to 1 by generate_sorted_domains_wrap if there
2036 * is only a single component.
2037 * "list" collects the results.
2039 struct isl_ast_generate_parallel_domains_data {
2040 int n;
2041 isl_union_map *executed;
2042 isl_ast_build *build;
2044 int single;
2045 isl_ast_graft_list *list;
2048 /* Call generate_sorted_domains on "scc", fuse the result into a list
2049 * with either zero or one graft and collect the these single element
2050 * lists into data->list.
2052 * If there is only one component, i.e., if the number of basic sets
2053 * in the current component is equal to the total number of basic sets,
2054 * then data->single is set to 1 and the result of generate_sorted_domains
2055 * is not fused.
2057 static int generate_sorted_domains_wrap(__isl_take isl_basic_set_list *scc,
2058 void *user)
2060 struct isl_ast_generate_parallel_domains_data *data = user;
2061 isl_ast_graft_list *list;
2063 list = generate_sorted_domains(scc, data->executed, data->build);
2064 data->single = isl_basic_set_list_n_basic_set(scc) == data->n;
2065 if (!data->single)
2066 list = isl_ast_graft_list_fuse(list, data->build);
2067 if (!data->list)
2068 data->list = list;
2069 else
2070 data->list = isl_ast_graft_list_concat(data->list, list);
2072 isl_basic_set_list_free(scc);
2073 if (!data->list)
2074 return -1;
2076 return 0;
2079 /* Look for any (weakly connected) components in the "domain_list"
2080 * of domains that share some values of the outer dimensions.
2081 * That is, domains in different components do not share any values
2082 * of the outer dimensions. This means that these components
2083 * can be freely reordered.
2084 * Within each of the components, we sort the domains according
2085 * to the execution order at the current depth.
2087 * If there is more than one component, then generate_sorted_domains_wrap
2088 * fuses the result of each call to generate_sorted_domains
2089 * into a list with either zero or one graft and collects these (at most)
2090 * single element lists into a bigger list. This means that the elements of the
2091 * final list can be freely reordered. In particular, we sort them
2092 * according to an arbitrary but fixed ordering to ease merging of
2093 * graft lists from different components.
2095 static __isl_give isl_ast_graft_list *generate_parallel_domains(
2096 __isl_keep isl_basic_set_list *domain_list,
2097 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2099 int depth;
2100 struct isl_ast_generate_parallel_domains_data data;
2102 if (!domain_list)
2103 return NULL;
2105 data.n = isl_basic_set_list_n_basic_set(domain_list);
2106 if (data.n <= 1)
2107 return generate_sorted_domains(domain_list, executed, build);
2109 depth = isl_ast_build_get_depth(build);
2110 data.list = NULL;
2111 data.executed = executed;
2112 data.build = build;
2113 data.single = 0;
2114 if (isl_basic_set_list_foreach_scc(domain_list, &shared_outer, &depth,
2115 &generate_sorted_domains_wrap,
2116 &data) < 0)
2117 data.list = isl_ast_graft_list_free(data.list);
2119 if (!data.single)
2120 data.list = isl_ast_graft_list_sort_guard(data.list);
2122 return data.list;
2125 /* Internal data for separate_domain.
2127 * "explicit" is set if we only want to use explicit bounds.
2129 * "domain" collects the separated domains.
2131 struct isl_separate_domain_data {
2132 isl_ast_build *build;
2133 int explicit;
2134 isl_set *domain;
2137 /* Extract implicit bounds on the current dimension for the executed "map".
2139 * The domain of "map" may involve inner dimensions, so we
2140 * need to eliminate them.
2142 static __isl_give isl_set *implicit_bounds(__isl_take isl_map *map,
2143 __isl_keep isl_ast_build *build)
2145 isl_set *domain;
2147 domain = isl_map_domain(map);
2148 domain = isl_ast_build_eliminate(build, domain);
2150 return domain;
2153 /* Extract explicit bounds on the current dimension for the executed "map".
2155 * Rather than eliminating the inner dimensions as in implicit_bounds,
2156 * we simply drop any constraints involving those inner dimensions.
2157 * The idea is that most bounds that are implied by constraints on the
2158 * inner dimensions will be enforced by for loops and not by explicit guards.
2159 * There is then no need to separate along those bounds.
2161 static __isl_give isl_set *explicit_bounds(__isl_take isl_map *map,
2162 __isl_keep isl_ast_build *build)
2164 isl_set *domain;
2165 int depth, dim;
2167 dim = isl_map_dim(map, isl_dim_out);
2168 map = isl_map_drop_constraints_involving_dims(map, isl_dim_out, 0, dim);
2170 domain = isl_map_domain(map);
2171 depth = isl_ast_build_get_depth(build);
2172 dim = isl_set_dim(domain, isl_dim_set);
2173 domain = isl_set_detect_equalities(domain);
2174 domain = isl_set_drop_constraints_involving_dims(domain,
2175 isl_dim_set, depth + 1, dim - (depth + 1));
2176 domain = isl_set_remove_divs_involving_dims(domain,
2177 isl_dim_set, depth, 1);
2178 domain = isl_set_remove_unknown_divs(domain);
2180 return domain;
2183 /* Split data->domain into pieces that intersect with the range of "map"
2184 * and pieces that do not intersect with the range of "map"
2185 * and then add that part of the range of "map" that does not intersect
2186 * with data->domain.
2188 static int separate_domain(__isl_take isl_map *map, void *user)
2190 struct isl_separate_domain_data *data = user;
2191 isl_set *domain;
2192 isl_set *d1, *d2;
2194 if (data->explicit)
2195 domain = explicit_bounds(map, data->build);
2196 else
2197 domain = implicit_bounds(map, data->build);
2199 domain = isl_set_coalesce(domain);
2200 domain = isl_set_make_disjoint(domain);
2201 d1 = isl_set_subtract(isl_set_copy(domain), isl_set_copy(data->domain));
2202 d2 = isl_set_subtract(isl_set_copy(data->domain), isl_set_copy(domain));
2203 data->domain = isl_set_intersect(data->domain, domain);
2204 data->domain = isl_set_union(data->domain, d1);
2205 data->domain = isl_set_union(data->domain, d2);
2207 return 0;
2210 /* Separate the schedule domains of "executed".
2212 * That is, break up the domain of "executed" into basic sets,
2213 * such that for each basic set S, every element in S is associated with
2214 * the same domain spaces.
2216 * "space" is the (single) domain space of "executed".
2218 static __isl_give isl_set *separate_schedule_domains(
2219 __isl_take isl_space *space, __isl_take isl_union_map *executed,
2220 __isl_keep isl_ast_build *build)
2222 struct isl_separate_domain_data data = { build };
2223 isl_ctx *ctx;
2225 ctx = isl_ast_build_get_ctx(build);
2226 data.explicit = isl_options_get_ast_build_separation_bounds(ctx) ==
2227 ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT;
2228 data.domain = isl_set_empty(space);
2229 if (isl_union_map_foreach_map(executed, &separate_domain, &data) < 0)
2230 data.domain = isl_set_free(data.domain);
2232 isl_union_map_free(executed);
2233 return data.domain;
2236 /* Temporary data used during the search for a lower bound for unrolling.
2238 * "build" is the build in which the unrolling will be performed
2239 * "domain" is the original set for which to find a lower bound
2240 * "depth" is the dimension for which to find a lower boudn
2241 * "expansion" is the expansion that needs to be applied to "domain"
2242 * in the unrolling that will be performed
2244 * "lower" is the best lower bound found so far. It is NULL if we have not
2245 * found any yet.
2246 * "n" is the corresponding size. If lower is NULL, then the value of n
2247 * is undefined.
2248 * "n_div" is the maximal number of integer divisions in the first
2249 * unrolled iteration (after expansion). It is set to -1 if it hasn't
2250 * been computed yet.
2252 struct isl_find_unroll_data {
2253 isl_ast_build *build;
2254 isl_set *domain;
2255 int depth;
2256 isl_basic_map *expansion;
2258 isl_aff *lower;
2259 int *n;
2260 int n_div;
2263 /* Return the constraint
2265 * i_"depth" = aff + offset
2267 static __isl_give isl_constraint *at_offset(int depth, __isl_keep isl_aff *aff,
2268 int offset)
2270 aff = isl_aff_copy(aff);
2271 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, depth, -1);
2272 aff = isl_aff_add_constant_si(aff, offset);
2273 return isl_equality_from_aff(aff);
2276 /* Update *user to the number of integer divsions in the first element
2277 * of "ma", if it is larger than the current value.
2279 static int update_n_div(__isl_take isl_set *set, __isl_take isl_multi_aff *ma,
2280 void *user)
2282 isl_aff *aff;
2283 int *n = user;
2284 int n_div;
2286 aff = isl_multi_aff_get_aff(ma, 0);
2287 n_div = isl_aff_dim(aff, isl_dim_div);
2288 isl_aff_free(aff);
2289 isl_multi_aff_free(ma);
2290 isl_set_free(set);
2292 if (n_div > *n)
2293 *n = n_div;
2295 return aff ? 0 : -1;
2298 /* Get the number of integer divisions in the expression for the iterator
2299 * value at the first slice in the unrolling based on lower bound "lower",
2300 * taking into account the expansion that needs to be performed on this slice.
2302 static int get_expanded_n_div(struct isl_find_unroll_data *data,
2303 __isl_keep isl_aff *lower)
2305 isl_constraint *c;
2306 isl_set *set;
2307 isl_map *it_map, *expansion;
2308 isl_pw_multi_aff *pma;
2309 int n;
2311 c = at_offset(data->depth, lower, 0);
2312 set = isl_set_copy(data->domain);
2313 set = isl_set_add_constraint(set, c);
2314 expansion = isl_map_from_basic_map(isl_basic_map_copy(data->expansion));
2315 set = isl_set_apply(set, expansion);
2316 it_map = isl_ast_build_map_to_iterator(data->build, set);
2317 pma = isl_pw_multi_aff_from_map(it_map);
2318 n = 0;
2319 if (isl_pw_multi_aff_foreach_piece(pma, &update_n_div, &n) < 0)
2320 n = -1;
2321 isl_pw_multi_aff_free(pma);
2323 return n;
2326 /* Is the lower bound "lower" with corresponding iteration count "n"
2327 * better than the one stored in "data"?
2328 * If there is no upper bound on the iteration count ("n" is infinity) or
2329 * if the count is too large, then we cannot use this lower bound.
2330 * Otherwise, if there was no previous lower bound or
2331 * if the iteration count of the new lower bound is smaller than
2332 * the iteration count of the previous lower bound, then we consider
2333 * the new lower bound to be better.
2334 * If the iteration count is the same, then compare the number
2335 * of integer divisions that would be needed to express
2336 * the iterator value at the first slice in the unrolling
2337 * according to the lower bound. If we end up computing this
2338 * number, then store the lowest value in data->n_div.
2340 static int is_better_lower_bound(struct isl_find_unroll_data *data,
2341 __isl_keep isl_aff *lower, __isl_keep isl_val *n)
2343 int cmp;
2344 int n_div;
2346 if (!n)
2347 return -1;
2348 if (isl_val_is_infty(n))
2349 return 0;
2350 if (isl_val_cmp_si(n, INT_MAX) > 0)
2351 return 0;
2352 if (!data->lower)
2353 return 1;
2354 cmp = isl_val_cmp_si(n, *data->n);
2355 if (cmp < 0)
2356 return 1;
2357 if (cmp > 0)
2358 return 0;
2359 if (data->n_div < 0)
2360 data->n_div = get_expanded_n_div(data, data->lower);
2361 if (data->n_div < 0)
2362 return -1;
2363 if (data->n_div == 0)
2364 return 0;
2365 n_div = get_expanded_n_div(data, lower);
2366 if (n_div < 0)
2367 return -1;
2368 if (n_div >= data->n_div)
2369 return 0;
2370 data->n_div = n_div;
2372 return 1;
2375 /* Check if we can use "c" as a lower bound and if it is better than
2376 * any previously found lower bound.
2378 * If "c" does not involve the dimension at the current depth,
2379 * then we cannot use it.
2380 * Otherwise, let "c" be of the form
2382 * i >= f(j)/a
2384 * We compute the maximal value of
2386 * -ceil(f(j)/a)) + i + 1
2388 * over the domain. If there is such a value "n", then we know
2390 * -ceil(f(j)/a)) + i + 1 <= n
2392 * or
2394 * i < ceil(f(j)/a)) + n
2396 * meaning that we can use ceil(f(j)/a)) as a lower bound for unrolling.
2397 * We just need to check if we have found any lower bound before and
2398 * if the new lower bound is better (smaller n or fewer integer divisions)
2399 * than the previously found lower bounds.
2401 static int update_unrolling_lower_bound(struct isl_find_unroll_data *data,
2402 __isl_keep isl_constraint *c)
2404 isl_aff *aff, *lower;
2405 isl_val *max;
2406 int better;
2408 if (!isl_constraint_is_lower_bound(c, isl_dim_set, data->depth))
2409 return 0;
2411 lower = isl_constraint_get_bound(c, isl_dim_set, data->depth);
2412 lower = isl_aff_ceil(lower);
2413 aff = isl_aff_copy(lower);
2414 aff = isl_aff_neg(aff);
2415 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, data->depth, 1);
2416 aff = isl_aff_add_constant_si(aff, 1);
2417 max = isl_set_max_val(data->domain, aff);
2418 isl_aff_free(aff);
2420 better = is_better_lower_bound(data, lower, max);
2421 if (better < 0 || !better) {
2422 isl_val_free(max);
2423 isl_aff_free(lower);
2424 return better < 0 ? -1 : 0;
2427 isl_aff_free(data->lower);
2428 data->lower = lower;
2429 *data->n = isl_val_get_num_si(max);
2430 isl_val_free(max);
2432 return 1;
2435 /* Check if we can use "c" as a lower bound and if it is better than
2436 * any previously found lower bound.
2438 static int constraint_find_unroll(__isl_take isl_constraint *c, void *user)
2440 struct isl_find_unroll_data *data;
2441 int r;
2443 data = (struct isl_find_unroll_data *) user;
2444 r = update_unrolling_lower_bound(data, c);
2445 isl_constraint_free(c);
2447 return r;
2450 /* Look for a lower bound l(i) on the dimension at "depth"
2451 * and a size n such that "domain" is a subset of
2453 * { [i] : l(i) <= i_d < l(i) + n }
2455 * where d is "depth" and l(i) depends only on earlier dimensions.
2456 * Furthermore, try and find a lower bound such that n is as small as possible.
2457 * In particular, "n" needs to be finite.
2458 * "build" is the build in which the unrolling will be performed.
2459 * "expansion" is the expansion that needs to be applied to "domain"
2460 * in the unrolling that will be performed.
2462 * Inner dimensions have been eliminated from "domain" by the caller.
2464 * We first construct a collection of lower bounds on the input set
2465 * by computing its simple hull. We then iterate through them,
2466 * discarding those that we cannot use (either because they do not
2467 * involve the dimension at "depth" or because they have no corresponding
2468 * upper bound, meaning that "n" would be unbounded) and pick out the
2469 * best from the remaining ones.
2471 * If we cannot find a suitable lower bound, then we consider that
2472 * to be an error.
2474 static __isl_give isl_aff *find_unroll_lower_bound(
2475 __isl_keep isl_ast_build *build, __isl_keep isl_set *domain,
2476 int depth, __isl_keep isl_basic_map *expansion, int *n)
2478 struct isl_find_unroll_data data =
2479 { build, domain, depth, expansion, NULL, n, -1 };
2480 isl_basic_set *hull;
2482 hull = isl_set_simple_hull(isl_set_copy(domain));
2484 if (isl_basic_set_foreach_constraint(hull,
2485 &constraint_find_unroll, &data) < 0)
2486 goto error;
2488 isl_basic_set_free(hull);
2490 if (!data.lower)
2491 isl_die(isl_set_get_ctx(domain), isl_error_invalid,
2492 "cannot find lower bound for unrolling", return NULL);
2494 return data.lower;
2495 error:
2496 isl_basic_set_free(hull);
2497 return isl_aff_free(data.lower);
2500 /* Data structure for storing the results and the intermediate objects
2501 * of compute_domains.
2503 * "list" is the main result of the function and contains a list
2504 * of disjoint basic sets for which code should be generated.
2506 * "executed" and "build" are inputs to compute_domains.
2507 * "schedule_domain" is the domain of "executed".
2509 * "option" constains the domains at the current depth that should by
2510 * atomic, separated or unrolled. These domains are as specified by
2511 * the user, except that inner dimensions have been eliminated and
2512 * that they have been made pair-wise disjoint.
2514 * "sep_class" contains the user-specified split into separation classes
2515 * specialized to the current depth.
2516 * "done" contains the union of the separation domains that have already
2517 * been handled.
2519 struct isl_codegen_domains {
2520 isl_basic_set_list *list;
2522 isl_union_map *executed;
2523 isl_ast_build *build;
2524 isl_set *schedule_domain;
2526 isl_set *option[3];
2528 isl_map *sep_class;
2529 isl_set *done;
2532 /* Extend domains->list with a list of basic sets, one for each value
2533 * of the current dimension in "domain" and remove the corresponding
2534 * sets from the class domain. Return the updated class domain.
2535 * The divs that involve the current dimension have not been projected out
2536 * from this domain.
2538 * Since we are going to be iterating over the individual values,
2539 * we first check if there are any strides on the current dimension.
2540 * If there is, we rewrite the current dimension i as
2542 * i = stride i' + offset
2544 * and then iterate over individual values of i' instead.
2546 * We then look for a lower bound on i' and a size such that the domain
2547 * is a subset of
2549 * { [j,i'] : l(j) <= i' < l(j) + n }
2551 * and then take slices of the domain at values of i'
2552 * between l(j) and l(j) + n - 1.
2554 * We compute the unshifted simple hull of each slice to ensure that
2555 * we have a single basic set per offset. The slicing constraint
2556 * may get simplified away before the unshifted simple hull is taken
2557 * and may therefore in some rare cases disappear from the result.
2558 * We therefore explicitly add the constraint back after computing
2559 * the unshifted simple hull to ensure that the basic sets
2560 * remain disjoint. The constraints that are dropped by taking the hull
2561 * will be taken into account at the next level, as in the case of the
2562 * atomic option.
2564 * Finally, we map i' back to i and add each basic set to the list.
2565 * Since we may have dropped some constraints, we intersect with
2566 * the class domain again to ensure that each element in the list
2567 * is disjoint from the other class domains.
2569 static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains,
2570 __isl_take isl_set *domain, __isl_take isl_set *class_domain)
2572 int i, n;
2573 int depth;
2574 isl_ctx *ctx;
2575 isl_aff *lower;
2576 isl_multi_aff *expansion;
2577 isl_basic_map *bmap;
2578 isl_set *unroll_domain;
2579 isl_ast_build *build;
2581 if (!domain)
2582 return isl_set_free(class_domain);
2584 ctx = isl_set_get_ctx(domain);
2585 depth = isl_ast_build_get_depth(domains->build);
2586 build = isl_ast_build_copy(domains->build);
2587 domain = isl_ast_build_eliminate_inner(build, domain);
2588 domain = isl_set_intersect(domain, isl_ast_build_get_domain(build));
2589 build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
2590 expansion = isl_ast_build_get_stride_expansion(build);
2592 domain = isl_set_preimage_multi_aff(domain,
2593 isl_multi_aff_copy(expansion));
2594 domain = isl_ast_build_eliminate_divs(build, domain);
2596 isl_ast_build_free(build);
2598 bmap = isl_basic_map_from_multi_aff(expansion);
2600 lower = find_unroll_lower_bound(domains->build, domain, depth, bmap,
2601 &n);
2602 if (!lower)
2603 class_domain = isl_set_free(class_domain);
2605 unroll_domain = isl_set_empty(isl_set_get_space(domain));
2607 for (i = 0; class_domain && i < n; ++i) {
2608 isl_set *set;
2609 isl_basic_set *bset;
2610 isl_constraint *slice;
2611 isl_basic_set_list *list;
2613 slice = at_offset(depth, lower, i);
2614 set = isl_set_copy(domain);
2615 set = isl_set_add_constraint(set, isl_constraint_copy(slice));
2616 bset = isl_set_unshifted_simple_hull(set);
2617 bset = isl_basic_set_add_constraint(bset, slice);
2618 bset = isl_basic_set_apply(bset, isl_basic_map_copy(bmap));
2619 set = isl_set_from_basic_set(bset);
2620 unroll_domain = isl_set_union(unroll_domain, isl_set_copy(set));
2621 set = isl_set_intersect(set, isl_set_copy(class_domain));
2622 set = isl_set_make_disjoint(set);
2623 list = isl_basic_set_list_from_set(set);
2624 domains->list = isl_basic_set_list_concat(domains->list, list);
2627 class_domain = isl_set_subtract(class_domain, unroll_domain);
2629 isl_aff_free(lower);
2630 isl_set_free(domain);
2631 isl_basic_map_free(bmap);
2633 return class_domain;
2636 /* Add domains to domains->list for each individual value of the current
2637 * dimension, for that part of the schedule domain that lies in the
2638 * intersection of the option domain and the class domain.
2639 * Remove the corresponding sets from the class domain and
2640 * return the updated class domain.
2642 * We first break up the unroll option domain into individual pieces
2643 * and then handle each of them separately. The unroll option domain
2644 * has been made disjoint in compute_domains_init_options,
2646 * Note that we actively want to combine different pieces of the
2647 * schedule domain that have the same value at the current dimension.
2648 * We therefore need to break up the unroll option domain before
2649 * intersecting with class and schedule domain, hoping that the
2650 * unroll option domain specified by the user is relatively simple.
2652 static __isl_give isl_set *compute_unroll_domains(
2653 struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2655 isl_set *unroll_domain;
2656 isl_basic_set_list *unroll_list;
2657 int i, n;
2658 int empty;
2660 empty = isl_set_is_empty(domains->option[unroll]);
2661 if (empty < 0)
2662 return isl_set_free(class_domain);
2663 if (empty)
2664 return class_domain;
2666 unroll_domain = isl_set_copy(domains->option[unroll]);
2667 unroll_list = isl_basic_set_list_from_set(unroll_domain);
2669 n = isl_basic_set_list_n_basic_set(unroll_list);
2670 for (i = 0; i < n; ++i) {
2671 isl_basic_set *bset;
2673 bset = isl_basic_set_list_get_basic_set(unroll_list, i);
2674 unroll_domain = isl_set_from_basic_set(bset);
2675 unroll_domain = isl_set_intersect(unroll_domain,
2676 isl_set_copy(class_domain));
2677 unroll_domain = isl_set_intersect(unroll_domain,
2678 isl_set_copy(domains->schedule_domain));
2680 empty = isl_set_is_empty(unroll_domain);
2681 if (empty >= 0 && empty) {
2682 isl_set_free(unroll_domain);
2683 continue;
2686 class_domain = do_unroll(domains, unroll_domain, class_domain);
2689 isl_basic_set_list_free(unroll_list);
2691 return class_domain;
2694 /* Try and construct a single basic set that includes the intersection of
2695 * the schedule domain, the atomic option domain and the class domain.
2696 * Add the resulting basic set(s) to domains->list and remove them
2697 * from class_domain. Return the updated class domain.
2699 * We construct a single domain rather than trying to combine
2700 * the schedule domains of individual domains because we are working
2701 * within a single component so that non-overlapping schedule domains
2702 * should already have been separated.
2703 * We do however need to make sure that this single domains is a subset
2704 * of the class domain so that it would not intersect with any other
2705 * class domains. This means that we may end up splitting up the atomic
2706 * domain in case separation classes are being used.
2708 * "domain" is the intersection of the schedule domain and the class domain,
2709 * with inner dimensions projected out.
2711 static __isl_give isl_set *compute_atomic_domain(
2712 struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2714 isl_basic_set *bset;
2715 isl_basic_set_list *list;
2716 isl_set *domain, *atomic_domain;
2717 int empty;
2719 domain = isl_set_copy(domains->option[atomic]);
2720 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2721 domain = isl_set_intersect(domain,
2722 isl_set_copy(domains->schedule_domain));
2723 empty = isl_set_is_empty(domain);
2724 if (empty < 0)
2725 class_domain = isl_set_free(class_domain);
2726 if (empty) {
2727 isl_set_free(domain);
2728 return class_domain;
2731 domain = isl_ast_build_eliminate(domains->build, domain);
2732 domain = isl_set_coalesce(domain);
2733 bset = isl_set_unshifted_simple_hull(domain);
2734 domain = isl_set_from_basic_set(bset);
2735 atomic_domain = isl_set_copy(domain);
2736 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2737 class_domain = isl_set_subtract(class_domain, atomic_domain);
2738 domain = isl_set_make_disjoint(domain);
2739 list = isl_basic_set_list_from_set(domain);
2740 domains->list = isl_basic_set_list_concat(domains->list, list);
2742 return class_domain;
2745 /* Split up the schedule domain into uniform basic sets,
2746 * in the sense that each element in a basic set is associated to
2747 * elements of the same domains, and add the result to domains->list.
2748 * Do this for that part of the schedule domain that lies in the
2749 * intersection of "class_domain" and the separate option domain.
2751 * "class_domain" may or may not include the constraints
2752 * of the schedule domain, but this does not make a difference
2753 * since we are going to intersect it with the domain of the inverse schedule.
2754 * If it includes schedule domain constraints, then they may involve
2755 * inner dimensions, but we will eliminate them in separation_domain.
2757 static int compute_separate_domain(struct isl_codegen_domains *domains,
2758 __isl_keep isl_set *class_domain)
2760 isl_space *space;
2761 isl_set *domain;
2762 isl_union_map *executed;
2763 isl_basic_set_list *list;
2764 int empty;
2766 domain = isl_set_copy(domains->option[separate]);
2767 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2768 executed = isl_union_map_copy(domains->executed);
2769 executed = isl_union_map_intersect_domain(executed,
2770 isl_union_set_from_set(domain));
2771 empty = isl_union_map_is_empty(executed);
2772 if (empty < 0 || empty) {
2773 isl_union_map_free(executed);
2774 return empty < 0 ? -1 : 0;
2777 space = isl_set_get_space(class_domain);
2778 domain = separate_schedule_domains(space, executed, domains->build);
2780 list = isl_basic_set_list_from_set(domain);
2781 domains->list = isl_basic_set_list_concat(domains->list, list);
2783 return 0;
2786 /* Split up the domain at the current depth into disjoint
2787 * basic sets for which code should be generated separately
2788 * for the given separation class domain.
2790 * If any separation classes have been defined, then "class_domain"
2791 * is the domain of the current class and does not refer to inner dimensions.
2792 * Otherwise, "class_domain" is the universe domain.
2794 * We first make sure that the class domain is disjoint from
2795 * previously considered class domains.
2797 * The separate domains can be computed directly from the "class_domain".
2799 * The unroll, atomic and remainder domains need the constraints
2800 * from the schedule domain.
2802 * For unrolling, the actual schedule domain is needed (with divs that
2803 * may refer to the current dimension) so that stride detection can be
2804 * performed.
2806 * For atomic and remainder domains, inner dimensions and divs involving
2807 * the current dimensions should be eliminated.
2808 * In case we are working within a separation class, we need to intersect
2809 * the result with the current "class_domain" to ensure that the domains
2810 * are disjoint from those generated from other class domains.
2812 * The domain that has been made atomic may be larger than specified
2813 * by the user since it needs to be representable as a single basic set.
2814 * This possibly larger domain is removed from class_domain by
2815 * compute_atomic_domain. It is computed first so that the extended domain
2816 * would not overlap with any domains computed before.
2817 * Similary, the unrolled domains may have some constraints removed and
2818 * may therefore also be larger than specified by the user.
2820 * If anything is left after handling separate, unroll and atomic,
2821 * we split it up into basic sets and append the basic sets to domains->list.
2823 static int compute_partial_domains(struct isl_codegen_domains *domains,
2824 __isl_take isl_set *class_domain)
2826 isl_basic_set_list *list;
2827 isl_set *domain;
2829 class_domain = isl_set_subtract(class_domain,
2830 isl_set_copy(domains->done));
2831 domains->done = isl_set_union(domains->done,
2832 isl_set_copy(class_domain));
2834 class_domain = compute_atomic_domain(domains, class_domain);
2835 class_domain = compute_unroll_domains(domains, class_domain);
2837 domain = isl_set_copy(class_domain);
2839 if (compute_separate_domain(domains, domain) < 0)
2840 goto error;
2841 domain = isl_set_subtract(domain,
2842 isl_set_copy(domains->option[separate]));
2844 domain = isl_set_intersect(domain,
2845 isl_set_copy(domains->schedule_domain));
2847 domain = isl_ast_build_eliminate(domains->build, domain);
2848 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2850 domain = isl_set_coalesce(domain);
2851 domain = isl_set_make_disjoint(domain);
2853 list = isl_basic_set_list_from_set(domain);
2854 domains->list = isl_basic_set_list_concat(domains->list, list);
2856 isl_set_free(class_domain);
2858 return 0;
2859 error:
2860 isl_set_free(domain);
2861 isl_set_free(class_domain);
2862 return -1;
2865 /* Split up the domain at the current depth into disjoint
2866 * basic sets for which code should be generated separately
2867 * for the separation class identified by "pnt".
2869 * We extract the corresponding class domain from domains->sep_class,
2870 * eliminate inner dimensions and pass control to compute_partial_domains.
2872 static int compute_class_domains(__isl_take isl_point *pnt, void *user)
2874 struct isl_codegen_domains *domains = user;
2875 isl_set *class_set;
2876 isl_set *domain;
2877 int disjoint;
2879 class_set = isl_set_from_point(pnt);
2880 domain = isl_map_domain(isl_map_intersect_range(
2881 isl_map_copy(domains->sep_class), class_set));
2882 domain = isl_ast_build_compute_gist(domains->build, domain);
2883 domain = isl_ast_build_eliminate(domains->build, domain);
2885 disjoint = isl_set_plain_is_disjoint(domain, domains->schedule_domain);
2886 if (disjoint < 0)
2887 return -1;
2888 if (disjoint) {
2889 isl_set_free(domain);
2890 return 0;
2893 return compute_partial_domains(domains, domain);
2896 /* Extract the domains at the current depth that should be atomic,
2897 * separated or unrolled and store them in option.
2899 * The domains specified by the user might overlap, so we make
2900 * them disjoint by subtracting earlier domains from later domains.
2902 static void compute_domains_init_options(isl_set *option[3],
2903 __isl_keep isl_ast_build *build)
2905 enum isl_ast_build_domain_type type, type2;
2907 for (type = atomic; type <= separate; ++type) {
2908 option[type] = isl_ast_build_get_option_domain(build, type);
2909 for (type2 = atomic; type2 < type; ++type2)
2910 option[type] = isl_set_subtract(option[type],
2911 isl_set_copy(option[type2]));
2914 option[unroll] = isl_set_coalesce(option[unroll]);
2915 option[unroll] = isl_set_make_disjoint(option[unroll]);
2918 /* Split up the domain at the current depth into disjoint
2919 * basic sets for which code should be generated separately,
2920 * based on the user-specified options.
2921 * Return the list of disjoint basic sets.
2923 * There are three kinds of domains that we need to keep track of.
2924 * - the "schedule domain" is the domain of "executed"
2925 * - the "class domain" is the domain corresponding to the currrent
2926 * separation class
2927 * - the "option domain" is the domain corresponding to one of the options
2928 * atomic, unroll or separate
2930 * We first consider the individial values of the separation classes
2931 * and split up the domain for each of them separately.
2932 * Finally, we consider the remainder. If no separation classes were
2933 * specified, then we call compute_partial_domains with the universe
2934 * "class_domain". Otherwise, we take the "schedule_domain" as "class_domain",
2935 * with inner dimensions removed. We do this because we want to
2936 * avoid computing the complement of the class domains (i.e., the difference
2937 * between the universe and domains->done).
2939 static __isl_give isl_basic_set_list *compute_domains(
2940 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2942 struct isl_codegen_domains domains;
2943 isl_ctx *ctx;
2944 isl_set *domain;
2945 isl_union_set *schedule_domain;
2946 isl_set *classes;
2947 isl_space *space;
2948 int n_param;
2949 enum isl_ast_build_domain_type type;
2950 int empty;
2952 if (!executed)
2953 return NULL;
2955 ctx = isl_union_map_get_ctx(executed);
2956 domains.list = isl_basic_set_list_alloc(ctx, 0);
2958 schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
2959 domain = isl_set_from_union_set(schedule_domain);
2961 compute_domains_init_options(domains.option, build);
2963 domains.sep_class = isl_ast_build_get_separation_class(build);
2964 classes = isl_map_range(isl_map_copy(domains.sep_class));
2965 n_param = isl_set_dim(classes, isl_dim_param);
2966 classes = isl_set_project_out(classes, isl_dim_param, 0, n_param);
2968 space = isl_set_get_space(domain);
2969 domains.build = build;
2970 domains.schedule_domain = isl_set_copy(domain);
2971 domains.executed = executed;
2972 domains.done = isl_set_empty(space);
2974 if (isl_set_foreach_point(classes, &compute_class_domains, &domains) < 0)
2975 domains.list = isl_basic_set_list_free(domains.list);
2976 isl_set_free(classes);
2978 empty = isl_set_is_empty(domains.done);
2979 if (empty < 0) {
2980 domains.list = isl_basic_set_list_free(domains.list);
2981 domain = isl_set_free(domain);
2982 } else if (empty) {
2983 isl_set_free(domain);
2984 domain = isl_set_universe(isl_set_get_space(domains.done));
2985 } else {
2986 domain = isl_ast_build_eliminate(build, domain);
2988 if (compute_partial_domains(&domains, domain) < 0)
2989 domains.list = isl_basic_set_list_free(domains.list);
2991 isl_set_free(domains.schedule_domain);
2992 isl_set_free(domains.done);
2993 isl_map_free(domains.sep_class);
2994 for (type = atomic; type <= separate; ++type)
2995 isl_set_free(domains.option[type]);
2997 return domains.list;
3000 /* Generate code for a single component, after shifting (if any)
3001 * has been applied.
3003 * We first split up the domain at the current depth into disjoint
3004 * basic sets based on the user-specified options.
3005 * Then we generated code for each of them and concatenate the results.
3007 static __isl_give isl_ast_graft_list *generate_shifted_component(
3008 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3010 isl_basic_set_list *domain_list;
3011 isl_ast_graft_list *list = NULL;
3013 domain_list = compute_domains(executed, build);
3014 list = generate_parallel_domains(domain_list, executed, build);
3016 isl_basic_set_list_free(domain_list);
3017 isl_union_map_free(executed);
3018 isl_ast_build_free(build);
3020 return list;
3023 struct isl_set_map_pair {
3024 isl_set *set;
3025 isl_map *map;
3028 /* Given an array "domain" of isl_set_map_pairs and an array "order"
3029 * of indices into the "domain" array,
3030 * return the union of the "map" fields of the elements
3031 * indexed by the first "n" elements of "order".
3033 static __isl_give isl_union_map *construct_component_executed(
3034 struct isl_set_map_pair *domain, int *order, int n)
3036 int i;
3037 isl_map *map;
3038 isl_union_map *executed;
3040 map = isl_map_copy(domain[order[0]].map);
3041 executed = isl_union_map_from_map(map);
3042 for (i = 1; i < n; ++i) {
3043 map = isl_map_copy(domain[order[i]].map);
3044 executed = isl_union_map_add_map(executed, map);
3047 return executed;
3050 /* Generate code for a single component, after shifting (if any)
3051 * has been applied.
3053 * The component inverse schedule is specified as the "map" fields
3054 * of the elements of "domain" indexed by the first "n" elements of "order".
3056 static __isl_give isl_ast_graft_list *generate_shifted_component_from_list(
3057 struct isl_set_map_pair *domain, int *order, int n,
3058 __isl_take isl_ast_build *build)
3060 isl_union_map *executed;
3062 executed = construct_component_executed(domain, order, n);
3063 return generate_shifted_component(executed, build);
3066 /* Does set dimension "pos" of "set" have an obviously fixed value?
3068 static int dim_is_fixed(__isl_keep isl_set *set, int pos)
3070 int fixed;
3071 isl_val *v;
3073 v = isl_set_plain_get_val_if_fixed(set, isl_dim_set, pos);
3074 if (!v)
3075 return -1;
3076 fixed = !isl_val_is_nan(v);
3077 isl_val_free(v);
3079 return fixed;
3082 /* Given an array "domain" of isl_set_map_pairs and an array "order"
3083 * of indices into the "domain" array,
3084 * do all (except for at most one) of the "set" field of the elements
3085 * indexed by the first "n" elements of "order" have a fixed value
3086 * at position "depth"?
3088 static int at_most_one_non_fixed(struct isl_set_map_pair *domain,
3089 int *order, int n, int depth)
3091 int i;
3092 int non_fixed = -1;
3094 for (i = 0; i < n; ++i) {
3095 int f;
3097 f = dim_is_fixed(domain[order[i]].set, depth);
3098 if (f < 0)
3099 return -1;
3100 if (f)
3101 continue;
3102 if (non_fixed >= 0)
3103 return 0;
3104 non_fixed = i;
3107 return 1;
3110 /* Given an array "domain" of isl_set_map_pairs and an array "order"
3111 * of indices into the "domain" array,
3112 * eliminate the inner dimensions from the "set" field of the elements
3113 * indexed by the first "n" elements of "order", provided the current
3114 * dimension does not have a fixed value.
3116 * Return the index of the first element in "order" with a corresponding
3117 * "set" field that does not have an (obviously) fixed value.
3119 static int eliminate_non_fixed(struct isl_set_map_pair *domain,
3120 int *order, int n, int depth, __isl_keep isl_ast_build *build)
3122 int i;
3123 int base = -1;
3125 for (i = n - 1; i >= 0; --i) {
3126 int f;
3127 f = dim_is_fixed(domain[order[i]].set, depth);
3128 if (f < 0)
3129 return -1;
3130 if (f)
3131 continue;
3132 domain[order[i]].set = isl_ast_build_eliminate_inner(build,
3133 domain[order[i]].set);
3134 base = i;
3137 return base;
3140 /* Given an array "domain" of isl_set_map_pairs and an array "order"
3141 * of indices into the "domain" array,
3142 * find the element of "domain" (amongst those indexed by the first "n"
3143 * elements of "order") with the "set" field that has the smallest
3144 * value for the current iterator.
3146 * Note that the domain with the smallest value may depend on the parameters
3147 * and/or outer loop dimension. Since the result of this function is only
3148 * used as heuristic, we only make a reasonable attempt at finding the best
3149 * domain, one that should work in case a single domain provides the smallest
3150 * value for the current dimension over all values of the parameters
3151 * and outer dimensions.
3153 * In particular, we compute the smallest value of the first domain
3154 * and replace it by that of any later domain if that later domain
3155 * has a smallest value that is smaller for at least some value
3156 * of the parameters and outer dimensions.
3158 static int first_offset(struct isl_set_map_pair *domain, int *order, int n,
3159 __isl_keep isl_ast_build *build)
3161 int i;
3162 isl_map *min_first;
3163 int first = 0;
3165 min_first = isl_ast_build_map_to_iterator(build,
3166 isl_set_copy(domain[order[0]].set));
3167 min_first = isl_map_lexmin(min_first);
3169 for (i = 1; i < n; ++i) {
3170 isl_map *min, *test;
3171 int empty;
3173 min = isl_ast_build_map_to_iterator(build,
3174 isl_set_copy(domain[order[i]].set));
3175 min = isl_map_lexmin(min);
3176 test = isl_map_copy(min);
3177 test = isl_map_apply_domain(isl_map_copy(min_first), test);
3178 test = isl_map_order_lt(test, isl_dim_in, 0, isl_dim_out, 0);
3179 empty = isl_map_is_empty(test);
3180 isl_map_free(test);
3181 if (empty >= 0 && !empty) {
3182 isl_map_free(min_first);
3183 first = i;
3184 min_first = min;
3185 } else
3186 isl_map_free(min);
3188 if (empty < 0)
3189 break;
3192 isl_map_free(min_first);
3194 return i < n ? -1 : first;
3197 /* Construct a shifted inverse schedule based on the original inverse schedule,
3198 * the stride and the offset.
3200 * The original inverse schedule is specified as the "map" fields
3201 * of the elements of "domain" indexed by the first "n" elements of "order".
3203 * "stride" and "offset" are such that the difference
3204 * between the values of the current dimension of domain "i"
3205 * and the values of the current dimension for some reference domain are
3206 * equal to
3208 * stride * integer + offset[i]
3210 * Moreover, 0 <= offset[i] < stride.
3212 * For each domain, we create a map
3214 * { [..., j, ...] -> [..., j - offset[i], offset[i], ....] }
3216 * where j refers to the current dimension and the other dimensions are
3217 * unchanged, and apply this map to the original schedule domain.
3219 * For example, for the original schedule
3221 * { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3223 * and assuming the offset is 0 for the A domain and 1 for the B domain,
3224 * we apply the mapping
3226 * { [j] -> [j, 0] }
3228 * to the schedule of the "A" domain and the mapping
3230 * { [j - 1] -> [j, 1] }
3232 * to the schedule of the "B" domain.
3235 * Note that after the transformation, the differences between pairs
3236 * of values of the current dimension over all domains are multiples
3237 * of stride and that we have therefore exposed the stride.
3240 * To see that the mapping preserves the lexicographic order,
3241 * first note that each of the individual maps above preserves the order.
3242 * If the value of the current iterator is j1 in one domain and j2 in another,
3243 * then if j1 = j2, we know that the same map is applied to both domains
3244 * and the order is preserved.
3245 * Otherwise, let us assume, without loss of generality, that j1 < j2.
3246 * If c1 >= c2 (with c1 and c2 the corresponding offsets), then
3248 * j1 - c1 < j2 - c2
3250 * and the order is preserved.
3251 * If c1 < c2, then we know
3253 * 0 <= c2 - c1 < s
3255 * We also have
3257 * j2 - j1 = n * s + r
3259 * with n >= 0 and 0 <= r < s.
3260 * In other words, r = c2 - c1.
3261 * If n > 0, then
3263 * j1 - c1 < j2 - c2
3265 * If n = 0, then
3267 * j1 - c1 = j2 - c2
3269 * and so
3271 * (j1 - c1, c1) << (j2 - c2, c2)
3273 * with "<<" the lexicographic order, proving that the order is preserved
3274 * in all cases.
3276 static __isl_give isl_union_map *contruct_shifted_executed(
3277 struct isl_set_map_pair *domain, int *order, int n,
3278 __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3279 __isl_take isl_ast_build *build)
3281 int i;
3282 isl_union_map *executed;
3283 isl_space *space;
3284 isl_map *map;
3285 int depth;
3286 isl_constraint *c;
3288 depth = isl_ast_build_get_depth(build);
3289 space = isl_ast_build_get_space(build, 1);
3290 executed = isl_union_map_empty(isl_space_copy(space));
3291 space = isl_space_map_from_set(space);
3292 map = isl_map_identity(isl_space_copy(space));
3293 map = isl_map_eliminate(map, isl_dim_out, depth, 1);
3294 map = isl_map_insert_dims(map, isl_dim_out, depth + 1, 1);
3295 space = isl_space_insert_dims(space, isl_dim_out, depth + 1, 1);
3297 c = isl_equality_alloc(isl_local_space_from_space(space));
3298 c = isl_constraint_set_coefficient_si(c, isl_dim_in, depth, 1);
3299 c = isl_constraint_set_coefficient_si(c, isl_dim_out, depth, -1);
3301 for (i = 0; i < n; ++i) {
3302 isl_map *map_i;
3303 isl_val *v;
3305 v = isl_multi_val_get_val(offset, i);
3306 if (!v)
3307 break;
3308 map_i = isl_map_copy(map);
3309 map_i = isl_map_fix_val(map_i, isl_dim_out, depth + 1,
3310 isl_val_copy(v));
3311 v = isl_val_neg(v);
3312 c = isl_constraint_set_constant_val(c, v);
3313 map_i = isl_map_add_constraint(map_i, isl_constraint_copy(c));
3315 map_i = isl_map_apply_domain(isl_map_copy(domain[order[i]].map),
3316 map_i);
3317 executed = isl_union_map_add_map(executed, map_i);
3320 isl_constraint_free(c);
3321 isl_map_free(map);
3323 if (i < n)
3324 executed = isl_union_map_free(executed);
3326 return executed;
3329 /* Generate code for a single component, after exposing the stride,
3330 * given that the schedule domain is "shifted strided".
3332 * The component inverse schedule is specified as the "map" fields
3333 * of the elements of "domain" indexed by the first "n" elements of "order".
3335 * The schedule domain being "shifted strided" means that the differences
3336 * between the values of the current dimension of domain "i"
3337 * and the values of the current dimension for some reference domain are
3338 * equal to
3340 * stride * integer + offset[i]
3342 * We first look for the domain with the "smallest" value for the current
3343 * dimension and adjust the offsets such that the offset of the "smallest"
3344 * domain is equal to zero. The other offsets are reduced modulo stride.
3346 * Based on this information, we construct a new inverse schedule in
3347 * contruct_shifted_executed that exposes the stride.
3348 * Since this involves the introduction of a new schedule dimension,
3349 * the build needs to be changed accodingly.
3350 * After computing the AST, the newly introduced dimension needs
3351 * to be removed again from the list of grafts. We do this by plugging
3352 * in a mapping that represents the new schedule domain in terms of the
3353 * old schedule domain.
3355 static __isl_give isl_ast_graft_list *generate_shift_component(
3356 struct isl_set_map_pair *domain, int *order, int n,
3357 __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3358 __isl_take isl_ast_build *build)
3360 isl_ast_graft_list *list;
3361 int first;
3362 int depth;
3363 isl_ctx *ctx;
3364 isl_val *val;
3365 isl_multi_val *mv;
3366 isl_space *space;
3367 isl_multi_aff *ma, *zero;
3368 isl_union_map *executed;
3370 ctx = isl_ast_build_get_ctx(build);
3371 depth = isl_ast_build_get_depth(build);
3373 first = first_offset(domain, order, n, build);
3374 if (first < 0)
3375 goto error;
3377 mv = isl_multi_val_copy(offset);
3378 val = isl_multi_val_get_val(offset, first);
3379 val = isl_val_neg(val);
3380 mv = isl_multi_val_add_val(mv, val);
3381 mv = isl_multi_val_mod_val(mv, isl_val_copy(stride));
3383 executed = contruct_shifted_executed(domain, order, n, stride, mv,
3384 build);
3385 space = isl_ast_build_get_space(build, 1);
3386 space = isl_space_map_from_set(space);
3387 ma = isl_multi_aff_identity(isl_space_copy(space));
3388 space = isl_space_from_domain(isl_space_domain(space));
3389 space = isl_space_add_dims(space, isl_dim_out, 1);
3390 zero = isl_multi_aff_zero(space);
3391 ma = isl_multi_aff_range_splice(ma, depth + 1, zero);
3392 build = isl_ast_build_insert_dim(build, depth + 1);
3393 list = generate_shifted_component(executed, build);
3395 list = isl_ast_graft_list_preimage_multi_aff(list, ma);
3397 isl_multi_val_free(mv);
3399 return list;
3400 error:
3401 isl_ast_build_free(build);
3402 return NULL;
3405 /* Generate code for a single component.
3407 * The component inverse schedule is specified as the "map" fields
3408 * of the elements of "domain" indexed by the first "n" elements of "order".
3410 * This function may modify the "set" fields of "domain".
3412 * Before proceeding with the actual code generation for the component,
3413 * we first check if there are any "shifted" strides, meaning that
3414 * the schedule domains of the individual domains are all strided,
3415 * but that they have different offsets, resulting in the union
3416 * of schedule domains not being strided anymore.
3418 * The simplest example is the schedule
3420 * { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3422 * Both schedule domains are strided, but their union is not.
3423 * This function detects such cases and then rewrites the schedule to
3425 * { A[i] -> [2i, 0]: 0 <= i < 10; B[i] -> [2i, 1] : 0 <= i < 10 }
3427 * In the new schedule, the schedule domains have the same offset (modulo
3428 * the stride), ensuring that the union of schedule domains is also strided.
3431 * If there is only a single domain in the component, then there is
3432 * nothing to do. Similarly, if the current schedule dimension has
3433 * a fixed value for almost all domains then there is nothing to be done.
3434 * In particular, we need at least two domains where the current schedule
3435 * dimension does not have a fixed value.
3436 * Finally, if any of the options refer to the current schedule dimension,
3437 * then we bail out as well. It would be possible to reformulate the options
3438 * in terms of the new schedule domain, but that would introduce constraints
3439 * that separate the domains in the options and that is something we would
3440 * like to avoid.
3443 * To see if there is any shifted stride, we look at the differences
3444 * between the values of the current dimension in pairs of domains
3445 * for equal values of outer dimensions. These differences should be
3446 * of the form
3448 * m x + r
3450 * with "m" the stride and "r" a constant. Note that we cannot perform
3451 * this analysis on individual domains as the lower bound in each domain
3452 * may depend on parameters or outer dimensions and so the current dimension
3453 * itself may not have a fixed remainder on division by the stride.
3455 * In particular, we compare the first domain that does not have an
3456 * obviously fixed value for the current dimension to itself and all
3457 * other domains and collect the offsets and the gcd of the strides.
3458 * If the gcd becomes one, then we failed to find shifted strides.
3459 * If the gcd is zero, then the differences were all fixed, meaning
3460 * that some domains had non-obviously fixed values for the current dimension.
3461 * If all the offsets are the same (for those domains that do not have
3462 * an obviously fixed value for the current dimension), then we do not
3463 * apply the transformation.
3464 * If none of the domains were skipped, then there is nothing to do.
3465 * If some of them were skipped, then if we apply separation, the schedule
3466 * domain should get split in pieces with a (non-shifted) stride.
3468 * Otherwise, we apply a shift to expose the stride in
3469 * generate_shift_component.
3471 static __isl_give isl_ast_graft_list *generate_component(
3472 struct isl_set_map_pair *domain, int *order, int n,
3473 __isl_take isl_ast_build *build)
3475 int i, d;
3476 int depth;
3477 isl_ctx *ctx;
3478 isl_map *map;
3479 isl_set *deltas;
3480 isl_val *gcd = NULL;
3481 isl_multi_val *mv;
3482 int fixed, skip;
3483 int base;
3484 isl_ast_graft_list *list;
3485 int res = 0;
3487 depth = isl_ast_build_get_depth(build);
3489 skip = n == 1;
3490 if (skip >= 0 && !skip)
3491 skip = at_most_one_non_fixed(domain, order, n, depth);
3492 if (skip >= 0 && !skip)
3493 skip = isl_ast_build_options_involve_depth(build);
3494 if (skip < 0)
3495 goto error;
3496 if (skip)
3497 return generate_shifted_component_from_list(domain,
3498 order, n, build);
3500 base = eliminate_non_fixed(domain, order, n, depth, build);
3501 if (base < 0)
3502 goto error;
3504 ctx = isl_ast_build_get_ctx(build);
3506 mv = isl_multi_val_zero(isl_space_set_alloc(ctx, 0, n));
3508 fixed = 1;
3509 for (i = 0; i < n; ++i) {
3510 isl_val *r, *m;
3512 map = isl_map_from_domain_and_range(
3513 isl_set_copy(domain[order[base]].set),
3514 isl_set_copy(domain[order[i]].set));
3515 for (d = 0; d < depth; ++d)
3516 map = isl_map_equate(map, isl_dim_in, d,
3517 isl_dim_out, d);
3518 deltas = isl_map_deltas(map);
3519 res = isl_set_dim_residue_class_val(deltas, depth, &m, &r);
3520 isl_set_free(deltas);
3521 if (res < 0)
3522 break;
3524 if (i == 0)
3525 gcd = m;
3526 else
3527 gcd = isl_val_gcd(gcd, m);
3528 if (isl_val_is_one(gcd)) {
3529 isl_val_free(r);
3530 break;
3532 mv = isl_multi_val_set_val(mv, i, r);
3534 res = dim_is_fixed(domain[order[i]].set, depth);
3535 if (res < 0)
3536 break;
3537 if (res)
3538 continue;
3540 if (fixed && i > base) {
3541 isl_val *a, *b;
3542 a = isl_multi_val_get_val(mv, i);
3543 b = isl_multi_val_get_val(mv, base);
3544 if (isl_val_ne(a, b))
3545 fixed = 0;
3546 isl_val_free(a);
3547 isl_val_free(b);
3551 if (res < 0 || !gcd) {
3552 isl_ast_build_free(build);
3553 list = NULL;
3554 } else if (i < n || fixed || isl_val_is_zero(gcd)) {
3555 list = generate_shifted_component_from_list(domain,
3556 order, n, build);
3557 } else {
3558 list = generate_shift_component(domain, order, n, gcd, mv,
3559 build);
3562 isl_val_free(gcd);
3563 isl_multi_val_free(mv);
3565 return list;
3566 error:
3567 isl_ast_build_free(build);
3568 return NULL;
3571 /* Store both "map" itself and its domain in the
3572 * structure pointed to by *next and advance to the next array element.
3574 static int extract_domain(__isl_take isl_map *map, void *user)
3576 struct isl_set_map_pair **next = user;
3578 (*next)->map = isl_map_copy(map);
3579 (*next)->set = isl_map_domain(map);
3580 (*next)++;
3582 return 0;
3585 /* Internal data for any_scheduled_after.
3587 * "depth" is the number of loops that have already been generated
3588 * "group_coscheduled" is a local copy of options->ast_build_group_coscheduled
3589 * "domain" is an array of set-map pairs corresponding to the different
3590 * iteration domains. The set is the schedule domain, i.e., the domain
3591 * of the inverse schedule, while the map is the inverse schedule itself.
3593 struct isl_any_scheduled_after_data {
3594 int depth;
3595 int group_coscheduled;
3596 struct isl_set_map_pair *domain;
3599 /* Is any element of domain "i" scheduled after any element of domain "j"
3600 * (for a common iteration of the first data->depth loops)?
3602 * data->domain[i].set contains the domain of the inverse schedule
3603 * for domain "i", i.e., elements in the schedule domain.
3605 * If data->group_coscheduled is set, then we also return 1 if there
3606 * is any pair of elements in the two domains that are scheduled together.
3608 static int any_scheduled_after(int i, int j, void *user)
3610 struct isl_any_scheduled_after_data *data = user;
3611 int dim = isl_set_dim(data->domain[i].set, isl_dim_set);
3612 int pos;
3614 for (pos = data->depth; pos < dim; ++pos) {
3615 int follows;
3617 follows = isl_set_follows_at(data->domain[i].set,
3618 data->domain[j].set, pos);
3620 if (follows < -1)
3621 return -1;
3622 if (follows > 0)
3623 return 1;
3624 if (follows < 0)
3625 return 0;
3628 return data->group_coscheduled;
3631 /* Look for independent components at the current depth and generate code
3632 * for each component separately. The resulting lists of grafts are
3633 * merged in an attempt to combine grafts with identical guards.
3635 * Code for two domains can be generated separately if all the elements
3636 * of one domain are scheduled before (or together with) all the elements
3637 * of the other domain. We therefore consider the graph with as nodes
3638 * the domains and an edge between two nodes if any element of the first
3639 * node is scheduled after any element of the second node.
3640 * If the ast_build_group_coscheduled is set, then we also add an edge if
3641 * there is any pair of elements in the two domains that are scheduled
3642 * together.
3643 * Code is then generated (by generate_component)
3644 * for each of the strongly connected components in this graph
3645 * in their topological order.
3647 * Since the test is performed on the domain of the inverse schedules of
3648 * the different domains, we precompute these domains and store
3649 * them in data.domain.
3651 static __isl_give isl_ast_graft_list *generate_components(
3652 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3654 int i;
3655 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3656 int n = isl_union_map_n_map(executed);
3657 struct isl_any_scheduled_after_data data;
3658 struct isl_set_map_pair *next;
3659 struct isl_tarjan_graph *g = NULL;
3660 isl_ast_graft_list *list = NULL;
3661 int n_domain = 0;
3663 data.domain = isl_calloc_array(ctx, struct isl_set_map_pair, n);
3664 if (!data.domain)
3665 goto error;
3666 n_domain = n;
3668 next = data.domain;
3669 if (isl_union_map_foreach_map(executed, &extract_domain, &next) < 0)
3670 goto error;
3672 if (!build)
3673 goto error;
3674 data.depth = isl_ast_build_get_depth(build);
3675 data.group_coscheduled = isl_options_get_ast_build_group_coscheduled(ctx);
3676 g = isl_tarjan_graph_init(ctx, n, &any_scheduled_after, &data);
3677 if (!g)
3678 goto error;
3680 list = isl_ast_graft_list_alloc(ctx, 0);
3682 i = 0;
3683 while (list && n) {
3684 isl_ast_graft_list *list_c;
3685 int first = i;
3687 if (g->order[i] == -1)
3688 isl_die(ctx, isl_error_internal, "cannot happen",
3689 goto error);
3690 ++i; --n;
3691 while (g->order[i] != -1) {
3692 ++i; --n;
3695 list_c = generate_component(data.domain,
3696 g->order + first, i - first,
3697 isl_ast_build_copy(build));
3698 list = isl_ast_graft_list_merge(list, list_c, build);
3700 ++i;
3703 if (0)
3704 error: list = isl_ast_graft_list_free(list);
3705 isl_tarjan_graph_free(g);
3706 for (i = 0; i < n_domain; ++i) {
3707 isl_map_free(data.domain[i].map);
3708 isl_set_free(data.domain[i].set);
3710 free(data.domain);
3711 isl_union_map_free(executed);
3712 isl_ast_build_free(build);
3714 return list;
3717 /* Generate code for the next level (and all inner levels).
3719 * If "executed" is empty, i.e., no code needs to be generated,
3720 * then we return an empty list.
3722 * If we have already generated code for all loop levels, then we pass
3723 * control to generate_inner_level.
3725 * If "executed" lives in a single space, i.e., if code needs to be
3726 * generated for a single domain, then there can only be a single
3727 * component and we go directly to generate_shifted_component.
3728 * Otherwise, we call generate_components to detect the components
3729 * and to call generate_component on each of them separately.
3731 static __isl_give isl_ast_graft_list *generate_next_level(
3732 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3734 int depth;
3736 if (!build || !executed)
3737 goto error;
3739 if (isl_union_map_is_empty(executed)) {
3740 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3741 isl_union_map_free(executed);
3742 isl_ast_build_free(build);
3743 return isl_ast_graft_list_alloc(ctx, 0);
3746 depth = isl_ast_build_get_depth(build);
3747 if (depth >= isl_ast_build_dim(build, isl_dim_set))
3748 return generate_inner_level(executed, build);
3750 if (isl_union_map_n_map(executed) == 1)
3751 return generate_shifted_component(executed, build);
3753 return generate_components(executed, build);
3754 error:
3755 isl_union_map_free(executed);
3756 isl_ast_build_free(build);
3757 return NULL;
3760 /* Internal data structure used by isl_ast_build_ast_from_schedule.
3761 * internal, executed and build are the inputs to generate_code.
3762 * list collects the output.
3764 struct isl_generate_code_data {
3765 int internal;
3766 isl_union_map *executed;
3767 isl_ast_build *build;
3769 isl_ast_graft_list *list;
3772 /* Given an inverse schedule in terms of the external build schedule, i.e.,
3774 * [E -> S] -> D
3776 * with E the external build schedule and S the additional schedule "space",
3777 * reformulate the inverse schedule in terms of the internal schedule domain,
3778 * i.e., return
3780 * [I -> S] -> D
3782 * We first obtain a mapping
3784 * I -> E
3786 * take the inverse and the product with S -> S, resulting in
3788 * [I -> S] -> [E -> S]
3790 * Applying the map to the input produces the desired result.
3792 static __isl_give isl_union_map *internal_executed(
3793 __isl_take isl_union_map *executed, __isl_keep isl_space *space,
3794 __isl_keep isl_ast_build *build)
3796 isl_map *id, *proj;
3798 proj = isl_ast_build_get_schedule_map(build);
3799 proj = isl_map_reverse(proj);
3800 space = isl_space_map_from_set(isl_space_copy(space));
3801 id = isl_map_identity(space);
3802 proj = isl_map_product(proj, id);
3803 executed = isl_union_map_apply_domain(executed,
3804 isl_union_map_from_map(proj));
3805 return executed;
3808 /* Generate an AST that visits the elements in the range of data->executed
3809 * in the relative order specified by the corresponding domain element(s)
3810 * for those domain elements that belong to "set".
3811 * Add the result to data->list.
3813 * The caller ensures that "set" is a universe domain.
3814 * "space" is the space of the additional part of the schedule.
3815 * It is equal to the space of "set" if build->domain is parametric.
3816 * Otherwise, it is equal to the range of the wrapped space of "set".
3818 * If the build space is not parametric and if isl_ast_build_ast_from_schedule
3819 * was called from an outside user (data->internal not set), then
3820 * the (inverse) schedule refers to the external build domain and needs to
3821 * be transformed to refer to the internal build domain.
3823 * If the build space is parametric, then we add some of the parameter
3824 * constraints to the executed relation. Adding these constraints
3825 * allows for an earlier detection of conflicts in some cases.
3826 * However, we do not want to divide the executed relation into
3827 * more disjuncts than necessary. We therefore approximate
3828 * the constraints on the parameters by a single disjunct set.
3830 * The build is extended to include the additional part of the schedule.
3831 * If the original build space was not parametric, then the options
3832 * in data->build refer only to the additional part of the schedule
3833 * and they need to be adjusted to refer to the complete AST build
3834 * domain.
3836 * After having adjusted inverse schedule and build, we start generating
3837 * code with the outer loop of the current code generation
3838 * in generate_next_level.
3840 * If the original build space was not parametric, we undo the embedding
3841 * on the resulting isl_ast_node_list so that it can be used within
3842 * the outer AST build.
3844 static int generate_code_in_space(struct isl_generate_code_data *data,
3845 __isl_take isl_set *set, __isl_take isl_space *space)
3847 isl_union_map *executed;
3848 isl_ast_build *build;
3849 isl_ast_graft_list *list;
3850 int embed;
3852 executed = isl_union_map_copy(data->executed);
3853 executed = isl_union_map_intersect_domain(executed,
3854 isl_union_set_from_set(set));
3856 embed = !isl_set_is_params(data->build->domain);
3857 if (embed && !data->internal)
3858 executed = internal_executed(executed, space, data->build);
3859 if (!embed) {
3860 isl_set *domain;
3861 domain = isl_ast_build_get_domain(data->build);
3862 domain = isl_set_from_basic_set(isl_set_simple_hull(domain));
3863 executed = isl_union_map_intersect_params(executed, domain);
3866 build = isl_ast_build_copy(data->build);
3867 build = isl_ast_build_product(build, space);
3869 list = generate_next_level(executed, build);
3871 list = isl_ast_graft_list_unembed(list, embed);
3873 data->list = isl_ast_graft_list_concat(data->list, list);
3875 return 0;
3878 /* Generate an AST that visits the elements in the range of data->executed
3879 * in the relative order specified by the corresponding domain element(s)
3880 * for those domain elements that belong to "set".
3881 * Add the result to data->list.
3883 * The caller ensures that "set" is a universe domain.
3885 * If the build space S is not parametric, then the space of "set"
3886 * need to be a wrapped relation with S as domain. That is, it needs
3887 * to be of the form
3889 * [S -> T]
3891 * Check this property and pass control to generate_code_in_space
3892 * passing along T.
3893 * If the build space is not parametric, then T is the space of "set".
3895 static int generate_code_set(__isl_take isl_set *set, void *user)
3897 struct isl_generate_code_data *data = user;
3898 isl_space *space, *build_space;
3899 int is_domain;
3901 space = isl_set_get_space(set);
3903 if (isl_set_is_params(data->build->domain))
3904 return generate_code_in_space(data, set, space);
3906 build_space = isl_ast_build_get_space(data->build, data->internal);
3907 space = isl_space_unwrap(space);
3908 is_domain = isl_space_is_domain(build_space, space);
3909 isl_space_free(build_space);
3910 space = isl_space_range(space);
3912 if (is_domain < 0)
3913 goto error;
3914 if (!is_domain)
3915 isl_die(isl_set_get_ctx(set), isl_error_invalid,
3916 "invalid nested schedule space", goto error);
3918 return generate_code_in_space(data, set, space);
3919 error:
3920 isl_set_free(set);
3921 isl_space_free(space);
3922 return -1;
3925 /* Generate an AST that visits the elements in the range of "executed"
3926 * in the relative order specified by the corresponding domain element(s).
3928 * "build" is an isl_ast_build that has either been constructed by
3929 * isl_ast_build_from_context or passed to a callback set by
3930 * isl_ast_build_set_create_leaf.
3931 * In the first case, the space of the isl_ast_build is typically
3932 * a parametric space, although this is currently not enforced.
3933 * In the second case, the space is never a parametric space.
3934 * If the space S is not parametric, then the domain space(s) of "executed"
3935 * need to be wrapped relations with S as domain.
3937 * If the domain of "executed" consists of several spaces, then an AST
3938 * is generated for each of them (in arbitrary order) and the results
3939 * are concatenated.
3941 * If "internal" is set, then the domain "S" above refers to the internal
3942 * schedule domain representation. Otherwise, it refers to the external
3943 * representation, as returned by isl_ast_build_get_schedule_space.
3945 * We essentially run over all the spaces in the domain of "executed"
3946 * and call generate_code_set on each of them.
3948 static __isl_give isl_ast_graft_list *generate_code(
3949 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
3950 int internal)
3952 isl_ctx *ctx;
3953 struct isl_generate_code_data data = { 0 };
3954 isl_space *space;
3955 isl_union_set *schedule_domain;
3956 isl_union_map *universe;
3958 if (!build)
3959 goto error;
3960 space = isl_ast_build_get_space(build, 1);
3961 space = isl_space_align_params(space,
3962 isl_union_map_get_space(executed));
3963 space = isl_space_align_params(space,
3964 isl_union_map_get_space(build->options));
3965 build = isl_ast_build_align_params(build, isl_space_copy(space));
3966 executed = isl_union_map_align_params(executed, space);
3967 if (!executed || !build)
3968 goto error;
3970 ctx = isl_ast_build_get_ctx(build);
3972 data.internal = internal;
3973 data.executed = executed;
3974 data.build = build;
3975 data.list = isl_ast_graft_list_alloc(ctx, 0);
3977 universe = isl_union_map_universe(isl_union_map_copy(executed));
3978 schedule_domain = isl_union_map_domain(universe);
3979 if (isl_union_set_foreach_set(schedule_domain, &generate_code_set,
3980 &data) < 0)
3981 data.list = isl_ast_graft_list_free(data.list);
3983 isl_union_set_free(schedule_domain);
3984 isl_union_map_free(executed);
3986 isl_ast_build_free(build);
3987 return data.list;
3988 error:
3989 isl_union_map_free(executed);
3990 isl_ast_build_free(build);
3991 return NULL;
3994 /* Generate an AST that visits the elements in the domain of "schedule"
3995 * in the relative order specified by the corresponding image element(s).
3997 * "build" is an isl_ast_build that has either been constructed by
3998 * isl_ast_build_from_context or passed to a callback set by
3999 * isl_ast_build_set_create_leaf.
4000 * In the first case, the space of the isl_ast_build is typically
4001 * a parametric space, although this is currently not enforced.
4002 * In the second case, the space is never a parametric space.
4003 * If the space S is not parametric, then the range space(s) of "schedule"
4004 * need to be wrapped relations with S as domain.
4006 * If the range of "schedule" consists of several spaces, then an AST
4007 * is generated for each of them (in arbitrary order) and the results
4008 * are concatenated.
4010 * We first initialize the local copies of the relevant options.
4011 * We do this here rather than when the isl_ast_build is created
4012 * because the options may have changed between the construction
4013 * of the isl_ast_build and the call to isl_generate_code.
4015 * The main computation is performed on an inverse schedule (with
4016 * the schedule domain in the domain and the elements to be executed
4017 * in the range) called "executed".
4019 __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
4020 __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
4022 isl_ast_graft_list *list;
4023 isl_ast_node *node;
4024 isl_union_map *executed;
4026 build = isl_ast_build_copy(build);
4027 build = isl_ast_build_set_single_valued(build, 0);
4028 schedule = isl_union_map_coalesce(schedule);
4029 schedule = isl_union_map_remove_redundancies(schedule);
4030 executed = isl_union_map_reverse(schedule);
4031 list = generate_code(executed, isl_ast_build_copy(build), 0);
4032 node = isl_ast_node_from_graft_list(list, build);
4033 isl_ast_build_free(build);
4035 return node;