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