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