Merge branch 'maint'
[platform/upstream/isl.git] / isl_ast_codegen.c
1 /*
2  * Copyright 2012      Ecole Normale Superieure
3  *
4  * Use of this software is governed by the MIT license
5  *
6  * Written by Sven Verdoolaege,
7  * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
8  */
9
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>
21
22 /* Add the constraint to the list that "user" points to, if it is not
23  * a div constraint.
24  */
25 static int collect_constraint(__isl_take isl_constraint *constraint,
26         void *user)
27 {
28         isl_constraint_list **list = user;
29
30         if (isl_constraint_is_div_constraint(constraint))
31                 isl_constraint_free(constraint);
32         else
33                 *list = isl_constraint_list_add(*list, constraint);
34
35         return 0;
36 }
37
38 /* Extract the constraints of "bset" (except the div constraints)
39  * and collect them in an isl_constraint_list.
40  */
41 static __isl_give isl_constraint_list *isl_constraint_list_from_basic_set(
42         __isl_take isl_basic_set *bset)
43 {
44         int n;
45         isl_ctx *ctx;
46         isl_constraint_list *list;
47
48         if (!bset)
49                 return NULL;
50
51         ctx = isl_basic_set_get_ctx(bset);
52
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);
58
59         isl_basic_set_free(bset);
60         return list;
61 }
62
63 /* Data used in generate_domain.
64  *
65  * "build" is the input build.
66  * "list" collects the results.
67  */
68 struct isl_generate_domain_data {
69         isl_ast_build *build;
70
71         isl_ast_graft_list *list;
72 };
73
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);
80
81 /* Generate an AST for a single domain based on
82  * the (non single valued) inverse schedule "executed".
83  *
84  * We extend the schedule with the iteration domain
85  * and continue generating through a call to generate_code.
86  *
87  * In particular, if executed has the form
88  *
89  *      S -> D
90  *
91  * then we continue generating code on
92  *
93  *      [S -> D] -> D
94  *
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.
99  */
100 static int generate_non_single_valued(__isl_take isl_map *executed,
101         struct isl_generate_domain_data *data)
102 {
103         isl_map *identity;
104         isl_ast_build *build;
105         isl_ast_graft_list *list;
106
107         build = isl_ast_build_copy(data->build);
108
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);
112
113         list = generate_code(isl_union_map_from_map(executed), build, 1);
114
115         data->list = isl_ast_graft_list_concat(data->list, list);
116
117         return 0;
118 }
119
120 /* Call the at_each_domain callback, if requested by the user,
121  * after recording the current inverse schedule in the build.
122  */
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)
125 {
126         if (!graft || !build)
127                 return isl_ast_graft_free(graft);
128         if (!build->at_each_domain)
129                 return graft;
130
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);
136
137         graft->node = build->at_each_domain(graft->node,
138                                         build, build->at_each_domain_user);
139         isl_ast_build_free(build);
140
141         if (!graft->node)
142                 graft = isl_ast_graft_free(graft);
143
144         return graft;
145 }
146
147 /* Generate an AST for a single domain based on
148  * the inverse schedule "executed".
149  *
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.
169  *
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".
173  *
174  * If the user has set an at_each_domain callback, it is called
175  * on the constructed call expression node.
176  */
177 static int generate_domain(__isl_take isl_map *executed, void *user)
178 {
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;
185
186         executed = isl_map_intersect_domain(executed,
187                                             isl_set_copy(data->build->domain));
188
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);
201         }
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);
207
208         isl_map_free(executed);
209         graft = isl_ast_graft_add_guard(graft, guard, data->build);
210
211         list = isl_ast_graft_list_from_ast_graft(graft);
212         data->list = isl_ast_graft_list_concat(data->list, list);
213
214         return 0;
215 error:
216         isl_map_free(map);
217         isl_map_free(executed);
218         return -1;
219 }
220
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.
224  *
225  * Note that the node returned by the user may be an entire tree.
226  *
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.
232  */
233 static __isl_give isl_ast_graft_list *call_create_leaf(
234         __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
235 {
236         isl_ast_node *node;
237         isl_ast_graft *graft;
238         isl_ast_build *user_build;
239
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);
250 }
251
252 /* Generate an AST after having handled the complete schedule
253  * of this call to the code generator.
254  *
255  * If the user has specified a create_leaf callback, control
256  * is passed to the user in call_create_leaf.
257  *
258  * Otherwise, we generate one or more calls for each individual
259  * domain in generate_domain.
260  */
261 static __isl_give isl_ast_graft_list *generate_inner_level(
262         __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
263 {
264         isl_ctx *ctx;
265         struct isl_generate_domain_data data = { build };
266
267         if (!build || !executed)
268                 goto error;
269
270         if (build->create_leaf)
271                 return call_create_leaf(executed, build);
272
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);
277
278         if (0)
279 error:          data.list = NULL;
280         isl_ast_build_free(build);
281         isl_union_map_free(executed);
282         return data.list;
283 }
284
285 /* Call the before_each_for callback, if requested by the user.
286  */
287 static __isl_give isl_ast_node *before_each_for(__isl_take isl_ast_node *node,
288         __isl_keep isl_ast_build *build)
289 {
290         isl_id *id;
291
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;
299 }
300
301 /* Call the after_each_for callback, if requested by the user.
302  */
303 static __isl_give isl_ast_graft *after_each_for(__isl_keep isl_ast_graft *graft,
304         __isl_keep isl_ast_build *build)
305 {
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;
315 }
316
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.
322  */
323 static __isl_give isl_union_map *plug_in_values(
324         __isl_take isl_union_map *executed, __isl_keep isl_ast_build *build)
325 {
326         return isl_ast_build_substitute_values_union_map_domain(build,
327                                                                     executed);
328 }
329
330 /* Check if the constraint "c" is a lower bound on dimension "pos",
331  * an upper bound, or independent of dimension "pos".
332  */
333 static int constraint_type(isl_constraint *c, int pos)
334 {
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;
340 }
341
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".
346  */
347 static int cmp_constraint(__isl_keep isl_constraint *a,
348         __isl_keep isl_constraint *b, void *user)
349 {
350         int *depth = user;
351         int t1 = constraint_type(a, *depth);
352         int t2 = constraint_type(b, *depth);
353
354         return t1 - t2;
355 }
356
357 /* Extract a lower bound on dimension "pos" from constraint "c".
358  *
359  * If the constraint is of the form
360  *
361  *      a x + f(...) >= 0
362  *
363  * then we essentially return
364  *
365  *      l = ceil(-f(...)/a)
366  *
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
369  *
370  *      f + s a
371  *
372  * with f the offset and s the stride.
373  * We therefore compute
374  *
375  *      f + s * ceil((l - f)/s)
376  */
377 static __isl_give isl_aff *lower_bound(__isl_keep isl_constraint *c,
378         int pos, __isl_keep isl_ast_build *build)
379 {
380         isl_aff *aff;
381
382         aff = isl_constraint_get_bound(c, isl_dim_set, pos);
383         aff = isl_aff_ceil(aff);
384
385         if (isl_ast_build_has_stride(build, pos)) {
386                 isl_aff *offset;
387                 isl_int stride;
388
389                 isl_int_init(stride);
390
391                 offset = isl_ast_build_get_offset(build, pos);
392                 isl_ast_build_get_stride(build, pos, &stride);
393
394                 aff = isl_aff_sub(aff, isl_aff_copy(offset));
395                 aff = isl_aff_scale_down(aff, stride);
396                 aff = isl_aff_ceil(aff);
397                 aff = isl_aff_scale(aff, stride);
398                 aff = isl_aff_add(aff, offset);
399
400                 isl_int_clear(stride);
401         }
402
403         aff = isl_ast_build_compute_gist_aff(build, aff);
404
405         return aff;
406 }
407
408 /* Return the exact lower bound (or upper bound if "upper" is set)
409  * of "domain" as a piecewise affine expression.
410  *
411  * If we are computing a lower bound (of a strided dimension), then
412  * we need to make sure it is of the form
413  *
414  *      f + s a
415  *
416  * where f is the offset and s is the stride.
417  * We therefore need to include the stride constraint before computing
418  * the minimum.
419  */
420 static __isl_give isl_pw_aff *exact_bound(__isl_keep isl_set *domain,
421         __isl_keep isl_ast_build *build, int upper)
422 {
423         isl_set *stride;
424         isl_map *it_map;
425         isl_pw_aff *pa;
426         isl_pw_multi_aff *pma;
427
428         domain = isl_set_copy(domain);
429         if (!upper) {
430                 stride = isl_ast_build_get_stride_constraint(build);
431                 domain = isl_set_intersect(domain, stride);
432         }
433         it_map = isl_ast_build_map_to_iterator(build, domain);
434         if (upper)
435                 pma = isl_map_lexmax_pw_multi_aff(it_map);
436         else
437                 pma = isl_map_lexmin_pw_multi_aff(it_map);
438         pa = isl_pw_multi_aff_get_pw_aff(pma, 0);
439         isl_pw_multi_aff_free(pma);
440         pa = isl_ast_build_compute_gist_pw_aff(build, pa);
441         pa = isl_pw_aff_coalesce(pa);
442
443         return pa;
444 }
445
446 /* Extract a lower bound on dimension "pos" from each constraint
447  * in "constraints" and return the list of lower bounds.
448  * If "constraints" has zero elements, then we extract a lower bound
449  * from "domain" instead.
450  */
451 static __isl_give isl_pw_aff_list *lower_bounds(
452         __isl_keep isl_constraint_list *constraints, int pos,
453         __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
454 {
455         isl_ctx *ctx;
456         isl_pw_aff_list *list;
457         int i, n;
458
459         if (!build)
460                 return NULL;
461
462         n = isl_constraint_list_n_constraint(constraints);
463         if (n == 0) {
464                 isl_pw_aff *pa;
465                 pa = exact_bound(domain, build, 0);
466                 return isl_pw_aff_list_from_pw_aff(pa);
467         }
468
469         ctx = isl_ast_build_get_ctx(build);
470         list = isl_pw_aff_list_alloc(ctx,n);
471
472         for (i = 0; i < n; ++i) {
473                 isl_aff *aff;
474                 isl_constraint *c;
475
476                 c = isl_constraint_list_get_constraint(constraints, i);
477                 aff = lower_bound(c, pos, build);
478                 isl_constraint_free(c);
479                 list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
480         }
481
482         return list;
483 }
484
485 /* Extract an upper bound on dimension "pos" from each constraint
486  * in "constraints" and return the list of upper bounds.
487  * If "constraints" has zero elements, then we extract an upper bound
488  * from "domain" instead.
489  */
490 static __isl_give isl_pw_aff_list *upper_bounds(
491         __isl_keep isl_constraint_list *constraints, int pos,
492         __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
493 {
494         isl_ctx *ctx;
495         isl_pw_aff_list *list;
496         int i, n;
497
498         n = isl_constraint_list_n_constraint(constraints);
499         if (n == 0) {
500                 isl_pw_aff *pa;
501                 pa = exact_bound(domain, build, 1);
502                 return isl_pw_aff_list_from_pw_aff(pa);
503         }
504
505         ctx = isl_ast_build_get_ctx(build);
506         list = isl_pw_aff_list_alloc(ctx,n);
507
508         for (i = 0; i < n; ++i) {
509                 isl_aff *aff;
510                 isl_constraint *c;
511
512                 c = isl_constraint_list_get_constraint(constraints, i);
513                 aff = isl_constraint_get_bound(c, isl_dim_set, pos);
514                 isl_constraint_free(c);
515                 aff = isl_aff_floor(aff);
516                 list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
517         }
518
519         return list;
520 }
521
522 /* Return an isl_ast_expr that performs the reduction of type "type"
523  * on AST expressions corresponding to the elements in "list".
524  *
525  * The list is assumed to contain at least one element.
526  * If the list contains exactly one element, then the returned isl_ast_expr
527  * simply computes that affine expression.
528  */
529 static __isl_give isl_ast_expr *reduce_list(enum isl_ast_op_type type,
530         __isl_keep isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
531 {
532         int i, n;
533         isl_ctx *ctx;
534         isl_ast_expr *expr;
535
536         if (!list)
537                 return NULL;
538
539         n = isl_pw_aff_list_n_pw_aff(list);
540
541         if (n == 1)
542                 return isl_ast_build_expr_from_pw_aff_internal(build,
543                                 isl_pw_aff_list_get_pw_aff(list, 0));
544
545         ctx = isl_pw_aff_list_get_ctx(list);
546         expr = isl_ast_expr_alloc_op(ctx, type, n);
547         if (!expr)
548                 return NULL;
549
550         for (i = 0; i < n; ++i) {
551                 isl_ast_expr *expr_i;
552
553                 expr_i = isl_ast_build_expr_from_pw_aff_internal(build,
554                                 isl_pw_aff_list_get_pw_aff(list, i));
555                 if (!expr_i)
556                         return isl_ast_expr_free(expr);
557                 expr->u.op.args[i] = expr_i;
558         }
559
560         return expr;
561 }
562
563 /* Add a guard to "graft" based on "bound" in the case of a degenerate
564  * level (including the special case of an eliminated level).
565  *
566  * We eliminate the current dimension, simplify the result in the current
567  * build and add the result as guards to the graft.
568  *
569  * Note that we cannot simply drop the constraints on the current dimension
570  * even in the eliminated case, because the single affine expression may
571  * not be explicitly available in "bounds".  Moreover, the single affine
572  * expression may only be defined on a subset of the build domain,
573  * so we do in some cases need to insert a guard even in the eliminated case.
574  */
575 static __isl_give isl_ast_graft *add_degenerate_guard(
576         __isl_take isl_ast_graft *graft, __isl_keep isl_basic_set *bounds,
577         __isl_keep isl_ast_build *build)
578 {
579         int depth;
580         isl_set *dom;
581
582         depth = isl_ast_build_get_depth(build);
583
584         dom = isl_set_from_basic_set(isl_basic_set_copy(bounds));
585         if (isl_ast_build_has_stride(build, depth)) {
586                 isl_set *stride;
587
588                 stride = isl_ast_build_get_stride_constraint(build);
589                 dom = isl_set_intersect(dom, stride);
590         }
591         dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
592         dom = isl_ast_build_compute_gist(build, dom);
593
594         graft = isl_ast_graft_add_guard(graft, dom, build);
595
596         return graft;
597 }
598
599 /* Update "graft" based on "bounds" for the eliminated case.
600  *
601  * In the eliminated case, no for node is created, so we only need
602  * to check if "bounds" imply any guards that need to be inserted.
603  */
604 static __isl_give isl_ast_graft *refine_eliminated(
605         __isl_take isl_ast_graft *graft, __isl_keep isl_basic_set *bounds,
606         __isl_keep isl_ast_build *build)
607 {
608         return add_degenerate_guard(graft, bounds, build);
609 }
610
611 /* Update "graft" based on "bounds" and "sub_build" for the degenerate case.
612  *
613  * "build" is the build in which graft->node was created
614  * "sub_build" contains information about the current level itself,
615  * including the single value attained.
616  *
617  * We first set the initialization part of the for loop to the single
618  * value attained by the current dimension.
619  * The increment and condition are not strictly needed as the are known
620  * to be "1" and "iterator <= value" respectively.
621  * Then we set the size of the iterator and
622  * check if "bounds" imply any guards that need to be inserted.
623  */
624 static __isl_give isl_ast_graft *refine_degenerate(
625         __isl_take isl_ast_graft *graft, __isl_keep isl_basic_set *bounds,
626         __isl_keep isl_ast_build *build,
627         __isl_keep isl_ast_build *sub_build)
628 {
629         isl_pw_aff *value;
630
631         if (!graft || !sub_build)
632                 return isl_ast_graft_free(graft);
633
634         value = isl_pw_aff_copy(sub_build->value);
635
636         graft->node->u.f.init = isl_ast_build_expr_from_pw_aff_internal(build,
637                                                 value);
638         if (!graft->node->u.f.init)
639                 return isl_ast_graft_free(graft);
640
641         graft = add_degenerate_guard(graft, bounds, build);
642
643         return graft;
644 }
645
646 /* Return the intersection of constraints in "list" as a set.
647  */
648 static __isl_give isl_set *intersect_constraints(
649         __isl_keep isl_constraint_list *list)
650 {
651         int i, n;
652         isl_basic_set *bset;
653
654         n = isl_constraint_list_n_constraint(list);
655         if (n < 1)
656                 isl_die(isl_constraint_list_get_ctx(list), isl_error_internal,
657                         "expecting at least one constraint", return NULL);
658
659         bset = isl_basic_set_from_constraint(
660                                 isl_constraint_list_get_constraint(list, 0));
661         for (i = 1; i < n; ++i) {
662                 isl_basic_set *bset_i;
663
664                 bset_i = isl_basic_set_from_constraint(
665                                 isl_constraint_list_get_constraint(list, i));
666                 bset = isl_basic_set_intersect(bset, bset_i);
667         }
668
669         return isl_set_from_basic_set(bset);
670 }
671
672 /* Compute the constraints on the outer dimensions enforced by
673  * graft->node and add those constraints to graft->enforced,
674  * in case the upper bound is expressed as a set "upper".
675  *
676  * In particular, if l(...) is a lower bound in "lower", and
677  *
678  *      -a i + f(...) >= 0              or      a i <= f(...)
679  *
680  * is an upper bound ocnstraint on the current dimension i,
681  * then the for loop enforces the constraint
682  *
683  *      -a l(...) + f(...) >= 0         or      a l(...) <= f(...)
684  *
685  * We therefore simply take each lower bound in turn, plug it into
686  * the upper bounds and compute the intersection over all lower bounds.
687  *
688  * If a lower bound is a rational expression, then
689  * isl_basic_set_preimage_multi_aff will force this rational
690  * expression to have only integer values.  However, the loop
691  * itself does not enforce this integrality constraint.  We therefore
692  * use the ceil of the lower bounds instead of the lower bounds themselves.
693  * Other constraints will make sure that the for loop is only executed
694  * when each of the lower bounds attains an integral value.
695  * In particular, potentially rational values only occur in
696  * lower_bound if the offset is a (seemingly) rational expression,
697  * but then outer conditions will make sure that this rational expression
698  * only attains integer values.
699  */
700 static __isl_give isl_ast_graft *set_enforced_from_set(
701         __isl_take isl_ast_graft *graft,
702         __isl_keep isl_pw_aff_list *lower, int pos, __isl_keep isl_set *upper)
703 {
704         isl_space *space;
705         isl_basic_set *enforced;
706         isl_pw_multi_aff *pma;
707         int i, n;
708
709         if (!graft || !lower)
710                 return isl_ast_graft_free(graft);
711
712         space = isl_set_get_space(upper);
713         enforced = isl_basic_set_universe(isl_space_copy(space));
714
715         space = isl_space_map_from_set(space);
716         pma = isl_pw_multi_aff_identity(space);
717
718         n = isl_pw_aff_list_n_pw_aff(lower);
719         for (i = 0; i < n; ++i) {
720                 isl_pw_aff *pa;
721                 isl_set *enforced_i;
722                 isl_basic_set *hull;
723                 isl_pw_multi_aff *pma_i;
724
725                 pa = isl_pw_aff_list_get_pw_aff(lower, i);
726                 pa = isl_pw_aff_ceil(pa);
727                 pma_i = isl_pw_multi_aff_copy(pma);
728                 pma_i = isl_pw_multi_aff_set_pw_aff(pma_i, pos, pa);
729                 enforced_i = isl_set_copy(upper);
730                 enforced_i = isl_set_preimage_pw_multi_aff(enforced_i, pma_i);
731                 hull = isl_set_simple_hull(enforced_i);
732                 enforced = isl_basic_set_intersect(enforced, hull);
733         }
734
735         isl_pw_multi_aff_free(pma);
736
737         graft = isl_ast_graft_enforce(graft, enforced);
738
739         return graft;
740 }
741
742 /* Compute the constraints on the outer dimensions enforced by
743  * graft->node and add those constraints to graft->enforced,
744  * in case the upper bound is expressed as
745  * a list of affine expressions "upper".
746  *
747  * The enforced condition is that each lower bound expression is less
748  * than or equal to each upper bound expression.
749  */
750 static __isl_give isl_ast_graft *set_enforced_from_list(
751         __isl_take isl_ast_graft *graft,
752         __isl_keep isl_pw_aff_list *lower, __isl_keep isl_pw_aff_list *upper)
753 {
754         isl_set *cond;
755         isl_basic_set *enforced;
756
757         lower = isl_pw_aff_list_copy(lower);
758         upper = isl_pw_aff_list_copy(upper);
759         cond = isl_pw_aff_list_le_set(lower, upper);
760         enforced = isl_set_simple_hull(cond);
761         graft = isl_ast_graft_enforce(graft, enforced);
762
763         return graft;
764 }
765
766 /* Does "aff" have a negative constant term?
767  */
768 static int aff_constant_is_negative(__isl_take isl_set *set,
769         __isl_take isl_aff *aff, void *user)
770 {
771         int *neg = user;
772         isl_int v;
773
774         isl_int_init(v);
775         isl_aff_get_constant(aff, &v);
776         *neg = isl_int_is_neg(v);
777         isl_int_clear(v);
778         isl_set_free(set);
779         isl_aff_free(aff);
780
781         return *neg ? 0 : -1;
782 }
783
784 /* Does "pa" have a negative constant term over its entire domain?
785  */
786 static int pw_aff_constant_is_negative(__isl_take isl_pw_aff *pa, void *user)
787 {
788         int r;
789         int *neg = user;
790
791         r = isl_pw_aff_foreach_piece(pa, &aff_constant_is_negative, user);
792         isl_pw_aff_free(pa);
793
794         return *neg ? 0 : -1;
795 }
796
797 /* Does each element in "list" have a negative constant term?
798  *
799  * The callback terminates the iteration as soon an element has been
800  * found that does not have a negative constant term.
801  */
802 static int list_constant_is_negative(__isl_keep isl_pw_aff_list *list)
803 {
804         int neg = 1;
805
806         if (isl_pw_aff_list_foreach(list,
807                                 &pw_aff_constant_is_negative, &neg) < 0 && neg)
808                 return -1;
809
810         return neg;
811 }
812
813 /* Add 1 to each of the elements in "list", where each of these elements
814  * is defined over the internal schedule space of "build".
815  */
816 static __isl_give isl_pw_aff_list *list_add_one(
817         __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
818 {
819         int i, n;
820         isl_space *space;
821         isl_aff *aff;
822         isl_pw_aff *one;
823
824         space = isl_ast_build_get_space(build, 1);
825         aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
826         aff = isl_aff_add_constant_si(aff, 1);
827         one = isl_pw_aff_from_aff(aff);
828
829         n = isl_pw_aff_list_n_pw_aff(list);
830         for (i = 0; i < n; ++i) {
831                 isl_pw_aff *pa;
832                 pa = isl_pw_aff_list_get_pw_aff(list, i);
833                 pa = isl_pw_aff_add(pa, isl_pw_aff_copy(one));
834                 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
835         }
836
837         isl_pw_aff_free(one);
838
839         return list;
840 }
841
842 /* Set the condition part of the for node graft->node in case
843  * the upper bound is represented as a list of piecewise affine expressions.
844  *
845  * In particular, set the condition to
846  *
847  *      iterator <= min(list of upper bounds)
848  *
849  * If each of the upper bounds has a negative constant term, then
850  * set the condition to
851  *
852  *      iterator < min(list of (upper bound + 1)s)
853  *
854  */
855 static __isl_give isl_ast_graft *set_for_cond_from_list(
856         __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *list,
857         __isl_keep isl_ast_build *build)
858 {
859         int neg;
860         isl_ast_expr *bound, *iterator, *cond;
861         enum isl_ast_op_type type = isl_ast_op_le;
862
863         if (!graft || !list)
864                 return isl_ast_graft_free(graft);
865
866         neg = list_constant_is_negative(list);
867         if (neg < 0)
868                 return isl_ast_graft_free(graft);
869         list = isl_pw_aff_list_copy(list);
870         if (neg) {
871                 list = list_add_one(list, build);
872                 type = isl_ast_op_lt;
873         }
874
875         bound = reduce_list(isl_ast_op_min, list, build);
876         iterator = isl_ast_expr_copy(graft->node->u.f.iterator);
877         cond = isl_ast_expr_alloc_binary(type, iterator, bound);
878         graft->node->u.f.cond = cond;
879
880         isl_pw_aff_list_free(list);
881         if (!graft->node->u.f.cond)
882                 return isl_ast_graft_free(graft);
883         return graft;
884 }
885
886 /* Set the condition part of the for node graft->node in case
887  * the upper bound is represented as a set.
888  */
889 static __isl_give isl_ast_graft *set_for_cond_from_set(
890         __isl_take isl_ast_graft *graft, __isl_keep isl_set *set,
891         __isl_keep isl_ast_build *build)
892 {
893         isl_ast_expr *cond;
894
895         if (!graft)
896                 return NULL;
897
898         cond = isl_ast_build_expr_from_set(build, isl_set_copy(set));
899         graft->node->u.f.cond = cond;
900         if (!graft->node->u.f.cond)
901                 return isl_ast_graft_free(graft);
902         return graft;
903 }
904
905 /* Construct an isl_ast_expr for the increment (i.e., stride) of
906  * the current dimension.
907  */
908 static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
909 {
910         int depth;
911         isl_int v;
912         isl_ctx *ctx;
913         isl_ast_expr *inc;
914
915         if (!build)
916                 return NULL;
917         ctx = isl_ast_build_get_ctx(build);
918         depth = isl_ast_build_get_depth(build);
919
920         if (!isl_ast_build_has_stride(build, depth))
921                 return isl_ast_expr_alloc_int_si(ctx, 1);
922
923         isl_int_init(v);
924         isl_ast_build_get_stride(build, depth, &v);
925         inc = isl_ast_expr_alloc_int(ctx, v);
926         isl_int_clear(v);
927
928         return inc;
929 }
930
931 /* Should we express the loop condition as
932  *
933  *      iterator <= min(list of upper bounds)
934  *
935  * or as a conjunction of constraints?
936  *
937  * The first is constructed from a list of upper bounds.
938  * The second is constructed from a set.
939  *
940  * If there are no upper bounds in "constraints", then this could mean
941  * that "domain" simply doesn't have an upper bound or that we didn't
942  * pick any upper bound.  In the first case, we want to generate the
943  * loop condition as a(n empty) conjunction of constraints
944  * In the second case, we will compute
945  * a single upper bound from "domain" and so we use the list form.
946  *
947  * If there are upper bounds in "constraints",
948  * then we use the list form iff the atomic_upper_bound option is set.
949  */
950 static int use_upper_bound_list(isl_ctx *ctx, int n_upper,
951         __isl_keep isl_set *domain, int depth)
952 {
953         if (n_upper > 0)
954                 return isl_options_get_ast_build_atomic_upper_bound(ctx);
955         else
956                 return isl_set_dim_has_upper_bound(domain, isl_dim_set, depth);
957 }
958
959 /* Fill in the expressions of the for node in graft->node.
960  *
961  * In particular,
962  * - set the initialization part of the loop to the maximum of the lower bounds
963  * - set the size of the iterator based on the values attained by the iterator
964  * - extract the increment from the stride of the current dimension
965  * - construct the for condition either based on a list of upper bounds
966  *      or on a set of upper bound constraints.
967  */
968 static __isl_give isl_ast_graft *set_for_node_expressions(
969         __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *lower,
970         int use_list, __isl_keep isl_pw_aff_list *upper_list,
971         __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build)
972 {
973         isl_ast_node *node;
974
975         if (!graft)
976                 return NULL;
977
978         build = isl_ast_build_copy(build);
979         build = isl_ast_build_set_enforced(build,
980                                         isl_ast_graft_get_enforced(graft));
981
982         node = graft->node;
983         node->u.f.init = reduce_list(isl_ast_op_max, lower, build);
984         node->u.f.inc = for_inc(build);
985
986         if (use_list)
987                 graft = set_for_cond_from_list(graft, upper_list, build);
988         else
989                 graft = set_for_cond_from_set(graft, upper_set, build);
990
991         isl_ast_build_free(build);
992
993         if (!node->u.f.iterator || !node->u.f.init ||
994             !node->u.f.cond || !node->u.f.inc)
995                 return isl_ast_graft_free(graft);
996
997         return graft;
998 }
999
1000 /* Update "graft" based on "bounds" and "domain" for the generic,
1001  * non-degenerate, case.
1002  *
1003  * "c_lower" and "c_upper" contain the lower and upper bounds
1004  * that the loop node should express.
1005  * "domain" is the subset of the intersection of the constraints
1006  * for which some code is executed.
1007  *
1008  * There may be zero lower bounds or zero upper bounds in "constraints"
1009  * in case the list of constraints was created
1010  * based on the atomic option or based on separation with explicit bounds.
1011  * In that case, we use "domain" to derive lower and/or upper bounds.
1012  *
1013  * We first compute a list of one or more lower bounds.
1014  *
1015  * Then we decide if we want to express the condition as
1016  *
1017  *      iterator <= min(list of upper bounds)
1018  *
1019  * or as a conjunction of constraints.
1020  *
1021  * The set of enforced constraints is then computed either based on
1022  * a list of upper bounds or on a set of upper bound constraints.
1023  * We do not compute any enforced constraints if we were forced
1024  * to compute a lower or upper bound using exact_bound.  The domains
1025  * of the resulting expressions may imply some bounds on outer dimensions
1026  * that we do not want to appear in the enforced constraints since
1027  * they are not actually enforced by the corresponding code.
1028  *
1029  * Finally, we fill in the expressions of the for node.
1030  */
1031 static __isl_give isl_ast_graft *refine_generic_bounds(
1032         __isl_take isl_ast_graft *graft,
1033         __isl_take isl_constraint_list *c_lower,
1034         __isl_take isl_constraint_list *c_upper,
1035         __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1036 {
1037         int depth;
1038         isl_ctx *ctx;
1039         isl_pw_aff_list *lower;
1040         int use_list;
1041         isl_set *upper_set = NULL;
1042         isl_pw_aff_list *upper_list = NULL;
1043         int n_lower, n_upper;
1044
1045         if (!graft || !c_lower || !c_upper || !build)
1046                 goto error;
1047
1048         depth = isl_ast_build_get_depth(build);
1049         ctx = isl_ast_graft_get_ctx(graft);
1050
1051         n_lower = isl_constraint_list_n_constraint(c_lower);
1052         n_upper = isl_constraint_list_n_constraint(c_upper);
1053
1054         use_list = use_upper_bound_list(ctx, n_upper, domain, depth);
1055
1056         lower = lower_bounds(c_lower, depth, domain, build);
1057
1058         if (use_list)
1059                 upper_list = upper_bounds(c_upper, depth, domain, build);
1060         else if (n_upper > 0)
1061                 upper_set = intersect_constraints(c_upper);
1062         else
1063                 upper_set = isl_set_universe(isl_set_get_space(domain));
1064
1065         if (n_lower == 0 || n_upper == 0)
1066                 ;
1067         else if (use_list)
1068                 graft = set_enforced_from_list(graft, lower, upper_list);
1069         else
1070                 graft = set_enforced_from_set(graft, lower, depth, upper_set);
1071
1072         graft = set_for_node_expressions(graft, lower, use_list, upper_list,
1073                                         upper_set, build);
1074
1075         isl_pw_aff_list_free(lower);
1076         isl_pw_aff_list_free(upper_list);
1077         isl_set_free(upper_set);
1078         isl_constraint_list_free(c_lower);
1079         isl_constraint_list_free(c_upper);
1080
1081         return graft;
1082 error:
1083         isl_constraint_list_free(c_lower);
1084         isl_constraint_list_free(c_upper);
1085         return isl_ast_graft_free(graft);
1086 }
1087
1088 /* Internal data structure used inside count_constraints to keep
1089  * track of the number of constraints that are independent of dimension "pos",
1090  * the lower bounds in "pos" and the upper bounds in "pos".
1091  */
1092 struct isl_ast_count_constraints_data {
1093         int pos;
1094
1095         int n_indep;
1096         int n_lower;
1097         int n_upper;
1098 };
1099
1100 /* Increment data->n_indep, data->lower or data->upper depending
1101  * on whether "c" is independenct of dimensions data->pos,
1102  * a lower bound or an upper bound.
1103  */
1104 static int count_constraints(__isl_take isl_constraint *c, void *user)
1105 {
1106         struct isl_ast_count_constraints_data *data = user;
1107
1108         if (isl_constraint_is_lower_bound(c, isl_dim_set, data->pos))
1109                 data->n_lower++;
1110         else if (isl_constraint_is_upper_bound(c, isl_dim_set, data->pos))
1111                 data->n_upper++;
1112         else
1113                 data->n_indep++;
1114
1115         isl_constraint_free(c);
1116
1117         return 0;
1118 }
1119
1120 /* Update "graft" based on "bounds" and "domain" for the generic,
1121  * non-degenerate, case.
1122  *
1123  * "list" respresent the list of bounds that need to be encoded by
1124  * the for loop (or a guard around the for loop).
1125  * "domain" is the subset of the intersection of the constraints
1126  * for which some code is executed.
1127  * "build" is the build in which graft->node was created.
1128  *
1129  * We separate lower bounds, upper bounds and constraints that
1130  * are independent of the loop iterator.
1131  *
1132  * The actual for loop bounds are generated in refine_generic_bounds.
1133  * If there are any constraints that are independent of the loop iterator,
1134  * we need to put a guard around the for loop (which may get hoisted up
1135  * to higher levels) and we call refine_generic_bounds in a build
1136  * where this guard is enforced.
1137  */
1138 static __isl_give isl_ast_graft *refine_generic_split(
1139         __isl_take isl_ast_graft *graft, __isl_take isl_constraint_list *list,
1140         __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1141 {
1142         isl_ast_build *for_build;
1143         isl_set *guard;
1144         struct isl_ast_count_constraints_data data;
1145         isl_constraint_list *lower;
1146         isl_constraint_list *upper;
1147
1148         if (!list)
1149                 return isl_ast_graft_free(graft);
1150
1151         data.pos = isl_ast_build_get_depth(build);
1152
1153         list = isl_constraint_list_sort(list, &cmp_constraint, &data.pos);
1154         if (!list)
1155                 return isl_ast_graft_free(graft);
1156
1157         data.n_indep = data.n_lower = data.n_upper = 0;
1158         if (isl_constraint_list_foreach(list, &count_constraints, &data) < 0) {
1159                 isl_constraint_list_free(list);
1160                 return isl_ast_graft_free(graft);
1161         }
1162
1163         lower = isl_constraint_list_copy(list);
1164         lower = isl_constraint_list_drop(lower, 0, data.n_indep);
1165         upper = isl_constraint_list_copy(lower);
1166         lower = isl_constraint_list_drop(lower, data.n_lower, data.n_upper);
1167         upper = isl_constraint_list_drop(upper, 0, data.n_lower);
1168
1169         if (data.n_indep == 0) {
1170                 isl_constraint_list_free(list);
1171                 return refine_generic_bounds(graft, lower, upper,
1172                                                 domain, build);
1173         }
1174
1175         list = isl_constraint_list_drop(list, data.n_indep,
1176                                         data.n_lower + data.n_upper);
1177         guard = intersect_constraints(list);
1178         isl_constraint_list_free(list);
1179
1180         for_build = isl_ast_build_copy(build);
1181         for_build = isl_ast_build_restrict_pending(for_build,
1182                                                 isl_set_copy(guard));
1183         graft = refine_generic_bounds(graft, lower, upper, domain, for_build);
1184         isl_ast_build_free(for_build);
1185
1186         graft = isl_ast_graft_add_guard(graft, guard, build);
1187
1188         return graft;
1189 }
1190
1191 /* Add the guard implied by the current stride constraint (if any),
1192  * but not (necessarily) enforced by the generated AST to "graft".
1193  */
1194 static __isl_give isl_ast_graft *add_stride_guard(
1195         __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
1196 {
1197         int depth;
1198         isl_set *dom;
1199
1200         depth = isl_ast_build_get_depth(build);
1201         if (!isl_ast_build_has_stride(build, depth))
1202                 return graft;
1203
1204         dom = isl_ast_build_get_stride_constraint(build);
1205         dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
1206         dom = isl_ast_build_compute_gist(build, dom);
1207
1208         graft = isl_ast_graft_add_guard(graft, dom, build);
1209
1210         return graft;
1211 }
1212
1213 /* Update "graft" based on "bounds" and "domain" for the generic,
1214  * non-degenerate, case.
1215  *
1216  * "bounds" respresent the bounds that need to be encoded by
1217  * the for loop (or a guard around the for loop).
1218  * "domain" is the subset of "bounds" for which some code is executed.
1219  * "build" is the build in which graft->node was created.
1220  *
1221  * We break up "bounds" into a list of constraints and continue with
1222  * refine_generic_split.
1223  */
1224 static __isl_give isl_ast_graft *refine_generic(
1225         __isl_take isl_ast_graft *graft,
1226         __isl_keep isl_basic_set *bounds, __isl_keep isl_set *domain,
1227         __isl_keep isl_ast_build *build)
1228 {
1229         isl_constraint_list *list;
1230
1231         if (!build || !graft)
1232                 return isl_ast_graft_free(graft);
1233
1234         bounds = isl_basic_set_copy(bounds);
1235         bounds = isl_ast_build_compute_gist_basic_set(build, bounds);
1236         list = isl_constraint_list_from_basic_set(bounds);
1237
1238         graft = refine_generic_split(graft, list, domain, build);
1239         graft = add_stride_guard(graft, build);
1240
1241         return graft;
1242 }
1243
1244 /* Create a for node for the current level.
1245  *
1246  * Mark the for node degenerate if "degenerate" is set.
1247  */
1248 static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build,
1249         int degenerate)
1250 {
1251         int depth;
1252         isl_id *id;
1253         isl_ast_node *node;
1254
1255         if (!build)
1256                 return NULL;
1257
1258         depth = isl_ast_build_get_depth(build);
1259         id = isl_ast_build_get_iterator_id(build, depth);
1260         node = isl_ast_node_alloc_for(id);
1261         if (degenerate)
1262                 node = isl_ast_node_for_mark_degenerate(node);
1263
1264         return node;
1265 }
1266
1267 /* Create an AST node for the current dimension based on
1268  * the schedule domain "bounds" and return the node encapsulated
1269  * in an isl_ast_graft.
1270  *
1271  * "executed" is the current inverse schedule, taking into account
1272  * the bounds in "bounds"
1273  * "domain" is the domain of "executed", with inner dimensions projected out.
1274  * It may be a strict subset of "bounds" in case "bounds" was created
1275  * based on the atomic option or based on separation with explicit bounds.
1276  *
1277  * "domain" may satisfy additional equalities that result
1278  * from intersecting "executed" with "bounds" in add_node.
1279  * It may also satisfy some global constraints that were dropped out because
1280  * we performed separation with explicit bounds.
1281  * The very first step is then to copy these constraints to "bounds".
1282  *
1283  * Since we may be calling before_each_for and after_each_for
1284  * callbacks, we record the current inverse schedule in the build.
1285  *
1286  * We consider three builds,
1287  * "build" is the one in which the current level is created,
1288  * "body_build" is the build in which the next level is created,
1289  * "sub_build" is essentially the same as "body_build", except that
1290  * the depth has not been increased yet.
1291  *
1292  * "build" already contains information (in strides and offsets)
1293  * about the strides at the current level, but this information is not
1294  * reflected in the build->domain.
1295  * We first add this information and the "bounds" to the sub_build->domain.
1296  * isl_ast_build_set_loop_bounds checks whether the current dimension attains
1297  * only a single value and whether this single value can be represented using
1298  * a single affine expression.
1299  * In the first case, the current level is considered "degenerate".
1300  * In the second, sub-case, the current level is considered "eliminated".
1301  * Eliminated level don't need to be reflected in the AST since we can
1302  * simply plug in the affine expression.  For degenerate, but non-eliminated,
1303  * levels, we do introduce a for node, but mark is as degenerate so that
1304  * it can be printed as an assignment of the single value to the loop
1305  * "iterator".
1306  *
1307  * If the current level is eliminated, we explicitly plug in the value
1308  * for the current level found by isl_ast_build_set_loop_bounds in the
1309  * inverse schedule.  This ensures that if we are working on a slice
1310  * of the domain based on information available in the inverse schedule
1311  * and the build domain, that then this information is also reflected
1312  * in the inverse schedule.  This operation also eliminates the current
1313  * dimension from the inverse schedule making sure no inner dimensions depend
1314  * on the current dimension.  Otherwise, we create a for node, marking
1315  * it degenerate if appropriate.  The initial for node is still incomplete
1316  * and will be completed in either refine_degenerate or refine_generic.
1317  *
1318  * We then generate a sequence of grafts for the next level,
1319  * create a surrounding graft for the current level and insert
1320  * the for node we created (if the current level is not eliminated).
1321  *
1322  * Finally, we set the bounds of the for loop and insert guards
1323  * (either in the AST or in the graft) in one of
1324  * refine_eliminated, refine_degenerate or refine_generic.
1325  */
1326 static __isl_give isl_ast_graft *create_node_scaled(
1327         __isl_take isl_union_map *executed,
1328         __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1329         __isl_take isl_ast_build *build)
1330 {
1331         int depth;
1332         int degenerate, eliminated;
1333         isl_basic_set *hull;
1334         isl_ast_node *node = NULL;
1335         isl_ast_graft *graft;
1336         isl_ast_graft_list *children;
1337         isl_ast_build *sub_build;
1338         isl_ast_build *body_build;
1339
1340         domain = isl_ast_build_eliminate_divs(build, domain);
1341         domain = isl_set_detect_equalities(domain);
1342         hull = isl_set_unshifted_simple_hull(isl_set_copy(domain));
1343         bounds = isl_basic_set_intersect(bounds, hull);
1344         build = isl_ast_build_set_executed(build, isl_union_map_copy(executed));
1345
1346         depth = isl_ast_build_get_depth(build);
1347         sub_build = isl_ast_build_copy(build);
1348         sub_build = isl_ast_build_include_stride(sub_build);
1349         sub_build = isl_ast_build_set_loop_bounds(sub_build,
1350                                                 isl_basic_set_copy(bounds));
1351         degenerate = isl_ast_build_has_value(sub_build);
1352         eliminated = isl_ast_build_has_affine_value(sub_build, depth);
1353         if (degenerate < 0 || eliminated < 0)
1354                 executed = isl_union_map_free(executed);
1355         if (eliminated)
1356                 executed = plug_in_values(executed, sub_build);
1357         else
1358                 node = create_for(build, degenerate);
1359
1360         body_build = isl_ast_build_copy(sub_build);
1361         body_build = isl_ast_build_increase_depth(body_build);
1362         if (!eliminated)
1363                 node = before_each_for(node, body_build);
1364         children = generate_next_level(executed,
1365                                     isl_ast_build_copy(body_build));
1366
1367         graft = isl_ast_graft_alloc_level(children, build, sub_build);
1368         if (!eliminated)
1369                 graft = isl_ast_graft_insert_for(graft, node);
1370         if (eliminated)
1371                 graft = refine_eliminated(graft, bounds, build);
1372         else if (degenerate)
1373                 graft = refine_degenerate(graft, bounds, build, sub_build);
1374         else
1375                 graft = refine_generic(graft, bounds, domain, build);
1376         if (!eliminated)
1377                 graft = after_each_for(graft, body_build);
1378
1379         isl_ast_build_free(body_build);
1380         isl_ast_build_free(sub_build);
1381         isl_ast_build_free(build);
1382         isl_basic_set_free(bounds);
1383         isl_set_free(domain);
1384
1385         return graft;
1386 }
1387
1388 /* Internal data structure for checking if all constraints involving
1389  * the input dimension "depth" are such that the other coefficients
1390  * are multiples of "m", reducing "m" if they are not.
1391  * If "m" is reduced all the way down to "1", then the check has failed
1392  * and we break out of the iteration.
1393  * "d" is an initialized isl_int that can be used internally.
1394  */
1395 struct isl_check_scaled_data {
1396         int depth;
1397         isl_int m, d;
1398 };
1399
1400 /* If constraint "c" involves the input dimension data->depth,
1401  * then make sure that all the other coefficients are multiples of data->m,
1402  * reducing data->m if needed.
1403  * Break out of the iteration if data->m has become equal to "1".
1404  */
1405 static int constraint_check_scaled(__isl_take isl_constraint *c, void *user)
1406 {
1407         struct isl_check_scaled_data *data = user;
1408         int i, j, n;
1409         enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_out,
1410                                     isl_dim_div };
1411
1412         if (!isl_constraint_involves_dims(c, isl_dim_in, data->depth, 1)) {
1413                 isl_constraint_free(c);
1414                 return 0;
1415         }
1416
1417         for (i = 0; i < 4; ++i) {
1418                 n = isl_constraint_dim(c, t[i]);
1419                 for (j = 0; j < n; ++j) {
1420                         if (t[i] == isl_dim_in && j == data->depth)
1421                                 continue;
1422                         if (!isl_constraint_involves_dims(c, t[i], j, 1))
1423                                 continue;
1424                         isl_constraint_get_coefficient(c, t[i], j, &data->d);
1425                         isl_int_gcd(data->m, data->m, data->d);
1426                         if (isl_int_is_one(data->m))
1427                                 break;
1428                 }
1429                 if (j < n)
1430                         break;
1431         }
1432
1433         isl_constraint_free(c);
1434
1435         return i < 4 ? -1 : 0;
1436 }
1437
1438 /* For each constraint of "bmap" that involves the input dimension data->depth,
1439  * make sure that all the other coefficients are multiples of data->m,
1440  * reducing data->m if needed.
1441  * Break out of the iteration if data->m has become equal to "1".
1442  */
1443 static int basic_map_check_scaled(__isl_take isl_basic_map *bmap, void *user)
1444 {
1445         int r;
1446
1447         r = isl_basic_map_foreach_constraint(bmap,
1448                                                 &constraint_check_scaled, user);
1449         isl_basic_map_free(bmap);
1450
1451         return r;
1452 }
1453
1454 /* For each constraint of "map" that involves the input dimension data->depth,
1455  * make sure that all the other coefficients are multiples of data->m,
1456  * reducing data->m if needed.
1457  * Break out of the iteration if data->m has become equal to "1".
1458  */
1459 static int map_check_scaled(__isl_take isl_map *map, void *user)
1460 {
1461         int r;
1462
1463         r = isl_map_foreach_basic_map(map, &basic_map_check_scaled, user);
1464         isl_map_free(map);
1465
1466         return r;
1467 }
1468
1469 /* Create an AST node for the current dimension based on
1470  * the schedule domain "bounds" and return the node encapsulated
1471  * in an isl_ast_graft.
1472  *
1473  * "executed" is the current inverse schedule, taking into account
1474  * the bounds in "bounds"
1475  * "domain" is the domain of "executed", with inner dimensions projected out.
1476  *
1477  *
1478  * Before moving on to the actual AST node construction in create_node_scaled,
1479  * we first check if the current dimension is strided and if we can scale
1480  * down this stride.  Note that we only do this if the ast_build_scale_strides
1481  * option is set.
1482  *
1483  * In particular, let the current dimension take on values
1484  *
1485  *      f + s a
1486  *
1487  * with a an integer.  We check if we can find an integer m that (obviouly)
1488  * divides both f and s.
1489  *
1490  * If so, we check if the current dimension only appears in constraints
1491  * where the coefficients of the other variables are multiples of m.
1492  * We perform this extra check to avoid the risk of introducing
1493  * divisions by scaling down the current dimension.
1494  *
1495  * If so, we scale the current dimension down by a factor of m.
1496  * That is, we plug in
1497  *
1498  *      i = m i'                                                        (1)
1499  *
1500  * Note that in principle we could always scale down strided loops
1501  * by plugging in
1502  *
1503  *      i = f + s i'
1504  *
1505  * but this may result in i' taking on larger values than the original i,
1506  * due to the shift by "f".
1507  * By constrast, the scaling in (1) can only reduce the (absolute) value "i".
1508  */
1509 static __isl_give isl_ast_graft *create_node(__isl_take isl_union_map *executed,
1510         __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1511         __isl_take isl_ast_build *build)
1512 {
1513         struct isl_check_scaled_data data;
1514         isl_ctx *ctx;
1515         isl_aff *offset;
1516
1517         ctx = isl_ast_build_get_ctx(build);
1518         if (!isl_options_get_ast_build_scale_strides(ctx))
1519                 return create_node_scaled(executed, bounds, domain, build);
1520
1521         data.depth = isl_ast_build_get_depth(build);
1522         if (!isl_ast_build_has_stride(build, data.depth))
1523                 return create_node_scaled(executed, bounds, domain, build);
1524
1525         isl_int_init(data.m);
1526         isl_int_init(data.d);
1527
1528         offset = isl_ast_build_get_offset(build, data.depth);
1529         if (isl_ast_build_get_stride(build, data.depth, &data.m) < 0)
1530                 offset = isl_aff_free(offset);
1531         offset = isl_aff_scale_down(offset, data.m);
1532         if (isl_aff_get_denominator(offset, &data.d) < 0)
1533                 executed = isl_union_map_free(executed);
1534
1535         if (executed && isl_int_is_divisible_by(data.m, data.d))
1536                 isl_int_divexact(data.m, data.m, data.d);
1537         else
1538                 isl_int_set_si(data.m, 1);
1539
1540         if (!isl_int_is_one(data.m)) {
1541                 if (isl_union_map_foreach_map(executed, &map_check_scaled,
1542                                                 &data) < 0 &&
1543                     !isl_int_is_one(data.m))
1544                         executed = isl_union_map_free(executed);
1545         }
1546
1547         if (!isl_int_is_one(data.m)) {
1548                 isl_space *space;
1549                 isl_multi_aff *ma;
1550                 isl_aff *aff;
1551                 isl_map *map;
1552                 isl_union_map *umap;
1553
1554                 space = isl_ast_build_get_space(build, 1);
1555                 space = isl_space_map_from_set(space);
1556                 ma = isl_multi_aff_identity(space);
1557                 aff = isl_multi_aff_get_aff(ma, data.depth);
1558                 aff = isl_aff_scale(aff, data.m);
1559                 ma = isl_multi_aff_set_aff(ma, data.depth, aff);
1560
1561                 bounds = isl_basic_set_preimage_multi_aff(bounds,
1562                                                 isl_multi_aff_copy(ma));
1563                 domain = isl_set_preimage_multi_aff(domain,
1564                                                 isl_multi_aff_copy(ma));
1565                 map = isl_map_reverse(isl_map_from_multi_aff(ma));
1566                 umap = isl_union_map_from_map(map);
1567                 executed = isl_union_map_apply_domain(executed,
1568                                                 isl_union_map_copy(umap));
1569                 build = isl_ast_build_scale_down(build, data.m, umap);
1570         }
1571         isl_aff_free(offset);
1572
1573         isl_int_clear(data.d);
1574         isl_int_clear(data.m);
1575
1576         return create_node_scaled(executed, bounds, domain, build);
1577 }
1578
1579 /* Add the basic set to the list that "user" points to.
1580  */
1581 static int collect_basic_set(__isl_take isl_basic_set *bset, void *user)
1582 {
1583         isl_basic_set_list **list = user;
1584
1585         *list = isl_basic_set_list_add(*list, bset);
1586
1587         return 0;
1588 }
1589
1590 /* Extract the basic sets of "set" and collect them in an isl_basic_set_list.
1591  */
1592 static __isl_give isl_basic_set_list *isl_basic_set_list_from_set(
1593         __isl_take isl_set *set)
1594 {
1595         int n;
1596         isl_ctx *ctx;
1597         isl_basic_set_list *list;
1598
1599         if (!set)
1600                 return NULL;
1601
1602         ctx = isl_set_get_ctx(set);
1603
1604         n = isl_set_n_basic_set(set);
1605         list = isl_basic_set_list_alloc(ctx, n);
1606         if (isl_set_foreach_basic_set(set, &collect_basic_set, &list) < 0)
1607                 list = isl_basic_set_list_free(list);
1608
1609         isl_set_free(set);
1610         return list;
1611 }
1612
1613 /* Generate code for the schedule domain "bounds"
1614  * and add the result to "list".
1615  *
1616  * We mainly detect strides and additional equalities here
1617  * and then pass over control to create_node.
1618  *
1619  * "bounds" reflects the bounds on the current dimension and possibly
1620  * some extra conditions on outer dimensions.
1621  * It does not, however, include any divs involving the current dimension,
1622  * so it does not capture any stride constraints.
1623  * We therefore need to compute that part of the schedule domain that
1624  * intersects with "bounds" and derive the strides from the result.
1625  */
1626 static __isl_give isl_ast_graft_list *add_node(
1627         __isl_take isl_ast_graft_list *list, __isl_take isl_union_map *executed,
1628         __isl_take isl_basic_set *bounds, __isl_take isl_ast_build *build)
1629 {
1630         isl_ast_graft *graft;
1631         isl_set *domain = NULL;
1632         isl_union_set *uset;
1633         int empty;
1634
1635         uset = isl_union_set_from_basic_set(isl_basic_set_copy(bounds));
1636         executed = isl_union_map_intersect_domain(executed, uset);
1637         empty = isl_union_map_is_empty(executed);
1638         if (empty < 0)
1639                 goto error;
1640         if (empty)
1641                 goto done;
1642
1643         uset = isl_union_map_domain(isl_union_map_copy(executed));
1644         domain = isl_set_from_union_set(uset);
1645         domain = isl_ast_build_compute_gist(build, domain);
1646         empty = isl_set_is_empty(domain);
1647         if (empty < 0)
1648                 goto error;
1649         if (empty)
1650                 goto done;
1651
1652         domain = isl_ast_build_eliminate_inner(build, domain);
1653         build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
1654
1655         graft = create_node(executed, bounds, domain,
1656                                 isl_ast_build_copy(build));
1657         list = isl_ast_graft_list_add(list, graft);
1658         isl_ast_build_free(build);
1659         return list;
1660 error:
1661         list = isl_ast_graft_list_free(list);
1662 done:
1663         isl_set_free(domain);
1664         isl_basic_set_free(bounds);
1665         isl_union_map_free(executed);
1666         isl_ast_build_free(build);
1667         return list;
1668 }
1669
1670 /* Does any element of i follow or coincide with any element of j
1671  * at the current depth for equal values of the outer dimensions?
1672  */
1673 static int domain_follows_at_depth(__isl_keep isl_basic_set *i,
1674         __isl_keep isl_basic_set *j, void *user)
1675 {
1676         int depth = *(int *) user;
1677         isl_basic_map *test;
1678         int empty;
1679         int l;
1680
1681         test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1682                                                     isl_basic_set_copy(j));
1683         for (l = 0; l < depth; ++l)
1684                 test = isl_basic_map_equate(test, isl_dim_in, l,
1685                                                 isl_dim_out, l);
1686         test = isl_basic_map_order_ge(test, isl_dim_in, depth,
1687                                         isl_dim_out, depth);
1688         empty = isl_basic_map_is_empty(test);
1689         isl_basic_map_free(test);
1690
1691         return empty < 0 ? -1 : !empty;
1692 }
1693
1694 /* Split up each element of "list" into a part that is related to "bset"
1695  * according to "gt" and a part that is not.
1696  * Return a list that consist of "bset" and all the pieces.
1697  */
1698 static __isl_give isl_basic_set_list *add_split_on(
1699         __isl_take isl_basic_set_list *list, __isl_take isl_basic_set *bset,
1700         __isl_keep isl_basic_map *gt)
1701 {
1702         int i, n;
1703         isl_basic_set_list *res;
1704
1705         gt = isl_basic_map_copy(gt);
1706         gt = isl_basic_map_intersect_domain(gt, isl_basic_set_copy(bset));
1707         n = isl_basic_set_list_n_basic_set(list);
1708         res = isl_basic_set_list_from_basic_set(bset);
1709         for (i = 0; res && i < n; ++i) {
1710                 isl_basic_set *bset;
1711                 isl_set *set1, *set2;
1712                 isl_basic_map *bmap;
1713                 int empty;
1714
1715                 bset = isl_basic_set_list_get_basic_set(list, i);
1716                 bmap = isl_basic_map_copy(gt);
1717                 bmap = isl_basic_map_intersect_range(bmap, bset);
1718                 bset = isl_basic_map_range(bmap);
1719                 empty = isl_basic_set_is_empty(bset);
1720                 if (empty < 0)
1721                         res = isl_basic_set_list_free(res);
1722                 if (empty)  {
1723                         isl_basic_set_free(bset);
1724                         bset = isl_basic_set_list_get_basic_set(list, i);
1725                         res = isl_basic_set_list_add(res, bset);
1726                         continue;
1727                 }
1728
1729                 res = isl_basic_set_list_add(res, isl_basic_set_copy(bset));
1730                 set1 = isl_set_from_basic_set(bset);
1731                 bset = isl_basic_set_list_get_basic_set(list, i);
1732                 set2 = isl_set_from_basic_set(bset);
1733                 set1 = isl_set_subtract(set2, set1);
1734                 set1 = isl_set_make_disjoint(set1);
1735
1736                 res = isl_basic_set_list_concat(res,
1737                                             isl_basic_set_list_from_set(set1));
1738         }
1739         isl_basic_map_free(gt);
1740         isl_basic_set_list_free(list);
1741         return res;
1742 }
1743
1744 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1745         __isl_keep isl_basic_set_list *domain_list,
1746         __isl_keep isl_union_map *executed,
1747         __isl_keep isl_ast_build *build);
1748
1749 /* Internal data structure for add_nodes.
1750  *
1751  * "executed" and "build" are extra arguments to be passed to add_node.
1752  * "list" collects the results.
1753  */
1754 struct isl_add_nodes_data {
1755         isl_union_map *executed;
1756         isl_ast_build *build;
1757
1758         isl_ast_graft_list *list;
1759 };
1760
1761 /* Generate code for the schedule domains in "scc"
1762  * and add the results to "list".
1763  *
1764  * The domains in "scc" form a strongly connected component in the ordering.
1765  * If the number of domains in "scc" is larger than 1, then this means
1766  * that we cannot determine a valid ordering for the domains in the component.
1767  * This should be fairly rare because the individual domains
1768  * have been made disjoint first.
1769  * The problem is that the domains may be integrally disjoint but not
1770  * rationally disjoint.  For example, we may have domains
1771  *
1772  *      { [i,i] : 0 <= i <= 1 }         and     { [i,1-i] : 0 <= i <= 1 }
1773  *
1774  * These two domains have an empty intersection, but their rational
1775  * relaxations do intersect.  It is impossible to order these domains
1776  * in the second dimension because the first should be ordered before
1777  * the second for outer dimension equal to 0, while it should be ordered
1778  * after for outer dimension equal to 1.
1779  *
1780  * This may happen in particular in case of unrolling since the domain
1781  * of each slice is replaced by its simple hull.
1782  *
1783  * For each basic set i in "scc" and for each of the following basic sets j,
1784  * we split off that part of the basic set i that shares the outer dimensions
1785  * with j and lies before j in the current dimension.
1786  * We collect all the pieces in a new list that replaces "scc".
1787  */
1788 static int add_nodes(__isl_take isl_basic_set_list *scc, void *user)
1789 {
1790         struct isl_add_nodes_data *data = user;
1791         int i, n, depth;
1792         isl_basic_set *bset;
1793         isl_basic_set_list *list;
1794         isl_space *space;
1795         isl_basic_map *gt;
1796
1797         n = isl_basic_set_list_n_basic_set(scc);
1798         bset = isl_basic_set_list_get_basic_set(scc, 0);
1799         if (n == 1) {
1800                 isl_basic_set_list_free(scc);
1801                 data->list = add_node(data->list,
1802                                 isl_union_map_copy(data->executed), bset,
1803                                 isl_ast_build_copy(data->build));
1804                 return data->list ? 0 : -1;
1805         }
1806
1807         depth = isl_ast_build_get_depth(data->build);
1808         space = isl_basic_set_get_space(bset);
1809         space = isl_space_map_from_set(space);
1810         gt = isl_basic_map_universe(space);
1811         for (i = 0; i < depth; ++i)
1812                 gt = isl_basic_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
1813         gt = isl_basic_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
1814
1815         list = isl_basic_set_list_from_basic_set(bset);
1816         for (i = 1; i < n; ++i) {
1817                 bset = isl_basic_set_list_get_basic_set(scc, i);
1818                 list = add_split_on(list, bset, gt);
1819         }
1820         isl_basic_map_free(gt);
1821         isl_basic_set_list_free(scc);
1822         scc = list;
1823         data->list = isl_ast_graft_list_concat(data->list,
1824                     generate_sorted_domains(scc, data->executed, data->build));
1825         isl_basic_set_list_free(scc);
1826
1827         return data->list ? 0 : -1;
1828 }
1829
1830 /* Sort the domains in "domain_list" according to the execution order
1831  * at the current depth (for equal values of the outer dimensions),
1832  * generate code for each of them, collecting the results in a list.
1833  * If no code is generated (because the intersection of the inverse schedule
1834  * with the domains turns out to be empty), then an empty list is returned.
1835  *
1836  * The caller is responsible for ensuring that the basic sets in "domain_list"
1837  * are pair-wise disjoint.  It can, however, in principle happen that
1838  * two basic sets should be ordered one way for one value of the outer
1839  * dimensions and the other way for some other value of the outer dimensions.
1840  * We therefore play safe and look for strongly connected components.
1841  * The function add_nodes takes care of handling non-trivial components.
1842  */
1843 static __isl_give isl_ast_graft_list *generate_sorted_domains(
1844         __isl_keep isl_basic_set_list *domain_list,
1845         __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
1846 {
1847         isl_ctx *ctx;
1848         struct isl_add_nodes_data data;
1849         int depth;
1850         int n;
1851
1852         if (!domain_list)
1853                 return NULL;
1854
1855         ctx = isl_basic_set_list_get_ctx(domain_list);
1856         n = isl_basic_set_list_n_basic_set(domain_list);
1857         data.list = isl_ast_graft_list_alloc(ctx, n);
1858         if (n == 0)
1859                 return data.list;
1860         if (n == 1)
1861                 return add_node(data.list, isl_union_map_copy(executed),
1862                         isl_basic_set_list_get_basic_set(domain_list, 0),
1863                         isl_ast_build_copy(build));
1864
1865         depth = isl_ast_build_get_depth(build);
1866         data.executed = executed;
1867         data.build = build;
1868         if (isl_basic_set_list_foreach_scc(domain_list,
1869                                         &domain_follows_at_depth, &depth,
1870                                         &add_nodes, &data) < 0)
1871                 data.list = isl_ast_graft_list_free(data.list);
1872
1873         return data.list;
1874 }
1875
1876 /* Do i and j share any values for the outer dimensions?
1877  */
1878 static int shared_outer(__isl_keep isl_basic_set *i,
1879         __isl_keep isl_basic_set *j, void *user)
1880 {
1881         int depth = *(int *) user;
1882         isl_basic_map *test;
1883         int empty;
1884         int l;
1885
1886         test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1887                                                     isl_basic_set_copy(j));
1888         for (l = 0; l < depth; ++l)
1889                 test = isl_basic_map_equate(test, isl_dim_in, l,
1890                                                 isl_dim_out, l);
1891         empty = isl_basic_map_is_empty(test);
1892         isl_basic_map_free(test);
1893
1894         return empty < 0 ? -1 : !empty;
1895 }
1896
1897 /* Internal data structure for generate_sorted_domains_wrap.
1898  *
1899  * "n" is the total number of basic sets
1900  * "executed" and "build" are extra arguments to be passed
1901  *      to generate_sorted_domains.
1902  *
1903  * "single" is set to 1 by generate_sorted_domains_wrap if there
1904  * is only a single component.
1905  * "list" collects the results.
1906  */
1907 struct isl_ast_generate_parallel_domains_data {
1908         int n;
1909         isl_union_map *executed;
1910         isl_ast_build *build;
1911
1912         int single;
1913         isl_ast_graft_list *list;
1914 };
1915
1916 /* Call generate_sorted_domains on "scc", fuse the result into a list
1917  * with either zero or one graft and collect the these single element
1918  * lists into data->list.
1919  *
1920  * If there is only one component, i.e., if the number of basic sets
1921  * in the current component is equal to the total number of basic sets,
1922  * then data->single is set to 1 and the result of generate_sorted_domains
1923  * is not fused.
1924  */
1925 static int generate_sorted_domains_wrap(__isl_take isl_basic_set_list *scc,
1926         void *user)
1927 {
1928         struct isl_ast_generate_parallel_domains_data *data = user;
1929         isl_ast_graft_list *list;
1930
1931         list = generate_sorted_domains(scc, data->executed, data->build);
1932         data->single = isl_basic_set_list_n_basic_set(scc) == data->n;
1933         if (!data->single)
1934                 list = isl_ast_graft_list_fuse(list, data->build);
1935         if (!data->list)
1936                 data->list = list;
1937         else
1938                 data->list = isl_ast_graft_list_concat(data->list, list);
1939
1940         isl_basic_set_list_free(scc);
1941         if (!data->list)
1942                 return -1;
1943
1944         return 0;
1945 }
1946
1947 /* Look for any (weakly connected) components in the "domain_list"
1948  * of domains that share some values of the outer dimensions.
1949  * That is, domains in different components do not share any values
1950  * of the outer dimensions.  This means that these components
1951  * can be freely reordered.
1952  * Within each of the components, we sort the domains according
1953  * to the execution order at the current depth.
1954  *
1955  * If there is more than one component, then generate_sorted_domains_wrap
1956  * fuses the result of each call to generate_sorted_domains
1957  * into a list with either zero or one graft and collects these (at most)
1958  * single element lists into a bigger list. This means that the elements of the
1959  * final list can be freely reordered.  In particular, we sort them
1960  * according to an arbitrary but fixed ordering to ease merging of
1961  * graft lists from different components.
1962  */
1963 static __isl_give isl_ast_graft_list *generate_parallel_domains(
1964         __isl_keep isl_basic_set_list *domain_list,
1965         __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
1966 {
1967         int depth;
1968         struct isl_ast_generate_parallel_domains_data data;
1969
1970         if (!domain_list)
1971                 return NULL;
1972
1973         data.n = isl_basic_set_list_n_basic_set(domain_list);
1974         if (data.n <= 1)
1975                 return generate_sorted_domains(domain_list, executed, build);
1976
1977         depth = isl_ast_build_get_depth(build);
1978         data.list = NULL;
1979         data.executed = executed;
1980         data.build = build;
1981         data.single = 0;
1982         if (isl_basic_set_list_foreach_scc(domain_list, &shared_outer, &depth,
1983                                             &generate_sorted_domains_wrap,
1984                                             &data) < 0)
1985                 data.list = isl_ast_graft_list_free(data.list);
1986
1987         if (!data.single)
1988                 data.list = isl_ast_graft_list_sort_guard(data.list);
1989
1990         return data.list;
1991 }
1992
1993 /* Internal data for separate_domain.
1994  *
1995  * "explicit" is set if we only want to use explicit bounds.
1996  *
1997  * "domain" collects the separated domains.
1998  */
1999 struct isl_separate_domain_data {
2000         isl_ast_build *build;
2001         int explicit;
2002         isl_set *domain;
2003 };
2004
2005 /* Extract implicit bounds on the current dimension for the executed "map".
2006  *
2007  * The domain of "map" may involve inner dimensions, so we
2008  * need to eliminate them.
2009  */
2010 static __isl_give isl_set *implicit_bounds(__isl_take isl_map *map,
2011         __isl_keep isl_ast_build *build)
2012 {
2013         isl_set *domain;
2014
2015         domain = isl_map_domain(map);
2016         domain = isl_ast_build_eliminate(build, domain);
2017
2018         return domain;
2019 }
2020
2021 /* Extract explicit bounds on the current dimension for the executed "map".
2022  *
2023  * Rather than eliminating the inner dimensions as in implicit_bounds,
2024  * we simply drop any constraints involving those inner dimensions.
2025  * The idea is that most bounds that are implied by constraints on the
2026  * inner dimensions will be enforced by for loops and not by explicit guards.
2027  * There is then no need to separate along those bounds.
2028  */
2029 static __isl_give isl_set *explicit_bounds(__isl_take isl_map *map,
2030         __isl_keep isl_ast_build *build)
2031 {
2032         isl_set *domain;
2033         int depth, dim;
2034
2035         dim = isl_map_dim(map, isl_dim_out);
2036         map = isl_map_drop_constraints_involving_dims(map, isl_dim_out, 0, dim);
2037
2038         domain = isl_map_domain(map);
2039         depth = isl_ast_build_get_depth(build);
2040         dim = isl_set_dim(domain, isl_dim_set);
2041         domain = isl_set_detect_equalities(domain);
2042         domain = isl_set_drop_constraints_involving_dims(domain,
2043                                 isl_dim_set, depth + 1, dim - (depth + 1));
2044         domain = isl_set_remove_divs_involving_dims(domain,
2045                                 isl_dim_set, depth, 1);
2046         domain = isl_set_remove_unknown_divs(domain);
2047
2048         return domain;
2049 }
2050
2051 /* Split data->domain into pieces that intersect with the range of "map"
2052  * and pieces that do not intersect with the range of "map"
2053  * and then add that part of the range of "map" that does not intersect
2054  * with data->domain.
2055  */
2056 static int separate_domain(__isl_take isl_map *map, void *user)
2057 {
2058         struct isl_separate_domain_data *data = user;
2059         isl_set *domain;
2060         isl_set *d1, *d2;
2061
2062         if (data->explicit)
2063                 domain = explicit_bounds(map, data->build);
2064         else
2065                 domain = implicit_bounds(map, data->build);
2066
2067         domain = isl_set_coalesce(domain);
2068         domain = isl_set_make_disjoint(domain);
2069         d1 = isl_set_subtract(isl_set_copy(domain), isl_set_copy(data->domain));
2070         d2 = isl_set_subtract(isl_set_copy(data->domain), isl_set_copy(domain));
2071         data->domain = isl_set_intersect(data->domain, domain);
2072         data->domain = isl_set_union(data->domain, d1);
2073         data->domain = isl_set_union(data->domain, d2);
2074
2075         return 0;
2076 }
2077
2078 /* Separate the schedule domains of "executed".
2079  *
2080  * That is, break up the domain of "executed" into basic sets,
2081  * such that for each basic set S, every element in S is associated with
2082  * the same domain spaces.
2083  *
2084  * "space" is the (single) domain space of "executed".
2085  */
2086 static __isl_give isl_set *separate_schedule_domains(
2087         __isl_take isl_space *space, __isl_take isl_union_map *executed,
2088         __isl_keep isl_ast_build *build)
2089 {
2090         struct isl_separate_domain_data data = { build };
2091         isl_ctx *ctx;
2092
2093         ctx = isl_ast_build_get_ctx(build);
2094         data.explicit = isl_options_get_ast_build_separation_bounds(ctx) ==
2095                                     ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT;
2096         data.domain = isl_set_empty(space);
2097         if (isl_union_map_foreach_map(executed, &separate_domain, &data) < 0)
2098                 data.domain = isl_set_free(data.domain);
2099
2100         isl_union_map_free(executed);
2101         return data.domain;
2102 }
2103
2104 /* Temporary data used during the search for a lower bound for unrolling.
2105  *
2106  * "domain" is the original set for which to find a lower bound
2107  * "depth" is the dimension for which to find a lower boudn
2108  *
2109  * "lower" is the best lower bound found so far.  It is NULL if we have not
2110  * found any yet.
2111  * "n" is the corresponding size.  If lower is NULL, then the value of n
2112  * is undefined.
2113  *
2114  * "tmp" is a temporary initialized isl_int.
2115  */
2116 struct isl_find_unroll_data {
2117         isl_set *domain;
2118         int depth;
2119
2120         isl_aff *lower;
2121         int *n;
2122         isl_int tmp;
2123 };
2124
2125 /* Check if we can use "c" as a lower bound and if it is better than
2126  * any previously found lower bound.
2127  *
2128  * If "c" does not involve the dimension at the current depth,
2129  * then we cannot use it.
2130  * Otherwise, let "c" be of the form
2131  *
2132  *      i >= f(j)/a
2133  *
2134  * We compute the maximal value of
2135  *
2136  *      -ceil(f(j)/a)) + i + 1
2137  *
2138  * over the domain.  If there is such a value "n", then we know
2139  *
2140  *      -ceil(f(j)/a)) + i + 1 <= n
2141  *
2142  * or
2143  *
2144  *      i < ceil(f(j)/a)) + n
2145  *
2146  * meaning that we can use ceil(f(j)/a)) as a lower bound for unrolling.
2147  * We just need to check if we have found any lower bound before and
2148  * if the new lower bound is better (smaller n) than the previously found
2149  * lower bounds.
2150  */
2151 static int update_unrolling_lower_bound(struct isl_find_unroll_data *data,
2152         __isl_keep isl_constraint *c)
2153 {
2154         isl_aff *aff, *lower;
2155         enum isl_lp_result res;
2156
2157         if (!isl_constraint_is_lower_bound(c, isl_dim_set, data->depth))
2158                 return 0;
2159
2160         lower = isl_constraint_get_bound(c, isl_dim_set, data->depth);
2161         lower = isl_aff_ceil(lower);
2162         aff = isl_aff_copy(lower);
2163         aff = isl_aff_neg(aff);
2164         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, data->depth, 1);
2165         aff = isl_aff_add_constant_si(aff, 1);
2166         res = isl_set_max(data->domain, aff, &data->tmp);
2167         isl_aff_free(aff);
2168
2169         if (res == isl_lp_error)
2170                 goto error;
2171         if (res == isl_lp_unbounded) {
2172                 isl_aff_free(lower);
2173                 return 0;
2174         }
2175
2176         if (isl_int_cmp_si(data->tmp, INT_MAX) <= 0 &&
2177             (!data->lower || isl_int_cmp_si(data->tmp, *data->n) < 0)) {
2178                 isl_aff_free(data->lower);
2179                 data->lower = lower;
2180                 *data->n = isl_int_get_si(data->tmp);
2181         } else
2182                 isl_aff_free(lower);
2183
2184         return 1;
2185 error:
2186         isl_aff_free(lower);
2187         return -1;
2188 }
2189
2190 /* Check if we can use "c" as a lower bound and if it is better than
2191  * any previously found lower bound.
2192  */
2193 static int constraint_find_unroll(__isl_take isl_constraint *c, void *user)
2194 {
2195         struct isl_find_unroll_data *data;
2196         int r;
2197
2198         data = (struct isl_find_unroll_data *) user;
2199         r = update_unrolling_lower_bound(data, c);
2200         isl_constraint_free(c);
2201
2202         return r;
2203 }
2204
2205 /* Look for a lower bound l(i) on the dimension at "depth"
2206  * and a size n such that "domain" is a subset of
2207  *
2208  *      { [i] : l(i) <= i_d < l(i) + n }
2209  *
2210  * where d is "depth" and l(i) depends only on earlier dimensions.
2211  * Furthermore, try and find a lower bound such that n is as small as possible.
2212  * In particular, "n" needs to be finite.
2213  *
2214  * Inner dimensions have been eliminated from "domain" by the caller.
2215  *
2216  * We first construct a collection of lower bounds on the input set
2217  * by computing its simple hull.  We then iterate through them,
2218  * discarding those that we cannot use (either because they do not
2219  * involve the dimension at "depth" or because they have no corresponding
2220  * upper bound, meaning that "n" would be unbounded) and pick out the
2221  * best from the remaining ones.
2222  *
2223  * If we cannot find a suitable lower bound, then we consider that
2224  * to be an error.
2225  */
2226 static __isl_give isl_aff *find_unroll_lower_bound(__isl_keep isl_set *domain,
2227         int depth, int *n)
2228 {
2229         struct isl_find_unroll_data data = { domain, depth, NULL, n };
2230         isl_basic_set *hull;
2231
2232         isl_int_init(data.tmp);
2233         hull = isl_set_simple_hull(isl_set_copy(domain));
2234
2235         if (isl_basic_set_foreach_constraint(hull,
2236                                             &constraint_find_unroll, &data) < 0)
2237                 goto error;
2238
2239         isl_basic_set_free(hull);
2240         isl_int_clear(data.tmp);
2241
2242         if (!data.lower)
2243                 isl_die(isl_set_get_ctx(domain), isl_error_invalid,
2244                         "cannot find lower bound for unrolling", return NULL);
2245
2246         return data.lower;
2247 error:
2248         isl_basic_set_free(hull);
2249         isl_int_clear(data.tmp);
2250         return isl_aff_free(data.lower);
2251 }
2252
2253 /* Return the constraint
2254  *
2255  *      i_"depth" = aff + offset
2256  */
2257 static __isl_give isl_constraint *at_offset(int depth, __isl_keep isl_aff *aff,
2258         int offset)
2259 {
2260         aff = isl_aff_copy(aff);
2261         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, depth, -1);
2262         aff = isl_aff_add_constant_si(aff, offset);
2263         return isl_equality_from_aff(aff);
2264 }
2265
2266 /* Return a list of basic sets, one for each value of the current dimension
2267  * in "domain".
2268  * The divs that involve the current dimension have not been projected out
2269  * from this domain.
2270  *
2271  * Since we are going to be iterating over the individual values,
2272  * we first check if there are any strides on the current dimension.
2273  * If there is, we rewrite the current dimension i as
2274  *
2275  *              i = stride i' + offset
2276  *
2277  * and then iterate over individual values of i' instead.
2278  *
2279  * We then look for a lower bound on i' and a size such that the domain
2280  * is a subset of
2281  *
2282  *      { [j,i'] : l(j) <= i' < l(j) + n }
2283  *
2284  * and then take slices of the domain at values of i'
2285  * between l(j) and l(j) + n - 1.
2286  *
2287  * We compute the unshifted simple hull of each slice to ensure that
2288  * we have a single basic set per offset.  The slicing constraint
2289  * may get simplified away before the unshifted simple hull is taken
2290  * and may therefore in some rare cases disappear from the result.
2291  * We therefore explicitly add the constraint back after computing
2292  * the unshifted simple hull to ensure that the basic sets
2293  * remain disjoint.  The constraints that are dropped by taking the hull
2294  * will be taken into account at the next level, as in the case of the
2295  * atomic option.
2296  *
2297  * Finally, we map i' back to i and add each basic set to the list.
2298  */
2299 static __isl_give isl_basic_set_list *do_unroll(__isl_take isl_set *domain,
2300         __isl_keep isl_ast_build *build)
2301 {
2302         int i, n;
2303         int depth;
2304         isl_ctx *ctx;
2305         isl_aff *lower;
2306         isl_basic_set_list *list;
2307         isl_multi_aff *expansion;
2308         isl_basic_map *bmap;
2309
2310         if (!domain)
2311                 return NULL;
2312
2313         ctx = isl_set_get_ctx(domain);
2314         depth = isl_ast_build_get_depth(build);
2315         build = isl_ast_build_copy(build);
2316         domain = isl_ast_build_eliminate_inner(build, domain);
2317         build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
2318         expansion = isl_ast_build_get_stride_expansion(build);
2319
2320         domain = isl_set_preimage_multi_aff(domain,
2321                                             isl_multi_aff_copy(expansion));
2322         domain = isl_ast_build_eliminate_divs(build, domain);
2323
2324         isl_ast_build_free(build);
2325
2326         list = isl_basic_set_list_alloc(ctx, 0);
2327
2328         lower = find_unroll_lower_bound(domain, depth, &n);
2329         if (!lower)
2330                 list = isl_basic_set_list_free(list);
2331
2332         bmap = isl_basic_map_from_multi_aff(expansion);
2333
2334         for (i = 0; list && i < n; ++i) {
2335                 isl_set *set;
2336                 isl_basic_set *bset;
2337                 isl_constraint *slice;
2338
2339                 slice = at_offset(depth, lower, i);
2340                 set = isl_set_copy(domain);
2341                 set = isl_set_add_constraint(set, isl_constraint_copy(slice));
2342                 bset = isl_set_unshifted_simple_hull(set);
2343                 bset = isl_basic_set_add_constraint(bset, slice);
2344                 bset = isl_basic_set_apply(bset, isl_basic_map_copy(bmap));
2345                 list = isl_basic_set_list_add(list, bset);
2346         }
2347
2348         isl_aff_free(lower);
2349         isl_set_free(domain);
2350         isl_basic_map_free(bmap);
2351
2352         return list;
2353 }
2354
2355 /* Data structure for storing the results and the intermediate objects
2356  * of compute_domains.
2357  *
2358  * "list" is the main result of the function and contains a list
2359  * of disjoint basic sets for which code should be generated.
2360  *
2361  * "executed" and "build" are inputs to compute_domains.
2362  * "schedule_domain" is the domain of "executed".
2363  *
2364  * "option" constains the domains at the current depth that should by
2365  * atomic, separated or unrolled.  These domains are as specified by
2366  * the user, except that inner dimensions have been eliminated and
2367  * that they have been made pair-wise disjoint.
2368  *
2369  * "sep_class" contains the user-specified split into separation classes
2370  * specialized to the current depth.
2371  * "done" contains the union of the separation domains that have already
2372  * been handled.
2373  * "atomic" contains the domain that has effectively been made atomic.
2374  * This domain may be larger than the intersection of option[atomic]
2375  * and the schedule domain.
2376  */
2377 struct isl_codegen_domains {
2378         isl_basic_set_list *list;
2379
2380         isl_union_map *executed;
2381         isl_ast_build *build;
2382         isl_set *schedule_domain;
2383
2384         isl_set *option[3];
2385
2386         isl_map *sep_class;
2387         isl_set *done;
2388         isl_set *atomic;
2389 };
2390
2391 /* Add domains to domains->list for each individual value of the current
2392  * dimension, for that part of the schedule domain that lies in the
2393  * intersection of the option domain and the class domain.
2394  *
2395  * "domain" is the intersection of the class domain and the schedule domain.
2396  * The divs that involve the current dimension have not been projected out
2397  * from this domain.
2398  *
2399  * We first break up the unroll option domain into individual pieces
2400  * and then handle each of them separately.  The unroll option domain
2401  * has been made disjoint in compute_domains_init_options,
2402  *
2403  * Note that we actively want to combine different pieces of the
2404  * schedule domain that have the same value at the current dimension.
2405  * We therefore need to break up the unroll option domain before
2406  * intersecting with class and schedule domain, hoping that the
2407  * unroll option domain specified by the user is relatively simple.
2408  */
2409 static int compute_unroll_domains(struct isl_codegen_domains *domains,
2410         __isl_keep isl_set *domain)
2411 {
2412         isl_set *unroll_domain;
2413         isl_basic_set_list *unroll_list;
2414         int i, n;
2415         int empty;
2416
2417         empty = isl_set_is_empty(domains->option[unroll]);
2418         if (empty < 0)
2419                 return -1;
2420         if (empty)
2421                 return 0;
2422
2423         unroll_domain = isl_set_copy(domains->option[unroll]);
2424         unroll_list = isl_basic_set_list_from_set(unroll_domain);
2425
2426         n = isl_basic_set_list_n_basic_set(unroll_list);
2427         for (i = 0; i < n; ++i) {
2428                 isl_basic_set *bset;
2429                 isl_basic_set_list *list;
2430
2431                 bset = isl_basic_set_list_get_basic_set(unroll_list, i);
2432                 unroll_domain = isl_set_from_basic_set(bset);
2433                 unroll_domain = isl_set_intersect(unroll_domain,
2434                                                     isl_set_copy(domain));
2435
2436                 empty = isl_set_is_empty(unroll_domain);
2437                 if (empty >= 0 && empty) {
2438                         isl_set_free(unroll_domain);
2439                         continue;
2440                 }
2441
2442                 list = do_unroll(unroll_domain, domains->build);
2443                 domains->list = isl_basic_set_list_concat(domains->list, list);
2444         }
2445
2446         isl_basic_set_list_free(unroll_list);
2447
2448         return 0;
2449 }
2450
2451 /* Construct a single basic set that includes the intersection of
2452  * the schedule domain, the atomic option domain and the class domain.
2453  * Add the resulting basic set to domains->list and save a copy
2454  * in domains->atomic for use in compute_partial_domains.
2455  *
2456  * We construct a single domain rather than trying to combine
2457  * the schedule domains of individual domains because we are working
2458  * within a single component so that non-overlapping schedule domains
2459  * should already have been separated.
2460  * Note, though, that this does not take into account the class domain.
2461  * So, it is possible for a class domain to carve out a piece of the
2462  * schedule domain with independent pieces and then we would only
2463  * generate a single domain for them.  If this proves to be problematic
2464  * for some users, then this function will have to be adjusted.
2465  *
2466  * "domain" is the intersection of the schedule domain and the class domain,
2467  * with inner dimensions projected out.
2468  */
2469 static int compute_atomic_domain(struct isl_codegen_domains *domains,
2470         __isl_keep isl_set *domain)
2471 {
2472         isl_basic_set *bset;
2473         isl_set *atomic_domain;
2474         int empty;
2475
2476         atomic_domain = isl_set_copy(domains->option[atomic]);
2477         atomic_domain = isl_set_intersect(atomic_domain, isl_set_copy(domain));
2478         empty = isl_set_is_empty(atomic_domain);
2479         if (empty < 0 || empty) {
2480                 domains->atomic = atomic_domain;
2481                 return empty < 0 ? -1 : 0;
2482         }
2483
2484         atomic_domain = isl_set_coalesce(atomic_domain);
2485         bset = isl_set_unshifted_simple_hull(atomic_domain);
2486         domains->atomic = isl_set_from_basic_set(isl_basic_set_copy(bset));
2487         domains->list = isl_basic_set_list_add(domains->list, bset);
2488
2489         return 0;
2490 }
2491
2492 /* Split up the schedule domain into uniform basic sets,
2493  * in the sense that each element in a basic set is associated to
2494  * elements of the same domains, and add the result to domains->list.
2495  * Do this for that part of the schedule domain that lies in the
2496  * intersection of "class_domain" and the separate option domain.
2497  *
2498  * "class_domain" may or may not include the constraints
2499  * of the schedule domain, but this does not make a difference
2500  * since we are going to intersect it with the domain of the inverse schedule.
2501  * If it includes schedule domain constraints, then they may involve
2502  * inner dimensions, but we will eliminate them in separation_domain.
2503  */
2504 static int compute_separate_domain(struct isl_codegen_domains *domains,
2505         __isl_keep isl_set *class_domain)
2506 {
2507         isl_space *space;
2508         isl_set *domain;
2509         isl_union_map *executed;
2510         isl_basic_set_list *list;
2511         int empty;
2512
2513         domain = isl_set_copy(domains->option[separate]);
2514         domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2515         executed = isl_union_map_copy(domains->executed);
2516         executed = isl_union_map_intersect_domain(executed,
2517                                     isl_union_set_from_set(domain));
2518         empty = isl_union_map_is_empty(executed);
2519         if (empty < 0 || empty) {
2520                 isl_union_map_free(executed);
2521                 return empty < 0 ? -1 : 0;
2522         }
2523
2524         space = isl_set_get_space(class_domain);
2525         domain = separate_schedule_domains(space, executed, domains->build);
2526
2527         list = isl_basic_set_list_from_set(domain);
2528         domains->list = isl_basic_set_list_concat(domains->list, list);
2529
2530         return 0;
2531 }
2532
2533 /* Split up the domain at the current depth into disjoint
2534  * basic sets for which code should be generated separately
2535  * for the given separation class domain.
2536  *
2537  * If any separation classes have been defined, then "class_domain"
2538  * is the domain of the current class and does not refer to inner dimensions.
2539  * Otherwise, "class_domain" is the universe domain.
2540  *
2541  * We first make sure that the class domain is disjoint from
2542  * previously considered class domains.
2543  *
2544  * The separate domains can be computed directly from the "class_domain".
2545  *
2546  * The unroll, atomic and remainder domains need the constraints
2547  * from the schedule domain.
2548  *
2549  * For unrolling, the actual schedule domain is needed (with divs that
2550  * may refer to the current dimension) so that stride detection can be
2551  * performed.
2552  *
2553  * For atomic and remainder domains, inner dimensions and divs involving
2554  * the current dimensions should be eliminated.
2555  * In case we are working within a separation class, we need to intersect
2556  * the result with the current "class_domain" to ensure that the domains
2557  * are disjoint from those generated from other class domains.
2558  *
2559  * The domain that has been made atomic may be larger than specified
2560  * by the user since it needs to be representable as a single basic set.
2561  * This possibly larger domain is stored in domains->atomic by
2562  * compute_atomic_domain.
2563  *
2564  * If anything is left after handling separate, unroll and atomic,
2565  * we split it up into basic sets and append the basic sets to domains->list.
2566  */
2567 static int compute_partial_domains(struct isl_codegen_domains *domains,
2568         __isl_take isl_set *class_domain)
2569 {
2570         isl_basic_set_list *list;
2571         isl_set *domain;
2572
2573         class_domain = isl_set_subtract(class_domain,
2574                                         isl_set_copy(domains->done));
2575         domains->done = isl_set_union(domains->done,
2576                                         isl_set_copy(class_domain));
2577
2578         domain = isl_set_copy(class_domain);
2579
2580         if (compute_separate_domain(domains, domain) < 0)
2581                 goto error;
2582         domain = isl_set_subtract(domain,
2583                                     isl_set_copy(domains->option[separate]));
2584
2585         domain = isl_set_intersect(domain,
2586                                 isl_set_copy(domains->schedule_domain));
2587
2588         if (compute_unroll_domains(domains, domain) < 0)
2589                 goto error;
2590         domain = isl_set_subtract(domain,
2591                                     isl_set_copy(domains->option[unroll]));
2592
2593         domain = isl_ast_build_eliminate(domains->build, domain);
2594         domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2595
2596         if (compute_atomic_domain(domains, domain) < 0)
2597                 domain = isl_set_free(domain);
2598         domain = isl_set_subtract(domain, domains->atomic);
2599
2600         domain = isl_set_coalesce(domain);
2601         domain = isl_set_make_disjoint(domain);
2602
2603         list = isl_basic_set_list_from_set(domain);
2604         domains->list = isl_basic_set_list_concat(domains->list, list);
2605
2606         isl_set_free(class_domain);
2607
2608         return 0;
2609 error:
2610         isl_set_free(domain);
2611         isl_set_free(class_domain);
2612         return -1;
2613 }
2614
2615 /* Split up the domain at the current depth into disjoint
2616  * basic sets for which code should be generated separately
2617  * for the separation class identified by "pnt".
2618  *
2619  * We extract the corresponding class domain from domains->sep_class,
2620  * eliminate inner dimensions and pass control to compute_partial_domains.
2621  */
2622 static int compute_class_domains(__isl_take isl_point *pnt, void *user)
2623 {
2624         struct isl_codegen_domains *domains = user;
2625         isl_set *class_set;
2626         isl_set *domain;
2627         int disjoint;
2628
2629         class_set = isl_set_from_point(pnt);
2630         domain = isl_map_domain(isl_map_intersect_range(
2631                                 isl_map_copy(domains->sep_class), class_set));
2632         domain = isl_ast_build_compute_gist(domains->build, domain);
2633         domain = isl_ast_build_eliminate(domains->build, domain);
2634
2635         disjoint = isl_set_plain_is_disjoint(domain, domains->schedule_domain);
2636         if (disjoint < 0)
2637                 return -1;
2638         if (disjoint) {
2639                 isl_set_free(domain);
2640                 return 0;
2641         }
2642
2643         return compute_partial_domains(domains, domain);
2644 }
2645
2646 /* Extract the domains at the current depth that should be atomic,
2647  * separated or unrolled and store them in option.
2648  *
2649  * The domains specified by the user might overlap, so we make
2650  * them disjoint by subtracting earlier domains from later domains.
2651  */
2652 static void compute_domains_init_options(isl_set *option[3],
2653         __isl_keep isl_ast_build *build)
2654 {
2655         enum isl_ast_build_domain_type type, type2;
2656
2657         for (type = atomic; type <= separate; ++type) {
2658                 option[type] = isl_ast_build_get_option_domain(build, type);
2659                 for (type2 = atomic; type2 < type; ++type2)
2660                         option[type] = isl_set_subtract(option[type],
2661                                                 isl_set_copy(option[type2]));
2662         }
2663
2664         option[unroll] = isl_set_coalesce(option[unroll]);
2665         option[unroll] = isl_set_make_disjoint(option[unroll]);
2666 }
2667
2668 /* Split up the domain at the current depth into disjoint
2669  * basic sets for which code should be generated separately,
2670  * based on the user-specified options.
2671  * Return the list of disjoint basic sets.
2672  *
2673  * There are three kinds of domains that we need to keep track of.
2674  * - the "schedule domain" is the domain of "executed"
2675  * - the "class domain" is the domain corresponding to the currrent
2676  *      separation class
2677  * - the "option domain" is the domain corresponding to one of the options
2678  *      atomic, unroll or separate
2679  *
2680  * We first consider the individial values of the separation classes
2681  * and split up the domain for each of them separately.
2682  * Finally, we consider the remainder.  If no separation classes were
2683  * specified, then we call compute_partial_domains with the universe
2684  * "class_domain".  Otherwise, we take the "schedule_domain" as "class_domain",
2685  * with inner dimensions removed.  We do this because we want to
2686  * avoid computing the complement of the class domains (i.e., the difference
2687  * between the universe and domains->done).
2688  */
2689 static __isl_give isl_basic_set_list *compute_domains(
2690         __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2691 {
2692         struct isl_codegen_domains domains;
2693         isl_ctx *ctx;
2694         isl_set *domain;
2695         isl_union_set *schedule_domain;
2696         isl_set *classes;
2697         isl_space *space;
2698         int n_param;
2699         enum isl_ast_build_domain_type type;
2700         int empty;
2701
2702         if (!executed)
2703                 return NULL;
2704
2705         ctx = isl_union_map_get_ctx(executed);
2706         domains.list = isl_basic_set_list_alloc(ctx, 0);
2707
2708         schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
2709         domain = isl_set_from_union_set(schedule_domain);
2710
2711         compute_domains_init_options(domains.option, build);
2712
2713         domains.sep_class = isl_ast_build_get_separation_class(build);
2714         classes = isl_map_range(isl_map_copy(domains.sep_class));
2715         n_param = isl_set_dim(classes, isl_dim_param);
2716         classes = isl_set_project_out(classes, isl_dim_param, 0, n_param);
2717
2718         space = isl_set_get_space(domain);
2719         domains.build = build;
2720         domains.schedule_domain = isl_set_copy(domain);
2721         domains.executed = executed;
2722         domains.done = isl_set_empty(space);
2723
2724         if (isl_set_foreach_point(classes, &compute_class_domains, &domains) < 0)
2725                 domains.list = isl_basic_set_list_free(domains.list);
2726         isl_set_free(classes);
2727
2728         empty = isl_set_is_empty(domains.done);
2729         if (empty < 0) {
2730                 domains.list = isl_basic_set_list_free(domains.list);
2731                 domain = isl_set_free(domain);
2732         } else if (empty) {
2733                 isl_set_free(domain);
2734                 domain = isl_set_universe(isl_set_get_space(domains.done));
2735         } else {
2736                 domain = isl_ast_build_eliminate(build, domain);
2737         }
2738         if (compute_partial_domains(&domains, domain) < 0)
2739                 domains.list = isl_basic_set_list_free(domains.list);
2740
2741         isl_set_free(domains.schedule_domain);
2742         isl_set_free(domains.done);
2743         isl_map_free(domains.sep_class);
2744         for (type = atomic; type <= separate; ++type)
2745                 isl_set_free(domains.option[type]);
2746
2747         return domains.list;
2748 }
2749
2750 /* Generate code for a single component, after shifting (if any)
2751  * has been applied.
2752  *
2753  * We first split up the domain at the current depth into disjoint
2754  * basic sets based on the user-specified options.
2755  * Then we generated code for each of them and concatenate the results.
2756  */
2757 static __isl_give isl_ast_graft_list *generate_shifted_component(
2758         __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
2759 {
2760         isl_basic_set_list *domain_list;
2761         isl_ast_graft_list *list = NULL;
2762
2763         domain_list = compute_domains(executed, build);
2764         list = generate_parallel_domains(domain_list, executed, build);
2765
2766         isl_basic_set_list_free(domain_list);
2767         isl_union_map_free(executed);
2768         isl_ast_build_free(build);
2769
2770         return list;
2771 }
2772
2773 struct isl_set_map_pair {
2774         isl_set *set;
2775         isl_map *map;
2776 };
2777
2778 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2779  * of indices into the "domain" array,
2780  * return the union of the "map" fields of the elements
2781  * indexed by the first "n" elements of "order".
2782  */
2783 static __isl_give isl_union_map *construct_component_executed(
2784         struct isl_set_map_pair *domain, int *order, int n)
2785 {
2786         int i;
2787         isl_map *map;
2788         isl_union_map *executed;
2789
2790         map = isl_map_copy(domain[order[0]].map);
2791         executed = isl_union_map_from_map(map);
2792         for (i = 1; i < n; ++i) {
2793                 map = isl_map_copy(domain[order[i]].map);
2794                 executed = isl_union_map_add_map(executed, map);
2795         }
2796
2797         return executed;
2798 }
2799
2800 /* Generate code for a single component, after shifting (if any)
2801  * has been applied.
2802  *
2803  * The component inverse schedule is specified as the "map" fields
2804  * of the elements of "domain" indexed by the first "n" elements of "order".
2805  */
2806 static __isl_give isl_ast_graft_list *generate_shifted_component_from_list(
2807         struct isl_set_map_pair *domain, int *order, int n,
2808         __isl_take isl_ast_build *build)
2809 {
2810         isl_union_map *executed;
2811
2812         executed = construct_component_executed(domain, order, n);
2813         return generate_shifted_component(executed, build);
2814 }
2815
2816 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2817  * of indices into the "domain" array,
2818  * do all (except for at most one) of the "set" field of the elements
2819  * indexed by the first "n" elements of "order" have a fixed value
2820  * at position "depth"?
2821  */
2822 static int at_most_one_non_fixed(struct isl_set_map_pair *domain,
2823         int *order, int n, int depth)
2824 {
2825         int i;
2826         int non_fixed = -1;
2827
2828         for (i = 0; i < n; ++i) {
2829                 int f;
2830
2831                 f = isl_set_plain_is_fixed(domain[order[i]].set,
2832                                                 isl_dim_set, depth, NULL);
2833                 if (f < 0)
2834                         return -1;
2835                 if (f)
2836                         continue;
2837                 if (non_fixed >= 0)
2838                         return 0;
2839                 non_fixed = i;
2840         }
2841
2842         return 1;
2843 }
2844
2845 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2846  * of indices into the "domain" array,
2847  * eliminate the inner dimensions from the "set" field of the elements
2848  * indexed by the first "n" elements of "order", provided the current
2849  * dimension does not have a fixed value.
2850  *
2851  * Return the index of the first element in "order" with a corresponding
2852  * "set" field that does not have an (obviously) fixed value.
2853  */
2854 static int eliminate_non_fixed(struct isl_set_map_pair *domain,
2855         int *order, int n, int depth, __isl_keep isl_ast_build *build)
2856 {
2857         int i;
2858         int base = -1;
2859
2860         for (i = n - 1; i >= 0; --i) {
2861                 int f;
2862                 f = isl_set_plain_is_fixed(domain[order[i]].set,
2863                                                 isl_dim_set, depth, NULL);
2864                 if (f < 0)
2865                         return -1;
2866                 if (f)
2867                         continue;
2868                 domain[order[i]].set = isl_ast_build_eliminate_inner(build,
2869                                                         domain[order[i]].set);
2870                 base = i;
2871         }
2872
2873         return base;
2874 }
2875
2876 /* Given an array "domain" of isl_set_map_pairs and an array "order"
2877  * of indices into the "domain" array,
2878  * find the element of "domain" (amongst those indexed by the first "n"
2879  * elements of "order") with the "set" field that has the smallest
2880  * value for the current iterator.
2881  *
2882  * Note that the domain with the smallest value may depend on the parameters
2883  * and/or outer loop dimension.  Since the result of this function is only
2884  * used as heuristic, we only make a reasonable attempt at finding the best
2885  * domain, one that should work in case a single domain provides the smallest
2886  * value for the current dimension over all values of the parameters
2887  * and outer dimensions.
2888  *
2889  * In particular, we compute the smallest value of the first domain
2890  * and replace it by that of any later domain if that later domain
2891  * has a smallest value that is smaller for at least some value
2892  * of the parameters and outer dimensions.
2893  */
2894 static int first_offset(struct isl_set_map_pair *domain, int *order, int n,
2895         __isl_keep isl_ast_build *build)
2896 {
2897         int i;
2898         isl_map *min_first;
2899         int first = 0;
2900
2901         min_first = isl_ast_build_map_to_iterator(build,
2902                                         isl_set_copy(domain[order[0]].set));
2903         min_first = isl_map_lexmin(min_first);
2904
2905         for (i = 1; i < n; ++i) {
2906                 isl_map *min, *test;
2907                 int empty;
2908
2909                 min = isl_ast_build_map_to_iterator(build,
2910                                         isl_set_copy(domain[order[i]].set));
2911                 min = isl_map_lexmin(min);
2912                 test = isl_map_copy(min);
2913                 test = isl_map_apply_domain(isl_map_copy(min_first), test);
2914                 test = isl_map_order_lt(test, isl_dim_in, 0, isl_dim_out, 0);
2915                 empty = isl_map_is_empty(test);
2916                 isl_map_free(test);
2917                 if (empty >= 0 && !empty) {
2918                         isl_map_free(min_first);
2919                         first = i;
2920                         min_first = min;
2921                 } else
2922                         isl_map_free(min);
2923
2924                 if (empty < 0)
2925                         break;
2926         }
2927
2928         isl_map_free(min_first);
2929
2930         return i < n ? -1 : first;
2931 }
2932
2933 /* Construct a shifted inverse schedule based on the original inverse schedule,
2934  * the stride and the offset.
2935  *
2936  * The original inverse schedule is specified as the "map" fields
2937  * of the elements of "domain" indexed by the first "n" elements of "order".
2938  *
2939  * "stride" and "offset" are such that the difference
2940  * between the values of the current dimension of domain "i"
2941  * and the values of the current dimension for some reference domain are
2942  * equal to
2943  *
2944  *      stride * integer + offset[i]
2945  *
2946  * Moreover, 0 <= offset[i] < stride.
2947  *
2948  * For each domain, we create a map
2949  *
2950  *      { [..., j, ...] -> [..., j - offset[i], offset[i], ....] }
2951  *
2952  * where j refers to the current dimension and the other dimensions are
2953  * unchanged, and apply this map to the original schedule domain.
2954  *
2955  * For example, for the original schedule
2956  *
2957  *      { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
2958  *
2959  * and assuming the offset is 0 for the A domain and 1 for the B domain,
2960  * we apply the mapping
2961  *
2962  *      { [j] -> [j, 0] }
2963  *
2964  * to the schedule of the "A" domain and the mapping
2965  *
2966  *      { [j - 1] -> [j, 1] }
2967  *
2968  * to the schedule of the "B" domain.
2969  *
2970  *
2971  * Note that after the transformation, the differences between pairs
2972  * of values of the current dimension over all domains are multiples
2973  * of stride and that we have therefore exposed the stride.
2974  *
2975  *
2976  * To see that the mapping preserves the lexicographic order,
2977  * first note that each of the individual maps above preserves the order.
2978  * If the value of the current iterator is j1 in one domain and j2 in another,
2979  * then if j1 = j2, we know that the same map is applied to both domains
2980  * and the order is preserved.
2981  * Otherwise, let us assume, without loss of generality, that j1 < j2.
2982  * If c1 >= c2 (with c1 and c2 the corresponding offsets), then
2983  *
2984  *      j1 - c1 < j2 - c2
2985  *
2986  * and the order is preserved.
2987  * If c1 < c2, then we know
2988  *
2989  *      0 <= c2 - c1 < s
2990  *
2991  * We also have
2992  *
2993  *      j2 - j1 = n * s + r
2994  *
2995  * with n >= 0 and 0 <= r < s.
2996  * In other words, r = c2 - c1.
2997  * If n > 0, then
2998  *
2999  *      j1 - c1 < j2 - c2
3000  *
3001  * If n = 0, then
3002  *
3003  *      j1 - c1 = j2 - c2
3004  *
3005  * and so
3006  *
3007  *      (j1 - c1, c1) << (j2 - c2, c2)
3008  *
3009  * with "<<" the lexicographic order, proving that the order is preserved
3010  * in all cases.
3011  */
3012 static __isl_give isl_union_map *contruct_shifted_executed(
3013         struct isl_set_map_pair *domain, int *order, int n, isl_int stride,
3014         __isl_keep isl_vec *offset, __isl_keep isl_ast_build *build)
3015 {
3016         int i;
3017         isl_int v;
3018         isl_union_map *executed;
3019         isl_space *space;
3020         isl_map *map;
3021         int depth;
3022         isl_constraint *c;
3023
3024         depth = isl_ast_build_get_depth(build);
3025         space = isl_ast_build_get_space(build, 1);
3026         executed = isl_union_map_empty(isl_space_copy(space));
3027         space = isl_space_map_from_set(space);
3028         map = isl_map_identity(isl_space_copy(space));
3029         map = isl_map_eliminate(map, isl_dim_out, depth, 1);
3030         map = isl_map_insert_dims(map, isl_dim_out, depth + 1, 1);
3031         space = isl_space_insert_dims(space, isl_dim_out, depth + 1, 1);
3032
3033         c = isl_equality_alloc(isl_local_space_from_space(space));
3034         c = isl_constraint_set_coefficient_si(c, isl_dim_in, depth, 1);
3035         c = isl_constraint_set_coefficient_si(c, isl_dim_out, depth, -1);
3036
3037         isl_int_init(v);
3038
3039         for (i = 0; i < n; ++i) {
3040                 isl_map *map_i;
3041
3042                 if (isl_vec_get_element(offset, i, &v) < 0)
3043                         break;
3044                 map_i = isl_map_copy(map);
3045                 map_i = isl_map_fix(map_i, isl_dim_out, depth + 1, v);
3046                 isl_int_neg(v, v);
3047                 c = isl_constraint_set_constant(c, v);
3048                 map_i = isl_map_add_constraint(map_i, isl_constraint_copy(c));
3049
3050                 map_i = isl_map_apply_domain(isl_map_copy(domain[order[i]].map),
3051                                                 map_i);
3052                 executed = isl_union_map_add_map(executed, map_i);
3053         }
3054
3055         isl_constraint_free(c);
3056         isl_map_free(map);
3057
3058         isl_int_clear(v);
3059
3060         if (i < n)
3061                 executed = isl_union_map_free(executed);
3062
3063         return executed;
3064 }
3065
3066 /* Generate code for a single component, after exposing the stride,
3067  * given that the schedule domain is "shifted strided".
3068  *
3069  * The component inverse schedule is specified as the "map" fields
3070  * of the elements of "domain" indexed by the first "n" elements of "order".
3071  *
3072  * The schedule domain being "shifted strided" means that the differences
3073  * between the values of the current dimension of domain "i"
3074  * and the values of the current dimension for some reference domain are
3075  * equal to
3076  *
3077  *      stride * integer + offset[i]
3078  *
3079  * We first look for the domain with the "smallest" value for the current
3080  * dimension and adjust the offsets such that the offset of the "smallest"
3081  * domain is equal to zero.  The other offsets are reduced modulo stride.
3082  *
3083  * Based on this information, we construct a new inverse schedule in
3084  * contruct_shifted_executed that exposes the stride.
3085  * Since this involves the introduction of a new schedule dimension,
3086  * the build needs to be changed accodingly.
3087  * After computing the AST, the newly introduced dimension needs
3088  * to be removed again from the list of grafts.  We do this by plugging
3089  * in a mapping that represents the new schedule domain in terms of the
3090  * old schedule domain.
3091  */
3092 static __isl_give isl_ast_graft_list *generate_shift_component(
3093         struct isl_set_map_pair *domain, int *order, int n, isl_int stride,
3094         __isl_keep isl_vec *offset, __isl_take isl_ast_build *build)
3095 {
3096         isl_ast_graft_list *list;
3097         int first;
3098         int depth;
3099         isl_ctx *ctx;
3100         isl_int val;
3101         isl_vec *v;
3102         isl_space *space;
3103         isl_multi_aff *ma, *zero;
3104         isl_union_map *executed;
3105
3106         ctx = isl_ast_build_get_ctx(build);
3107         depth = isl_ast_build_get_depth(build);
3108
3109         first = first_offset(domain, order, n, build);
3110         if (first < 0)
3111                 return isl_ast_build_free(build);
3112
3113         isl_int_init(val);
3114         v = isl_vec_alloc(ctx, n);
3115         if (isl_vec_get_element(offset, first, &val) < 0)
3116                 v = isl_vec_free(v);
3117         isl_int_neg(val, val);
3118         v = isl_vec_set(v, val);
3119         v = isl_vec_add(v, isl_vec_copy(offset));
3120         v = isl_vec_fdiv_r(v, stride);
3121
3122         executed = contruct_shifted_executed(domain, order, n, stride, v,
3123                                                 build);
3124         space = isl_ast_build_get_space(build, 1);
3125         space = isl_space_map_from_set(space);
3126         ma = isl_multi_aff_identity(isl_space_copy(space));
3127         space = isl_space_from_domain(isl_space_domain(space));
3128         space = isl_space_add_dims(space, isl_dim_out, 1);
3129         zero = isl_multi_aff_zero(space);
3130         ma = isl_multi_aff_range_splice(ma, depth + 1, zero);
3131         build = isl_ast_build_insert_dim(build, depth + 1);
3132         list = generate_shifted_component(executed, build);
3133
3134         list = isl_ast_graft_list_preimage_multi_aff(list, ma);
3135
3136         isl_vec_free(v);
3137         isl_int_clear(val);
3138
3139         return list;
3140 }
3141
3142 /* Generate code for a single component.
3143  *
3144  * The component inverse schedule is specified as the "map" fields
3145  * of the elements of "domain" indexed by the first "n" elements of "order".
3146  *
3147  * This function may modify the "set" fields of "domain".
3148  *
3149  * Before proceeding with the actual code generation for the component,
3150  * we first check if there are any "shifted" strides, meaning that
3151  * the schedule domains of the individual domains are all strided,
3152  * but that they have different offsets, resulting in the union
3153  * of schedule domains not being strided anymore.
3154  *
3155  * The simplest example is the schedule
3156  *
3157  *      { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3158  *
3159  * Both schedule domains are strided, but their union is not.
3160  * This function detects such cases and then rewrites the schedule to
3161  *
3162  *      { A[i] -> [2i, 0]: 0 <= i < 10; B[i] -> [2i, 1] : 0 <= i < 10 }
3163  *
3164  * In the new schedule, the schedule domains have the same offset (modulo
3165  * the stride), ensuring that the union of schedule domains is also strided.
3166  *
3167  *
3168  * If there is only a single domain in the component, then there is
3169  * nothing to do.   Similarly, if the current schedule dimension has
3170  * a fixed value for almost all domains then there is nothing to be done.
3171  * In particular, we need at least two domains where the current schedule
3172  * dimension does not have a fixed value.
3173  * Finally, if any of the options refer to the current schedule dimension,
3174  * then we bail out as well.  It would be possible to reformulate the options
3175  * in terms of the new schedule domain, but that would introduce constraints
3176  * that separate the domains in the options and that is something we would
3177  * like to avoid.
3178  *
3179  *
3180  * To see if there is any shifted stride, we look at the differences
3181  * between the values of the current dimension in pairs of domains
3182  * for equal values of outer dimensions.  These differences should be
3183  * of the form
3184  *
3185  *      m x + r
3186  *
3187  * with "m" the stride and "r" a constant.  Note that we cannot perform
3188  * this analysis on individual domains as the lower bound in each domain
3189  * may depend on parameters or outer dimensions and so the current dimension
3190  * itself may not have a fixed remainder on division by the stride.
3191  *
3192  * In particular, we compare the first domain that does not have an
3193  * obviously fixed value for the current dimension to itself and all
3194  * other domains and collect the offsets and the gcd of the strides.
3195  * If the gcd becomes one, then we failed to find shifted strides.
3196  * If all the offsets are the same (for those domains that do not have
3197  * an obviously fixed value for the current dimension), then we do not
3198  * apply the transformation.
3199  * If none of the domains were skipped, then there is nothing to do.
3200  * If some of them were skipped, then if we apply separation, the schedule
3201  * domain should get split in pieces with a (non-shifted) stride.
3202  *
3203  * Otherwise, we apply a shift to expose the stride in
3204  * generate_shift_component.
3205  */
3206 static __isl_give isl_ast_graft_list *generate_component(
3207         struct isl_set_map_pair *domain, int *order, int n,
3208         __isl_take isl_ast_build *build)
3209 {
3210         int i, d;
3211         int depth;
3212         isl_ctx *ctx;
3213         isl_map *map;
3214         isl_set *deltas;
3215         isl_int m, r, gcd;
3216         isl_vec *v;
3217         int fixed, skip;
3218         int base;
3219         isl_ast_graft_list *list;
3220         int res = 0;
3221
3222         depth = isl_ast_build_get_depth(build);
3223
3224         skip = n == 1;
3225         if (skip >= 0 && !skip)
3226                 skip = at_most_one_non_fixed(domain, order, n, depth);
3227         if (skip >= 0 && !skip)
3228                 skip = isl_ast_build_options_involve_depth(build);
3229         if (skip < 0)
3230                 return isl_ast_build_free(build);
3231         if (skip)
3232                 return generate_shifted_component_from_list(domain,
3233                                                             order, n, build);
3234
3235         base = eliminate_non_fixed(domain, order, n, depth, build);
3236         if (base < 0)
3237                 return isl_ast_build_free(build);
3238
3239         ctx = isl_ast_build_get_ctx(build);
3240
3241         isl_int_init(m);
3242         isl_int_init(r);
3243         isl_int_init(gcd);
3244         v = isl_vec_alloc(ctx, n);
3245
3246         fixed = 1;
3247         for (i = 0; i < n; ++i) {
3248                 map = isl_map_from_domain_and_range(
3249                                         isl_set_copy(domain[order[base]].set),
3250                                         isl_set_copy(domain[order[i]].set));
3251                 for (d = 0; d < depth; ++d)
3252                         map = isl_map_equate(map, isl_dim_in, d,
3253                                                     isl_dim_out, d);
3254                 deltas = isl_map_deltas(map);
3255                 res = isl_set_dim_residue_class(deltas, depth, &m, &r);
3256                 isl_set_free(deltas);
3257                 if (res < 0)
3258                         break;
3259
3260                 if (i == 0)
3261                         isl_int_set(gcd, m);
3262                 else
3263                         isl_int_gcd(gcd, gcd, m);
3264                 if (isl_int_is_one(gcd))
3265                         break;
3266                 v = isl_vec_set_element(v, i, r);
3267
3268                 res = isl_set_plain_is_fixed(domain[order[i]].set,
3269                                                 isl_dim_set, depth, NULL);
3270                 if (res < 0)
3271                         break;
3272                 if (res)
3273                         continue;
3274
3275                 if (fixed && i > base) {
3276                         isl_vec_get_element(v, base, &m);
3277                         if (isl_int_ne(m, r))
3278                                 fixed = 0;
3279                 }
3280         }
3281
3282         if (res < 0) {
3283                 isl_ast_build_free(build);
3284                 list = NULL;
3285         } else if (i < n || fixed) {
3286                 list = generate_shifted_component_from_list(domain,
3287                                                             order, n, build);
3288         } else {
3289                 list = generate_shift_component(domain, order, n, gcd, v,
3290                                                 build);
3291         }
3292
3293         isl_vec_free(v);
3294         isl_int_clear(gcd);
3295         isl_int_clear(r);
3296         isl_int_clear(m);
3297
3298         return list;
3299 }
3300
3301 /* Store both "map" itself and its domain in the
3302  * structure pointed to by *next and advance to the next array element.
3303  */
3304 static int extract_domain(__isl_take isl_map *map, void *user)
3305 {
3306         struct isl_set_map_pair **next = user;
3307
3308         (*next)->map = isl_map_copy(map);
3309         (*next)->set = isl_map_domain(map);
3310         (*next)++;
3311
3312         return 0;
3313 }
3314
3315 /* Internal data for any_scheduled_after.
3316  *
3317  * "depth" is the number of loops that have already been generated
3318  * "group_coscheduled" is a local copy of options->ast_build_group_coscheduled
3319  * "domain" is an array of set-map pairs corresponding to the different
3320  * iteration domains.  The set is the schedule domain, i.e., the domain
3321  * of the inverse schedule, while the map is the inverse schedule itself.
3322  */
3323 struct isl_any_scheduled_after_data {
3324         int depth;
3325         int group_coscheduled;
3326         struct isl_set_map_pair *domain;
3327 };
3328
3329 /* Is any element of domain "i" scheduled after any element of domain "j"
3330  * (for a common iteration of the first data->depth loops)?
3331  *
3332  * data->domain[i].set contains the domain of the inverse schedule
3333  * for domain "i", i.e., elements in the schedule domain.
3334  *
3335  * If data->group_coscheduled is set, then we also return 1 if there
3336  * is any pair of elements in the two domains that are scheduled together.
3337  */
3338 static int any_scheduled_after(int i, int j, void *user)
3339 {
3340         struct isl_any_scheduled_after_data *data = user;
3341         int dim = isl_set_dim(data->domain[i].set, isl_dim_set);
3342         int pos;
3343
3344         for (pos = data->depth; pos < dim; ++pos) {
3345                 int follows;
3346
3347                 follows = isl_set_follows_at(data->domain[i].set,
3348                                                 data->domain[j].set, pos);
3349
3350                 if (follows < -1)
3351                         return -1;
3352                 if (follows > 0)
3353                         return 1;
3354                 if (follows < 0)
3355                         return 0;
3356         }
3357
3358         return data->group_coscheduled;
3359 }
3360
3361 /* Look for independent components at the current depth and generate code
3362  * for each component separately.  The resulting lists of grafts are
3363  * merged in an attempt to combine grafts with identical guards.
3364  *
3365  * Code for two domains can be generated separately if all the elements
3366  * of one domain are scheduled before (or together with) all the elements
3367  * of the other domain.  We therefore consider the graph with as nodes
3368  * the domains and an edge between two nodes if any element of the first
3369  * node is scheduled after any element of the second node.
3370  * If the ast_build_group_coscheduled is set, then we also add an edge if
3371  * there is any pair of elements in the two domains that are scheduled
3372  * together.
3373  * Code is then generated (by generate_component)
3374  * for each of the strongly connected components in this graph
3375  * in their topological order.
3376  *
3377  * Since the test is performed on the domain of the inverse schedules of
3378  * the different domains, we precompute these domains and store
3379  * them in data.domain.
3380  */
3381 static __isl_give isl_ast_graft_list *generate_components(
3382         __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3383 {
3384         int i;
3385         isl_ctx *ctx = isl_ast_build_get_ctx(build);
3386         int n = isl_union_map_n_map(executed);
3387         struct isl_any_scheduled_after_data data;
3388         struct isl_set_map_pair *next;
3389         struct isl_tarjan_graph *g = NULL;
3390         isl_ast_graft_list *list = NULL;
3391         int n_domain = 0;
3392
3393         data.domain = isl_calloc_array(ctx, struct isl_set_map_pair, n);
3394         if (!data.domain)
3395                 goto error;
3396         n_domain = n;
3397
3398         next = data.domain;
3399         if (isl_union_map_foreach_map(executed, &extract_domain, &next) < 0)
3400                 goto error;
3401
3402         if (!build)
3403                 goto error;
3404         data.depth = isl_ast_build_get_depth(build);
3405         data.group_coscheduled = isl_options_get_ast_build_group_coscheduled(ctx);
3406         g = isl_tarjan_graph_init(ctx, n, &any_scheduled_after, &data);
3407
3408         list = isl_ast_graft_list_alloc(ctx, 0);
3409
3410         i = 0;
3411         while (list && n) {
3412                 isl_ast_graft_list *list_c;
3413                 int first = i;
3414
3415                 if (g->order[i] == -1)
3416                         isl_die(ctx, isl_error_internal, "cannot happen",
3417                                 goto error);
3418                 ++i; --n;
3419                 while (g->order[i] != -1) {
3420                         ++i; --n;
3421                 }
3422
3423                 list_c = generate_component(data.domain,
3424                                             g->order + first, i - first,
3425                                             isl_ast_build_copy(build));
3426                 list = isl_ast_graft_list_merge(list, list_c, build);
3427
3428                 ++i;
3429         }
3430
3431         if (0)
3432 error:          list = isl_ast_graft_list_free(list);
3433         isl_tarjan_graph_free(g);
3434         for (i = 0; i < n_domain; ++i) {
3435                 isl_map_free(data.domain[i].map);
3436                 isl_set_free(data.domain[i].set);
3437         }
3438         free(data.domain);
3439         isl_union_map_free(executed);
3440         isl_ast_build_free(build);
3441
3442         return list;
3443 }
3444
3445 /* Generate code for the next level (and all inner levels).
3446  *
3447  * If "executed" is empty, i.e., no code needs to be generated,
3448  * then we return an empty list.
3449  *
3450  * If we have already generated code for all loop levels, then we pass
3451  * control to generate_inner_level.
3452  *
3453  * If "executed" lives in a single space, i.e., if code needs to be
3454  * generated for a single domain, then there can only be a single
3455  * component and we go directly to generate_shifted_component.
3456  * Otherwise, we call generate_components to detect the components
3457  * and to call generate_component on each of them separately.
3458  */
3459 static __isl_give isl_ast_graft_list *generate_next_level(
3460         __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3461 {
3462         int depth;
3463
3464         if (!build || !executed)
3465                 goto error;
3466
3467         if (isl_union_map_is_empty(executed)) {
3468                 isl_ctx *ctx = isl_ast_build_get_ctx(build);
3469                 isl_union_map_free(executed);
3470                 isl_ast_build_free(build);
3471                 return isl_ast_graft_list_alloc(ctx, 0);
3472         }
3473
3474         depth = isl_ast_build_get_depth(build);
3475         if (depth >= isl_set_dim(build->domain, isl_dim_set))
3476                 return generate_inner_level(executed, build);
3477
3478         if (isl_union_map_n_map(executed) == 1)
3479                 return generate_shifted_component(executed, build);
3480
3481         return generate_components(executed, build);
3482 error:
3483         isl_union_map_free(executed);
3484         isl_ast_build_free(build);
3485         return NULL;
3486 }
3487
3488 /* Internal data structure used by isl_ast_build_ast_from_schedule.
3489  * internal, executed and build are the inputs to generate_code.
3490  * list collects the output.
3491  */
3492 struct isl_generate_code_data {
3493         int internal;
3494         isl_union_map *executed;
3495         isl_ast_build *build;
3496
3497         isl_ast_graft_list *list;
3498 };
3499
3500 /* Given an inverse schedule in terms of the external build schedule, i.e.,
3501  *
3502  *      [E -> S] -> D
3503  *
3504  * with E the external build schedule and S the additional schedule "space",
3505  * reformulate the inverse schedule in terms of the internal schedule domain,
3506  * i.e., return
3507  *
3508  *      [I -> S] -> D
3509  *
3510  * We first obtain a mapping
3511  *
3512  *      I -> E
3513  *
3514  * take the inverse and the product with S -> S, resulting in
3515  *
3516  *      [I -> S] -> [E -> S]
3517  *
3518  * Applying the map to the input produces the desired result.
3519  */
3520 static __isl_give isl_union_map *internal_executed(
3521         __isl_take isl_union_map *executed, __isl_keep isl_space *space,
3522         __isl_keep isl_ast_build *build)
3523 {
3524         isl_map *id, *proj;
3525
3526         proj = isl_ast_build_get_schedule_map(build);
3527         proj = isl_map_reverse(proj);
3528         space = isl_space_map_from_set(isl_space_copy(space));
3529         id = isl_map_identity(space);
3530         proj = isl_map_product(proj, id);
3531         executed = isl_union_map_apply_domain(executed,
3532                                                 isl_union_map_from_map(proj));
3533         return executed;
3534 }
3535
3536 /* Generate an AST that visits the elements in the range of data->executed
3537  * in the relative order specified by the corresponding image element(s)
3538  * for those image elements that belong to "set".
3539  * Add the result to data->list.
3540  *
3541  * The caller ensures that "set" is a universe domain.
3542  * "space" is the space of the additional part of the schedule.
3543  * It is equal to the space of "set" if build->domain is parametric.
3544  * Otherwise, it is equal to the range of the wrapped space of "set".
3545  *
3546  * If the build space is not parametric and if isl_ast_build_ast_from_schedule
3547  * was called from an outside user (data->internal not set), then
3548  * the (inverse) schedule refers to the external build domain and needs to
3549  * be transformed to refer to the internal build domain.
3550  *
3551  * The build is extended to include the additional part of the schedule.
3552  * If the original build space was not parametric, then the options
3553  * in data->build refer only to the additional part of the schedule
3554  * and they need to be adjusted to refer to the complete AST build
3555  * domain.
3556  *
3557  * After having adjusted inverse schedule and build, we start generating
3558  * code with the outer loop of the current code generation
3559  * in generate_next_level.
3560  *
3561  * If the original build space was not parametric, we undo the embedding
3562  * on the resulting isl_ast_node_list so that it can be used within
3563  * the outer AST build.
3564  */
3565 static int generate_code_in_space(struct isl_generate_code_data *data,
3566         __isl_take isl_set *set, __isl_take isl_space *space)
3567 {
3568         isl_union_map *executed;
3569         isl_ast_build *build;
3570         isl_ast_graft_list *list;
3571         int embed;
3572
3573         executed = isl_union_map_copy(data->executed);
3574         executed = isl_union_map_intersect_domain(executed,
3575                                                  isl_union_set_from_set(set));
3576
3577         embed = !isl_set_is_params(data->build->domain);
3578         if (embed && !data->internal)
3579                 executed = internal_executed(executed, space, data->build);
3580
3581         build = isl_ast_build_copy(data->build);
3582         build = isl_ast_build_product(build, space);
3583
3584         list = generate_next_level(executed, build);
3585
3586         list = isl_ast_graft_list_unembed(list, embed);
3587
3588         data->list = isl_ast_graft_list_concat(data->list, list);
3589
3590         return 0;
3591 }
3592
3593 /* Generate an AST that visits the elements in the range of data->executed
3594  * in the relative order specified by the corresponding domain element(s)
3595  * for those domain elements that belong to "set".
3596  * Add the result to data->list.
3597  *
3598  * The caller ensures that "set" is a universe domain.
3599  *
3600  * If the build space S is not parametric, then the space of "set"
3601  * need to be a wrapped relation with S as domain.  That is, it needs
3602  * to be of the form
3603  *
3604  *      [S -> T]
3605  *
3606  * Check this property and pass control to generate_code_in_space
3607  * passing along T.
3608  * If the build space is not parametric, then T is the space of "set".
3609  */
3610 static int generate_code_set(__isl_take isl_set *set, void *user)
3611 {
3612         struct isl_generate_code_data *data = user;
3613         isl_space *space, *build_space;
3614         int is_domain;
3615
3616         space = isl_set_get_space(set);
3617
3618         if (isl_set_is_params(data->build->domain))
3619                 return generate_code_in_space(data, set, space);
3620
3621         build_space = isl_ast_build_get_space(data->build, data->internal);
3622         space = isl_space_unwrap(space);
3623         is_domain = isl_space_is_domain(build_space, space);
3624         isl_space_free(build_space);
3625         space = isl_space_range(space);
3626
3627         if (is_domain < 0)
3628                 goto error;
3629         if (!is_domain)
3630                 isl_die(isl_set_get_ctx(set), isl_error_invalid,
3631                         "invalid nested schedule space", goto error);
3632
3633         return generate_code_in_space(data, set, space);
3634 error:
3635         isl_set_free(set);
3636         isl_space_free(space);
3637         return -1;
3638 }
3639
3640 /* Generate an AST that visits the elements in the range of "executed"
3641  * in the relative order specified by the corresponding domain element(s).
3642  *
3643  * "build" is an isl_ast_build that has either been constructed by
3644  * isl_ast_build_from_context or passed to a callback set by
3645  * isl_ast_build_set_create_leaf.
3646  * In the first case, the space of the isl_ast_build is typically
3647  * a parametric space, although this is currently not enforced.
3648  * In the second case, the space is never a parametric space.
3649  * If the space S is not parametric, then the domain space(s) of "executed"
3650  * need to be wrapped relations with S as domain.
3651  *
3652  * If the domain of "executed" consists of several spaces, then an AST
3653  * is generated for each of them (in arbitrary order) and the results
3654  * are concatenated.
3655  *
3656  * If "internal" is set, then the domain "S" above refers to the internal
3657  * schedule domain representation.  Otherwise, it refers to the external
3658  * representation, as returned by isl_ast_build_get_schedule_space.
3659  *
3660  * We essentially run over all the spaces in the domain of "executed"
3661  * and call generate_code_set on each of them.
3662  */
3663 static __isl_give isl_ast_graft_list *generate_code(
3664         __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
3665         int internal)
3666 {
3667         isl_ctx *ctx;
3668         struct isl_generate_code_data data = { 0 };
3669         isl_space *space;
3670         isl_union_set *schedule_domain;
3671         isl_union_map *universe;
3672
3673         if (!build)
3674                 goto error;
3675         space = isl_ast_build_get_space(build, 1);
3676         space = isl_space_align_params(space,
3677                                     isl_union_map_get_space(executed));
3678         space = isl_space_align_params(space,
3679                                     isl_union_map_get_space(build->options));
3680         build = isl_ast_build_align_params(build, isl_space_copy(space));
3681         executed = isl_union_map_align_params(executed, space);
3682         if (!executed || !build)
3683                 goto error;
3684
3685         ctx = isl_ast_build_get_ctx(build);
3686
3687         data.internal = internal;
3688         data.executed = executed;
3689         data.build = build;
3690         data.list = isl_ast_graft_list_alloc(ctx, 0);
3691
3692         universe = isl_union_map_universe(isl_union_map_copy(executed));
3693         schedule_domain = isl_union_map_domain(universe);
3694         if (isl_union_set_foreach_set(schedule_domain, &generate_code_set,
3695                                         &data) < 0)
3696                 data.list = isl_ast_graft_list_free(data.list);
3697
3698         isl_union_set_free(schedule_domain);
3699         isl_union_map_free(executed);
3700
3701         isl_ast_build_free(build);
3702         return data.list;
3703 error:
3704         isl_union_map_free(executed);
3705         isl_ast_build_free(build);
3706         return NULL;
3707 }
3708
3709 /* Generate an AST that visits the elements in the domain of "schedule"
3710  * in the relative order specified by the corresponding image element(s).
3711  *
3712  * "build" is an isl_ast_build that has either been constructed by
3713  * isl_ast_build_from_context or passed to a callback set by
3714  * isl_ast_build_set_create_leaf.
3715  * In the first case, the space of the isl_ast_build is typically
3716  * a parametric space, although this is currently not enforced.
3717  * In the second case, the space is never a parametric space.
3718  * If the space S is not parametric, then the range space(s) of "schedule"
3719  * need to be wrapped relations with S as domain.
3720  *
3721  * If the range of "schedule" consists of several spaces, then an AST
3722  * is generated for each of them (in arbitrary order) and the results
3723  * are concatenated.
3724  *
3725  * We first initialize the local copies of the relevant options.
3726  * We do this here rather than when the isl_ast_build is created
3727  * because the options may have changed between the construction
3728  * of the isl_ast_build and the call to isl_generate_code.
3729  *
3730  * The main computation is performed on an inverse schedule (with
3731  * the schedule domain in the domain and the elements to be executed
3732  * in the range) called "executed".
3733  */
3734 __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
3735         __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
3736 {
3737         isl_ast_graft_list *list;
3738         isl_ast_node *node;
3739         isl_union_map *executed;
3740
3741         build = isl_ast_build_copy(build);
3742         build = isl_ast_build_set_single_valued(build, 0);
3743         executed = isl_union_map_reverse(schedule);
3744         list = generate_code(executed, isl_ast_build_copy(build), 0);
3745         node = isl_ast_node_from_graft_list(list, build);
3746         isl_ast_build_free(build);
3747
3748         return node;
3749 }