isl_union_set_compute_schedule: make preference for large bands configurable
[platform/upstream/isl.git] / isl_schedule.c
1 /*
2  * Copyright 2011      INRIA Saclay
3  *
4  * Use of this software is governed by the GNU LGPLv2.1 license
5  *
6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8  * 91893 Orsay, France
9  */
10
11 #include <isl_ctx_private.h>
12 #include <isl_map_private.h>
13 #include <isl_dim_private.h>
14 #include <isl/hash.h>
15 #include <isl/constraint.h>
16 #include <isl/schedule.h>
17 #include <isl_mat_private.h>
18 #include <isl/set.h>
19 #include <isl/seq.h>
20 #include <isl_tab.h>
21 #include <isl_dim_map.h>
22 #include <isl_hmap_map_basic_set.h>
23 #include <isl_qsort.h>
24 #include <isl_schedule_private.h>
25 #include <isl_band_private.h>
26 #include <isl_list_private.h>
27
28 /*
29  * The scheduling algorithm implemented in this file was inspired by
30  * Bondhugula et al., "Automatic Transformations for Communication-Minimized
31  * Parallelization and Locality Optimization in the Polyhedral Model".
32  */
33
34
35 /* Internal information about a node that is used during the construction
36  * of a schedule.
37  * dim represents the space in which the domain lives
38  * sched is a matrix representation of the schedule being constructed
39  *      for this node
40  * sched_map is an isl_map representation of the same (partial) schedule
41  *      sched_map may be NULL
42  * rank is the number of linearly independent rows in the linear part
43  *      of sched
44  * the columns of cmap represent a change of basis for the schedule
45  *      coefficients; the first rank columns span the linear part of
46  *      the schedule rows
47  * start is the first variable in the LP problem in the sequences that
48  *      represents the schedule coefficients of this node
49  * nvar is the dimension of the domain
50  * nparam is the number of parameters or 0 if we are not constructing
51  *      a parametric schedule
52  *
53  * scc is the index of SCC (or WCC) this node belongs to
54  *
55  * band contains the band index for each of the rows of the schedule.
56  * band_id is used to differentiate between separate bands at the same
57  * level within the same parent band, i.e., bands that are separated
58  * by the parent band or bands that are independent of each other.
59  * zero contains a boolean for each of the rows of the schedule,
60  * indicating whether the corresponding scheduling dimension results
61  * in zero dependence distances within its band and with respect
62  * to the proximity edges.
63  *
64  * index, min_index and on_stack are used during the SCC detection
65  * index represents the order in which nodes are visited.
66  * min_index is the index of the root of a (sub)component.
67  * on_stack indicates whether the node is currently on the stack.
68  */
69 struct isl_sched_node {
70         isl_dim *dim;
71         isl_mat *sched;
72         isl_map *sched_map;
73         int      rank;
74         isl_mat *cmap;
75         int      start;
76         int      nvar;
77         int      nparam;
78
79         int      scc;
80
81         int     *band;
82         int     *band_id;
83         int     *zero;
84
85         /* scc detection */
86         int      index;
87         int      min_index;
88         int      on_stack;
89 };
90
91 static int node_has_dim(const void *entry, const void *val)
92 {
93         struct isl_sched_node *node = (struct isl_sched_node *)entry;
94         isl_dim *dim = (isl_dim *)val;
95
96         return isl_dim_equal(node->dim, dim);
97 }
98
99 /* An edge in the dependence graph.  An edge may be used to
100  * ensure validity of the generated schedule, to minimize the dependence
101  * distance or both
102  *
103  * map is the dependence relation
104  * src is the source node
105  * dst is the sink node
106  * validity is set if the edge is used to ensure correctness
107  * proximity is set if the edge is used to minimize dependence distances
108  *
109  * For validity edges, start and end mark the sequence of inequality
110  * constraints in the LP problem that encode the validity constraint
111  * corresponding to this edge.
112  */
113 struct isl_sched_edge {
114         isl_map *map;
115
116         struct isl_sched_node *src;
117         struct isl_sched_node *dst;
118
119         int validity;
120         int proximity;
121
122         int start;
123         int end;
124 };
125
126 /* Internal information about the dependence graph used during
127  * the construction of the schedule.
128  *
129  * intra_hmap is a cache, mapping dependence relations to their dual,
130  *      for dependences from a node to itself
131  * inter_hmap is a cache, mapping dependence relations to their dual,
132  *      for dependences between distinct nodes
133  *
134  * n is the number of nodes
135  * node is the list of nodes
136  * maxvar is the maximal number of variables over all nodes
137  * n_row is the current (maximal) number of linearly independent
138  *      rows in the node schedules
139  * n_total_row is the current number of rows in the node schedules
140  * n_band is the current number of completed bands
141  * band_start is the starting row in the node schedules of the current band
142  * root is set if this graph is the original dependence graph,
143  *      without any splitting
144  *
145  * sorted contains a list of node indices sorted according to the
146  *      SCC to which a node belongs
147  *
148  * n_edge is the number of edges
149  * edge is the list of edges
150  * edge_table contains pointers into the edge array, hashed on the source
151  *      and sink spaces; the table only contains edges that represent
152  *      validity constraints (and that may or may not also represent proximity
153  *      constraints)
154  *
155  * node_table contains pointers into the node array, hashed on the space
156  *
157  * region contains a list of variable sequences that should be non-trivial
158  *
159  * lp contains the (I)LP problem used to obtain new schedule rows
160  *
161  * src_scc and dst_scc are the source and sink SCCs of an edge with
162  *      conflicting constraints
163  *
164  * scc, sp, index and stack are used during the detection of SCCs
165  * scc is the number of the next SCC
166  * stack contains the nodes on the path from the root to the current node
167  * sp is the stack pointer
168  * index is the index of the last node visited
169  */
170 struct isl_sched_graph {
171         isl_hmap_map_basic_set *intra_hmap;
172         isl_hmap_map_basic_set *inter_hmap;
173
174         struct isl_sched_node *node;
175         int n;
176         int maxvar;
177         int n_row;
178
179         int *sorted;
180
181         int n_band;
182         int n_total_row;
183         int band_start;
184
185         int root;
186
187         struct isl_sched_edge *edge;
188         int n_edge;
189         struct isl_hash_table *edge_table;
190
191         struct isl_hash_table *node_table;
192         struct isl_region *region;
193
194         isl_basic_set *lp;
195
196         int src_scc;
197         int dst_scc;
198
199         /* scc detection */
200         int scc;
201         int sp;
202         int index;
203         int *stack;
204 };
205
206 /* Initialize node_table based on the list of nodes.
207  */
208 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
209 {
210         int i;
211
212         graph->node_table = isl_hash_table_alloc(ctx, graph->n);
213         if (!graph->node_table)
214                 return -1;
215
216         for (i = 0; i < graph->n; ++i) {
217                 struct isl_hash_table_entry *entry;
218                 uint32_t hash;
219
220                 hash = isl_dim_get_hash(graph->node[i].dim);
221                 entry = isl_hash_table_find(ctx, graph->node_table, hash,
222                                             &node_has_dim,
223                                             graph->node[i].dim, 1);
224                 if (!entry)
225                         return -1;
226                 entry->data = &graph->node[i];
227         }
228
229         return 0;
230 }
231
232 /* Return a pointer to the node that lives within the given space,
233  * or NULL if there is no such node.
234  */
235 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
236         struct isl_sched_graph *graph, __isl_keep isl_dim *dim)
237 {
238         struct isl_hash_table_entry *entry;
239         uint32_t hash;
240
241         hash = isl_dim_get_hash(dim);
242         entry = isl_hash_table_find(ctx, graph->node_table, hash,
243                                     &node_has_dim, dim, 0);
244
245         return entry ? entry->data : NULL;
246 }
247
248 static int edge_has_src_and_dst(const void *entry, const void *val)
249 {
250         const struct isl_sched_edge *edge = entry;
251         const struct isl_sched_edge *temp = val;
252
253         return edge->src == temp->src && edge->dst == temp->dst;
254 }
255
256 /* Initialize edge_table based on the list of edges.
257  * Only edges with validity set are added to the table.
258  */
259 static int graph_init_edge_table(isl_ctx *ctx, struct isl_sched_graph *graph)
260 {
261         int i;
262
263         graph->edge_table = isl_hash_table_alloc(ctx, graph->n_edge);
264         if (!graph->edge_table)
265                 return -1;
266
267         for (i = 0; i < graph->n_edge; ++i) {
268                 struct isl_hash_table_entry *entry;
269                 uint32_t hash;
270
271                 if (!graph->edge[i].validity)
272                         continue;
273
274                 hash = isl_hash_init();
275                 hash = isl_hash_builtin(hash, graph->edge[i].src);
276                 hash = isl_hash_builtin(hash, graph->edge[i].dst);
277                 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
278                                             &edge_has_src_and_dst,
279                                             &graph->edge[i], 1);
280                 if (!entry)
281                         return -1;
282                 entry->data = &graph->edge[i];
283         }
284
285         return 0;
286 }
287
288 /* Check whether the dependence graph has a (validity) edge
289  * between the given two nodes.
290  */
291 static int graph_has_edge(struct isl_sched_graph *graph,
292         struct isl_sched_node *src, struct isl_sched_node *dst)
293 {
294         isl_ctx *ctx = isl_dim_get_ctx(src->dim);
295         struct isl_hash_table_entry *entry;
296         uint32_t hash;
297         struct isl_sched_edge temp = { .src = src, .dst = dst };
298         struct isl_sched_edge *edge;
299         int empty;
300
301         hash = isl_hash_init();
302         hash = isl_hash_builtin(hash, temp.src);
303         hash = isl_hash_builtin(hash, temp.dst);
304         entry = isl_hash_table_find(ctx, graph->edge_table, hash,
305                                     &edge_has_src_and_dst, &temp, 0);
306         if (!entry)
307                 return 0;
308
309         edge = entry->data;
310         empty = isl_map_plain_is_empty(edge->map);
311         if (empty < 0)
312                 return -1;
313
314         return !empty;
315 }
316
317 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
318         int n_node, int n_edge)
319 {
320         int i;
321
322         graph->n = n_node;
323         graph->n_edge = n_edge;
324         graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
325         graph->sorted = isl_calloc_array(ctx, int, graph->n);
326         graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
327         graph->stack = isl_alloc_array(ctx, int, graph->n);
328         graph->edge = isl_calloc_array(ctx,
329                                         struct isl_sched_edge, graph->n_edge);
330
331         graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
332         graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
333
334         if (!graph->node || !graph->region || !graph->stack || !graph->edge ||
335             !graph->sorted)
336                 return -1;
337
338         for(i = 0; i < graph->n; ++i)
339                 graph->sorted[i] = i;
340
341         return 0;
342 }
343
344 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
345 {
346         int i;
347
348         isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
349         isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
350
351         for (i = 0; i < graph->n; ++i) {
352                 isl_dim_free(graph->node[i].dim);
353                 isl_mat_free(graph->node[i].sched);
354                 isl_map_free(graph->node[i].sched_map);
355                 isl_mat_free(graph->node[i].cmap);
356                 if (graph->root) {
357                         free(graph->node[i].band);
358                         free(graph->node[i].band_id);
359                         free(graph->node[i].zero);
360                 }
361         }
362         free(graph->node);
363         free(graph->sorted);
364         for (i = 0; i < graph->n_edge; ++i)
365                 isl_map_free(graph->edge[i].map);
366         free(graph->edge);
367         free(graph->region);
368         free(graph->stack);
369         isl_hash_table_free(ctx, graph->edge_table);
370         isl_hash_table_free(ctx, graph->node_table);
371         isl_basic_set_free(graph->lp);
372 }
373
374 /* Add a new node to the graph representing the given set.
375  */
376 static int extract_node(__isl_take isl_set *set, void *user)
377 {
378         int nvar, nparam;
379         isl_ctx *ctx;
380         isl_dim *dim;
381         isl_mat *sched;
382         struct isl_sched_graph *graph = user;
383         int *band, *band_id, *zero;
384
385         ctx = isl_set_get_ctx(set);
386         dim = isl_set_get_dim(set);
387         isl_set_free(set);
388         nvar = isl_dim_size(dim, isl_dim_set);
389         nparam = isl_dim_size(dim, isl_dim_param);
390         if (!ctx->opt->schedule_parametric)
391                 nparam = 0;
392         sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
393         graph->node[graph->n].dim = dim;
394         graph->node[graph->n].nvar = nvar;
395         graph->node[graph->n].nparam = nparam;
396         graph->node[graph->n].sched = sched;
397         graph->node[graph->n].sched_map = NULL;
398         band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
399         graph->node[graph->n].band = band;
400         band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
401         graph->node[graph->n].band_id = band_id;
402         zero = isl_calloc_array(ctx, int, graph->n_edge + nvar);
403         graph->node[graph->n].zero = zero;
404         graph->n++;
405
406         if (!sched || !band || !band_id || !zero)
407                 return -1;
408
409         return 0;
410 }
411
412 /* Add a new edge to the graph based on the given map.
413  * Edges are first extracted from the validity dependences,
414  * from which the edge_table is constructed.
415  * Afterwards, the proximity dependences are added.  If a proximity
416  * dependence relation happens to be identical to one of the
417  * validity dependence relations added before, then we don't create
418  * a new edge, but instead mark the original edge as also representing
419  * a proximity dependence.
420  */
421 static int extract_edge(__isl_take isl_map *map, void *user)
422 {
423         isl_ctx *ctx = isl_map_get_ctx(map);
424         struct isl_sched_graph *graph = user;
425         struct isl_sched_node *src, *dst;
426         isl_dim *dim;
427
428         dim = isl_dim_domain(isl_map_get_dim(map));
429         src = graph_find_node(ctx, graph, dim);
430         isl_dim_free(dim);
431         dim = isl_dim_range(isl_map_get_dim(map));
432         dst = graph_find_node(ctx, graph, dim);
433         isl_dim_free(dim);
434
435         if (!src || !dst) {
436                 isl_map_free(map);
437                 return 0;
438         }
439
440         graph->edge[graph->n_edge].src = src;
441         graph->edge[graph->n_edge].dst = dst;
442         graph->edge[graph->n_edge].map = map;
443         graph->edge[graph->n_edge].validity = !graph->edge_table;
444         graph->edge[graph->n_edge].proximity = !!graph->edge_table;
445         graph->n_edge++;
446
447         if (graph->edge_table) {
448                 uint32_t hash;
449                 struct isl_hash_table_entry *entry;
450                 struct isl_sched_edge *edge;
451                 int is_equal;
452
453                 hash = isl_hash_init();
454                 hash = isl_hash_builtin(hash, src);
455                 hash = isl_hash_builtin(hash, dst);
456                 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
457                                             &edge_has_src_and_dst,
458                                             &graph->edge[graph->n_edge - 1], 0);
459                 if (!entry)
460                         return 0;
461                 edge = entry->data;
462                 is_equal = isl_map_plain_is_equal(map, edge->map);
463                 if (is_equal < 0)
464                         return -1;
465                 if (!is_equal)
466                         return 0;
467
468                 graph->n_edge--;
469                 edge->proximity = 1;
470                 isl_map_free(map);
471         }
472
473         return 0;
474 }
475
476 /* Check whether there is a validity dependence from src to dst,
477  * forcing dst to follow src.
478  */
479 static int node_follows(struct isl_sched_graph *graph, 
480         struct isl_sched_node *dst, struct isl_sched_node *src)
481 {
482         return graph_has_edge(graph, src, dst);
483 }
484
485 /* Perform Tarjan's algorithm for computing the strongly connected components
486  * in the dependence graph (only validity edges).
487  * If directed is not set, we consider the graph to be undirected and
488  * we effectively compute the (weakly) connected components.
489  */
490 static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed)
491 {
492         int j;
493
494         g->node[i].index = g->index;
495         g->node[i].min_index = g->index;
496         g->node[i].on_stack = 1;
497         g->index++;
498         g->stack[g->sp++] = i;
499
500         for (j = g->n - 1; j >= 0; --j) {
501                 int f;
502
503                 if (j == i)
504                         continue;
505                 if (g->node[j].index >= 0 &&
506                         (!g->node[j].on_stack ||
507                          g->node[j].index > g->node[i].min_index))
508                         continue;
509                 
510                 f = node_follows(g, &g->node[i], &g->node[j]);
511                 if (f < 0)
512                         return -1;
513                 if (!f && !directed) {
514                         f = node_follows(g, &g->node[j], &g->node[i]);
515                         if (f < 0)
516                                 return -1;
517                 }
518                 if (!f)
519                         continue;
520                 if (g->node[j].index < 0) {
521                         detect_sccs_tarjan(g, j, directed);
522                         if (g->node[j].min_index < g->node[i].min_index)
523                                 g->node[i].min_index = g->node[j].min_index;
524                 } else if (g->node[j].index < g->node[i].min_index)
525                         g->node[i].min_index = g->node[j].index;
526         }
527
528         if (g->node[i].index != g->node[i].min_index)
529                 return 0;
530
531         do {
532                 j = g->stack[--g->sp];
533                 g->node[j].on_stack = 0;
534                 g->node[j].scc = g->scc;
535         } while (j != i);
536         g->scc++;
537
538         return 0;
539 }
540
541 static int detect_ccs(struct isl_sched_graph *graph, int directed)
542 {
543         int i;
544
545         graph->index = 0;
546         graph->sp = 0;
547         graph->scc = 0;
548         for (i = graph->n - 1; i >= 0; --i)
549                 graph->node[i].index = -1;
550
551         for (i = graph->n - 1; i >= 0; --i) {
552                 if (graph->node[i].index >= 0)
553                         continue;
554                 if (detect_sccs_tarjan(graph, i, directed) < 0)
555                         return -1;
556         }
557
558         return 0;
559 }
560
561 /* Apply Tarjan's algorithm to detect the strongly connected components
562  * in the dependence graph.
563  */
564 static int detect_sccs(struct isl_sched_graph *graph)
565 {
566         return detect_ccs(graph, 1);
567 }
568
569 /* Apply Tarjan's algorithm to detect the (weakly) connected components
570  * in the dependence graph.
571  */
572 static int detect_wccs(struct isl_sched_graph *graph)
573 {
574         return detect_ccs(graph, 0);
575 }
576
577 static int cmp_scc(const void *a, const void *b, void *data)
578 {
579         struct isl_sched_graph *graph = data;
580         const int *i1 = a;
581         const int *i2 = b;
582
583         return graph->node[*i1].scc - graph->node[*i2].scc;
584 }
585
586 /* Sort the elements of graph->sorted according to the corresponding SCCs.
587  */
588 static void sort_sccs(struct isl_sched_graph *graph)
589 {
590         isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
591 }
592
593 /* Given a dependence relation R from a node to itself,
594  * construct the set of coefficients of valid constraints for elements
595  * in that dependence relation.
596  * In particular, the result contains tuples of coefficients
597  * c_0, c_n, c_x such that
598  *
599  *      c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
600  *
601  * or, equivalently,
602  *
603  *      c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
604  *
605  * We choose here to compute the dual of delta R.
606  * Alternatively, we could have computed the dual of R, resulting
607  * in a set of tuples c_0, c_n, c_x, c_y, and then
608  * plugged in (c_0, c_n, c_x, -c_x).
609  */
610 static __isl_give isl_basic_set *intra_coefficients(
611         struct isl_sched_graph *graph, __isl_take isl_map *map)
612 {
613         isl_ctx *ctx = isl_map_get_ctx(map);
614         isl_set *delta;
615         isl_basic_set *coef;
616
617         if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
618                 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
619
620         delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
621         coef = isl_set_coefficients(delta);
622         isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
623                                         isl_basic_set_copy(coef));
624
625         return coef;
626 }
627
628 /* Given a dependence relation R, * construct the set of coefficients
629  * of valid constraints for elements in that dependence relation.
630  * In particular, the result contains tuples of coefficients
631  * c_0, c_n, c_x, c_y such that
632  *
633  *      c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
634  *
635  */
636 static __isl_give isl_basic_set *inter_coefficients(
637         struct isl_sched_graph *graph, __isl_take isl_map *map)
638 {
639         isl_ctx *ctx = isl_map_get_ctx(map);
640         isl_set *set;
641         isl_basic_set *coef;
642
643         if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
644                 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
645
646         set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
647         coef = isl_set_coefficients(set);
648         isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
649                                         isl_basic_set_copy(coef));
650
651         return coef;
652 }
653
654 /* Add constraints to graph->lp that force validity for the given
655  * dependence from a node i to itself.
656  * That is, add constraints that enforce
657  *
658  *      (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
659  *      = c_i_x (y - x) >= 0
660  *
661  * for each (x,y) in R.
662  * We obtain general constraints on coefficients (c_0, c_n, c_x)
663  * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
664  * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
665  * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
666  *
667  * Actually, we do not construct constraints for the c_i_x themselves,
668  * but for the coefficients of c_i_x written as a linear combination
669  * of the columns in node->cmap.
670  */
671 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
672         struct isl_sched_edge *edge)
673 {
674         unsigned total;
675         isl_map *map = isl_map_copy(edge->map);
676         isl_ctx *ctx = isl_map_get_ctx(map);
677         isl_dim *dim;
678         isl_dim_map *dim_map;
679         isl_basic_set *coef;
680         struct isl_sched_node *node = edge->src;
681
682         coef = intra_coefficients(graph, map);
683
684         dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
685
686         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
687                     isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap));
688
689         total = isl_basic_set_total_dim(graph->lp);
690         dim_map = isl_dim_map_alloc(ctx, total);
691         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
692                           isl_dim_size(dim, isl_dim_set), 1,
693                           node->nvar, -1);
694         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
695                           isl_dim_size(dim, isl_dim_set), 1,
696                           node->nvar, 1);
697         graph->lp = isl_basic_set_extend_constraints(graph->lp,
698                         coef->n_eq, coef->n_ineq);
699         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
700                                                            coef, dim_map);
701         isl_dim_free(dim);
702
703         return 0;
704 }
705
706 /* Add constraints to graph->lp that force validity for the given
707  * dependence from node i to node j.
708  * That is, add constraints that enforce
709  *
710  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
711  *
712  * for each (x,y) in R.
713  * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
714  * of valid constraints for R and then plug in
715  * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
716  *  c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
717  * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
718  * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
719  *
720  * Actually, we do not construct constraints for the c_*_x themselves,
721  * but for the coefficients of c_*_x written as a linear combination
722  * of the columns in node->cmap.
723  */
724 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
725         struct isl_sched_edge *edge)
726 {
727         unsigned total;
728         isl_map *map = isl_map_copy(edge->map);
729         isl_ctx *ctx = isl_map_get_ctx(map);
730         isl_dim *dim;
731         isl_dim_map *dim_map;
732         isl_basic_set *coef;
733         struct isl_sched_node *src = edge->src;
734         struct isl_sched_node *dst = edge->dst;
735
736         coef = inter_coefficients(graph, map);
737
738         dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
739
740         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
741                     isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap));
742         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
743                     isl_dim_size(dim, isl_dim_set) + src->nvar,
744                     isl_mat_copy(dst->cmap));
745
746         total = isl_basic_set_total_dim(graph->lp);
747         dim_map = isl_dim_map_alloc(ctx, total);
748
749         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
750         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
751         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
752         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
753                           isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
754                           dst->nvar, -1);
755         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
756                           isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
757                           dst->nvar, 1);
758
759         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
760         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
761         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
762         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
763                           isl_dim_size(dim, isl_dim_set), 1,
764                           src->nvar, 1);
765         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
766                           isl_dim_size(dim, isl_dim_set), 1,
767                           src->nvar, -1);
768
769         edge->start = graph->lp->n_ineq;
770         graph->lp = isl_basic_set_extend_constraints(graph->lp,
771                         coef->n_eq, coef->n_ineq);
772         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
773                                                            coef, dim_map);
774         isl_dim_free(dim);
775         edge->end = graph->lp->n_ineq;
776
777         return 0;
778 }
779
780 /* Add constraints to graph->lp that bound the dependence distance for the given
781  * dependence from a node i to itself.
782  * If s = 1, we add the constraint
783  *
784  *      c_i_x (y - x) <= m_0 + m_n n
785  *
786  * or
787  *
788  *      -c_i_x (y - x) + m_0 + m_n n >= 0
789  *
790  * for each (x,y) in R.
791  * If s = -1, we add the constraint
792  *
793  *      -c_i_x (y - x) <= m_0 + m_n n
794  *
795  * or
796  *
797  *      c_i_x (y - x) + m_0 + m_n n >= 0
798  *
799  * for each (x,y) in R.
800  * We obtain general constraints on coefficients (c_0, c_n, c_x)
801  * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
802  * with each coefficient (except m_0) represented as a pair of non-negative
803  * coefficients.
804  *
805  * Actually, we do not construct constraints for the c_i_x themselves,
806  * but for the coefficients of c_i_x written as a linear combination
807  * of the columns in node->cmap.
808  */
809 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
810         struct isl_sched_edge *edge, int s)
811 {
812         unsigned total;
813         unsigned nparam;
814         isl_map *map = isl_map_copy(edge->map);
815         isl_ctx *ctx = isl_map_get_ctx(map);
816         isl_dim *dim;
817         isl_dim_map *dim_map;
818         isl_basic_set *coef;
819         struct isl_sched_node *node = edge->src;
820
821         coef = intra_coefficients(graph, map);
822
823         dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
824
825         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
826                     isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap));
827
828         nparam = isl_dim_size(node->dim, isl_dim_param);
829         total = isl_basic_set_total_dim(graph->lp);
830         dim_map = isl_dim_map_alloc(ctx, total);
831         isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
832         isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
833         isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
834         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
835                           isl_dim_size(dim, isl_dim_set), 1,
836                           node->nvar, s);
837         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
838                           isl_dim_size(dim, isl_dim_set), 1,
839                           node->nvar, -s);
840         graph->lp = isl_basic_set_extend_constraints(graph->lp,
841                         coef->n_eq, coef->n_ineq);
842         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
843                                                            coef, dim_map);
844         isl_dim_free(dim);
845
846         return 0;
847 }
848
849 /* Add constraints to graph->lp that bound the dependence distance for the given
850  * dependence from node i to node j.
851  * If s = 1, we add the constraint
852  *
853  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
854  *              <= m_0 + m_n n
855  *
856  * or
857  *
858  *      -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
859  *              m_0 + m_n n >= 0
860  *
861  * for each (x,y) in R.
862  * If s = -1, we add the constraint
863  *
864  *      -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
865  *              <= m_0 + m_n n
866  *
867  * or
868  *
869  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
870  *              m_0 + m_n n >= 0
871  *
872  * for each (x,y) in R.
873  * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
874  * of valid constraints for R and then plug in
875  * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
876  *  -s*c_j_x+s*c_i_x)
877  * with each coefficient (except m_0, c_j_0 and c_i_0)
878  * represented as a pair of non-negative coefficients.
879  *
880  * Actually, we do not construct constraints for the c_*_x themselves,
881  * but for the coefficients of c_*_x written as a linear combination
882  * of the columns in node->cmap.
883  */
884 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
885         struct isl_sched_edge *edge, int s)
886 {
887         unsigned total;
888         unsigned nparam;
889         isl_map *map = isl_map_copy(edge->map);
890         isl_ctx *ctx = isl_map_get_ctx(map);
891         isl_dim *dim;
892         isl_dim_map *dim_map;
893         isl_basic_set *coef;
894         struct isl_sched_node *src = edge->src;
895         struct isl_sched_node *dst = edge->dst;
896
897         coef = inter_coefficients(graph, map);
898
899         dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
900
901         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
902                     isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap));
903         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
904                     isl_dim_size(dim, isl_dim_set) + src->nvar,
905                     isl_mat_copy(dst->cmap));
906
907         nparam = isl_dim_size(src->dim, isl_dim_param);
908         total = isl_basic_set_total_dim(graph->lp);
909         dim_map = isl_dim_map_alloc(ctx, total);
910
911         isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
912         isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
913         isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
914
915         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
916         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
917         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
918         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
919                           isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
920                           dst->nvar, s);
921         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
922                           isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
923                           dst->nvar, -s);
924
925         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
926         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
927         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
928         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
929                           isl_dim_size(dim, isl_dim_set), 1,
930                           src->nvar, -s);
931         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
932                           isl_dim_size(dim, isl_dim_set), 1,
933                           src->nvar, s);
934
935         graph->lp = isl_basic_set_extend_constraints(graph->lp,
936                         coef->n_eq, coef->n_ineq);
937         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
938                                                            coef, dim_map);
939         isl_dim_free(dim);
940
941         return 0;
942 }
943
944 static int add_all_validity_constraints(struct isl_sched_graph *graph)
945 {
946         int i;
947
948         for (i = 0; i < graph->n_edge; ++i) {
949                 struct isl_sched_edge *edge= &graph->edge[i];
950                 if (!edge->validity)
951                         continue;
952                 if (edge->src != edge->dst)
953                         continue;
954                 if (add_intra_validity_constraints(graph, edge) < 0)
955                         return -1;
956         }
957
958         for (i = 0; i < graph->n_edge; ++i) {
959                 struct isl_sched_edge *edge = &graph->edge[i];
960                 if (!edge->validity)
961                         continue;
962                 if (edge->src == edge->dst)
963                         continue;
964                 if (add_inter_validity_constraints(graph, edge) < 0)
965                         return -1;
966         }
967
968         return 0;
969 }
970
971 /* Add constraints to graph->lp that bound the dependence distance
972  * for all dependence relations.
973  * If a given proximity dependence is identical to a validity
974  * dependence, then the dependence distance is already bounded
975  * from below (by zero), so we only need to bound the distance
976  * from above.
977  * Otherwise, we need to bound the distance both from above and from below.
978  */
979 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
980 {
981         int i;
982
983         for (i = 0; i < graph->n_edge; ++i) {
984                 struct isl_sched_edge *edge= &graph->edge[i];
985                 if (!edge->proximity)
986                         continue;
987                 if (edge->src == edge->dst &&
988                     add_intra_proximity_constraints(graph, edge, 1) < 0)
989                         return -1;
990                 if (edge->src != edge->dst &&
991                     add_inter_proximity_constraints(graph, edge, 1) < 0)
992                         return -1;
993                 if (edge->validity)
994                         continue;
995                 if (edge->src == edge->dst &&
996                     add_intra_proximity_constraints(graph, edge, -1) < 0)
997                         return -1;
998                 if (edge->src != edge->dst &&
999                     add_inter_proximity_constraints(graph, edge, -1) < 0)
1000                         return -1;
1001         }
1002
1003         return 0;
1004 }
1005
1006 /* Compute a basis for the rows in the linear part of the schedule
1007  * and extend this basis to a full basis.  The remaining rows
1008  * can then be used to force linear independence from the rows
1009  * in the schedule.
1010  *
1011  * In particular, given the schedule rows S, we compute
1012  *
1013  *      S = H Q
1014  *
1015  * with H the Hermite normal form of S.  That is, all but the
1016  * first rank columns of Q are zero and so each row in S is
1017  * a linear combination of the first rank rows of Q.
1018  * The matrix Q is then transposed because we will write the
1019  * coefficients of the next schedule row as a column vector s
1020  * and express this s as a linear combination s = Q c of the
1021  * computed basis.
1022  */
1023 static int node_update_cmap(struct isl_sched_node *node)
1024 {
1025         isl_mat *H, *Q;
1026         int n_row = isl_mat_rows(node->sched);
1027
1028         H = isl_mat_sub_alloc(node->sched, 0, n_row,
1029                               1 + node->nparam, node->nvar);
1030
1031         H = isl_mat_left_hermite(H, 0, NULL, &Q);
1032         isl_mat_free(node->cmap);
1033         node->cmap = isl_mat_transpose(Q);
1034         node->rank = isl_mat_initial_non_zero_cols(H);
1035         isl_mat_free(H);
1036
1037         if (!node->cmap || node->rank < 0)
1038                 return -1;
1039         return 0;
1040 }
1041
1042 /* Count the number of equality and inequality constraints
1043  * that will be added.  If once is set, then we count
1044  * each edge exactly once.  Otherwise, we count as follows
1045  * validity             -> 1 (>= 0)
1046  * validity+proximity   -> 2 (>= 0 and upper bound)
1047  * proximity            -> 2 (lower and upper bound)
1048  */
1049 static int count_constraints(struct isl_sched_graph *graph,
1050         int *n_eq, int *n_ineq, int once)
1051 {
1052         int i;
1053         isl_basic_set *coef;
1054
1055         *n_eq = *n_ineq = 0;
1056         for (i = 0; i < graph->n_edge; ++i) {
1057                 struct isl_sched_edge *edge= &graph->edge[i];
1058                 isl_map *map = isl_map_copy(edge->map);
1059                 int f = once ? 1 : edge->proximity ? 2 : 1;
1060
1061                 if (edge->src == edge->dst)
1062                         coef = intra_coefficients(graph, map);
1063                 else
1064                         coef = inter_coefficients(graph, map);
1065                 if (!coef)
1066                         return -1;
1067                 *n_eq += f * coef->n_eq;
1068                 *n_ineq += f * coef->n_ineq;
1069                 isl_basic_set_free(coef);
1070         }
1071
1072         return 0;
1073 }
1074
1075 /* Construct an ILP problem for finding schedule coefficients
1076  * that result in non-negative, but small dependence distances
1077  * over all dependences.
1078  * In particular, the dependence distances over proximity edges
1079  * are bounded by m_0 + m_n n and we compute schedule coefficients
1080  * with small values (preferably zero) of m_n and m_0.
1081  *
1082  * All variables of the ILP are non-negative.  The actual coefficients
1083  * may be negative, so each coefficient is represented as the difference
1084  * of two non-negative variables.  The negative part always appears
1085  * immediately before the positive part.
1086  * Other than that, the variables have the following order
1087  *
1088  *      - sum of positive and negative parts of m_n coefficients
1089  *      - m_0
1090  *      - sum of positive and negative parts of all c_n coefficients
1091  *              (unconstrained when computing non-parametric schedules)
1092  *      - sum of positive and negative parts of all c_x coefficients
1093  *      - positive and negative parts of m_n coefficients
1094  *      - for each node
1095  *              - c_i_0
1096  *              - positive and negative parts of c_i_n (if parametric)
1097  *              - positive and negative parts of c_i_x
1098  *
1099  * The c_i_x are not represented directly, but through the columns of
1100  * node->cmap.  That is, the computed values are for variable t_i_x
1101  * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1102  *
1103  * The constraints are those from the edges plus two or three equalities
1104  * to express the sums.
1105  *
1106  * If force_zero is set, then we add equalities to ensure that
1107  * the sum of the m_n coefficients and m_0 are both zero.
1108  */
1109 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
1110         int force_zero)
1111 {
1112         int i, j;
1113         int k;
1114         unsigned nparam;
1115         unsigned total;
1116         isl_dim *dim;
1117         int parametric;
1118         int param_pos;
1119         int n_eq, n_ineq;
1120
1121         parametric = ctx->opt->schedule_parametric;
1122         nparam = isl_dim_size(graph->node[0].dim, isl_dim_param);
1123         param_pos = 4;
1124         total = param_pos + 2 * nparam;
1125         for (i = 0; i < graph->n; ++i) {
1126                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1127                 if (node_update_cmap(node) < 0)
1128                         return -1;
1129                 node->start = total;
1130                 total += 1 + 2 * (node->nparam + node->nvar);
1131         }
1132
1133         if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0)
1134                 return -1;
1135
1136         dim = isl_dim_set_alloc(ctx, 0, total);
1137         isl_basic_set_free(graph->lp);
1138         n_eq += 2 + parametric + force_zero;
1139         graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq);
1140
1141         k = isl_basic_set_alloc_equality(graph->lp);
1142         if (k < 0)
1143                 return -1;
1144         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1145         if (!force_zero)
1146                 isl_int_set_si(graph->lp->eq[k][1], -1);
1147         for (i = 0; i < 2 * nparam; ++i)
1148                 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1149
1150         if (force_zero) {
1151                 k = isl_basic_set_alloc_equality(graph->lp);
1152                 if (k < 0)
1153                         return -1;
1154                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1155                 isl_int_set_si(graph->lp->eq[k][2], -1);
1156         }
1157
1158         if (parametric) {
1159                 k = isl_basic_set_alloc_equality(graph->lp);
1160                 if (k < 0)
1161                         return -1;
1162                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1163                 isl_int_set_si(graph->lp->eq[k][3], -1);
1164                 for (i = 0; i < graph->n; ++i) {
1165                         int pos = 1 + graph->node[i].start + 1;
1166
1167                         for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1168                                 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1169                 }
1170         }
1171
1172         k = isl_basic_set_alloc_equality(graph->lp);
1173         if (k < 0)
1174                 return -1;
1175         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1176         isl_int_set_si(graph->lp->eq[k][4], -1);
1177         for (i = 0; i < graph->n; ++i) {
1178                 struct isl_sched_node *node = &graph->node[i];
1179                 int pos = 1 + node->start + 1 + 2 * node->nparam;
1180
1181                 for (j = 0; j < 2 * node->nvar; ++j)
1182                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1183         }
1184
1185         if (add_all_validity_constraints(graph) < 0)
1186                 return -1;
1187         if (add_all_proximity_constraints(graph) < 0)
1188                 return -1;
1189
1190         return 0;
1191 }
1192
1193 /* Analyze the conflicting constraint found by
1194  * isl_tab_basic_set_non_trivial_lexmin.  If it corresponds to the validity
1195  * constraint of one of the edges between distinct nodes, living, moreover
1196  * in distinct SCCs, then record the source and sink SCC as this may
1197  * be a good place to cut between SCCs.
1198  */
1199 static int check_conflict(int con, void *user)
1200 {
1201         int i;
1202         struct isl_sched_graph *graph = user;
1203
1204         if (graph->src_scc >= 0)
1205                 return 0;
1206
1207         con -= graph->lp->n_eq;
1208
1209         if (con >= graph->lp->n_ineq)
1210                 return 0;
1211
1212         for (i = 0; i < graph->n_edge; ++i) {
1213                 if (!graph->edge[i].validity)
1214                         continue;
1215                 if (graph->edge[i].src == graph->edge[i].dst)
1216                         continue;
1217                 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1218                         continue;
1219                 if (graph->edge[i].start > con)
1220                         continue;
1221                 if (graph->edge[i].end <= con)
1222                         continue;
1223                 graph->src_scc = graph->edge[i].src->scc;
1224                 graph->dst_scc = graph->edge[i].dst->scc;
1225         }
1226
1227         return 0;
1228 }
1229
1230 /* Check whether the next schedule row of the given node needs to be
1231  * non-trivial.  Lower-dimensional domains may have some trivial rows,
1232  * but as soon as the number of remaining required non-trivial rows
1233  * is as large as the number or remaining rows to be computed,
1234  * all remaining rows need to be non-trivial.
1235  */
1236 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1237 {
1238         return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1239 }
1240
1241 /* Solve the ILP problem constructed in setup_lp.
1242  * For each node such that all the remaining rows of its schedule
1243  * need to be non-trivial, we construct a non-triviality region.
1244  * This region imposes that the next row is independent of previous rows.
1245  * In particular the coefficients c_i_x are represented by t_i_x
1246  * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1247  * its first columns span the rows of the previously computed part
1248  * of the schedule.  The non-triviality region enforces that at least
1249  * one of the remaining components of t_i_x is non-zero, i.e.,
1250  * that the new schedule row depends on at least one of the remaining
1251  * columns of Q.
1252  */
1253 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1254 {
1255         int i;
1256         isl_vec *sol;
1257         isl_basic_set *lp;
1258
1259         for (i = 0; i < graph->n; ++i) {
1260                 struct isl_sched_node *node = &graph->node[i];
1261                 int skip = node->rank;
1262                 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1263                 if (needs_row(graph, node))
1264                         graph->region[i].len = 2 * (node->nvar - skip);
1265                 else
1266                         graph->region[i].len = 0;
1267         }
1268         lp = isl_basic_set_copy(graph->lp);
1269         sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1270                                        graph->region, &check_conflict, graph);
1271         return sol;
1272 }
1273
1274 /* Update the schedules of all nodes based on the given solution
1275  * of the LP problem.
1276  * The new row is added to the current band.
1277  * All possibly negative coefficients are encoded as a difference
1278  * of two non-negative variables, so we need to perform the subtraction
1279  * here.  Moreover, if use_cmap is set, then the solution does
1280  * not refer to the actual coefficients c_i_x, but instead to variables
1281  * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1282  * In this case, we then also need to perform this multiplication
1283  * to obtain the values of c_i_x.
1284  *
1285  * If check_zero is set, then the first two coordinates of sol are
1286  * assumed to correspond to the dependence distance.  If these two
1287  * coordinates are zero, then the corresponding scheduling dimension
1288  * is marked as being zero distance.
1289  */
1290 static int update_schedule(struct isl_sched_graph *graph,
1291         __isl_take isl_vec *sol, int use_cmap, int check_zero)
1292 {
1293         int i, j;
1294         int zero = 0;
1295         isl_vec *csol = NULL;
1296
1297         if (!sol)
1298                 goto error;
1299         if (sol->size == 0)
1300                 isl_die(sol->ctx, isl_error_internal,
1301                         "no solution found", goto error);
1302
1303         if (check_zero)
1304                 zero = isl_int_is_zero(sol->el[1]) &&
1305                            isl_int_is_zero(sol->el[2]);
1306
1307         for (i = 0; i < graph->n; ++i) {
1308                 struct isl_sched_node *node = &graph->node[i];
1309                 int pos = node->start;
1310                 int row = isl_mat_rows(node->sched);
1311
1312                 isl_vec_free(csol);
1313                 csol = isl_vec_alloc(sol->ctx, node->nvar);
1314                 if (!csol)
1315                         goto error;
1316
1317                 isl_map_free(node->sched_map);
1318                 node->sched_map = NULL;
1319                 node->sched = isl_mat_add_rows(node->sched, 1);
1320                 if (!node->sched)
1321                         goto error;
1322                 node->sched = isl_mat_set_element(node->sched, row, 0,
1323                                                   sol->el[1 + pos]);
1324                 for (j = 0; j < node->nparam + node->nvar; ++j)
1325                         isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1326                                     sol->el[1 + pos + 1 + 2 * j + 1],
1327                                     sol->el[1 + pos + 1 + 2 * j]);
1328                 for (j = 0; j < node->nparam; ++j)
1329                         node->sched = isl_mat_set_element(node->sched,
1330                                         row, 1 + j, sol->el[1+pos+1+2*j+1]);
1331                 for (j = 0; j < node->nvar; ++j)
1332                         isl_int_set(csol->el[j],
1333                                     sol->el[1+pos+1+2*(node->nparam+j)+1]);
1334                 if (use_cmap)
1335                         csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1336                                                    csol);
1337                 if (!csol)
1338                         goto error;
1339                 for (j = 0; j < node->nvar; ++j)
1340                         node->sched = isl_mat_set_element(node->sched,
1341                                         row, 1 + node->nparam + j, csol->el[j]);
1342                 node->band[graph->n_total_row] = graph->n_band;
1343                 node->zero[graph->n_total_row] = zero;
1344         }
1345         isl_vec_free(sol);
1346         isl_vec_free(csol);
1347
1348         graph->n_row++;
1349         graph->n_total_row++;
1350
1351         return 0;
1352 error:
1353         isl_vec_free(sol);
1354         isl_vec_free(csol);
1355         return -1;
1356 }
1357
1358 /* Convert node->sched into a map and return this map.
1359  * We simply add equality constraints that express each output variable
1360  * as the affine combination of parameters and input variables specified
1361  * by the schedule matrix.
1362  *
1363  * The result is cached in node->sched_map, which needs to be released
1364  * whenever node->sched is updated.
1365  */
1366 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1367 {
1368         int i, j;
1369         isl_dim *dim;
1370         isl_basic_map *bmap;
1371         isl_constraint *c;
1372         int nrow, ncol;
1373         isl_int v;
1374
1375         if (node->sched_map)
1376                 return isl_map_copy(node->sched_map);
1377
1378         nrow = isl_mat_rows(node->sched);
1379         ncol = isl_mat_cols(node->sched) - 1;
1380         dim = isl_dim_from_domain(isl_dim_copy(node->dim));
1381         dim = isl_dim_add(dim, isl_dim_out, nrow);
1382         bmap = isl_basic_map_universe(isl_dim_copy(dim));
1383
1384         isl_int_init(v);
1385
1386         for (i = 0; i < nrow; ++i) {
1387                 c = isl_equality_alloc(isl_dim_copy(dim));
1388                 isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
1389                 isl_mat_get_element(node->sched, i, 0, &v);
1390                 isl_constraint_set_constant(c, v);
1391                 for (j = 0; j < node->nparam; ++j) {
1392                         isl_mat_get_element(node->sched, i, 1 + j, &v);
1393                         isl_constraint_set_coefficient(c, isl_dim_param, j, v);
1394                 }
1395                 for (j = 0; j < node->nvar; ++j) {
1396                         isl_mat_get_element(node->sched,
1397                                             i, 1 + node->nparam + j, &v);
1398                         isl_constraint_set_coefficient(c, isl_dim_in, j, v);
1399                 }
1400                 bmap = isl_basic_map_add_constraint(bmap, c);
1401         }
1402
1403         isl_int_clear(v);
1404
1405         isl_dim_free(dim);
1406
1407         node->sched_map = isl_map_from_basic_map(bmap);
1408         return isl_map_copy(node->sched_map);
1409 }
1410
1411 /* Update the given dependence relation based on the current schedule.
1412  * That is, intersect the dependence relation with a map expressing
1413  * that source and sink are executed within the same iteration of
1414  * the current schedule.
1415  * This is not the most efficient way, but this shouldn't be a critical
1416  * operation.
1417  */
1418 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1419         struct isl_sched_node *src, struct isl_sched_node *dst)
1420 {
1421         isl_map *src_sched, *dst_sched, *id;
1422
1423         src_sched = node_extract_schedule(src);
1424         dst_sched = node_extract_schedule(dst);
1425         id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1426         return isl_map_intersect(map, id);
1427 }
1428
1429 /* Update the dependence relations of all edges based on the current schedule.
1430  * If a dependence is carried completely by the current schedule, then
1431  * it is removed and edge_table is updated accordingly.
1432  */
1433 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1434 {
1435         int i;
1436         int reset_table = 0;
1437
1438         for (i = graph->n_edge - 1; i >= 0; --i) {
1439                 struct isl_sched_edge *edge = &graph->edge[i];
1440                 edge->map = specialize(edge->map, edge->src, edge->dst);
1441                 if (!edge->map)
1442                         return -1;
1443
1444                 if (isl_map_plain_is_empty(edge->map)) {
1445                         reset_table = 1;
1446                         isl_map_free(edge->map);
1447                         if (i != graph->n_edge - 1)
1448                                 graph->edge[i] = graph->edge[graph->n_edge - 1];
1449                         graph->n_edge--;
1450                 }
1451         }
1452
1453         if (reset_table) {
1454                 isl_hash_table_free(ctx, graph->edge_table);
1455                 graph->edge_table = NULL;
1456                 return graph_init_edge_table(ctx, graph);
1457         }
1458
1459         return 0;
1460 }
1461
1462 static void next_band(struct isl_sched_graph *graph)
1463 {
1464         graph->band_start = graph->n_total_row;
1465         graph->n_band++;
1466 }
1467
1468 /* Topologically sort statements mapped to same schedule iteration
1469  * and add a row to the schedule corresponding to this order.
1470  */
1471 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1472 {
1473         int i, j;
1474
1475         if (graph->n <= 1)
1476                 return 0;
1477
1478         if (update_edges(ctx, graph) < 0)
1479                 return -1;
1480
1481         if (graph->n_edge == 0)
1482                 return 0;
1483
1484         if (detect_sccs(graph) < 0)
1485                 return -1;
1486
1487         for (i = 0; i < graph->n; ++i) {
1488                 struct isl_sched_node *node = &graph->node[i];
1489                 int row = isl_mat_rows(node->sched);
1490                 int cols = isl_mat_cols(node->sched);
1491
1492                 isl_map_free(node->sched_map);
1493                 node->sched_map = NULL;
1494                 node->sched = isl_mat_add_rows(node->sched, 1);
1495                 if (!node->sched)
1496                         return -1;
1497                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1498                                                      node->scc);
1499                 for (j = 1; j < cols; ++j)
1500                         node->sched = isl_mat_set_element_si(node->sched,
1501                                                              row, j, 0);
1502                 node->band[graph->n_total_row] = graph->n_band;
1503         }
1504
1505         graph->n_total_row++;
1506         next_band(graph);
1507
1508         return 0;
1509 }
1510
1511 /* Construct an isl_schedule based on the computed schedule stored
1512  * in graph and with parameters specified by dim.
1513  */
1514 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1515         __isl_take isl_dim *dim)
1516 {
1517         int i;
1518         isl_ctx *ctx;
1519         isl_schedule *sched = NULL;
1520                 
1521         if (!dim)
1522                 return NULL;
1523
1524         ctx = isl_dim_get_ctx(dim);
1525         sched = isl_calloc(ctx, struct isl_schedule,
1526                            sizeof(struct isl_schedule) +
1527                            (graph->n - 1) * sizeof(struct isl_schedule_node));
1528         if (!sched)
1529                 goto error;
1530
1531         sched->ref = 1;
1532         sched->n = graph->n;
1533         sched->n_band = graph->n_band;
1534         sched->n_total_row = graph->n_total_row;
1535
1536         for (i = 0; i < sched->n; ++i) {
1537                 int r, b;
1538                 int *band_end, *band_id, *zero;
1539
1540                 band_end = isl_alloc_array(ctx, int, graph->n_band);
1541                 band_id = isl_alloc_array(ctx, int, graph->n_band);
1542                 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1543                 sched->node[i].sched = node_extract_schedule(&graph->node[i]);
1544                 sched->node[i].band_end = band_end;
1545                 sched->node[i].band_id = band_id;
1546                 sched->node[i].zero = zero;
1547                 if (!band_end || !band_id || !zero)
1548                         goto error;
1549
1550                 for (r = 0; r < graph->n_total_row; ++r)
1551                         zero[r] = graph->node[i].zero[r];
1552                 for (r = b = 0; r < graph->n_total_row; ++r) {
1553                         if (graph->node[i].band[r] == b)
1554                                 continue;
1555                         band_end[b++] = r;
1556                         if (graph->node[i].band[r] == -1)
1557                                 break;
1558                 }
1559                 if (r == graph->n_total_row)
1560                         band_end[b++] = r;
1561                 sched->node[i].n_band = b;
1562                 for (--b; b >= 0; --b)
1563                         band_id[b] = graph->node[i].band_id[b];
1564         }
1565
1566         sched->dim = dim;
1567
1568         return sched;
1569 error:
1570         isl_dim_free(dim);
1571         isl_schedule_free(sched);
1572         return NULL;
1573 }
1574
1575 /* Copy nodes that satisfy node_pred from the src dependence graph
1576  * to the dst dependence graph.
1577  */
1578 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1579         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1580 {
1581         int i;
1582
1583         dst->n = 0;
1584         for (i = 0; i < src->n; ++i) {
1585                 if (!node_pred(&src->node[i], data))
1586                         continue;
1587                 dst->node[dst->n].dim = isl_dim_copy(src->node[i].dim);
1588                 dst->node[dst->n].nvar = src->node[i].nvar;
1589                 dst->node[dst->n].nparam = src->node[i].nparam;
1590                 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1591                 dst->node[dst->n].sched_map =
1592                         isl_map_copy(src->node[i].sched_map);
1593                 dst->node[dst->n].band = src->node[i].band;
1594                 dst->node[dst->n].band_id = src->node[i].band_id;
1595                 dst->node[dst->n].zero = src->node[i].zero;
1596                 dst->n++;
1597         }
1598
1599         return 0;
1600 }
1601
1602 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1603  * to the dst dependence graph.
1604  */
1605 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1606         struct isl_sched_graph *src,
1607         int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1608 {
1609         int i;
1610
1611         dst->n_edge = 0;
1612         for (i = 0; i < src->n_edge; ++i) {
1613                 struct isl_sched_edge *edge = &src->edge[i];
1614                 isl_map *map;
1615
1616                 if (!edge_pred(edge, data))
1617                         continue;
1618
1619                 if (isl_map_plain_is_empty(edge->map))
1620                         continue;
1621
1622                 map = isl_map_copy(edge->map);
1623
1624                 dst->edge[dst->n_edge].src =
1625                         graph_find_node(ctx, dst, edge->src->dim);
1626                 dst->edge[dst->n_edge].dst =
1627                         graph_find_node(ctx, dst, edge->dst->dim);
1628                 dst->edge[dst->n_edge].map = map;
1629                 dst->edge[dst->n_edge].validity = edge->validity;
1630                 dst->edge[dst->n_edge].proximity = edge->proximity;
1631                 dst->n_edge++;
1632         }
1633
1634         return 0;
1635 }
1636
1637 /* Given a "src" dependence graph that contains the nodes from "dst"
1638  * that satisfy node_pred, copy the schedule computed in "src"
1639  * for those nodes back to "dst".
1640  */
1641 static int copy_schedule(struct isl_sched_graph *dst,
1642         struct isl_sched_graph *src,
1643         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1644 {
1645         int i;
1646
1647         src->n = 0;
1648         for (i = 0; i < dst->n; ++i) {
1649                 if (!node_pred(&dst->node[i], data))
1650                         continue;
1651                 isl_mat_free(dst->node[i].sched);
1652                 isl_map_free(dst->node[i].sched_map);
1653                 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1654                 dst->node[i].sched_map =
1655                         isl_map_copy(src->node[src->n].sched_map);
1656                 src->n++;
1657         }
1658
1659         dst->n_total_row = src->n_total_row;
1660         dst->n_band = src->n_band;
1661
1662         return 0;
1663 }
1664
1665 /* Compute the maximal number of variables over all nodes.
1666  * This is the maximal number of linearly independent schedule
1667  * rows that we need to compute.
1668  * Just in case we end up in a part of the dependence graph
1669  * with only lower-dimensional domains, we make sure we will
1670  * compute the required amount of extra linearly independent rows.
1671  */
1672 static int compute_maxvar(struct isl_sched_graph *graph)
1673 {
1674         int i;
1675
1676         graph->maxvar = 0;
1677         for (i = 0; i < graph->n; ++i) {
1678                 struct isl_sched_node *node = &graph->node[i];
1679                 int nvar;
1680
1681                 if (node_update_cmap(node) < 0)
1682                         return -1;
1683                 nvar = node->nvar + graph->n_row - node->rank;
1684                 if (nvar > graph->maxvar)
1685                         graph->maxvar = nvar;
1686         }
1687
1688         return 0;
1689 }
1690
1691 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1692 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1693
1694 /* Compute a schedule for a subgraph of "graph".  In particular, for
1695  * the graph composed of nodes that satisfy node_pred and edges that
1696  * that satisfy edge_pred.  The caller should precompute the number
1697  * of nodes and edges that satisfy these predicates and pass them along
1698  * as "n" and "n_edge".
1699  * If the subgraph is known to consist of a single component, then wcc should
1700  * be set and then we call compute_schedule_wcc on the constructed subgraph.
1701  * Otherwise, we call compute_schedule, which will check whether the subgraph
1702  * is connected.
1703  */
1704 static int compute_sub_schedule(isl_ctx *ctx,
1705         struct isl_sched_graph *graph, int n, int n_edge,
1706         int (*node_pred)(struct isl_sched_node *node, int data),
1707         int (*edge_pred)(struct isl_sched_edge *edge, int data),
1708         int data, int wcc)
1709 {
1710         struct isl_sched_graph split = { 0 };
1711
1712         if (graph_alloc(ctx, &split, n, n_edge) < 0)
1713                 goto error;
1714         if (copy_nodes(&split, graph, node_pred, data) < 0)
1715                 goto error;
1716         if (graph_init_table(ctx, &split) < 0)
1717                 goto error;
1718         if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1719                 goto error;
1720         if (graph_init_edge_table(ctx, &split) < 0)
1721                 goto error;
1722         split.n_row = graph->n_row;
1723         split.n_total_row = graph->n_total_row;
1724         split.n_band = graph->n_band;
1725         split.band_start = graph->band_start;
1726
1727         if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1728                 goto error;
1729         if (!wcc && compute_schedule(ctx, &split) < 0)
1730                 goto error;
1731
1732         copy_schedule(graph, &split, node_pred, data);
1733
1734         graph_free(ctx, &split);
1735         return 0;
1736 error:
1737         graph_free(ctx, &split);
1738         return -1;
1739 }
1740
1741 static int node_scc_exactly(struct isl_sched_node *node, int scc)
1742 {
1743         return node->scc == scc;
1744 }
1745
1746 static int node_scc_at_most(struct isl_sched_node *node, int scc)
1747 {
1748         return node->scc <= scc;
1749 }
1750
1751 static int node_scc_at_least(struct isl_sched_node *node, int scc)
1752 {
1753         return node->scc >= scc;
1754 }
1755
1756 static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc)
1757 {
1758         return edge->src->scc == scc;
1759 }
1760
1761 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
1762 {
1763         return edge->dst->scc <= scc;
1764 }
1765
1766 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
1767 {
1768         return edge->src->scc >= scc;
1769 }
1770
1771 /* Pad the schedules of all nodes with zero rows such that in the end
1772  * they all have graph->n_total_row rows.
1773  * The extra rows don't belong to any band, so they get assigned band number -1.
1774  */
1775 static int pad_schedule(struct isl_sched_graph *graph)
1776 {
1777         int i, j;
1778
1779         for (i = 0; i < graph->n; ++i) {
1780                 struct isl_sched_node *node = &graph->node[i];
1781                 int row = isl_mat_rows(node->sched);
1782                 if (graph->n_total_row > row) {
1783                         isl_map_free(node->sched_map);
1784                         node->sched_map = NULL;
1785                 }
1786                 node->sched = isl_mat_add_zero_rows(node->sched,
1787                                                     graph->n_total_row - row);
1788                 if (!node->sched)
1789                         return -1;
1790                 for (j = row; j < graph->n_total_row; ++j)
1791                         node->band[j] = -1;
1792         }
1793
1794         return 0;
1795 }
1796
1797 /* Split the current graph into two parts and compute a schedule for each
1798  * part individually.  In particular, one part consists of all SCCs up
1799  * to and including graph->src_scc, while the other part contains the other
1800  * SCCS.
1801  *
1802  * The split is enforced in the schedule by constant rows with two different
1803  * values (0 and 1).  These constant rows replace the previously computed rows
1804  * in the current band.
1805  * It would be possible to reuse them as the first rows in the next
1806  * band, but recomputing them may result in better rows as we are looking
1807  * at a smaller part of the dependence graph.
1808  *
1809  * The band_id of the second group is set to n, where n is the number
1810  * of nodes in the first group.  This ensures that the band_ids over
1811  * the two groups remain disjoint, even if either or both of the two
1812  * groups contain independent components.
1813  */
1814 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
1815 {
1816         int i, j, n, e1, e2;
1817         int n_total_row, orig_total_row;
1818         int n_band, orig_band;
1819         int drop;
1820
1821         drop = graph->n_total_row - graph->band_start;
1822         graph->n_total_row -= drop;
1823         graph->n_row -= drop;
1824
1825         n = 0;
1826         for (i = 0; i < graph->n; ++i) {
1827                 struct isl_sched_node *node = &graph->node[i];
1828                 int row = isl_mat_rows(node->sched) - drop;
1829                 int cols = isl_mat_cols(node->sched);
1830                 int before = node->scc <= graph->src_scc;
1831
1832                 if (before)
1833                         n++;
1834
1835                 isl_map_free(node->sched_map);
1836                 node->sched_map = NULL;
1837                 node->sched = isl_mat_drop_rows(node->sched,
1838                                                 graph->band_start, drop);
1839                 node->sched = isl_mat_add_rows(node->sched, 1);
1840                 if (!node->sched)
1841                         return -1;
1842                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1843                                                      !before);
1844                 for (j = 1; j < cols; ++j)
1845                         node->sched = isl_mat_set_element_si(node->sched,
1846                                                              row, j, 0);
1847                 node->band[graph->n_total_row] = graph->n_band;
1848         }
1849
1850         e1 = e2 = 0;
1851         for (i = 0; i < graph->n_edge; ++i) {
1852                 if (graph->edge[i].dst->scc <= graph->src_scc)
1853                         e1++;
1854                 if (graph->edge[i].src->scc > graph->src_scc)
1855                         e2++;
1856         }
1857
1858         graph->n_total_row++;
1859         next_band(graph);
1860
1861         for (i = 0; i < graph->n; ++i) {
1862                 struct isl_sched_node *node = &graph->node[i];
1863                 if (node->scc > graph->src_scc)
1864                         node->band_id[graph->n_band] = n;
1865         }
1866
1867         orig_total_row = graph->n_total_row;
1868         orig_band = graph->n_band;
1869         if (compute_sub_schedule(ctx, graph, n, e1,
1870                                 &node_scc_at_most, &edge_dst_scc_at_most,
1871                                 graph->src_scc, 0) < 0)
1872                 return -1;
1873         n_total_row = graph->n_total_row;
1874         graph->n_total_row = orig_total_row;
1875         n_band = graph->n_band;
1876         graph->n_band = orig_band;
1877         if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
1878                                 &node_scc_at_least, &edge_src_scc_at_least,
1879                                 graph->src_scc + 1, 0) < 0)
1880                 return -1;
1881         if (n_total_row > graph->n_total_row)
1882                 graph->n_total_row = n_total_row;
1883         if (n_band > graph->n_band)
1884                 graph->n_band = n_band;
1885
1886         return pad_schedule(graph);
1887 }
1888
1889 /* Compute the next band of the schedule after updating the dependence
1890  * relations based on the the current schedule.
1891  */
1892 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
1893 {
1894         if (update_edges(ctx, graph) < 0)
1895                 return -1;
1896         next_band(graph);
1897                 
1898         return compute_schedule(ctx, graph);
1899 }
1900
1901 /* Add constraints to graph->lp that force the dependence of edge i
1902  * to be respected and attempt to carry it, where edge i is one from
1903  * a node j to itself.
1904  * That is, add constraints that enforce
1905  *
1906  *      (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
1907  *      = c_j_x (y - x) >= e_i
1908  *
1909  * for each (x,y) in R.
1910  * We obtain general constraints on coefficients (c_0, c_n, c_x)
1911  * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
1912  * with each coefficient in c_j_x represented as a pair of non-negative
1913  * coefficients.
1914  */
1915 static int add_intra_constraints(struct isl_sched_graph *graph, int i)
1916 {
1917         unsigned total;
1918         struct isl_sched_edge *edge= &graph->edge[i];
1919         isl_map *map = isl_map_copy(edge->map);
1920         isl_ctx *ctx = isl_map_get_ctx(map);
1921         isl_dim *dim;
1922         isl_dim_map *dim_map;
1923         isl_basic_set *coef;
1924         struct isl_sched_node *node = edge->src;
1925
1926         coef = intra_coefficients(graph, map);
1927
1928         dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
1929
1930         total = isl_basic_set_total_dim(graph->lp);
1931         dim_map = isl_dim_map_alloc(ctx, total);
1932         isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1);
1933         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1934                           isl_dim_size(dim, isl_dim_set), 1,
1935                           node->nvar, -1);
1936         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1937                           isl_dim_size(dim, isl_dim_set), 1,
1938                           node->nvar, 1);
1939         graph->lp = isl_basic_set_extend_constraints(graph->lp,
1940                         coef->n_eq, coef->n_ineq);
1941         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1942                                                            coef, dim_map);
1943         isl_dim_free(dim);
1944
1945         return 0;
1946 }
1947
1948 /* Add constraints to graph->lp that force the dependence of edge i
1949  * to be respected and attempt to carry it, where edge i is one from
1950  * node j to node k.
1951  * That is, add constraints that enforce
1952  *
1953  *      (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
1954  *
1955  * for each (x,y) in R.
1956  * We obtain general constraints on coefficients (c_0, c_n, c_x)
1957  * of valid constraints for R and then plug in
1958  * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
1959  * with each coefficient (except e_i, c_k_0 and c_j_0)
1960  * represented as a pair of non-negative coefficients.
1961  */
1962 static int add_inter_constraints(struct isl_sched_graph *graph, int i)
1963 {
1964         unsigned total;
1965         struct isl_sched_edge *edge= &graph->edge[i];
1966         isl_map *map = isl_map_copy(edge->map);
1967         isl_ctx *ctx = isl_map_get_ctx(map);
1968         isl_dim *dim;
1969         isl_dim_map *dim_map;
1970         isl_basic_set *coef;
1971         struct isl_sched_node *src = edge->src;
1972         struct isl_sched_node *dst = edge->dst;
1973
1974         coef = inter_coefficients(graph, map);
1975
1976         dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
1977
1978         total = isl_basic_set_total_dim(graph->lp);
1979         dim_map = isl_dim_map_alloc(ctx, total);
1980
1981         isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1);
1982
1983         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
1984         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
1985         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
1986         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1987                           isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
1988                           dst->nvar, -1);
1989         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1990                           isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
1991                           dst->nvar, 1);
1992
1993         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
1994         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
1995         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
1996         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1997                           isl_dim_size(dim, isl_dim_set), 1,
1998                           src->nvar, 1);
1999         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
2000                           isl_dim_size(dim, isl_dim_set), 1,
2001                           src->nvar, -1);
2002
2003         graph->lp = isl_basic_set_extend_constraints(graph->lp,
2004                         coef->n_eq, coef->n_ineq);
2005         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2006                                                            coef, dim_map);
2007         isl_dim_free(dim);
2008
2009         return 0;
2010 }
2011
2012 /* Add constraints to graph->lp that force all dependence
2013  * to be respected and attempt to carry it.
2014  */
2015 static int add_all_constraints(struct isl_sched_graph *graph)
2016 {
2017         int i;
2018
2019         for (i = 0; i < graph->n_edge; ++i) {
2020                 struct isl_sched_edge *edge= &graph->edge[i];
2021                 if (edge->src == edge->dst &&
2022                     add_intra_constraints(graph, i) < 0)
2023                         return -1;
2024                 if (edge->src != edge->dst &&
2025                     add_inter_constraints(graph, i) < 0)
2026                         return -1;
2027         }
2028
2029         return 0;
2030 }
2031
2032 /* Construct an LP problem for finding schedule coefficients
2033  * such that the schedule carries as many dependences as possible.
2034  * In particular, for each dependence i, we bound the dependence distance
2035  * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2036  * of all e_i's.  Dependence with e_i = 0 in the solution are simply
2037  * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2038  *
2039  * All variables of the LP are non-negative.  The actual coefficients
2040  * may be negative, so each coefficient is represented as the difference
2041  * of two non-negative variables.  The negative part always appears
2042  * immediately before the positive part.
2043  * Other than that, the variables have the following order
2044  *
2045  *      - sum of (1 - e_i) over all edges
2046  *      - sum of positive and negative parts of all c_n coefficients
2047  *              (unconstrained when computing non-parametric schedules)
2048  *      - sum of positive and negative parts of all c_x coefficients
2049  *      - for each edge
2050  *              - e_i
2051  *      - for each node
2052  *              - c_i_0
2053  *              - positive and negative parts of c_i_n (if parametric)
2054  *              - positive and negative parts of c_i_x
2055  *
2056  * The constraints are those from the edges plus three equalities
2057  * to express the sums and n_edge inequalities to express e_i <= 1.
2058  */
2059 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2060 {
2061         int i, j;
2062         int k;
2063         isl_dim *dim;
2064         unsigned total;
2065         int n_eq, n_ineq;
2066
2067         total = 3 + graph->n_edge;
2068         for (i = 0; i < graph->n; ++i) {
2069                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2070                 node->start = total;
2071                 total += 1 + 2 * (node->nparam + node->nvar);
2072         }
2073
2074         if (count_constraints(graph, &n_eq, &n_ineq, 1) < 0)
2075                 return -1;
2076
2077         dim = isl_dim_set_alloc(ctx, 0, total);
2078         isl_basic_set_free(graph->lp);
2079         n_eq += 3;
2080         n_ineq += graph->n_edge;
2081         graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq);
2082         graph->lp = isl_basic_set_set_rational(graph->lp);
2083
2084         k = isl_basic_set_alloc_equality(graph->lp);
2085         if (k < 0)
2086                 return -1;
2087         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2088         isl_int_set_si(graph->lp->eq[k][0], -graph->n_edge);
2089         isl_int_set_si(graph->lp->eq[k][1], 1);
2090         for (i = 0; i < graph->n_edge; ++i)
2091                 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2092
2093         k = isl_basic_set_alloc_equality(graph->lp);
2094         if (k < 0)
2095                 return -1;
2096         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2097         isl_int_set_si(graph->lp->eq[k][2], -1);
2098         for (i = 0; i < graph->n; ++i) {
2099                 int pos = 1 + graph->node[i].start + 1;
2100
2101                 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2102                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2103         }
2104
2105         k = isl_basic_set_alloc_equality(graph->lp);
2106         if (k < 0)
2107                 return -1;
2108         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2109         isl_int_set_si(graph->lp->eq[k][3], -1);
2110         for (i = 0; i < graph->n; ++i) {
2111                 struct isl_sched_node *node = &graph->node[i];
2112                 int pos = 1 + node->start + 1 + 2 * node->nparam;
2113
2114                 for (j = 0; j < 2 * node->nvar; ++j)
2115                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2116         }
2117
2118         for (i = 0; i < graph->n_edge; ++i) {
2119                 k = isl_basic_set_alloc_inequality(graph->lp);
2120                 if (k < 0)
2121                         return -1;
2122                 isl_seq_clr(graph->lp->ineq[k], 1 +  total);
2123                 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2124                 isl_int_set_si(graph->lp->ineq[k][0], 1);
2125         }
2126
2127         if (add_all_constraints(graph) < 0)
2128                 return -1;
2129
2130         return 0;
2131 }
2132
2133 /* If the schedule_split_parallel option is set and if the linear
2134  * parts of the scheduling rows for all nodes in the graphs are the same,
2135  * then split off the constant term from the linear part.
2136  * The constant term is then placed in a separate band and
2137  * the linear part is simplified.
2138  */
2139 static int split_parallel(isl_ctx *ctx, struct isl_sched_graph *graph)
2140 {
2141         int i;
2142         int equal = 1;
2143         int row, cols;
2144         struct isl_sched_node *node0;
2145
2146         if (!ctx->opt->schedule_split_parallel)
2147                 return 0;
2148         if (graph->n <= 1)
2149                 return 0;
2150
2151         node0 = &graph->node[0];
2152         row = isl_mat_rows(node0->sched) - 1;
2153         cols = isl_mat_cols(node0->sched);
2154         for (i = 1; i < graph->n; ++i) {
2155                 struct isl_sched_node *node = &graph->node[i];
2156
2157                 if (!isl_seq_eq(node0->sched->row[row] + 1,
2158                                 node->sched->row[row] + 1, cols - 1))
2159                         return 0;
2160                 if (equal &&
2161                     isl_int_ne(node0->sched->row[row][0],
2162                                node->sched->row[row][0]))
2163                         equal = 0;
2164         }
2165         if (equal)
2166                 return 0;
2167
2168         next_band(graph);
2169
2170         for (i = 0; i < graph->n; ++i) {
2171                 struct isl_sched_node *node = &graph->node[i];
2172
2173                 isl_map_free(node->sched_map);
2174                 node->sched_map = NULL;
2175                 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2176                 if (!node->sched)
2177                         return -1;
2178                 isl_int_set(node->sched->row[row + 1][0],
2179                             node->sched->row[row][0]);
2180                 isl_int_set_si(node->sched->row[row][0], 0);
2181                 node->sched = isl_mat_normalize_row(node->sched, row);
2182                 if (!node->sched)
2183                         return -1;
2184                 node->band[graph->n_total_row] = graph->n_band;
2185         }
2186
2187         graph->n_total_row++;
2188
2189         return 0;
2190 }
2191
2192 /* Construct a schedule row for each node such that as many dependences
2193  * as possible are carried and then continue with the next band.
2194  */
2195 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2196 {
2197         isl_vec *sol;
2198         isl_basic_set *lp;
2199
2200         if (setup_carry_lp(ctx, graph) < 0)
2201                 return -1;
2202
2203         lp = isl_basic_set_copy(graph->lp);
2204         sol = isl_tab_basic_set_non_neg_lexmin(lp);
2205         if (!sol)
2206                 return -1;
2207
2208         if (sol->size == 0) {
2209                 isl_vec_free(sol);
2210                 isl_die(ctx, isl_error_internal,
2211                         "error in schedule construction", return -1);
2212         }
2213
2214         if (isl_int_cmp_si(sol->el[1], graph->n_edge) >= 0) {
2215                 isl_vec_free(sol);
2216                 isl_die(ctx, isl_error_unknown,
2217                         "unable to carry dependences", return -1);
2218         }
2219
2220         if (update_schedule(graph, sol, 0, 0) < 0)
2221                 return -1;
2222
2223         if (split_parallel(ctx, graph) < 0)
2224                 return -1;
2225
2226         return compute_next_band(ctx, graph);
2227 }
2228
2229 /* Compute a schedule for a connected dependence graph.
2230  * We try to find a sequence of as many schedule rows as possible that result
2231  * in non-negative dependence distances (independent of the previous rows
2232  * in the sequence, i.e., such that the sequence is tilable).
2233  * If we can't find any more rows we either
2234  * - split between SCCs and start over (assuming we found an interesting
2235  *      pair of SCCs between which to split)
2236  * - continue with the next band (assuming the current band has at least
2237  *      one row)
2238  * - try to carry as many dependences as possible and continue with the next
2239  *      band
2240  *
2241  * If we manage to complete the schedule, we finish off by topologically
2242  * sorting the statements based on the remaining dependences.
2243  *
2244  * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2245  * outermost dimension in the current band to be zero distance.  If this
2246  * turns out to be impossible, we fall back on the general scheme above
2247  * and try to carry as many dependences as possible.
2248  */
2249 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2250 {
2251         int force_zero = 0;
2252
2253         if (detect_sccs(graph) < 0)
2254                 return -1;
2255         sort_sccs(graph);
2256
2257         if (compute_maxvar(graph) < 0)
2258                 return -1;
2259
2260         if (ctx->opt->schedule_outer_zero_distance)
2261                 force_zero = 1;
2262
2263         while (graph->n_row < graph->maxvar) {
2264                 isl_vec *sol;
2265
2266                 graph->src_scc = -1;
2267                 graph->dst_scc = -1;
2268
2269                 if (setup_lp(ctx, graph, force_zero) < 0)
2270                         return -1;
2271                 sol = solve_lp(graph);
2272                 if (!sol)
2273                         return -1;
2274                 if (sol->size == 0) {
2275                         isl_vec_free(sol);
2276                         if (!ctx->opt->schedule_maximize_band_depth &&
2277                             graph->n_total_row > graph->band_start)
2278                                 return compute_next_band(ctx, graph);
2279                         if (graph->src_scc >= 0)
2280                                 return compute_split_schedule(ctx, graph);
2281                         if (graph->n_total_row > graph->band_start)
2282                                 return compute_next_band(ctx, graph);
2283                         return carry_dependences(ctx, graph);
2284                 }
2285                 if (update_schedule(graph, sol, 1, 1) < 0)
2286                         return -1;
2287                 force_zero = 0;
2288         }
2289
2290         if (graph->n_total_row > graph->band_start)
2291                 next_band(graph);
2292         return sort_statements(ctx, graph);
2293 }
2294
2295 /* Compute a schedule for each component (identified by node->scc)
2296  * of the dependence graph separately and then combine the results.
2297  *
2298  * The band_id is adjusted such that each component has a separate id.
2299  * Note that the band_id may have already been set to a value different
2300  * from zero by compute_split_schedule.
2301  */
2302 static int compute_component_schedule(isl_ctx *ctx,
2303         struct isl_sched_graph *graph)
2304 {
2305         int wcc, i;
2306         int n, n_edge;
2307         int n_total_row, orig_total_row;
2308         int n_band, orig_band;
2309
2310         n_total_row = 0;
2311         orig_total_row = graph->n_total_row;
2312         n_band = 0;
2313         orig_band = graph->n_band;
2314         for (i = 0; i < graph->n; ++i)
2315                 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2316         for (wcc = 0; wcc < graph->scc; ++wcc) {
2317                 n = 0;
2318                 for (i = 0; i < graph->n; ++i)
2319                         if (graph->node[i].scc == wcc)
2320                                 n++;
2321                 n_edge = 0;
2322                 for (i = 0; i < graph->n_edge; ++i)
2323                         if (graph->edge[i].src->scc == wcc)
2324                                 n_edge++;
2325
2326                 if (compute_sub_schedule(ctx, graph, n, n_edge,
2327                                     &node_scc_exactly,
2328                                     &edge_src_scc_exactly, wcc, 1) < 0)
2329                         return -1;
2330                 if (graph->n_total_row > n_total_row)
2331                         n_total_row = graph->n_total_row;
2332                 graph->n_total_row = orig_total_row;
2333                 if (graph->n_band > n_band)
2334                         n_band = graph->n_band;
2335                 graph->n_band = orig_band;
2336         }
2337
2338         graph->n_total_row = n_total_row;
2339         graph->n_band = n_band;
2340
2341         return pad_schedule(graph);
2342 }
2343
2344 /* Compute a schedule for the given dependence graph.
2345  * We first check if the graph is connected (through validity dependences)
2346  * and if so compute a schedule for each component separately.
2347  */
2348 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2349 {
2350         if (detect_wccs(graph) < 0)
2351                 return -1;
2352
2353         if (graph->scc > 1)
2354                 return compute_component_schedule(ctx, graph);
2355
2356         return compute_schedule_wcc(ctx, graph);
2357 }
2358
2359 /* Compute a schedule for the given union of domains that respects
2360  * all the validity dependences and tries to minimize the dependence
2361  * distances over the proximity dependences.
2362  */
2363 __isl_give isl_schedule *isl_union_set_compute_schedule(
2364         __isl_take isl_union_set *domain,
2365         __isl_take isl_union_map *validity,
2366         __isl_take isl_union_map *proximity)
2367 {
2368         isl_ctx *ctx = isl_union_set_get_ctx(domain);
2369         isl_dim *dim;
2370         struct isl_sched_graph graph = { 0 };
2371         isl_schedule *sched;
2372
2373         domain = isl_union_set_align_params(domain,
2374                                             isl_union_map_get_dim(validity));
2375         domain = isl_union_set_align_params(domain,
2376                                             isl_union_map_get_dim(proximity));
2377         dim = isl_union_set_get_dim(domain);
2378         validity = isl_union_map_align_params(validity, isl_dim_copy(dim));
2379         proximity = isl_union_map_align_params(proximity, dim);
2380
2381         if (!domain)
2382                 goto error;
2383
2384         graph.n = isl_union_set_n_set(domain);
2385         if (graph.n == 0)
2386                 goto empty;
2387         if (graph_alloc(ctx, &graph, graph.n,
2388             isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2389                 goto error;
2390         graph.root = 1;
2391         graph.n = 0;
2392         if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2393                 goto error;
2394         if (graph_init_table(ctx, &graph) < 0)
2395                 goto error;
2396         graph.n_edge = 0;
2397         if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0)
2398                 goto error;
2399         if (graph_init_edge_table(ctx, &graph) < 0)
2400                 goto error;
2401         if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0)
2402                 goto error;
2403
2404         if (compute_schedule(ctx, &graph) < 0)
2405                 goto error;
2406
2407 empty:
2408         sched = extract_schedule(&graph, isl_union_set_get_dim(domain));
2409
2410         graph_free(ctx, &graph);
2411         isl_union_set_free(domain);
2412         isl_union_map_free(validity);
2413         isl_union_map_free(proximity);
2414
2415         return sched;
2416 error:
2417         graph_free(ctx, &graph);
2418         isl_union_set_free(domain);
2419         isl_union_map_free(validity);
2420         isl_union_map_free(proximity);
2421         return NULL;
2422 }
2423
2424 void *isl_schedule_free(__isl_take isl_schedule *sched)
2425 {
2426         int i;
2427         if (!sched)
2428                 return NULL;
2429
2430         if (--sched->ref > 0)
2431                 return NULL;
2432
2433         for (i = 0; i < sched->n; ++i) {
2434                 isl_map_free(sched->node[i].sched);
2435                 free(sched->node[i].band_end);
2436                 free(sched->node[i].band_id);
2437                 free(sched->node[i].zero);
2438         }
2439         isl_dim_free(sched->dim);
2440         isl_band_list_free(sched->band_forest);
2441         free(sched);
2442         return NULL;
2443 }
2444
2445 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2446 {
2447         return schedule ? isl_dim_get_ctx(schedule->dim) : NULL;
2448 }
2449
2450 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2451 {
2452         int i;
2453         isl_union_map *umap;
2454
2455         if (!sched)
2456                 return NULL;
2457
2458         umap = isl_union_map_empty(isl_dim_copy(sched->dim));
2459         for (i = 0; i < sched->n; ++i)
2460                 umap = isl_union_map_add_map(umap,
2461                                             isl_map_copy(sched->node[i].sched));
2462
2463         return umap;
2464 }
2465
2466 static __isl_give isl_band_list *construct_band_list(
2467         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2468         int band_nr, int *parent_active, int n_active);
2469
2470 /* Construct an isl_band structure for the band in the given schedule
2471  * with sequence number band_nr for the n_active nodes marked by active.
2472  * If the nodes don't have a band with the given sequence number,
2473  * then a band without members is created.
2474  *
2475  * Because of the way the schedule is constructed, we know that
2476  * the position of the band inside the schedule of a node is the same
2477  * for all active nodes.
2478  */
2479 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2480         __isl_keep isl_band *parent,
2481         int band_nr, int *active, int n_active)
2482 {
2483         int i, j;
2484         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2485         isl_band *band;
2486         unsigned start, end;
2487
2488         band = isl_calloc_type(ctx, isl_band);
2489         if (!band)
2490                 return NULL;
2491
2492         band->ref = 1;
2493         band->schedule = schedule;
2494         band->parent = parent;
2495
2496         for (i = 0; i < schedule->n; ++i)
2497                 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2498                         break;
2499
2500         if (i < schedule->n) {
2501                 band->children = construct_band_list(schedule, band,
2502                                                 band_nr + 1, active, n_active);
2503                 if (!band->children)
2504                         goto error;
2505         }
2506
2507         for (i = 0; i < schedule->n; ++i)
2508                 if (active[i])
2509                         break;
2510
2511         if (i >= schedule->n)
2512                 isl_die(ctx, isl_error_internal,
2513                         "band without active statements", goto error);
2514
2515         start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2516         end = band_nr < schedule->node[i].n_band ?
2517                 schedule->node[i].band_end[band_nr] : start;
2518         band->n = end - start;
2519
2520         band->zero = isl_alloc_array(ctx, int, band->n);
2521         if (!band->zero)
2522                 goto error;
2523
2524         for (j = 0; j < band->n; ++j)
2525                 band->zero[j] = schedule->node[i].zero[start + j];
2526
2527         band->map = isl_union_map_empty(isl_dim_copy(schedule->dim));
2528         for (i = 0; i < schedule->n; ++i) {
2529                 isl_map *map;
2530                 unsigned n_out;
2531
2532                 if (!active[i])
2533                         continue;
2534
2535                 map = isl_map_copy(schedule->node[i].sched);
2536                 n_out = isl_map_dim(map, isl_dim_out);
2537                 map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
2538                 map = isl_map_project_out(map, isl_dim_out, 0, start);
2539                 band->map = isl_union_map_union(band->map,
2540                                                 isl_union_map_from_map(map));
2541         }
2542         if (!band->map)
2543                 goto error;
2544
2545         return band;
2546 error:
2547         isl_band_free(band);
2548         return NULL;
2549 }
2550
2551 /* Construct a list of bands that start at the same position (with
2552  * sequence number band_nr) in the schedules of the nodes that
2553  * were active in the parent band.
2554  *
2555  * A separate isl_band structure is created for each band_id
2556  * and for each node that does not have a band with sequence
2557  * number band_nr.  In the latter case, a band without members
2558  * is created.
2559  * This ensures that if a band has any children, then each node
2560  * that was active in the band is active in exactly one of the children.
2561  */
2562 static __isl_give isl_band_list *construct_band_list(
2563         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2564         int band_nr, int *parent_active, int n_active)
2565 {
2566         int i, j;
2567         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2568         int *active;
2569         int n_band;
2570         isl_band_list *list;
2571
2572         n_band = 0;
2573         for (i = 0; i < n_active; ++i) {
2574                 for (j = 0; j < schedule->n; ++j) {
2575                         if (!parent_active[j])
2576                                 continue;
2577                         if (schedule->node[j].n_band <= band_nr)
2578                                 continue;
2579                         if (schedule->node[j].band_id[band_nr] == i) {
2580                                 n_band++;
2581                                 break;
2582                         }
2583                 }
2584         }
2585         for (j = 0; j < schedule->n; ++j)
2586                 if (schedule->node[j].n_band <= band_nr)
2587                         n_band++;
2588
2589         if (n_band == 1) {
2590                 isl_band *band;
2591                 list = isl_band_list_alloc(ctx, n_band);
2592                 band = construct_band(schedule, parent, band_nr,
2593                                         parent_active, n_active);
2594                 return isl_band_list_add(list, band);
2595         }
2596
2597         active = isl_alloc_array(ctx, int, schedule->n);
2598         if (!active)
2599                 return NULL;
2600
2601         list = isl_band_list_alloc(ctx, n_band);
2602
2603         for (i = 0; i < n_active; ++i) {
2604                 int n = 0;
2605                 isl_band *band;
2606
2607                 for (j = 0; j < schedule->n; ++j) {
2608                         active[j] = parent_active[j] &&
2609                                         schedule->node[j].n_band > band_nr &&
2610                                         schedule->node[j].band_id[band_nr] == i;
2611                         if (active[j])
2612                                 n++;
2613                 }
2614                 if (n == 0)
2615                         continue;
2616
2617                 band = construct_band(schedule, parent, band_nr, active, n);
2618
2619                 list = isl_band_list_add(list, band);
2620         }
2621         for (i = 0; i < schedule->n; ++i) {
2622                 isl_band *band;
2623                 if (!parent_active[i])
2624                         continue;
2625                 if (schedule->node[i].n_band > band_nr)
2626                         continue;
2627                 for (j = 0; j < schedule->n; ++j)
2628                         active[j] = j == i;
2629                 band = construct_band(schedule, parent, band_nr, active, 1);
2630                 list = isl_band_list_add(list, band);
2631         }
2632
2633         free(active);
2634
2635         return list;
2636 }
2637
2638 /* Construct a band forest representation of the schedule and
2639  * return the list of roots.
2640  */
2641 static __isl_give isl_band_list *construct_forest(
2642         __isl_keep isl_schedule *schedule)
2643 {
2644         int i;
2645         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2646         isl_band_list *forest;
2647         int *active;
2648
2649         active = isl_alloc_array(ctx, int, schedule->n);
2650         if (!active)
2651                 return NULL;
2652
2653         for (i = 0; i < schedule->n; ++i)
2654                 active[i] = 1;
2655
2656         forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
2657
2658         free(active);
2659
2660         return forest;
2661 }
2662
2663 /* Return the roots of a band forest representation of the schedule.
2664  */
2665 __isl_give isl_band_list *isl_schedule_get_band_forest(
2666         __isl_keep isl_schedule *schedule)
2667 {
2668         if (!schedule)
2669                 return NULL;
2670         if (!schedule->band_forest)
2671                 schedule->band_forest = construct_forest(schedule);
2672         return isl_band_list_dup(schedule->band_forest);
2673 }
2674
2675 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2676         __isl_keep isl_band_list *list);
2677
2678 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
2679         __isl_keep isl_band *band)
2680 {
2681         isl_band_list *children;
2682
2683         p = isl_printer_start_line(p);
2684         p = isl_printer_print_union_map(p, band->map);
2685         p = isl_printer_end_line(p);
2686
2687         if (!isl_band_has_children(band))
2688                 return p;
2689
2690         children = isl_band_get_children(band);
2691
2692         p = isl_printer_indent(p, 4);
2693         p = print_band_list(p, children);
2694         p = isl_printer_indent(p, -4);
2695
2696         isl_band_list_free(children);
2697
2698         return p;
2699 }
2700
2701 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2702         __isl_keep isl_band_list *list)
2703 {
2704         int i, n;
2705
2706         n = isl_band_list_n_band(list);
2707         for (i = 0; i < n; ++i) {
2708                 isl_band *band;
2709                 band = isl_band_list_get_band(list, i);
2710                 p = print_band(p, band);
2711                 isl_band_free(band);
2712         }
2713
2714         return p;
2715 }
2716
2717 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
2718         __isl_keep isl_schedule *schedule)
2719 {
2720         isl_band_list *forest;
2721
2722         forest = isl_schedule_get_band_forest(schedule);
2723
2724         p = print_band_list(p, forest);
2725
2726         isl_band_list_free(forest);
2727
2728         return p;
2729 }
2730
2731 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
2732 {
2733         isl_printer *printer;
2734
2735         if (!schedule)
2736                 return;
2737
2738         printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
2739         printer = isl_printer_print_schedule(printer, schedule);
2740
2741         isl_printer_free(printer);
2742 }