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