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