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