add isl_union_map_factor_range
[isl.git] / isl_ast_codegen.c
blob679d2612d698400242e1cacf4b5a53ab0f4c6d91
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.
669 static __isl_give isl_set *add_implied_guards(__isl_take isl_set *guard,
670 int degenerate, __isl_keep isl_basic_set *bounds,
671 __isl_keep isl_ast_build *build)
673 int depth, has_stride;
674 isl_set *dom;
676 depth = isl_ast_build_get_depth(build);
677 has_stride = isl_ast_build_has_stride(build, depth);
678 if (!has_stride && !degenerate)
679 return guard;
681 if (degenerate) {
682 bounds = isl_basic_set_copy(bounds);
683 bounds = isl_basic_set_drop_constraints_not_involving_dims(
684 bounds, isl_dim_set, depth, 1);
685 dom = isl_set_from_basic_set(bounds);
686 dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
687 dom = isl_ast_build_compute_gist(build, dom);
688 guard = isl_set_intersect(guard, dom);
691 if (has_stride) {
692 dom = isl_ast_build_get_stride_constraint(build);
693 dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
694 dom = isl_ast_build_compute_gist(build, dom);
695 guard = isl_set_intersect(guard, dom);
698 return guard;
701 /* Update "graft" based on "sub_build" for the degenerate case.
703 * "build" is the build in which graft->node was created
704 * "sub_build" contains information about the current level itself,
705 * including the single value attained.
707 * We set the initialization part of the for loop to the single
708 * value attained by the current dimension.
709 * The increment and condition are not strictly needed as the are known
710 * to be "1" and "iterator <= value" respectively.
712 static __isl_give isl_ast_graft *refine_degenerate(
713 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build,
714 __isl_keep isl_ast_build *sub_build)
716 isl_pw_aff *value;
718 if (!graft || !sub_build)
719 return isl_ast_graft_free(graft);
721 value = isl_pw_aff_copy(sub_build->value);
723 graft->node->u.f.init = isl_ast_build_expr_from_pw_aff_internal(build,
724 value);
725 if (!graft->node->u.f.init)
726 return isl_ast_graft_free(graft);
728 return graft;
731 /* Return the intersection of constraints in "list" as a set.
733 static __isl_give isl_set *intersect_constraints(
734 __isl_keep isl_constraint_list *list)
736 int i, n;
737 isl_basic_set *bset;
739 n = isl_constraint_list_n_constraint(list);
740 if (n < 1)
741 isl_die(isl_constraint_list_get_ctx(list), isl_error_internal,
742 "expecting at least one constraint", return NULL);
744 bset = isl_basic_set_from_constraint(
745 isl_constraint_list_get_constraint(list, 0));
746 for (i = 1; i < n; ++i) {
747 isl_basic_set *bset_i;
749 bset_i = isl_basic_set_from_constraint(
750 isl_constraint_list_get_constraint(list, i));
751 bset = isl_basic_set_intersect(bset, bset_i);
754 return isl_set_from_basic_set(bset);
757 /* Compute the constraints on the outer dimensions enforced by
758 * graft->node and add those constraints to graft->enforced,
759 * in case the upper bound is expressed as a set "upper".
761 * In particular, if l(...) is a lower bound in "lower", and
763 * -a i + f(...) >= 0 or a i <= f(...)
765 * is an upper bound ocnstraint on the current dimension i,
766 * then the for loop enforces the constraint
768 * -a l(...) + f(...) >= 0 or a l(...) <= f(...)
770 * We therefore simply take each lower bound in turn, plug it into
771 * the upper bounds and compute the intersection over all lower bounds.
773 * If a lower bound is a rational expression, then
774 * isl_basic_set_preimage_multi_aff will force this rational
775 * expression to have only integer values. However, the loop
776 * itself does not enforce this integrality constraint. We therefore
777 * use the ceil of the lower bounds instead of the lower bounds themselves.
778 * Other constraints will make sure that the for loop is only executed
779 * when each of the lower bounds attains an integral value.
780 * In particular, potentially rational values only occur in
781 * lower_bound if the offset is a (seemingly) rational expression,
782 * but then outer conditions will make sure that this rational expression
783 * only attains integer values.
785 static __isl_give isl_ast_graft *set_enforced_from_set(
786 __isl_take isl_ast_graft *graft,
787 __isl_keep isl_pw_aff_list *lower, int pos, __isl_keep isl_set *upper)
789 isl_space *space;
790 isl_basic_set *enforced;
791 isl_pw_multi_aff *pma;
792 int i, n;
794 if (!graft || !lower)
795 return isl_ast_graft_free(graft);
797 space = isl_set_get_space(upper);
798 enforced = isl_basic_set_universe(isl_space_copy(space));
800 space = isl_space_map_from_set(space);
801 pma = isl_pw_multi_aff_identity(space);
803 n = isl_pw_aff_list_n_pw_aff(lower);
804 for (i = 0; i < n; ++i) {
805 isl_pw_aff *pa;
806 isl_set *enforced_i;
807 isl_basic_set *hull;
808 isl_pw_multi_aff *pma_i;
810 pa = isl_pw_aff_list_get_pw_aff(lower, i);
811 pa = isl_pw_aff_ceil(pa);
812 pma_i = isl_pw_multi_aff_copy(pma);
813 pma_i = isl_pw_multi_aff_set_pw_aff(pma_i, pos, pa);
814 enforced_i = isl_set_copy(upper);
815 enforced_i = isl_set_preimage_pw_multi_aff(enforced_i, pma_i);
816 hull = isl_set_simple_hull(enforced_i);
817 enforced = isl_basic_set_intersect(enforced, hull);
820 isl_pw_multi_aff_free(pma);
822 graft = isl_ast_graft_enforce(graft, enforced);
824 return graft;
827 /* Compute the constraints on the outer dimensions enforced by
828 * graft->node and add those constraints to graft->enforced,
829 * in case the upper bound is expressed as
830 * a list of affine expressions "upper".
832 * The enforced condition is that each lower bound expression is less
833 * than or equal to each upper bound expression.
835 static __isl_give isl_ast_graft *set_enforced_from_list(
836 __isl_take isl_ast_graft *graft,
837 __isl_keep isl_pw_aff_list *lower, __isl_keep isl_pw_aff_list *upper)
839 isl_set *cond;
840 isl_basic_set *enforced;
842 lower = isl_pw_aff_list_copy(lower);
843 upper = isl_pw_aff_list_copy(upper);
844 cond = isl_pw_aff_list_le_set(lower, upper);
845 enforced = isl_set_simple_hull(cond);
846 graft = isl_ast_graft_enforce(graft, enforced);
848 return graft;
851 /* Does "aff" have a negative constant term?
853 static int aff_constant_is_negative(__isl_take isl_set *set,
854 __isl_take isl_aff *aff, void *user)
856 int *neg = user;
857 isl_val *v;
859 v = isl_aff_get_constant_val(aff);
860 *neg = isl_val_is_neg(v);
861 isl_val_free(v);
862 isl_set_free(set);
863 isl_aff_free(aff);
865 return *neg ? 0 : -1;
868 /* Does "pa" have a negative constant term over its entire domain?
870 static int pw_aff_constant_is_negative(__isl_take isl_pw_aff *pa, void *user)
872 int r;
873 int *neg = user;
875 r = isl_pw_aff_foreach_piece(pa, &aff_constant_is_negative, user);
876 isl_pw_aff_free(pa);
878 return *neg ? 0 : -1;
881 /* Does each element in "list" have a negative constant term?
883 * The callback terminates the iteration as soon an element has been
884 * found that does not have a negative constant term.
886 static int list_constant_is_negative(__isl_keep isl_pw_aff_list *list)
888 int neg = 1;
890 if (isl_pw_aff_list_foreach(list,
891 &pw_aff_constant_is_negative, &neg) < 0 && neg)
892 return -1;
894 return neg;
897 /* Add 1 to each of the elements in "list", where each of these elements
898 * is defined over the internal schedule space of "build".
900 static __isl_give isl_pw_aff_list *list_add_one(
901 __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
903 int i, n;
904 isl_space *space;
905 isl_aff *aff;
906 isl_pw_aff *one;
908 space = isl_ast_build_get_space(build, 1);
909 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
910 aff = isl_aff_add_constant_si(aff, 1);
911 one = isl_pw_aff_from_aff(aff);
913 n = isl_pw_aff_list_n_pw_aff(list);
914 for (i = 0; i < n; ++i) {
915 isl_pw_aff *pa;
916 pa = isl_pw_aff_list_get_pw_aff(list, i);
917 pa = isl_pw_aff_add(pa, isl_pw_aff_copy(one));
918 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
921 isl_pw_aff_free(one);
923 return list;
926 /* Set the condition part of the for node graft->node in case
927 * the upper bound is represented as a list of piecewise affine expressions.
929 * In particular, set the condition to
931 * iterator <= min(list of upper bounds)
933 * If each of the upper bounds has a negative constant term, then
934 * set the condition to
936 * iterator < min(list of (upper bound + 1)s)
939 static __isl_give isl_ast_graft *set_for_cond_from_list(
940 __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *list,
941 __isl_keep isl_ast_build *build)
943 int neg;
944 isl_ast_expr *bound, *iterator, *cond;
945 enum isl_ast_op_type type = isl_ast_op_le;
947 if (!graft || !list)
948 return isl_ast_graft_free(graft);
950 neg = list_constant_is_negative(list);
951 if (neg < 0)
952 return isl_ast_graft_free(graft);
953 list = isl_pw_aff_list_copy(list);
954 if (neg) {
955 list = list_add_one(list, build);
956 type = isl_ast_op_lt;
959 bound = reduce_list(isl_ast_op_min, list, build);
960 iterator = isl_ast_expr_copy(graft->node->u.f.iterator);
961 cond = isl_ast_expr_alloc_binary(type, iterator, bound);
962 graft->node->u.f.cond = cond;
964 isl_pw_aff_list_free(list);
965 if (!graft->node->u.f.cond)
966 return isl_ast_graft_free(graft);
967 return graft;
970 /* Set the condition part of the for node graft->node in case
971 * the upper bound is represented as a set.
973 static __isl_give isl_ast_graft *set_for_cond_from_set(
974 __isl_take isl_ast_graft *graft, __isl_keep isl_set *set,
975 __isl_keep isl_ast_build *build)
977 isl_ast_expr *cond;
979 if (!graft)
980 return NULL;
982 cond = isl_ast_build_expr_from_set(build, isl_set_copy(set));
983 graft->node->u.f.cond = cond;
984 if (!graft->node->u.f.cond)
985 return isl_ast_graft_free(graft);
986 return graft;
989 /* Construct an isl_ast_expr for the increment (i.e., stride) of
990 * the current dimension.
992 static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
994 int depth;
995 isl_val *v;
996 isl_ctx *ctx;
998 if (!build)
999 return NULL;
1000 ctx = isl_ast_build_get_ctx(build);
1001 depth = isl_ast_build_get_depth(build);
1003 if (!isl_ast_build_has_stride(build, depth))
1004 return isl_ast_expr_alloc_int_si(ctx, 1);
1006 v = isl_ast_build_get_stride(build, depth);
1007 return isl_ast_expr_from_val(v);
1010 /* Should we express the loop condition as
1012 * iterator <= min(list of upper bounds)
1014 * or as a conjunction of constraints?
1016 * The first is constructed from a list of upper bounds.
1017 * The second is constructed from a set.
1019 * If there are no upper bounds in "constraints", then this could mean
1020 * that "domain" simply doesn't have an upper bound or that we didn't
1021 * pick any upper bound. In the first case, we want to generate the
1022 * loop condition as a(n empty) conjunction of constraints
1023 * In the second case, we will compute
1024 * a single upper bound from "domain" and so we use the list form.
1026 * If there are upper bounds in "constraints",
1027 * then we use the list form iff the atomic_upper_bound option is set.
1029 static int use_upper_bound_list(isl_ctx *ctx, int n_upper,
1030 __isl_keep isl_set *domain, int depth)
1032 if (n_upper > 0)
1033 return isl_options_get_ast_build_atomic_upper_bound(ctx);
1034 else
1035 return isl_set_dim_has_upper_bound(domain, isl_dim_set, depth);
1038 /* Fill in the expressions of the for node in graft->node.
1040 * In particular,
1041 * - set the initialization part of the loop to the maximum of the lower bounds
1042 * - extract the increment from the stride of the current dimension
1043 * - construct the for condition either based on a list of upper bounds
1044 * or on a set of upper bound constraints.
1046 static __isl_give isl_ast_graft *set_for_node_expressions(
1047 __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *lower,
1048 int use_list, __isl_keep isl_pw_aff_list *upper_list,
1049 __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build)
1051 isl_ast_node *node;
1053 if (!graft)
1054 return NULL;
1056 build = isl_ast_build_copy(build);
1058 node = graft->node;
1059 node->u.f.init = reduce_list(isl_ast_op_max, lower, build);
1060 node->u.f.inc = for_inc(build);
1062 if (use_list)
1063 graft = set_for_cond_from_list(graft, upper_list, build);
1064 else
1065 graft = set_for_cond_from_set(graft, upper_set, build);
1067 isl_ast_build_free(build);
1069 if (!node->u.f.iterator || !node->u.f.init ||
1070 !node->u.f.cond || !node->u.f.inc)
1071 return isl_ast_graft_free(graft);
1073 return graft;
1076 /* Update "graft" based on "bounds" and "domain" for the generic,
1077 * non-degenerate, case.
1079 * "c_lower" and "c_upper" contain the lower and upper bounds
1080 * that the loop node should express.
1081 * "domain" is the subset of the intersection of the constraints
1082 * for which some code is executed.
1084 * There may be zero lower bounds or zero upper bounds in "constraints"
1085 * in case the list of constraints was created
1086 * based on the atomic option or based on separation with explicit bounds.
1087 * In that case, we use "domain" to derive lower and/or upper bounds.
1089 * We first compute a list of one or more lower bounds.
1091 * Then we decide if we want to express the condition as
1093 * iterator <= min(list of upper bounds)
1095 * or as a conjunction of constraints.
1097 * The set of enforced constraints is then computed either based on
1098 * a list of upper bounds or on a set of upper bound constraints.
1099 * We do not compute any enforced constraints if we were forced
1100 * to compute a lower or upper bound using exact_bound. The domains
1101 * of the resulting expressions may imply some bounds on outer dimensions
1102 * that we do not want to appear in the enforced constraints since
1103 * they are not actually enforced by the corresponding code.
1105 * Finally, we fill in the expressions of the for node.
1107 static __isl_give isl_ast_graft *refine_generic_bounds(
1108 __isl_take isl_ast_graft *graft,
1109 __isl_take isl_constraint_list *c_lower,
1110 __isl_take isl_constraint_list *c_upper,
1111 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1113 int depth;
1114 isl_ctx *ctx;
1115 isl_pw_aff_list *lower;
1116 int use_list;
1117 isl_set *upper_set = NULL;
1118 isl_pw_aff_list *upper_list = NULL;
1119 int n_lower, n_upper;
1121 if (!graft || !c_lower || !c_upper || !build)
1122 goto error;
1124 depth = isl_ast_build_get_depth(build);
1125 ctx = isl_ast_graft_get_ctx(graft);
1127 n_lower = isl_constraint_list_n_constraint(c_lower);
1128 n_upper = isl_constraint_list_n_constraint(c_upper);
1130 use_list = use_upper_bound_list(ctx, n_upper, domain, depth);
1132 lower = lower_bounds(c_lower, depth, domain, build);
1134 if (use_list)
1135 upper_list = upper_bounds(c_upper, depth, domain, build);
1136 else if (n_upper > 0)
1137 upper_set = intersect_constraints(c_upper);
1138 else
1139 upper_set = isl_set_universe(isl_set_get_space(domain));
1141 if (n_lower == 0 || n_upper == 0)
1143 else if (use_list)
1144 graft = set_enforced_from_list(graft, lower, upper_list);
1145 else
1146 graft = set_enforced_from_set(graft, lower, depth, upper_set);
1148 graft = set_for_node_expressions(graft, lower, use_list, upper_list,
1149 upper_set, build);
1151 isl_pw_aff_list_free(lower);
1152 isl_pw_aff_list_free(upper_list);
1153 isl_set_free(upper_set);
1154 isl_constraint_list_free(c_lower);
1155 isl_constraint_list_free(c_upper);
1157 return graft;
1158 error:
1159 isl_constraint_list_free(c_lower);
1160 isl_constraint_list_free(c_upper);
1161 return isl_ast_graft_free(graft);
1164 /* Internal data structure used inside count_constraints to keep
1165 * track of the number of constraints that are independent of dimension "pos",
1166 * the lower bounds in "pos" and the upper bounds in "pos".
1168 struct isl_ast_count_constraints_data {
1169 int pos;
1171 int n_indep;
1172 int n_lower;
1173 int n_upper;
1176 /* Increment data->n_indep, data->lower or data->upper depending
1177 * on whether "c" is independenct of dimensions data->pos,
1178 * a lower bound or an upper bound.
1180 static int count_constraints(__isl_take isl_constraint *c, void *user)
1182 struct isl_ast_count_constraints_data *data = user;
1184 if (isl_constraint_is_lower_bound(c, isl_dim_set, data->pos))
1185 data->n_lower++;
1186 else if (isl_constraint_is_upper_bound(c, isl_dim_set, data->pos))
1187 data->n_upper++;
1188 else
1189 data->n_indep++;
1191 isl_constraint_free(c);
1193 return 0;
1196 /* Update "graft" based on "bounds" and "domain" for the generic,
1197 * non-degenerate, case.
1199 * "list" respresent the list of bounds that need to be encoded by
1200 * the for loop. Only the constraints that involve the iterator
1201 * are relevant here. The other constraints are taken care of by
1202 * the caller and are included in the generated constraints of "build".
1203 * "domain" is the subset of the intersection of the constraints
1204 * for which some code is executed.
1205 * "build" is the build in which graft->node was created.
1207 * We separate lower bounds, upper bounds and constraints that
1208 * are independent of the loop iterator.
1210 * The actual for loop bounds are generated in refine_generic_bounds.
1212 static __isl_give isl_ast_graft *refine_generic_split(
1213 __isl_take isl_ast_graft *graft, __isl_take isl_constraint_list *list,
1214 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1216 struct isl_ast_count_constraints_data data;
1217 isl_constraint_list *lower;
1218 isl_constraint_list *upper;
1220 if (!list)
1221 return isl_ast_graft_free(graft);
1223 data.pos = isl_ast_build_get_depth(build);
1225 list = isl_constraint_list_sort(list, &cmp_constraint, &data.pos);
1226 if (!list)
1227 return isl_ast_graft_free(graft);
1229 data.n_indep = data.n_lower = data.n_upper = 0;
1230 if (isl_constraint_list_foreach(list, &count_constraints, &data) < 0) {
1231 isl_constraint_list_free(list);
1232 return isl_ast_graft_free(graft);
1235 lower = isl_constraint_list_drop(list, 0, data.n_indep);
1236 upper = isl_constraint_list_copy(lower);
1237 lower = isl_constraint_list_drop(lower, data.n_lower, data.n_upper);
1238 upper = isl_constraint_list_drop(upper, 0, data.n_lower);
1240 return refine_generic_bounds(graft, lower, upper, domain, build);
1243 /* Update "graft" based on "bounds" and "domain" for the generic,
1244 * non-degenerate, case.
1246 * "bounds" respresent the bounds that need to be encoded by
1247 * the for loop (or a guard around the for loop).
1248 * "domain" is the subset of "bounds" for which some code is executed.
1249 * "build" is the build in which graft->node was created.
1251 * We break up "bounds" into a list of constraints and continue with
1252 * refine_generic_split.
1254 static __isl_give isl_ast_graft *refine_generic(
1255 __isl_take isl_ast_graft *graft,
1256 __isl_keep isl_basic_set *bounds, __isl_keep isl_set *domain,
1257 __isl_keep isl_ast_build *build)
1259 isl_constraint_list *list;
1261 if (!build || !graft)
1262 return isl_ast_graft_free(graft);
1264 list = isl_basic_set_get_constraint_list(bounds);
1266 graft = refine_generic_split(graft, list, domain, build);
1268 return graft;
1271 /* Create a for node for the current level.
1273 * Mark the for node degenerate if "degenerate" is set.
1275 static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build,
1276 int degenerate)
1278 int depth;
1279 isl_id *id;
1280 isl_ast_node *node;
1282 if (!build)
1283 return NULL;
1285 depth = isl_ast_build_get_depth(build);
1286 id = isl_ast_build_get_iterator_id(build, depth);
1287 node = isl_ast_node_alloc_for(id);
1288 if (degenerate)
1289 node = isl_ast_node_for_mark_degenerate(node);
1291 return node;
1294 /* If the ast_build_exploit_nested_bounds option is set, then return
1295 * the constraints enforced by all elements in "list".
1296 * Otherwise, return the universe.
1298 static __isl_give isl_basic_set *extract_shared_enforced(
1299 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
1301 isl_ctx *ctx;
1302 isl_space *space;
1304 if (!list)
1305 return NULL;
1307 ctx = isl_ast_graft_list_get_ctx(list);
1308 if (isl_options_get_ast_build_exploit_nested_bounds(ctx))
1309 return isl_ast_graft_list_extract_shared_enforced(list, build);
1311 space = isl_ast_build_get_space(build, 1);
1312 return isl_basic_set_universe(space);
1315 /* Return the pending constraints of "build" that are not already taken
1316 * care of (by a combination of "enforced" and the generated constraints
1317 * of "build").
1319 static __isl_give isl_set *extract_pending(__isl_keep isl_ast_build *build,
1320 __isl_keep isl_basic_set *enforced)
1322 isl_set *guard, *context;
1324 guard = isl_ast_build_get_pending(build);
1325 context = isl_set_from_basic_set(isl_basic_set_copy(enforced));
1326 context = isl_set_intersect(context,
1327 isl_ast_build_get_generated(build));
1328 return isl_set_gist(guard, context);
1331 /* Create an AST node for the current dimension based on
1332 * the schedule domain "bounds" and return the node encapsulated
1333 * in an isl_ast_graft.
1335 * "executed" is the current inverse schedule, taking into account
1336 * the bounds in "bounds"
1337 * "domain" is the domain of "executed", with inner dimensions projected out.
1338 * It may be a strict subset of "bounds" in case "bounds" was created
1339 * based on the atomic option or based on separation with explicit bounds.
1341 * "domain" may satisfy additional equalities that result
1342 * from intersecting "executed" with "bounds" in add_node.
1343 * It may also satisfy some global constraints that were dropped out because
1344 * we performed separation with explicit bounds.
1345 * The very first step is then to copy these constraints to "bounds".
1347 * Since we may be calling before_each_for and after_each_for
1348 * callbacks, we record the current inverse schedule in the build.
1350 * We consider three builds,
1351 * "build" is the one in which the current level is created,
1352 * "body_build" is the build in which the next level is created,
1353 * "sub_build" is essentially the same as "body_build", except that
1354 * the depth has not been increased yet.
1356 * "build" already contains information (in strides and offsets)
1357 * about the strides at the current level, but this information is not
1358 * reflected in the build->domain.
1359 * We first add this information and the "bounds" to the sub_build->domain.
1360 * isl_ast_build_set_loop_bounds adds the stride information and
1361 * checks whether the current dimension attains
1362 * only a single value and whether this single value can be represented using
1363 * a single affine expression.
1364 * In the first case, the current level is considered "degenerate".
1365 * In the second, sub-case, the current level is considered "eliminated".
1366 * Eliminated levels don't need to be reflected in the AST since we can
1367 * simply plug in the affine expression. For degenerate, but non-eliminated,
1368 * levels, we do introduce a for node, but mark is as degenerate so that
1369 * it can be printed as an assignment of the single value to the loop
1370 * "iterator".
1372 * If the current level is eliminated, we explicitly plug in the value
1373 * for the current level found by isl_ast_build_set_loop_bounds in the
1374 * inverse schedule. This ensures that if we are working on a slice
1375 * of the domain based on information available in the inverse schedule
1376 * and the build domain, that then this information is also reflected
1377 * in the inverse schedule. This operation also eliminates the current
1378 * dimension from the inverse schedule making sure no inner dimensions depend
1379 * on the current dimension. Otherwise, we create a for node, marking
1380 * it degenerate if appropriate. The initial for node is still incomplete
1381 * and will be completed in either refine_degenerate or refine_generic.
1383 * We then generate a sequence of grafts for the next level,
1384 * create a surrounding graft for the current level and insert
1385 * the for node we created (if the current level is not eliminated).
1386 * Before creating a graft for the current level, we first extract
1387 * hoistable constraints from the child guards and combine them
1388 * with the pending constraints in the build. These constraints
1389 * are used to simplify the child guards and then added to the guard
1390 * of the current graft to ensure that they will be generated.
1391 * If the hoisted guard is a disjunction, then we use it directly
1392 * to gist the guards on the children before intersect it with the
1393 * pending constraints. We do so because this disjunction is typically
1394 * identical to the guards on the children such that these guards
1395 * can be effectively removed completely. After the intersection,
1396 * the gist operation would have a harder time figuring this out.
1398 * Finally, we set the bounds of the for loop in either
1399 * refine_degenerate or refine_generic.
1400 * We do so in a context where the pending constraints of the build
1401 * have been replaced by the guard of the current graft.
1403 static __isl_give isl_ast_graft *create_node_scaled(
1404 __isl_take isl_union_map *executed,
1405 __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1406 __isl_take isl_ast_build *build)
1408 int depth;
1409 int degenerate, eliminated;
1410 isl_basic_set *hull;
1411 isl_basic_set *enforced;
1412 isl_set *guard, *hoisted;
1413 isl_ast_node *node = NULL;
1414 isl_ast_graft *graft;
1415 isl_ast_graft_list *children;
1416 isl_ast_build *sub_build;
1417 isl_ast_build *body_build;
1419 domain = isl_ast_build_eliminate_divs(build, domain);
1420 domain = isl_set_detect_equalities(domain);
1421 hull = isl_set_unshifted_simple_hull(isl_set_copy(domain));
1422 bounds = isl_basic_set_intersect(bounds, hull);
1423 build = isl_ast_build_set_executed(build, isl_union_map_copy(executed));
1425 depth = isl_ast_build_get_depth(build);
1426 sub_build = isl_ast_build_copy(build);
1427 sub_build = isl_ast_build_set_loop_bounds(sub_build,
1428 isl_basic_set_copy(bounds));
1429 degenerate = isl_ast_build_has_value(sub_build);
1430 eliminated = isl_ast_build_has_affine_value(sub_build, depth);
1431 if (degenerate < 0 || eliminated < 0)
1432 executed = isl_union_map_free(executed);
1433 if (eliminated)
1434 executed = plug_in_values(executed, sub_build);
1435 else
1436 node = create_for(build, degenerate);
1438 body_build = isl_ast_build_copy(sub_build);
1439 body_build = isl_ast_build_increase_depth(body_build);
1440 if (!eliminated)
1441 node = before_each_for(node, body_build);
1442 children = generate_next_level(executed,
1443 isl_ast_build_copy(body_build));
1445 enforced = extract_shared_enforced(children, build);
1446 guard = extract_pending(sub_build, enforced);
1447 hoisted = isl_ast_graft_list_extract_hoistable_guard(children, build);
1448 if (isl_set_n_basic_set(hoisted) > 1)
1449 children = isl_ast_graft_list_gist_guards(children,
1450 isl_set_copy(hoisted));
1451 guard = isl_set_intersect(guard, hoisted);
1452 if (!eliminated)
1453 guard = add_implied_guards(guard, degenerate, bounds, build);
1455 graft = isl_ast_graft_alloc_from_children(children,
1456 isl_set_copy(guard), enforced, build, sub_build);
1458 if (!degenerate)
1459 bounds = isl_ast_build_compute_gist_basic_set(build, bounds);
1460 if (!eliminated) {
1461 isl_ast_build *for_build;
1463 graft = isl_ast_graft_insert_for(graft, node);
1464 for_build = isl_ast_build_copy(build);
1465 for_build = isl_ast_build_replace_pending_by_guard(for_build,
1466 isl_set_copy(guard));
1467 if (degenerate)
1468 graft = refine_degenerate(graft, for_build, sub_build);
1469 else
1470 graft = refine_generic(graft, bounds,
1471 domain, for_build);
1472 isl_ast_build_free(for_build);
1474 isl_set_free(guard);
1475 if (!eliminated)
1476 graft = after_each_for(graft, body_build);
1478 isl_ast_build_free(body_build);
1479 isl_ast_build_free(sub_build);
1480 isl_ast_build_free(build);
1481 isl_basic_set_free(bounds);
1482 isl_set_free(domain);
1484 return graft;
1487 /* Internal data structure for checking if all constraints involving
1488 * the input dimension "depth" are such that the other coefficients
1489 * are multiples of "m", reducing "m" if they are not.
1490 * If "m" is reduced all the way down to "1", then the check has failed
1491 * and we break out of the iteration.
1493 struct isl_check_scaled_data {
1494 int depth;
1495 isl_val *m;
1498 /* If constraint "c" involves the input dimension data->depth,
1499 * then make sure that all the other coefficients are multiples of data->m,
1500 * reducing data->m if needed.
1501 * Break out of the iteration if data->m has become equal to "1".
1503 static int constraint_check_scaled(__isl_take isl_constraint *c, void *user)
1505 struct isl_check_scaled_data *data = user;
1506 int i, j, n;
1507 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_out,
1508 isl_dim_div };
1510 if (!isl_constraint_involves_dims(c, isl_dim_in, data->depth, 1)) {
1511 isl_constraint_free(c);
1512 return 0;
1515 for (i = 0; i < 4; ++i) {
1516 n = isl_constraint_dim(c, t[i]);
1517 for (j = 0; j < n; ++j) {
1518 isl_val *d;
1520 if (t[i] == isl_dim_in && j == data->depth)
1521 continue;
1522 if (!isl_constraint_involves_dims(c, t[i], j, 1))
1523 continue;
1524 d = isl_constraint_get_coefficient_val(c, t[i], j);
1525 data->m = isl_val_gcd(data->m, d);
1526 if (isl_val_is_one(data->m))
1527 break;
1529 if (j < n)
1530 break;
1533 isl_constraint_free(c);
1535 return i < 4 ? -1 : 0;
1538 /* For each constraint of "bmap" that involves the input dimension data->depth,
1539 * make sure that all the other coefficients are multiples of data->m,
1540 * reducing data->m if needed.
1541 * Break out of the iteration if data->m has become equal to "1".
1543 static int basic_map_check_scaled(__isl_take isl_basic_map *bmap, void *user)
1545 int r;
1547 r = isl_basic_map_foreach_constraint(bmap,
1548 &constraint_check_scaled, user);
1549 isl_basic_map_free(bmap);
1551 return r;
1554 /* For each constraint of "map" that involves the input dimension data->depth,
1555 * make sure that all the other coefficients are multiples of data->m,
1556 * reducing data->m if needed.
1557 * Break out of the iteration if data->m has become equal to "1".
1559 static int map_check_scaled(__isl_take isl_map *map, void *user)
1561 int r;
1563 r = isl_map_foreach_basic_map(map, &basic_map_check_scaled, user);
1564 isl_map_free(map);
1566 return r;
1569 /* Create an AST node for the current dimension based on
1570 * the schedule domain "bounds" and return the node encapsulated
1571 * in an isl_ast_graft.
1573 * "executed" is the current inverse schedule, taking into account
1574 * the bounds in "bounds"
1575 * "domain" is the domain of "executed", with inner dimensions projected out.
1578 * Before moving on to the actual AST node construction in create_node_scaled,
1579 * we first check if the current dimension is strided and if we can scale
1580 * down this stride. Note that we only do this if the ast_build_scale_strides
1581 * option is set.
1583 * In particular, let the current dimension take on values
1585 * f + s a
1587 * with a an integer. We check if we can find an integer m that (obviously)
1588 * divides both f and s.
1590 * If so, we check if the current dimension only appears in constraints
1591 * where the coefficients of the other variables are multiples of m.
1592 * We perform this extra check to avoid the risk of introducing
1593 * divisions by scaling down the current dimension.
1595 * If so, we scale the current dimension down by a factor of m.
1596 * That is, we plug in
1598 * i = m i' (1)
1600 * Note that in principle we could always scale down strided loops
1601 * by plugging in
1603 * i = f + s i'
1605 * but this may result in i' taking on larger values than the original i,
1606 * due to the shift by "f".
1607 * By constrast, the scaling in (1) can only reduce the (absolute) value "i".
1609 static __isl_give isl_ast_graft *create_node(__isl_take isl_union_map *executed,
1610 __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1611 __isl_take isl_ast_build *build)
1613 struct isl_check_scaled_data data;
1614 isl_ctx *ctx;
1615 isl_aff *offset;
1616 isl_val *d;
1618 ctx = isl_ast_build_get_ctx(build);
1619 if (!isl_options_get_ast_build_scale_strides(ctx))
1620 return create_node_scaled(executed, bounds, domain, build);
1622 data.depth = isl_ast_build_get_depth(build);
1623 if (!isl_ast_build_has_stride(build, data.depth))
1624 return create_node_scaled(executed, bounds, domain, build);
1626 offset = isl_ast_build_get_offset(build, data.depth);
1627 data.m = isl_ast_build_get_stride(build, data.depth);
1628 if (!data.m)
1629 offset = isl_aff_free(offset);
1630 offset = isl_aff_scale_down_val(offset, isl_val_copy(data.m));
1631 d = isl_aff_get_denominator_val(offset);
1632 if (!d)
1633 executed = isl_union_map_free(executed);
1635 if (executed && isl_val_is_divisible_by(data.m, d))
1636 data.m = isl_val_div(data.m, d);
1637 else {
1638 data.m = isl_val_set_si(data.m, 1);
1639 isl_val_free(d);
1642 if (!isl_val_is_one(data.m)) {
1643 if (isl_union_map_foreach_map(executed, &map_check_scaled,
1644 &data) < 0 &&
1645 !isl_val_is_one(data.m))
1646 executed = isl_union_map_free(executed);
1649 if (!isl_val_is_one(data.m)) {
1650 isl_space *space;
1651 isl_multi_aff *ma;
1652 isl_aff *aff;
1653 isl_map *map;
1654 isl_union_map *umap;
1656 space = isl_ast_build_get_space(build, 1);
1657 space = isl_space_map_from_set(space);
1658 ma = isl_multi_aff_identity(space);
1659 aff = isl_multi_aff_get_aff(ma, data.depth);
1660 aff = isl_aff_scale_val(aff, isl_val_copy(data.m));
1661 ma = isl_multi_aff_set_aff(ma, data.depth, aff);
1663 bounds = isl_basic_set_preimage_multi_aff(bounds,
1664 isl_multi_aff_copy(ma));
1665 domain = isl_set_preimage_multi_aff(domain,
1666 isl_multi_aff_copy(ma));
1667 map = isl_map_reverse(isl_map_from_multi_aff(ma));
1668 umap = isl_union_map_from_map(map);
1669 executed = isl_union_map_apply_domain(executed,
1670 isl_union_map_copy(umap));
1671 build = isl_ast_build_scale_down(build, isl_val_copy(data.m),
1672 umap);
1674 isl_aff_free(offset);
1675 isl_val_free(data.m);
1677 return create_node_scaled(executed, bounds, domain, build);
1680 /* Add the basic set to the list that "user" points to.
1682 static int collect_basic_set(__isl_take isl_basic_set *bset, void *user)
1684 isl_basic_set_list **list = user;
1686 *list = isl_basic_set_list_add(*list, bset);
1688 return 0;
1691 /* Extract the basic sets of "set" and collect them in an isl_basic_set_list.
1693 static __isl_give isl_basic_set_list *isl_basic_set_list_from_set(
1694 __isl_take isl_set *set)
1696 int n;
1697 isl_ctx *ctx;
1698 isl_basic_set_list *list;
1700 if (!set)
1701 return NULL;
1703 ctx = isl_set_get_ctx(set);
1705 n = isl_set_n_basic_set(set);
1706 list = isl_basic_set_list_alloc(ctx, n);
1707 if (isl_set_foreach_basic_set(set, &collect_basic_set, &list) < 0)
1708 list = isl_basic_set_list_free(list);
1710 isl_set_free(set);
1711 return list;
1714 /* Generate code for the schedule domain "bounds"
1715 * and add the result to "list".
1717 * We mainly detect strides here and check if the bounds do not
1718 * conflict with the current build domain
1719 * and then pass over control to create_node.
1721 * "bounds" reflects the bounds on the current dimension and possibly
1722 * some extra conditions on outer dimensions.
1723 * It does not, however, include any divs involving the current dimension,
1724 * so it does not capture any stride constraints.
1725 * We therefore need to compute that part of the schedule domain that
1726 * intersects with "bounds" and derive the strides from the result.
1728 static __isl_give isl_ast_graft_list *add_node(
1729 __isl_take isl_ast_graft_list *list, __isl_take isl_union_map *executed,
1730 __isl_take isl_basic_set *bounds, __isl_take isl_ast_build *build)
1732 isl_ast_graft *graft;
1733 isl_set *domain = NULL;
1734 isl_union_set *uset;
1735 int empty, disjoint;
1737 uset = isl_union_set_from_basic_set(isl_basic_set_copy(bounds));
1738 executed = isl_union_map_intersect_domain(executed, uset);
1739 empty = isl_union_map_is_empty(executed);
1740 if (empty < 0)
1741 goto error;
1742 if (empty)
1743 goto done;
1745 uset = isl_union_map_domain(isl_union_map_copy(executed));
1746 domain = isl_set_from_union_set(uset);
1747 domain = isl_ast_build_specialize(build, domain);
1749 domain = isl_set_compute_divs(domain);
1750 domain = isl_ast_build_eliminate_inner(build, domain);
1751 disjoint = isl_set_is_disjoint(domain, build->domain);
1752 if (disjoint < 0)
1753 goto error;
1754 if (disjoint)
1755 goto done;
1757 build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
1759 graft = create_node(executed, bounds, domain,
1760 isl_ast_build_copy(build));
1761 list = isl_ast_graft_list_add(list, graft);
1762 isl_ast_build_free(build);
1763 return list;
1764 error:
1765 list = isl_ast_graft_list_free(list);
1766 done:
1767 isl_set_free(domain);
1768 isl_basic_set_free(bounds);
1769 isl_union_map_free(executed);
1770 isl_ast_build_free(build);
1771 return list;
1774 /* Does any element of i follow or coincide with any element of j
1775 * at the current depth for equal values of the outer dimensions?
1777 static int domain_follows_at_depth(__isl_keep isl_basic_set *i,
1778 __isl_keep isl_basic_set *j, void *user)
1780 int depth = *(int *) user;
1781 isl_basic_map *test;
1782 int empty;
1783 int l;
1785 test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1786 isl_basic_set_copy(j));
1787 for (l = 0; l < depth; ++l)
1788 test = isl_basic_map_equate(test, isl_dim_in, l,
1789 isl_dim_out, l);
1790 test = isl_basic_map_order_ge(test, isl_dim_in, depth,
1791 isl_dim_out, depth);
1792 empty = isl_basic_map_is_empty(test);
1793 isl_basic_map_free(test);
1795 return empty < 0 ? -1 : !empty;
1798 /* Split up each element of "list" into a part that is related to "bset"
1799 * according to "gt" and a part that is not.
1800 * Return a list that consist of "bset" and all the pieces.
1802 static __isl_give isl_basic_set_list *add_split_on(
1803 __isl_take isl_basic_set_list *list, __isl_take isl_basic_set *bset,
1804 __isl_keep isl_basic_map *gt)
1806 int i, n;
1807 isl_basic_set_list *res;
1809 if (!list)
1810 bset = isl_basic_set_free(bset);
1812 gt = isl_basic_map_copy(gt);
1813 gt = isl_basic_map_intersect_domain(gt, isl_basic_set_copy(bset));
1814 n = isl_basic_set_list_n_basic_set(list);
1815 res = isl_basic_set_list_from_basic_set(bset);
1816 for (i = 0; res && i < n; ++i) {
1817 isl_basic_set *bset;
1818 isl_set *set1, *set2;
1819 isl_basic_map *bmap;
1820 int empty;
1822 bset = isl_basic_set_list_get_basic_set(list, i);
1823 bmap = isl_basic_map_copy(gt);
1824 bmap = isl_basic_map_intersect_range(bmap, bset);
1825 bset = isl_basic_map_range(bmap);
1826 empty = isl_basic_set_is_empty(bset);
1827 if (empty < 0)
1828 res = isl_basic_set_list_free(res);
1829 if (empty) {
1830 isl_basic_set_free(bset);
1831 bset = isl_basic_set_list_get_basic_set(list, i);
1832 res = isl_basic_set_list_add(res, bset);
1833 continue;
1836 res = isl_basic_set_list_add(res, isl_basic_set_copy(bset));
1837 set1 = isl_set_from_basic_set(bset);
1838 bset = isl_basic_set_list_get_basic_set(list, i);
1839 set2 = isl_set_from_basic_set(bset);
1840 set1 = isl_set_subtract(set2, set1);
1841 set1 = isl_set_make_disjoint(set1);
1843 res = isl_basic_set_list_concat(res,
1844 isl_basic_set_list_from_set(set1));
1846 isl_basic_map_free(gt);
1847 isl_basic_set_list_free(list);
1848 return res;
1851 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1852 __isl_keep isl_basic_set_list *domain_list,
1853 __isl_keep isl_union_map *executed,
1854 __isl_keep isl_ast_build *build);
1856 /* Internal data structure for add_nodes.
1858 * "executed" and "build" are extra arguments to be passed to add_node.
1859 * "list" collects the results.
1861 struct isl_add_nodes_data {
1862 isl_union_map *executed;
1863 isl_ast_build *build;
1865 isl_ast_graft_list *list;
1868 /* Generate code for the schedule domains in "scc"
1869 * and add the results to "list".
1871 * The domains in "scc" form a strongly connected component in the ordering.
1872 * If the number of domains in "scc" is larger than 1, then this means
1873 * that we cannot determine a valid ordering for the domains in the component.
1874 * This should be fairly rare because the individual domains
1875 * have been made disjoint first.
1876 * The problem is that the domains may be integrally disjoint but not
1877 * rationally disjoint. For example, we may have domains
1879 * { [i,i] : 0 <= i <= 1 } and { [i,1-i] : 0 <= i <= 1 }
1881 * These two domains have an empty intersection, but their rational
1882 * relaxations do intersect. It is impossible to order these domains
1883 * in the second dimension because the first should be ordered before
1884 * the second for outer dimension equal to 0, while it should be ordered
1885 * after for outer dimension equal to 1.
1887 * This may happen in particular in case of unrolling since the domain
1888 * of each slice is replaced by its simple hull.
1890 * For each basic set i in "scc" and for each of the following basic sets j,
1891 * we split off that part of the basic set i that shares the outer dimensions
1892 * with j and lies before j in the current dimension.
1893 * We collect all the pieces in a new list that replaces "scc".
1895 * While the elements in "scc" should be disjoint, we double-check
1896 * this property to avoid running into an infinite recursion in case
1897 * they intersect due to some internal error.
1899 static int add_nodes(__isl_take isl_basic_set_list *scc, void *user)
1901 struct isl_add_nodes_data *data = user;
1902 int i, n, depth;
1903 isl_basic_set *bset, *first;
1904 isl_basic_set_list *list;
1905 isl_space *space;
1906 isl_basic_map *gt;
1908 n = isl_basic_set_list_n_basic_set(scc);
1909 bset = isl_basic_set_list_get_basic_set(scc, 0);
1910 if (n == 1) {
1911 isl_basic_set_list_free(scc);
1912 data->list = add_node(data->list,
1913 isl_union_map_copy(data->executed), bset,
1914 isl_ast_build_copy(data->build));
1915 return data->list ? 0 : -1;
1918 depth = isl_ast_build_get_depth(data->build);
1919 space = isl_basic_set_get_space(bset);
1920 space = isl_space_map_from_set(space);
1921 gt = isl_basic_map_universe(space);
1922 for (i = 0; i < depth; ++i)
1923 gt = isl_basic_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
1924 gt = isl_basic_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
1926 first = isl_basic_set_copy(bset);
1927 list = isl_basic_set_list_from_basic_set(bset);
1928 for (i = 1; i < n; ++i) {
1929 int disjoint;
1931 bset = isl_basic_set_list_get_basic_set(scc, i);
1933 disjoint = isl_basic_set_is_disjoint(bset, first);
1934 if (disjoint < 0)
1935 list = isl_basic_set_list_free(list);
1936 else if (!disjoint)
1937 isl_die(isl_basic_set_list_get_ctx(scc),
1938 isl_error_internal,
1939 "basic sets in scc are assumed to be disjoint",
1940 list = isl_basic_set_list_free(list));
1942 list = add_split_on(list, bset, gt);
1944 isl_basic_set_free(first);
1945 isl_basic_map_free(gt);
1946 isl_basic_set_list_free(scc);
1947 scc = list;
1948 data->list = isl_ast_graft_list_concat(data->list,
1949 generate_sorted_domains(scc, data->executed, data->build));
1950 isl_basic_set_list_free(scc);
1952 return data->list ? 0 : -1;
1955 /* Sort the domains in "domain_list" according to the execution order
1956 * at the current depth (for equal values of the outer dimensions),
1957 * generate code for each of them, collecting the results in a list.
1958 * If no code is generated (because the intersection of the inverse schedule
1959 * with the domains turns out to be empty), then an empty list is returned.
1961 * The caller is responsible for ensuring that the basic sets in "domain_list"
1962 * are pair-wise disjoint. It can, however, in principle happen that
1963 * two basic sets should be ordered one way for one value of the outer
1964 * dimensions and the other way for some other value of the outer dimensions.
1965 * We therefore play safe and look for strongly connected components.
1966 * The function add_nodes takes care of handling non-trivial components.
1968 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1969 __isl_keep isl_basic_set_list *domain_list,
1970 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
1972 isl_ctx *ctx;
1973 struct isl_add_nodes_data data;
1974 int depth;
1975 int n;
1977 if (!domain_list)
1978 return NULL;
1980 ctx = isl_basic_set_list_get_ctx(domain_list);
1981 n = isl_basic_set_list_n_basic_set(domain_list);
1982 data.list = isl_ast_graft_list_alloc(ctx, n);
1983 if (n == 0)
1984 return data.list;
1985 if (n == 1)
1986 return add_node(data.list, isl_union_map_copy(executed),
1987 isl_basic_set_list_get_basic_set(domain_list, 0),
1988 isl_ast_build_copy(build));
1990 depth = isl_ast_build_get_depth(build);
1991 data.executed = executed;
1992 data.build = build;
1993 if (isl_basic_set_list_foreach_scc(domain_list,
1994 &domain_follows_at_depth, &depth,
1995 &add_nodes, &data) < 0)
1996 data.list = isl_ast_graft_list_free(data.list);
1998 return data.list;
2001 /* Do i and j share any values for the outer dimensions?
2003 static int shared_outer(__isl_keep isl_basic_set *i,
2004 __isl_keep isl_basic_set *j, void *user)
2006 int depth = *(int *) user;
2007 isl_basic_map *test;
2008 int empty;
2009 int l;
2011 test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
2012 isl_basic_set_copy(j));
2013 for (l = 0; l < depth; ++l)
2014 test = isl_basic_map_equate(test, isl_dim_in, l,
2015 isl_dim_out, l);
2016 empty = isl_basic_map_is_empty(test);
2017 isl_basic_map_free(test);
2019 return empty < 0 ? -1 : !empty;
2022 /* Internal data structure for generate_sorted_domains_wrap.
2024 * "n" is the total number of basic sets
2025 * "executed" and "build" are extra arguments to be passed
2026 * to generate_sorted_domains.
2028 * "single" is set to 1 by generate_sorted_domains_wrap if there
2029 * is only a single component.
2030 * "list" collects the results.
2032 struct isl_ast_generate_parallel_domains_data {
2033 int n;
2034 isl_union_map *executed;
2035 isl_ast_build *build;
2037 int single;
2038 isl_ast_graft_list *list;
2041 /* Call generate_sorted_domains on "scc", fuse the result into a list
2042 * with either zero or one graft and collect the these single element
2043 * lists into data->list.
2045 * If there is only one component, i.e., if the number of basic sets
2046 * in the current component is equal to the total number of basic sets,
2047 * then data->single is set to 1 and the result of generate_sorted_domains
2048 * is not fused.
2050 static int generate_sorted_domains_wrap(__isl_take isl_basic_set_list *scc,
2051 void *user)
2053 struct isl_ast_generate_parallel_domains_data *data = user;
2054 isl_ast_graft_list *list;
2056 list = generate_sorted_domains(scc, data->executed, data->build);
2057 data->single = isl_basic_set_list_n_basic_set(scc) == data->n;
2058 if (!data->single)
2059 list = isl_ast_graft_list_fuse(list, data->build);
2060 if (!data->list)
2061 data->list = list;
2062 else
2063 data->list = isl_ast_graft_list_concat(data->list, list);
2065 isl_basic_set_list_free(scc);
2066 if (!data->list)
2067 return -1;
2069 return 0;
2072 /* Look for any (weakly connected) components in the "domain_list"
2073 * of domains that share some values of the outer dimensions.
2074 * That is, domains in different components do not share any values
2075 * of the outer dimensions. This means that these components
2076 * can be freely reordered.
2077 * Within each of the components, we sort the domains according
2078 * to the execution order at the current depth.
2080 * If there is more than one component, then generate_sorted_domains_wrap
2081 * fuses the result of each call to generate_sorted_domains
2082 * into a list with either zero or one graft and collects these (at most)
2083 * single element lists into a bigger list. This means that the elements of the
2084 * final list can be freely reordered. In particular, we sort them
2085 * according to an arbitrary but fixed ordering to ease merging of
2086 * graft lists from different components.
2088 static __isl_give isl_ast_graft_list *generate_parallel_domains(
2089 __isl_keep isl_basic_set_list *domain_list,
2090 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2092 int depth;
2093 struct isl_ast_generate_parallel_domains_data data;
2095 if (!domain_list)
2096 return NULL;
2098 data.n = isl_basic_set_list_n_basic_set(domain_list);
2099 if (data.n <= 1)
2100 return generate_sorted_domains(domain_list, executed, build);
2102 depth = isl_ast_build_get_depth(build);
2103 data.list = NULL;
2104 data.executed = executed;
2105 data.build = build;
2106 data.single = 0;
2107 if (isl_basic_set_list_foreach_scc(domain_list, &shared_outer, &depth,
2108 &generate_sorted_domains_wrap,
2109 &data) < 0)
2110 data.list = isl_ast_graft_list_free(data.list);
2112 if (!data.single)
2113 data.list = isl_ast_graft_list_sort_guard(data.list);
2115 return data.list;
2118 /* Internal data for separate_domain.
2120 * "explicit" is set if we only want to use explicit bounds.
2122 * "domain" collects the separated domains.
2124 struct isl_separate_domain_data {
2125 isl_ast_build *build;
2126 int explicit;
2127 isl_set *domain;
2130 /* Extract implicit bounds on the current dimension for the executed "map".
2132 * The domain of "map" may involve inner dimensions, so we
2133 * need to eliminate them.
2135 static __isl_give isl_set *implicit_bounds(__isl_take isl_map *map,
2136 __isl_keep isl_ast_build *build)
2138 isl_set *domain;
2140 domain = isl_map_domain(map);
2141 domain = isl_ast_build_eliminate(build, domain);
2143 return domain;
2146 /* Extract explicit bounds on the current dimension for the executed "map".
2148 * Rather than eliminating the inner dimensions as in implicit_bounds,
2149 * we simply drop any constraints involving those inner dimensions.
2150 * The idea is that most bounds that are implied by constraints on the
2151 * inner dimensions will be enforced by for loops and not by explicit guards.
2152 * There is then no need to separate along those bounds.
2154 static __isl_give isl_set *explicit_bounds(__isl_take isl_map *map,
2155 __isl_keep isl_ast_build *build)
2157 isl_set *domain;
2158 int depth, dim;
2160 dim = isl_map_dim(map, isl_dim_out);
2161 map = isl_map_drop_constraints_involving_dims(map, isl_dim_out, 0, dim);
2163 domain = isl_map_domain(map);
2164 depth = isl_ast_build_get_depth(build);
2165 dim = isl_set_dim(domain, isl_dim_set);
2166 domain = isl_set_detect_equalities(domain);
2167 domain = isl_set_drop_constraints_involving_dims(domain,
2168 isl_dim_set, depth + 1, dim - (depth + 1));
2169 domain = isl_set_remove_divs_involving_dims(domain,
2170 isl_dim_set, depth, 1);
2171 domain = isl_set_remove_unknown_divs(domain);
2173 return domain;
2176 /* Split data->domain into pieces that intersect with the range of "map"
2177 * and pieces that do not intersect with the range of "map"
2178 * and then add that part of the range of "map" that does not intersect
2179 * with data->domain.
2181 static int separate_domain(__isl_take isl_map *map, void *user)
2183 struct isl_separate_domain_data *data = user;
2184 isl_set *domain;
2185 isl_set *d1, *d2;
2187 if (data->explicit)
2188 domain = explicit_bounds(map, data->build);
2189 else
2190 domain = implicit_bounds(map, data->build);
2192 domain = isl_set_coalesce(domain);
2193 domain = isl_set_make_disjoint(domain);
2194 d1 = isl_set_subtract(isl_set_copy(domain), isl_set_copy(data->domain));
2195 d2 = isl_set_subtract(isl_set_copy(data->domain), isl_set_copy(domain));
2196 data->domain = isl_set_intersect(data->domain, domain);
2197 data->domain = isl_set_union(data->domain, d1);
2198 data->domain = isl_set_union(data->domain, d2);
2200 return 0;
2203 /* Separate the schedule domains of "executed".
2205 * That is, break up the domain of "executed" into basic sets,
2206 * such that for each basic set S, every element in S is associated with
2207 * the same domain spaces.
2209 * "space" is the (single) domain space of "executed".
2211 static __isl_give isl_set *separate_schedule_domains(
2212 __isl_take isl_space *space, __isl_take isl_union_map *executed,
2213 __isl_keep isl_ast_build *build)
2215 struct isl_separate_domain_data data = { build };
2216 isl_ctx *ctx;
2218 ctx = isl_ast_build_get_ctx(build);
2219 data.explicit = isl_options_get_ast_build_separation_bounds(ctx) ==
2220 ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT;
2221 data.domain = isl_set_empty(space);
2222 if (isl_union_map_foreach_map(executed, &separate_domain, &data) < 0)
2223 data.domain = isl_set_free(data.domain);
2225 isl_union_map_free(executed);
2226 return data.domain;
2229 /* Temporary data used during the search for a lower bound for unrolling.
2231 * "domain" is the original set for which to find a lower bound
2232 * "depth" is the dimension for which to find a lower boudn
2234 * "lower" is the best lower bound found so far. It is NULL if we have not
2235 * found any yet.
2236 * "n" is the corresponding size. If lower is NULL, then the value of n
2237 * is undefined.
2239 struct isl_find_unroll_data {
2240 isl_set *domain;
2241 int depth;
2243 isl_aff *lower;
2244 int *n;
2247 /* Check if we can use "c" as a lower bound and if it is better than
2248 * any previously found lower bound.
2250 * If "c" does not involve the dimension at the current depth,
2251 * then we cannot use it.
2252 * Otherwise, let "c" be of the form
2254 * i >= f(j)/a
2256 * We compute the maximal value of
2258 * -ceil(f(j)/a)) + i + 1
2260 * over the domain. If there is such a value "n", then we know
2262 * -ceil(f(j)/a)) + i + 1 <= n
2264 * or
2266 * i < ceil(f(j)/a)) + n
2268 * meaning that we can use ceil(f(j)/a)) as a lower bound for unrolling.
2269 * We just need to check if we have found any lower bound before and
2270 * if the new lower bound is better (smaller n) than the previously found
2271 * lower bounds.
2273 static int update_unrolling_lower_bound(struct isl_find_unroll_data *data,
2274 __isl_keep isl_constraint *c)
2276 isl_aff *aff, *lower;
2277 isl_val *max;
2279 if (!isl_constraint_is_lower_bound(c, isl_dim_set, data->depth))
2280 return 0;
2282 lower = isl_constraint_get_bound(c, isl_dim_set, data->depth);
2283 lower = isl_aff_ceil(lower);
2284 aff = isl_aff_copy(lower);
2285 aff = isl_aff_neg(aff);
2286 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, data->depth, 1);
2287 aff = isl_aff_add_constant_si(aff, 1);
2288 max = isl_set_max_val(data->domain, aff);
2289 isl_aff_free(aff);
2291 if (!max)
2292 goto error;
2293 if (isl_val_is_infty(max)) {
2294 isl_val_free(max);
2295 isl_aff_free(lower);
2296 return 0;
2299 if (isl_val_cmp_si(max, INT_MAX) <= 0 &&
2300 (!data->lower || isl_val_cmp_si(max, *data->n) < 0)) {
2301 isl_aff_free(data->lower);
2302 data->lower = lower;
2303 *data->n = isl_val_get_num_si(max);
2304 } else
2305 isl_aff_free(lower);
2306 isl_val_free(max);
2308 return 1;
2309 error:
2310 isl_aff_free(lower);
2311 return -1;
2314 /* Check if we can use "c" as a lower bound and if it is better than
2315 * any previously found lower bound.
2317 static int constraint_find_unroll(__isl_take isl_constraint *c, void *user)
2319 struct isl_find_unroll_data *data;
2320 int r;
2322 data = (struct isl_find_unroll_data *) user;
2323 r = update_unrolling_lower_bound(data, c);
2324 isl_constraint_free(c);
2326 return r;
2329 /* Look for a lower bound l(i) on the dimension at "depth"
2330 * and a size n such that "domain" is a subset of
2332 * { [i] : l(i) <= i_d < l(i) + n }
2334 * where d is "depth" and l(i) depends only on earlier dimensions.
2335 * Furthermore, try and find a lower bound such that n is as small as possible.
2336 * In particular, "n" needs to be finite.
2338 * Inner dimensions have been eliminated from "domain" by the caller.
2340 * We first construct a collection of lower bounds on the input set
2341 * by computing its simple hull. We then iterate through them,
2342 * discarding those that we cannot use (either because they do not
2343 * involve the dimension at "depth" or because they have no corresponding
2344 * upper bound, meaning that "n" would be unbounded) and pick out the
2345 * best from the remaining ones.
2347 * If we cannot find a suitable lower bound, then we consider that
2348 * to be an error.
2350 static __isl_give isl_aff *find_unroll_lower_bound(__isl_keep isl_set *domain,
2351 int depth, int *n)
2353 struct isl_find_unroll_data data = { domain, depth, NULL, n };
2354 isl_basic_set *hull;
2356 hull = isl_set_simple_hull(isl_set_copy(domain));
2358 if (isl_basic_set_foreach_constraint(hull,
2359 &constraint_find_unroll, &data) < 0)
2360 goto error;
2362 isl_basic_set_free(hull);
2364 if (!data.lower)
2365 isl_die(isl_set_get_ctx(domain), isl_error_invalid,
2366 "cannot find lower bound for unrolling", return NULL);
2368 return data.lower;
2369 error:
2370 isl_basic_set_free(hull);
2371 return isl_aff_free(data.lower);
2374 /* Return the constraint
2376 * i_"depth" = aff + offset
2378 static __isl_give isl_constraint *at_offset(int depth, __isl_keep isl_aff *aff,
2379 int offset)
2381 aff = isl_aff_copy(aff);
2382 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, depth, -1);
2383 aff = isl_aff_add_constant_si(aff, offset);
2384 return isl_equality_from_aff(aff);
2387 /* Data structure for storing the results and the intermediate objects
2388 * of compute_domains.
2390 * "list" is the main result of the function and contains a list
2391 * of disjoint basic sets for which code should be generated.
2393 * "executed" and "build" are inputs to compute_domains.
2394 * "schedule_domain" is the domain of "executed".
2396 * "option" constains the domains at the current depth that should by
2397 * atomic, separated or unrolled. These domains are as specified by
2398 * the user, except that inner dimensions have been eliminated and
2399 * that they have been made pair-wise disjoint.
2401 * "sep_class" contains the user-specified split into separation classes
2402 * specialized to the current depth.
2403 * "done" contains the union of the separation domains that have already
2404 * been handled.
2406 struct isl_codegen_domains {
2407 isl_basic_set_list *list;
2409 isl_union_map *executed;
2410 isl_ast_build *build;
2411 isl_set *schedule_domain;
2413 isl_set *option[3];
2415 isl_map *sep_class;
2416 isl_set *done;
2419 /* Extend domains->list with a list of basic sets, one for each value
2420 * of the current dimension in "domain" and remove the corresponding
2421 * sets from the class domain. Return the updated class domain.
2422 * The divs that involve the current dimension have not been projected out
2423 * from this domain.
2425 * Since we are going to be iterating over the individual values,
2426 * we first check if there are any strides on the current dimension.
2427 * If there is, we rewrite the current dimension i as
2429 * i = stride i' + offset
2431 * and then iterate over individual values of i' instead.
2433 * We then look for a lower bound on i' and a size such that the domain
2434 * is a subset of
2436 * { [j,i'] : l(j) <= i' < l(j) + n }
2438 * and then take slices of the domain at values of i'
2439 * between l(j) and l(j) + n - 1.
2441 * We compute the unshifted simple hull of each slice to ensure that
2442 * we have a single basic set per offset. The slicing constraint
2443 * may get simplified away before the unshifted simple hull is taken
2444 * and may therefore in some rare cases disappear from the result.
2445 * We therefore explicitly add the constraint back after computing
2446 * the unshifted simple hull to ensure that the basic sets
2447 * remain disjoint. The constraints that are dropped by taking the hull
2448 * will be taken into account at the next level, as in the case of the
2449 * atomic option.
2451 * Finally, we map i' back to i and add each basic set to the list.
2452 * Since we may have dropped some constraints, we intersect with
2453 * the class domain again to ensure that each element in the list
2454 * is disjoint from the other class domains.
2456 static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains,
2457 __isl_take isl_set *domain, __isl_take isl_set *class_domain)
2459 int i, n;
2460 int depth;
2461 isl_ctx *ctx;
2462 isl_aff *lower;
2463 isl_multi_aff *expansion;
2464 isl_basic_map *bmap;
2465 isl_set *unroll_domain;
2466 isl_ast_build *build;
2468 if (!domain)
2469 return isl_set_free(class_domain);
2471 ctx = isl_set_get_ctx(domain);
2472 depth = isl_ast_build_get_depth(domains->build);
2473 build = isl_ast_build_copy(domains->build);
2474 domain = isl_ast_build_eliminate_inner(build, domain);
2475 domain = isl_set_intersect(domain, isl_ast_build_get_domain(build));
2476 build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
2477 expansion = isl_ast_build_get_stride_expansion(build);
2479 domain = isl_set_preimage_multi_aff(domain,
2480 isl_multi_aff_copy(expansion));
2481 domain = isl_ast_build_eliminate_divs(build, domain);
2483 isl_ast_build_free(build);
2485 lower = find_unroll_lower_bound(domain, depth, &n);
2486 if (!lower)
2487 class_domain = isl_set_free(class_domain);
2489 bmap = isl_basic_map_from_multi_aff(expansion);
2491 unroll_domain = isl_set_empty(isl_set_get_space(domain));
2493 for (i = 0; class_domain && i < n; ++i) {
2494 isl_set *set;
2495 isl_basic_set *bset;
2496 isl_constraint *slice;
2497 isl_basic_set_list *list;
2499 slice = at_offset(depth, lower, i);
2500 set = isl_set_copy(domain);
2501 set = isl_set_add_constraint(set, isl_constraint_copy(slice));
2502 bset = isl_set_unshifted_simple_hull(set);
2503 bset = isl_basic_set_add_constraint(bset, slice);
2504 bset = isl_basic_set_apply(bset, isl_basic_map_copy(bmap));
2505 set = isl_set_from_basic_set(bset);
2506 unroll_domain = isl_set_union(unroll_domain, isl_set_copy(set));
2507 set = isl_set_intersect(set, isl_set_copy(class_domain));
2508 set = isl_set_make_disjoint(set);
2509 list = isl_basic_set_list_from_set(set);
2510 domains->list = isl_basic_set_list_concat(domains->list, list);
2513 class_domain = isl_set_subtract(class_domain, unroll_domain);
2515 isl_aff_free(lower);
2516 isl_set_free(domain);
2517 isl_basic_map_free(bmap);
2519 return class_domain;
2522 /* Add domains to domains->list for each individual value of the current
2523 * dimension, for that part of the schedule domain that lies in the
2524 * intersection of the option domain and the class domain.
2525 * Remove the corresponding sets from the class domain and
2526 * return the updated class domain.
2528 * We first break up the unroll option domain into individual pieces
2529 * and then handle each of them separately. The unroll option domain
2530 * has been made disjoint in compute_domains_init_options,
2532 * Note that we actively want to combine different pieces of the
2533 * schedule domain that have the same value at the current dimension.
2534 * We therefore need to break up the unroll option domain before
2535 * intersecting with class and schedule domain, hoping that the
2536 * unroll option domain specified by the user is relatively simple.
2538 static __isl_give isl_set *compute_unroll_domains(
2539 struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2541 isl_set *unroll_domain;
2542 isl_basic_set_list *unroll_list;
2543 int i, n;
2544 int empty;
2546 empty = isl_set_is_empty(domains->option[unroll]);
2547 if (empty < 0)
2548 return isl_set_free(class_domain);
2549 if (empty)
2550 return class_domain;
2552 unroll_domain = isl_set_copy(domains->option[unroll]);
2553 unroll_list = isl_basic_set_list_from_set(unroll_domain);
2555 n = isl_basic_set_list_n_basic_set(unroll_list);
2556 for (i = 0; i < n; ++i) {
2557 isl_basic_set *bset;
2559 bset = isl_basic_set_list_get_basic_set(unroll_list, i);
2560 unroll_domain = isl_set_from_basic_set(bset);
2561 unroll_domain = isl_set_intersect(unroll_domain,
2562 isl_set_copy(class_domain));
2563 unroll_domain = isl_set_intersect(unroll_domain,
2564 isl_set_copy(domains->schedule_domain));
2566 empty = isl_set_is_empty(unroll_domain);
2567 if (empty >= 0 && empty) {
2568 isl_set_free(unroll_domain);
2569 continue;
2572 class_domain = do_unroll(domains, unroll_domain, class_domain);
2575 isl_basic_set_list_free(unroll_list);
2577 return class_domain;
2580 /* Try and construct a single basic set that includes the intersection of
2581 * the schedule domain, the atomic option domain and the class domain.
2582 * Add the resulting basic set(s) to domains->list and remove them
2583 * from class_domain. Return the updated class domain.
2585 * We construct a single domain rather than trying to combine
2586 * the schedule domains of individual domains because we are working
2587 * within a single component so that non-overlapping schedule domains
2588 * should already have been separated.
2589 * We do however need to make sure that this single domains is a subset
2590 * of the class domain so that it would not intersect with any other
2591 * class domains. This means that we may end up splitting up the atomic
2592 * domain in case separation classes are being used.
2594 * "domain" is the intersection of the schedule domain and the class domain,
2595 * with inner dimensions projected out.
2597 static __isl_give isl_set *compute_atomic_domain(
2598 struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2600 isl_basic_set *bset;
2601 isl_basic_set_list *list;
2602 isl_set *domain, *atomic_domain;
2603 int empty;
2605 domain = isl_set_copy(domains->option[atomic]);
2606 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2607 domain = isl_set_intersect(domain,
2608 isl_set_copy(domains->schedule_domain));
2609 empty = isl_set_is_empty(domain);
2610 if (empty < 0)
2611 class_domain = isl_set_free(class_domain);
2612 if (empty) {
2613 isl_set_free(domain);
2614 return class_domain;
2617 domain = isl_ast_build_eliminate(domains->build, domain);
2618 domain = isl_set_coalesce(domain);
2619 bset = isl_set_unshifted_simple_hull(domain);
2620 domain = isl_set_from_basic_set(bset);
2621 atomic_domain = isl_set_copy(domain);
2622 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2623 class_domain = isl_set_subtract(class_domain, atomic_domain);
2624 domain = isl_set_make_disjoint(domain);
2625 list = isl_basic_set_list_from_set(domain);
2626 domains->list = isl_basic_set_list_concat(domains->list, list);
2628 return class_domain;
2631 /* Split up the schedule domain into uniform basic sets,
2632 * in the sense that each element in a basic set is associated to
2633 * elements of the same domains, and add the result to domains->list.
2634 * Do this for that part of the schedule domain that lies in the
2635 * intersection of "class_domain" and the separate option domain.
2637 * "class_domain" may or may not include the constraints
2638 * of the schedule domain, but this does not make a difference
2639 * since we are going to intersect it with the domain of the inverse schedule.
2640 * If it includes schedule domain constraints, then they may involve
2641 * inner dimensions, but we will eliminate them in separation_domain.
2643 static int compute_separate_domain(struct isl_codegen_domains *domains,
2644 __isl_keep isl_set *class_domain)
2646 isl_space *space;
2647 isl_set *domain;
2648 isl_union_map *executed;
2649 isl_basic_set_list *list;
2650 int empty;
2652 domain = isl_set_copy(domains->option[separate]);
2653 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2654 executed = isl_union_map_copy(domains->executed);
2655 executed = isl_union_map_intersect_domain(executed,
2656 isl_union_set_from_set(domain));
2657 empty = isl_union_map_is_empty(executed);
2658 if (empty < 0 || empty) {
2659 isl_union_map_free(executed);
2660 return empty < 0 ? -1 : 0;
2663 space = isl_set_get_space(class_domain);
2664 domain = separate_schedule_domains(space, executed, domains->build);
2666 list = isl_basic_set_list_from_set(domain);
2667 domains->list = isl_basic_set_list_concat(domains->list, list);
2669 return 0;
2672 /* Split up the domain at the current depth into disjoint
2673 * basic sets for which code should be generated separately
2674 * for the given separation class domain.
2676 * If any separation classes have been defined, then "class_domain"
2677 * is the domain of the current class and does not refer to inner dimensions.
2678 * Otherwise, "class_domain" is the universe domain.
2680 * We first make sure that the class domain is disjoint from
2681 * previously considered class domains.
2683 * The separate domains can be computed directly from the "class_domain".
2685 * The unroll, atomic and remainder domains need the constraints
2686 * from the schedule domain.
2688 * For unrolling, the actual schedule domain is needed (with divs that
2689 * may refer to the current dimension) so that stride detection can be
2690 * performed.
2692 * For atomic and remainder domains, inner dimensions and divs involving
2693 * the current dimensions should be eliminated.
2694 * In case we are working within a separation class, we need to intersect
2695 * the result with the current "class_domain" to ensure that the domains
2696 * are disjoint from those generated from other class domains.
2698 * The domain that has been made atomic may be larger than specified
2699 * by the user since it needs to be representable as a single basic set.
2700 * This possibly larger domain is removed from class_domain by
2701 * compute_atomic_domain. It is computed first so that the extended domain
2702 * would not overlap with any domains computed before.
2703 * Similary, the unrolled domains may have some constraints removed and
2704 * may therefore also be larger than specified by the user.
2706 * If anything is left after handling separate, unroll and atomic,
2707 * we split it up into basic sets and append the basic sets to domains->list.
2709 static int compute_partial_domains(struct isl_codegen_domains *domains,
2710 __isl_take isl_set *class_domain)
2712 isl_basic_set_list *list;
2713 isl_set *domain;
2715 class_domain = isl_set_subtract(class_domain,
2716 isl_set_copy(domains->done));
2717 domains->done = isl_set_union(domains->done,
2718 isl_set_copy(class_domain));
2720 class_domain = compute_atomic_domain(domains, class_domain);
2721 class_domain = compute_unroll_domains(domains, class_domain);
2723 domain = isl_set_copy(class_domain);
2725 if (compute_separate_domain(domains, domain) < 0)
2726 goto error;
2727 domain = isl_set_subtract(domain,
2728 isl_set_copy(domains->option[separate]));
2730 domain = isl_set_intersect(domain,
2731 isl_set_copy(domains->schedule_domain));
2733 domain = isl_ast_build_eliminate(domains->build, domain);
2734 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2736 domain = isl_set_coalesce(domain);
2737 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 isl_set_free(class_domain);
2744 return 0;
2745 error:
2746 isl_set_free(domain);
2747 isl_set_free(class_domain);
2748 return -1;
2751 /* Split up the domain at the current depth into disjoint
2752 * basic sets for which code should be generated separately
2753 * for the separation class identified by "pnt".
2755 * We extract the corresponding class domain from domains->sep_class,
2756 * eliminate inner dimensions and pass control to compute_partial_domains.
2758 static int compute_class_domains(__isl_take isl_point *pnt, void *user)
2760 struct isl_codegen_domains *domains = user;
2761 isl_set *class_set;
2762 isl_set *domain;
2763 int disjoint;
2765 class_set = isl_set_from_point(pnt);
2766 domain = isl_map_domain(isl_map_intersect_range(
2767 isl_map_copy(domains->sep_class), class_set));
2768 domain = isl_ast_build_compute_gist(domains->build, domain);
2769 domain = isl_ast_build_eliminate(domains->build, domain);
2771 disjoint = isl_set_plain_is_disjoint(domain, domains->schedule_domain);
2772 if (disjoint < 0)
2773 return -1;
2774 if (disjoint) {
2775 isl_set_free(domain);
2776 return 0;
2779 return compute_partial_domains(domains, domain);
2782 /* Extract the domains at the current depth that should be atomic,
2783 * separated or unrolled and store them in option.
2785 * The domains specified by the user might overlap, so we make
2786 * them disjoint by subtracting earlier domains from later domains.
2788 static void compute_domains_init_options(isl_set *option[3],
2789 __isl_keep isl_ast_build *build)
2791 enum isl_ast_build_domain_type type, type2;
2793 for (type = atomic; type <= separate; ++type) {
2794 option[type] = isl_ast_build_get_option_domain(build, type);
2795 for (type2 = atomic; type2 < type; ++type2)
2796 option[type] = isl_set_subtract(option[type],
2797 isl_set_copy(option[type2]));
2800 option[unroll] = isl_set_coalesce(option[unroll]);
2801 option[unroll] = isl_set_make_disjoint(option[unroll]);
2804 /* Split up the domain at the current depth into disjoint
2805 * basic sets for which code should be generated separately,
2806 * based on the user-specified options.
2807 * Return the list of disjoint basic sets.
2809 * There are three kinds of domains that we need to keep track of.
2810 * - the "schedule domain" is the domain of "executed"
2811 * - the "class domain" is the domain corresponding to the currrent
2812 * separation class
2813 * - the "option domain" is the domain corresponding to one of the options
2814 * atomic, unroll or separate
2816 * We first consider the individial values of the separation classes
2817 * and split up the domain for each of them separately.
2818 * Finally, we consider the remainder. If no separation classes were
2819 * specified, then we call compute_partial_domains with the universe
2820 * "class_domain". Otherwise, we take the "schedule_domain" as "class_domain",
2821 * with inner dimensions removed. We do this because we want to
2822 * avoid computing the complement of the class domains (i.e., the difference
2823 * between the universe and domains->done).
2825 static __isl_give isl_basic_set_list *compute_domains(
2826 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2828 struct isl_codegen_domains domains;
2829 isl_ctx *ctx;
2830 isl_set *domain;
2831 isl_union_set *schedule_domain;
2832 isl_set *classes;
2833 isl_space *space;
2834 int n_param;
2835 enum isl_ast_build_domain_type type;
2836 int empty;
2838 if (!executed)
2839 return NULL;
2841 ctx = isl_union_map_get_ctx(executed);
2842 domains.list = isl_basic_set_list_alloc(ctx, 0);
2844 schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
2845 domain = isl_set_from_union_set(schedule_domain);
2847 compute_domains_init_options(domains.option, build);
2849 domains.sep_class = isl_ast_build_get_separation_class(build);
2850 classes = isl_map_range(isl_map_copy(domains.sep_class));
2851 n_param = isl_set_dim(classes, isl_dim_param);
2852 classes = isl_set_project_out(classes, isl_dim_param, 0, n_param);
2854 space = isl_set_get_space(domain);
2855 domains.build = build;
2856 domains.schedule_domain = isl_set_copy(domain);
2857 domains.executed = executed;
2858 domains.done = isl_set_empty(space);
2860 if (isl_set_foreach_point(classes, &compute_class_domains, &domains) < 0)
2861 domains.list = isl_basic_set_list_free(domains.list);
2862 isl_set_free(classes);
2864 empty = isl_set_is_empty(domains.done);
2865 if (empty < 0) {
2866 domains.list = isl_basic_set_list_free(domains.list);
2867 domain = isl_set_free(domain);
2868 } else if (empty) {
2869 isl_set_free(domain);
2870 domain = isl_set_universe(isl_set_get_space(domains.done));
2871 } else {
2872 domain = isl_ast_build_eliminate(build, domain);
2874 if (compute_partial_domains(&domains, domain) < 0)
2875 domains.list = isl_basic_set_list_free(domains.list);
2877 isl_set_free(domains.schedule_domain);
2878 isl_set_free(domains.done);
2879 isl_map_free(domains.sep_class);
2880 for (type = atomic; type <= separate; ++type)
2881 isl_set_free(domains.option[type]);
2883 return domains.list;
2886 /* Generate code for a single component, after shifting (if any)
2887 * has been applied.
2889 * We first split up the domain at the current depth into disjoint
2890 * basic sets based on the user-specified options.
2891 * Then we generated code for each of them and concatenate the results.
2893 static __isl_give isl_ast_graft_list *generate_shifted_component(
2894 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
2896 isl_basic_set_list *domain_list;
2897 isl_ast_graft_list *list = NULL;
2899 domain_list = compute_domains(executed, build);
2900 list = generate_parallel_domains(domain_list, executed, build);
2902 isl_basic_set_list_free(domain_list);
2903 isl_union_map_free(executed);
2904 isl_ast_build_free(build);
2906 return list;
2909 struct isl_set_map_pair {
2910 isl_set *set;
2911 isl_map *map;
2914 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2915 * of indices into the "domain" array,
2916 * return the union of the "map" fields of the elements
2917 * indexed by the first "n" elements of "order".
2919 static __isl_give isl_union_map *construct_component_executed(
2920 struct isl_set_map_pair *domain, int *order, int n)
2922 int i;
2923 isl_map *map;
2924 isl_union_map *executed;
2926 map = isl_map_copy(domain[order[0]].map);
2927 executed = isl_union_map_from_map(map);
2928 for (i = 1; i < n; ++i) {
2929 map = isl_map_copy(domain[order[i]].map);
2930 executed = isl_union_map_add_map(executed, map);
2933 return executed;
2936 /* Generate code for a single component, after shifting (if any)
2937 * has been applied.
2939 * The component inverse schedule is specified as the "map" fields
2940 * of the elements of "domain" indexed by the first "n" elements of "order".
2942 static __isl_give isl_ast_graft_list *generate_shifted_component_from_list(
2943 struct isl_set_map_pair *domain, int *order, int n,
2944 __isl_take isl_ast_build *build)
2946 isl_union_map *executed;
2948 executed = construct_component_executed(domain, order, n);
2949 return generate_shifted_component(executed, build);
2952 /* Does set dimension "pos" of "set" have an obviously fixed value?
2954 static int dim_is_fixed(__isl_keep isl_set *set, int pos)
2956 int fixed;
2957 isl_val *v;
2959 v = isl_set_plain_get_val_if_fixed(set, isl_dim_set, pos);
2960 if (!v)
2961 return -1;
2962 fixed = !isl_val_is_nan(v);
2963 isl_val_free(v);
2965 return fixed;
2968 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2969 * of indices into the "domain" array,
2970 * do all (except for at most one) of the "set" field of the elements
2971 * indexed by the first "n" elements of "order" have a fixed value
2972 * at position "depth"?
2974 static int at_most_one_non_fixed(struct isl_set_map_pair *domain,
2975 int *order, int n, int depth)
2977 int i;
2978 int non_fixed = -1;
2980 for (i = 0; i < n; ++i) {
2981 int f;
2983 f = dim_is_fixed(domain[order[i]].set, depth);
2984 if (f < 0)
2985 return -1;
2986 if (f)
2987 continue;
2988 if (non_fixed >= 0)
2989 return 0;
2990 non_fixed = i;
2993 return 1;
2996 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2997 * of indices into the "domain" array,
2998 * eliminate the inner dimensions from the "set" field of the elements
2999 * indexed by the first "n" elements of "order", provided the current
3000 * dimension does not have a fixed value.
3002 * Return the index of the first element in "order" with a corresponding
3003 * "set" field that does not have an (obviously) fixed value.
3005 static int eliminate_non_fixed(struct isl_set_map_pair *domain,
3006 int *order, int n, int depth, __isl_keep isl_ast_build *build)
3008 int i;
3009 int base = -1;
3011 for (i = n - 1; i >= 0; --i) {
3012 int f;
3013 f = dim_is_fixed(domain[order[i]].set, depth);
3014 if (f < 0)
3015 return -1;
3016 if (f)
3017 continue;
3018 domain[order[i]].set = isl_ast_build_eliminate_inner(build,
3019 domain[order[i]].set);
3020 base = i;
3023 return base;
3026 /* Given an array "domain" of isl_set_map_pairs and an array "order"
3027 * of indices into the "domain" array,
3028 * find the element of "domain" (amongst those indexed by the first "n"
3029 * elements of "order") with the "set" field that has the smallest
3030 * value for the current iterator.
3032 * Note that the domain with the smallest value may depend on the parameters
3033 * and/or outer loop dimension. Since the result of this function is only
3034 * used as heuristic, we only make a reasonable attempt at finding the best
3035 * domain, one that should work in case a single domain provides the smallest
3036 * value for the current dimension over all values of the parameters
3037 * and outer dimensions.
3039 * In particular, we compute the smallest value of the first domain
3040 * and replace it by that of any later domain if that later domain
3041 * has a smallest value that is smaller for at least some value
3042 * of the parameters and outer dimensions.
3044 static int first_offset(struct isl_set_map_pair *domain, int *order, int n,
3045 __isl_keep isl_ast_build *build)
3047 int i;
3048 isl_map *min_first;
3049 int first = 0;
3051 min_first = isl_ast_build_map_to_iterator(build,
3052 isl_set_copy(domain[order[0]].set));
3053 min_first = isl_map_lexmin(min_first);
3055 for (i = 1; i < n; ++i) {
3056 isl_map *min, *test;
3057 int empty;
3059 min = isl_ast_build_map_to_iterator(build,
3060 isl_set_copy(domain[order[i]].set));
3061 min = isl_map_lexmin(min);
3062 test = isl_map_copy(min);
3063 test = isl_map_apply_domain(isl_map_copy(min_first), test);
3064 test = isl_map_order_lt(test, isl_dim_in, 0, isl_dim_out, 0);
3065 empty = isl_map_is_empty(test);
3066 isl_map_free(test);
3067 if (empty >= 0 && !empty) {
3068 isl_map_free(min_first);
3069 first = i;
3070 min_first = min;
3071 } else
3072 isl_map_free(min);
3074 if (empty < 0)
3075 break;
3078 isl_map_free(min_first);
3080 return i < n ? -1 : first;
3083 /* Construct a shifted inverse schedule based on the original inverse schedule,
3084 * the stride and the offset.
3086 * The original inverse schedule is specified as the "map" fields
3087 * of the elements of "domain" indexed by the first "n" elements of "order".
3089 * "stride" and "offset" are such that the difference
3090 * between the values of the current dimension of domain "i"
3091 * and the values of the current dimension for some reference domain are
3092 * equal to
3094 * stride * integer + offset[i]
3096 * Moreover, 0 <= offset[i] < stride.
3098 * For each domain, we create a map
3100 * { [..., j, ...] -> [..., j - offset[i], offset[i], ....] }
3102 * where j refers to the current dimension and the other dimensions are
3103 * unchanged, and apply this map to the original schedule domain.
3105 * For example, for the original schedule
3107 * { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3109 * and assuming the offset is 0 for the A domain and 1 for the B domain,
3110 * we apply the mapping
3112 * { [j] -> [j, 0] }
3114 * to the schedule of the "A" domain and the mapping
3116 * { [j - 1] -> [j, 1] }
3118 * to the schedule of the "B" domain.
3121 * Note that after the transformation, the differences between pairs
3122 * of values of the current dimension over all domains are multiples
3123 * of stride and that we have therefore exposed the stride.
3126 * To see that the mapping preserves the lexicographic order,
3127 * first note that each of the individual maps above preserves the order.
3128 * If the value of the current iterator is j1 in one domain and j2 in another,
3129 * then if j1 = j2, we know that the same map is applied to both domains
3130 * and the order is preserved.
3131 * Otherwise, let us assume, without loss of generality, that j1 < j2.
3132 * If c1 >= c2 (with c1 and c2 the corresponding offsets), then
3134 * j1 - c1 < j2 - c2
3136 * and the order is preserved.
3137 * If c1 < c2, then we know
3139 * 0 <= c2 - c1 < s
3141 * We also have
3143 * j2 - j1 = n * s + r
3145 * with n >= 0 and 0 <= r < s.
3146 * In other words, r = c2 - c1.
3147 * If n > 0, then
3149 * j1 - c1 < j2 - c2
3151 * If n = 0, then
3153 * j1 - c1 = j2 - c2
3155 * and so
3157 * (j1 - c1, c1) << (j2 - c2, c2)
3159 * with "<<" the lexicographic order, proving that the order is preserved
3160 * in all cases.
3162 static __isl_give isl_union_map *contruct_shifted_executed(
3163 struct isl_set_map_pair *domain, int *order, int n,
3164 __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3165 __isl_take isl_ast_build *build)
3167 int i;
3168 isl_union_map *executed;
3169 isl_space *space;
3170 isl_map *map;
3171 int depth;
3172 isl_constraint *c;
3174 depth = isl_ast_build_get_depth(build);
3175 space = isl_ast_build_get_space(build, 1);
3176 executed = isl_union_map_empty(isl_space_copy(space));
3177 space = isl_space_map_from_set(space);
3178 map = isl_map_identity(isl_space_copy(space));
3179 map = isl_map_eliminate(map, isl_dim_out, depth, 1);
3180 map = isl_map_insert_dims(map, isl_dim_out, depth + 1, 1);
3181 space = isl_space_insert_dims(space, isl_dim_out, depth + 1, 1);
3183 c = isl_equality_alloc(isl_local_space_from_space(space));
3184 c = isl_constraint_set_coefficient_si(c, isl_dim_in, depth, 1);
3185 c = isl_constraint_set_coefficient_si(c, isl_dim_out, depth, -1);
3187 for (i = 0; i < n; ++i) {
3188 isl_map *map_i;
3189 isl_val *v;
3191 v = isl_multi_val_get_val(offset, i);
3192 if (!v)
3193 break;
3194 map_i = isl_map_copy(map);
3195 map_i = isl_map_fix_val(map_i, isl_dim_out, depth + 1,
3196 isl_val_copy(v));
3197 v = isl_val_neg(v);
3198 c = isl_constraint_set_constant_val(c, v);
3199 map_i = isl_map_add_constraint(map_i, isl_constraint_copy(c));
3201 map_i = isl_map_apply_domain(isl_map_copy(domain[order[i]].map),
3202 map_i);
3203 executed = isl_union_map_add_map(executed, map_i);
3206 isl_constraint_free(c);
3207 isl_map_free(map);
3209 if (i < n)
3210 executed = isl_union_map_free(executed);
3212 return executed;
3215 /* Generate code for a single component, after exposing the stride,
3216 * given that the schedule domain is "shifted strided".
3218 * The component inverse schedule is specified as the "map" fields
3219 * of the elements of "domain" indexed by the first "n" elements of "order".
3221 * The schedule domain being "shifted strided" means that the differences
3222 * between the values of the current dimension of domain "i"
3223 * and the values of the current dimension for some reference domain are
3224 * equal to
3226 * stride * integer + offset[i]
3228 * We first look for the domain with the "smallest" value for the current
3229 * dimension and adjust the offsets such that the offset of the "smallest"
3230 * domain is equal to zero. The other offsets are reduced modulo stride.
3232 * Based on this information, we construct a new inverse schedule in
3233 * contruct_shifted_executed that exposes the stride.
3234 * Since this involves the introduction of a new schedule dimension,
3235 * the build needs to be changed accodingly.
3236 * After computing the AST, the newly introduced dimension needs
3237 * to be removed again from the list of grafts. We do this by plugging
3238 * in a mapping that represents the new schedule domain in terms of the
3239 * old schedule domain.
3241 static __isl_give isl_ast_graft_list *generate_shift_component(
3242 struct isl_set_map_pair *domain, int *order, int n,
3243 __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3244 __isl_take isl_ast_build *build)
3246 isl_ast_graft_list *list;
3247 int first;
3248 int depth;
3249 isl_ctx *ctx;
3250 isl_val *val;
3251 isl_multi_val *mv;
3252 isl_space *space;
3253 isl_multi_aff *ma, *zero;
3254 isl_union_map *executed;
3256 ctx = isl_ast_build_get_ctx(build);
3257 depth = isl_ast_build_get_depth(build);
3259 first = first_offset(domain, order, n, build);
3260 if (first < 0)
3261 goto error;
3263 mv = isl_multi_val_copy(offset);
3264 val = isl_multi_val_get_val(offset, first);
3265 val = isl_val_neg(val);
3266 mv = isl_multi_val_add_val(mv, val);
3267 mv = isl_multi_val_mod_val(mv, isl_val_copy(stride));
3269 executed = contruct_shifted_executed(domain, order, n, stride, mv,
3270 build);
3271 space = isl_ast_build_get_space(build, 1);
3272 space = isl_space_map_from_set(space);
3273 ma = isl_multi_aff_identity(isl_space_copy(space));
3274 space = isl_space_from_domain(isl_space_domain(space));
3275 space = isl_space_add_dims(space, isl_dim_out, 1);
3276 zero = isl_multi_aff_zero(space);
3277 ma = isl_multi_aff_range_splice(ma, depth + 1, zero);
3278 build = isl_ast_build_insert_dim(build, depth + 1);
3279 list = generate_shifted_component(executed, build);
3281 list = isl_ast_graft_list_preimage_multi_aff(list, ma);
3283 isl_multi_val_free(mv);
3285 return list;
3286 error:
3287 isl_ast_build_free(build);
3288 return NULL;
3291 /* Generate code for a single component.
3293 * The component inverse schedule is specified as the "map" fields
3294 * of the elements of "domain" indexed by the first "n" elements of "order".
3296 * This function may modify the "set" fields of "domain".
3298 * Before proceeding with the actual code generation for the component,
3299 * we first check if there are any "shifted" strides, meaning that
3300 * the schedule domains of the individual domains are all strided,
3301 * but that they have different offsets, resulting in the union
3302 * of schedule domains not being strided anymore.
3304 * The simplest example is the schedule
3306 * { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3308 * Both schedule domains are strided, but their union is not.
3309 * This function detects such cases and then rewrites the schedule to
3311 * { A[i] -> [2i, 0]: 0 <= i < 10; B[i] -> [2i, 1] : 0 <= i < 10 }
3313 * In the new schedule, the schedule domains have the same offset (modulo
3314 * the stride), ensuring that the union of schedule domains is also strided.
3317 * If there is only a single domain in the component, then there is
3318 * nothing to do. Similarly, if the current schedule dimension has
3319 * a fixed value for almost all domains then there is nothing to be done.
3320 * In particular, we need at least two domains where the current schedule
3321 * dimension does not have a fixed value.
3322 * Finally, if any of the options refer to the current schedule dimension,
3323 * then we bail out as well. It would be possible to reformulate the options
3324 * in terms of the new schedule domain, but that would introduce constraints
3325 * that separate the domains in the options and that is something we would
3326 * like to avoid.
3329 * To see if there is any shifted stride, we look at the differences
3330 * between the values of the current dimension in pairs of domains
3331 * for equal values of outer dimensions. These differences should be
3332 * of the form
3334 * m x + r
3336 * with "m" the stride and "r" a constant. Note that we cannot perform
3337 * this analysis on individual domains as the lower bound in each domain
3338 * may depend on parameters or outer dimensions and so the current dimension
3339 * itself may not have a fixed remainder on division by the stride.
3341 * In particular, we compare the first domain that does not have an
3342 * obviously fixed value for the current dimension to itself and all
3343 * other domains and collect the offsets and the gcd of the strides.
3344 * If the gcd becomes one, then we failed to find shifted strides.
3345 * If the gcd is zero, then the differences were all fixed, meaning
3346 * that some domains had non-obviously fixed values for the current dimension.
3347 * If all the offsets are the same (for those domains that do not have
3348 * an obviously fixed value for the current dimension), then we do not
3349 * apply the transformation.
3350 * If none of the domains were skipped, then there is nothing to do.
3351 * If some of them were skipped, then if we apply separation, the schedule
3352 * domain should get split in pieces with a (non-shifted) stride.
3354 * Otherwise, we apply a shift to expose the stride in
3355 * generate_shift_component.
3357 static __isl_give isl_ast_graft_list *generate_component(
3358 struct isl_set_map_pair *domain, int *order, int n,
3359 __isl_take isl_ast_build *build)
3361 int i, d;
3362 int depth;
3363 isl_ctx *ctx;
3364 isl_map *map;
3365 isl_set *deltas;
3366 isl_val *gcd = NULL;
3367 isl_multi_val *mv;
3368 int fixed, skip;
3369 int base;
3370 isl_ast_graft_list *list;
3371 int res = 0;
3373 depth = isl_ast_build_get_depth(build);
3375 skip = n == 1;
3376 if (skip >= 0 && !skip)
3377 skip = at_most_one_non_fixed(domain, order, n, depth);
3378 if (skip >= 0 && !skip)
3379 skip = isl_ast_build_options_involve_depth(build);
3380 if (skip < 0)
3381 goto error;
3382 if (skip)
3383 return generate_shifted_component_from_list(domain,
3384 order, n, build);
3386 base = eliminate_non_fixed(domain, order, n, depth, build);
3387 if (base < 0)
3388 goto error;
3390 ctx = isl_ast_build_get_ctx(build);
3392 mv = isl_multi_val_zero(isl_space_set_alloc(ctx, 0, n));
3394 fixed = 1;
3395 for (i = 0; i < n; ++i) {
3396 isl_val *r, *m;
3398 map = isl_map_from_domain_and_range(
3399 isl_set_copy(domain[order[base]].set),
3400 isl_set_copy(domain[order[i]].set));
3401 for (d = 0; d < depth; ++d)
3402 map = isl_map_equate(map, isl_dim_in, d,
3403 isl_dim_out, d);
3404 deltas = isl_map_deltas(map);
3405 res = isl_set_dim_residue_class_val(deltas, depth, &m, &r);
3406 isl_set_free(deltas);
3407 if (res < 0)
3408 break;
3410 if (i == 0)
3411 gcd = m;
3412 else
3413 gcd = isl_val_gcd(gcd, m);
3414 if (isl_val_is_one(gcd)) {
3415 isl_val_free(r);
3416 break;
3418 mv = isl_multi_val_set_val(mv, i, r);
3420 res = dim_is_fixed(domain[order[i]].set, depth);
3421 if (res < 0)
3422 break;
3423 if (res)
3424 continue;
3426 if (fixed && i > base) {
3427 isl_val *a, *b;
3428 a = isl_multi_val_get_val(mv, i);
3429 b = isl_multi_val_get_val(mv, base);
3430 if (isl_val_ne(a, b))
3431 fixed = 0;
3432 isl_val_free(a);
3433 isl_val_free(b);
3437 if (res < 0 || !gcd) {
3438 isl_ast_build_free(build);
3439 list = NULL;
3440 } else if (i < n || fixed || isl_val_is_zero(gcd)) {
3441 list = generate_shifted_component_from_list(domain,
3442 order, n, build);
3443 } else {
3444 list = generate_shift_component(domain, order, n, gcd, mv,
3445 build);
3448 isl_val_free(gcd);
3449 isl_multi_val_free(mv);
3451 return list;
3452 error:
3453 isl_ast_build_free(build);
3454 return NULL;
3457 /* Store both "map" itself and its domain in the
3458 * structure pointed to by *next and advance to the next array element.
3460 static int extract_domain(__isl_take isl_map *map, void *user)
3462 struct isl_set_map_pair **next = user;
3464 (*next)->map = isl_map_copy(map);
3465 (*next)->set = isl_map_domain(map);
3466 (*next)++;
3468 return 0;
3471 /* Internal data for any_scheduled_after.
3473 * "depth" is the number of loops that have already been generated
3474 * "group_coscheduled" is a local copy of options->ast_build_group_coscheduled
3475 * "domain" is an array of set-map pairs corresponding to the different
3476 * iteration domains. The set is the schedule domain, i.e., the domain
3477 * of the inverse schedule, while the map is the inverse schedule itself.
3479 struct isl_any_scheduled_after_data {
3480 int depth;
3481 int group_coscheduled;
3482 struct isl_set_map_pair *domain;
3485 /* Is any element of domain "i" scheduled after any element of domain "j"
3486 * (for a common iteration of the first data->depth loops)?
3488 * data->domain[i].set contains the domain of the inverse schedule
3489 * for domain "i", i.e., elements in the schedule domain.
3491 * If data->group_coscheduled is set, then we also return 1 if there
3492 * is any pair of elements in the two domains that are scheduled together.
3494 static int any_scheduled_after(int i, int j, void *user)
3496 struct isl_any_scheduled_after_data *data = user;
3497 int dim = isl_set_dim(data->domain[i].set, isl_dim_set);
3498 int pos;
3500 for (pos = data->depth; pos < dim; ++pos) {
3501 int follows;
3503 follows = isl_set_follows_at(data->domain[i].set,
3504 data->domain[j].set, pos);
3506 if (follows < -1)
3507 return -1;
3508 if (follows > 0)
3509 return 1;
3510 if (follows < 0)
3511 return 0;
3514 return data->group_coscheduled;
3517 /* Look for independent components at the current depth and generate code
3518 * for each component separately. The resulting lists of grafts are
3519 * merged in an attempt to combine grafts with identical guards.
3521 * Code for two domains can be generated separately if all the elements
3522 * of one domain are scheduled before (or together with) all the elements
3523 * of the other domain. We therefore consider the graph with as nodes
3524 * the domains and an edge between two nodes if any element of the first
3525 * node is scheduled after any element of the second node.
3526 * If the ast_build_group_coscheduled is set, then we also add an edge if
3527 * there is any pair of elements in the two domains that are scheduled
3528 * together.
3529 * Code is then generated (by generate_component)
3530 * for each of the strongly connected components in this graph
3531 * in their topological order.
3533 * Since the test is performed on the domain of the inverse schedules of
3534 * the different domains, we precompute these domains and store
3535 * them in data.domain.
3537 static __isl_give isl_ast_graft_list *generate_components(
3538 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3540 int i;
3541 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3542 int n = isl_union_map_n_map(executed);
3543 struct isl_any_scheduled_after_data data;
3544 struct isl_set_map_pair *next;
3545 struct isl_tarjan_graph *g = NULL;
3546 isl_ast_graft_list *list = NULL;
3547 int n_domain = 0;
3549 data.domain = isl_calloc_array(ctx, struct isl_set_map_pair, n);
3550 if (!data.domain)
3551 goto error;
3552 n_domain = n;
3554 next = data.domain;
3555 if (isl_union_map_foreach_map(executed, &extract_domain, &next) < 0)
3556 goto error;
3558 if (!build)
3559 goto error;
3560 data.depth = isl_ast_build_get_depth(build);
3561 data.group_coscheduled = isl_options_get_ast_build_group_coscheduled(ctx);
3562 g = isl_tarjan_graph_init(ctx, n, &any_scheduled_after, &data);
3563 if (!g)
3564 goto error;
3566 list = isl_ast_graft_list_alloc(ctx, 0);
3568 i = 0;
3569 while (list && n) {
3570 isl_ast_graft_list *list_c;
3571 int first = i;
3573 if (g->order[i] == -1)
3574 isl_die(ctx, isl_error_internal, "cannot happen",
3575 goto error);
3576 ++i; --n;
3577 while (g->order[i] != -1) {
3578 ++i; --n;
3581 list_c = generate_component(data.domain,
3582 g->order + first, i - first,
3583 isl_ast_build_copy(build));
3584 list = isl_ast_graft_list_merge(list, list_c, build);
3586 ++i;
3589 if (0)
3590 error: list = isl_ast_graft_list_free(list);
3591 isl_tarjan_graph_free(g);
3592 for (i = 0; i < n_domain; ++i) {
3593 isl_map_free(data.domain[i].map);
3594 isl_set_free(data.domain[i].set);
3596 free(data.domain);
3597 isl_union_map_free(executed);
3598 isl_ast_build_free(build);
3600 return list;
3603 /* Generate code for the next level (and all inner levels).
3605 * If "executed" is empty, i.e., no code needs to be generated,
3606 * then we return an empty list.
3608 * If we have already generated code for all loop levels, then we pass
3609 * control to generate_inner_level.
3611 * If "executed" lives in a single space, i.e., if code needs to be
3612 * generated for a single domain, then there can only be a single
3613 * component and we go directly to generate_shifted_component.
3614 * Otherwise, we call generate_components to detect the components
3615 * and to call generate_component on each of them separately.
3617 static __isl_give isl_ast_graft_list *generate_next_level(
3618 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3620 int depth;
3622 if (!build || !executed)
3623 goto error;
3625 if (isl_union_map_is_empty(executed)) {
3626 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3627 isl_union_map_free(executed);
3628 isl_ast_build_free(build);
3629 return isl_ast_graft_list_alloc(ctx, 0);
3632 depth = isl_ast_build_get_depth(build);
3633 if (depth >= isl_ast_build_dim(build, isl_dim_set))
3634 return generate_inner_level(executed, build);
3636 if (isl_union_map_n_map(executed) == 1)
3637 return generate_shifted_component(executed, build);
3639 return generate_components(executed, build);
3640 error:
3641 isl_union_map_free(executed);
3642 isl_ast_build_free(build);
3643 return NULL;
3646 /* Internal data structure used by isl_ast_build_ast_from_schedule.
3647 * internal, executed and build are the inputs to generate_code.
3648 * list collects the output.
3650 struct isl_generate_code_data {
3651 int internal;
3652 isl_union_map *executed;
3653 isl_ast_build *build;
3655 isl_ast_graft_list *list;
3658 /* Given an inverse schedule in terms of the external build schedule, i.e.,
3660 * [E -> S] -> D
3662 * with E the external build schedule and S the additional schedule "space",
3663 * reformulate the inverse schedule in terms of the internal schedule domain,
3664 * i.e., return
3666 * [I -> S] -> D
3668 * We first obtain a mapping
3670 * I -> E
3672 * take the inverse and the product with S -> S, resulting in
3674 * [I -> S] -> [E -> S]
3676 * Applying the map to the input produces the desired result.
3678 static __isl_give isl_union_map *internal_executed(
3679 __isl_take isl_union_map *executed, __isl_keep isl_space *space,
3680 __isl_keep isl_ast_build *build)
3682 isl_map *id, *proj;
3684 proj = isl_ast_build_get_schedule_map(build);
3685 proj = isl_map_reverse(proj);
3686 space = isl_space_map_from_set(isl_space_copy(space));
3687 id = isl_map_identity(space);
3688 proj = isl_map_product(proj, id);
3689 executed = isl_union_map_apply_domain(executed,
3690 isl_union_map_from_map(proj));
3691 return executed;
3694 /* Generate an AST that visits the elements in the range of data->executed
3695 * in the relative order specified by the corresponding domain element(s)
3696 * for those domain elements that belong to "set".
3697 * Add the result to data->list.
3699 * The caller ensures that "set" is a universe domain.
3700 * "space" is the space of the additional part of the schedule.
3701 * It is equal to the space of "set" if build->domain is parametric.
3702 * Otherwise, it is equal to the range of the wrapped space of "set".
3704 * If the build space is not parametric and if isl_ast_build_ast_from_schedule
3705 * was called from an outside user (data->internal not set), then
3706 * the (inverse) schedule refers to the external build domain and needs to
3707 * be transformed to refer to the internal build domain.
3709 * If the build space is parametric, then we add some of the parameter
3710 * constraints to the executed relation. Adding these constraints
3711 * allows for an earlier detection of conflicts in some cases.
3712 * However, we do not want to divide the executed relation into
3713 * more disjuncts than necessary. We therefore approximate
3714 * the constraints on the parameters by a single disjunct set.
3716 * The build is extended to include the additional part of the schedule.
3717 * If the original build space was not parametric, then the options
3718 * in data->build refer only to the additional part of the schedule
3719 * and they need to be adjusted to refer to the complete AST build
3720 * domain.
3722 * After having adjusted inverse schedule and build, we start generating
3723 * code with the outer loop of the current code generation
3724 * in generate_next_level.
3726 * If the original build space was not parametric, we undo the embedding
3727 * on the resulting isl_ast_node_list so that it can be used within
3728 * the outer AST build.
3730 static int generate_code_in_space(struct isl_generate_code_data *data,
3731 __isl_take isl_set *set, __isl_take isl_space *space)
3733 isl_union_map *executed;
3734 isl_ast_build *build;
3735 isl_ast_graft_list *list;
3736 int embed;
3738 executed = isl_union_map_copy(data->executed);
3739 executed = isl_union_map_intersect_domain(executed,
3740 isl_union_set_from_set(set));
3742 embed = !isl_set_is_params(data->build->domain);
3743 if (embed && !data->internal)
3744 executed = internal_executed(executed, space, data->build);
3745 if (!embed) {
3746 isl_set *domain;
3747 domain = isl_ast_build_get_domain(data->build);
3748 domain = isl_set_from_basic_set(isl_set_simple_hull(domain));
3749 executed = isl_union_map_intersect_params(executed, domain);
3752 build = isl_ast_build_copy(data->build);
3753 build = isl_ast_build_product(build, space);
3755 list = generate_next_level(executed, build);
3757 list = isl_ast_graft_list_unembed(list, embed);
3759 data->list = isl_ast_graft_list_concat(data->list, list);
3761 return 0;
3764 /* Generate an AST that visits the elements in the range of data->executed
3765 * in the relative order specified by the corresponding domain element(s)
3766 * for those domain elements that belong to "set".
3767 * Add the result to data->list.
3769 * The caller ensures that "set" is a universe domain.
3771 * If the build space S is not parametric, then the space of "set"
3772 * need to be a wrapped relation with S as domain. That is, it needs
3773 * to be of the form
3775 * [S -> T]
3777 * Check this property and pass control to generate_code_in_space
3778 * passing along T.
3779 * If the build space is not parametric, then T is the space of "set".
3781 static int generate_code_set(__isl_take isl_set *set, void *user)
3783 struct isl_generate_code_data *data = user;
3784 isl_space *space, *build_space;
3785 int is_domain;
3787 space = isl_set_get_space(set);
3789 if (isl_set_is_params(data->build->domain))
3790 return generate_code_in_space(data, set, space);
3792 build_space = isl_ast_build_get_space(data->build, data->internal);
3793 space = isl_space_unwrap(space);
3794 is_domain = isl_space_is_domain(build_space, space);
3795 isl_space_free(build_space);
3796 space = isl_space_range(space);
3798 if (is_domain < 0)
3799 goto error;
3800 if (!is_domain)
3801 isl_die(isl_set_get_ctx(set), isl_error_invalid,
3802 "invalid nested schedule space", goto error);
3804 return generate_code_in_space(data, set, space);
3805 error:
3806 isl_set_free(set);
3807 isl_space_free(space);
3808 return -1;
3811 /* Generate an AST that visits the elements in the range of "executed"
3812 * in the relative order specified by the corresponding domain element(s).
3814 * "build" is an isl_ast_build that has either been constructed by
3815 * isl_ast_build_from_context or passed to a callback set by
3816 * isl_ast_build_set_create_leaf.
3817 * In the first case, the space of the isl_ast_build is typically
3818 * a parametric space, although this is currently not enforced.
3819 * In the second case, the space is never a parametric space.
3820 * If the space S is not parametric, then the domain space(s) of "executed"
3821 * need to be wrapped relations with S as domain.
3823 * If the domain of "executed" consists of several spaces, then an AST
3824 * is generated for each of them (in arbitrary order) and the results
3825 * are concatenated.
3827 * If "internal" is set, then the domain "S" above refers to the internal
3828 * schedule domain representation. Otherwise, it refers to the external
3829 * representation, as returned by isl_ast_build_get_schedule_space.
3831 * We essentially run over all the spaces in the domain of "executed"
3832 * and call generate_code_set on each of them.
3834 static __isl_give isl_ast_graft_list *generate_code(
3835 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
3836 int internal)
3838 isl_ctx *ctx;
3839 struct isl_generate_code_data data = { 0 };
3840 isl_space *space;
3841 isl_union_set *schedule_domain;
3842 isl_union_map *universe;
3844 if (!build)
3845 goto error;
3846 space = isl_ast_build_get_space(build, 1);
3847 space = isl_space_align_params(space,
3848 isl_union_map_get_space(executed));
3849 space = isl_space_align_params(space,
3850 isl_union_map_get_space(build->options));
3851 build = isl_ast_build_align_params(build, isl_space_copy(space));
3852 executed = isl_union_map_align_params(executed, space);
3853 if (!executed || !build)
3854 goto error;
3856 ctx = isl_ast_build_get_ctx(build);
3858 data.internal = internal;
3859 data.executed = executed;
3860 data.build = build;
3861 data.list = isl_ast_graft_list_alloc(ctx, 0);
3863 universe = isl_union_map_universe(isl_union_map_copy(executed));
3864 schedule_domain = isl_union_map_domain(universe);
3865 if (isl_union_set_foreach_set(schedule_domain, &generate_code_set,
3866 &data) < 0)
3867 data.list = isl_ast_graft_list_free(data.list);
3869 isl_union_set_free(schedule_domain);
3870 isl_union_map_free(executed);
3872 isl_ast_build_free(build);
3873 return data.list;
3874 error:
3875 isl_union_map_free(executed);
3876 isl_ast_build_free(build);
3877 return NULL;
3880 /* Generate an AST that visits the elements in the domain of "schedule"
3881 * in the relative order specified by the corresponding image element(s).
3883 * "build" is an isl_ast_build that has either been constructed by
3884 * isl_ast_build_from_context or passed to a callback set by
3885 * isl_ast_build_set_create_leaf.
3886 * In the first case, the space of the isl_ast_build is typically
3887 * a parametric space, although this is currently not enforced.
3888 * In the second case, the space is never a parametric space.
3889 * If the space S is not parametric, then the range space(s) of "schedule"
3890 * need to be wrapped relations with S as domain.
3892 * If the range of "schedule" consists of several spaces, then an AST
3893 * is generated for each of them (in arbitrary order) and the results
3894 * are concatenated.
3896 * We first initialize the local copies of the relevant options.
3897 * We do this here rather than when the isl_ast_build is created
3898 * because the options may have changed between the construction
3899 * of the isl_ast_build and the call to isl_generate_code.
3901 * The main computation is performed on an inverse schedule (with
3902 * the schedule domain in the domain and the elements to be executed
3903 * in the range) called "executed".
3905 __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
3906 __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
3908 isl_ast_graft_list *list;
3909 isl_ast_node *node;
3910 isl_union_map *executed;
3912 build = isl_ast_build_copy(build);
3913 build = isl_ast_build_set_single_valued(build, 0);
3914 schedule = isl_union_map_coalesce(schedule);
3915 executed = isl_union_map_reverse(schedule);
3916 list = generate_code(executed, isl_ast_build_copy(build), 0);
3917 node = isl_ast_node_from_graft_list(list, build);
3918 isl_ast_build_free(build);
3920 return node;