doc/SubmittingPatches: explain how to submit patch revisions
[isl.git] / isl_ast_codegen.c
blob3626b684dd20de8456ca554ecf5238610c0e062c
1 /*
2 * Copyright 2012-2014 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
8 */
10 #include <limits.h>
11 #include <isl/aff.h>
12 #include <isl/set.h>
13 #include <isl/ilp.h>
14 #include <isl/union_map.h>
15 #include <isl_sort.h>
16 #include <isl_tarjan.h>
17 #include <isl_ast_private.h>
18 #include <isl_ast_build_expr.h>
19 #include <isl_ast_build_private.h>
20 #include <isl_ast_graft_private.h>
22 /* Add the constraint to the list that "user" points to, if it is not
23 * a div constraint.
25 static int collect_constraint(__isl_take isl_constraint *constraint,
26 void *user)
28 isl_constraint_list **list = user;
30 if (isl_constraint_is_div_constraint(constraint))
31 isl_constraint_free(constraint);
32 else
33 *list = isl_constraint_list_add(*list, constraint);
35 return 0;
38 /* Extract the constraints of "bset" (except the div constraints)
39 * and collect them in an isl_constraint_list.
41 static __isl_give isl_constraint_list *isl_constraint_list_from_basic_set(
42 __isl_take isl_basic_set *bset)
44 int n;
45 isl_ctx *ctx;
46 isl_constraint_list *list;
48 if (!bset)
49 return NULL;
51 ctx = isl_basic_set_get_ctx(bset);
53 n = isl_basic_set_n_constraint(bset);
54 list = isl_constraint_list_alloc(ctx, n);
55 if (isl_basic_set_foreach_constraint(bset,
56 &collect_constraint, &list) < 0)
57 list = isl_constraint_list_free(list);
59 isl_basic_set_free(bset);
60 return list;
63 /* Data used in generate_domain.
65 * "build" is the input build.
66 * "list" collects the results.
68 struct isl_generate_domain_data {
69 isl_ast_build *build;
71 isl_ast_graft_list *list;
74 static __isl_give isl_ast_graft_list *generate_next_level(
75 __isl_take isl_union_map *executed,
76 __isl_take isl_ast_build *build);
77 static __isl_give isl_ast_graft_list *generate_code(
78 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
79 int internal);
81 /* Generate an AST for a single domain based on
82 * the (non single valued) inverse schedule "executed".
84 * We extend the schedule with the iteration domain
85 * and continue generating through a call to generate_code.
87 * In particular, if executed has the form
89 * S -> D
91 * then we continue generating code on
93 * [S -> D] -> D
95 * The extended inverse schedule is clearly single valued
96 * ensuring that the nested generate_code will not reach this function,
97 * but will instead create calls to all elements of D that need
98 * to be executed from the current schedule domain.
100 static int generate_non_single_valued(__isl_take isl_map *executed,
101 struct isl_generate_domain_data *data)
103 isl_map *identity;
104 isl_ast_build *build;
105 isl_ast_graft_list *list;
107 build = isl_ast_build_copy(data->build);
109 identity = isl_set_identity(isl_map_range(isl_map_copy(executed)));
110 executed = isl_map_domain_product(executed, identity);
111 build = isl_ast_build_set_single_valued(build, 1);
113 list = generate_code(isl_union_map_from_map(executed), build, 1);
115 data->list = isl_ast_graft_list_concat(data->list, list);
117 return 0;
120 /* Call the at_each_domain callback, if requested by the user,
121 * after recording the current inverse schedule in the build.
123 static __isl_give isl_ast_graft *at_each_domain(__isl_take isl_ast_graft *graft,
124 __isl_keep isl_map *executed, __isl_keep isl_ast_build *build)
126 if (!graft || !build)
127 return isl_ast_graft_free(graft);
128 if (!build->at_each_domain)
129 return graft;
131 build = isl_ast_build_copy(build);
132 build = isl_ast_build_set_executed(build,
133 isl_union_map_from_map(isl_map_copy(executed)));
134 if (!build)
135 return isl_ast_graft_free(graft);
137 graft->node = build->at_each_domain(graft->node,
138 build, build->at_each_domain_user);
139 isl_ast_build_free(build);
141 if (!graft->node)
142 graft = isl_ast_graft_free(graft);
144 return graft;
147 /* Generate an AST for a single domain based on
148 * the inverse schedule "executed".
150 * If there is more than one domain element associated to the current
151 * schedule "time", then we need to continue the generation process
152 * in generate_non_single_valued.
153 * Note that the inverse schedule being single-valued may depend
154 * on constraints that are only available in the original context
155 * domain specified by the user. We therefore first introduce
156 * the constraints from data->build->domain.
157 * On the other hand, we only perform the test after having taken the gist
158 * of the domain as the resulting map is the one from which the call
159 * expression is constructed. Using this map to construct the call
160 * expression usually yields simpler results.
161 * Because we perform the single-valuedness test on the gisted map,
162 * we may in rare cases fail to recognize that the inverse schedule
163 * is single-valued. This becomes problematic if this happens
164 * from the recursive call through generate_non_single_valued
165 * as we would then end up in an infinite recursion.
166 * We therefore check if we are inside a call to generate_non_single_valued
167 * and revert to the ungisted map if the gisted map turns out not to be
168 * single-valued.
170 * Otherwise, we generate a call expression for the single executed
171 * domain element and put a guard around it based on the (simplified)
172 * domain of "executed".
174 * If the user has set an at_each_domain callback, it is called
175 * on the constructed call expression node.
177 static int generate_domain(__isl_take isl_map *executed, void *user)
179 struct isl_generate_domain_data *data = user;
180 isl_ast_graft *graft;
181 isl_ast_graft_list *list;
182 isl_set *guard;
183 isl_map *map;
184 int sv;
186 executed = isl_map_intersect_domain(executed,
187 isl_set_copy(data->build->domain));
189 executed = isl_map_coalesce(executed);
190 map = isl_map_copy(executed);
191 map = isl_ast_build_compute_gist_map_domain(data->build, map);
192 sv = isl_map_is_single_valued(map);
193 if (sv < 0)
194 goto error;
195 if (!sv) {
196 isl_map_free(map);
197 if (data->build->single_valued)
198 map = isl_map_copy(executed);
199 else
200 return generate_non_single_valued(executed, data);
202 guard = isl_map_domain(isl_map_copy(map));
203 guard = isl_set_coalesce(guard);
204 guard = isl_ast_build_compute_gist(data->build, guard);
205 graft = isl_ast_graft_alloc_domain(map, data->build);
206 graft = at_each_domain(graft, executed, data->build);
208 isl_map_free(executed);
209 graft = isl_ast_graft_add_guard(graft, guard, data->build);
211 list = isl_ast_graft_list_from_ast_graft(graft);
212 data->list = isl_ast_graft_list_concat(data->list, list);
214 return 0;
215 error:
216 isl_map_free(map);
217 isl_map_free(executed);
218 return -1;
221 /* Call build->create_leaf to a create "leaf" node in the AST,
222 * encapsulate the result in an isl_ast_graft and return the result
223 * as a 1-element list.
225 * Note that the node returned by the user may be an entire tree.
227 * Before we pass control to the user, we first clear some information
228 * from the build that is (presumbably) only meaningful
229 * for the current code generation.
230 * This includes the create_leaf callback itself, so we make a copy
231 * of the build first.
233 static __isl_give isl_ast_graft_list *call_create_leaf(
234 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
236 isl_ast_node *node;
237 isl_ast_graft *graft;
238 isl_ast_build *user_build;
240 user_build = isl_ast_build_copy(build);
241 user_build = isl_ast_build_set_executed(user_build, executed);
242 user_build = isl_ast_build_clear_local_info(user_build);
243 if (!user_build)
244 node = NULL;
245 else
246 node = build->create_leaf(user_build, build->create_leaf_user);
247 graft = isl_ast_graft_alloc(node, build);
248 isl_ast_build_free(build);
249 return isl_ast_graft_list_from_ast_graft(graft);
252 /* Generate an AST after having handled the complete schedule
253 * of this call to the code generator.
255 * If the user has specified a create_leaf callback, control
256 * is passed to the user in call_create_leaf.
258 * Otherwise, we generate one or more calls for each individual
259 * domain in generate_domain.
261 static __isl_give isl_ast_graft_list *generate_inner_level(
262 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
264 isl_ctx *ctx;
265 struct isl_generate_domain_data data = { build };
267 if (!build || !executed)
268 goto error;
270 if (build->create_leaf)
271 return call_create_leaf(executed, build);
273 ctx = isl_union_map_get_ctx(executed);
274 data.list = isl_ast_graft_list_alloc(ctx, 0);
275 if (isl_union_map_foreach_map(executed, &generate_domain, &data) < 0)
276 data.list = isl_ast_graft_list_free(data.list);
278 if (0)
279 error: data.list = NULL;
280 isl_ast_build_free(build);
281 isl_union_map_free(executed);
282 return data.list;
285 /* Call the before_each_for callback, if requested by the user.
287 static __isl_give isl_ast_node *before_each_for(__isl_take isl_ast_node *node,
288 __isl_keep isl_ast_build *build)
290 isl_id *id;
292 if (!node || !build)
293 return isl_ast_node_free(node);
294 if (!build->before_each_for)
295 return node;
296 id = build->before_each_for(build, build->before_each_for_user);
297 node = isl_ast_node_set_annotation(node, id);
298 return node;
301 /* Call the after_each_for callback, if requested by the user.
303 static __isl_give isl_ast_graft *after_each_for(__isl_keep isl_ast_graft *graft,
304 __isl_keep isl_ast_build *build)
306 if (!graft || !build)
307 return isl_ast_graft_free(graft);
308 if (!build->after_each_for)
309 return graft;
310 graft->node = build->after_each_for(graft->node, build,
311 build->after_each_for_user);
312 if (!graft->node)
313 return isl_ast_graft_free(graft);
314 return graft;
317 /* Plug in all the know values of the current and outer dimensions
318 * in the domain of "executed". In principle, we only need to plug
319 * in the known value of the current dimension since the values of
320 * outer dimensions have been plugged in already.
321 * However, it turns out to be easier to just plug in all known values.
323 static __isl_give isl_union_map *plug_in_values(
324 __isl_take isl_union_map *executed, __isl_keep isl_ast_build *build)
326 return isl_ast_build_substitute_values_union_map_domain(build,
327 executed);
330 /* Check if the constraint "c" is a lower bound on dimension "pos",
331 * an upper bound, or independent of dimension "pos".
333 static int constraint_type(isl_constraint *c, int pos)
335 if (isl_constraint_is_lower_bound(c, isl_dim_set, pos))
336 return 1;
337 if (isl_constraint_is_upper_bound(c, isl_dim_set, pos))
338 return 2;
339 return 0;
342 /* Compare the types of the constraints "a" and "b",
343 * resulting in constraints that are independent of "depth"
344 * to be sorted before the lower bounds on "depth", which in
345 * turn are sorted before the upper bounds on "depth".
347 static int cmp_constraint(__isl_keep isl_constraint *a,
348 __isl_keep isl_constraint *b, void *user)
350 int *depth = user;
351 int t1 = constraint_type(a, *depth);
352 int t2 = constraint_type(b, *depth);
354 return t1 - t2;
357 /* Extract a lower bound on dimension "pos" from constraint "c".
359 * If the constraint is of the form
361 * a x + f(...) >= 0
363 * then we essentially return
365 * l = ceil(-f(...)/a)
367 * However, if the current dimension is strided, then we need to make
368 * sure that the lower bound we construct is of the form
370 * f + s a
372 * with f the offset and s the stride.
373 * We therefore compute
375 * f + s * ceil((l - f)/s)
377 static __isl_give isl_aff *lower_bound(__isl_keep isl_constraint *c,
378 int pos, __isl_keep isl_ast_build *build)
380 isl_aff *aff;
382 aff = isl_constraint_get_bound(c, isl_dim_set, pos);
383 aff = isl_aff_ceil(aff);
385 if (isl_ast_build_has_stride(build, pos)) {
386 isl_aff *offset;
387 isl_val *stride;
389 offset = isl_ast_build_get_offset(build, pos);
390 stride = isl_ast_build_get_stride(build, pos);
392 aff = isl_aff_sub(aff, isl_aff_copy(offset));
393 aff = isl_aff_scale_down_val(aff, isl_val_copy(stride));
394 aff = isl_aff_ceil(aff);
395 aff = isl_aff_scale_val(aff, stride);
396 aff = isl_aff_add(aff, offset);
399 aff = isl_ast_build_compute_gist_aff(build, aff);
401 return aff;
404 /* Return the exact lower bound (or upper bound if "upper" is set)
405 * of "domain" as a piecewise affine expression.
407 * If we are computing a lower bound (of a strided dimension), then
408 * we need to make sure it is of the form
410 * f + s a
412 * where f is the offset and s is the stride.
413 * We therefore need to include the stride constraint before computing
414 * the minimum.
416 static __isl_give isl_pw_aff *exact_bound(__isl_keep isl_set *domain,
417 __isl_keep isl_ast_build *build, int upper)
419 isl_set *stride;
420 isl_map *it_map;
421 isl_pw_aff *pa;
422 isl_pw_multi_aff *pma;
424 domain = isl_set_copy(domain);
425 if (!upper) {
426 stride = isl_ast_build_get_stride_constraint(build);
427 domain = isl_set_intersect(domain, stride);
429 it_map = isl_ast_build_map_to_iterator(build, domain);
430 if (upper)
431 pma = isl_map_lexmax_pw_multi_aff(it_map);
432 else
433 pma = isl_map_lexmin_pw_multi_aff(it_map);
434 pa = isl_pw_multi_aff_get_pw_aff(pma, 0);
435 isl_pw_multi_aff_free(pma);
436 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
437 pa = isl_pw_aff_coalesce(pa);
439 return pa;
442 /* Extract a lower bound on dimension "pos" from each constraint
443 * in "constraints" and return the list of lower bounds.
444 * If "constraints" has zero elements, then we extract a lower bound
445 * from "domain" instead.
447 static __isl_give isl_pw_aff_list *lower_bounds(
448 __isl_keep isl_constraint_list *constraints, int pos,
449 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
451 isl_ctx *ctx;
452 isl_pw_aff_list *list;
453 int i, n;
455 if (!build)
456 return NULL;
458 n = isl_constraint_list_n_constraint(constraints);
459 if (n == 0) {
460 isl_pw_aff *pa;
461 pa = exact_bound(domain, build, 0);
462 return isl_pw_aff_list_from_pw_aff(pa);
465 ctx = isl_ast_build_get_ctx(build);
466 list = isl_pw_aff_list_alloc(ctx,n);
468 for (i = 0; i < n; ++i) {
469 isl_aff *aff;
470 isl_constraint *c;
472 c = isl_constraint_list_get_constraint(constraints, i);
473 aff = lower_bound(c, pos, build);
474 isl_constraint_free(c);
475 list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
478 return list;
481 /* Extract an upper bound on dimension "pos" from each constraint
482 * in "constraints" and return the list of upper bounds.
483 * If "constraints" has zero elements, then we extract an upper bound
484 * from "domain" instead.
486 static __isl_give isl_pw_aff_list *upper_bounds(
487 __isl_keep isl_constraint_list *constraints, int pos,
488 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
490 isl_ctx *ctx;
491 isl_pw_aff_list *list;
492 int i, n;
494 n = isl_constraint_list_n_constraint(constraints);
495 if (n == 0) {
496 isl_pw_aff *pa;
497 pa = exact_bound(domain, build, 1);
498 return isl_pw_aff_list_from_pw_aff(pa);
501 ctx = isl_ast_build_get_ctx(build);
502 list = isl_pw_aff_list_alloc(ctx,n);
504 for (i = 0; i < n; ++i) {
505 isl_aff *aff;
506 isl_constraint *c;
508 c = isl_constraint_list_get_constraint(constraints, i);
509 aff = isl_constraint_get_bound(c, isl_dim_set, pos);
510 isl_constraint_free(c);
511 aff = isl_aff_floor(aff);
512 list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
515 return list;
518 /* Callback for sorting the isl_pw_aff_list passed to reduce_list.
520 static int reduce_list_cmp(__isl_keep isl_pw_aff *a, __isl_keep isl_pw_aff *b,
521 void *user)
523 return isl_pw_aff_plain_cmp(a, b);
526 /* Return an isl_ast_expr that performs the reduction of type "type"
527 * on AST expressions corresponding to the elements in "list".
529 * The list is assumed to contain at least one element.
530 * If the list contains exactly one element, then the returned isl_ast_expr
531 * simply computes that affine expression.
532 * If the list contains more than one element, then we sort it
533 * using a fairly abitrary but hopefully reasonably stable order.
535 static __isl_give isl_ast_expr *reduce_list(enum isl_ast_op_type type,
536 __isl_keep isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
538 int i, n;
539 isl_ctx *ctx;
540 isl_ast_expr *expr;
542 if (!list)
543 return NULL;
545 n = isl_pw_aff_list_n_pw_aff(list);
547 if (n == 1)
548 return isl_ast_build_expr_from_pw_aff_internal(build,
549 isl_pw_aff_list_get_pw_aff(list, 0));
551 ctx = isl_pw_aff_list_get_ctx(list);
552 expr = isl_ast_expr_alloc_op(ctx, type, n);
553 if (!expr)
554 return NULL;
556 list = isl_pw_aff_list_copy(list);
557 list = isl_pw_aff_list_sort(list, &reduce_list_cmp, NULL);
558 if (!list)
559 return isl_ast_expr_free(expr);
561 for (i = 0; i < n; ++i) {
562 isl_ast_expr *expr_i;
564 expr_i = isl_ast_build_expr_from_pw_aff_internal(build,
565 isl_pw_aff_list_get_pw_aff(list, i));
566 if (!expr_i)
567 goto error;
568 expr->u.op.args[i] = expr_i;
571 isl_pw_aff_list_free(list);
572 return expr;
573 error:
574 isl_pw_aff_list_free(list);
575 isl_ast_expr_free(expr);
576 return NULL;
579 /* Add a guard to "graft" based on "bound" in the case of a degenerate
580 * level (including the special case of an eliminated level).
582 * We eliminate the current dimension, simplify the result in the current
583 * build and add the result as guards to the graft.
585 * Note that we cannot simply drop the constraints on the current dimension
586 * even in the eliminated case, because the single affine expression may
587 * not be explicitly available in "bounds". Moreover, the single affine
588 * expression may only be defined on a subset of the build domain,
589 * so we do in some cases need to insert a guard even in the eliminated case.
591 static __isl_give isl_ast_graft *add_degenerate_guard(
592 __isl_take isl_ast_graft *graft, __isl_keep isl_basic_set *bounds,
593 __isl_keep isl_ast_build *build)
595 int depth;
596 isl_set *dom;
598 depth = isl_ast_build_get_depth(build);
600 dom = isl_set_from_basic_set(isl_basic_set_copy(bounds));
601 if (isl_ast_build_has_stride(build, depth)) {
602 isl_set *stride;
604 stride = isl_ast_build_get_stride_constraint(build);
605 dom = isl_set_intersect(dom, stride);
607 dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
608 dom = isl_ast_build_compute_gist(build, dom);
610 graft = isl_ast_graft_add_guard(graft, dom, build);
612 return graft;
615 /* Update "graft" based on "bounds" for the eliminated case.
617 * In the eliminated case, no for node is created, so we only need
618 * to check if "bounds" imply any guards that need to be inserted.
620 static __isl_give isl_ast_graft *refine_eliminated(
621 __isl_take isl_ast_graft *graft, __isl_keep isl_basic_set *bounds,
622 __isl_keep isl_ast_build *build)
624 return add_degenerate_guard(graft, bounds, build);
627 /* Update "graft" based on "bounds" and "sub_build" for the degenerate case.
629 * "build" is the build in which graft->node was created
630 * "sub_build" contains information about the current level itself,
631 * including the single value attained.
633 * We first set the initialization part of the for loop to the single
634 * value attained by the current dimension.
635 * The increment and condition are not strictly needed as the are known
636 * to be "1" and "iterator <= value" respectively.
637 * Then we set the size of the iterator and
638 * check if "bounds" imply any guards that need to be inserted.
640 static __isl_give isl_ast_graft *refine_degenerate(
641 __isl_take isl_ast_graft *graft, __isl_keep isl_basic_set *bounds,
642 __isl_keep isl_ast_build *build,
643 __isl_keep isl_ast_build *sub_build)
645 isl_pw_aff *value;
647 if (!graft || !sub_build)
648 return isl_ast_graft_free(graft);
650 value = isl_pw_aff_copy(sub_build->value);
652 graft->node->u.f.init = isl_ast_build_expr_from_pw_aff_internal(build,
653 value);
654 if (!graft->node->u.f.init)
655 return isl_ast_graft_free(graft);
657 graft = add_degenerate_guard(graft, bounds, build);
659 return graft;
662 /* Return the intersection of constraints in "list" as a set.
664 static __isl_give isl_set *intersect_constraints(
665 __isl_keep isl_constraint_list *list)
667 int i, n;
668 isl_basic_set *bset;
670 n = isl_constraint_list_n_constraint(list);
671 if (n < 1)
672 isl_die(isl_constraint_list_get_ctx(list), isl_error_internal,
673 "expecting at least one constraint", return NULL);
675 bset = isl_basic_set_from_constraint(
676 isl_constraint_list_get_constraint(list, 0));
677 for (i = 1; i < n; ++i) {
678 isl_basic_set *bset_i;
680 bset_i = isl_basic_set_from_constraint(
681 isl_constraint_list_get_constraint(list, i));
682 bset = isl_basic_set_intersect(bset, bset_i);
685 return isl_set_from_basic_set(bset);
688 /* Compute the constraints on the outer dimensions enforced by
689 * graft->node and add those constraints to graft->enforced,
690 * in case the upper bound is expressed as a set "upper".
692 * In particular, if l(...) is a lower bound in "lower", and
694 * -a i + f(...) >= 0 or a i <= f(...)
696 * is an upper bound ocnstraint on the current dimension i,
697 * then the for loop enforces the constraint
699 * -a l(...) + f(...) >= 0 or a l(...) <= f(...)
701 * We therefore simply take each lower bound in turn, plug it into
702 * the upper bounds and compute the intersection over all lower bounds.
704 * If a lower bound is a rational expression, then
705 * isl_basic_set_preimage_multi_aff will force this rational
706 * expression to have only integer values. However, the loop
707 * itself does not enforce this integrality constraint. We therefore
708 * use the ceil of the lower bounds instead of the lower bounds themselves.
709 * Other constraints will make sure that the for loop is only executed
710 * when each of the lower bounds attains an integral value.
711 * In particular, potentially rational values only occur in
712 * lower_bound if the offset is a (seemingly) rational expression,
713 * but then outer conditions will make sure that this rational expression
714 * only attains integer values.
716 static __isl_give isl_ast_graft *set_enforced_from_set(
717 __isl_take isl_ast_graft *graft,
718 __isl_keep isl_pw_aff_list *lower, int pos, __isl_keep isl_set *upper)
720 isl_space *space;
721 isl_basic_set *enforced;
722 isl_pw_multi_aff *pma;
723 int i, n;
725 if (!graft || !lower)
726 return isl_ast_graft_free(graft);
728 space = isl_set_get_space(upper);
729 enforced = isl_basic_set_universe(isl_space_copy(space));
731 space = isl_space_map_from_set(space);
732 pma = isl_pw_multi_aff_identity(space);
734 n = isl_pw_aff_list_n_pw_aff(lower);
735 for (i = 0; i < n; ++i) {
736 isl_pw_aff *pa;
737 isl_set *enforced_i;
738 isl_basic_set *hull;
739 isl_pw_multi_aff *pma_i;
741 pa = isl_pw_aff_list_get_pw_aff(lower, i);
742 pa = isl_pw_aff_ceil(pa);
743 pma_i = isl_pw_multi_aff_copy(pma);
744 pma_i = isl_pw_multi_aff_set_pw_aff(pma_i, pos, pa);
745 enforced_i = isl_set_copy(upper);
746 enforced_i = isl_set_preimage_pw_multi_aff(enforced_i, pma_i);
747 hull = isl_set_simple_hull(enforced_i);
748 enforced = isl_basic_set_intersect(enforced, hull);
751 isl_pw_multi_aff_free(pma);
753 graft = isl_ast_graft_enforce(graft, enforced);
755 return graft;
758 /* Compute the constraints on the outer dimensions enforced by
759 * graft->node and add those constraints to graft->enforced,
760 * in case the upper bound is expressed as
761 * a list of affine expressions "upper".
763 * The enforced condition is that each lower bound expression is less
764 * than or equal to each upper bound expression.
766 static __isl_give isl_ast_graft *set_enforced_from_list(
767 __isl_take isl_ast_graft *graft,
768 __isl_keep isl_pw_aff_list *lower, __isl_keep isl_pw_aff_list *upper)
770 isl_set *cond;
771 isl_basic_set *enforced;
773 lower = isl_pw_aff_list_copy(lower);
774 upper = isl_pw_aff_list_copy(upper);
775 cond = isl_pw_aff_list_le_set(lower, upper);
776 enforced = isl_set_simple_hull(cond);
777 graft = isl_ast_graft_enforce(graft, enforced);
779 return graft;
782 /* Does "aff" have a negative constant term?
784 static int aff_constant_is_negative(__isl_take isl_set *set,
785 __isl_take isl_aff *aff, void *user)
787 int *neg = user;
788 isl_val *v;
790 v = isl_aff_get_constant_val(aff);
791 *neg = isl_val_is_neg(v);
792 isl_val_free(v);
793 isl_set_free(set);
794 isl_aff_free(aff);
796 return *neg ? 0 : -1;
799 /* Does "pa" have a negative constant term over its entire domain?
801 static int pw_aff_constant_is_negative(__isl_take isl_pw_aff *pa, void *user)
803 int r;
804 int *neg = user;
806 r = isl_pw_aff_foreach_piece(pa, &aff_constant_is_negative, user);
807 isl_pw_aff_free(pa);
809 return *neg ? 0 : -1;
812 /* Does each element in "list" have a negative constant term?
814 * The callback terminates the iteration as soon an element has been
815 * found that does not have a negative constant term.
817 static int list_constant_is_negative(__isl_keep isl_pw_aff_list *list)
819 int neg = 1;
821 if (isl_pw_aff_list_foreach(list,
822 &pw_aff_constant_is_negative, &neg) < 0 && neg)
823 return -1;
825 return neg;
828 /* Add 1 to each of the elements in "list", where each of these elements
829 * is defined over the internal schedule space of "build".
831 static __isl_give isl_pw_aff_list *list_add_one(
832 __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
834 int i, n;
835 isl_space *space;
836 isl_aff *aff;
837 isl_pw_aff *one;
839 space = isl_ast_build_get_space(build, 1);
840 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
841 aff = isl_aff_add_constant_si(aff, 1);
842 one = isl_pw_aff_from_aff(aff);
844 n = isl_pw_aff_list_n_pw_aff(list);
845 for (i = 0; i < n; ++i) {
846 isl_pw_aff *pa;
847 pa = isl_pw_aff_list_get_pw_aff(list, i);
848 pa = isl_pw_aff_add(pa, isl_pw_aff_copy(one));
849 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
852 isl_pw_aff_free(one);
854 return list;
857 /* Set the condition part of the for node graft->node in case
858 * the upper bound is represented as a list of piecewise affine expressions.
860 * In particular, set the condition to
862 * iterator <= min(list of upper bounds)
864 * If each of the upper bounds has a negative constant term, then
865 * set the condition to
867 * iterator < min(list of (upper bound + 1)s)
870 static __isl_give isl_ast_graft *set_for_cond_from_list(
871 __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *list,
872 __isl_keep isl_ast_build *build)
874 int neg;
875 isl_ast_expr *bound, *iterator, *cond;
876 enum isl_ast_op_type type = isl_ast_op_le;
878 if (!graft || !list)
879 return isl_ast_graft_free(graft);
881 neg = list_constant_is_negative(list);
882 if (neg < 0)
883 return isl_ast_graft_free(graft);
884 list = isl_pw_aff_list_copy(list);
885 if (neg) {
886 list = list_add_one(list, build);
887 type = isl_ast_op_lt;
890 bound = reduce_list(isl_ast_op_min, list, build);
891 iterator = isl_ast_expr_copy(graft->node->u.f.iterator);
892 cond = isl_ast_expr_alloc_binary(type, iterator, bound);
893 graft->node->u.f.cond = cond;
895 isl_pw_aff_list_free(list);
896 if (!graft->node->u.f.cond)
897 return isl_ast_graft_free(graft);
898 return graft;
901 /* Set the condition part of the for node graft->node in case
902 * the upper bound is represented as a set.
904 static __isl_give isl_ast_graft *set_for_cond_from_set(
905 __isl_take isl_ast_graft *graft, __isl_keep isl_set *set,
906 __isl_keep isl_ast_build *build)
908 isl_ast_expr *cond;
910 if (!graft)
911 return NULL;
913 cond = isl_ast_build_expr_from_set(build, isl_set_copy(set));
914 graft->node->u.f.cond = cond;
915 if (!graft->node->u.f.cond)
916 return isl_ast_graft_free(graft);
917 return graft;
920 /* Construct an isl_ast_expr for the increment (i.e., stride) of
921 * the current dimension.
923 static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
925 int depth;
926 isl_val *v;
927 isl_ctx *ctx;
929 if (!build)
930 return NULL;
931 ctx = isl_ast_build_get_ctx(build);
932 depth = isl_ast_build_get_depth(build);
934 if (!isl_ast_build_has_stride(build, depth))
935 return isl_ast_expr_alloc_int_si(ctx, 1);
937 v = isl_ast_build_get_stride(build, depth);
938 return isl_ast_expr_from_val(v);
941 /* Should we express the loop condition as
943 * iterator <= min(list of upper bounds)
945 * or as a conjunction of constraints?
947 * The first is constructed from a list of upper bounds.
948 * The second is constructed from a set.
950 * If there are no upper bounds in "constraints", then this could mean
951 * that "domain" simply doesn't have an upper bound or that we didn't
952 * pick any upper bound. In the first case, we want to generate the
953 * loop condition as a(n empty) conjunction of constraints
954 * In the second case, we will compute
955 * a single upper bound from "domain" and so we use the list form.
957 * If there are upper bounds in "constraints",
958 * then we use the list form iff the atomic_upper_bound option is set.
960 static int use_upper_bound_list(isl_ctx *ctx, int n_upper,
961 __isl_keep isl_set *domain, int depth)
963 if (n_upper > 0)
964 return isl_options_get_ast_build_atomic_upper_bound(ctx);
965 else
966 return isl_set_dim_has_upper_bound(domain, isl_dim_set, depth);
969 /* Fill in the expressions of the for node in graft->node.
971 * In particular,
972 * - set the initialization part of the loop to the maximum of the lower bounds
973 * - set the size of the iterator based on the values attained by the iterator
974 * - extract the increment from the stride of the current dimension
975 * - construct the for condition either based on a list of upper bounds
976 * or on a set of upper bound constraints.
978 static __isl_give isl_ast_graft *set_for_node_expressions(
979 __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *lower,
980 int use_list, __isl_keep isl_pw_aff_list *upper_list,
981 __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build)
983 isl_ast_node *node;
985 if (!graft)
986 return NULL;
988 build = isl_ast_build_copy(build);
989 build = isl_ast_build_set_enforced(build,
990 isl_ast_graft_get_enforced(graft));
992 node = graft->node;
993 node->u.f.init = reduce_list(isl_ast_op_max, lower, build);
994 node->u.f.inc = for_inc(build);
996 if (use_list)
997 graft = set_for_cond_from_list(graft, upper_list, build);
998 else
999 graft = set_for_cond_from_set(graft, upper_set, build);
1001 isl_ast_build_free(build);
1003 if (!node->u.f.iterator || !node->u.f.init ||
1004 !node->u.f.cond || !node->u.f.inc)
1005 return isl_ast_graft_free(graft);
1007 return graft;
1010 /* Update "graft" based on "bounds" and "domain" for the generic,
1011 * non-degenerate, case.
1013 * "c_lower" and "c_upper" contain the lower and upper bounds
1014 * that the loop node should express.
1015 * "domain" is the subset of the intersection of the constraints
1016 * for which some code is executed.
1018 * There may be zero lower bounds or zero upper bounds in "constraints"
1019 * in case the list of constraints was created
1020 * based on the atomic option or based on separation with explicit bounds.
1021 * In that case, we use "domain" to derive lower and/or upper bounds.
1023 * We first compute a list of one or more lower bounds.
1025 * Then we decide if we want to express the condition as
1027 * iterator <= min(list of upper bounds)
1029 * or as a conjunction of constraints.
1031 * The set of enforced constraints is then computed either based on
1032 * a list of upper bounds or on a set of upper bound constraints.
1033 * We do not compute any enforced constraints if we were forced
1034 * to compute a lower or upper bound using exact_bound. The domains
1035 * of the resulting expressions may imply some bounds on outer dimensions
1036 * that we do not want to appear in the enforced constraints since
1037 * they are not actually enforced by the corresponding code.
1039 * Finally, we fill in the expressions of the for node.
1041 static __isl_give isl_ast_graft *refine_generic_bounds(
1042 __isl_take isl_ast_graft *graft,
1043 __isl_take isl_constraint_list *c_lower,
1044 __isl_take isl_constraint_list *c_upper,
1045 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1047 int depth;
1048 isl_ctx *ctx;
1049 isl_pw_aff_list *lower;
1050 int use_list;
1051 isl_set *upper_set = NULL;
1052 isl_pw_aff_list *upper_list = NULL;
1053 int n_lower, n_upper;
1055 if (!graft || !c_lower || !c_upper || !build)
1056 goto error;
1058 depth = isl_ast_build_get_depth(build);
1059 ctx = isl_ast_graft_get_ctx(graft);
1061 n_lower = isl_constraint_list_n_constraint(c_lower);
1062 n_upper = isl_constraint_list_n_constraint(c_upper);
1064 use_list = use_upper_bound_list(ctx, n_upper, domain, depth);
1066 lower = lower_bounds(c_lower, depth, domain, build);
1068 if (use_list)
1069 upper_list = upper_bounds(c_upper, depth, domain, build);
1070 else if (n_upper > 0)
1071 upper_set = intersect_constraints(c_upper);
1072 else
1073 upper_set = isl_set_universe(isl_set_get_space(domain));
1075 if (n_lower == 0 || n_upper == 0)
1077 else if (use_list)
1078 graft = set_enforced_from_list(graft, lower, upper_list);
1079 else
1080 graft = set_enforced_from_set(graft, lower, depth, upper_set);
1082 graft = set_for_node_expressions(graft, lower, use_list, upper_list,
1083 upper_set, build);
1085 isl_pw_aff_list_free(lower);
1086 isl_pw_aff_list_free(upper_list);
1087 isl_set_free(upper_set);
1088 isl_constraint_list_free(c_lower);
1089 isl_constraint_list_free(c_upper);
1091 return graft;
1092 error:
1093 isl_constraint_list_free(c_lower);
1094 isl_constraint_list_free(c_upper);
1095 return isl_ast_graft_free(graft);
1098 /* Internal data structure used inside count_constraints to keep
1099 * track of the number of constraints that are independent of dimension "pos",
1100 * the lower bounds in "pos" and the upper bounds in "pos".
1102 struct isl_ast_count_constraints_data {
1103 int pos;
1105 int n_indep;
1106 int n_lower;
1107 int n_upper;
1110 /* Increment data->n_indep, data->lower or data->upper depending
1111 * on whether "c" is independenct of dimensions data->pos,
1112 * a lower bound or an upper bound.
1114 static int count_constraints(__isl_take isl_constraint *c, void *user)
1116 struct isl_ast_count_constraints_data *data = user;
1118 if (isl_constraint_is_lower_bound(c, isl_dim_set, data->pos))
1119 data->n_lower++;
1120 else if (isl_constraint_is_upper_bound(c, isl_dim_set, data->pos))
1121 data->n_upper++;
1122 else
1123 data->n_indep++;
1125 isl_constraint_free(c);
1127 return 0;
1130 /* Update "graft" based on "bounds" and "domain" for the generic,
1131 * non-degenerate, case.
1133 * "list" respresent the list of bounds that need to be encoded by
1134 * the for loop (or a guard around the for loop).
1135 * "domain" is the subset of the intersection of the constraints
1136 * for which some code is executed.
1137 * "build" is the build in which graft->node was created.
1139 * We separate lower bounds, upper bounds and constraints that
1140 * are independent of the loop iterator.
1142 * The actual for loop bounds are generated in refine_generic_bounds.
1143 * If there are any constraints that are independent of the loop iterator,
1144 * we need to put a guard around the for loop (which may get hoisted up
1145 * to higher levels) and we call refine_generic_bounds in a build
1146 * where this guard is enforced.
1148 static __isl_give isl_ast_graft *refine_generic_split(
1149 __isl_take isl_ast_graft *graft, __isl_take isl_constraint_list *list,
1150 __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1152 isl_ast_build *for_build;
1153 isl_set *guard;
1154 struct isl_ast_count_constraints_data data;
1155 isl_constraint_list *lower;
1156 isl_constraint_list *upper;
1158 if (!list)
1159 return isl_ast_graft_free(graft);
1161 data.pos = isl_ast_build_get_depth(build);
1163 list = isl_constraint_list_sort(list, &cmp_constraint, &data.pos);
1164 if (!list)
1165 return isl_ast_graft_free(graft);
1167 data.n_indep = data.n_lower = data.n_upper = 0;
1168 if (isl_constraint_list_foreach(list, &count_constraints, &data) < 0) {
1169 isl_constraint_list_free(list);
1170 return isl_ast_graft_free(graft);
1173 lower = isl_constraint_list_copy(list);
1174 lower = isl_constraint_list_drop(lower, 0, data.n_indep);
1175 upper = isl_constraint_list_copy(lower);
1176 lower = isl_constraint_list_drop(lower, data.n_lower, data.n_upper);
1177 upper = isl_constraint_list_drop(upper, 0, data.n_lower);
1179 if (data.n_indep == 0) {
1180 isl_constraint_list_free(list);
1181 return refine_generic_bounds(graft, lower, upper,
1182 domain, build);
1185 list = isl_constraint_list_drop(list, data.n_indep,
1186 data.n_lower + data.n_upper);
1187 guard = intersect_constraints(list);
1188 isl_constraint_list_free(list);
1190 for_build = isl_ast_build_copy(build);
1191 for_build = isl_ast_build_restrict_pending(for_build,
1192 isl_set_copy(guard));
1193 graft = refine_generic_bounds(graft, lower, upper, domain, for_build);
1194 isl_ast_build_free(for_build);
1196 graft = isl_ast_graft_add_guard(graft, guard, build);
1198 return graft;
1201 /* Add the guard implied by the current stride constraint (if any),
1202 * but not (necessarily) enforced by the generated AST to "graft".
1204 static __isl_give isl_ast_graft *add_stride_guard(
1205 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
1207 int depth;
1208 isl_set *dom;
1210 depth = isl_ast_build_get_depth(build);
1211 if (!isl_ast_build_has_stride(build, depth))
1212 return graft;
1214 dom = isl_ast_build_get_stride_constraint(build);
1215 dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
1216 dom = isl_ast_build_compute_gist(build, dom);
1218 graft = isl_ast_graft_add_guard(graft, dom, build);
1220 return graft;
1223 /* Update "graft" based on "bounds" and "domain" for the generic,
1224 * non-degenerate, case.
1226 * "bounds" respresent the bounds that need to be encoded by
1227 * the for loop (or a guard around the for loop).
1228 * "domain" is the subset of "bounds" for which some code is executed.
1229 * "build" is the build in which graft->node was created.
1231 * We break up "bounds" into a list of constraints and continue with
1232 * refine_generic_split.
1234 static __isl_give isl_ast_graft *refine_generic(
1235 __isl_take isl_ast_graft *graft,
1236 __isl_keep isl_basic_set *bounds, __isl_keep isl_set *domain,
1237 __isl_keep isl_ast_build *build)
1239 isl_constraint_list *list;
1241 if (!build || !graft)
1242 return isl_ast_graft_free(graft);
1244 bounds = isl_basic_set_copy(bounds);
1245 bounds = isl_ast_build_compute_gist_basic_set(build, bounds);
1246 list = isl_constraint_list_from_basic_set(bounds);
1248 graft = refine_generic_split(graft, list, domain, build);
1249 graft = add_stride_guard(graft, build);
1251 return graft;
1254 /* Create a for node for the current level.
1256 * Mark the for node degenerate if "degenerate" is set.
1258 static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build,
1259 int degenerate)
1261 int depth;
1262 isl_id *id;
1263 isl_ast_node *node;
1265 if (!build)
1266 return NULL;
1268 depth = isl_ast_build_get_depth(build);
1269 id = isl_ast_build_get_iterator_id(build, depth);
1270 node = isl_ast_node_alloc_for(id);
1271 if (degenerate)
1272 node = isl_ast_node_for_mark_degenerate(node);
1274 return node;
1277 /* Create an AST node for the current dimension based on
1278 * the schedule domain "bounds" and return the node encapsulated
1279 * in an isl_ast_graft.
1281 * "executed" is the current inverse schedule, taking into account
1282 * the bounds in "bounds"
1283 * "domain" is the domain of "executed", with inner dimensions projected out.
1284 * It may be a strict subset of "bounds" in case "bounds" was created
1285 * based on the atomic option or based on separation with explicit bounds.
1287 * "domain" may satisfy additional equalities that result
1288 * from intersecting "executed" with "bounds" in add_node.
1289 * It may also satisfy some global constraints that were dropped out because
1290 * we performed separation with explicit bounds.
1291 * The very first step is then to copy these constraints to "bounds".
1293 * Since we may be calling before_each_for and after_each_for
1294 * callbacks, we record the current inverse schedule in the build.
1296 * We consider three builds,
1297 * "build" is the one in which the current level is created,
1298 * "body_build" is the build in which the next level is created,
1299 * "sub_build" is essentially the same as "body_build", except that
1300 * the depth has not been increased yet.
1302 * "build" already contains information (in strides and offsets)
1303 * about the strides at the current level, but this information is not
1304 * reflected in the build->domain.
1305 * We first add this information and the "bounds" to the sub_build->domain.
1306 * isl_ast_build_set_loop_bounds checks whether the current dimension attains
1307 * only a single value and whether this single value can be represented using
1308 * a single affine expression.
1309 * In the first case, the current level is considered "degenerate".
1310 * In the second, sub-case, the current level is considered "eliminated".
1311 * Eliminated level don't need to be reflected in the AST since we can
1312 * simply plug in the affine expression. For degenerate, but non-eliminated,
1313 * levels, we do introduce a for node, but mark is as degenerate so that
1314 * it can be printed as an assignment of the single value to the loop
1315 * "iterator".
1317 * If the current level is eliminated, we explicitly plug in the value
1318 * for the current level found by isl_ast_build_set_loop_bounds in the
1319 * inverse schedule. This ensures that if we are working on a slice
1320 * of the domain based on information available in the inverse schedule
1321 * and the build domain, that then this information is also reflected
1322 * in the inverse schedule. This operation also eliminates the current
1323 * dimension from the inverse schedule making sure no inner dimensions depend
1324 * on the current dimension. Otherwise, we create a for node, marking
1325 * it degenerate if appropriate. The initial for node is still incomplete
1326 * and will be completed in either refine_degenerate or refine_generic.
1328 * We then generate a sequence of grafts for the next level,
1329 * create a surrounding graft for the current level and insert
1330 * the for node we created (if the current level is not eliminated).
1332 * Finally, we set the bounds of the for loop and insert guards
1333 * (either in the AST or in the graft) in one of
1334 * refine_eliminated, refine_degenerate or refine_generic.
1336 static __isl_give isl_ast_graft *create_node_scaled(
1337 __isl_take isl_union_map *executed,
1338 __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1339 __isl_take isl_ast_build *build)
1341 int depth;
1342 int degenerate, eliminated;
1343 isl_basic_set *hull;
1344 isl_ast_node *node = NULL;
1345 isl_ast_graft *graft;
1346 isl_ast_graft_list *children;
1347 isl_ast_build *sub_build;
1348 isl_ast_build *body_build;
1350 domain = isl_ast_build_eliminate_divs(build, domain);
1351 domain = isl_set_detect_equalities(domain);
1352 hull = isl_set_unshifted_simple_hull(isl_set_copy(domain));
1353 bounds = isl_basic_set_intersect(bounds, hull);
1354 build = isl_ast_build_set_executed(build, isl_union_map_copy(executed));
1356 depth = isl_ast_build_get_depth(build);
1357 sub_build = isl_ast_build_copy(build);
1358 sub_build = isl_ast_build_include_stride(sub_build);
1359 sub_build = isl_ast_build_set_loop_bounds(sub_build,
1360 isl_basic_set_copy(bounds));
1361 degenerate = isl_ast_build_has_value(sub_build);
1362 eliminated = isl_ast_build_has_affine_value(sub_build, depth);
1363 if (degenerate < 0 || eliminated < 0)
1364 executed = isl_union_map_free(executed);
1365 if (eliminated)
1366 executed = plug_in_values(executed, sub_build);
1367 else
1368 node = create_for(build, degenerate);
1370 body_build = isl_ast_build_copy(sub_build);
1371 body_build = isl_ast_build_increase_depth(body_build);
1372 if (!eliminated)
1373 node = before_each_for(node, body_build);
1374 children = generate_next_level(executed,
1375 isl_ast_build_copy(body_build));
1377 graft = isl_ast_graft_alloc_level(children, build, sub_build);
1378 if (!eliminated)
1379 graft = isl_ast_graft_insert_for(graft, node);
1380 if (eliminated)
1381 graft = refine_eliminated(graft, bounds, build);
1382 else if (degenerate)
1383 graft = refine_degenerate(graft, bounds, build, sub_build);
1384 else
1385 graft = refine_generic(graft, bounds, domain, build);
1386 if (!eliminated)
1387 graft = after_each_for(graft, body_build);
1389 isl_ast_build_free(body_build);
1390 isl_ast_build_free(sub_build);
1391 isl_ast_build_free(build);
1392 isl_basic_set_free(bounds);
1393 isl_set_free(domain);
1395 return graft;
1398 /* Internal data structure for checking if all constraints involving
1399 * the input dimension "depth" are such that the other coefficients
1400 * are multiples of "m", reducing "m" if they are not.
1401 * If "m" is reduced all the way down to "1", then the check has failed
1402 * and we break out of the iteration.
1404 struct isl_check_scaled_data {
1405 int depth;
1406 isl_val *m;
1409 /* If constraint "c" involves the input dimension data->depth,
1410 * then make sure that all the other coefficients are multiples of data->m,
1411 * reducing data->m if needed.
1412 * Break out of the iteration if data->m has become equal to "1".
1414 static int constraint_check_scaled(__isl_take isl_constraint *c, void *user)
1416 struct isl_check_scaled_data *data = user;
1417 int i, j, n;
1418 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_out,
1419 isl_dim_div };
1421 if (!isl_constraint_involves_dims(c, isl_dim_in, data->depth, 1)) {
1422 isl_constraint_free(c);
1423 return 0;
1426 for (i = 0; i < 4; ++i) {
1427 n = isl_constraint_dim(c, t[i]);
1428 for (j = 0; j < n; ++j) {
1429 isl_val *d;
1431 if (t[i] == isl_dim_in && j == data->depth)
1432 continue;
1433 if (!isl_constraint_involves_dims(c, t[i], j, 1))
1434 continue;
1435 d = isl_constraint_get_coefficient_val(c, t[i], j);
1436 data->m = isl_val_gcd(data->m, d);
1437 if (isl_val_is_one(data->m))
1438 break;
1440 if (j < n)
1441 break;
1444 isl_constraint_free(c);
1446 return i < 4 ? -1 : 0;
1449 /* For each constraint of "bmap" that involves the input dimension data->depth,
1450 * make sure that all the other coefficients are multiples of data->m,
1451 * reducing data->m if needed.
1452 * Break out of the iteration if data->m has become equal to "1".
1454 static int basic_map_check_scaled(__isl_take isl_basic_map *bmap, void *user)
1456 int r;
1458 r = isl_basic_map_foreach_constraint(bmap,
1459 &constraint_check_scaled, user);
1460 isl_basic_map_free(bmap);
1462 return r;
1465 /* For each constraint of "map" that involves the input dimension data->depth,
1466 * make sure that all the other coefficients are multiples of data->m,
1467 * reducing data->m if needed.
1468 * Break out of the iteration if data->m has become equal to "1".
1470 static int map_check_scaled(__isl_take isl_map *map, void *user)
1472 int r;
1474 r = isl_map_foreach_basic_map(map, &basic_map_check_scaled, user);
1475 isl_map_free(map);
1477 return r;
1480 /* Create an AST node for the current dimension based on
1481 * the schedule domain "bounds" and return the node encapsulated
1482 * in an isl_ast_graft.
1484 * "executed" is the current inverse schedule, taking into account
1485 * the bounds in "bounds"
1486 * "domain" is the domain of "executed", with inner dimensions projected out.
1489 * Before moving on to the actual AST node construction in create_node_scaled,
1490 * we first check if the current dimension is strided and if we can scale
1491 * down this stride. Note that we only do this if the ast_build_scale_strides
1492 * option is set.
1494 * In particular, let the current dimension take on values
1496 * f + s a
1498 * with a an integer. We check if we can find an integer m that (obviouly)
1499 * divides both f and s.
1501 * If so, we check if the current dimension only appears in constraints
1502 * where the coefficients of the other variables are multiples of m.
1503 * We perform this extra check to avoid the risk of introducing
1504 * divisions by scaling down the current dimension.
1506 * If so, we scale the current dimension down by a factor of m.
1507 * That is, we plug in
1509 * i = m i' (1)
1511 * Note that in principle we could always scale down strided loops
1512 * by plugging in
1514 * i = f + s i'
1516 * but this may result in i' taking on larger values than the original i,
1517 * due to the shift by "f".
1518 * By constrast, the scaling in (1) can only reduce the (absolute) value "i".
1520 static __isl_give isl_ast_graft *create_node(__isl_take isl_union_map *executed,
1521 __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1522 __isl_take isl_ast_build *build)
1524 struct isl_check_scaled_data data;
1525 isl_ctx *ctx;
1526 isl_aff *offset;
1527 isl_val *d;
1529 ctx = isl_ast_build_get_ctx(build);
1530 if (!isl_options_get_ast_build_scale_strides(ctx))
1531 return create_node_scaled(executed, bounds, domain, build);
1533 data.depth = isl_ast_build_get_depth(build);
1534 if (!isl_ast_build_has_stride(build, data.depth))
1535 return create_node_scaled(executed, bounds, domain, build);
1537 offset = isl_ast_build_get_offset(build, data.depth);
1538 data.m = isl_ast_build_get_stride(build, data.depth);
1539 if (!data.m)
1540 offset = isl_aff_free(offset);
1541 offset = isl_aff_scale_down_val(offset, isl_val_copy(data.m));
1542 d = isl_aff_get_denominator_val(offset);
1543 if (!d)
1544 executed = isl_union_map_free(executed);
1546 if (executed && isl_val_is_divisible_by(data.m, d))
1547 data.m = isl_val_div(data.m, d);
1548 else {
1549 data.m = isl_val_set_si(data.m, 1);
1550 isl_val_free(d);
1553 if (!isl_val_is_one(data.m)) {
1554 if (isl_union_map_foreach_map(executed, &map_check_scaled,
1555 &data) < 0 &&
1556 !isl_val_is_one(data.m))
1557 executed = isl_union_map_free(executed);
1560 if (!isl_val_is_one(data.m)) {
1561 isl_space *space;
1562 isl_multi_aff *ma;
1563 isl_aff *aff;
1564 isl_map *map;
1565 isl_union_map *umap;
1567 space = isl_ast_build_get_space(build, 1);
1568 space = isl_space_map_from_set(space);
1569 ma = isl_multi_aff_identity(space);
1570 aff = isl_multi_aff_get_aff(ma, data.depth);
1571 aff = isl_aff_scale_val(aff, isl_val_copy(data.m));
1572 ma = isl_multi_aff_set_aff(ma, data.depth, aff);
1574 bounds = isl_basic_set_preimage_multi_aff(bounds,
1575 isl_multi_aff_copy(ma));
1576 domain = isl_set_preimage_multi_aff(domain,
1577 isl_multi_aff_copy(ma));
1578 map = isl_map_reverse(isl_map_from_multi_aff(ma));
1579 umap = isl_union_map_from_map(map);
1580 executed = isl_union_map_apply_domain(executed,
1581 isl_union_map_copy(umap));
1582 build = isl_ast_build_scale_down(build, isl_val_copy(data.m),
1583 umap);
1585 isl_aff_free(offset);
1586 isl_val_free(data.m);
1588 return create_node_scaled(executed, bounds, domain, build);
1591 /* Add the basic set to the list that "user" points to.
1593 static int collect_basic_set(__isl_take isl_basic_set *bset, void *user)
1595 isl_basic_set_list **list = user;
1597 *list = isl_basic_set_list_add(*list, bset);
1599 return 0;
1602 /* Extract the basic sets of "set" and collect them in an isl_basic_set_list.
1604 static __isl_give isl_basic_set_list *isl_basic_set_list_from_set(
1605 __isl_take isl_set *set)
1607 int n;
1608 isl_ctx *ctx;
1609 isl_basic_set_list *list;
1611 if (!set)
1612 return NULL;
1614 ctx = isl_set_get_ctx(set);
1616 n = isl_set_n_basic_set(set);
1617 list = isl_basic_set_list_alloc(ctx, n);
1618 if (isl_set_foreach_basic_set(set, &collect_basic_set, &list) < 0)
1619 list = isl_basic_set_list_free(list);
1621 isl_set_free(set);
1622 return list;
1625 /* Generate code for the schedule domain "bounds"
1626 * and add the result to "list".
1628 * We mainly detect strides and additional equalities here
1629 * and then pass over control to create_node.
1631 * "bounds" reflects the bounds on the current dimension and possibly
1632 * some extra conditions on outer dimensions.
1633 * It does not, however, include any divs involving the current dimension,
1634 * so it does not capture any stride constraints.
1635 * We therefore need to compute that part of the schedule domain that
1636 * intersects with "bounds" and derive the strides from the result.
1638 static __isl_give isl_ast_graft_list *add_node(
1639 __isl_take isl_ast_graft_list *list, __isl_take isl_union_map *executed,
1640 __isl_take isl_basic_set *bounds, __isl_take isl_ast_build *build)
1642 isl_ast_graft *graft;
1643 isl_set *domain = NULL;
1644 isl_union_set *uset;
1645 int empty;
1647 uset = isl_union_set_from_basic_set(isl_basic_set_copy(bounds));
1648 executed = isl_union_map_intersect_domain(executed, uset);
1649 empty = isl_union_map_is_empty(executed);
1650 if (empty < 0)
1651 goto error;
1652 if (empty)
1653 goto done;
1655 uset = isl_union_map_domain(isl_union_map_copy(executed));
1656 domain = isl_set_from_union_set(uset);
1657 domain = isl_ast_build_compute_gist(build, domain);
1658 empty = isl_set_is_empty(domain);
1659 if (empty < 0)
1660 goto error;
1661 if (empty)
1662 goto done;
1664 domain = isl_ast_build_eliminate_inner(build, domain);
1665 build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
1667 graft = create_node(executed, bounds, domain,
1668 isl_ast_build_copy(build));
1669 list = isl_ast_graft_list_add(list, graft);
1670 isl_ast_build_free(build);
1671 return list;
1672 error:
1673 list = isl_ast_graft_list_free(list);
1674 done:
1675 isl_set_free(domain);
1676 isl_basic_set_free(bounds);
1677 isl_union_map_free(executed);
1678 isl_ast_build_free(build);
1679 return list;
1682 /* Does any element of i follow or coincide with any element of j
1683 * at the current depth for equal values of the outer dimensions?
1685 static int domain_follows_at_depth(__isl_keep isl_basic_set *i,
1686 __isl_keep isl_basic_set *j, void *user)
1688 int depth = *(int *) user;
1689 isl_basic_map *test;
1690 int empty;
1691 int l;
1693 test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1694 isl_basic_set_copy(j));
1695 for (l = 0; l < depth; ++l)
1696 test = isl_basic_map_equate(test, isl_dim_in, l,
1697 isl_dim_out, l);
1698 test = isl_basic_map_order_ge(test, isl_dim_in, depth,
1699 isl_dim_out, depth);
1700 empty = isl_basic_map_is_empty(test);
1701 isl_basic_map_free(test);
1703 return empty < 0 ? -1 : !empty;
1706 /* Split up each element of "list" into a part that is related to "bset"
1707 * according to "gt" and a part that is not.
1708 * Return a list that consist of "bset" and all the pieces.
1710 static __isl_give isl_basic_set_list *add_split_on(
1711 __isl_take isl_basic_set_list *list, __isl_take isl_basic_set *bset,
1712 __isl_keep isl_basic_map *gt)
1714 int i, n;
1715 isl_basic_set_list *res;
1717 if (!list)
1718 bset = isl_basic_set_free(bset);
1720 gt = isl_basic_map_copy(gt);
1721 gt = isl_basic_map_intersect_domain(gt, isl_basic_set_copy(bset));
1722 n = isl_basic_set_list_n_basic_set(list);
1723 res = isl_basic_set_list_from_basic_set(bset);
1724 for (i = 0; res && i < n; ++i) {
1725 isl_basic_set *bset;
1726 isl_set *set1, *set2;
1727 isl_basic_map *bmap;
1728 int empty;
1730 bset = isl_basic_set_list_get_basic_set(list, i);
1731 bmap = isl_basic_map_copy(gt);
1732 bmap = isl_basic_map_intersect_range(bmap, bset);
1733 bset = isl_basic_map_range(bmap);
1734 empty = isl_basic_set_is_empty(bset);
1735 if (empty < 0)
1736 res = isl_basic_set_list_free(res);
1737 if (empty) {
1738 isl_basic_set_free(bset);
1739 bset = isl_basic_set_list_get_basic_set(list, i);
1740 res = isl_basic_set_list_add(res, bset);
1741 continue;
1744 res = isl_basic_set_list_add(res, isl_basic_set_copy(bset));
1745 set1 = isl_set_from_basic_set(bset);
1746 bset = isl_basic_set_list_get_basic_set(list, i);
1747 set2 = isl_set_from_basic_set(bset);
1748 set1 = isl_set_subtract(set2, set1);
1749 set1 = isl_set_make_disjoint(set1);
1751 res = isl_basic_set_list_concat(res,
1752 isl_basic_set_list_from_set(set1));
1754 isl_basic_map_free(gt);
1755 isl_basic_set_list_free(list);
1756 return res;
1759 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1760 __isl_keep isl_basic_set_list *domain_list,
1761 __isl_keep isl_union_map *executed,
1762 __isl_keep isl_ast_build *build);
1764 /* Internal data structure for add_nodes.
1766 * "executed" and "build" are extra arguments to be passed to add_node.
1767 * "list" collects the results.
1769 struct isl_add_nodes_data {
1770 isl_union_map *executed;
1771 isl_ast_build *build;
1773 isl_ast_graft_list *list;
1776 /* Generate code for the schedule domains in "scc"
1777 * and add the results to "list".
1779 * The domains in "scc" form a strongly connected component in the ordering.
1780 * If the number of domains in "scc" is larger than 1, then this means
1781 * that we cannot determine a valid ordering for the domains in the component.
1782 * This should be fairly rare because the individual domains
1783 * have been made disjoint first.
1784 * The problem is that the domains may be integrally disjoint but not
1785 * rationally disjoint. For example, we may have domains
1787 * { [i,i] : 0 <= i <= 1 } and { [i,1-i] : 0 <= i <= 1 }
1789 * These two domains have an empty intersection, but their rational
1790 * relaxations do intersect. It is impossible to order these domains
1791 * in the second dimension because the first should be ordered before
1792 * the second for outer dimension equal to 0, while it should be ordered
1793 * after for outer dimension equal to 1.
1795 * This may happen in particular in case of unrolling since the domain
1796 * of each slice is replaced by its simple hull.
1798 * For each basic set i in "scc" and for each of the following basic sets j,
1799 * we split off that part of the basic set i that shares the outer dimensions
1800 * with j and lies before j in the current dimension.
1801 * We collect all the pieces in a new list that replaces "scc".
1803 * While the elements in "scc" should be disjoint, we double-check
1804 * this property to avoid running into an infinite recursion in case
1805 * they intersect due to some internal error.
1807 static int add_nodes(__isl_take isl_basic_set_list *scc, void *user)
1809 struct isl_add_nodes_data *data = user;
1810 int i, n, depth;
1811 isl_basic_set *bset, *first;
1812 isl_basic_set_list *list;
1813 isl_space *space;
1814 isl_basic_map *gt;
1816 n = isl_basic_set_list_n_basic_set(scc);
1817 bset = isl_basic_set_list_get_basic_set(scc, 0);
1818 if (n == 1) {
1819 isl_basic_set_list_free(scc);
1820 data->list = add_node(data->list,
1821 isl_union_map_copy(data->executed), bset,
1822 isl_ast_build_copy(data->build));
1823 return data->list ? 0 : -1;
1826 depth = isl_ast_build_get_depth(data->build);
1827 space = isl_basic_set_get_space(bset);
1828 space = isl_space_map_from_set(space);
1829 gt = isl_basic_map_universe(space);
1830 for (i = 0; i < depth; ++i)
1831 gt = isl_basic_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
1832 gt = isl_basic_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
1834 first = isl_basic_set_copy(bset);
1835 list = isl_basic_set_list_from_basic_set(bset);
1836 for (i = 1; i < n; ++i) {
1837 int disjoint;
1839 bset = isl_basic_set_list_get_basic_set(scc, i);
1841 disjoint = isl_basic_set_is_disjoint(bset, first);
1842 if (disjoint < 0)
1843 list = isl_basic_set_list_free(list);
1844 else if (!disjoint)
1845 isl_die(isl_basic_set_list_get_ctx(scc),
1846 isl_error_internal,
1847 "basic sets in scc are assumed to be disjoint",
1848 list = isl_basic_set_list_free(list));
1850 list = add_split_on(list, bset, gt);
1852 isl_basic_set_free(first);
1853 isl_basic_map_free(gt);
1854 isl_basic_set_list_free(scc);
1855 scc = list;
1856 data->list = isl_ast_graft_list_concat(data->list,
1857 generate_sorted_domains(scc, data->executed, data->build));
1858 isl_basic_set_list_free(scc);
1860 return data->list ? 0 : -1;
1863 /* Sort the domains in "domain_list" according to the execution order
1864 * at the current depth (for equal values of the outer dimensions),
1865 * generate code for each of them, collecting the results in a list.
1866 * If no code is generated (because the intersection of the inverse schedule
1867 * with the domains turns out to be empty), then an empty list is returned.
1869 * The caller is responsible for ensuring that the basic sets in "domain_list"
1870 * are pair-wise disjoint. It can, however, in principle happen that
1871 * two basic sets should be ordered one way for one value of the outer
1872 * dimensions and the other way for some other value of the outer dimensions.
1873 * We therefore play safe and look for strongly connected components.
1874 * The function add_nodes takes care of handling non-trivial components.
1876 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1877 __isl_keep isl_basic_set_list *domain_list,
1878 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
1880 isl_ctx *ctx;
1881 struct isl_add_nodes_data data;
1882 int depth;
1883 int n;
1885 if (!domain_list)
1886 return NULL;
1888 ctx = isl_basic_set_list_get_ctx(domain_list);
1889 n = isl_basic_set_list_n_basic_set(domain_list);
1890 data.list = isl_ast_graft_list_alloc(ctx, n);
1891 if (n == 0)
1892 return data.list;
1893 if (n == 1)
1894 return add_node(data.list, isl_union_map_copy(executed),
1895 isl_basic_set_list_get_basic_set(domain_list, 0),
1896 isl_ast_build_copy(build));
1898 depth = isl_ast_build_get_depth(build);
1899 data.executed = executed;
1900 data.build = build;
1901 if (isl_basic_set_list_foreach_scc(domain_list,
1902 &domain_follows_at_depth, &depth,
1903 &add_nodes, &data) < 0)
1904 data.list = isl_ast_graft_list_free(data.list);
1906 return data.list;
1909 /* Do i and j share any values for the outer dimensions?
1911 static int shared_outer(__isl_keep isl_basic_set *i,
1912 __isl_keep isl_basic_set *j, void *user)
1914 int depth = *(int *) user;
1915 isl_basic_map *test;
1916 int empty;
1917 int l;
1919 test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1920 isl_basic_set_copy(j));
1921 for (l = 0; l < depth; ++l)
1922 test = isl_basic_map_equate(test, isl_dim_in, l,
1923 isl_dim_out, l);
1924 empty = isl_basic_map_is_empty(test);
1925 isl_basic_map_free(test);
1927 return empty < 0 ? -1 : !empty;
1930 /* Internal data structure for generate_sorted_domains_wrap.
1932 * "n" is the total number of basic sets
1933 * "executed" and "build" are extra arguments to be passed
1934 * to generate_sorted_domains.
1936 * "single" is set to 1 by generate_sorted_domains_wrap if there
1937 * is only a single component.
1938 * "list" collects the results.
1940 struct isl_ast_generate_parallel_domains_data {
1941 int n;
1942 isl_union_map *executed;
1943 isl_ast_build *build;
1945 int single;
1946 isl_ast_graft_list *list;
1949 /* Call generate_sorted_domains on "scc", fuse the result into a list
1950 * with either zero or one graft and collect the these single element
1951 * lists into data->list.
1953 * If there is only one component, i.e., if the number of basic sets
1954 * in the current component is equal to the total number of basic sets,
1955 * then data->single is set to 1 and the result of generate_sorted_domains
1956 * is not fused.
1958 static int generate_sorted_domains_wrap(__isl_take isl_basic_set_list *scc,
1959 void *user)
1961 struct isl_ast_generate_parallel_domains_data *data = user;
1962 isl_ast_graft_list *list;
1964 list = generate_sorted_domains(scc, data->executed, data->build);
1965 data->single = isl_basic_set_list_n_basic_set(scc) == data->n;
1966 if (!data->single)
1967 list = isl_ast_graft_list_fuse(list, data->build);
1968 if (!data->list)
1969 data->list = list;
1970 else
1971 data->list = isl_ast_graft_list_concat(data->list, list);
1973 isl_basic_set_list_free(scc);
1974 if (!data->list)
1975 return -1;
1977 return 0;
1980 /* Look for any (weakly connected) components in the "domain_list"
1981 * of domains that share some values of the outer dimensions.
1982 * That is, domains in different components do not share any values
1983 * of the outer dimensions. This means that these components
1984 * can be freely reordered.
1985 * Within each of the components, we sort the domains according
1986 * to the execution order at the current depth.
1988 * If there is more than one component, then generate_sorted_domains_wrap
1989 * fuses the result of each call to generate_sorted_domains
1990 * into a list with either zero or one graft and collects these (at most)
1991 * single element lists into a bigger list. This means that the elements of the
1992 * final list can be freely reordered. In particular, we sort them
1993 * according to an arbitrary but fixed ordering to ease merging of
1994 * graft lists from different components.
1996 static __isl_give isl_ast_graft_list *generate_parallel_domains(
1997 __isl_keep isl_basic_set_list *domain_list,
1998 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2000 int depth;
2001 struct isl_ast_generate_parallel_domains_data data;
2003 if (!domain_list)
2004 return NULL;
2006 data.n = isl_basic_set_list_n_basic_set(domain_list);
2007 if (data.n <= 1)
2008 return generate_sorted_domains(domain_list, executed, build);
2010 depth = isl_ast_build_get_depth(build);
2011 data.list = NULL;
2012 data.executed = executed;
2013 data.build = build;
2014 data.single = 0;
2015 if (isl_basic_set_list_foreach_scc(domain_list, &shared_outer, &depth,
2016 &generate_sorted_domains_wrap,
2017 &data) < 0)
2018 data.list = isl_ast_graft_list_free(data.list);
2020 if (!data.single)
2021 data.list = isl_ast_graft_list_sort_guard(data.list);
2023 return data.list;
2026 /* Internal data for separate_domain.
2028 * "explicit" is set if we only want to use explicit bounds.
2030 * "domain" collects the separated domains.
2032 struct isl_separate_domain_data {
2033 isl_ast_build *build;
2034 int explicit;
2035 isl_set *domain;
2038 /* Extract implicit bounds on the current dimension for the executed "map".
2040 * The domain of "map" may involve inner dimensions, so we
2041 * need to eliminate them.
2043 static __isl_give isl_set *implicit_bounds(__isl_take isl_map *map,
2044 __isl_keep isl_ast_build *build)
2046 isl_set *domain;
2048 domain = isl_map_domain(map);
2049 domain = isl_ast_build_eliminate(build, domain);
2051 return domain;
2054 /* Extract explicit bounds on the current dimension for the executed "map".
2056 * Rather than eliminating the inner dimensions as in implicit_bounds,
2057 * we simply drop any constraints involving those inner dimensions.
2058 * The idea is that most bounds that are implied by constraints on the
2059 * inner dimensions will be enforced by for loops and not by explicit guards.
2060 * There is then no need to separate along those bounds.
2062 static __isl_give isl_set *explicit_bounds(__isl_take isl_map *map,
2063 __isl_keep isl_ast_build *build)
2065 isl_set *domain;
2066 int depth, dim;
2068 dim = isl_map_dim(map, isl_dim_out);
2069 map = isl_map_drop_constraints_involving_dims(map, isl_dim_out, 0, dim);
2071 domain = isl_map_domain(map);
2072 depth = isl_ast_build_get_depth(build);
2073 dim = isl_set_dim(domain, isl_dim_set);
2074 domain = isl_set_detect_equalities(domain);
2075 domain = isl_set_drop_constraints_involving_dims(domain,
2076 isl_dim_set, depth + 1, dim - (depth + 1));
2077 domain = isl_set_remove_divs_involving_dims(domain,
2078 isl_dim_set, depth, 1);
2079 domain = isl_set_remove_unknown_divs(domain);
2081 return domain;
2084 /* Split data->domain into pieces that intersect with the range of "map"
2085 * and pieces that do not intersect with the range of "map"
2086 * and then add that part of the range of "map" that does not intersect
2087 * with data->domain.
2089 static int separate_domain(__isl_take isl_map *map, void *user)
2091 struct isl_separate_domain_data *data = user;
2092 isl_set *domain;
2093 isl_set *d1, *d2;
2095 if (data->explicit)
2096 domain = explicit_bounds(map, data->build);
2097 else
2098 domain = implicit_bounds(map, data->build);
2100 domain = isl_set_coalesce(domain);
2101 domain = isl_set_make_disjoint(domain);
2102 d1 = isl_set_subtract(isl_set_copy(domain), isl_set_copy(data->domain));
2103 d2 = isl_set_subtract(isl_set_copy(data->domain), isl_set_copy(domain));
2104 data->domain = isl_set_intersect(data->domain, domain);
2105 data->domain = isl_set_union(data->domain, d1);
2106 data->domain = isl_set_union(data->domain, d2);
2108 return 0;
2111 /* Separate the schedule domains of "executed".
2113 * That is, break up the domain of "executed" into basic sets,
2114 * such that for each basic set S, every element in S is associated with
2115 * the same domain spaces.
2117 * "space" is the (single) domain space of "executed".
2119 static __isl_give isl_set *separate_schedule_domains(
2120 __isl_take isl_space *space, __isl_take isl_union_map *executed,
2121 __isl_keep isl_ast_build *build)
2123 struct isl_separate_domain_data data = { build };
2124 isl_ctx *ctx;
2126 ctx = isl_ast_build_get_ctx(build);
2127 data.explicit = isl_options_get_ast_build_separation_bounds(ctx) ==
2128 ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT;
2129 data.domain = isl_set_empty(space);
2130 if (isl_union_map_foreach_map(executed, &separate_domain, &data) < 0)
2131 data.domain = isl_set_free(data.domain);
2133 isl_union_map_free(executed);
2134 return data.domain;
2137 /* Temporary data used during the search for a lower bound for unrolling.
2139 * "domain" is the original set for which to find a lower bound
2140 * "depth" is the dimension for which to find a lower boudn
2142 * "lower" is the best lower bound found so far. It is NULL if we have not
2143 * found any yet.
2144 * "n" is the corresponding size. If lower is NULL, then the value of n
2145 * is undefined.
2147 struct isl_find_unroll_data {
2148 isl_set *domain;
2149 int depth;
2151 isl_aff *lower;
2152 int *n;
2155 /* Check if we can use "c" as a lower bound and if it is better than
2156 * any previously found lower bound.
2158 * If "c" does not involve the dimension at the current depth,
2159 * then we cannot use it.
2160 * Otherwise, let "c" be of the form
2162 * i >= f(j)/a
2164 * We compute the maximal value of
2166 * -ceil(f(j)/a)) + i + 1
2168 * over the domain. If there is such a value "n", then we know
2170 * -ceil(f(j)/a)) + i + 1 <= n
2172 * or
2174 * i < ceil(f(j)/a)) + n
2176 * meaning that we can use ceil(f(j)/a)) as a lower bound for unrolling.
2177 * We just need to check if we have found any lower bound before and
2178 * if the new lower bound is better (smaller n) than the previously found
2179 * lower bounds.
2181 static int update_unrolling_lower_bound(struct isl_find_unroll_data *data,
2182 __isl_keep isl_constraint *c)
2184 isl_aff *aff, *lower;
2185 isl_val *max;
2187 if (!isl_constraint_is_lower_bound(c, isl_dim_set, data->depth))
2188 return 0;
2190 lower = isl_constraint_get_bound(c, isl_dim_set, data->depth);
2191 lower = isl_aff_ceil(lower);
2192 aff = isl_aff_copy(lower);
2193 aff = isl_aff_neg(aff);
2194 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, data->depth, 1);
2195 aff = isl_aff_add_constant_si(aff, 1);
2196 max = isl_set_max_val(data->domain, aff);
2197 isl_aff_free(aff);
2199 if (!max)
2200 goto error;
2201 if (isl_val_is_infty(max)) {
2202 isl_val_free(max);
2203 isl_aff_free(lower);
2204 return 0;
2207 if (isl_val_cmp_si(max, INT_MAX) <= 0 &&
2208 (!data->lower || isl_val_cmp_si(max, *data->n) < 0)) {
2209 isl_aff_free(data->lower);
2210 data->lower = lower;
2211 *data->n = isl_val_get_num_si(max);
2212 } else
2213 isl_aff_free(lower);
2214 isl_val_free(max);
2216 return 1;
2217 error:
2218 isl_aff_free(lower);
2219 return -1;
2222 /* Check if we can use "c" as a lower bound and if it is better than
2223 * any previously found lower bound.
2225 static int constraint_find_unroll(__isl_take isl_constraint *c, void *user)
2227 struct isl_find_unroll_data *data;
2228 int r;
2230 data = (struct isl_find_unroll_data *) user;
2231 r = update_unrolling_lower_bound(data, c);
2232 isl_constraint_free(c);
2234 return r;
2237 /* Look for a lower bound l(i) on the dimension at "depth"
2238 * and a size n such that "domain" is a subset of
2240 * { [i] : l(i) <= i_d < l(i) + n }
2242 * where d is "depth" and l(i) depends only on earlier dimensions.
2243 * Furthermore, try and find a lower bound such that n is as small as possible.
2244 * In particular, "n" needs to be finite.
2246 * Inner dimensions have been eliminated from "domain" by the caller.
2248 * We first construct a collection of lower bounds on the input set
2249 * by computing its simple hull. We then iterate through them,
2250 * discarding those that we cannot use (either because they do not
2251 * involve the dimension at "depth" or because they have no corresponding
2252 * upper bound, meaning that "n" would be unbounded) and pick out the
2253 * best from the remaining ones.
2255 * If we cannot find a suitable lower bound, then we consider that
2256 * to be an error.
2258 static __isl_give isl_aff *find_unroll_lower_bound(__isl_keep isl_set *domain,
2259 int depth, int *n)
2261 struct isl_find_unroll_data data = { domain, depth, NULL, n };
2262 isl_basic_set *hull;
2264 hull = isl_set_simple_hull(isl_set_copy(domain));
2266 if (isl_basic_set_foreach_constraint(hull,
2267 &constraint_find_unroll, &data) < 0)
2268 goto error;
2270 isl_basic_set_free(hull);
2272 if (!data.lower)
2273 isl_die(isl_set_get_ctx(domain), isl_error_invalid,
2274 "cannot find lower bound for unrolling", return NULL);
2276 return data.lower;
2277 error:
2278 isl_basic_set_free(hull);
2279 return isl_aff_free(data.lower);
2282 /* Return the constraint
2284 * i_"depth" = aff + offset
2286 static __isl_give isl_constraint *at_offset(int depth, __isl_keep isl_aff *aff,
2287 int offset)
2289 aff = isl_aff_copy(aff);
2290 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, depth, -1);
2291 aff = isl_aff_add_constant_si(aff, offset);
2292 return isl_equality_from_aff(aff);
2295 /* Data structure for storing the results and the intermediate objects
2296 * of compute_domains.
2298 * "list" is the main result of the function and contains a list
2299 * of disjoint basic sets for which code should be generated.
2301 * "executed" and "build" are inputs to compute_domains.
2302 * "schedule_domain" is the domain of "executed".
2304 * "option" constains the domains at the current depth that should by
2305 * atomic, separated or unrolled. These domains are as specified by
2306 * the user, except that inner dimensions have been eliminated and
2307 * that they have been made pair-wise disjoint.
2309 * "sep_class" contains the user-specified split into separation classes
2310 * specialized to the current depth.
2311 * "done" contains the union of the separation domains that have already
2312 * been handled.
2314 struct isl_codegen_domains {
2315 isl_basic_set_list *list;
2317 isl_union_map *executed;
2318 isl_ast_build *build;
2319 isl_set *schedule_domain;
2321 isl_set *option[3];
2323 isl_map *sep_class;
2324 isl_set *done;
2327 /* Extend domains->list with a list of basic sets, one for each value
2328 * of the current dimension in "domain" and remove the corresponding
2329 * sets from the class domain. Return the updated class domain.
2330 * The divs that involve the current dimension have not been projected out
2331 * from this domain.
2333 * Since we are going to be iterating over the individual values,
2334 * we first check if there are any strides on the current dimension.
2335 * If there is, we rewrite the current dimension i as
2337 * i = stride i' + offset
2339 * and then iterate over individual values of i' instead.
2341 * We then look for a lower bound on i' and a size such that the domain
2342 * is a subset of
2344 * { [j,i'] : l(j) <= i' < l(j) + n }
2346 * and then take slices of the domain at values of i'
2347 * between l(j) and l(j) + n - 1.
2349 * We compute the unshifted simple hull of each slice to ensure that
2350 * we have a single basic set per offset. The slicing constraint
2351 * may get simplified away before the unshifted simple hull is taken
2352 * and may therefore in some rare cases disappear from the result.
2353 * We therefore explicitly add the constraint back after computing
2354 * the unshifted simple hull to ensure that the basic sets
2355 * remain disjoint. The constraints that are dropped by taking the hull
2356 * will be taken into account at the next level, as in the case of the
2357 * atomic option.
2359 * Finally, we map i' back to i and add each basic set to the list.
2360 * Since we may have dropped some constraints, we intersect with
2361 * the class domain again to ensure that each element in the list
2362 * is disjoint from the other class domains.
2364 static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains,
2365 __isl_take isl_set *domain, __isl_take isl_set *class_domain)
2367 int i, n;
2368 int depth;
2369 isl_ctx *ctx;
2370 isl_aff *lower;
2371 isl_multi_aff *expansion;
2372 isl_basic_map *bmap;
2373 isl_set *unroll_domain;
2374 isl_ast_build *build;
2376 if (!domain)
2377 return isl_set_free(class_domain);
2379 ctx = isl_set_get_ctx(domain);
2380 depth = isl_ast_build_get_depth(domains->build);
2381 build = isl_ast_build_copy(domains->build);
2382 domain = isl_ast_build_eliminate_inner(build, domain);
2383 build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
2384 expansion = isl_ast_build_get_stride_expansion(build);
2386 domain = isl_set_preimage_multi_aff(domain,
2387 isl_multi_aff_copy(expansion));
2388 domain = isl_ast_build_eliminate_divs(build, domain);
2390 isl_ast_build_free(build);
2392 lower = find_unroll_lower_bound(domain, depth, &n);
2393 if (!lower)
2394 class_domain = isl_set_free(class_domain);
2396 bmap = isl_basic_map_from_multi_aff(expansion);
2398 unroll_domain = isl_set_empty(isl_set_get_space(domain));
2400 for (i = 0; class_domain && i < n; ++i) {
2401 isl_set *set;
2402 isl_basic_set *bset;
2403 isl_constraint *slice;
2404 isl_basic_set_list *list;
2406 slice = at_offset(depth, lower, i);
2407 set = isl_set_copy(domain);
2408 set = isl_set_add_constraint(set, isl_constraint_copy(slice));
2409 bset = isl_set_unshifted_simple_hull(set);
2410 bset = isl_basic_set_add_constraint(bset, slice);
2411 bset = isl_basic_set_apply(bset, isl_basic_map_copy(bmap));
2412 set = isl_set_from_basic_set(bset);
2413 unroll_domain = isl_set_union(unroll_domain, isl_set_copy(set));
2414 set = isl_set_intersect(set, isl_set_copy(class_domain));
2415 set = isl_set_make_disjoint(set);
2416 list = isl_basic_set_list_from_set(set);
2417 domains->list = isl_basic_set_list_concat(domains->list, list);
2420 class_domain = isl_set_subtract(class_domain, unroll_domain);
2422 isl_aff_free(lower);
2423 isl_set_free(domain);
2424 isl_basic_map_free(bmap);
2426 return class_domain;
2429 /* Add domains to domains->list for each individual value of the current
2430 * dimension, for that part of the schedule domain that lies in the
2431 * intersection of the option domain and the class domain.
2432 * Remove the corresponding sets from the class domain and
2433 * return the updated class domain.
2435 * We first break up the unroll option domain into individual pieces
2436 * and then handle each of them separately. The unroll option domain
2437 * has been made disjoint in compute_domains_init_options,
2439 * Note that we actively want to combine different pieces of the
2440 * schedule domain that have the same value at the current dimension.
2441 * We therefore need to break up the unroll option domain before
2442 * intersecting with class and schedule domain, hoping that the
2443 * unroll option domain specified by the user is relatively simple.
2445 static __isl_give isl_set *compute_unroll_domains(
2446 struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2448 isl_set *unroll_domain;
2449 isl_basic_set_list *unroll_list;
2450 int i, n;
2451 int empty;
2453 empty = isl_set_is_empty(domains->option[unroll]);
2454 if (empty < 0)
2455 return isl_set_free(class_domain);
2456 if (empty)
2457 return class_domain;
2459 unroll_domain = isl_set_copy(domains->option[unroll]);
2460 unroll_list = isl_basic_set_list_from_set(unroll_domain);
2462 n = isl_basic_set_list_n_basic_set(unroll_list);
2463 for (i = 0; i < n; ++i) {
2464 isl_basic_set *bset;
2466 bset = isl_basic_set_list_get_basic_set(unroll_list, i);
2467 unroll_domain = isl_set_from_basic_set(bset);
2468 unroll_domain = isl_set_intersect(unroll_domain,
2469 isl_set_copy(class_domain));
2470 unroll_domain = isl_set_intersect(unroll_domain,
2471 isl_set_copy(domains->schedule_domain));
2473 empty = isl_set_is_empty(unroll_domain);
2474 if (empty >= 0 && empty) {
2475 isl_set_free(unroll_domain);
2476 continue;
2479 class_domain = do_unroll(domains, unroll_domain, class_domain);
2482 isl_basic_set_list_free(unroll_list);
2484 return class_domain;
2487 /* Try and construct a single basic set that includes the intersection of
2488 * the schedule domain, the atomic option domain and the class domain.
2489 * Add the resulting basic set(s) to domains->list and remove them
2490 * from class_domain. Return the updated class domain.
2492 * We construct a single domain rather than trying to combine
2493 * the schedule domains of individual domains because we are working
2494 * within a single component so that non-overlapping schedule domains
2495 * should already have been separated.
2496 * We do however need to make sure that this single domains is a subset
2497 * of the class domain so that it would not intersect with any other
2498 * class domains. This means that we may end up splitting up the atomic
2499 * domain in case separation classes are being used.
2501 * "domain" is the intersection of the schedule domain and the class domain,
2502 * with inner dimensions projected out.
2504 static __isl_give isl_set *compute_atomic_domain(
2505 struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2507 isl_basic_set *bset;
2508 isl_basic_set_list *list;
2509 isl_set *domain, *atomic_domain;
2510 int empty;
2512 domain = isl_set_copy(domains->option[atomic]);
2513 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2514 domain = isl_set_intersect(domain,
2515 isl_set_copy(domains->schedule_domain));
2516 empty = isl_set_is_empty(domain);
2517 if (empty < 0)
2518 class_domain = isl_set_free(class_domain);
2519 if (empty) {
2520 isl_set_free(domain);
2521 return class_domain;
2524 domain = isl_ast_build_eliminate(domains->build, domain);
2525 domain = isl_set_coalesce(domain);
2526 bset = isl_set_unshifted_simple_hull(domain);
2527 domain = isl_set_from_basic_set(bset);
2528 atomic_domain = isl_set_copy(domain);
2529 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2530 class_domain = isl_set_subtract(class_domain, atomic_domain);
2531 domain = isl_set_make_disjoint(domain);
2532 list = isl_basic_set_list_from_set(domain);
2533 domains->list = isl_basic_set_list_concat(domains->list, list);
2535 return class_domain;
2538 /* Split up the schedule domain into uniform basic sets,
2539 * in the sense that each element in a basic set is associated to
2540 * elements of the same domains, and add the result to domains->list.
2541 * Do this for that part of the schedule domain that lies in the
2542 * intersection of "class_domain" and the separate option domain.
2544 * "class_domain" may or may not include the constraints
2545 * of the schedule domain, but this does not make a difference
2546 * since we are going to intersect it with the domain of the inverse schedule.
2547 * If it includes schedule domain constraints, then they may involve
2548 * inner dimensions, but we will eliminate them in separation_domain.
2550 static int compute_separate_domain(struct isl_codegen_domains *domains,
2551 __isl_keep isl_set *class_domain)
2553 isl_space *space;
2554 isl_set *domain;
2555 isl_union_map *executed;
2556 isl_basic_set_list *list;
2557 int empty;
2559 domain = isl_set_copy(domains->option[separate]);
2560 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2561 executed = isl_union_map_copy(domains->executed);
2562 executed = isl_union_map_intersect_domain(executed,
2563 isl_union_set_from_set(domain));
2564 empty = isl_union_map_is_empty(executed);
2565 if (empty < 0 || empty) {
2566 isl_union_map_free(executed);
2567 return empty < 0 ? -1 : 0;
2570 space = isl_set_get_space(class_domain);
2571 domain = separate_schedule_domains(space, executed, domains->build);
2573 list = isl_basic_set_list_from_set(domain);
2574 domains->list = isl_basic_set_list_concat(domains->list, list);
2576 return 0;
2579 /* Split up the domain at the current depth into disjoint
2580 * basic sets for which code should be generated separately
2581 * for the given separation class domain.
2583 * If any separation classes have been defined, then "class_domain"
2584 * is the domain of the current class and does not refer to inner dimensions.
2585 * Otherwise, "class_domain" is the universe domain.
2587 * We first make sure that the class domain is disjoint from
2588 * previously considered class domains.
2590 * The separate domains can be computed directly from the "class_domain".
2592 * The unroll, atomic and remainder domains need the constraints
2593 * from the schedule domain.
2595 * For unrolling, the actual schedule domain is needed (with divs that
2596 * may refer to the current dimension) so that stride detection can be
2597 * performed.
2599 * For atomic and remainder domains, inner dimensions and divs involving
2600 * the current dimensions should be eliminated.
2601 * In case we are working within a separation class, we need to intersect
2602 * the result with the current "class_domain" to ensure that the domains
2603 * are disjoint from those generated from other class domains.
2605 * The domain that has been made atomic may be larger than specified
2606 * by the user since it needs to be representable as a single basic set.
2607 * This possibly larger domain is removed from class_domain by
2608 * compute_atomic_domain. It is computed first so that the extended domain
2609 * would not overlap with any domains computed before.
2610 * Similary, the unrolled domains may have some constraints removed and
2611 * may therefore also be larger than specified by the user.
2613 * If anything is left after handling separate, unroll and atomic,
2614 * we split it up into basic sets and append the basic sets to domains->list.
2616 static int compute_partial_domains(struct isl_codegen_domains *domains,
2617 __isl_take isl_set *class_domain)
2619 isl_basic_set_list *list;
2620 isl_set *domain;
2622 class_domain = isl_set_subtract(class_domain,
2623 isl_set_copy(domains->done));
2624 domains->done = isl_set_union(domains->done,
2625 isl_set_copy(class_domain));
2627 class_domain = compute_atomic_domain(domains, class_domain);
2628 class_domain = compute_unroll_domains(domains, class_domain);
2630 domain = isl_set_copy(class_domain);
2632 if (compute_separate_domain(domains, domain) < 0)
2633 goto error;
2634 domain = isl_set_subtract(domain,
2635 isl_set_copy(domains->option[separate]));
2637 domain = isl_set_intersect(domain,
2638 isl_set_copy(domains->schedule_domain));
2640 domain = isl_ast_build_eliminate(domains->build, domain);
2641 domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2643 domain = isl_set_coalesce(domain);
2644 domain = isl_set_make_disjoint(domain);
2646 list = isl_basic_set_list_from_set(domain);
2647 domains->list = isl_basic_set_list_concat(domains->list, list);
2649 isl_set_free(class_domain);
2651 return 0;
2652 error:
2653 isl_set_free(domain);
2654 isl_set_free(class_domain);
2655 return -1;
2658 /* Split up the domain at the current depth into disjoint
2659 * basic sets for which code should be generated separately
2660 * for the separation class identified by "pnt".
2662 * We extract the corresponding class domain from domains->sep_class,
2663 * eliminate inner dimensions and pass control to compute_partial_domains.
2665 static int compute_class_domains(__isl_take isl_point *pnt, void *user)
2667 struct isl_codegen_domains *domains = user;
2668 isl_set *class_set;
2669 isl_set *domain;
2670 int disjoint;
2672 class_set = isl_set_from_point(pnt);
2673 domain = isl_map_domain(isl_map_intersect_range(
2674 isl_map_copy(domains->sep_class), class_set));
2675 domain = isl_ast_build_compute_gist(domains->build, domain);
2676 domain = isl_ast_build_eliminate(domains->build, domain);
2678 disjoint = isl_set_plain_is_disjoint(domain, domains->schedule_domain);
2679 if (disjoint < 0)
2680 return -1;
2681 if (disjoint) {
2682 isl_set_free(domain);
2683 return 0;
2686 return compute_partial_domains(domains, domain);
2689 /* Extract the domains at the current depth that should be atomic,
2690 * separated or unrolled and store them in option.
2692 * The domains specified by the user might overlap, so we make
2693 * them disjoint by subtracting earlier domains from later domains.
2695 static void compute_domains_init_options(isl_set *option[3],
2696 __isl_keep isl_ast_build *build)
2698 enum isl_ast_build_domain_type type, type2;
2700 for (type = atomic; type <= separate; ++type) {
2701 option[type] = isl_ast_build_get_option_domain(build, type);
2702 for (type2 = atomic; type2 < type; ++type2)
2703 option[type] = isl_set_subtract(option[type],
2704 isl_set_copy(option[type2]));
2707 option[unroll] = isl_set_coalesce(option[unroll]);
2708 option[unroll] = isl_set_make_disjoint(option[unroll]);
2711 /* Split up the domain at the current depth into disjoint
2712 * basic sets for which code should be generated separately,
2713 * based on the user-specified options.
2714 * Return the list of disjoint basic sets.
2716 * There are three kinds of domains that we need to keep track of.
2717 * - the "schedule domain" is the domain of "executed"
2718 * - the "class domain" is the domain corresponding to the currrent
2719 * separation class
2720 * - the "option domain" is the domain corresponding to one of the options
2721 * atomic, unroll or separate
2723 * We first consider the individial values of the separation classes
2724 * and split up the domain for each of them separately.
2725 * Finally, we consider the remainder. If no separation classes were
2726 * specified, then we call compute_partial_domains with the universe
2727 * "class_domain". Otherwise, we take the "schedule_domain" as "class_domain",
2728 * with inner dimensions removed. We do this because we want to
2729 * avoid computing the complement of the class domains (i.e., the difference
2730 * between the universe and domains->done).
2732 static __isl_give isl_basic_set_list *compute_domains(
2733 __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2735 struct isl_codegen_domains domains;
2736 isl_ctx *ctx;
2737 isl_set *domain;
2738 isl_union_set *schedule_domain;
2739 isl_set *classes;
2740 isl_space *space;
2741 int n_param;
2742 enum isl_ast_build_domain_type type;
2743 int empty;
2745 if (!executed)
2746 return NULL;
2748 ctx = isl_union_map_get_ctx(executed);
2749 domains.list = isl_basic_set_list_alloc(ctx, 0);
2751 schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
2752 domain = isl_set_from_union_set(schedule_domain);
2754 compute_domains_init_options(domains.option, build);
2756 domains.sep_class = isl_ast_build_get_separation_class(build);
2757 classes = isl_map_range(isl_map_copy(domains.sep_class));
2758 n_param = isl_set_dim(classes, isl_dim_param);
2759 classes = isl_set_project_out(classes, isl_dim_param, 0, n_param);
2761 space = isl_set_get_space(domain);
2762 domains.build = build;
2763 domains.schedule_domain = isl_set_copy(domain);
2764 domains.executed = executed;
2765 domains.done = isl_set_empty(space);
2767 if (isl_set_foreach_point(classes, &compute_class_domains, &domains) < 0)
2768 domains.list = isl_basic_set_list_free(domains.list);
2769 isl_set_free(classes);
2771 empty = isl_set_is_empty(domains.done);
2772 if (empty < 0) {
2773 domains.list = isl_basic_set_list_free(domains.list);
2774 domain = isl_set_free(domain);
2775 } else if (empty) {
2776 isl_set_free(domain);
2777 domain = isl_set_universe(isl_set_get_space(domains.done));
2778 } else {
2779 domain = isl_ast_build_eliminate(build, domain);
2781 if (compute_partial_domains(&domains, domain) < 0)
2782 domains.list = isl_basic_set_list_free(domains.list);
2784 isl_set_free(domains.schedule_domain);
2785 isl_set_free(domains.done);
2786 isl_map_free(domains.sep_class);
2787 for (type = atomic; type <= separate; ++type)
2788 isl_set_free(domains.option[type]);
2790 return domains.list;
2793 /* Generate code for a single component, after shifting (if any)
2794 * has been applied.
2796 * We first split up the domain at the current depth into disjoint
2797 * basic sets based on the user-specified options.
2798 * Then we generated code for each of them and concatenate the results.
2800 static __isl_give isl_ast_graft_list *generate_shifted_component(
2801 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
2803 isl_basic_set_list *domain_list;
2804 isl_ast_graft_list *list = NULL;
2806 domain_list = compute_domains(executed, build);
2807 list = generate_parallel_domains(domain_list, executed, build);
2809 isl_basic_set_list_free(domain_list);
2810 isl_union_map_free(executed);
2811 isl_ast_build_free(build);
2813 return list;
2816 struct isl_set_map_pair {
2817 isl_set *set;
2818 isl_map *map;
2821 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2822 * of indices into the "domain" array,
2823 * return the union of the "map" fields of the elements
2824 * indexed by the first "n" elements of "order".
2826 static __isl_give isl_union_map *construct_component_executed(
2827 struct isl_set_map_pair *domain, int *order, int n)
2829 int i;
2830 isl_map *map;
2831 isl_union_map *executed;
2833 map = isl_map_copy(domain[order[0]].map);
2834 executed = isl_union_map_from_map(map);
2835 for (i = 1; i < n; ++i) {
2836 map = isl_map_copy(domain[order[i]].map);
2837 executed = isl_union_map_add_map(executed, map);
2840 return executed;
2843 /* Generate code for a single component, after shifting (if any)
2844 * has been applied.
2846 * The component inverse schedule is specified as the "map" fields
2847 * of the elements of "domain" indexed by the first "n" elements of "order".
2849 static __isl_give isl_ast_graft_list *generate_shifted_component_from_list(
2850 struct isl_set_map_pair *domain, int *order, int n,
2851 __isl_take isl_ast_build *build)
2853 isl_union_map *executed;
2855 executed = construct_component_executed(domain, order, n);
2856 return generate_shifted_component(executed, build);
2859 /* Does set dimension "pos" of "set" have an obviously fixed value?
2861 static int dim_is_fixed(__isl_keep isl_set *set, int pos)
2863 int fixed;
2864 isl_val *v;
2866 v = isl_set_plain_get_val_if_fixed(set, isl_dim_set, pos);
2867 if (!v)
2868 return -1;
2869 fixed = !isl_val_is_nan(v);
2870 isl_val_free(v);
2872 return fixed;
2875 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2876 * of indices into the "domain" array,
2877 * do all (except for at most one) of the "set" field of the elements
2878 * indexed by the first "n" elements of "order" have a fixed value
2879 * at position "depth"?
2881 static int at_most_one_non_fixed(struct isl_set_map_pair *domain,
2882 int *order, int n, int depth)
2884 int i;
2885 int non_fixed = -1;
2887 for (i = 0; i < n; ++i) {
2888 int f;
2890 f = dim_is_fixed(domain[order[i]].set, depth);
2891 if (f < 0)
2892 return -1;
2893 if (f)
2894 continue;
2895 if (non_fixed >= 0)
2896 return 0;
2897 non_fixed = i;
2900 return 1;
2903 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2904 * of indices into the "domain" array,
2905 * eliminate the inner dimensions from the "set" field of the elements
2906 * indexed by the first "n" elements of "order", provided the current
2907 * dimension does not have a fixed value.
2909 * Return the index of the first element in "order" with a corresponding
2910 * "set" field that does not have an (obviously) fixed value.
2912 static int eliminate_non_fixed(struct isl_set_map_pair *domain,
2913 int *order, int n, int depth, __isl_keep isl_ast_build *build)
2915 int i;
2916 int base = -1;
2918 for (i = n - 1; i >= 0; --i) {
2919 int f;
2920 f = dim_is_fixed(domain[order[i]].set, depth);
2921 if (f < 0)
2922 return -1;
2923 if (f)
2924 continue;
2925 domain[order[i]].set = isl_ast_build_eliminate_inner(build,
2926 domain[order[i]].set);
2927 base = i;
2930 return base;
2933 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2934 * of indices into the "domain" array,
2935 * find the element of "domain" (amongst those indexed by the first "n"
2936 * elements of "order") with the "set" field that has the smallest
2937 * value for the current iterator.
2939 * Note that the domain with the smallest value may depend on the parameters
2940 * and/or outer loop dimension. Since the result of this function is only
2941 * used as heuristic, we only make a reasonable attempt at finding the best
2942 * domain, one that should work in case a single domain provides the smallest
2943 * value for the current dimension over all values of the parameters
2944 * and outer dimensions.
2946 * In particular, we compute the smallest value of the first domain
2947 * and replace it by that of any later domain if that later domain
2948 * has a smallest value that is smaller for at least some value
2949 * of the parameters and outer dimensions.
2951 static int first_offset(struct isl_set_map_pair *domain, int *order, int n,
2952 __isl_keep isl_ast_build *build)
2954 int i;
2955 isl_map *min_first;
2956 int first = 0;
2958 min_first = isl_ast_build_map_to_iterator(build,
2959 isl_set_copy(domain[order[0]].set));
2960 min_first = isl_map_lexmin(min_first);
2962 for (i = 1; i < n; ++i) {
2963 isl_map *min, *test;
2964 int empty;
2966 min = isl_ast_build_map_to_iterator(build,
2967 isl_set_copy(domain[order[i]].set));
2968 min = isl_map_lexmin(min);
2969 test = isl_map_copy(min);
2970 test = isl_map_apply_domain(isl_map_copy(min_first), test);
2971 test = isl_map_order_lt(test, isl_dim_in, 0, isl_dim_out, 0);
2972 empty = isl_map_is_empty(test);
2973 isl_map_free(test);
2974 if (empty >= 0 && !empty) {
2975 isl_map_free(min_first);
2976 first = i;
2977 min_first = min;
2978 } else
2979 isl_map_free(min);
2981 if (empty < 0)
2982 break;
2985 isl_map_free(min_first);
2987 return i < n ? -1 : first;
2990 /* Construct a shifted inverse schedule based on the original inverse schedule,
2991 * the stride and the offset.
2993 * The original inverse schedule is specified as the "map" fields
2994 * of the elements of "domain" indexed by the first "n" elements of "order".
2996 * "stride" and "offset" are such that the difference
2997 * between the values of the current dimension of domain "i"
2998 * and the values of the current dimension for some reference domain are
2999 * equal to
3001 * stride * integer + offset[i]
3003 * Moreover, 0 <= offset[i] < stride.
3005 * For each domain, we create a map
3007 * { [..., j, ...] -> [..., j - offset[i], offset[i], ....] }
3009 * where j refers to the current dimension and the other dimensions are
3010 * unchanged, and apply this map to the original schedule domain.
3012 * For example, for the original schedule
3014 * { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3016 * and assuming the offset is 0 for the A domain and 1 for the B domain,
3017 * we apply the mapping
3019 * { [j] -> [j, 0] }
3021 * to the schedule of the "A" domain and the mapping
3023 * { [j - 1] -> [j, 1] }
3025 * to the schedule of the "B" domain.
3028 * Note that after the transformation, the differences between pairs
3029 * of values of the current dimension over all domains are multiples
3030 * of stride and that we have therefore exposed the stride.
3033 * To see that the mapping preserves the lexicographic order,
3034 * first note that each of the individual maps above preserves the order.
3035 * If the value of the current iterator is j1 in one domain and j2 in another,
3036 * then if j1 = j2, we know that the same map is applied to both domains
3037 * and the order is preserved.
3038 * Otherwise, let us assume, without loss of generality, that j1 < j2.
3039 * If c1 >= c2 (with c1 and c2 the corresponding offsets), then
3041 * j1 - c1 < j2 - c2
3043 * and the order is preserved.
3044 * If c1 < c2, then we know
3046 * 0 <= c2 - c1 < s
3048 * We also have
3050 * j2 - j1 = n * s + r
3052 * with n >= 0 and 0 <= r < s.
3053 * In other words, r = c2 - c1.
3054 * If n > 0, then
3056 * j1 - c1 < j2 - c2
3058 * If n = 0, then
3060 * j1 - c1 = j2 - c2
3062 * and so
3064 * (j1 - c1, c1) << (j2 - c2, c2)
3066 * with "<<" the lexicographic order, proving that the order is preserved
3067 * in all cases.
3069 static __isl_give isl_union_map *contruct_shifted_executed(
3070 struct isl_set_map_pair *domain, int *order, int n,
3071 __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3072 __isl_take isl_ast_build *build)
3074 int i;
3075 isl_union_map *executed;
3076 isl_space *space;
3077 isl_map *map;
3078 int depth;
3079 isl_constraint *c;
3081 depth = isl_ast_build_get_depth(build);
3082 space = isl_ast_build_get_space(build, 1);
3083 executed = isl_union_map_empty(isl_space_copy(space));
3084 space = isl_space_map_from_set(space);
3085 map = isl_map_identity(isl_space_copy(space));
3086 map = isl_map_eliminate(map, isl_dim_out, depth, 1);
3087 map = isl_map_insert_dims(map, isl_dim_out, depth + 1, 1);
3088 space = isl_space_insert_dims(space, isl_dim_out, depth + 1, 1);
3090 c = isl_equality_alloc(isl_local_space_from_space(space));
3091 c = isl_constraint_set_coefficient_si(c, isl_dim_in, depth, 1);
3092 c = isl_constraint_set_coefficient_si(c, isl_dim_out, depth, -1);
3094 for (i = 0; i < n; ++i) {
3095 isl_map *map_i;
3096 isl_val *v;
3098 v = isl_multi_val_get_val(offset, i);
3099 if (!v)
3100 break;
3101 map_i = isl_map_copy(map);
3102 map_i = isl_map_fix_val(map_i, isl_dim_out, depth + 1,
3103 isl_val_copy(v));
3104 v = isl_val_neg(v);
3105 c = isl_constraint_set_constant_val(c, v);
3106 map_i = isl_map_add_constraint(map_i, isl_constraint_copy(c));
3108 map_i = isl_map_apply_domain(isl_map_copy(domain[order[i]].map),
3109 map_i);
3110 executed = isl_union_map_add_map(executed, map_i);
3113 isl_constraint_free(c);
3114 isl_map_free(map);
3116 if (i < n)
3117 executed = isl_union_map_free(executed);
3119 return executed;
3122 /* Generate code for a single component, after exposing the stride,
3123 * given that the schedule domain is "shifted strided".
3125 * The component inverse schedule is specified as the "map" fields
3126 * of the elements of "domain" indexed by the first "n" elements of "order".
3128 * The schedule domain being "shifted strided" means that the differences
3129 * between the values of the current dimension of domain "i"
3130 * and the values of the current dimension for some reference domain are
3131 * equal to
3133 * stride * integer + offset[i]
3135 * We first look for the domain with the "smallest" value for the current
3136 * dimension and adjust the offsets such that the offset of the "smallest"
3137 * domain is equal to zero. The other offsets are reduced modulo stride.
3139 * Based on this information, we construct a new inverse schedule in
3140 * contruct_shifted_executed that exposes the stride.
3141 * Since this involves the introduction of a new schedule dimension,
3142 * the build needs to be changed accodingly.
3143 * After computing the AST, the newly introduced dimension needs
3144 * to be removed again from the list of grafts. We do this by plugging
3145 * in a mapping that represents the new schedule domain in terms of the
3146 * old schedule domain.
3148 static __isl_give isl_ast_graft_list *generate_shift_component(
3149 struct isl_set_map_pair *domain, int *order, int n,
3150 __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3151 __isl_take isl_ast_build *build)
3153 isl_ast_graft_list *list;
3154 int first;
3155 int depth;
3156 isl_ctx *ctx;
3157 isl_val *val;
3158 isl_multi_val *mv;
3159 isl_space *space;
3160 isl_multi_aff *ma, *zero;
3161 isl_union_map *executed;
3163 ctx = isl_ast_build_get_ctx(build);
3164 depth = isl_ast_build_get_depth(build);
3166 first = first_offset(domain, order, n, build);
3167 if (first < 0)
3168 goto error;
3170 mv = isl_multi_val_copy(offset);
3171 val = isl_multi_val_get_val(offset, first);
3172 val = isl_val_neg(val);
3173 mv = isl_multi_val_add_val(mv, val);
3174 mv = isl_multi_val_mod_val(mv, isl_val_copy(stride));
3176 executed = contruct_shifted_executed(domain, order, n, stride, mv,
3177 build);
3178 space = isl_ast_build_get_space(build, 1);
3179 space = isl_space_map_from_set(space);
3180 ma = isl_multi_aff_identity(isl_space_copy(space));
3181 space = isl_space_from_domain(isl_space_domain(space));
3182 space = isl_space_add_dims(space, isl_dim_out, 1);
3183 zero = isl_multi_aff_zero(space);
3184 ma = isl_multi_aff_range_splice(ma, depth + 1, zero);
3185 build = isl_ast_build_insert_dim(build, depth + 1);
3186 list = generate_shifted_component(executed, build);
3188 list = isl_ast_graft_list_preimage_multi_aff(list, ma);
3190 isl_multi_val_free(mv);
3192 return list;
3193 error:
3194 isl_ast_build_free(build);
3195 return NULL;
3198 /* Generate code for a single component.
3200 * The component inverse schedule is specified as the "map" fields
3201 * of the elements of "domain" indexed by the first "n" elements of "order".
3203 * This function may modify the "set" fields of "domain".
3205 * Before proceeding with the actual code generation for the component,
3206 * we first check if there are any "shifted" strides, meaning that
3207 * the schedule domains of the individual domains are all strided,
3208 * but that they have different offsets, resulting in the union
3209 * of schedule domains not being strided anymore.
3211 * The simplest example is the schedule
3213 * { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3215 * Both schedule domains are strided, but their union is not.
3216 * This function detects such cases and then rewrites the schedule to
3218 * { A[i] -> [2i, 0]: 0 <= i < 10; B[i] -> [2i, 1] : 0 <= i < 10 }
3220 * In the new schedule, the schedule domains have the same offset (modulo
3221 * the stride), ensuring that the union of schedule domains is also strided.
3224 * If there is only a single domain in the component, then there is
3225 * nothing to do. Similarly, if the current schedule dimension has
3226 * a fixed value for almost all domains then there is nothing to be done.
3227 * In particular, we need at least two domains where the current schedule
3228 * dimension does not have a fixed value.
3229 * Finally, if any of the options refer to the current schedule dimension,
3230 * then we bail out as well. It would be possible to reformulate the options
3231 * in terms of the new schedule domain, but that would introduce constraints
3232 * that separate the domains in the options and that is something we would
3233 * like to avoid.
3236 * To see if there is any shifted stride, we look at the differences
3237 * between the values of the current dimension in pairs of domains
3238 * for equal values of outer dimensions. These differences should be
3239 * of the form
3241 * m x + r
3243 * with "m" the stride and "r" a constant. Note that we cannot perform
3244 * this analysis on individual domains as the lower bound in each domain
3245 * may depend on parameters or outer dimensions and so the current dimension
3246 * itself may not have a fixed remainder on division by the stride.
3248 * In particular, we compare the first domain that does not have an
3249 * obviously fixed value for the current dimension to itself and all
3250 * other domains and collect the offsets and the gcd of the strides.
3251 * If the gcd becomes one, then we failed to find shifted strides.
3252 * If the gcd is zero, then the differences were all fixed, meaning
3253 * that some domains had non-obviously fixed values for the current dimension.
3254 * If all the offsets are the same (for those domains that do not have
3255 * an obviously fixed value for the current dimension), then we do not
3256 * apply the transformation.
3257 * If none of the domains were skipped, then there is nothing to do.
3258 * If some of them were skipped, then if we apply separation, the schedule
3259 * domain should get split in pieces with a (non-shifted) stride.
3261 * Otherwise, we apply a shift to expose the stride in
3262 * generate_shift_component.
3264 static __isl_give isl_ast_graft_list *generate_component(
3265 struct isl_set_map_pair *domain, int *order, int n,
3266 __isl_take isl_ast_build *build)
3268 int i, d;
3269 int depth;
3270 isl_ctx *ctx;
3271 isl_map *map;
3272 isl_set *deltas;
3273 isl_val *gcd = NULL;
3274 isl_multi_val *mv;
3275 int fixed, skip;
3276 int base;
3277 isl_ast_graft_list *list;
3278 int res = 0;
3280 depth = isl_ast_build_get_depth(build);
3282 skip = n == 1;
3283 if (skip >= 0 && !skip)
3284 skip = at_most_one_non_fixed(domain, order, n, depth);
3285 if (skip >= 0 && !skip)
3286 skip = isl_ast_build_options_involve_depth(build);
3287 if (skip < 0)
3288 goto error;
3289 if (skip)
3290 return generate_shifted_component_from_list(domain,
3291 order, n, build);
3293 base = eliminate_non_fixed(domain, order, n, depth, build);
3294 if (base < 0)
3295 goto error;
3297 ctx = isl_ast_build_get_ctx(build);
3299 mv = isl_multi_val_zero(isl_space_set_alloc(ctx, 0, n));
3301 fixed = 1;
3302 for (i = 0; i < n; ++i) {
3303 isl_val *r, *m;
3305 map = isl_map_from_domain_and_range(
3306 isl_set_copy(domain[order[base]].set),
3307 isl_set_copy(domain[order[i]].set));
3308 for (d = 0; d < depth; ++d)
3309 map = isl_map_equate(map, isl_dim_in, d,
3310 isl_dim_out, d);
3311 deltas = isl_map_deltas(map);
3312 res = isl_set_dim_residue_class_val(deltas, depth, &m, &r);
3313 isl_set_free(deltas);
3314 if (res < 0)
3315 break;
3317 if (i == 0)
3318 gcd = m;
3319 else
3320 gcd = isl_val_gcd(gcd, m);
3321 if (isl_val_is_one(gcd)) {
3322 isl_val_free(r);
3323 break;
3325 mv = isl_multi_val_set_val(mv, i, r);
3327 res = dim_is_fixed(domain[order[i]].set, depth);
3328 if (res < 0)
3329 break;
3330 if (res)
3331 continue;
3333 if (fixed && i > base) {
3334 isl_val *a, *b;
3335 a = isl_multi_val_get_val(mv, i);
3336 b = isl_multi_val_get_val(mv, base);
3337 if (isl_val_ne(a, b))
3338 fixed = 0;
3339 isl_val_free(a);
3340 isl_val_free(b);
3344 if (res < 0 || !gcd) {
3345 isl_ast_build_free(build);
3346 list = NULL;
3347 } else if (i < n || fixed || isl_val_is_zero(gcd)) {
3348 list = generate_shifted_component_from_list(domain,
3349 order, n, build);
3350 } else {
3351 list = generate_shift_component(domain, order, n, gcd, mv,
3352 build);
3355 isl_val_free(gcd);
3356 isl_multi_val_free(mv);
3358 return list;
3359 error:
3360 isl_ast_build_free(build);
3361 return NULL;
3364 /* Store both "map" itself and its domain in the
3365 * structure pointed to by *next and advance to the next array element.
3367 static int extract_domain(__isl_take isl_map *map, void *user)
3369 struct isl_set_map_pair **next = user;
3371 (*next)->map = isl_map_copy(map);
3372 (*next)->set = isl_map_domain(map);
3373 (*next)++;
3375 return 0;
3378 /* Internal data for any_scheduled_after.
3380 * "depth" is the number of loops that have already been generated
3381 * "group_coscheduled" is a local copy of options->ast_build_group_coscheduled
3382 * "domain" is an array of set-map pairs corresponding to the different
3383 * iteration domains. The set is the schedule domain, i.e., the domain
3384 * of the inverse schedule, while the map is the inverse schedule itself.
3386 struct isl_any_scheduled_after_data {
3387 int depth;
3388 int group_coscheduled;
3389 struct isl_set_map_pair *domain;
3392 /* Is any element of domain "i" scheduled after any element of domain "j"
3393 * (for a common iteration of the first data->depth loops)?
3395 * data->domain[i].set contains the domain of the inverse schedule
3396 * for domain "i", i.e., elements in the schedule domain.
3398 * If data->group_coscheduled is set, then we also return 1 if there
3399 * is any pair of elements in the two domains that are scheduled together.
3401 static int any_scheduled_after(int i, int j, void *user)
3403 struct isl_any_scheduled_after_data *data = user;
3404 int dim = isl_set_dim(data->domain[i].set, isl_dim_set);
3405 int pos;
3407 for (pos = data->depth; pos < dim; ++pos) {
3408 int follows;
3410 follows = isl_set_follows_at(data->domain[i].set,
3411 data->domain[j].set, pos);
3413 if (follows < -1)
3414 return -1;
3415 if (follows > 0)
3416 return 1;
3417 if (follows < 0)
3418 return 0;
3421 return data->group_coscheduled;
3424 /* Look for independent components at the current depth and generate code
3425 * for each component separately. The resulting lists of grafts are
3426 * merged in an attempt to combine grafts with identical guards.
3428 * Code for two domains can be generated separately if all the elements
3429 * of one domain are scheduled before (or together with) all the elements
3430 * of the other domain. We therefore consider the graph with as nodes
3431 * the domains and an edge between two nodes if any element of the first
3432 * node is scheduled after any element of the second node.
3433 * If the ast_build_group_coscheduled is set, then we also add an edge if
3434 * there is any pair of elements in the two domains that are scheduled
3435 * together.
3436 * Code is then generated (by generate_component)
3437 * for each of the strongly connected components in this graph
3438 * in their topological order.
3440 * Since the test is performed on the domain of the inverse schedules of
3441 * the different domains, we precompute these domains and store
3442 * them in data.domain.
3444 static __isl_give isl_ast_graft_list *generate_components(
3445 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3447 int i;
3448 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3449 int n = isl_union_map_n_map(executed);
3450 struct isl_any_scheduled_after_data data;
3451 struct isl_set_map_pair *next;
3452 struct isl_tarjan_graph *g = NULL;
3453 isl_ast_graft_list *list = NULL;
3454 int n_domain = 0;
3456 data.domain = isl_calloc_array(ctx, struct isl_set_map_pair, n);
3457 if (!data.domain)
3458 goto error;
3459 n_domain = n;
3461 next = data.domain;
3462 if (isl_union_map_foreach_map(executed, &extract_domain, &next) < 0)
3463 goto error;
3465 if (!build)
3466 goto error;
3467 data.depth = isl_ast_build_get_depth(build);
3468 data.group_coscheduled = isl_options_get_ast_build_group_coscheduled(ctx);
3469 g = isl_tarjan_graph_init(ctx, n, &any_scheduled_after, &data);
3471 list = isl_ast_graft_list_alloc(ctx, 0);
3473 i = 0;
3474 while (list && n) {
3475 isl_ast_graft_list *list_c;
3476 int first = i;
3478 if (g->order[i] == -1)
3479 isl_die(ctx, isl_error_internal, "cannot happen",
3480 goto error);
3481 ++i; --n;
3482 while (g->order[i] != -1) {
3483 ++i; --n;
3486 list_c = generate_component(data.domain,
3487 g->order + first, i - first,
3488 isl_ast_build_copy(build));
3489 list = isl_ast_graft_list_merge(list, list_c, build);
3491 ++i;
3494 if (0)
3495 error: list = isl_ast_graft_list_free(list);
3496 isl_tarjan_graph_free(g);
3497 for (i = 0; i < n_domain; ++i) {
3498 isl_map_free(data.domain[i].map);
3499 isl_set_free(data.domain[i].set);
3501 free(data.domain);
3502 isl_union_map_free(executed);
3503 isl_ast_build_free(build);
3505 return list;
3508 /* Generate code for the next level (and all inner levels).
3510 * If "executed" is empty, i.e., no code needs to be generated,
3511 * then we return an empty list.
3513 * If we have already generated code for all loop levels, then we pass
3514 * control to generate_inner_level.
3516 * If "executed" lives in a single space, i.e., if code needs to be
3517 * generated for a single domain, then there can only be a single
3518 * component and we go directly to generate_shifted_component.
3519 * Otherwise, we call generate_components to detect the components
3520 * and to call generate_component on each of them separately.
3522 static __isl_give isl_ast_graft_list *generate_next_level(
3523 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3525 int depth;
3527 if (!build || !executed)
3528 goto error;
3530 if (isl_union_map_is_empty(executed)) {
3531 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3532 isl_union_map_free(executed);
3533 isl_ast_build_free(build);
3534 return isl_ast_graft_list_alloc(ctx, 0);
3537 depth = isl_ast_build_get_depth(build);
3538 if (depth >= isl_set_dim(build->domain, isl_dim_set))
3539 return generate_inner_level(executed, build);
3541 if (isl_union_map_n_map(executed) == 1)
3542 return generate_shifted_component(executed, build);
3544 return generate_components(executed, build);
3545 error:
3546 isl_union_map_free(executed);
3547 isl_ast_build_free(build);
3548 return NULL;
3551 /* Internal data structure used by isl_ast_build_ast_from_schedule.
3552 * internal, executed and build are the inputs to generate_code.
3553 * list collects the output.
3555 struct isl_generate_code_data {
3556 int internal;
3557 isl_union_map *executed;
3558 isl_ast_build *build;
3560 isl_ast_graft_list *list;
3563 /* Given an inverse schedule in terms of the external build schedule, i.e.,
3565 * [E -> S] -> D
3567 * with E the external build schedule and S the additional schedule "space",
3568 * reformulate the inverse schedule in terms of the internal schedule domain,
3569 * i.e., return
3571 * [I -> S] -> D
3573 * We first obtain a mapping
3575 * I -> E
3577 * take the inverse and the product with S -> S, resulting in
3579 * [I -> S] -> [E -> S]
3581 * Applying the map to the input produces the desired result.
3583 static __isl_give isl_union_map *internal_executed(
3584 __isl_take isl_union_map *executed, __isl_keep isl_space *space,
3585 __isl_keep isl_ast_build *build)
3587 isl_map *id, *proj;
3589 proj = isl_ast_build_get_schedule_map(build);
3590 proj = isl_map_reverse(proj);
3591 space = isl_space_map_from_set(isl_space_copy(space));
3592 id = isl_map_identity(space);
3593 proj = isl_map_product(proj, id);
3594 executed = isl_union_map_apply_domain(executed,
3595 isl_union_map_from_map(proj));
3596 return executed;
3599 /* Generate an AST that visits the elements in the range of data->executed
3600 * in the relative order specified by the corresponding image element(s)
3601 * for those image elements that belong to "set".
3602 * Add the result to data->list.
3604 * The caller ensures that "set" is a universe domain.
3605 * "space" is the space of the additional part of the schedule.
3606 * It is equal to the space of "set" if build->domain is parametric.
3607 * Otherwise, it is equal to the range of the wrapped space of "set".
3609 * If the build space is not parametric and if isl_ast_build_ast_from_schedule
3610 * was called from an outside user (data->internal not set), then
3611 * the (inverse) schedule refers to the external build domain and needs to
3612 * be transformed to refer to the internal build domain.
3614 * The build is extended to include the additional part of the schedule.
3615 * If the original build space was not parametric, then the options
3616 * in data->build refer only to the additional part of the schedule
3617 * and they need to be adjusted to refer to the complete AST build
3618 * domain.
3620 * After having adjusted inverse schedule and build, we start generating
3621 * code with the outer loop of the current code generation
3622 * in generate_next_level.
3624 * If the original build space was not parametric, we undo the embedding
3625 * on the resulting isl_ast_node_list so that it can be used within
3626 * the outer AST build.
3628 static int generate_code_in_space(struct isl_generate_code_data *data,
3629 __isl_take isl_set *set, __isl_take isl_space *space)
3631 isl_union_map *executed;
3632 isl_ast_build *build;
3633 isl_ast_graft_list *list;
3634 int embed;
3636 executed = isl_union_map_copy(data->executed);
3637 executed = isl_union_map_intersect_domain(executed,
3638 isl_union_set_from_set(set));
3640 embed = !isl_set_is_params(data->build->domain);
3641 if (embed && !data->internal)
3642 executed = internal_executed(executed, space, data->build);
3644 build = isl_ast_build_copy(data->build);
3645 build = isl_ast_build_product(build, space);
3647 list = generate_next_level(executed, build);
3649 list = isl_ast_graft_list_unembed(list, embed);
3651 data->list = isl_ast_graft_list_concat(data->list, list);
3653 return 0;
3656 /* Generate an AST that visits the elements in the range of data->executed
3657 * in the relative order specified by the corresponding domain element(s)
3658 * for those domain elements that belong to "set".
3659 * Add the result to data->list.
3661 * The caller ensures that "set" is a universe domain.
3663 * If the build space S is not parametric, then the space of "set"
3664 * need to be a wrapped relation with S as domain. That is, it needs
3665 * to be of the form
3667 * [S -> T]
3669 * Check this property and pass control to generate_code_in_space
3670 * passing along T.
3671 * If the build space is not parametric, then T is the space of "set".
3673 static int generate_code_set(__isl_take isl_set *set, void *user)
3675 struct isl_generate_code_data *data = user;
3676 isl_space *space, *build_space;
3677 int is_domain;
3679 space = isl_set_get_space(set);
3681 if (isl_set_is_params(data->build->domain))
3682 return generate_code_in_space(data, set, space);
3684 build_space = isl_ast_build_get_space(data->build, data->internal);
3685 space = isl_space_unwrap(space);
3686 is_domain = isl_space_is_domain(build_space, space);
3687 isl_space_free(build_space);
3688 space = isl_space_range(space);
3690 if (is_domain < 0)
3691 goto error;
3692 if (!is_domain)
3693 isl_die(isl_set_get_ctx(set), isl_error_invalid,
3694 "invalid nested schedule space", goto error);
3696 return generate_code_in_space(data, set, space);
3697 error:
3698 isl_set_free(set);
3699 isl_space_free(space);
3700 return -1;
3703 /* Generate an AST that visits the elements in the range of "executed"
3704 * in the relative order specified by the corresponding domain element(s).
3706 * "build" is an isl_ast_build that has either been constructed by
3707 * isl_ast_build_from_context or passed to a callback set by
3708 * isl_ast_build_set_create_leaf.
3709 * In the first case, the space of the isl_ast_build is typically
3710 * a parametric space, although this is currently not enforced.
3711 * In the second case, the space is never a parametric space.
3712 * If the space S is not parametric, then the domain space(s) of "executed"
3713 * need to be wrapped relations with S as domain.
3715 * If the domain of "executed" consists of several spaces, then an AST
3716 * is generated for each of them (in arbitrary order) and the results
3717 * are concatenated.
3719 * If "internal" is set, then the domain "S" above refers to the internal
3720 * schedule domain representation. Otherwise, it refers to the external
3721 * representation, as returned by isl_ast_build_get_schedule_space.
3723 * We essentially run over all the spaces in the domain of "executed"
3724 * and call generate_code_set on each of them.
3726 static __isl_give isl_ast_graft_list *generate_code(
3727 __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
3728 int internal)
3730 isl_ctx *ctx;
3731 struct isl_generate_code_data data = { 0 };
3732 isl_space *space;
3733 isl_union_set *schedule_domain;
3734 isl_union_map *universe;
3736 if (!build)
3737 goto error;
3738 space = isl_ast_build_get_space(build, 1);
3739 space = isl_space_align_params(space,
3740 isl_union_map_get_space(executed));
3741 space = isl_space_align_params(space,
3742 isl_union_map_get_space(build->options));
3743 build = isl_ast_build_align_params(build, isl_space_copy(space));
3744 executed = isl_union_map_align_params(executed, space);
3745 if (!executed || !build)
3746 goto error;
3748 ctx = isl_ast_build_get_ctx(build);
3750 data.internal = internal;
3751 data.executed = executed;
3752 data.build = build;
3753 data.list = isl_ast_graft_list_alloc(ctx, 0);
3755 universe = isl_union_map_universe(isl_union_map_copy(executed));
3756 schedule_domain = isl_union_map_domain(universe);
3757 if (isl_union_set_foreach_set(schedule_domain, &generate_code_set,
3758 &data) < 0)
3759 data.list = isl_ast_graft_list_free(data.list);
3761 isl_union_set_free(schedule_domain);
3762 isl_union_map_free(executed);
3764 isl_ast_build_free(build);
3765 return data.list;
3766 error:
3767 isl_union_map_free(executed);
3768 isl_ast_build_free(build);
3769 return NULL;
3772 /* Generate an AST that visits the elements in the domain of "schedule"
3773 * in the relative order specified by the corresponding image element(s).
3775 * "build" is an isl_ast_build that has either been constructed by
3776 * isl_ast_build_from_context or passed to a callback set by
3777 * isl_ast_build_set_create_leaf.
3778 * In the first case, the space of the isl_ast_build is typically
3779 * a parametric space, although this is currently not enforced.
3780 * In the second case, the space is never a parametric space.
3781 * If the space S is not parametric, then the range space(s) of "schedule"
3782 * need to be wrapped relations with S as domain.
3784 * If the range of "schedule" consists of several spaces, then an AST
3785 * is generated for each of them (in arbitrary order) and the results
3786 * are concatenated.
3788 * We first initialize the local copies of the relevant options.
3789 * We do this here rather than when the isl_ast_build is created
3790 * because the options may have changed between the construction
3791 * of the isl_ast_build and the call to isl_generate_code.
3793 * The main computation is performed on an inverse schedule (with
3794 * the schedule domain in the domain and the elements to be executed
3795 * in the range) called "executed".
3797 __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
3798 __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
3800 isl_ast_graft_list *list;
3801 isl_ast_node *node;
3802 isl_union_map *executed;
3804 build = isl_ast_build_copy(build);
3805 build = isl_ast_build_set_single_valued(build, 0);
3806 schedule = isl_union_map_coalesce(schedule);
3807 executed = isl_union_map_reverse(schedule);
3808 list = generate_code(executed, isl_ast_build_copy(build), 0);
3809 node = isl_ast_node_from_graft_list(list, build);
3810 isl_ast_build_free(build);
3812 return node;