isl_union_set_compute_schedule: fix check for progress in feautrier scheduler
[platform/upstream/isl.git] / isl_schedule.c
1 /*
2  * Copyright 2011      INRIA Saclay
3  *
4  * Use of this software is governed by the MIT 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_space_private.h>
14 #include <isl/aff.h>
15 #include <isl/hash.h>
16 #include <isl/constraint.h>
17 #include <isl/schedule.h>
18 #include <isl_mat_private.h>
19 #include <isl/set.h>
20 #include <isl/seq.h>
21 #include <isl_tab.h>
22 #include <isl_dim_map.h>
23 #include <isl_hmap_map_basic_set.h>
24 #include <isl_sort.h>
25 #include <isl_schedule_private.h>
26 #include <isl_band_private.h>
27 #include <isl_list_private.h>
28 #include <isl_options_private.h>
29 #include <isl_tarjan.h>
30
31 /*
32  * The scheduling algorithm implemented in this file was inspired by
33  * Bondhugula et al., "Automatic Transformations for Communication-Minimized
34  * Parallelization and Locality Optimization in the Polyhedral Model".
35  */
36
37
38 /* Internal information about a node that is used during the construction
39  * of a schedule.
40  * dim represents the space in which the domain lives
41  * sched is a matrix representation of the schedule being constructed
42  *      for this node
43  * sched_map is an isl_map representation of the same (partial) schedule
44  *      sched_map may be NULL
45  * rank is the number of linearly independent rows in the linear part
46  *      of sched
47  * the columns of cmap represent a change of basis for the schedule
48  *      coefficients; the first rank columns span the linear part of
49  *      the schedule rows
50  * start is the first variable in the LP problem in the sequences that
51  *      represents the schedule coefficients of this node
52  * nvar is the dimension of the domain
53  * nparam is the number of parameters or 0 if we are not constructing
54  *      a parametric schedule
55  *
56  * scc is the index of SCC (or WCC) this node belongs to
57  *
58  * band contains the band index for each of the rows of the schedule.
59  * band_id is used to differentiate between separate bands at the same
60  * level within the same parent band, i.e., bands that are separated
61  * by the parent band or bands that are independent of each other.
62  * zero contains a boolean for each of the rows of the schedule,
63  * indicating whether the corresponding scheduling dimension results
64  * in zero dependence distances within its band and with respect
65  * to the proximity edges.
66  */
67 struct isl_sched_node {
68         isl_space *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     *zero;
82 };
83
84 static int node_has_dim(const void *entry, const void *val)
85 {
86         struct isl_sched_node *node = (struct isl_sched_node *)entry;
87         isl_space *dim = (isl_space *)val;
88
89         return isl_space_is_equal(node->dim, dim);
90 }
91
92 /* An edge in the dependence graph.  An edge may be used to
93  * ensure validity of the generated schedule, to minimize the dependence
94  * distance or both
95  *
96  * map is the dependence relation
97  * src is the source node
98  * dst is the sink node
99  * validity is set if the edge is used to ensure correctness
100  * proximity is set if the edge is used to minimize dependence distances
101  *
102  * For validity edges, start and end mark the sequence of inequality
103  * constraints in the LP problem that encode the validity constraint
104  * corresponding to this edge.
105  */
106 struct isl_sched_edge {
107         isl_map *map;
108
109         struct isl_sched_node *src;
110         struct isl_sched_node *dst;
111
112         int validity;
113         int proximity;
114
115         int start;
116         int end;
117 };
118
119 enum isl_edge_type {
120         isl_edge_validity = 0,
121         isl_edge_first = isl_edge_validity,
122         isl_edge_proximity,
123         isl_edge_last = isl_edge_proximity
124 };
125
126 /* Internal information about the dependence graph used during
127  * the construction of the schedule.
128  *
129  * intra_hmap is a cache, mapping dependence relations to their dual,
130  *      for dependences from a node to itself
131  * inter_hmap is a cache, mapping dependence relations to their dual,
132  *      for dependences between distinct nodes
133  *
134  * n is the number of nodes
135  * node is the list of nodes
136  * maxvar is the maximal number of variables over all nodes
137  * max_row is the allocated number of rows in the schedule
138  * n_row is the current (maximal) number of linearly independent
139  *      rows in the node schedules
140  * n_total_row is the current number of rows in the node schedules
141  * n_band is the current number of completed bands
142  * band_start is the starting row in the node schedules of the current band
143  * root is set if this graph is the original dependence graph,
144  *      without any splitting
145  *
146  * sorted contains a list of node indices sorted according to the
147  *      SCC to which a node belongs
148  *
149  * n_edge is the number of edges
150  * edge is the list of edges
151  * max_edge contains the maximal number of edges of each type;
152  *      in particular, it contains the number of edges in the inital graph.
153  * edge_table contains pointers into the edge array, hashed on the source
154  *      and sink spaces; there is one such table for each type;
155  *      a given edge may be referenced from more than one table
156  *      if the corresponding relation appears in more than of the
157  *      sets of dependences
158  *
159  * node_table contains pointers into the node array, hashed on the space
160  *
161  * region contains a list of variable sequences that should be non-trivial
162  *
163  * lp contains the (I)LP problem used to obtain new schedule rows
164  *
165  * src_scc and dst_scc are the source and sink SCCs of an edge with
166  *      conflicting constraints
167  *
168  * scc represents the number of components
169  */
170 struct isl_sched_graph {
171         isl_hmap_map_basic_set *intra_hmap;
172         isl_hmap_map_basic_set *inter_hmap;
173
174         struct isl_sched_node *node;
175         int n;
176         int maxvar;
177         int max_row;
178         int n_row;
179
180         int *sorted;
181
182         int n_band;
183         int n_total_row;
184         int band_start;
185
186         int root;
187
188         struct isl_sched_edge *edge;
189         int n_edge;
190         int max_edge[isl_edge_last + 1];
191         struct isl_hash_table *edge_table[isl_edge_last + 1];
192
193         struct isl_hash_table *node_table;
194         struct isl_region *region;
195
196         isl_basic_set *lp;
197
198         int src_scc;
199         int dst_scc;
200
201         int scc;
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_space_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_space *dim)
235 {
236         struct isl_hash_table_entry *entry;
237         uint32_t hash;
238
239         hash = isl_space_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 /* Add the given edge to graph->edge_table[type].
255  */
256 static int graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph,
257         enum isl_edge_type type, struct isl_sched_edge *edge)
258 {
259         struct isl_hash_table_entry *entry;
260         uint32_t hash;
261
262         hash = isl_hash_init();
263         hash = isl_hash_builtin(hash, edge->src);
264         hash = isl_hash_builtin(hash, edge->dst);
265         entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
266                                     &edge_has_src_and_dst, edge, 1);
267         if (!entry)
268                 return -1;
269         entry->data = edge;
270
271         return 0;
272 }
273
274 /* Allocate the edge_tables based on the maximal number of edges of
275  * each type.
276  */
277 static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
278 {
279         int i;
280
281         for (i = 0; i <= isl_edge_last; ++i) {
282                 graph->edge_table[i] = isl_hash_table_alloc(ctx,
283                                                             graph->max_edge[i]);
284                 if (!graph->edge_table[i])
285                         return -1;
286         }
287
288         return 0;
289 }
290
291 /* If graph->edge_table[type] contains an edge from the given source
292  * to the given destination, then return the hash table entry of this edge.
293  * Otherwise, return NULL.
294  */
295 static struct isl_hash_table_entry *graph_find_edge_entry(
296         struct isl_sched_graph *graph,
297         enum isl_edge_type type,
298         struct isl_sched_node *src, struct isl_sched_node *dst)
299 {
300         isl_ctx *ctx = isl_space_get_ctx(src->dim);
301         uint32_t hash;
302         struct isl_sched_edge temp = { .src = src, .dst = dst };
303
304         hash = isl_hash_init();
305         hash = isl_hash_builtin(hash, temp.src);
306         hash = isl_hash_builtin(hash, temp.dst);
307         return isl_hash_table_find(ctx, graph->edge_table[type], hash,
308                                     &edge_has_src_and_dst, &temp, 0);
309 }
310
311
312 /* If graph->edge_table[type] contains an edge from the given source
313  * to the given destination, then return this edge.
314  * Otherwise, return NULL.
315  */
316 static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
317         enum isl_edge_type type,
318         struct isl_sched_node *src, struct isl_sched_node *dst)
319 {
320         struct isl_hash_table_entry *entry;
321
322         entry = graph_find_edge_entry(graph, type, src, dst);
323         if (!entry)
324                 return NULL;
325
326         return entry->data;
327 }
328
329 /* Check whether the dependence graph has an edge of the give type
330  * between the given two nodes.
331  */
332 static int graph_has_edge(struct isl_sched_graph *graph,
333         enum isl_edge_type type,
334         struct isl_sched_node *src, struct isl_sched_node *dst)
335 {
336         struct isl_sched_edge *edge;
337         int empty;
338
339         edge = graph_find_edge(graph, type, src, dst);
340         if (!edge)
341                 return 0;
342
343         empty = isl_map_plain_is_empty(edge->map);
344         if (empty < 0)
345                 return -1;
346
347         return !empty;
348 }
349
350 /* If there is an edge from the given source to the given destination
351  * of any type then return this edge.
352  * Otherwise, return NULL.
353  */
354 static struct isl_sched_edge *graph_find_any_edge(struct isl_sched_graph *graph,
355         struct isl_sched_node *src, struct isl_sched_node *dst)
356 {
357         enum isl_edge_type i;
358         struct isl_sched_edge *edge;
359
360         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
361                 edge = graph_find_edge(graph, i, src, dst);
362                 if (edge)
363                         return edge;
364         }
365
366         return NULL;
367 }
368
369 /* Remove the given edge from all the edge_tables that refer to it.
370  */
371 static void graph_remove_edge(struct isl_sched_graph *graph,
372         struct isl_sched_edge *edge)
373 {
374         isl_ctx *ctx = isl_map_get_ctx(edge->map);
375         enum isl_edge_type i;
376
377         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
378                 struct isl_hash_table_entry *entry;
379
380                 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
381                 if (!entry)
382                         continue;
383                 if (entry->data != edge)
384                         continue;
385                 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
386         }
387 }
388
389 /* Check whether the dependence graph has any edge
390  * between the given two nodes.
391  */
392 static int graph_has_any_edge(struct isl_sched_graph *graph,
393         struct isl_sched_node *src, struct isl_sched_node *dst)
394 {
395         enum isl_edge_type i;
396         int r;
397
398         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
399                 r = graph_has_edge(graph, i, src, dst);
400                 if (r < 0 || r)
401                         return r;
402         }
403
404         return r;
405 }
406
407 /* Check whether the dependence graph has a validity edge
408  * between the given two nodes.
409  */
410 static int graph_has_validity_edge(struct isl_sched_graph *graph,
411         struct isl_sched_node *src, struct isl_sched_node *dst)
412 {
413         return graph_has_edge(graph, isl_edge_validity, src, dst);
414 }
415
416 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
417         int n_node, int n_edge)
418 {
419         int i;
420
421         graph->n = n_node;
422         graph->n_edge = n_edge;
423         graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
424         graph->sorted = isl_calloc_array(ctx, int, graph->n);
425         graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
426         graph->edge = isl_calloc_array(ctx,
427                                         struct isl_sched_edge, graph->n_edge);
428
429         graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
430         graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
431
432         if (!graph->node || !graph->region || !graph->edge || !graph->sorted)
433                 return -1;
434
435         for(i = 0; i < graph->n; ++i)
436                 graph->sorted[i] = i;
437
438         return 0;
439 }
440
441 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
442 {
443         int i;
444
445         isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
446         isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
447
448         for (i = 0; i < graph->n; ++i) {
449                 isl_space_free(graph->node[i].dim);
450                 isl_mat_free(graph->node[i].sched);
451                 isl_map_free(graph->node[i].sched_map);
452                 isl_mat_free(graph->node[i].cmap);
453                 if (graph->root) {
454                         free(graph->node[i].band);
455                         free(graph->node[i].band_id);
456                         free(graph->node[i].zero);
457                 }
458         }
459         free(graph->node);
460         free(graph->sorted);
461         for (i = 0; i < graph->n_edge; ++i)
462                 isl_map_free(graph->edge[i].map);
463         free(graph->edge);
464         free(graph->region);
465         for (i = 0; i <= isl_edge_last; ++i)
466                 isl_hash_table_free(ctx, graph->edge_table[i]);
467         isl_hash_table_free(ctx, graph->node_table);
468         isl_basic_set_free(graph->lp);
469 }
470
471 /* For each "set" on which this function is called, increment
472  * graph->n by one and update graph->maxvar.
473  */
474 static int init_n_maxvar(__isl_take isl_set *set, void *user)
475 {
476         struct isl_sched_graph *graph = user;
477         int nvar = isl_set_dim(set, isl_dim_set);
478
479         graph->n++;
480         if (nvar > graph->maxvar)
481                 graph->maxvar = nvar;
482
483         isl_set_free(set);
484
485         return 0;
486 }
487
488 /* Compute the number of rows that should be allocated for the schedule.
489  * The graph can be split at most "n - 1" times, there can be at most
490  * two rows for each dimension in the iteration domains (in particular,
491  * we usually have one row, but it may be split by split_scaled),
492  * and there can be one extra row for ordering the statements.
493  * Note that if we have actually split "n - 1" times, then no ordering
494  * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
495  */
496 static int compute_max_row(struct isl_sched_graph *graph,
497         __isl_keep isl_union_set *domain)
498 {
499         graph->n = 0;
500         graph->maxvar = 0;
501         if (isl_union_set_foreach_set(domain, &init_n_maxvar, graph) < 0)
502                 return -1;
503         graph->max_row = graph->n + 2 * graph->maxvar;
504
505         return 0;
506 }
507
508 /* Add a new node to the graph representing the given set.
509  */
510 static int extract_node(__isl_take isl_set *set, void *user)
511 {
512         int nvar, nparam;
513         isl_ctx *ctx;
514         isl_space *dim;
515         isl_mat *sched;
516         struct isl_sched_graph *graph = user;
517         int *band, *band_id, *zero;
518
519         ctx = isl_set_get_ctx(set);
520         dim = isl_set_get_space(set);
521         isl_set_free(set);
522         nvar = isl_space_dim(dim, isl_dim_set);
523         nparam = isl_space_dim(dim, isl_dim_param);
524         if (!ctx->opt->schedule_parametric)
525                 nparam = 0;
526         sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
527         graph->node[graph->n].dim = dim;
528         graph->node[graph->n].nvar = nvar;
529         graph->node[graph->n].nparam = nparam;
530         graph->node[graph->n].sched = sched;
531         graph->node[graph->n].sched_map = NULL;
532         band = isl_alloc_array(ctx, int, graph->max_row);
533         graph->node[graph->n].band = band;
534         band_id = isl_calloc_array(ctx, int, graph->max_row);
535         graph->node[graph->n].band_id = band_id;
536         zero = isl_calloc_array(ctx, int, graph->max_row);
537         graph->node[graph->n].zero = zero;
538         graph->n++;
539
540         if (!sched || !band || !band_id || !zero)
541                 return -1;
542
543         return 0;
544 }
545
546 struct isl_extract_edge_data {
547         enum isl_edge_type type;
548         struct isl_sched_graph *graph;
549 };
550
551 /* Add a new edge to the graph based on the given map
552  * and add it to data->graph->edge_table[data->type].
553  * If a dependence relation of a given type happens to be identical
554  * to one of the dependence relations of a type that was added before,
555  * then we don't create a new edge, but instead mark the original edge
556  * as also representing a dependence of the current type.
557  */
558 static int extract_edge(__isl_take isl_map *map, void *user)
559 {
560         isl_ctx *ctx = isl_map_get_ctx(map);
561         struct isl_extract_edge_data *data = user;
562         struct isl_sched_graph *graph = data->graph;
563         struct isl_sched_node *src, *dst;
564         isl_space *dim;
565         struct isl_sched_edge *edge;
566         int is_equal;
567
568         dim = isl_space_domain(isl_map_get_space(map));
569         src = graph_find_node(ctx, graph, dim);
570         isl_space_free(dim);
571         dim = isl_space_range(isl_map_get_space(map));
572         dst = graph_find_node(ctx, graph, dim);
573         isl_space_free(dim);
574
575         if (!src || !dst) {
576                 isl_map_free(map);
577                 return 0;
578         }
579
580         graph->edge[graph->n_edge].src = src;
581         graph->edge[graph->n_edge].dst = dst;
582         graph->edge[graph->n_edge].map = map;
583         if (data->type == isl_edge_validity) {
584                 graph->edge[graph->n_edge].validity = 1;
585                 graph->edge[graph->n_edge].proximity = 0;
586         }
587         if (data->type == isl_edge_proximity) {
588                 graph->edge[graph->n_edge].validity = 0;
589                 graph->edge[graph->n_edge].proximity = 1;
590         }
591         graph->n_edge++;
592
593         edge = graph_find_any_edge(graph, src, dst);
594         if (!edge)
595                 return graph_edge_table_add(ctx, graph, data->type,
596                                     &graph->edge[graph->n_edge - 1]);
597         is_equal = isl_map_plain_is_equal(map, edge->map);
598         if (is_equal < 0)
599                 return -1;
600         if (!is_equal)
601                 return graph_edge_table_add(ctx, graph, data->type,
602                                     &graph->edge[graph->n_edge - 1]);
603
604         graph->n_edge--;
605         edge->validity |= graph->edge[graph->n_edge].validity;
606         edge->proximity |= graph->edge[graph->n_edge].proximity;
607         isl_map_free(map);
608
609         return graph_edge_table_add(ctx, graph, data->type, edge);
610 }
611
612 /* Check whether there is any dependence from node[j] to node[i]
613  * or from node[i] to node[j].
614  */
615 static int node_follows_weak(int i, int j, void *user)
616 {
617         int f;
618         struct isl_sched_graph *graph = user;
619
620         f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]);
621         if (f < 0 || f)
622                 return f;
623         return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]);
624 }
625
626 /* Check whether there is a validity dependence from node[j] to node[i],
627  * forcing node[i] to follow node[j].
628  */
629 static int node_follows_strong(int i, int j, void *user)
630 {
631         struct isl_sched_graph *graph = user;
632
633         return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
634 }
635
636 /* Use Tarjan's algorithm for computing the strongly connected components
637  * in the dependence graph (only validity edges).
638  * If weak is set, we consider the graph to be undirected and
639  * we effectively compute the (weakly) connected components.
640  * Additionally, we also consider other edges when weak is set.
641  */
642 static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, int weak)
643 {
644         int i, n;
645         struct isl_tarjan_graph *g = NULL;
646
647         g = isl_tarjan_graph_init(ctx, graph->n,
648                 weak ? &node_follows_weak : &node_follows_strong, graph);
649         if (!g)
650                 return -1;
651
652         graph->scc = 0;
653         i = 0;
654         n = graph->n;
655         while (n) {
656                 while (g->order[i] != -1) {
657                         graph->node[g->order[i]].scc = graph->scc;
658                         --n;
659                         ++i;
660                 }
661                 ++i;
662                 graph->scc++;
663         }
664
665         isl_tarjan_graph_free(g);
666
667         return 0;
668 }
669
670 /* Apply Tarjan's algorithm to detect the strongly connected components
671  * in the dependence graph.
672  */
673 static int detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph)
674 {
675         return detect_ccs(ctx, graph, 0);
676 }
677
678 /* Apply Tarjan's algorithm to detect the (weakly) connected components
679  * in the dependence graph.
680  */
681 static int detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph)
682 {
683         return detect_ccs(ctx, graph, 1);
684 }
685
686 static int cmp_scc(const void *a, const void *b, void *data)
687 {
688         struct isl_sched_graph *graph = data;
689         const int *i1 = a;
690         const int *i2 = b;
691
692         return graph->node[*i1].scc - graph->node[*i2].scc;
693 }
694
695 /* Sort the elements of graph->sorted according to the corresponding SCCs.
696  */
697 static int sort_sccs(struct isl_sched_graph *graph)
698 {
699         return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
700 }
701
702 /* Given a dependence relation R from a node to itself,
703  * construct the set of coefficients of valid constraints for elements
704  * in that dependence relation.
705  * In particular, the result contains tuples of coefficients
706  * c_0, c_n, c_x such that
707  *
708  *      c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
709  *
710  * or, equivalently,
711  *
712  *      c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
713  *
714  * We choose here to compute the dual of delta R.
715  * Alternatively, we could have computed the dual of R, resulting
716  * in a set of tuples c_0, c_n, c_x, c_y, and then
717  * plugged in (c_0, c_n, c_x, -c_x).
718  */
719 static __isl_give isl_basic_set *intra_coefficients(
720         struct isl_sched_graph *graph, __isl_take isl_map *map)
721 {
722         isl_ctx *ctx = isl_map_get_ctx(map);
723         isl_set *delta;
724         isl_basic_set *coef;
725
726         if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
727                 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
728
729         delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
730         coef = isl_set_coefficients(delta);
731         isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
732                                         isl_basic_set_copy(coef));
733
734         return coef;
735 }
736
737 /* Given a dependence relation R, * construct the set of coefficients
738  * of valid constraints for elements in that dependence relation.
739  * In particular, the result contains tuples of coefficients
740  * c_0, c_n, c_x, c_y such that
741  *
742  *      c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
743  *
744  */
745 static __isl_give isl_basic_set *inter_coefficients(
746         struct isl_sched_graph *graph, __isl_take isl_map *map)
747 {
748         isl_ctx *ctx = isl_map_get_ctx(map);
749         isl_set *set;
750         isl_basic_set *coef;
751
752         if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
753                 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
754
755         set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
756         coef = isl_set_coefficients(set);
757         isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
758                                         isl_basic_set_copy(coef));
759
760         return coef;
761 }
762
763 /* Add constraints to graph->lp that force validity for the given
764  * dependence from a node i to itself.
765  * That is, add constraints that enforce
766  *
767  *      (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
768  *      = c_i_x (y - x) >= 0
769  *
770  * for each (x,y) in R.
771  * We obtain general constraints on coefficients (c_0, c_n, c_x)
772  * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
773  * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
774  * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
775  *
776  * Actually, we do not construct constraints for the c_i_x themselves,
777  * but for the coefficients of c_i_x written as a linear combination
778  * of the columns in node->cmap.
779  */
780 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
781         struct isl_sched_edge *edge)
782 {
783         unsigned total;
784         isl_map *map = isl_map_copy(edge->map);
785         isl_ctx *ctx = isl_map_get_ctx(map);
786         isl_space *dim;
787         isl_dim_map *dim_map;
788         isl_basic_set *coef;
789         struct isl_sched_node *node = edge->src;
790
791         coef = intra_coefficients(graph, map);
792
793         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
794
795         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
796                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
797         if (!coef)
798                 goto error;
799
800         total = isl_basic_set_total_dim(graph->lp);
801         dim_map = isl_dim_map_alloc(ctx, total);
802         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
803                           isl_space_dim(dim, isl_dim_set), 1,
804                           node->nvar, -1);
805         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
806                           isl_space_dim(dim, isl_dim_set), 1,
807                           node->nvar, 1);
808         graph->lp = isl_basic_set_extend_constraints(graph->lp,
809                         coef->n_eq, coef->n_ineq);
810         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
811                                                            coef, dim_map);
812         isl_space_free(dim);
813
814         return 0;
815 error:
816         isl_space_free(dim);
817         return -1;
818 }
819
820 /* Add constraints to graph->lp that force validity for the given
821  * dependence from node i to node j.
822  * That is, add constraints that enforce
823  *
824  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
825  *
826  * for each (x,y) in R.
827  * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
828  * of valid constraints for R and then plug in
829  * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
830  *  c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
831  * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
832  * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
833  *
834  * Actually, we do not construct constraints for the c_*_x themselves,
835  * but for the coefficients of c_*_x written as a linear combination
836  * of the columns in node->cmap.
837  */
838 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
839         struct isl_sched_edge *edge)
840 {
841         unsigned total;
842         isl_map *map = isl_map_copy(edge->map);
843         isl_ctx *ctx = isl_map_get_ctx(map);
844         isl_space *dim;
845         isl_dim_map *dim_map;
846         isl_basic_set *coef;
847         struct isl_sched_node *src = edge->src;
848         struct isl_sched_node *dst = edge->dst;
849
850         coef = inter_coefficients(graph, map);
851
852         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
853
854         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
855                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
856         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
857                     isl_space_dim(dim, isl_dim_set) + src->nvar,
858                     isl_mat_copy(dst->cmap));
859         if (!coef)
860                 goto error;
861
862         total = isl_basic_set_total_dim(graph->lp);
863         dim_map = isl_dim_map_alloc(ctx, total);
864
865         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
866         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
867         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
868         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
869                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
870                           dst->nvar, -1);
871         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
872                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
873                           dst->nvar, 1);
874
875         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
876         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
877         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
878         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
879                           isl_space_dim(dim, isl_dim_set), 1,
880                           src->nvar, 1);
881         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
882                           isl_space_dim(dim, isl_dim_set), 1,
883                           src->nvar, -1);
884
885         edge->start = graph->lp->n_ineq;
886         graph->lp = isl_basic_set_extend_constraints(graph->lp,
887                         coef->n_eq, coef->n_ineq);
888         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
889                                                            coef, dim_map);
890         if (!graph->lp)
891                 goto error;
892         isl_space_free(dim);
893         edge->end = graph->lp->n_ineq;
894
895         return 0;
896 error:
897         isl_space_free(dim);
898         return -1;
899 }
900
901 /* Add constraints to graph->lp that bound the dependence distance for the given
902  * dependence from a node i to itself.
903  * If s = 1, we add the constraint
904  *
905  *      c_i_x (y - x) <= m_0 + m_n n
906  *
907  * or
908  *
909  *      -c_i_x (y - x) + m_0 + m_n n >= 0
910  *
911  * for each (x,y) in R.
912  * If s = -1, we add the constraint
913  *
914  *      -c_i_x (y - x) <= m_0 + m_n n
915  *
916  * or
917  *
918  *      c_i_x (y - x) + m_0 + m_n n >= 0
919  *
920  * for each (x,y) in R.
921  * We obtain general constraints on coefficients (c_0, c_n, c_x)
922  * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
923  * with each coefficient (except m_0) represented as a pair of non-negative
924  * coefficients.
925  *
926  * Actually, we do not construct constraints for the c_i_x themselves,
927  * but for the coefficients of c_i_x written as a linear combination
928  * of the columns in node->cmap.
929  */
930 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
931         struct isl_sched_edge *edge, int s)
932 {
933         unsigned total;
934         unsigned nparam;
935         isl_map *map = isl_map_copy(edge->map);
936         isl_ctx *ctx = isl_map_get_ctx(map);
937         isl_space *dim;
938         isl_dim_map *dim_map;
939         isl_basic_set *coef;
940         struct isl_sched_node *node = edge->src;
941
942         coef = intra_coefficients(graph, map);
943
944         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
945
946         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
947                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
948         if (!coef)
949                 goto error;
950
951         nparam = isl_space_dim(node->dim, isl_dim_param);
952         total = isl_basic_set_total_dim(graph->lp);
953         dim_map = isl_dim_map_alloc(ctx, total);
954         isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
955         isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
956         isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
957         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
958                           isl_space_dim(dim, isl_dim_set), 1,
959                           node->nvar, s);
960         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
961                           isl_space_dim(dim, isl_dim_set), 1,
962                           node->nvar, -s);
963         graph->lp = isl_basic_set_extend_constraints(graph->lp,
964                         coef->n_eq, coef->n_ineq);
965         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
966                                                            coef, dim_map);
967         isl_space_free(dim);
968
969         return 0;
970 error:
971         isl_space_free(dim);
972         return -1;
973 }
974
975 /* Add constraints to graph->lp that bound the dependence distance for the given
976  * dependence from node i to node j.
977  * If s = 1, we add the constraint
978  *
979  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
980  *              <= m_0 + m_n n
981  *
982  * or
983  *
984  *      -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
985  *              m_0 + m_n n >= 0
986  *
987  * for each (x,y) in R.
988  * If s = -1, we add the constraint
989  *
990  *      -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
991  *              <= m_0 + m_n n
992  *
993  * or
994  *
995  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
996  *              m_0 + m_n n >= 0
997  *
998  * for each (x,y) in R.
999  * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1000  * of valid constraints for R and then plug in
1001  * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1002  *  -s*c_j_x+s*c_i_x)
1003  * with each coefficient (except m_0, c_j_0 and c_i_0)
1004  * represented as a pair of non-negative coefficients.
1005  *
1006  * Actually, we do not construct constraints for the c_*_x themselves,
1007  * but for the coefficients of c_*_x written as a linear combination
1008  * of the columns in node->cmap.
1009  */
1010 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
1011         struct isl_sched_edge *edge, int s)
1012 {
1013         unsigned total;
1014         unsigned nparam;
1015         isl_map *map = isl_map_copy(edge->map);
1016         isl_ctx *ctx = isl_map_get_ctx(map);
1017         isl_space *dim;
1018         isl_dim_map *dim_map;
1019         isl_basic_set *coef;
1020         struct isl_sched_node *src = edge->src;
1021         struct isl_sched_node *dst = edge->dst;
1022
1023         coef = inter_coefficients(graph, map);
1024
1025         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1026
1027         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1028                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1029         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1030                     isl_space_dim(dim, isl_dim_set) + src->nvar,
1031                     isl_mat_copy(dst->cmap));
1032         if (!coef)
1033                 goto error;
1034
1035         nparam = isl_space_dim(src->dim, isl_dim_param);
1036         total = isl_basic_set_total_dim(graph->lp);
1037         dim_map = isl_dim_map_alloc(ctx, total);
1038
1039         isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1040         isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1041         isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1042
1043         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
1044         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
1045         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
1046         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1047                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1048                           dst->nvar, s);
1049         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1050                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1051                           dst->nvar, -s);
1052
1053         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
1054         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
1055         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
1056         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1057                           isl_space_dim(dim, isl_dim_set), 1,
1058                           src->nvar, -s);
1059         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1060                           isl_space_dim(dim, isl_dim_set), 1,
1061                           src->nvar, s);
1062
1063         graph->lp = isl_basic_set_extend_constraints(graph->lp,
1064                         coef->n_eq, coef->n_ineq);
1065         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1066                                                            coef, dim_map);
1067         isl_space_free(dim);
1068
1069         return 0;
1070 error:
1071         isl_space_free(dim);
1072         return -1;
1073 }
1074
1075 static int add_all_validity_constraints(struct isl_sched_graph *graph)
1076 {
1077         int i;
1078
1079         for (i = 0; i < graph->n_edge; ++i) {
1080                 struct isl_sched_edge *edge= &graph->edge[i];
1081                 if (!edge->validity)
1082                         continue;
1083                 if (edge->src != edge->dst)
1084                         continue;
1085                 if (add_intra_validity_constraints(graph, edge) < 0)
1086                         return -1;
1087         }
1088
1089         for (i = 0; i < graph->n_edge; ++i) {
1090                 struct isl_sched_edge *edge = &graph->edge[i];
1091                 if (!edge->validity)
1092                         continue;
1093                 if (edge->src == edge->dst)
1094                         continue;
1095                 if (add_inter_validity_constraints(graph, edge) < 0)
1096                         return -1;
1097         }
1098
1099         return 0;
1100 }
1101
1102 /* Add constraints to graph->lp that bound the dependence distance
1103  * for all dependence relations.
1104  * If a given proximity dependence is identical to a validity
1105  * dependence, then the dependence distance is already bounded
1106  * from below (by zero), so we only need to bound the distance
1107  * from above.
1108  * Otherwise, we need to bound the distance both from above and from below.
1109  */
1110 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
1111 {
1112         int i;
1113
1114         for (i = 0; i < graph->n_edge; ++i) {
1115                 struct isl_sched_edge *edge= &graph->edge[i];
1116                 if (!edge->proximity)
1117                         continue;
1118                 if (edge->src == edge->dst &&
1119                     add_intra_proximity_constraints(graph, edge, 1) < 0)
1120                         return -1;
1121                 if (edge->src != edge->dst &&
1122                     add_inter_proximity_constraints(graph, edge, 1) < 0)
1123                         return -1;
1124                 if (edge->validity)
1125                         continue;
1126                 if (edge->src == edge->dst &&
1127                     add_intra_proximity_constraints(graph, edge, -1) < 0)
1128                         return -1;
1129                 if (edge->src != edge->dst &&
1130                     add_inter_proximity_constraints(graph, edge, -1) < 0)
1131                         return -1;
1132         }
1133
1134         return 0;
1135 }
1136
1137 /* Compute a basis for the rows in the linear part of the schedule
1138  * and extend this basis to a full basis.  The remaining rows
1139  * can then be used to force linear independence from the rows
1140  * in the schedule.
1141  *
1142  * In particular, given the schedule rows S, we compute
1143  *
1144  *      S = H Q
1145  *
1146  * with H the Hermite normal form of S.  That is, all but the
1147  * first rank columns of Q are zero and so each row in S is
1148  * a linear combination of the first rank rows of Q.
1149  * The matrix Q is then transposed because we will write the
1150  * coefficients of the next schedule row as a column vector s
1151  * and express this s as a linear combination s = Q c of the
1152  * computed basis.
1153  */
1154 static int node_update_cmap(struct isl_sched_node *node)
1155 {
1156         isl_mat *H, *Q;
1157         int n_row = isl_mat_rows(node->sched);
1158
1159         H = isl_mat_sub_alloc(node->sched, 0, n_row,
1160                               1 + node->nparam, node->nvar);
1161
1162         H = isl_mat_left_hermite(H, 0, NULL, &Q);
1163         isl_mat_free(node->cmap);
1164         node->cmap = isl_mat_transpose(Q);
1165         node->rank = isl_mat_initial_non_zero_cols(H);
1166         isl_mat_free(H);
1167
1168         if (!node->cmap || node->rank < 0)
1169                 return -1;
1170         return 0;
1171 }
1172
1173 /* Count the number of equality and inequality constraints
1174  * that will be added for the given map.
1175  * If carry is set, then we are counting the number of (validity)
1176  * constraints that will be added in setup_carry_lp and we count
1177  * each edge exactly once.  Otherwise, we count as follows
1178  * validity             -> 1 (>= 0)
1179  * validity+proximity   -> 2 (>= 0 and upper bound)
1180  * proximity            -> 2 (lower and upper bound)
1181  */
1182 static int count_map_constraints(struct isl_sched_graph *graph,
1183         struct isl_sched_edge *edge, __isl_take isl_map *map,
1184         int *n_eq, int *n_ineq, int carry)
1185 {
1186         isl_basic_set *coef;
1187         int f = carry ? 1 : edge->proximity ? 2 : 1;
1188
1189         if (carry && !edge->validity) {
1190                 isl_map_free(map);
1191                 return 0;
1192         }
1193
1194         if (edge->src == edge->dst)
1195                 coef = intra_coefficients(graph, map);
1196         else
1197                 coef = inter_coefficients(graph, map);
1198         if (!coef)
1199                 return -1;
1200         *n_eq += f * coef->n_eq;
1201         *n_ineq += f * coef->n_ineq;
1202         isl_basic_set_free(coef);
1203
1204         return 0;
1205 }
1206
1207 /* Count the number of equality and inequality constraints
1208  * that will be added to the main lp problem.
1209  * We count as follows
1210  * validity             -> 1 (>= 0)
1211  * validity+proximity   -> 2 (>= 0 and upper bound)
1212  * proximity            -> 2 (lower and upper bound)
1213  */
1214 static int count_constraints(struct isl_sched_graph *graph,
1215         int *n_eq, int *n_ineq)
1216 {
1217         int i;
1218
1219         *n_eq = *n_ineq = 0;
1220         for (i = 0; i < graph->n_edge; ++i) {
1221                 struct isl_sched_edge *edge= &graph->edge[i];
1222                 isl_map *map = isl_map_copy(edge->map);
1223
1224                 if (count_map_constraints(graph, edge, map,
1225                                           n_eq, n_ineq, 0) < 0)
1226                         return -1;
1227         }
1228
1229         return 0;
1230 }
1231
1232 /* Add constraints that bound the values of the variable and parameter
1233  * coefficients of the schedule.
1234  *
1235  * The maximal value of the coefficients is defined by the option
1236  * 'schedule_max_coefficient'.
1237  */
1238 static int add_bound_coefficient_constraints(isl_ctx *ctx,
1239         struct isl_sched_graph *graph)
1240 {
1241         int i, j, k;
1242         int max_coefficient;
1243         int total;
1244
1245         max_coefficient = ctx->opt->schedule_max_coefficient;
1246
1247         if (max_coefficient == -1)
1248                 return 0;
1249
1250         total = isl_basic_set_total_dim(graph->lp);
1251
1252         for (i = 0; i < graph->n; ++i) {
1253                 struct isl_sched_node *node = &graph->node[i];
1254                 for (j = 0; j < 2 * node->nparam + 2 * node->nvar; ++j) {
1255                         int dim;
1256                         k = isl_basic_set_alloc_inequality(graph->lp);
1257                         if (k < 0)
1258                                 return -1;
1259                         dim = 1 + node->start + 1 + j;
1260                         isl_seq_clr(graph->lp->ineq[k], 1 +  total);
1261                         isl_int_set_si(graph->lp->ineq[k][dim], -1);
1262                         isl_int_set_si(graph->lp->ineq[k][0], max_coefficient);
1263                 }
1264         }
1265
1266         return 0;
1267 }
1268
1269 /* Construct an ILP problem for finding schedule coefficients
1270  * that result in non-negative, but small dependence distances
1271  * over all dependences.
1272  * In particular, the dependence distances over proximity edges
1273  * are bounded by m_0 + m_n n and we compute schedule coefficients
1274  * with small values (preferably zero) of m_n and m_0.
1275  *
1276  * All variables of the ILP are non-negative.  The actual coefficients
1277  * may be negative, so each coefficient is represented as the difference
1278  * of two non-negative variables.  The negative part always appears
1279  * immediately before the positive part.
1280  * Other than that, the variables have the following order
1281  *
1282  *      - sum of positive and negative parts of m_n coefficients
1283  *      - m_0
1284  *      - sum of positive and negative parts of all c_n coefficients
1285  *              (unconstrained when computing non-parametric schedules)
1286  *      - sum of positive and negative parts of all c_x coefficients
1287  *      - positive and negative parts of m_n coefficients
1288  *      - for each node
1289  *              - c_i_0
1290  *              - positive and negative parts of c_i_n (if parametric)
1291  *              - positive and negative parts of c_i_x
1292  *
1293  * The c_i_x are not represented directly, but through the columns of
1294  * node->cmap.  That is, the computed values are for variable t_i_x
1295  * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1296  *
1297  * The constraints are those from the edges plus two or three equalities
1298  * to express the sums.
1299  *
1300  * If force_zero is set, then we add equalities to ensure that
1301  * the sum of the m_n coefficients and m_0 are both zero.
1302  */
1303 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
1304         int force_zero)
1305 {
1306         int i, j;
1307         int k;
1308         unsigned nparam;
1309         unsigned total;
1310         isl_space *dim;
1311         int parametric;
1312         int param_pos;
1313         int n_eq, n_ineq;
1314         int max_constant_term;
1315         int max_coefficient;
1316
1317         max_constant_term = ctx->opt->schedule_max_constant_term;
1318         max_coefficient = ctx->opt->schedule_max_coefficient;
1319
1320         parametric = ctx->opt->schedule_parametric;
1321         nparam = isl_space_dim(graph->node[0].dim, isl_dim_param);
1322         param_pos = 4;
1323         total = param_pos + 2 * nparam;
1324         for (i = 0; i < graph->n; ++i) {
1325                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1326                 if (node_update_cmap(node) < 0)
1327                         return -1;
1328                 node->start = total;
1329                 total += 1 + 2 * (node->nparam + node->nvar);
1330         }
1331
1332         if (count_constraints(graph, &n_eq, &n_ineq) < 0)
1333                 return -1;
1334
1335         dim = isl_space_set_alloc(ctx, 0, total);
1336         isl_basic_set_free(graph->lp);
1337         n_eq += 2 + parametric + force_zero;
1338         if (max_constant_term != -1)
1339                 n_ineq += graph->n;
1340         if (max_coefficient != -1)
1341                 for (i = 0; i < graph->n; ++i)
1342                         n_ineq += 2 * graph->node[i].nparam +
1343                                   2 * graph->node[i].nvar;
1344
1345         graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
1346
1347         k = isl_basic_set_alloc_equality(graph->lp);
1348         if (k < 0)
1349                 return -1;
1350         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1351         if (!force_zero)
1352                 isl_int_set_si(graph->lp->eq[k][1], -1);
1353         for (i = 0; i < 2 * nparam; ++i)
1354                 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1355
1356         if (force_zero) {
1357                 k = isl_basic_set_alloc_equality(graph->lp);
1358                 if (k < 0)
1359                         return -1;
1360                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1361                 isl_int_set_si(graph->lp->eq[k][2], -1);
1362         }
1363
1364         if (parametric) {
1365                 k = isl_basic_set_alloc_equality(graph->lp);
1366                 if (k < 0)
1367                         return -1;
1368                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1369                 isl_int_set_si(graph->lp->eq[k][3], -1);
1370                 for (i = 0; i < graph->n; ++i) {
1371                         int pos = 1 + graph->node[i].start + 1;
1372
1373                         for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1374                                 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1375                 }
1376         }
1377
1378         k = isl_basic_set_alloc_equality(graph->lp);
1379         if (k < 0)
1380                 return -1;
1381         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1382         isl_int_set_si(graph->lp->eq[k][4], -1);
1383         for (i = 0; i < graph->n; ++i) {
1384                 struct isl_sched_node *node = &graph->node[i];
1385                 int pos = 1 + node->start + 1 + 2 * node->nparam;
1386
1387                 for (j = 0; j < 2 * node->nvar; ++j)
1388                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1389         }
1390
1391         if (max_constant_term != -1)
1392                 for (i = 0; i < graph->n; ++i) {
1393                         struct isl_sched_node *node = &graph->node[i];
1394                         k = isl_basic_set_alloc_inequality(graph->lp);
1395                         if (k < 0)
1396                                 return -1;
1397                         isl_seq_clr(graph->lp->ineq[k], 1 +  total);
1398                         isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1);
1399                         isl_int_set_si(graph->lp->ineq[k][0], max_constant_term);
1400                 }
1401
1402         if (add_bound_coefficient_constraints(ctx, graph) < 0)
1403                 return -1;
1404         if (add_all_validity_constraints(graph) < 0)
1405                 return -1;
1406         if (add_all_proximity_constraints(graph) < 0)
1407                 return -1;
1408
1409         return 0;
1410 }
1411
1412 /* Analyze the conflicting constraint found by
1413  * isl_tab_basic_set_non_trivial_lexmin.  If it corresponds to the validity
1414  * constraint of one of the edges between distinct nodes, living, moreover
1415  * in distinct SCCs, then record the source and sink SCC as this may
1416  * be a good place to cut between SCCs.
1417  */
1418 static int check_conflict(int con, void *user)
1419 {
1420         int i;
1421         struct isl_sched_graph *graph = user;
1422
1423         if (graph->src_scc >= 0)
1424                 return 0;
1425
1426         con -= graph->lp->n_eq;
1427
1428         if (con >= graph->lp->n_ineq)
1429                 return 0;
1430
1431         for (i = 0; i < graph->n_edge; ++i) {
1432                 if (!graph->edge[i].validity)
1433                         continue;
1434                 if (graph->edge[i].src == graph->edge[i].dst)
1435                         continue;
1436                 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1437                         continue;
1438                 if (graph->edge[i].start > con)
1439                         continue;
1440                 if (graph->edge[i].end <= con)
1441                         continue;
1442                 graph->src_scc = graph->edge[i].src->scc;
1443                 graph->dst_scc = graph->edge[i].dst->scc;
1444         }
1445
1446         return 0;
1447 }
1448
1449 /* Check whether the next schedule row of the given node needs to be
1450  * non-trivial.  Lower-dimensional domains may have some trivial rows,
1451  * but as soon as the number of remaining required non-trivial rows
1452  * is as large as the number or remaining rows to be computed,
1453  * all remaining rows need to be non-trivial.
1454  */
1455 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1456 {
1457         return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1458 }
1459
1460 /* Solve the ILP problem constructed in setup_lp.
1461  * For each node such that all the remaining rows of its schedule
1462  * need to be non-trivial, we construct a non-triviality region.
1463  * This region imposes that the next row is independent of previous rows.
1464  * In particular the coefficients c_i_x are represented by t_i_x
1465  * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1466  * its first columns span the rows of the previously computed part
1467  * of the schedule.  The non-triviality region enforces that at least
1468  * one of the remaining components of t_i_x is non-zero, i.e.,
1469  * that the new schedule row depends on at least one of the remaining
1470  * columns of Q.
1471  */
1472 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1473 {
1474         int i;
1475         isl_vec *sol;
1476         isl_basic_set *lp;
1477
1478         for (i = 0; i < graph->n; ++i) {
1479                 struct isl_sched_node *node = &graph->node[i];
1480                 int skip = node->rank;
1481                 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1482                 if (needs_row(graph, node))
1483                         graph->region[i].len = 2 * (node->nvar - skip);
1484                 else
1485                         graph->region[i].len = 0;
1486         }
1487         lp = isl_basic_set_copy(graph->lp);
1488         sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1489                                        graph->region, &check_conflict, graph);
1490         return sol;
1491 }
1492
1493 /* Update the schedules of all nodes based on the given solution
1494  * of the LP problem.
1495  * The new row is added to the current band.
1496  * All possibly negative coefficients are encoded as a difference
1497  * of two non-negative variables, so we need to perform the subtraction
1498  * here.  Moreover, if use_cmap is set, then the solution does
1499  * not refer to the actual coefficients c_i_x, but instead to variables
1500  * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1501  * In this case, we then also need to perform this multiplication
1502  * to obtain the values of c_i_x.
1503  *
1504  * If check_zero is set, then the first two coordinates of sol are
1505  * assumed to correspond to the dependence distance.  If these two
1506  * coordinates are zero, then the corresponding scheduling dimension
1507  * is marked as being zero distance.
1508  */
1509 static int update_schedule(struct isl_sched_graph *graph,
1510         __isl_take isl_vec *sol, int use_cmap, int check_zero)
1511 {
1512         int i, j;
1513         int zero = 0;
1514         isl_vec *csol = NULL;
1515
1516         if (!sol)
1517                 goto error;
1518         if (sol->size == 0)
1519                 isl_die(sol->ctx, isl_error_internal,
1520                         "no solution found", goto error);
1521         if (graph->n_total_row >= graph->max_row)
1522                 isl_die(sol->ctx, isl_error_internal,
1523                         "too many schedule rows", goto error);
1524
1525         if (check_zero)
1526                 zero = isl_int_is_zero(sol->el[1]) &&
1527                            isl_int_is_zero(sol->el[2]);
1528
1529         for (i = 0; i < graph->n; ++i) {
1530                 struct isl_sched_node *node = &graph->node[i];
1531                 int pos = node->start;
1532                 int row = isl_mat_rows(node->sched);
1533
1534                 isl_vec_free(csol);
1535                 csol = isl_vec_alloc(sol->ctx, node->nvar);
1536                 if (!csol)
1537                         goto error;
1538
1539                 isl_map_free(node->sched_map);
1540                 node->sched_map = NULL;
1541                 node->sched = isl_mat_add_rows(node->sched, 1);
1542                 if (!node->sched)
1543                         goto error;
1544                 node->sched = isl_mat_set_element(node->sched, row, 0,
1545                                                   sol->el[1 + pos]);
1546                 for (j = 0; j < node->nparam + node->nvar; ++j)
1547                         isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1548                                     sol->el[1 + pos + 1 + 2 * j + 1],
1549                                     sol->el[1 + pos + 1 + 2 * j]);
1550                 for (j = 0; j < node->nparam; ++j)
1551                         node->sched = isl_mat_set_element(node->sched,
1552                                         row, 1 + j, sol->el[1+pos+1+2*j+1]);
1553                 for (j = 0; j < node->nvar; ++j)
1554                         isl_int_set(csol->el[j],
1555                                     sol->el[1+pos+1+2*(node->nparam+j)+1]);
1556                 if (use_cmap)
1557                         csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1558                                                    csol);
1559                 if (!csol)
1560                         goto error;
1561                 for (j = 0; j < node->nvar; ++j)
1562                         node->sched = isl_mat_set_element(node->sched,
1563                                         row, 1 + node->nparam + j, csol->el[j]);
1564                 node->band[graph->n_total_row] = graph->n_band;
1565                 node->zero[graph->n_total_row] = zero;
1566         }
1567         isl_vec_free(sol);
1568         isl_vec_free(csol);
1569
1570         graph->n_row++;
1571         graph->n_total_row++;
1572
1573         return 0;
1574 error:
1575         isl_vec_free(sol);
1576         isl_vec_free(csol);
1577         return -1;
1578 }
1579
1580 /* Convert node->sched into a multi_aff and return this multi_aff.
1581  */
1582 static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
1583         struct isl_sched_node *node)
1584 {
1585         int i, j;
1586         isl_space *space;
1587         isl_local_space *ls;
1588         isl_aff *aff;
1589         isl_multi_aff *ma;
1590         int nrow, ncol;
1591         isl_int v;
1592
1593         nrow = isl_mat_rows(node->sched);
1594         ncol = isl_mat_cols(node->sched) - 1;
1595         space = isl_space_from_domain(isl_space_copy(node->dim));
1596         space = isl_space_add_dims(space, isl_dim_out, nrow);
1597         ma = isl_multi_aff_zero(space);
1598         ls = isl_local_space_from_space(isl_space_copy(node->dim));
1599
1600         isl_int_init(v);
1601
1602         for (i = 0; i < nrow; ++i) {
1603                 aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1604                 isl_mat_get_element(node->sched, i, 0, &v);
1605                 aff = isl_aff_set_constant(aff, v);
1606                 for (j = 0; j < node->nparam; ++j) {
1607                         isl_mat_get_element(node->sched, i, 1 + j, &v);
1608                         aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
1609                 }
1610                 for (j = 0; j < node->nvar; ++j) {
1611                         isl_mat_get_element(node->sched,
1612                                             i, 1 + node->nparam + j, &v);
1613                         aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
1614                 }
1615                 ma = isl_multi_aff_set_aff(ma, i, aff);
1616         }
1617
1618         isl_int_clear(v);
1619
1620         isl_local_space_free(ls);
1621
1622         return ma;
1623 }
1624
1625 /* Convert node->sched into a map and return this map.
1626  *
1627  * The result is cached in node->sched_map, which needs to be released
1628  * whenever node->sched is updated.
1629  */
1630 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1631 {
1632         if (!node->sched_map) {
1633                 isl_multi_aff *ma;
1634
1635                 ma = node_extract_schedule_multi_aff(node);
1636                 node->sched_map = isl_map_from_multi_aff(ma);
1637         }
1638
1639         return isl_map_copy(node->sched_map);
1640 }
1641
1642 /* Update the given dependence relation based on the current schedule.
1643  * That is, intersect the dependence relation with a map expressing
1644  * that source and sink are executed within the same iteration of
1645  * the current schedule.
1646  * This is not the most efficient way, but this shouldn't be a critical
1647  * operation.
1648  */
1649 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1650         struct isl_sched_node *src, struct isl_sched_node *dst)
1651 {
1652         isl_map *src_sched, *dst_sched, *id;
1653
1654         src_sched = node_extract_schedule(src);
1655         dst_sched = node_extract_schedule(dst);
1656         id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1657         return isl_map_intersect(map, id);
1658 }
1659
1660 /* Update the dependence relations of all edges based on the current schedule.
1661  * If a dependence is carried completely by the current schedule, then
1662  * it is removed from the edge_tables.  It is kept in the list of edges
1663  * as otherwise all edge_tables would have to be recomputed.
1664  */
1665 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1666 {
1667         int i;
1668
1669         for (i = graph->n_edge - 1; i >= 0; --i) {
1670                 struct isl_sched_edge *edge = &graph->edge[i];
1671                 edge->map = specialize(edge->map, edge->src, edge->dst);
1672                 if (!edge->map)
1673                         return -1;
1674
1675                 if (isl_map_plain_is_empty(edge->map))
1676                         graph_remove_edge(graph, edge);
1677         }
1678
1679         return 0;
1680 }
1681
1682 static void next_band(struct isl_sched_graph *graph)
1683 {
1684         graph->band_start = graph->n_total_row;
1685         graph->n_band++;
1686 }
1687
1688 /* Topologically sort statements mapped to the same schedule iteration
1689  * and add a row to the schedule corresponding to this order.
1690  */
1691 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1692 {
1693         int i, j;
1694
1695         if (graph->n <= 1)
1696                 return 0;
1697
1698         if (update_edges(ctx, graph) < 0)
1699                 return -1;
1700
1701         if (graph->n_edge == 0)
1702                 return 0;
1703
1704         if (detect_sccs(ctx, graph) < 0)
1705                 return -1;
1706
1707         if (graph->n_total_row >= graph->max_row)
1708                 isl_die(ctx, isl_error_internal,
1709                         "too many schedule rows", return -1);
1710
1711         for (i = 0; i < graph->n; ++i) {
1712                 struct isl_sched_node *node = &graph->node[i];
1713                 int row = isl_mat_rows(node->sched);
1714                 int cols = isl_mat_cols(node->sched);
1715
1716                 isl_map_free(node->sched_map);
1717                 node->sched_map = NULL;
1718                 node->sched = isl_mat_add_rows(node->sched, 1);
1719                 if (!node->sched)
1720                         return -1;
1721                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1722                                                      node->scc);
1723                 for (j = 1; j < cols; ++j)
1724                         node->sched = isl_mat_set_element_si(node->sched,
1725                                                              row, j, 0);
1726                 node->band[graph->n_total_row] = graph->n_band;
1727         }
1728
1729         graph->n_total_row++;
1730         next_band(graph);
1731
1732         return 0;
1733 }
1734
1735 /* Construct an isl_schedule based on the computed schedule stored
1736  * in graph and with parameters specified by dim.
1737  */
1738 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1739         __isl_take isl_space *dim)
1740 {
1741         int i;
1742         isl_ctx *ctx;
1743         isl_schedule *sched = NULL;
1744                 
1745         if (!dim)
1746                 return NULL;
1747
1748         ctx = isl_space_get_ctx(dim);
1749         sched = isl_calloc(ctx, struct isl_schedule,
1750                            sizeof(struct isl_schedule) +
1751                            (graph->n - 1) * sizeof(struct isl_schedule_node));
1752         if (!sched)
1753                 goto error;
1754
1755         sched->ref = 1;
1756         sched->n = graph->n;
1757         sched->n_band = graph->n_band;
1758         sched->n_total_row = graph->n_total_row;
1759
1760         for (i = 0; i < sched->n; ++i) {
1761                 int r, b;
1762                 int *band_end, *band_id, *zero;
1763
1764                 sched->node[i].sched =
1765                         node_extract_schedule_multi_aff(&graph->node[i]);
1766                 if (!sched->node[i].sched)
1767                         goto error;
1768
1769                 sched->node[i].n_band = graph->n_band;
1770                 if (graph->n_band == 0)
1771                         continue;
1772
1773                 band_end = isl_alloc_array(ctx, int, graph->n_band);
1774                 band_id = isl_alloc_array(ctx, int, graph->n_band);
1775                 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1776                 sched->node[i].band_end = band_end;
1777                 sched->node[i].band_id = band_id;
1778                 sched->node[i].zero = zero;
1779                 if (!band_end || !band_id || !zero)
1780                         goto error;
1781
1782                 for (r = 0; r < graph->n_total_row; ++r)
1783                         zero[r] = graph->node[i].zero[r];
1784                 for (r = b = 0; r < graph->n_total_row; ++r) {
1785                         if (graph->node[i].band[r] == b)
1786                                 continue;
1787                         band_end[b++] = r;
1788                         if (graph->node[i].band[r] == -1)
1789                                 break;
1790                 }
1791                 if (r == graph->n_total_row)
1792                         band_end[b++] = r;
1793                 sched->node[i].n_band = b;
1794                 for (--b; b >= 0; --b)
1795                         band_id[b] = graph->node[i].band_id[b];
1796         }
1797
1798         sched->dim = dim;
1799
1800         return sched;
1801 error:
1802         isl_space_free(dim);
1803         isl_schedule_free(sched);
1804         return NULL;
1805 }
1806
1807 /* Copy nodes that satisfy node_pred from the src dependence graph
1808  * to the dst dependence graph.
1809  */
1810 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1811         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1812 {
1813         int i;
1814
1815         dst->n = 0;
1816         for (i = 0; i < src->n; ++i) {
1817                 if (!node_pred(&src->node[i], data))
1818                         continue;
1819                 dst->node[dst->n].dim = isl_space_copy(src->node[i].dim);
1820                 dst->node[dst->n].nvar = src->node[i].nvar;
1821                 dst->node[dst->n].nparam = src->node[i].nparam;
1822                 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1823                 dst->node[dst->n].sched_map =
1824                         isl_map_copy(src->node[i].sched_map);
1825                 dst->node[dst->n].band = src->node[i].band;
1826                 dst->node[dst->n].band_id = src->node[i].band_id;
1827                 dst->node[dst->n].zero = src->node[i].zero;
1828                 dst->n++;
1829         }
1830
1831         return 0;
1832 }
1833
1834 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1835  * to the dst dependence graph.
1836  * If the source or destination node of the edge is not in the destination
1837  * graph, then it must be a backward proximity edge and it should simply
1838  * be ignored.
1839  */
1840 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1841         struct isl_sched_graph *src,
1842         int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1843 {
1844         int i;
1845         enum isl_edge_type t;
1846
1847         dst->n_edge = 0;
1848         for (i = 0; i < src->n_edge; ++i) {
1849                 struct isl_sched_edge *edge = &src->edge[i];
1850                 isl_map *map;
1851                 struct isl_sched_node *dst_src, *dst_dst;
1852
1853                 if (!edge_pred(edge, data))
1854                         continue;
1855
1856                 if (isl_map_plain_is_empty(edge->map))
1857                         continue;
1858
1859                 dst_src = graph_find_node(ctx, dst, edge->src->dim);
1860                 dst_dst = graph_find_node(ctx, dst, edge->dst->dim);
1861                 if (!dst_src || !dst_dst) {
1862                         if (edge->validity)
1863                                 isl_die(ctx, isl_error_internal,
1864                                         "backward validity edge", return -1);
1865                         continue;
1866                 }
1867
1868                 map = isl_map_copy(edge->map);
1869
1870                 dst->edge[dst->n_edge].src = dst_src;
1871                 dst->edge[dst->n_edge].dst = dst_dst;
1872                 dst->edge[dst->n_edge].map = map;
1873                 dst->edge[dst->n_edge].validity = edge->validity;
1874                 dst->edge[dst->n_edge].proximity = edge->proximity;
1875                 dst->n_edge++;
1876
1877                 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
1878                         if (edge !=
1879                             graph_find_edge(src, t, edge->src, edge->dst))
1880                                 continue;
1881                         if (graph_edge_table_add(ctx, dst, t,
1882                                             &dst->edge[dst->n_edge - 1]) < 0)
1883                                 return -1;
1884                 }
1885         }
1886
1887         return 0;
1888 }
1889
1890 /* Given a "src" dependence graph that contains the nodes from "dst"
1891  * that satisfy node_pred, copy the schedule computed in "src"
1892  * for those nodes back to "dst".
1893  */
1894 static int copy_schedule(struct isl_sched_graph *dst,
1895         struct isl_sched_graph *src,
1896         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1897 {
1898         int i;
1899
1900         src->n = 0;
1901         for (i = 0; i < dst->n; ++i) {
1902                 if (!node_pred(&dst->node[i], data))
1903                         continue;
1904                 isl_mat_free(dst->node[i].sched);
1905                 isl_map_free(dst->node[i].sched_map);
1906                 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1907                 dst->node[i].sched_map =
1908                         isl_map_copy(src->node[src->n].sched_map);
1909                 src->n++;
1910         }
1911
1912         dst->max_row = src->max_row;
1913         dst->n_total_row = src->n_total_row;
1914         dst->n_band = src->n_band;
1915
1916         return 0;
1917 }
1918
1919 /* Compute the maximal number of variables over all nodes.
1920  * This is the maximal number of linearly independent schedule
1921  * rows that we need to compute.
1922  * Just in case we end up in a part of the dependence graph
1923  * with only lower-dimensional domains, we make sure we will
1924  * compute the required amount of extra linearly independent rows.
1925  */
1926 static int compute_maxvar(struct isl_sched_graph *graph)
1927 {
1928         int i;
1929
1930         graph->maxvar = 0;
1931         for (i = 0; i < graph->n; ++i) {
1932                 struct isl_sched_node *node = &graph->node[i];
1933                 int nvar;
1934
1935                 if (node_update_cmap(node) < 0)
1936                         return -1;
1937                 nvar = node->nvar + graph->n_row - node->rank;
1938                 if (nvar > graph->maxvar)
1939                         graph->maxvar = nvar;
1940         }
1941
1942         return 0;
1943 }
1944
1945 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1946 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1947
1948 /* Compute a schedule for a subgraph of "graph".  In particular, for
1949  * the graph composed of nodes that satisfy node_pred and edges that
1950  * that satisfy edge_pred.  The caller should precompute the number
1951  * of nodes and edges that satisfy these predicates and pass them along
1952  * as "n" and "n_edge".
1953  * If the subgraph is known to consist of a single component, then wcc should
1954  * be set and then we call compute_schedule_wcc on the constructed subgraph.
1955  * Otherwise, we call compute_schedule, which will check whether the subgraph
1956  * is connected.
1957  */
1958 static int compute_sub_schedule(isl_ctx *ctx,
1959         struct isl_sched_graph *graph, int n, int n_edge,
1960         int (*node_pred)(struct isl_sched_node *node, int data),
1961         int (*edge_pred)(struct isl_sched_edge *edge, int data),
1962         int data, int wcc)
1963 {
1964         struct isl_sched_graph split = { 0 };
1965         int t;
1966
1967         if (graph_alloc(ctx, &split, n, n_edge) < 0)
1968                 goto error;
1969         if (copy_nodes(&split, graph, node_pred, data) < 0)
1970                 goto error;
1971         if (graph_init_table(ctx, &split) < 0)
1972                 goto error;
1973         for (t = 0; t <= isl_edge_last; ++t)
1974                 split.max_edge[t] = graph->max_edge[t];
1975         if (graph_init_edge_tables(ctx, &split) < 0)
1976                 goto error;
1977         if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1978                 goto error;
1979         split.n_row = graph->n_row;
1980         split.max_row = graph->max_row;
1981         split.n_total_row = graph->n_total_row;
1982         split.n_band = graph->n_band;
1983         split.band_start = graph->band_start;
1984
1985         if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1986                 goto error;
1987         if (!wcc && compute_schedule(ctx, &split) < 0)
1988                 goto error;
1989
1990         copy_schedule(graph, &split, node_pred, data);
1991
1992         graph_free(ctx, &split);
1993         return 0;
1994 error:
1995         graph_free(ctx, &split);
1996         return -1;
1997 }
1998
1999 static int node_scc_exactly(struct isl_sched_node *node, int scc)
2000 {
2001         return node->scc == scc;
2002 }
2003
2004 static int node_scc_at_most(struct isl_sched_node *node, int scc)
2005 {
2006         return node->scc <= scc;
2007 }
2008
2009 static int node_scc_at_least(struct isl_sched_node *node, int scc)
2010 {
2011         return node->scc >= scc;
2012 }
2013
2014 static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
2015 {
2016         return edge->src->scc == scc && edge->dst->scc == scc;
2017 }
2018
2019 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
2020 {
2021         return edge->dst->scc <= scc;
2022 }
2023
2024 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
2025 {
2026         return edge->src->scc >= scc;
2027 }
2028
2029 /* Pad the schedules of all nodes with zero rows such that in the end
2030  * they all have graph->n_total_row rows.
2031  * The extra rows don't belong to any band, so they get assigned band number -1.
2032  */
2033 static int pad_schedule(struct isl_sched_graph *graph)
2034 {
2035         int i, j;
2036
2037         for (i = 0; i < graph->n; ++i) {
2038                 struct isl_sched_node *node = &graph->node[i];
2039                 int row = isl_mat_rows(node->sched);
2040                 if (graph->n_total_row > row) {
2041                         isl_map_free(node->sched_map);
2042                         node->sched_map = NULL;
2043                 }
2044                 node->sched = isl_mat_add_zero_rows(node->sched,
2045                                                     graph->n_total_row - row);
2046                 if (!node->sched)
2047                         return -1;
2048                 for (j = row; j < graph->n_total_row; ++j)
2049                         node->band[j] = -1;
2050         }
2051
2052         return 0;
2053 }
2054
2055 /* Split the current graph into two parts and compute a schedule for each
2056  * part individually.  In particular, one part consists of all SCCs up
2057  * to and including graph->src_scc, while the other part contains the other
2058  * SCCS.
2059  *
2060  * The split is enforced in the schedule by constant rows with two different
2061  * values (0 and 1).  These constant rows replace the previously computed rows
2062  * in the current band.
2063  * It would be possible to reuse them as the first rows in the next
2064  * band, but recomputing them may result in better rows as we are looking
2065  * at a smaller part of the dependence graph.
2066  * compute_split_schedule is only called when no zero-distance schedule row
2067  * could be found on the entire graph, so we wark the splitting row as
2068  * non zero-distance.
2069  *
2070  * The band_id of the second group is set to n, where n is the number
2071  * of nodes in the first group.  This ensures that the band_ids over
2072  * the two groups remain disjoint, even if either or both of the two
2073  * groups contain independent components.
2074  */
2075 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2076 {
2077         int i, j, n, e1, e2;
2078         int n_total_row, orig_total_row;
2079         int n_band, orig_band;
2080         int drop;
2081
2082         if (graph->n_total_row >= graph->max_row)
2083                 isl_die(ctx, isl_error_internal,
2084                         "too many schedule rows", return -1);
2085
2086         drop = graph->n_total_row - graph->band_start;
2087         graph->n_total_row -= drop;
2088         graph->n_row -= drop;
2089
2090         n = 0;
2091         for (i = 0; i < graph->n; ++i) {
2092                 struct isl_sched_node *node = &graph->node[i];
2093                 int row = isl_mat_rows(node->sched) - drop;
2094                 int cols = isl_mat_cols(node->sched);
2095                 int before = node->scc <= graph->src_scc;
2096
2097                 if (before)
2098                         n++;
2099
2100                 isl_map_free(node->sched_map);
2101                 node->sched_map = NULL;
2102                 node->sched = isl_mat_drop_rows(node->sched,
2103                                                 graph->band_start, drop);
2104                 node->sched = isl_mat_add_rows(node->sched, 1);
2105                 if (!node->sched)
2106                         return -1;
2107                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2108                                                      !before);
2109                 for (j = 1; j < cols; ++j)
2110                         node->sched = isl_mat_set_element_si(node->sched,
2111                                                              row, j, 0);
2112                 node->band[graph->n_total_row] = graph->n_band;
2113                 node->zero[graph->n_total_row] = 0;
2114         }
2115
2116         e1 = e2 = 0;
2117         for (i = 0; i < graph->n_edge; ++i) {
2118                 if (graph->edge[i].dst->scc <= graph->src_scc)
2119                         e1++;
2120                 if (graph->edge[i].src->scc > graph->src_scc)
2121                         e2++;
2122         }
2123
2124         graph->n_total_row++;
2125         next_band(graph);
2126
2127         for (i = 0; i < graph->n; ++i) {
2128                 struct isl_sched_node *node = &graph->node[i];
2129                 if (node->scc > graph->src_scc)
2130                         node->band_id[graph->n_band] = n;
2131         }
2132
2133         orig_total_row = graph->n_total_row;
2134         orig_band = graph->n_band;
2135         if (compute_sub_schedule(ctx, graph, n, e1,
2136                                 &node_scc_at_most, &edge_dst_scc_at_most,
2137                                 graph->src_scc, 0) < 0)
2138                 return -1;
2139         n_total_row = graph->n_total_row;
2140         graph->n_total_row = orig_total_row;
2141         n_band = graph->n_band;
2142         graph->n_band = orig_band;
2143         if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
2144                                 &node_scc_at_least, &edge_src_scc_at_least,
2145                                 graph->src_scc + 1, 0) < 0)
2146                 return -1;
2147         if (n_total_row > graph->n_total_row)
2148                 graph->n_total_row = n_total_row;
2149         if (n_band > graph->n_band)
2150                 graph->n_band = n_band;
2151
2152         return pad_schedule(graph);
2153 }
2154
2155 /* Compute the next band of the schedule after updating the dependence
2156  * relations based on the the current schedule.
2157  */
2158 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
2159 {
2160         if (update_edges(ctx, graph) < 0)
2161                 return -1;
2162         next_band(graph);
2163                 
2164         return compute_schedule(ctx, graph);
2165 }
2166
2167 /* Add constraints to graph->lp that force the dependence "map" (which
2168  * is part of the dependence relation of "edge")
2169  * to be respected and attempt to carry it, where the edge is one from
2170  * a node j to itself.  "pos" is the sequence number of the given map.
2171  * That is, add constraints that enforce
2172  *
2173  *      (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2174  *      = c_j_x (y - x) >= e_i
2175  *
2176  * for each (x,y) in R.
2177  * We obtain general constraints on coefficients (c_0, c_n, c_x)
2178  * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2179  * with each coefficient in c_j_x represented as a pair of non-negative
2180  * coefficients.
2181  */
2182 static int add_intra_constraints(struct isl_sched_graph *graph,
2183         struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2184 {
2185         unsigned total;
2186         isl_ctx *ctx = isl_map_get_ctx(map);
2187         isl_space *dim;
2188         isl_dim_map *dim_map;
2189         isl_basic_set *coef;
2190         struct isl_sched_node *node = edge->src;
2191
2192         coef = intra_coefficients(graph, map);
2193         if (!coef)
2194                 return -1;
2195
2196         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2197
2198         total = isl_basic_set_total_dim(graph->lp);
2199         dim_map = isl_dim_map_alloc(ctx, total);
2200         isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2201         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
2202                           isl_space_dim(dim, isl_dim_set), 1,
2203                           node->nvar, -1);
2204         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
2205                           isl_space_dim(dim, isl_dim_set), 1,
2206                           node->nvar, 1);
2207         graph->lp = isl_basic_set_extend_constraints(graph->lp,
2208                         coef->n_eq, coef->n_ineq);
2209         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2210                                                            coef, dim_map);
2211         isl_space_free(dim);
2212
2213         return 0;
2214 }
2215
2216 /* Add constraints to graph->lp that force the dependence "map" (which
2217  * is part of the dependence relation of "edge")
2218  * to be respected and attempt to carry it, where the edge is one from
2219  * node j to node k.  "pos" is the sequence number of the given map.
2220  * That is, add constraints that enforce
2221  *
2222  *      (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2223  *
2224  * for each (x,y) in R.
2225  * We obtain general constraints on coefficients (c_0, c_n, c_x)
2226  * of valid constraints for R and then plug in
2227  * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2228  * with each coefficient (except e_i, c_k_0 and c_j_0)
2229  * represented as a pair of non-negative coefficients.
2230  */
2231 static int add_inter_constraints(struct isl_sched_graph *graph,
2232         struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2233 {
2234         unsigned total;
2235         isl_ctx *ctx = isl_map_get_ctx(map);
2236         isl_space *dim;
2237         isl_dim_map *dim_map;
2238         isl_basic_set *coef;
2239         struct isl_sched_node *src = edge->src;
2240         struct isl_sched_node *dst = edge->dst;
2241
2242         coef = inter_coefficients(graph, map);
2243         if (!coef)
2244                 return -1;
2245
2246         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2247
2248         total = isl_basic_set_total_dim(graph->lp);
2249         dim_map = isl_dim_map_alloc(ctx, total);
2250
2251         isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2252
2253         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
2254         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
2255         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
2256         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
2257                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2258                           dst->nvar, -1);
2259         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
2260                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2261                           dst->nvar, 1);
2262
2263         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
2264         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
2265         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
2266         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
2267                           isl_space_dim(dim, isl_dim_set), 1,
2268                           src->nvar, 1);
2269         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
2270                           isl_space_dim(dim, isl_dim_set), 1,
2271                           src->nvar, -1);
2272
2273         graph->lp = isl_basic_set_extend_constraints(graph->lp,
2274                         coef->n_eq, coef->n_ineq);
2275         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2276                                                            coef, dim_map);
2277         isl_space_free(dim);
2278
2279         return 0;
2280 }
2281
2282 /* Add constraints to graph->lp that force all validity dependences
2283  * to be respected and attempt to carry them.
2284  */
2285 static int add_all_constraints(struct isl_sched_graph *graph)
2286 {
2287         int i, j;
2288         int pos;
2289
2290         pos = 0;
2291         for (i = 0; i < graph->n_edge; ++i) {
2292                 struct isl_sched_edge *edge= &graph->edge[i];
2293
2294                 if (!edge->validity)
2295                         continue;
2296
2297                 for (j = 0; j < edge->map->n; ++j) {
2298                         isl_basic_map *bmap;
2299                         isl_map *map;
2300
2301                         bmap = isl_basic_map_copy(edge->map->p[j]);
2302                         map = isl_map_from_basic_map(bmap);
2303
2304                         if (edge->src == edge->dst &&
2305                             add_intra_constraints(graph, edge, map, pos) < 0)
2306                                 return -1;
2307                         if (edge->src != edge->dst &&
2308                             add_inter_constraints(graph, edge, map, pos) < 0)
2309                                 return -1;
2310                         ++pos;
2311                 }
2312         }
2313
2314         return 0;
2315 }
2316
2317 /* Count the number of equality and inequality constraints
2318  * that will be added to the carry_lp problem.
2319  * We count each edge exactly once.
2320  */
2321 static int count_all_constraints(struct isl_sched_graph *graph,
2322         int *n_eq, int *n_ineq)
2323 {
2324         int i, j;
2325
2326         *n_eq = *n_ineq = 0;
2327         for (i = 0; i < graph->n_edge; ++i) {
2328                 struct isl_sched_edge *edge= &graph->edge[i];
2329                 for (j = 0; j < edge->map->n; ++j) {
2330                         isl_basic_map *bmap;
2331                         isl_map *map;
2332
2333                         bmap = isl_basic_map_copy(edge->map->p[j]);
2334                         map = isl_map_from_basic_map(bmap);
2335
2336                         if (count_map_constraints(graph, edge, map,
2337                                                   n_eq, n_ineq, 1) < 0)
2338                                     return -1;
2339                 }
2340         }
2341
2342         return 0;
2343 }
2344
2345 /* Construct an LP problem for finding schedule coefficients
2346  * such that the schedule carries as many dependences as possible.
2347  * In particular, for each dependence i, we bound the dependence distance
2348  * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2349  * of all e_i's.  Dependence with e_i = 0 in the solution are simply
2350  * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2351  * Note that if the dependence relation is a union of basic maps,
2352  * then we have to consider each basic map individually as it may only
2353  * be possible to carry the dependences expressed by some of those
2354  * basic maps and not all off them.
2355  * Below, we consider each of those basic maps as a separate "edge".
2356  *
2357  * All variables of the LP are non-negative.  The actual coefficients
2358  * may be negative, so each coefficient is represented as the difference
2359  * of two non-negative variables.  The negative part always appears
2360  * immediately before the positive part.
2361  * Other than that, the variables have the following order
2362  *
2363  *      - sum of (1 - e_i) over all edges
2364  *      - sum of positive and negative parts of all c_n coefficients
2365  *              (unconstrained when computing non-parametric schedules)
2366  *      - sum of positive and negative parts of all c_x coefficients
2367  *      - for each edge
2368  *              - e_i
2369  *      - for each node
2370  *              - c_i_0
2371  *              - positive and negative parts of c_i_n (if parametric)
2372  *              - positive and negative parts of c_i_x
2373  *
2374  * The constraints are those from the (validity) edges plus three equalities
2375  * to express the sums and n_edge inequalities to express e_i <= 1.
2376  */
2377 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2378 {
2379         int i, j;
2380         int k;
2381         isl_space *dim;
2382         unsigned total;
2383         int n_eq, n_ineq;
2384         int n_edge;
2385
2386         n_edge = 0;
2387         for (i = 0; i < graph->n_edge; ++i)
2388                 n_edge += graph->edge[i].map->n;
2389
2390         total = 3 + n_edge;
2391         for (i = 0; i < graph->n; ++i) {
2392                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2393                 node->start = total;
2394                 total += 1 + 2 * (node->nparam + node->nvar);
2395         }
2396
2397         if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
2398                 return -1;
2399
2400         dim = isl_space_set_alloc(ctx, 0, total);
2401         isl_basic_set_free(graph->lp);
2402         n_eq += 3;
2403         n_ineq += n_edge;
2404         graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2405         graph->lp = isl_basic_set_set_rational(graph->lp);
2406
2407         k = isl_basic_set_alloc_equality(graph->lp);
2408         if (k < 0)
2409                 return -1;
2410         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2411         isl_int_set_si(graph->lp->eq[k][0], -n_edge);
2412         isl_int_set_si(graph->lp->eq[k][1], 1);
2413         for (i = 0; i < n_edge; ++i)
2414                 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2415
2416         k = isl_basic_set_alloc_equality(graph->lp);
2417         if (k < 0)
2418                 return -1;
2419         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2420         isl_int_set_si(graph->lp->eq[k][2], -1);
2421         for (i = 0; i < graph->n; ++i) {
2422                 int pos = 1 + graph->node[i].start + 1;
2423
2424                 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2425                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2426         }
2427
2428         k = isl_basic_set_alloc_equality(graph->lp);
2429         if (k < 0)
2430                 return -1;
2431         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2432         isl_int_set_si(graph->lp->eq[k][3], -1);
2433         for (i = 0; i < graph->n; ++i) {
2434                 struct isl_sched_node *node = &graph->node[i];
2435                 int pos = 1 + node->start + 1 + 2 * node->nparam;
2436
2437                 for (j = 0; j < 2 * node->nvar; ++j)
2438                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2439         }
2440
2441         for (i = 0; i < n_edge; ++i) {
2442                 k = isl_basic_set_alloc_inequality(graph->lp);
2443                 if (k < 0)
2444                         return -1;
2445                 isl_seq_clr(graph->lp->ineq[k], 1 +  total);
2446                 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2447                 isl_int_set_si(graph->lp->ineq[k][0], 1);
2448         }
2449
2450         if (add_all_constraints(graph) < 0)
2451                 return -1;
2452
2453         return 0;
2454 }
2455
2456 /* If the schedule_split_scaled option is set and if the linear
2457  * parts of the scheduling rows for all nodes in the graphs have
2458  * non-trivial common divisor, then split off the constant term
2459  * from the linear part.
2460  * The constant term is then placed in a separate band and
2461  * the linear part is reduced.
2462  */
2463 static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph)
2464 {
2465         int i;
2466         int row;
2467         isl_int gcd, gcd_i;
2468
2469         if (!ctx->opt->schedule_split_scaled)
2470                 return 0;
2471         if (graph->n <= 1)
2472                 return 0;
2473
2474         if (graph->n_total_row >= graph->max_row)
2475                 isl_die(ctx, isl_error_internal,
2476                         "too many schedule rows", return -1);
2477
2478         isl_int_init(gcd);
2479         isl_int_init(gcd_i);
2480
2481         isl_int_set_si(gcd, 0);
2482
2483         row = isl_mat_rows(graph->node[0].sched) - 1;
2484
2485         for (i = 0; i < graph->n; ++i) {
2486                 struct isl_sched_node *node = &graph->node[i];
2487                 int cols = isl_mat_cols(node->sched);
2488
2489                 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
2490                 isl_int_gcd(gcd, gcd, gcd_i);
2491         }
2492
2493         isl_int_clear(gcd_i);
2494
2495         if (isl_int_cmp_si(gcd, 1) <= 0) {
2496                 isl_int_clear(gcd);
2497                 return 0;
2498         }
2499
2500         next_band(graph);
2501
2502         for (i = 0; i < graph->n; ++i) {
2503                 struct isl_sched_node *node = &graph->node[i];
2504
2505                 isl_map_free(node->sched_map);
2506                 node->sched_map = NULL;
2507                 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2508                 if (!node->sched)
2509                         goto error;
2510                 isl_int_fdiv_r(node->sched->row[row + 1][0],
2511                                node->sched->row[row][0], gcd);
2512                 isl_int_fdiv_q(node->sched->row[row][0],
2513                                node->sched->row[row][0], gcd);
2514                 isl_int_mul(node->sched->row[row][0],
2515                             node->sched->row[row][0], gcd);
2516                 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
2517                 if (!node->sched)
2518                         goto error;
2519                 node->band[graph->n_total_row] = graph->n_band;
2520         }
2521
2522         graph->n_total_row++;
2523
2524         isl_int_clear(gcd);
2525         return 0;
2526 error:
2527         isl_int_clear(gcd);
2528         return -1;
2529 }
2530
2531 static int compute_component_schedule(isl_ctx *ctx,
2532         struct isl_sched_graph *graph);
2533
2534 /* Is the schedule row "sol" trivial on node "node"?
2535  * That is, is the solution zero on the dimensions orthogonal to
2536  * the previously found solutions?
2537  * Each coefficient is represented as the difference between
2538  * two non-negative values in "sol".  The coefficient is then
2539  * zero if those two values are equal to each other.
2540  */
2541 static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
2542 {
2543         int i;
2544         int pos;
2545         int len;
2546
2547         pos = 1 + node->start + 1 + 2 * (node->nparam + node->rank);
2548         len = 2 * (node->nvar - node->rank);
2549
2550         if (len == 0)
2551                 return 0;
2552
2553         for (i = 0; i < len; i += 2)
2554                 if (isl_int_ne(sol->el[pos + i], sol->el[pos + i + 1]))
2555                         return 0;
2556
2557         return 1;
2558 }
2559
2560 /* Is the schedule row "sol" trivial on any node where it should
2561  * not be trivial?
2562  */
2563 static int is_any_trivial(struct isl_sched_graph *graph,
2564         __isl_keep isl_vec *sol)
2565 {
2566         int i;
2567
2568         for (i = 0; i < graph->n; ++i) {
2569                 struct isl_sched_node *node = &graph->node[i];
2570
2571                 if (!needs_row(graph, node))
2572                         continue;
2573                 if (is_trivial(node, sol))
2574                         return 1;
2575         }
2576
2577         return 0;
2578 }
2579
2580 /* Construct a schedule row for each node such that as many dependences
2581  * as possible are carried and then continue with the next band.
2582  *
2583  * If the computed schedule row turns out to be trivial on one or
2584  * more nodes where it should not be trivial, then we throw it away
2585  * and try again on each component separately.
2586  */
2587 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2588 {
2589         int i;
2590         int n_edge;
2591         isl_vec *sol;
2592         isl_basic_set *lp;
2593
2594         n_edge = 0;
2595         for (i = 0; i < graph->n_edge; ++i)
2596                 n_edge += graph->edge[i].map->n;
2597
2598         if (setup_carry_lp(ctx, graph) < 0)
2599                 return -1;
2600
2601         lp = isl_basic_set_copy(graph->lp);
2602         sol = isl_tab_basic_set_non_neg_lexmin(lp);
2603         if (!sol)
2604                 return -1;
2605
2606         if (sol->size == 0) {
2607                 isl_vec_free(sol);
2608                 isl_die(ctx, isl_error_internal,
2609                         "error in schedule construction", return -1);
2610         }
2611
2612         isl_int_divexact(sol->el[1], sol->el[1], sol->el[0]);
2613         if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
2614                 isl_vec_free(sol);
2615                 isl_die(ctx, isl_error_unknown,
2616                         "unable to carry dependences", return -1);
2617         }
2618
2619         if (is_any_trivial(graph, sol)) {
2620                 isl_vec_free(sol);
2621                 if (graph->scc > 1)
2622                         return compute_component_schedule(ctx, graph);
2623                 isl_die(ctx, isl_error_unknown,
2624                         "unable to construct non-trivial solution", return -1);
2625         }
2626
2627         if (update_schedule(graph, sol, 0, 0) < 0)
2628                 return -1;
2629
2630         if (split_scaled(ctx, graph) < 0)
2631                 return -1;
2632
2633         return compute_next_band(ctx, graph);
2634 }
2635
2636 /* Are there any (non-empty) validity edges in the graph?
2637  */
2638 static int has_validity_edges(struct isl_sched_graph *graph)
2639 {
2640         int i;
2641
2642         for (i = 0; i < graph->n_edge; ++i) {
2643                 int empty;
2644
2645                 empty = isl_map_plain_is_empty(graph->edge[i].map);
2646                 if (empty < 0)
2647                         return -1;
2648                 if (empty)
2649                         continue;
2650                 if (graph->edge[i].validity)
2651                         return 1;
2652         }
2653
2654         return 0;
2655 }
2656
2657 /* Should we apply a Feautrier step?
2658  * That is, did the user request the Feautrier algorithm and are
2659  * there any validity dependences (left)?
2660  */
2661 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
2662 {
2663         if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
2664                 return 0;
2665
2666         return has_validity_edges(graph);
2667 }
2668
2669 /* Compute a schedule for a connected dependence graph using Feautrier's
2670  * multi-dimensional scheduling algorithm.
2671  * The original algorithm is described in [1].
2672  * The main idea is to minimize the number of scheduling dimensions, by
2673  * trying to satisfy as many dependences as possible per scheduling dimension.
2674  *
2675  * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2676  *     Problem, Part II: Multi-Dimensional Time.
2677  *     In Intl. Journal of Parallel Programming, 1992.
2678  */
2679 static int compute_schedule_wcc_feautrier(isl_ctx *ctx,
2680         struct isl_sched_graph *graph)
2681 {
2682         return carry_dependences(ctx, graph);
2683 }
2684
2685 /* Compute a schedule for a connected dependence graph.
2686  * We try to find a sequence of as many schedule rows as possible that result
2687  * in non-negative dependence distances (independent of the previous rows
2688  * in the sequence, i.e., such that the sequence is tilable).
2689  * If we can't find any more rows we either
2690  * - split between SCCs and start over (assuming we found an interesting
2691  *      pair of SCCs between which to split)
2692  * - continue with the next band (assuming the current band has at least
2693  *      one row)
2694  * - try to carry as many dependences as possible and continue with the next
2695  *      band
2696  *
2697  * If Feautrier's algorithm is selected, we first recursively try to satisfy
2698  * as many validity dependences as possible. When all validity dependences
2699  * are satisfied we extend the schedule to a full-dimensional schedule.
2700  *
2701  * If we manage to complete the schedule, we finish off by topologically
2702  * sorting the statements based on the remaining dependences.
2703  *
2704  * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2705  * outermost dimension in the current band to be zero distance.  If this
2706  * turns out to be impossible, we fall back on the general scheme above
2707  * and try to carry as many dependences as possible.
2708  */
2709 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2710 {
2711         int force_zero = 0;
2712
2713         if (detect_sccs(ctx, graph) < 0)
2714                 return -1;
2715         if (sort_sccs(graph) < 0)
2716                 return -1;
2717
2718         if (compute_maxvar(graph) < 0)
2719                 return -1;
2720
2721         if (need_feautrier_step(ctx, graph))
2722                 return compute_schedule_wcc_feautrier(ctx, graph);
2723
2724         if (ctx->opt->schedule_outer_zero_distance)
2725                 force_zero = 1;
2726
2727         while (graph->n_row < graph->maxvar) {
2728                 isl_vec *sol;
2729
2730                 graph->src_scc = -1;
2731                 graph->dst_scc = -1;
2732
2733                 if (setup_lp(ctx, graph, force_zero) < 0)
2734                         return -1;
2735                 sol = solve_lp(graph);
2736                 if (!sol)
2737                         return -1;
2738                 if (sol->size == 0) {
2739                         isl_vec_free(sol);
2740                         if (!ctx->opt->schedule_maximize_band_depth &&
2741                             graph->n_total_row > graph->band_start)
2742                                 return compute_next_band(ctx, graph);
2743                         if (graph->src_scc >= 0)
2744                                 return compute_split_schedule(ctx, graph);
2745                         if (graph->n_total_row > graph->band_start)
2746                                 return compute_next_band(ctx, graph);
2747                         return carry_dependences(ctx, graph);
2748                 }
2749                 if (update_schedule(graph, sol, 1, 1) < 0)
2750                         return -1;
2751                 force_zero = 0;
2752         }
2753
2754         if (graph->n_total_row > graph->band_start)
2755                 next_band(graph);
2756         return sort_statements(ctx, graph);
2757 }
2758
2759 /* Add a row to the schedules that separates the SCCs and move
2760  * to the next band.
2761  */
2762 static int split_on_scc(isl_ctx *ctx, struct isl_sched_graph *graph)
2763 {
2764         int i;
2765
2766         if (graph->n_total_row >= graph->max_row)
2767                 isl_die(ctx, isl_error_internal,
2768                         "too many schedule rows", return -1);
2769
2770         for (i = 0; i < graph->n; ++i) {
2771                 struct isl_sched_node *node = &graph->node[i];
2772                 int row = isl_mat_rows(node->sched);
2773
2774                 isl_map_free(node->sched_map);
2775                 node->sched_map = NULL;
2776                 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2777                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2778                                                      node->scc);
2779                 if (!node->sched)
2780                         return -1;
2781                 node->band[graph->n_total_row] = graph->n_band;
2782         }
2783
2784         graph->n_total_row++;
2785         next_band(graph);
2786
2787         return 0;
2788 }
2789
2790 /* Compute a schedule for each component (identified by node->scc)
2791  * of the dependence graph separately and then combine the results.
2792  * Depending on the setting of schedule_fuse, a component may be
2793  * either weakly or strongly connected.
2794  *
2795  * The band_id is adjusted such that each component has a separate id.
2796  * Note that the band_id may have already been set to a value different
2797  * from zero by compute_split_schedule.
2798  */
2799 static int compute_component_schedule(isl_ctx *ctx,
2800         struct isl_sched_graph *graph)
2801 {
2802         int wcc, i;
2803         int n, n_edge;
2804         int n_total_row, orig_total_row;
2805         int n_band, orig_band;
2806
2807         if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN ||
2808             ctx->opt->schedule_separate_components)
2809                 if (split_on_scc(ctx, graph) < 0)
2810                         return -1;
2811
2812         n_total_row = 0;
2813         orig_total_row = graph->n_total_row;
2814         n_band = 0;
2815         orig_band = graph->n_band;
2816         for (i = 0; i < graph->n; ++i)
2817                 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2818         for (wcc = 0; wcc < graph->scc; ++wcc) {
2819                 n = 0;
2820                 for (i = 0; i < graph->n; ++i)
2821                         if (graph->node[i].scc == wcc)
2822                                 n++;
2823                 n_edge = 0;
2824                 for (i = 0; i < graph->n_edge; ++i)
2825                         if (graph->edge[i].src->scc == wcc &&
2826                             graph->edge[i].dst->scc == wcc)
2827                                 n_edge++;
2828
2829                 if (compute_sub_schedule(ctx, graph, n, n_edge,
2830                                     &node_scc_exactly,
2831                                     &edge_scc_exactly, wcc, 1) < 0)
2832                         return -1;
2833                 if (graph->n_total_row > n_total_row)
2834                         n_total_row = graph->n_total_row;
2835                 graph->n_total_row = orig_total_row;
2836                 if (graph->n_band > n_band)
2837                         n_band = graph->n_band;
2838                 graph->n_band = orig_band;
2839         }
2840
2841         graph->n_total_row = n_total_row;
2842         graph->n_band = n_band;
2843
2844         return pad_schedule(graph);
2845 }
2846
2847 /* Compute a schedule for the given dependence graph.
2848  * We first check if the graph is connected (through validity dependences)
2849  * and, if not, compute a schedule for each component separately.
2850  * If schedule_fuse is set to minimal fusion, then we check for strongly
2851  * connected components instead and compute a separate schedule for
2852  * each such strongly connected component.
2853  */
2854 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2855 {
2856         if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) {
2857                 if (detect_sccs(ctx, graph) < 0)
2858                         return -1;
2859         } else {
2860                 if (detect_wccs(ctx, graph) < 0)
2861                         return -1;
2862         }
2863
2864         if (graph->scc > 1)
2865                 return compute_component_schedule(ctx, graph);
2866
2867         return compute_schedule_wcc(ctx, graph);
2868 }
2869
2870 /* Compute a schedule for the given union of domains that respects
2871  * all the validity dependences.
2872  * If the default isl scheduling algorithm is used, it tries to minimize
2873  * the dependence distances over the proximity dependences.
2874  * If Feautrier's scheduling algorithm is used, the proximity dependence
2875  * distances are only minimized during the extension to a full-dimensional
2876  * schedule.
2877  */
2878 __isl_give isl_schedule *isl_union_set_compute_schedule(
2879         __isl_take isl_union_set *domain,
2880         __isl_take isl_union_map *validity,
2881         __isl_take isl_union_map *proximity)
2882 {
2883         isl_ctx *ctx = isl_union_set_get_ctx(domain);
2884         isl_space *dim;
2885         struct isl_sched_graph graph = { 0 };
2886         isl_schedule *sched;
2887         struct isl_extract_edge_data data;
2888
2889         domain = isl_union_set_align_params(domain,
2890                                             isl_union_map_get_space(validity));
2891         domain = isl_union_set_align_params(domain,
2892                                             isl_union_map_get_space(proximity));
2893         dim = isl_union_set_get_space(domain);
2894         validity = isl_union_map_align_params(validity, isl_space_copy(dim));
2895         proximity = isl_union_map_align_params(proximity, dim);
2896
2897         if (!domain)
2898                 goto error;
2899
2900         graph.n = isl_union_set_n_set(domain);
2901         if (graph.n == 0)
2902                 goto empty;
2903         if (graph_alloc(ctx, &graph, graph.n,
2904             isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2905                 goto error;
2906         if (compute_max_row(&graph, domain) < 0)
2907                 goto error;
2908         graph.root = 1;
2909         graph.n = 0;
2910         if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2911                 goto error;
2912         if (graph_init_table(ctx, &graph) < 0)
2913                 goto error;
2914         graph.max_edge[isl_edge_validity] = isl_union_map_n_map(validity);
2915         graph.max_edge[isl_edge_proximity] = isl_union_map_n_map(proximity);
2916         if (graph_init_edge_tables(ctx, &graph) < 0)
2917                 goto error;
2918         graph.n_edge = 0;
2919         data.graph = &graph;
2920         data.type = isl_edge_validity;
2921         if (isl_union_map_foreach_map(validity, &extract_edge, &data) < 0)
2922                 goto error;
2923         data.type = isl_edge_proximity;
2924         if (isl_union_map_foreach_map(proximity, &extract_edge, &data) < 0)
2925                 goto error;
2926
2927         if (compute_schedule(ctx, &graph) < 0)
2928                 goto error;
2929
2930 empty:
2931         sched = extract_schedule(&graph, isl_union_set_get_space(domain));
2932
2933         graph_free(ctx, &graph);
2934         isl_union_set_free(domain);
2935         isl_union_map_free(validity);
2936         isl_union_map_free(proximity);
2937
2938         return sched;
2939 error:
2940         graph_free(ctx, &graph);
2941         isl_union_set_free(domain);
2942         isl_union_map_free(validity);
2943         isl_union_map_free(proximity);
2944         return NULL;
2945 }
2946
2947 void *isl_schedule_free(__isl_take isl_schedule *sched)
2948 {
2949         int i;
2950         if (!sched)
2951                 return NULL;
2952
2953         if (--sched->ref > 0)
2954                 return NULL;
2955
2956         for (i = 0; i < sched->n; ++i) {
2957                 isl_multi_aff_free(sched->node[i].sched);
2958                 free(sched->node[i].band_end);
2959                 free(sched->node[i].band_id);
2960                 free(sched->node[i].zero);
2961         }
2962         isl_space_free(sched->dim);
2963         isl_band_list_free(sched->band_forest);
2964         free(sched);
2965         return NULL;
2966 }
2967
2968 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2969 {
2970         return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
2971 }
2972
2973 /* Set max_out to the maximal number of output dimensions over
2974  * all maps.
2975  */
2976 static int update_max_out(__isl_take isl_map *map, void *user)
2977 {
2978         int *max_out = user;
2979         int n_out = isl_map_dim(map, isl_dim_out);
2980
2981         if (n_out > *max_out)
2982                 *max_out = n_out;
2983
2984         isl_map_free(map);
2985         return 0;
2986 }
2987
2988 /* Internal data structure for map_pad_range.
2989  *
2990  * "max_out" is the maximal schedule dimension.
2991  * "res" collects the results.
2992  */
2993 struct isl_pad_schedule_map_data {
2994         int max_out;
2995         isl_union_map *res;
2996 };
2997
2998 /* Pad the range of the given map with zeros to data->max_out and
2999  * then add the result to data->res.
3000  */
3001 static int map_pad_range(__isl_take isl_map *map, void *user)
3002 {
3003         struct isl_pad_schedule_map_data *data = user;
3004         int i;
3005         int n_out = isl_map_dim(map, isl_dim_out);
3006
3007         map = isl_map_add_dims(map, isl_dim_out, data->max_out - n_out);
3008         for (i = n_out; i < data->max_out; ++i)
3009                 map = isl_map_fix_si(map, isl_dim_out, i, 0);
3010
3011         data->res = isl_union_map_add_map(data->res, map);
3012         if (!data->res)
3013                 return -1;
3014
3015         return 0;
3016 }
3017
3018 /* Pad the ranges of the maps in the union map with zeros such they all have
3019  * the same dimension.
3020  */
3021 static __isl_give isl_union_map *pad_schedule_map(
3022         __isl_take isl_union_map *umap)
3023 {
3024         struct isl_pad_schedule_map_data data;
3025
3026         if (!umap)
3027                 return NULL;
3028         if (isl_union_map_n_map(umap) <= 1)
3029                 return umap;
3030
3031         data.max_out = 0;
3032         if (isl_union_map_foreach_map(umap, &update_max_out, &data.max_out) < 0)
3033                 return isl_union_map_free(umap);
3034
3035         data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3036         if (isl_union_map_foreach_map(umap, &map_pad_range, &data) < 0)
3037                 data.res = isl_union_map_free(data.res);
3038
3039         isl_union_map_free(umap);
3040         return data.res;
3041 }
3042
3043 /* Return an isl_union_map of the schedule.  If we have already constructed
3044  * a band forest, then this band forest may have been modified so we need
3045  * to extract the isl_union_map from the forest rather than from
3046  * the originally computed schedule.  This reconstructed schedule map
3047  * then needs to be padded with zeros to unify the schedule space
3048  * since the result of isl_band_list_get_suffix_schedule may not have
3049  * a unified schedule space.
3050  */
3051 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
3052 {
3053         int i;
3054         isl_union_map *umap;
3055
3056         if (!sched)
3057                 return NULL;
3058
3059         if (sched->band_forest) {
3060                 umap = isl_band_list_get_suffix_schedule(sched->band_forest);
3061                 return pad_schedule_map(umap);
3062         }
3063
3064         umap = isl_union_map_empty(isl_space_copy(sched->dim));
3065         for (i = 0; i < sched->n; ++i) {
3066                 isl_multi_aff *ma;
3067
3068                 ma = isl_multi_aff_copy(sched->node[i].sched);
3069                 umap = isl_union_map_add_map(umap, isl_map_from_multi_aff(ma));
3070         }
3071
3072         return umap;
3073 }
3074
3075 static __isl_give isl_band_list *construct_band_list(
3076         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
3077         int band_nr, int *parent_active, int n_active);
3078
3079 /* Construct an isl_band structure for the band in the given schedule
3080  * with sequence number band_nr for the n_active nodes marked by active.
3081  * If the nodes don't have a band with the given sequence number,
3082  * then a band without members is created.
3083  *
3084  * Because of the way the schedule is constructed, we know that
3085  * the position of the band inside the schedule of a node is the same
3086  * for all active nodes.
3087  */
3088 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
3089         __isl_keep isl_band *parent,
3090         int band_nr, int *active, int n_active)
3091 {
3092         int i, j;
3093         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
3094         isl_band *band;
3095         unsigned start, end;
3096
3097         band = isl_band_alloc(ctx);
3098         if (!band)
3099                 return NULL;
3100
3101         band->schedule = schedule;
3102         band->parent = parent;
3103
3104         for (i = 0; i < schedule->n; ++i)
3105                 if (active[i] && schedule->node[i].n_band > band_nr + 1)
3106                         break;
3107
3108         if (i < schedule->n) {
3109                 band->children = construct_band_list(schedule, band,
3110                                                 band_nr + 1, active, n_active);
3111                 if (!band->children)
3112                         goto error;
3113         }
3114
3115         for (i = 0; i < schedule->n; ++i)
3116                 if (active[i])
3117                         break;
3118
3119         if (i >= schedule->n)
3120                 isl_die(ctx, isl_error_internal,
3121                         "band without active statements", goto error);
3122
3123         start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
3124         end = band_nr < schedule->node[i].n_band ?
3125                 schedule->node[i].band_end[band_nr] : start;
3126         band->n = end - start;
3127
3128         band->zero = isl_alloc_array(ctx, int, band->n);
3129         if (!band->zero)
3130                 goto error;
3131
3132         for (j = 0; j < band->n; ++j)
3133                 band->zero[j] = schedule->node[i].zero[start + j];
3134
3135         band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
3136         for (i = 0; i < schedule->n; ++i) {
3137                 isl_multi_aff *ma;
3138                 isl_pw_multi_aff *pma;
3139                 unsigned n_out;
3140
3141                 if (!active[i])
3142                         continue;
3143
3144                 ma = isl_multi_aff_copy(schedule->node[i].sched);
3145                 n_out = isl_multi_aff_dim(ma, isl_dim_out);
3146                 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end);
3147                 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start);
3148                 pma = isl_pw_multi_aff_from_multi_aff(ma);
3149                 band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma,
3150                                                                     pma);
3151         }
3152         if (!band->pma)
3153                 goto error;
3154
3155         return band;
3156 error:
3157         isl_band_free(band);
3158         return NULL;
3159 }
3160
3161 /* Construct a list of bands that start at the same position (with
3162  * sequence number band_nr) in the schedules of the nodes that
3163  * were active in the parent band.
3164  *
3165  * A separate isl_band structure is created for each band_id
3166  * and for each node that does not have a band with sequence
3167  * number band_nr.  In the latter case, a band without members
3168  * is created.
3169  * This ensures that if a band has any children, then each node
3170  * that was active in the band is active in exactly one of the children.
3171  */
3172 static __isl_give isl_band_list *construct_band_list(
3173         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
3174         int band_nr, int *parent_active, int n_active)
3175 {
3176         int i, j;
3177         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
3178         int *active;
3179         int n_band;
3180         isl_band_list *list;
3181
3182         n_band = 0;
3183         for (i = 0; i < n_active; ++i) {
3184                 for (j = 0; j < schedule->n; ++j) {
3185                         if (!parent_active[j])
3186                                 continue;
3187                         if (schedule->node[j].n_band <= band_nr)
3188                                 continue;
3189                         if (schedule->node[j].band_id[band_nr] == i) {
3190                                 n_band++;
3191                                 break;
3192                         }
3193                 }
3194         }
3195         for (j = 0; j < schedule->n; ++j)
3196                 if (schedule->node[j].n_band <= band_nr)
3197                         n_band++;
3198
3199         if (n_band == 1) {
3200                 isl_band *band;
3201                 list = isl_band_list_alloc(ctx, n_band);
3202                 band = construct_band(schedule, parent, band_nr,
3203                                         parent_active, n_active);
3204                 return isl_band_list_add(list, band);
3205         }
3206
3207         active = isl_alloc_array(ctx, int, schedule->n);
3208         if (!active)
3209                 return NULL;
3210
3211         list = isl_band_list_alloc(ctx, n_band);
3212
3213         for (i = 0; i < n_active; ++i) {
3214                 int n = 0;
3215                 isl_band *band;
3216
3217                 for (j = 0; j < schedule->n; ++j) {
3218                         active[j] = parent_active[j] &&
3219                                         schedule->node[j].n_band > band_nr &&
3220                                         schedule->node[j].band_id[band_nr] == i;
3221                         if (active[j])
3222                                 n++;
3223                 }
3224                 if (n == 0)
3225                         continue;
3226
3227                 band = construct_band(schedule, parent, band_nr, active, n);
3228
3229                 list = isl_band_list_add(list, band);
3230         }
3231         for (i = 0; i < schedule->n; ++i) {
3232                 isl_band *band;
3233                 if (!parent_active[i])
3234                         continue;
3235                 if (schedule->node[i].n_band > band_nr)
3236                         continue;
3237                 for (j = 0; j < schedule->n; ++j)
3238                         active[j] = j == i;
3239                 band = construct_band(schedule, parent, band_nr, active, 1);
3240                 list = isl_band_list_add(list, band);
3241         }
3242
3243         free(active);
3244
3245         return list;
3246 }
3247
3248 /* Construct a band forest representation of the schedule and
3249  * return the list of roots.
3250  */
3251 static __isl_give isl_band_list *construct_forest(
3252         __isl_keep isl_schedule *schedule)
3253 {
3254         int i;
3255         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
3256         isl_band_list *forest;
3257         int *active;
3258
3259         active = isl_alloc_array(ctx, int, schedule->n);
3260         if (!active)
3261                 return NULL;
3262
3263         for (i = 0; i < schedule->n; ++i)
3264                 active[i] = 1;
3265
3266         forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
3267
3268         free(active);
3269
3270         return forest;
3271 }
3272
3273 /* Return the roots of a band forest representation of the schedule.
3274  */
3275 __isl_give isl_band_list *isl_schedule_get_band_forest(
3276         __isl_keep isl_schedule *schedule)
3277 {
3278         if (!schedule)
3279                 return NULL;
3280         if (!schedule->band_forest)
3281                 schedule->band_forest = construct_forest(schedule);
3282         return isl_band_list_dup(schedule->band_forest);
3283 }
3284
3285 /* Call "fn" on each band in the schedule in depth-first post-order.
3286  */
3287 int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
3288         int (*fn)(__isl_keep isl_band *band, void *user), void *user)
3289 {
3290         int r;
3291         isl_band_list *forest;
3292
3293         if (!sched)
3294                 return -1;
3295
3296         forest = isl_schedule_get_band_forest(sched);
3297         r = isl_band_list_foreach_band(forest, fn, user);
3298         isl_band_list_free(forest);
3299
3300         return r;
3301 }
3302
3303 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
3304         __isl_keep isl_band_list *list);
3305
3306 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
3307         __isl_keep isl_band *band)
3308 {
3309         isl_band_list *children;
3310
3311         p = isl_printer_start_line(p);
3312         p = isl_printer_print_union_pw_multi_aff(p, band->pma);
3313         p = isl_printer_end_line(p);
3314
3315         if (!isl_band_has_children(band))
3316                 return p;
3317
3318         children = isl_band_get_children(band);
3319
3320         p = isl_printer_indent(p, 4);
3321         p = print_band_list(p, children);
3322         p = isl_printer_indent(p, -4);
3323
3324         isl_band_list_free(children);
3325
3326         return p;
3327 }
3328
3329 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
3330         __isl_keep isl_band_list *list)
3331 {
3332         int i, n;
3333
3334         n = isl_band_list_n_band(list);
3335         for (i = 0; i < n; ++i) {
3336                 isl_band *band;
3337                 band = isl_band_list_get_band(list, i);
3338                 p = print_band(p, band);
3339                 isl_band_free(band);
3340         }
3341
3342         return p;
3343 }
3344
3345 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
3346         __isl_keep isl_schedule *schedule)
3347 {
3348         isl_band_list *forest;
3349
3350         forest = isl_schedule_get_band_forest(schedule);
3351
3352         p = print_band_list(p, forest);
3353
3354         isl_band_list_free(forest);
3355
3356         return p;
3357 }
3358
3359 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
3360 {
3361         isl_printer *printer;
3362
3363         if (!schedule)
3364                 return;
3365
3366         printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
3367         printer = isl_printer_print_schedule(printer, schedule);
3368
3369         isl_printer_free(printer);
3370 }