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