Merge branch 'maint'
[isl.git] / isl_schedule.c
bloba5df67fb1309711c262a8ae0517eb10cdcb2526f
1 /*
2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
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 */
11 #include <isl_ctx_private.h>
12 #include <isl_map_private.h>
13 #include <isl_dim_private.h>
14 #include <isl/hash.h>
15 #include <isl/constraint.h>
16 #include <isl/schedule.h>
17 #include <isl_mat_private.h>
18 #include <isl/set.h>
19 #include <isl/seq.h>
20 #include <isl_tab.h>
21 #include <isl_dim_map.h>
22 #include <isl_hmap_map_basic_set.h>
23 #include <isl_qsort.h>
24 #include <isl_schedule_private.h>
25 #include <isl_band_private.h>
28 * The scheduling algorithm implemented in this file was inspired by
29 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
30 * Parallelization and Locality Optimization in the Polyhedral Model".
34 /* Internal information about a node that is used during the construction
35 * of a schedule.
36 * dim represents the space in which the domain lives
37 * sched is a matrix representation of the schedule being constructed
38 * for this node
39 * sched_map is an isl_map representation of the same (partial) schedule
40 * sched_map may be NULL
41 * rank is the number of linearly independent rows in the linear part
42 * of sched
43 * the columns of cmap represent a change of basis for the schedule
44 * coefficients; the first rank columns span the linear part of
45 * the schedule rows
46 * start is the first variable in the LP problem in the sequences that
47 * represents the schedule coefficients of this node
48 * nvar is the dimension of the domain
49 * nparam is the number of parameters or 0 if we are not constructing
50 * a parametric schedule
52 * scc is the index of SCC (or WCC) this node belongs to
54 * band contains the band index for each of the rows of the schedule.
55 * band_id is used to differentiate between separate bands at the same
56 * level within the same parent band, i.e., bands that are separated
57 * by the parent band or bands that are independent of each other.
58 * zero contains a boolean for each of the rows of the schedule,
59 * indicating whether the corresponding scheduling dimension results
60 * in zero dependence distances within its band and with respect
61 * to the proximity edges.
63 * index, min_index and on_stack are used during the SCC detection
64 * index represents the order in which nodes are visited.
65 * min_index is the index of the root of a (sub)component.
66 * on_stack indicates whether the node is currently on the stack.
68 struct isl_sched_node {
69 isl_dim *dim;
70 isl_mat *sched;
71 isl_map *sched_map;
72 int rank;
73 isl_mat *cmap;
74 int start;
75 int nvar;
76 int nparam;
78 int scc;
80 int *band;
81 int *band_id;
82 int *zero;
84 /* scc detection */
85 int index;
86 int min_index;
87 int on_stack;
90 static int node_has_dim(const void *entry, const void *val)
92 struct isl_sched_node *node = (struct isl_sched_node *)entry;
93 isl_dim *dim = (isl_dim *)val;
95 return isl_dim_equal(node->dim, dim);
98 /* An edge in the dependence graph. An edge may be used to
99 * ensure validity of the generated schedule, to minimize the dependence
100 * distance or both
102 * map is the dependence relation
103 * src is the source node
104 * dst is the sink node
105 * validity is set if the edge is used to ensure correctness
106 * proximity is set if the edge is used to minimize dependence distances
108 * For validity edges, start and end mark the sequence of inequality
109 * constraints in the LP problem that encode the validity constraint
110 * corresponding to this edge.
112 struct isl_sched_edge {
113 isl_map *map;
115 struct isl_sched_node *src;
116 struct isl_sched_node *dst;
118 int validity;
119 int proximity;
121 int start;
122 int end;
125 /* Internal information about the dependence graph used during
126 * the construction of the schedule.
128 * intra_hmap is a cache, mapping dependence relations to their dual,
129 * for dependences from a node to itself
130 * inter_hmap is a cache, mapping dependence relations to their dual,
131 * for dependences between distinct nodes
133 * n is the number of nodes
134 * node is the list of nodes
135 * maxvar is the maximal number of variables over all nodes
136 * n_row is the current (maximal) number of linearly independent
137 * rows in the node schedules
138 * n_total_row is the current number of rows in the node schedules
139 * n_band is the current number of completed bands
140 * band_start is the starting row in the node schedules of the current band
141 * root is set if this graph is the original dependence graph,
142 * without any splitting
144 * sorted contains a list of node indices sorted according to the
145 * SCC to which a node belongs
147 * n_edge is the number of edges
148 * edge is the list of edges
149 * edge_table contains pointers into the edge array, hashed on the source
150 * and sink spaces; the table only contains edges that represent
151 * validity constraints (and that may or may not also represent proximity
152 * constraints)
154 * node_table contains pointers into the node array, hashed on the space
156 * region contains a list of variable sequences that should be non-trivial
158 * lp contains the (I)LP problem used to obtain new schedule rows
160 * src_scc and dst_scc are the source and sink SCCs of an edge with
161 * conflicting constraints
163 * scc, sp, index and stack are used during the detection of SCCs
164 * scc is the number of the next SCC
165 * stack contains the nodes on the path from the root to the current node
166 * sp is the stack pointer
167 * index is the index of the last node visited
169 struct isl_sched_graph {
170 isl_hmap_map_basic_set *intra_hmap;
171 isl_hmap_map_basic_set *inter_hmap;
173 struct isl_sched_node *node;
174 int n;
175 int maxvar;
176 int n_row;
178 int *sorted;
180 int n_band;
181 int n_total_row;
182 int band_start;
184 int root;
186 struct isl_sched_edge *edge;
187 int n_edge;
188 struct isl_hash_table *edge_table;
190 struct isl_hash_table *node_table;
191 struct isl_region *region;
193 isl_basic_set *lp;
195 int src_scc;
196 int dst_scc;
198 /* scc detection */
199 int scc;
200 int sp;
201 int index;
202 int *stack;
205 /* Initialize node_table based on the list of nodes.
207 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
209 int i;
211 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
212 if (!graph->node_table)
213 return -1;
215 for (i = 0; i < graph->n; ++i) {
216 struct isl_hash_table_entry *entry;
217 uint32_t hash;
219 hash = isl_dim_get_hash(graph->node[i].dim);
220 entry = isl_hash_table_find(ctx, graph->node_table, hash,
221 &node_has_dim,
222 graph->node[i].dim, 1);
223 if (!entry)
224 return -1;
225 entry->data = &graph->node[i];
228 return 0;
231 /* Return a pointer to the node that lives within the given space,
232 * or NULL if there is no such node.
234 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
235 struct isl_sched_graph *graph, __isl_keep isl_dim *dim)
237 struct isl_hash_table_entry *entry;
238 uint32_t hash;
240 hash = isl_dim_get_hash(dim);
241 entry = isl_hash_table_find(ctx, graph->node_table, hash,
242 &node_has_dim, dim, 0);
244 return entry ? entry->data : NULL;
247 static int edge_has_src_and_dst(const void *entry, const void *val)
249 const struct isl_sched_edge *edge = entry;
250 const struct isl_sched_edge *temp = val;
252 return edge->src == temp->src && edge->dst == temp->dst;
255 /* Initialize edge_table based on the list of edges.
256 * Only edges with validity set are added to the table.
258 static int graph_init_edge_table(isl_ctx *ctx, struct isl_sched_graph *graph)
260 int i;
262 graph->edge_table = isl_hash_table_alloc(ctx, graph->n_edge);
263 if (!graph->edge_table)
264 return -1;
266 for (i = 0; i < graph->n_edge; ++i) {
267 struct isl_hash_table_entry *entry;
268 uint32_t hash;
270 if (!graph->edge[i].validity)
271 continue;
273 hash = isl_hash_init();
274 hash = isl_hash_builtin(hash, graph->edge[i].src);
275 hash = isl_hash_builtin(hash, graph->edge[i].dst);
276 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
277 &edge_has_src_and_dst,
278 &graph->edge[i], 1);
279 if (!entry)
280 return -1;
281 entry->data = &graph->edge[i];
284 return 0;
287 /* Check whether the dependence graph has a (validity) edge
288 * between the given two nodes.
290 static int graph_has_edge(struct isl_sched_graph *graph,
291 struct isl_sched_node *src, struct isl_sched_node *dst)
293 isl_ctx *ctx = isl_dim_get_ctx(src->dim);
294 struct isl_hash_table_entry *entry;
295 uint32_t hash;
296 struct isl_sched_edge temp = { .src = src, .dst = dst };
297 struct isl_sched_edge *edge;
298 int empty;
300 hash = isl_hash_init();
301 hash = isl_hash_builtin(hash, temp.src);
302 hash = isl_hash_builtin(hash, temp.dst);
303 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
304 &edge_has_src_and_dst, &temp, 0);
305 if (!entry)
306 return 0;
308 edge = entry->data;
309 empty = isl_map_plain_is_empty(edge->map);
310 if (empty < 0)
311 return -1;
313 return !empty;
316 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
317 int n_node, int n_edge)
319 int i;
321 graph->n = n_node;
322 graph->n_edge = n_edge;
323 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
324 graph->sorted = isl_calloc_array(ctx, int, graph->n);
325 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
326 graph->stack = isl_alloc_array(ctx, int, graph->n);
327 graph->edge = isl_calloc_array(ctx,
328 struct isl_sched_edge, graph->n_edge);
330 graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
331 graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
333 if (!graph->node || !graph->region || !graph->stack || !graph->edge ||
334 !graph->sorted)
335 return -1;
337 for(i = 0; i < graph->n; ++i)
338 graph->sorted[i] = i;
340 return 0;
343 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
345 int i;
347 isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
348 isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
350 for (i = 0; i < graph->n; ++i) {
351 isl_dim_free(graph->node[i].dim);
352 isl_mat_free(graph->node[i].sched);
353 isl_map_free(graph->node[i].sched_map);
354 isl_mat_free(graph->node[i].cmap);
355 if (graph->root) {
356 free(graph->node[i].band);
357 free(graph->node[i].band_id);
358 free(graph->node[i].zero);
361 free(graph->node);
362 free(graph->sorted);
363 for (i = 0; i < graph->n_edge; ++i)
364 isl_map_free(graph->edge[i].map);
365 free(graph->edge);
366 free(graph->region);
367 free(graph->stack);
368 isl_hash_table_free(ctx, graph->edge_table);
369 isl_hash_table_free(ctx, graph->node_table);
370 isl_basic_set_free(graph->lp);
373 /* Add a new node to the graph representing the given set.
375 static int extract_node(__isl_take isl_set *set, void *user)
377 int nvar, nparam;
378 isl_ctx *ctx;
379 isl_dim *dim;
380 isl_mat *sched;
381 struct isl_sched_graph *graph = user;
382 int *band, *band_id, *zero;
384 ctx = isl_set_get_ctx(set);
385 dim = isl_set_get_dim(set);
386 isl_set_free(set);
387 nvar = isl_dim_size(dim, isl_dim_set);
388 nparam = isl_dim_size(dim, isl_dim_param);
389 if (!ctx->opt->schedule_parametric)
390 nparam = 0;
391 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
392 graph->node[graph->n].dim = dim;
393 graph->node[graph->n].nvar = nvar;
394 graph->node[graph->n].nparam = nparam;
395 graph->node[graph->n].sched = sched;
396 graph->node[graph->n].sched_map = NULL;
397 band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
398 graph->node[graph->n].band = band;
399 band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
400 graph->node[graph->n].band_id = band_id;
401 zero = isl_calloc_array(ctx, int, graph->n_edge + nvar);
402 graph->node[graph->n].zero = zero;
403 graph->n++;
405 if (!sched || !band || !band_id || !zero)
406 return -1;
408 return 0;
411 /* Add a new edge to the graph based on the given map.
412 * Edges are first extracted from the validity dependences,
413 * from which the edge_table is constructed.
414 * Afterwards, the proximity dependences are added. If a proximity
415 * dependence relation happens to be identical to one of the
416 * validity dependence relations added before, then we don't create
417 * a new edge, but instead mark the original edge as also representing
418 * a proximity dependence.
420 static int extract_edge(__isl_take isl_map *map, void *user)
422 isl_ctx *ctx = isl_map_get_ctx(map);
423 struct isl_sched_graph *graph = user;
424 struct isl_sched_node *src, *dst;
425 isl_dim *dim;
427 dim = isl_dim_domain(isl_map_get_dim(map));
428 src = graph_find_node(ctx, graph, dim);
429 isl_dim_free(dim);
430 dim = isl_dim_range(isl_map_get_dim(map));
431 dst = graph_find_node(ctx, graph, dim);
432 isl_dim_free(dim);
434 if (!src || !dst) {
435 isl_map_free(map);
436 return 0;
439 graph->edge[graph->n_edge].src = src;
440 graph->edge[graph->n_edge].dst = dst;
441 graph->edge[graph->n_edge].map = map;
442 graph->edge[graph->n_edge].validity = !graph->edge_table;
443 graph->edge[graph->n_edge].proximity = !!graph->edge_table;
444 graph->n_edge++;
446 if (graph->edge_table) {
447 uint32_t hash;
448 struct isl_hash_table_entry *entry;
449 struct isl_sched_edge *edge;
450 int is_equal;
452 hash = isl_hash_init();
453 hash = isl_hash_builtin(hash, src);
454 hash = isl_hash_builtin(hash, dst);
455 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
456 &edge_has_src_and_dst,
457 &graph->edge[graph->n_edge - 1], 0);
458 if (!entry)
459 return 0;
460 edge = entry->data;
461 is_equal = isl_map_plain_is_equal(map, edge->map);
462 if (is_equal < 0)
463 return -1;
464 if (!is_equal)
465 return 0;
467 graph->n_edge--;
468 edge->proximity = 1;
469 isl_map_free(map);
472 return 0;
475 /* Check whether there is a validity dependence from src to dst,
476 * forcing dst to follow src.
478 static int node_follows(struct isl_sched_graph *graph,
479 struct isl_sched_node *dst, struct isl_sched_node *src)
481 return graph_has_edge(graph, src, dst);
484 /* Perform Tarjan's algorithm for computing the strongly connected components
485 * in the dependence graph (only validity edges).
486 * If directed is not set, we consider the graph to be undirected and
487 * we effectively compute the (weakly) connected components.
489 static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed)
491 int j;
493 g->node[i].index = g->index;
494 g->node[i].min_index = g->index;
495 g->node[i].on_stack = 1;
496 g->index++;
497 g->stack[g->sp++] = i;
499 for (j = g->n - 1; j >= 0; --j) {
500 int f;
502 if (j == i)
503 continue;
504 if (g->node[j].index >= 0 &&
505 (!g->node[j].on_stack ||
506 g->node[j].index > g->node[i].min_index))
507 continue;
509 f = node_follows(g, &g->node[i], &g->node[j]);
510 if (f < 0)
511 return -1;
512 if (!f && !directed) {
513 f = node_follows(g, &g->node[j], &g->node[i]);
514 if (f < 0)
515 return -1;
517 if (!f)
518 continue;
519 if (g->node[j].index < 0) {
520 detect_sccs_tarjan(g, j, directed);
521 if (g->node[j].min_index < g->node[i].min_index)
522 g->node[i].min_index = g->node[j].min_index;
523 } else if (g->node[j].index < g->node[i].min_index)
524 g->node[i].min_index = g->node[j].index;
527 if (g->node[i].index != g->node[i].min_index)
528 return 0;
530 do {
531 j = g->stack[--g->sp];
532 g->node[j].on_stack = 0;
533 g->node[j].scc = g->scc;
534 } while (j != i);
535 g->scc++;
537 return 0;
540 static int detect_ccs(struct isl_sched_graph *graph, int directed)
542 int i;
544 graph->index = 0;
545 graph->sp = 0;
546 graph->scc = 0;
547 for (i = graph->n - 1; i >= 0; --i)
548 graph->node[i].index = -1;
550 for (i = graph->n - 1; i >= 0; --i) {
551 if (graph->node[i].index >= 0)
552 continue;
553 if (detect_sccs_tarjan(graph, i, directed) < 0)
554 return -1;
557 return 0;
560 /* Apply Tarjan's algorithm to detect the strongly connected components
561 * in the dependence graph.
563 static int detect_sccs(struct isl_sched_graph *graph)
565 return detect_ccs(graph, 1);
568 /* Apply Tarjan's algorithm to detect the (weakly) connected components
569 * in the dependence graph.
571 static int detect_wccs(struct isl_sched_graph *graph)
573 return detect_ccs(graph, 0);
576 static int cmp_scc(const void *a, const void *b, void *data)
578 struct isl_sched_graph *graph = data;
579 const int *i1 = a;
580 const int *i2 = b;
582 return graph->node[*i1].scc - graph->node[*i2].scc;
585 /* Sort the elements of graph->sorted according to the corresponding SCCs.
587 static void sort_sccs(struct isl_sched_graph *graph)
589 isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
592 /* Given a dependence relation R from a node to itself,
593 * construct the set of coefficients of valid constraints for elements
594 * in that dependence relation.
595 * In particular, the result contains tuples of coefficients
596 * c_0, c_n, c_x such that
598 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
600 * or, equivalently,
602 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
604 * We choose here to compute the dual of delta R.
605 * Alternatively, we could have computed the dual of R, resulting
606 * in a set of tuples c_0, c_n, c_x, c_y, and then
607 * plugged in (c_0, c_n, c_x, -c_x).
609 static __isl_give isl_basic_set *intra_coefficients(
610 struct isl_sched_graph *graph, __isl_take isl_map *map)
612 isl_ctx *ctx = isl_map_get_ctx(map);
613 isl_set *delta;
614 isl_basic_set *coef;
616 if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
617 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
619 delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
620 coef = isl_set_coefficients(delta);
621 isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
622 isl_basic_set_copy(coef));
624 return coef;
627 /* Given a dependence relation R, * construct the set of coefficients
628 * of valid constraints for elements in that dependence relation.
629 * In particular, the result contains tuples of coefficients
630 * c_0, c_n, c_x, c_y such that
632 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
635 static __isl_give isl_basic_set *inter_coefficients(
636 struct isl_sched_graph *graph, __isl_take isl_map *map)
638 isl_ctx *ctx = isl_map_get_ctx(map);
639 isl_set *set;
640 isl_basic_set *coef;
642 if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
643 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
645 set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
646 coef = isl_set_coefficients(set);
647 isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
648 isl_basic_set_copy(coef));
650 return coef;
653 /* Add constraints to graph->lp that force validity for the given
654 * dependence from a node i to itself.
655 * That is, add constraints that enforce
657 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
658 * = c_i_x (y - x) >= 0
660 * for each (x,y) in R.
661 * We obtain general constraints on coefficients (c_0, c_n, c_x)
662 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
663 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
664 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
666 * Actually, we do not construct constraints for the c_i_x themselves,
667 * but for the coefficients of c_i_x written as a linear combination
668 * of the columns in node->cmap.
670 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
671 struct isl_sched_edge *edge)
673 unsigned total;
674 isl_map *map = isl_map_copy(edge->map);
675 isl_ctx *ctx = isl_map_get_ctx(map);
676 isl_dim *dim;
677 isl_dim_map *dim_map;
678 isl_basic_set *coef;
679 struct isl_sched_node *node = edge->src;
681 coef = intra_coefficients(graph, map);
683 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
685 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
686 isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap));
688 total = isl_basic_set_total_dim(graph->lp);
689 dim_map = isl_dim_map_alloc(ctx, total);
690 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
691 isl_dim_size(dim, isl_dim_set), 1,
692 node->nvar, -1);
693 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
694 isl_dim_size(dim, isl_dim_set), 1,
695 node->nvar, 1);
696 graph->lp = isl_basic_set_extend_constraints(graph->lp,
697 coef->n_eq, coef->n_ineq);
698 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
699 coef, dim_map);
700 isl_dim_free(dim);
702 return 0;
705 /* Add constraints to graph->lp that force validity for the given
706 * dependence from node i to node j.
707 * That is, add constraints that enforce
709 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
711 * for each (x,y) in R.
712 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
713 * of valid constraints for R and then plug in
714 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
715 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
716 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
717 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
719 * Actually, we do not construct constraints for the c_*_x themselves,
720 * but for the coefficients of c_*_x written as a linear combination
721 * of the columns in node->cmap.
723 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
724 struct isl_sched_edge *edge)
726 unsigned total;
727 isl_map *map = isl_map_copy(edge->map);
728 isl_ctx *ctx = isl_map_get_ctx(map);
729 isl_dim *dim;
730 isl_dim_map *dim_map;
731 isl_basic_set *coef;
732 struct isl_sched_node *src = edge->src;
733 struct isl_sched_node *dst = edge->dst;
735 coef = inter_coefficients(graph, map);
737 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
739 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
740 isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap));
741 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
742 isl_dim_size(dim, isl_dim_set) + src->nvar,
743 isl_mat_copy(dst->cmap));
745 total = isl_basic_set_total_dim(graph->lp);
746 dim_map = isl_dim_map_alloc(ctx, total);
748 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
749 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
750 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
751 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
752 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
753 dst->nvar, -1);
754 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
755 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
756 dst->nvar, 1);
758 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
759 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
760 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
761 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
762 isl_dim_size(dim, isl_dim_set), 1,
763 src->nvar, 1);
764 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
765 isl_dim_size(dim, isl_dim_set), 1,
766 src->nvar, -1);
768 edge->start = graph->lp->n_ineq;
769 graph->lp = isl_basic_set_extend_constraints(graph->lp,
770 coef->n_eq, coef->n_ineq);
771 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
772 coef, dim_map);
773 isl_dim_free(dim);
774 edge->end = graph->lp->n_ineq;
776 return 0;
779 /* Add constraints to graph->lp that bound the dependence distance for the given
780 * dependence from a node i to itself.
781 * If s = 1, we add the constraint
783 * c_i_x (y - x) <= m_0 + m_n n
785 * or
787 * -c_i_x (y - x) + m_0 + m_n n >= 0
789 * for each (x,y) in R.
790 * If s = -1, we add the constraint
792 * -c_i_x (y - x) <= m_0 + m_n n
794 * or
796 * c_i_x (y - x) + m_0 + m_n n >= 0
798 * for each (x,y) in R.
799 * We obtain general constraints on coefficients (c_0, c_n, c_x)
800 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
801 * with each coefficient (except m_0) represented as a pair of non-negative
802 * coefficients.
804 * Actually, we do not construct constraints for the c_i_x themselves,
805 * but for the coefficients of c_i_x written as a linear combination
806 * of the columns in node->cmap.
808 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
809 struct isl_sched_edge *edge, int s)
811 unsigned total;
812 unsigned nparam;
813 isl_map *map = isl_map_copy(edge->map);
814 isl_ctx *ctx = isl_map_get_ctx(map);
815 isl_dim *dim;
816 isl_dim_map *dim_map;
817 isl_basic_set *coef;
818 struct isl_sched_node *node = edge->src;
820 coef = intra_coefficients(graph, map);
822 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
824 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
825 isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap));
827 nparam = isl_dim_size(node->dim, isl_dim_param);
828 total = isl_basic_set_total_dim(graph->lp);
829 dim_map = isl_dim_map_alloc(ctx, total);
830 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
831 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
832 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
833 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
834 isl_dim_size(dim, isl_dim_set), 1,
835 node->nvar, s);
836 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
837 isl_dim_size(dim, isl_dim_set), 1,
838 node->nvar, -s);
839 graph->lp = isl_basic_set_extend_constraints(graph->lp,
840 coef->n_eq, coef->n_ineq);
841 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
842 coef, dim_map);
843 isl_dim_free(dim);
845 return 0;
848 /* Add constraints to graph->lp that bound the dependence distance for the given
849 * dependence from node i to node j.
850 * If s = 1, we add the constraint
852 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
853 * <= m_0 + m_n n
855 * or
857 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
858 * m_0 + m_n n >= 0
860 * for each (x,y) in R.
861 * If s = -1, we add the constraint
863 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
864 * <= m_0 + m_n n
866 * or
868 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
869 * m_0 + m_n n >= 0
871 * for each (x,y) in R.
872 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
873 * of valid constraints for R and then plug in
874 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
875 * -s*c_j_x+s*c_i_x)
876 * with each coefficient (except m_0, c_j_0 and c_i_0)
877 * represented as a pair of non-negative coefficients.
879 * Actually, we do not construct constraints for the c_*_x themselves,
880 * but for the coefficients of c_*_x written as a linear combination
881 * of the columns in node->cmap.
883 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
884 struct isl_sched_edge *edge, int s)
886 unsigned total;
887 unsigned nparam;
888 isl_map *map = isl_map_copy(edge->map);
889 isl_ctx *ctx = isl_map_get_ctx(map);
890 isl_dim *dim;
891 isl_dim_map *dim_map;
892 isl_basic_set *coef;
893 struct isl_sched_node *src = edge->src;
894 struct isl_sched_node *dst = edge->dst;
896 coef = inter_coefficients(graph, map);
898 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
900 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
901 isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap));
902 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
903 isl_dim_size(dim, isl_dim_set) + src->nvar,
904 isl_mat_copy(dst->cmap));
906 nparam = isl_dim_size(src->dim, isl_dim_param);
907 total = isl_basic_set_total_dim(graph->lp);
908 dim_map = isl_dim_map_alloc(ctx, total);
910 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
911 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
912 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
914 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
915 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
916 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
917 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
918 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
919 dst->nvar, s);
920 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
921 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
922 dst->nvar, -s);
924 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
925 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
926 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
927 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
928 isl_dim_size(dim, isl_dim_set), 1,
929 src->nvar, -s);
930 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
931 isl_dim_size(dim, isl_dim_set), 1,
932 src->nvar, s);
934 graph->lp = isl_basic_set_extend_constraints(graph->lp,
935 coef->n_eq, coef->n_ineq);
936 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
937 coef, dim_map);
938 isl_dim_free(dim);
940 return 0;
943 static int add_all_validity_constraints(struct isl_sched_graph *graph)
945 int i;
947 for (i = 0; i < graph->n_edge; ++i) {
948 struct isl_sched_edge *edge= &graph->edge[i];
949 if (!edge->validity)
950 continue;
951 if (edge->src != edge->dst)
952 continue;
953 if (add_intra_validity_constraints(graph, edge) < 0)
954 return -1;
957 for (i = 0; i < graph->n_edge; ++i) {
958 struct isl_sched_edge *edge = &graph->edge[i];
959 if (!edge->validity)
960 continue;
961 if (edge->src == edge->dst)
962 continue;
963 if (add_inter_validity_constraints(graph, edge) < 0)
964 return -1;
967 return 0;
970 /* Add constraints to graph->lp that bound the dependence distance
971 * for all dependence relations.
972 * If a given proximity dependence is identical to a validity
973 * dependence, then the dependence distance is already bounded
974 * from below (by zero), so we only need to bound the distance
975 * from above.
976 * Otherwise, we need to bound the distance both from above and from below.
978 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
980 int i;
982 for (i = 0; i < graph->n_edge; ++i) {
983 struct isl_sched_edge *edge= &graph->edge[i];
984 if (!edge->proximity)
985 continue;
986 if (edge->src == edge->dst &&
987 add_intra_proximity_constraints(graph, edge, 1) < 0)
988 return -1;
989 if (edge->src != edge->dst &&
990 add_inter_proximity_constraints(graph, edge, 1) < 0)
991 return -1;
992 if (edge->validity)
993 continue;
994 if (edge->src == edge->dst &&
995 add_intra_proximity_constraints(graph, edge, -1) < 0)
996 return -1;
997 if (edge->src != edge->dst &&
998 add_inter_proximity_constraints(graph, edge, -1) < 0)
999 return -1;
1002 return 0;
1005 /* Compute a basis for the rows in the linear part of the schedule
1006 * and extend this basis to a full basis. The remaining rows
1007 * can then be used to force linear independence from the rows
1008 * in the schedule.
1010 * In particular, given the schedule rows S, we compute
1012 * S = H Q
1014 * with H the Hermite normal form of S. That is, all but the
1015 * first rank columns of Q are zero and so each row in S is
1016 * a linear combination of the first rank rows of Q.
1017 * The matrix Q is then transposed because we will write the
1018 * coefficients of the next schedule row as a column vector s
1019 * and express this s as a linear combination s = Q c of the
1020 * computed basis.
1022 static int node_update_cmap(struct isl_sched_node *node)
1024 isl_mat *H, *Q;
1025 int n_row = isl_mat_rows(node->sched);
1027 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1028 1 + node->nparam, node->nvar);
1030 H = isl_mat_left_hermite(H, 0, NULL, &Q);
1031 isl_mat_free(node->cmap);
1032 node->cmap = isl_mat_transpose(Q);
1033 node->rank = isl_mat_initial_non_zero_cols(H);
1034 isl_mat_free(H);
1036 if (!node->cmap || node->rank < 0)
1037 return -1;
1038 return 0;
1041 /* Count the number of equality and inequality constraints
1042 * that will be added. If once is set, then we count
1043 * each edge exactly once. Otherwise, we count as follows
1044 * validity -> 1 (>= 0)
1045 * validity+proximity -> 2 (>= 0 and upper bound)
1046 * proximity -> 2 (lower and upper bound)
1048 static int count_constraints(struct isl_sched_graph *graph,
1049 int *n_eq, int *n_ineq, int once)
1051 int i;
1052 isl_basic_set *coef;
1054 *n_eq = *n_ineq = 0;
1055 for (i = 0; i < graph->n_edge; ++i) {
1056 struct isl_sched_edge *edge= &graph->edge[i];
1057 isl_map *map = isl_map_copy(edge->map);
1058 int f = once ? 1 : edge->proximity ? 2 : 1;
1060 if (edge->src == edge->dst)
1061 coef = intra_coefficients(graph, map);
1062 else
1063 coef = inter_coefficients(graph, map);
1064 if (!coef)
1065 return -1;
1066 *n_eq += f * coef->n_eq;
1067 *n_ineq += f * coef->n_ineq;
1068 isl_basic_set_free(coef);
1071 return 0;
1074 /* Construct an ILP problem for finding schedule coefficients
1075 * that result in non-negative, but small dependence distances
1076 * over all dependences.
1077 * In particular, the dependence distances over proximity edges
1078 * are bounded by m_0 + m_n n and we compute schedule coefficients
1079 * with small values (preferably zero) of m_n and m_0.
1081 * All variables of the ILP are non-negative. The actual coefficients
1082 * may be negative, so each coefficient is represented as the difference
1083 * of two non-negative variables. The negative part always appears
1084 * immediately before the positive part.
1085 * Other than that, the variables have the following order
1087 * - sum of positive and negative parts of m_n coefficients
1088 * - m_0
1089 * - sum of positive and negative parts of all c_n coefficients
1090 * (unconstrained when computing non-parametric schedules)
1091 * - sum of positive and negative parts of all c_x coefficients
1092 * - positive and negative parts of m_n coefficients
1093 * - for each node
1094 * - c_i_0
1095 * - positive and negative parts of c_i_n (if parametric)
1096 * - positive and negative parts of c_i_x
1098 * The c_i_x are not represented directly, but through the columns of
1099 * node->cmap. That is, the computed values are for variable t_i_x
1100 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1102 * The constraints are those from the edges plus two or three equalities
1103 * to express the sums.
1105 * If force_zero is set, then we add equalities to ensure that
1106 * the sum of the m_n coefficients and m_0 are both zero.
1108 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
1109 int force_zero)
1111 int i, j;
1112 int k;
1113 unsigned nparam;
1114 unsigned total;
1115 isl_dim *dim;
1116 int parametric;
1117 int param_pos;
1118 int n_eq, n_ineq;
1120 parametric = ctx->opt->schedule_parametric;
1121 nparam = isl_dim_size(graph->node[0].dim, isl_dim_param);
1122 param_pos = 4;
1123 total = param_pos + 2 * nparam;
1124 for (i = 0; i < graph->n; ++i) {
1125 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1126 if (node_update_cmap(node) < 0)
1127 return -1;
1128 node->start = total;
1129 total += 1 + 2 * (node->nparam + node->nvar);
1132 if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0)
1133 return -1;
1135 dim = isl_dim_set_alloc(ctx, 0, total);
1136 isl_basic_set_free(graph->lp);
1137 n_eq += 2 + parametric + force_zero;
1138 graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq);
1140 k = isl_basic_set_alloc_equality(graph->lp);
1141 if (k < 0)
1142 return -1;
1143 isl_seq_clr(graph->lp->eq[k], 1 + total);
1144 if (!force_zero)
1145 isl_int_set_si(graph->lp->eq[k][1], -1);
1146 for (i = 0; i < 2 * nparam; ++i)
1147 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1149 if (force_zero) {
1150 k = isl_basic_set_alloc_equality(graph->lp);
1151 if (k < 0)
1152 return -1;
1153 isl_seq_clr(graph->lp->eq[k], 1 + total);
1154 isl_int_set_si(graph->lp->eq[k][2], -1);
1157 if (parametric) {
1158 k = isl_basic_set_alloc_equality(graph->lp);
1159 if (k < 0)
1160 return -1;
1161 isl_seq_clr(graph->lp->eq[k], 1 + total);
1162 isl_int_set_si(graph->lp->eq[k][3], -1);
1163 for (i = 0; i < graph->n; ++i) {
1164 int pos = 1 + graph->node[i].start + 1;
1166 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1167 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1171 k = isl_basic_set_alloc_equality(graph->lp);
1172 if (k < 0)
1173 return -1;
1174 isl_seq_clr(graph->lp->eq[k], 1 + total);
1175 isl_int_set_si(graph->lp->eq[k][4], -1);
1176 for (i = 0; i < graph->n; ++i) {
1177 struct isl_sched_node *node = &graph->node[i];
1178 int pos = 1 + node->start + 1 + 2 * node->nparam;
1180 for (j = 0; j < 2 * node->nvar; ++j)
1181 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1184 if (add_all_validity_constraints(graph) < 0)
1185 return -1;
1186 if (add_all_proximity_constraints(graph) < 0)
1187 return -1;
1189 return 0;
1192 /* Analyze the conflicting constraint found by
1193 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1194 * constraint of one of the edges between distinct nodes, living, moreover
1195 * in distinct SCCs, then record the source and sink SCC as this may
1196 * be a good place to cut between SCCs.
1198 static int check_conflict(int con, void *user)
1200 int i;
1201 struct isl_sched_graph *graph = user;
1203 if (graph->src_scc >= 0)
1204 return 0;
1206 con -= graph->lp->n_eq;
1208 if (con >= graph->lp->n_ineq)
1209 return 0;
1211 for (i = 0; i < graph->n_edge; ++i) {
1212 if (!graph->edge[i].validity)
1213 continue;
1214 if (graph->edge[i].src == graph->edge[i].dst)
1215 continue;
1216 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1217 continue;
1218 if (graph->edge[i].start > con)
1219 continue;
1220 if (graph->edge[i].end <= con)
1221 continue;
1222 graph->src_scc = graph->edge[i].src->scc;
1223 graph->dst_scc = graph->edge[i].dst->scc;
1226 return 0;
1229 /* Check whether the next schedule row of the given node needs to be
1230 * non-trivial. Lower-dimensional domains may have some trivial rows,
1231 * but as soon as the number of remaining required non-trivial rows
1232 * is as large as the number or remaining rows to be computed,
1233 * all remaining rows need to be non-trivial.
1235 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1237 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1240 /* Solve the ILP problem constructed in setup_lp.
1241 * For each node such that all the remaining rows of its schedule
1242 * need to be non-trivial, we construct a non-triviality region.
1243 * This region imposes that the next row is independent of previous rows.
1244 * In particular the coefficients c_i_x are represented by t_i_x
1245 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1246 * its first columns span the rows of the previously computed part
1247 * of the schedule. The non-triviality region enforces that at least
1248 * one of the remaining components of t_i_x is non-zero, i.e.,
1249 * that the new schedule row depends on at least one of the remaining
1250 * columns of Q.
1252 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1254 int i;
1255 isl_vec *sol;
1256 isl_basic_set *lp;
1258 for (i = 0; i < graph->n; ++i) {
1259 struct isl_sched_node *node = &graph->node[i];
1260 int skip = node->rank;
1261 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1262 if (needs_row(graph, node))
1263 graph->region[i].len = 2 * (node->nvar - skip);
1264 else
1265 graph->region[i].len = 0;
1267 lp = isl_basic_set_copy(graph->lp);
1268 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1269 graph->region, &check_conflict, graph);
1270 return sol;
1273 /* Update the schedules of all nodes based on the given solution
1274 * of the LP problem.
1275 * The new row is added to the current band.
1276 * All possibly negative coefficients are encoded as a difference
1277 * of two non-negative variables, so we need to perform the subtraction
1278 * here. Moreover, if use_cmap is set, then the solution does
1279 * not refer to the actual coefficients c_i_x, but instead to variables
1280 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1281 * In this case, we then also need to perform this multiplication
1282 * to obtain the values of c_i_x.
1284 * If check_zero is set, then the first two coordinates of sol are
1285 * assumed to correspond to the dependence distance. If these two
1286 * coordinates are zero, then the corresponding scheduling dimension
1287 * is marked as being zero distance.
1289 static int update_schedule(struct isl_sched_graph *graph,
1290 __isl_take isl_vec *sol, int use_cmap, int check_zero)
1292 int i, j;
1293 int zero = 0;
1294 isl_vec *csol = NULL;
1296 if (!sol)
1297 goto error;
1298 if (sol->size == 0)
1299 isl_die(sol->ctx, isl_error_internal,
1300 "no solution found", goto error);
1302 if (check_zero)
1303 zero = isl_int_is_zero(sol->el[1]) &&
1304 isl_int_is_zero(sol->el[2]);
1306 for (i = 0; i < graph->n; ++i) {
1307 struct isl_sched_node *node = &graph->node[i];
1308 int pos = node->start;
1309 int row = isl_mat_rows(node->sched);
1311 isl_vec_free(csol);
1312 csol = isl_vec_alloc(sol->ctx, node->nvar);
1313 if (!csol)
1314 goto error;
1316 isl_map_free(node->sched_map);
1317 node->sched_map = NULL;
1318 node->sched = isl_mat_add_rows(node->sched, 1);
1319 if (!node->sched)
1320 goto error;
1321 node->sched = isl_mat_set_element(node->sched, row, 0,
1322 sol->el[1 + pos]);
1323 for (j = 0; j < node->nparam + node->nvar; ++j)
1324 isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1325 sol->el[1 + pos + 1 + 2 * j + 1],
1326 sol->el[1 + pos + 1 + 2 * j]);
1327 for (j = 0; j < node->nparam; ++j)
1328 node->sched = isl_mat_set_element(node->sched,
1329 row, 1 + j, sol->el[1+pos+1+2*j+1]);
1330 for (j = 0; j < node->nvar; ++j)
1331 isl_int_set(csol->el[j],
1332 sol->el[1+pos+1+2*(node->nparam+j)+1]);
1333 if (use_cmap)
1334 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1335 csol);
1336 if (!csol)
1337 goto error;
1338 for (j = 0; j < node->nvar; ++j)
1339 node->sched = isl_mat_set_element(node->sched,
1340 row, 1 + node->nparam + j, csol->el[j]);
1341 node->band[graph->n_total_row] = graph->n_band;
1342 node->zero[graph->n_total_row] = zero;
1344 isl_vec_free(sol);
1345 isl_vec_free(csol);
1347 graph->n_row++;
1348 graph->n_total_row++;
1350 return 0;
1351 error:
1352 isl_vec_free(sol);
1353 isl_vec_free(csol);
1354 return -1;
1357 /* Convert node->sched into a map and return this map.
1358 * We simply add equality constraints that express each output variable
1359 * as the affine combination of parameters and input variables specified
1360 * by the schedule matrix.
1362 * The result is cached in node->sched_map, which needs to be released
1363 * whenever node->sched is updated.
1365 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1367 int i, j;
1368 isl_dim *dim;
1369 isl_basic_map *bmap;
1370 isl_constraint *c;
1371 int nrow, ncol;
1372 isl_int v;
1374 if (node->sched_map)
1375 return isl_map_copy(node->sched_map);
1377 nrow = isl_mat_rows(node->sched);
1378 ncol = isl_mat_cols(node->sched) - 1;
1379 dim = isl_dim_from_domain(isl_dim_copy(node->dim));
1380 dim = isl_dim_add(dim, isl_dim_out, nrow);
1381 bmap = isl_basic_map_universe(isl_dim_copy(dim));
1383 isl_int_init(v);
1385 for (i = 0; i < nrow; ++i) {
1386 c = isl_equality_alloc(isl_dim_copy(dim));
1387 isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
1388 isl_mat_get_element(node->sched, i, 0, &v);
1389 isl_constraint_set_constant(c, v);
1390 for (j = 0; j < node->nparam; ++j) {
1391 isl_mat_get_element(node->sched, i, 1 + j, &v);
1392 isl_constraint_set_coefficient(c, isl_dim_param, j, v);
1394 for (j = 0; j < node->nvar; ++j) {
1395 isl_mat_get_element(node->sched,
1396 i, 1 + node->nparam + j, &v);
1397 isl_constraint_set_coefficient(c, isl_dim_in, j, v);
1399 bmap = isl_basic_map_add_constraint(bmap, c);
1402 isl_int_clear(v);
1404 isl_dim_free(dim);
1406 node->sched_map = isl_map_from_basic_map(bmap);
1407 return isl_map_copy(node->sched_map);
1410 /* Update the given dependence relation based on the current schedule.
1411 * That is, intersect the dependence relation with a map expressing
1412 * that source and sink are executed within the same iteration of
1413 * the current schedule.
1414 * This is not the most efficient way, but this shouldn't be a critical
1415 * operation.
1417 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1418 struct isl_sched_node *src, struct isl_sched_node *dst)
1420 isl_map *src_sched, *dst_sched, *id;
1422 src_sched = node_extract_schedule(src);
1423 dst_sched = node_extract_schedule(dst);
1424 id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1425 return isl_map_intersect(map, id);
1428 /* Update the dependence relations of all edges based on the current schedule.
1429 * If a dependence is carried completely by the current schedule, then
1430 * it is removed and edge_table is updated accordingly.
1432 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1434 int i;
1435 int reset_table = 0;
1437 for (i = graph->n_edge - 1; i >= 0; --i) {
1438 struct isl_sched_edge *edge = &graph->edge[i];
1439 edge->map = specialize(edge->map, edge->src, edge->dst);
1440 if (!edge->map)
1441 return -1;
1443 if (isl_map_plain_is_empty(edge->map)) {
1444 reset_table = 1;
1445 isl_map_free(edge->map);
1446 if (i != graph->n_edge - 1)
1447 graph->edge[i] = graph->edge[graph->n_edge - 1];
1448 graph->n_edge--;
1452 if (reset_table) {
1453 isl_hash_table_free(ctx, graph->edge_table);
1454 graph->edge_table = NULL;
1455 return graph_init_edge_table(ctx, graph);
1458 return 0;
1461 static void next_band(struct isl_sched_graph *graph)
1463 graph->band_start = graph->n_total_row;
1464 graph->n_band++;
1467 /* Topologically sort statements mapped to same schedule iteration
1468 * and add a row to the schedule corresponding to this order.
1470 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1472 int i, j;
1474 if (graph->n <= 1)
1475 return 0;
1477 if (update_edges(ctx, graph) < 0)
1478 return -1;
1480 if (graph->n_edge == 0)
1481 return 0;
1483 if (detect_sccs(graph) < 0)
1484 return -1;
1486 for (i = 0; i < graph->n; ++i) {
1487 struct isl_sched_node *node = &graph->node[i];
1488 int row = isl_mat_rows(node->sched);
1489 int cols = isl_mat_cols(node->sched);
1491 isl_map_free(node->sched_map);
1492 node->sched_map = NULL;
1493 node->sched = isl_mat_add_rows(node->sched, 1);
1494 if (!node->sched)
1495 return -1;
1496 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1497 node->scc);
1498 for (j = 1; j < cols; ++j)
1499 node->sched = isl_mat_set_element_si(node->sched,
1500 row, j, 0);
1501 node->band[graph->n_total_row] = graph->n_band;
1504 graph->n_total_row++;
1505 next_band(graph);
1507 return 0;
1510 /* Construct an isl_schedule based on the computed schedule stored
1511 * in graph and with parameters specified by dim.
1513 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1514 __isl_take isl_dim *dim)
1516 int i;
1517 isl_ctx *ctx;
1518 isl_schedule *sched = NULL;
1520 if (!dim)
1521 return NULL;
1523 ctx = isl_dim_get_ctx(dim);
1524 sched = isl_calloc(ctx, struct isl_schedule,
1525 sizeof(struct isl_schedule) +
1526 (graph->n - 1) * sizeof(struct isl_schedule_node));
1527 if (!sched)
1528 goto error;
1530 sched->ref = 1;
1531 sched->n = graph->n;
1532 sched->n_band = graph->n_band;
1533 sched->n_total_row = graph->n_total_row;
1535 for (i = 0; i < sched->n; ++i) {
1536 int r, b;
1537 int *band_end, *band_id, *zero;
1539 band_end = isl_alloc_array(ctx, int, graph->n_band);
1540 band_id = isl_alloc_array(ctx, int, graph->n_band);
1541 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1542 sched->node[i].sched = node_extract_schedule(&graph->node[i]);
1543 sched->node[i].band_end = band_end;
1544 sched->node[i].band_id = band_id;
1545 sched->node[i].zero = zero;
1546 if (!band_end || !band_id || !zero)
1547 goto error;
1549 for (r = 0; r < graph->n_total_row; ++r)
1550 zero[r] = graph->node[i].zero[r];
1551 for (r = b = 0; r < graph->n_total_row; ++r) {
1552 if (graph->node[i].band[r] == b)
1553 continue;
1554 band_end[b++] = r;
1555 if (graph->node[i].band[r] == -1)
1556 break;
1558 if (r == graph->n_total_row)
1559 band_end[b++] = r;
1560 sched->node[i].n_band = b;
1561 for (--b; b >= 0; --b)
1562 band_id[b] = graph->node[i].band_id[b];
1565 sched->dim = dim;
1567 return sched;
1568 error:
1569 isl_dim_free(dim);
1570 isl_schedule_free(sched);
1571 return NULL;
1574 /* Copy nodes that satisfy node_pred from the src dependence graph
1575 * to the dst dependence graph.
1577 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1578 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1580 int i;
1582 dst->n = 0;
1583 for (i = 0; i < src->n; ++i) {
1584 if (!node_pred(&src->node[i], data))
1585 continue;
1586 dst->node[dst->n].dim = isl_dim_copy(src->node[i].dim);
1587 dst->node[dst->n].nvar = src->node[i].nvar;
1588 dst->node[dst->n].nparam = src->node[i].nparam;
1589 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1590 dst->node[dst->n].sched_map =
1591 isl_map_copy(src->node[i].sched_map);
1592 dst->node[dst->n].band = src->node[i].band;
1593 dst->node[dst->n].band_id = src->node[i].band_id;
1594 dst->node[dst->n].zero = src->node[i].zero;
1595 dst->n++;
1598 return 0;
1601 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1602 * to the dst dependence graph.
1604 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1605 struct isl_sched_graph *src,
1606 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1608 int i;
1610 dst->n_edge = 0;
1611 for (i = 0; i < src->n_edge; ++i) {
1612 struct isl_sched_edge *edge = &src->edge[i];
1613 isl_map *map;
1615 if (!edge_pred(edge, data))
1616 continue;
1618 if (isl_map_plain_is_empty(edge->map))
1619 continue;
1621 map = isl_map_copy(edge->map);
1623 dst->edge[dst->n_edge].src =
1624 graph_find_node(ctx, dst, edge->src->dim);
1625 dst->edge[dst->n_edge].dst =
1626 graph_find_node(ctx, dst, edge->dst->dim);
1627 dst->edge[dst->n_edge].map = map;
1628 dst->edge[dst->n_edge].validity = edge->validity;
1629 dst->edge[dst->n_edge].proximity = edge->proximity;
1630 dst->n_edge++;
1633 return 0;
1636 /* Given a "src" dependence graph that contains the nodes from "dst"
1637 * that satisfy node_pred, copy the schedule computed in "src"
1638 * for those nodes back to "dst".
1640 static int copy_schedule(struct isl_sched_graph *dst,
1641 struct isl_sched_graph *src,
1642 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1644 int i;
1646 src->n = 0;
1647 for (i = 0; i < dst->n; ++i) {
1648 if (!node_pred(&dst->node[i], data))
1649 continue;
1650 isl_mat_free(dst->node[i].sched);
1651 isl_map_free(dst->node[i].sched_map);
1652 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1653 dst->node[i].sched_map =
1654 isl_map_copy(src->node[src->n].sched_map);
1655 src->n++;
1658 dst->n_total_row = src->n_total_row;
1659 dst->n_band = src->n_band;
1661 return 0;
1664 /* Compute the maximal number of variables over all nodes.
1665 * This is the maximal number of linearly independent schedule
1666 * rows that we need to compute.
1667 * Just in case we end up in a part of the dependence graph
1668 * with only lower-dimensional domains, we make sure we will
1669 * compute the required amount of extra linearly independent rows.
1671 static int compute_maxvar(struct isl_sched_graph *graph)
1673 int i;
1675 graph->maxvar = 0;
1676 for (i = 0; i < graph->n; ++i) {
1677 struct isl_sched_node *node = &graph->node[i];
1678 int nvar;
1680 if (node_update_cmap(node) < 0)
1681 return -1;
1682 nvar = node->nvar + graph->n_row - node->rank;
1683 if (nvar > graph->maxvar)
1684 graph->maxvar = nvar;
1687 return 0;
1690 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1691 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1693 /* Compute a schedule for a subgraph of "graph". In particular, for
1694 * the graph composed of nodes that satisfy node_pred and edges that
1695 * that satisfy edge_pred. The caller should precompute the number
1696 * of nodes and edges that satisfy these predicates and pass them along
1697 * as "n" and "n_edge".
1698 * If the subgraph is known to consist of a single component, then wcc should
1699 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1700 * Otherwise, we call compute_schedule, which will check whether the subgraph
1701 * is connected.
1703 static int compute_sub_schedule(isl_ctx *ctx,
1704 struct isl_sched_graph *graph, int n, int n_edge,
1705 int (*node_pred)(struct isl_sched_node *node, int data),
1706 int (*edge_pred)(struct isl_sched_edge *edge, int data),
1707 int data, int wcc)
1709 struct isl_sched_graph split = { 0 };
1711 if (graph_alloc(ctx, &split, n, n_edge) < 0)
1712 goto error;
1713 if (copy_nodes(&split, graph, node_pred, data) < 0)
1714 goto error;
1715 if (graph_init_table(ctx, &split) < 0)
1716 goto error;
1717 if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1718 goto error;
1719 if (graph_init_edge_table(ctx, &split) < 0)
1720 goto error;
1721 split.n_row = graph->n_row;
1722 split.n_total_row = graph->n_total_row;
1723 split.n_band = graph->n_band;
1724 split.band_start = graph->band_start;
1726 if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1727 goto error;
1728 if (!wcc && compute_schedule(ctx, &split) < 0)
1729 goto error;
1731 copy_schedule(graph, &split, node_pred, data);
1733 graph_free(ctx, &split);
1734 return 0;
1735 error:
1736 graph_free(ctx, &split);
1737 return -1;
1740 static int node_scc_exactly(struct isl_sched_node *node, int scc)
1742 return node->scc == scc;
1745 static int node_scc_at_most(struct isl_sched_node *node, int scc)
1747 return node->scc <= scc;
1750 static int node_scc_at_least(struct isl_sched_node *node, int scc)
1752 return node->scc >= scc;
1755 static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc)
1757 return edge->src->scc == scc;
1760 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
1762 return edge->dst->scc <= scc;
1765 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
1767 return edge->src->scc >= scc;
1770 /* Pad the schedules of all nodes with zero rows such that in the end
1771 * they all have graph->n_total_row rows.
1772 * The extra rows don't belong to any band, so they get assigned band number -1.
1774 static int pad_schedule(struct isl_sched_graph *graph)
1776 int i, j;
1778 for (i = 0; i < graph->n; ++i) {
1779 struct isl_sched_node *node = &graph->node[i];
1780 int row = isl_mat_rows(node->sched);
1781 if (graph->n_total_row > row) {
1782 isl_map_free(node->sched_map);
1783 node->sched_map = NULL;
1785 node->sched = isl_mat_add_zero_rows(node->sched,
1786 graph->n_total_row - row);
1787 if (!node->sched)
1788 return -1;
1789 for (j = row; j < graph->n_total_row; ++j)
1790 node->band[j] = -1;
1793 return 0;
1796 /* Split the current graph into two parts and compute a schedule for each
1797 * part individually. In particular, one part consists of all SCCs up
1798 * to and including graph->src_scc, while the other part contains the other
1799 * SCCS.
1801 * The split is enforced in the schedule by constant rows with two different
1802 * values (0 and 1). These constant rows replace the previously computed rows
1803 * in the current band.
1804 * It would be possible to reuse them as the first rows in the next
1805 * band, but recomputing them may result in better rows as we are looking
1806 * at a smaller part of the dependence graph.
1808 * The band_id of the second group is set to n, where n is the number
1809 * of nodes in the first group. This ensures that the band_ids over
1810 * the two groups remain disjoint, even if either or both of the two
1811 * groups contain independent components.
1813 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
1815 int i, j, n, e1, e2;
1816 int n_total_row, orig_total_row;
1817 int n_band, orig_band;
1818 int drop;
1820 drop = graph->n_total_row - graph->band_start;
1821 graph->n_total_row -= drop;
1822 graph->n_row -= drop;
1824 n = 0;
1825 for (i = 0; i < graph->n; ++i) {
1826 struct isl_sched_node *node = &graph->node[i];
1827 int row = isl_mat_rows(node->sched) - drop;
1828 int cols = isl_mat_cols(node->sched);
1829 int before = node->scc <= graph->src_scc;
1831 if (before)
1832 n++;
1834 isl_map_free(node->sched_map);
1835 node->sched_map = NULL;
1836 node->sched = isl_mat_drop_rows(node->sched,
1837 graph->band_start, drop);
1838 node->sched = isl_mat_add_rows(node->sched, 1);
1839 if (!node->sched)
1840 return -1;
1841 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1842 !before);
1843 for (j = 1; j < cols; ++j)
1844 node->sched = isl_mat_set_element_si(node->sched,
1845 row, j, 0);
1846 node->band[graph->n_total_row] = graph->n_band;
1849 e1 = e2 = 0;
1850 for (i = 0; i < graph->n_edge; ++i) {
1851 if (graph->edge[i].dst->scc <= graph->src_scc)
1852 e1++;
1853 if (graph->edge[i].src->scc > graph->src_scc)
1854 e2++;
1857 graph->n_total_row++;
1858 next_band(graph);
1860 for (i = 0; i < graph->n; ++i) {
1861 struct isl_sched_node *node = &graph->node[i];
1862 if (node->scc > graph->src_scc)
1863 node->band_id[graph->n_band] = n;
1866 orig_total_row = graph->n_total_row;
1867 orig_band = graph->n_band;
1868 if (compute_sub_schedule(ctx, graph, n, e1,
1869 &node_scc_at_most, &edge_dst_scc_at_most,
1870 graph->src_scc, 0) < 0)
1871 return -1;
1872 n_total_row = graph->n_total_row;
1873 graph->n_total_row = orig_total_row;
1874 n_band = graph->n_band;
1875 graph->n_band = orig_band;
1876 if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
1877 &node_scc_at_least, &edge_src_scc_at_least,
1878 graph->src_scc + 1, 0) < 0)
1879 return -1;
1880 if (n_total_row > graph->n_total_row)
1881 graph->n_total_row = n_total_row;
1882 if (n_band > graph->n_band)
1883 graph->n_band = n_band;
1885 return pad_schedule(graph);
1888 /* Compute the next band of the schedule after updating the dependence
1889 * relations based on the the current schedule.
1891 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
1893 if (update_edges(ctx, graph) < 0)
1894 return -1;
1895 next_band(graph);
1897 return compute_schedule(ctx, graph);
1900 /* Add constraints to graph->lp that force the dependence of edge i
1901 * to be respected and attempt to carry it, where edge i is one from
1902 * a node j to itself.
1903 * That is, add constraints that enforce
1905 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
1906 * = c_j_x (y - x) >= e_i
1908 * for each (x,y) in R.
1909 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1910 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
1911 * with each coefficient in c_j_x represented as a pair of non-negative
1912 * coefficients.
1914 static int add_intra_constraints(struct isl_sched_graph *graph, int i)
1916 unsigned total;
1917 struct isl_sched_edge *edge= &graph->edge[i];
1918 isl_map *map = isl_map_copy(edge->map);
1919 isl_ctx *ctx = isl_map_get_ctx(map);
1920 isl_dim *dim;
1921 isl_dim_map *dim_map;
1922 isl_basic_set *coef;
1923 struct isl_sched_node *node = edge->src;
1925 coef = intra_coefficients(graph, map);
1927 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
1929 total = isl_basic_set_total_dim(graph->lp);
1930 dim_map = isl_dim_map_alloc(ctx, total);
1931 isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1);
1932 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1933 isl_dim_size(dim, isl_dim_set), 1,
1934 node->nvar, -1);
1935 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1936 isl_dim_size(dim, isl_dim_set), 1,
1937 node->nvar, 1);
1938 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1939 coef->n_eq, coef->n_ineq);
1940 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1941 coef, dim_map);
1942 isl_dim_free(dim);
1944 return 0;
1947 /* Add constraints to graph->lp that force the dependence of edge i
1948 * to be respected and attempt to carry it, where edge i is one from
1949 * node j to node k.
1950 * That is, add constraints that enforce
1952 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
1954 * for each (x,y) in R.
1955 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1956 * of valid constraints for R and then plug in
1957 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
1958 * with each coefficient (except e_i, c_k_0 and c_j_0)
1959 * represented as a pair of non-negative coefficients.
1961 static int add_inter_constraints(struct isl_sched_graph *graph, int i)
1963 unsigned total;
1964 struct isl_sched_edge *edge= &graph->edge[i];
1965 isl_map *map = isl_map_copy(edge->map);
1966 isl_ctx *ctx = isl_map_get_ctx(map);
1967 isl_dim *dim;
1968 isl_dim_map *dim_map;
1969 isl_basic_set *coef;
1970 struct isl_sched_node *src = edge->src;
1971 struct isl_sched_node *dst = edge->dst;
1973 coef = inter_coefficients(graph, map);
1975 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
1977 total = isl_basic_set_total_dim(graph->lp);
1978 dim_map = isl_dim_map_alloc(ctx, total);
1980 isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1);
1982 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
1983 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
1984 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
1985 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1986 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
1987 dst->nvar, -1);
1988 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1989 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
1990 dst->nvar, 1);
1992 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
1993 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
1994 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
1995 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1996 isl_dim_size(dim, isl_dim_set), 1,
1997 src->nvar, 1);
1998 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1999 isl_dim_size(dim, isl_dim_set), 1,
2000 src->nvar, -1);
2002 graph->lp = isl_basic_set_extend_constraints(graph->lp,
2003 coef->n_eq, coef->n_ineq);
2004 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2005 coef, dim_map);
2006 isl_dim_free(dim);
2008 return 0;
2011 /* Add constraints to graph->lp that force all dependence
2012 * to be respected and attempt to carry it.
2014 static int add_all_constraints(struct isl_sched_graph *graph)
2016 int i;
2018 for (i = 0; i < graph->n_edge; ++i) {
2019 struct isl_sched_edge *edge= &graph->edge[i];
2020 if (edge->src == edge->dst &&
2021 add_intra_constraints(graph, i) < 0)
2022 return -1;
2023 if (edge->src != edge->dst &&
2024 add_inter_constraints(graph, i) < 0)
2025 return -1;
2028 return 0;
2031 /* Construct an LP problem for finding schedule coefficients
2032 * such that the schedule carries as many dependences as possible.
2033 * In particular, for each dependence i, we bound the dependence distance
2034 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2035 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2036 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2038 * All variables of the LP are non-negative. The actual coefficients
2039 * may be negative, so each coefficient is represented as the difference
2040 * of two non-negative variables. The negative part always appears
2041 * immediately before the positive part.
2042 * Other than that, the variables have the following order
2044 * - sum of (1 - e_i) over all edges
2045 * - sum of positive and negative parts of all c_n coefficients
2046 * (unconstrained when computing non-parametric schedules)
2047 * - sum of positive and negative parts of all c_x coefficients
2048 * - for each edge
2049 * - e_i
2050 * - for each node
2051 * - c_i_0
2052 * - positive and negative parts of c_i_n (if parametric)
2053 * - positive and negative parts of c_i_x
2055 * The constraints are those from the edges plus three equalities
2056 * to express the sums and n_edge inequalities to express e_i <= 1.
2058 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2060 int i, j;
2061 int k;
2062 isl_dim *dim;
2063 unsigned total;
2064 int n_eq, n_ineq;
2066 total = 3 + graph->n_edge;
2067 for (i = 0; i < graph->n; ++i) {
2068 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2069 node->start = total;
2070 total += 1 + 2 * (node->nparam + node->nvar);
2073 if (count_constraints(graph, &n_eq, &n_ineq, 1) < 0)
2074 return -1;
2076 dim = isl_dim_set_alloc(ctx, 0, total);
2077 isl_basic_set_free(graph->lp);
2078 n_eq += 3;
2079 n_ineq += graph->n_edge;
2080 graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq);
2081 graph->lp = isl_basic_set_set_rational(graph->lp);
2083 k = isl_basic_set_alloc_equality(graph->lp);
2084 if (k < 0)
2085 return -1;
2086 isl_seq_clr(graph->lp->eq[k], 1 + total);
2087 isl_int_set_si(graph->lp->eq[k][0], -graph->n_edge);
2088 isl_int_set_si(graph->lp->eq[k][1], 1);
2089 for (i = 0; i < graph->n_edge; ++i)
2090 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2092 k = isl_basic_set_alloc_equality(graph->lp);
2093 if (k < 0)
2094 return -1;
2095 isl_seq_clr(graph->lp->eq[k], 1 + total);
2096 isl_int_set_si(graph->lp->eq[k][2], -1);
2097 for (i = 0; i < graph->n; ++i) {
2098 int pos = 1 + graph->node[i].start + 1;
2100 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2101 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2104 k = isl_basic_set_alloc_equality(graph->lp);
2105 if (k < 0)
2106 return -1;
2107 isl_seq_clr(graph->lp->eq[k], 1 + total);
2108 isl_int_set_si(graph->lp->eq[k][3], -1);
2109 for (i = 0; i < graph->n; ++i) {
2110 struct isl_sched_node *node = &graph->node[i];
2111 int pos = 1 + node->start + 1 + 2 * node->nparam;
2113 for (j = 0; j < 2 * node->nvar; ++j)
2114 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2117 for (i = 0; i < graph->n_edge; ++i) {
2118 k = isl_basic_set_alloc_inequality(graph->lp);
2119 if (k < 0)
2120 return -1;
2121 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2122 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2123 isl_int_set_si(graph->lp->ineq[k][0], 1);
2126 if (add_all_constraints(graph) < 0)
2127 return -1;
2129 return 0;
2132 /* If the schedule_split_parallel option is set and if the linear
2133 * parts of the scheduling rows for all nodes in the graphs are the same,
2134 * then split off the constant term from the linear part.
2135 * The constant term is then placed in a separate band and
2136 * the linear part is simplified.
2138 static int split_parallel(isl_ctx *ctx, struct isl_sched_graph *graph)
2140 int i;
2141 int equal = 1;
2142 int row, cols;
2143 struct isl_sched_node *node0;
2145 if (!ctx->opt->schedule_split_parallel)
2146 return 0;
2147 if (graph->n <= 1)
2148 return 0;
2150 node0 = &graph->node[0];
2151 row = isl_mat_rows(node0->sched) - 1;
2152 cols = isl_mat_cols(node0->sched);
2153 for (i = 1; i < graph->n; ++i) {
2154 struct isl_sched_node *node = &graph->node[i];
2156 if (!isl_seq_eq(node0->sched->row[row] + 1,
2157 node->sched->row[row] + 1, cols - 1))
2158 return 0;
2159 if (equal &&
2160 isl_int_ne(node0->sched->row[row][0],
2161 node->sched->row[row][0]))
2162 equal = 0;
2164 if (equal)
2165 return 0;
2167 next_band(graph);
2169 for (i = 0; i < graph->n; ++i) {
2170 struct isl_sched_node *node = &graph->node[i];
2172 isl_map_free(node->sched_map);
2173 node->sched_map = NULL;
2174 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2175 if (!node->sched)
2176 return -1;
2177 isl_int_set(node->sched->row[row + 1][0],
2178 node->sched->row[row][0]);
2179 isl_int_set_si(node->sched->row[row][0], 0);
2180 node->sched = isl_mat_normalize_row(node->sched, row);
2181 if (!node->sched)
2182 return -1;
2183 node->band[graph->n_total_row] = graph->n_band;
2186 graph->n_total_row++;
2188 return 0;
2191 /* Construct a schedule row for each node such that as many dependences
2192 * as possible are carried and then continue with the next band.
2194 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2196 isl_vec *sol;
2197 isl_basic_set *lp;
2199 if (setup_carry_lp(ctx, graph) < 0)
2200 return -1;
2202 lp = isl_basic_set_copy(graph->lp);
2203 sol = isl_tab_basic_set_non_neg_lexmin(lp);
2204 if (!sol)
2205 return -1;
2207 if (sol->size == 0) {
2208 isl_vec_free(sol);
2209 isl_die(ctx, isl_error_internal,
2210 "error in schedule construction", return -1);
2213 if (isl_int_cmp_si(sol->el[1], graph->n_edge) >= 0) {
2214 isl_vec_free(sol);
2215 isl_die(ctx, isl_error_unknown,
2216 "unable to carry dependences", return -1);
2219 if (update_schedule(graph, sol, 0, 0) < 0)
2220 return -1;
2222 if (split_parallel(ctx, graph) < 0)
2223 return -1;
2225 return compute_next_band(ctx, graph);
2228 /* Compute a schedule for a connected dependence graph.
2229 * We try to find a sequence of as many schedule rows as possible that result
2230 * in non-negative dependence distances (independent of the previous rows
2231 * in the sequence, i.e., such that the sequence is tilable).
2232 * If we can't find any more rows we either
2233 * - split between SCCs and start over (assuming we found an interesting
2234 * pair of SCCs between which to split)
2235 * - continue with the next band (assuming the current band has at least
2236 * one row)
2237 * - try to carry as many dependences as possible and continue with the next
2238 * band
2240 * If we manage to complete the schedule, we finish off by topologically
2241 * sorting the statements based on the remaining dependences.
2243 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2244 * outermost dimension in the current band to be zero distance. If this
2245 * turns out to be impossible, we fall back on the general scheme above
2246 * and try to carry as many dependences as possible.
2248 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2250 int force_zero = 0;
2252 if (detect_sccs(graph) < 0)
2253 return -1;
2254 sort_sccs(graph);
2256 if (compute_maxvar(graph) < 0)
2257 return -1;
2259 if (ctx->opt->schedule_outer_zero_distance)
2260 force_zero = 1;
2262 while (graph->n_row < graph->maxvar) {
2263 isl_vec *sol;
2265 graph->src_scc = -1;
2266 graph->dst_scc = -1;
2268 if (setup_lp(ctx, graph, force_zero) < 0)
2269 return -1;
2270 sol = solve_lp(graph);
2271 if (!sol)
2272 return -1;
2273 if (sol->size == 0) {
2274 isl_vec_free(sol);
2275 if (graph->src_scc >= 0)
2276 return compute_split_schedule(ctx, graph);
2277 if (graph->n_total_row > graph->band_start)
2278 return compute_next_band(ctx, graph);
2279 return carry_dependences(ctx, graph);
2281 if (update_schedule(graph, sol, 1, 1) < 0)
2282 return -1;
2283 force_zero = 0;
2286 if (graph->n_total_row > graph->band_start)
2287 next_band(graph);
2288 return sort_statements(ctx, graph);
2291 /* Compute a schedule for each component (identified by node->scc)
2292 * of the dependence graph separately and then combine the results.
2294 * The band_id is adjusted such that each component has a separate id.
2295 * Note that the band_id may have already been set to a value different
2296 * from zero by compute_split_schedule.
2298 static int compute_component_schedule(isl_ctx *ctx,
2299 struct isl_sched_graph *graph)
2301 int wcc, i;
2302 int n, n_edge;
2303 int n_total_row, orig_total_row;
2304 int n_band, orig_band;
2306 n_total_row = 0;
2307 orig_total_row = graph->n_total_row;
2308 n_band = 0;
2309 orig_band = graph->n_band;
2310 for (i = 0; i < graph->n; ++i)
2311 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2312 for (wcc = 0; wcc < graph->scc; ++wcc) {
2313 n = 0;
2314 for (i = 0; i < graph->n; ++i)
2315 if (graph->node[i].scc == wcc)
2316 n++;
2317 n_edge = 0;
2318 for (i = 0; i < graph->n_edge; ++i)
2319 if (graph->edge[i].src->scc == wcc)
2320 n_edge++;
2322 if (compute_sub_schedule(ctx, graph, n, n_edge,
2323 &node_scc_exactly,
2324 &edge_src_scc_exactly, wcc, 1) < 0)
2325 return -1;
2326 if (graph->n_total_row > n_total_row)
2327 n_total_row = graph->n_total_row;
2328 graph->n_total_row = orig_total_row;
2329 if (graph->n_band > n_band)
2330 n_band = graph->n_band;
2331 graph->n_band = orig_band;
2334 graph->n_total_row = n_total_row;
2335 graph->n_band = n_band;
2337 return pad_schedule(graph);
2340 /* Compute a schedule for the given dependence graph.
2341 * We first check if the graph is connected (through validity dependences)
2342 * and if so compute a schedule for each component separately.
2344 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2346 if (detect_wccs(graph) < 0)
2347 return -1;
2349 if (graph->scc > 1)
2350 return compute_component_schedule(ctx, graph);
2352 return compute_schedule_wcc(ctx, graph);
2355 /* Compute a schedule for the given union of domains that respects
2356 * all the validity dependences and tries to minimize the dependence
2357 * distances over the proximity dependences.
2359 __isl_give isl_schedule *isl_union_set_compute_schedule(
2360 __isl_take isl_union_set *domain,
2361 __isl_take isl_union_map *validity,
2362 __isl_take isl_union_map *proximity)
2364 isl_ctx *ctx = isl_union_set_get_ctx(domain);
2365 isl_dim *dim;
2366 struct isl_sched_graph graph = { 0 };
2367 isl_schedule *sched;
2369 domain = isl_union_set_align_params(domain,
2370 isl_union_map_get_dim(validity));
2371 domain = isl_union_set_align_params(domain,
2372 isl_union_map_get_dim(proximity));
2373 dim = isl_union_set_get_dim(domain);
2374 validity = isl_union_map_align_params(validity, isl_dim_copy(dim));
2375 proximity = isl_union_map_align_params(proximity, dim);
2377 if (!domain)
2378 goto error;
2380 graph.n = isl_union_set_n_set(domain);
2381 if (graph.n == 0)
2382 goto empty;
2383 if (graph_alloc(ctx, &graph, graph.n,
2384 isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2385 goto error;
2386 graph.root = 1;
2387 graph.n = 0;
2388 if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2389 goto error;
2390 if (graph_init_table(ctx, &graph) < 0)
2391 goto error;
2392 graph.n_edge = 0;
2393 if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0)
2394 goto error;
2395 if (graph_init_edge_table(ctx, &graph) < 0)
2396 goto error;
2397 if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0)
2398 goto error;
2400 if (compute_schedule(ctx, &graph) < 0)
2401 goto error;
2403 empty:
2404 sched = extract_schedule(&graph, isl_union_set_get_dim(domain));
2406 graph_free(ctx, &graph);
2407 isl_union_set_free(domain);
2408 isl_union_map_free(validity);
2409 isl_union_map_free(proximity);
2411 return sched;
2412 error:
2413 graph_free(ctx, &graph);
2414 isl_union_set_free(domain);
2415 isl_union_map_free(validity);
2416 isl_union_map_free(proximity);
2417 return NULL;
2420 void *isl_schedule_free(__isl_take isl_schedule *sched)
2422 int i;
2423 if (!sched)
2424 return NULL;
2426 if (--sched->ref > 0)
2427 return NULL;
2429 for (i = 0; i < sched->n; ++i) {
2430 isl_map_free(sched->node[i].sched);
2431 free(sched->node[i].band_end);
2432 free(sched->node[i].band_id);
2433 free(sched->node[i].zero);
2435 isl_dim_free(sched->dim);
2436 isl_band_list_free(sched->band_forest);
2437 free(sched);
2438 return NULL;
2441 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2443 return schedule ? isl_dim_get_ctx(schedule->dim) : NULL;
2446 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2448 int i;
2449 isl_union_map *umap;
2451 if (!sched)
2452 return NULL;
2454 umap = isl_union_map_empty(isl_dim_copy(sched->dim));
2455 for (i = 0; i < sched->n; ++i)
2456 umap = isl_union_map_add_map(umap,
2457 isl_map_copy(sched->node[i].sched));
2459 return umap;
2462 int isl_schedule_n_band(__isl_keep isl_schedule *sched)
2464 return sched ? sched->n_band : 0;
2467 /* Construct a mapping that maps each domain to the band in its schedule
2468 * with the specified band index. Note that bands with the same index
2469 * but for different domains do not need to be related.
2471 __isl_give isl_union_map *isl_schedule_get_band(__isl_keep isl_schedule *sched,
2472 unsigned band)
2474 int i;
2475 isl_union_map *umap;
2477 if (!sched)
2478 return NULL;
2480 umap = isl_union_map_empty(isl_dim_copy(sched->dim));
2481 for (i = 0; i < sched->n; ++i) {
2482 int start, end;
2483 isl_map *map;
2485 if (band >= sched->node[i].n_band)
2486 continue;
2488 start = band > 0 ? sched->node[i].band_end[band - 1] : 0;
2489 end = sched->node[i].band_end[band];
2491 map = isl_map_copy(sched->node[i].sched);
2493 map = isl_map_project_out(map, isl_dim_out, end,
2494 sched->n_total_row - end);
2495 map = isl_map_project_out(map, isl_dim_out, 0, start);
2497 umap = isl_union_map_add_map(umap, map);
2500 return umap;
2503 static __isl_give isl_band_list *construct_band_list(
2504 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2505 int band_nr, int *parent_active, int n_active);
2507 /* Construct an isl_band structure for the band in the given schedule
2508 * with sequence number band_nr for the n_active nodes marked by active.
2509 * If the nodes don't have a band with the given sequence number,
2510 * then a band without members is created.
2512 * Because of the way the schedule is constructed, we know that
2513 * the position of the band inside the schedule of a node is the same
2514 * for all active nodes.
2516 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2517 __isl_keep isl_band *parent,
2518 int band_nr, int *active, int n_active)
2520 int i, j;
2521 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2522 isl_band *band;
2523 unsigned start, end;
2525 band = isl_calloc_type(ctx, isl_band);
2526 if (!band)
2527 return NULL;
2529 band->ref = 1;
2530 band->schedule = schedule;
2531 band->parent = parent;
2533 for (i = 0; i < schedule->n; ++i)
2534 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2535 break;
2537 if (i < schedule->n) {
2538 band->children = construct_band_list(schedule, band,
2539 band_nr + 1, active, n_active);
2540 if (!band->children)
2541 goto error;
2544 for (i = 0; i < schedule->n; ++i)
2545 if (active[i])
2546 break;
2548 if (i >= schedule->n)
2549 isl_die(ctx, isl_error_internal,
2550 "band without active statements", goto error);
2552 start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2553 end = band_nr < schedule->node[i].n_band ?
2554 schedule->node[i].band_end[band_nr] : start;
2555 band->n = end - start;
2557 band->zero = isl_alloc_array(ctx, int, band->n);
2558 if (!band->zero)
2559 goto error;
2561 for (j = 0; j < band->n; ++j)
2562 band->zero[j] = schedule->node[i].zero[start + j];
2564 band->map = isl_union_map_empty(isl_dim_copy(schedule->dim));
2565 for (i = 0; i < schedule->n; ++i) {
2566 isl_map *map;
2567 unsigned n_out;
2569 if (!active[i])
2570 continue;
2572 map = isl_map_copy(schedule->node[i].sched);
2573 n_out = isl_map_dim(map, isl_dim_out);
2574 map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
2575 map = isl_map_project_out(map, isl_dim_out, 0, start);
2576 band->map = isl_union_map_union(band->map,
2577 isl_union_map_from_map(map));
2579 if (!band->map)
2580 goto error;
2582 return band;
2583 error:
2584 isl_band_free(band);
2585 return NULL;
2588 /* Construct a list of bands that start at the same position (with
2589 * sequence number band_nr) in the schedules of the nodes that
2590 * were active in the parent band.
2592 * A separate isl_band structure is created for each band_id
2593 * and for each node that does not have a band with sequence
2594 * number band_nr. In the latter case, a band without members
2595 * is created.
2596 * This ensures that if a band has any children, then each node
2597 * that was active in the band is active in exactly one of the children.
2599 static __isl_give isl_band_list *construct_band_list(
2600 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2601 int band_nr, int *parent_active, int n_active)
2603 int i, j;
2604 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2605 int *active;
2606 int n_band;
2607 isl_band_list *list;
2609 n_band = 0;
2610 for (i = 0; i < n_active; ++i) {
2611 for (j = 0; j < schedule->n; ++j) {
2612 if (!parent_active[j])
2613 continue;
2614 if (schedule->node[j].n_band <= band_nr)
2615 continue;
2616 if (schedule->node[j].band_id[band_nr] == i) {
2617 n_band++;
2618 break;
2622 for (j = 0; j < schedule->n; ++j)
2623 if (schedule->node[j].n_band <= band_nr)
2624 n_band++;
2626 if (n_band == 1) {
2627 isl_band *band;
2628 list = isl_band_list_alloc(ctx, n_band);
2629 band = construct_band(schedule, parent, band_nr,
2630 parent_active, n_active);
2631 return isl_band_list_add(list, band);
2634 active = isl_alloc_array(ctx, int, schedule->n);
2635 if (!active)
2636 return NULL;
2638 list = isl_band_list_alloc(ctx, n_band);
2640 for (i = 0; i < n_active; ++i) {
2641 int n = 0;
2642 isl_band *band;
2644 for (j = 0; j < schedule->n; ++j) {
2645 active[j] = parent_active[j] &&
2646 schedule->node[j].n_band > band_nr &&
2647 schedule->node[j].band_id[band_nr] == i;
2648 if (active[j])
2649 n++;
2651 if (n == 0)
2652 continue;
2654 band = construct_band(schedule, parent, band_nr, active, n);
2656 list = isl_band_list_add(list, band);
2658 for (i = 0; i < schedule->n; ++i) {
2659 isl_band *band;
2660 if (!parent_active[i])
2661 continue;
2662 if (schedule->node[i].n_band > band_nr)
2663 continue;
2664 for (j = 0; j < schedule->n; ++j)
2665 active[j] = j == i;
2666 band = construct_band(schedule, parent, band_nr, active, 1);
2667 list = isl_band_list_add(list, band);
2670 free(active);
2672 return list;
2675 /* Construct a band forest representation of the schedule and
2676 * return the list of roots.
2678 static __isl_give isl_band_list *construct_forest(
2679 __isl_keep isl_schedule *schedule)
2681 int i;
2682 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2683 isl_band_list *forest;
2684 int *active;
2686 active = isl_alloc_array(ctx, int, schedule->n);
2687 if (!active)
2688 return NULL;
2690 for (i = 0; i < schedule->n; ++i)
2691 active[i] = 1;
2693 forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
2695 free(active);
2697 return forest;
2700 /* Return the roots of a band forest representation of the schedule.
2702 __isl_give isl_band_list *isl_schedule_get_band_forest(
2703 __isl_keep isl_schedule *schedule)
2705 if (!schedule)
2706 return NULL;
2707 if (!schedule->band_forest)
2708 schedule->band_forest = construct_forest(schedule);
2709 return isl_band_list_copy(schedule->band_forest);
2712 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2713 __isl_keep isl_band_list *list);
2715 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
2716 __isl_keep isl_band *band)
2718 isl_band_list *children;
2720 p = isl_printer_start_line(p);
2721 p = isl_printer_print_union_map(p, band->map);
2722 p = isl_printer_end_line(p);
2724 if (!isl_band_has_children(band))
2725 return p;
2727 children = isl_band_get_children(band);
2729 p = isl_printer_indent(p, 4);
2730 p = print_band_list(p, children);
2731 p = isl_printer_indent(p, -4);
2733 isl_band_list_free(children);
2735 return p;
2738 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2739 __isl_keep isl_band_list *list)
2741 int i, n;
2743 n = isl_band_list_n_band(list);
2744 for (i = 0; i < n; ++i) {
2745 isl_band *band;
2746 band = isl_band_list_get_band(list, i);
2747 p = print_band(p, band);
2748 isl_band_free(band);
2751 return p;
2754 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
2755 __isl_keep isl_schedule *schedule)
2757 isl_band_list *forest;
2759 forest = isl_schedule_get_band_forest(schedule);
2761 p = print_band_list(p, forest);
2763 isl_band_list_free(forest);
2765 return p;
2768 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
2770 isl_printer *printer;
2772 if (!schedule)
2773 return;
2775 printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
2776 printer = isl_printer_print_schedule(printer, schedule);
2778 isl_printer_free(printer);