add isl_band_dup
[isl.git] / isl_schedule.c
blobfe430d6e837b5f30e13f63e0b3c85939afc5ba7f
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_space_private.h>
14 #include <isl/aff.h>
15 #include <isl/hash.h>
16 #include <isl/constraint.h>
17 #include <isl/schedule.h>
18 #include <isl_mat_private.h>
19 #include <isl/set.h>
20 #include <isl/seq.h>
21 #include <isl_tab.h>
22 #include <isl_dim_map.h>
23 #include <isl_hmap_map_basic_set.h>
24 #include <isl_qsort.h>
25 #include <isl_schedule_private.h>
26 #include <isl_band_private.h>
27 #include <isl_list_private.h>
28 #include <isl_options_private.h>
31 * The scheduling algorithm implemented in this file was inspired by
32 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
33 * Parallelization and Locality Optimization in the Polyhedral Model".
37 /* Internal information about a node that is used during the construction
38 * of a schedule.
39 * dim represents the space in which the domain lives
40 * sched is a matrix representation of the schedule being constructed
41 * for this node
42 * sched_map is an isl_map representation of the same (partial) schedule
43 * sched_map may be NULL
44 * rank is the number of linearly independent rows in the linear part
45 * of sched
46 * the columns of cmap represent a change of basis for the schedule
47 * coefficients; the first rank columns span the linear part of
48 * the schedule rows
49 * start is the first variable in the LP problem in the sequences that
50 * represents the schedule coefficients of this node
51 * nvar is the dimension of the domain
52 * nparam is the number of parameters or 0 if we are not constructing
53 * a parametric schedule
55 * scc is the index of SCC (or WCC) this node belongs to
57 * band contains the band index for each of the rows of the schedule.
58 * band_id is used to differentiate between separate bands at the same
59 * level within the same parent band, i.e., bands that are separated
60 * by the parent band or bands that are independent of each other.
61 * zero contains a boolean for each of the rows of the schedule,
62 * indicating whether the corresponding scheduling dimension results
63 * in zero dependence distances within its band and with respect
64 * to the proximity edges.
66 * index, min_index and on_stack are used during the SCC detection
67 * index represents the order in which nodes are visited.
68 * min_index is the index of the root of a (sub)component.
69 * on_stack indicates whether the node is currently on the stack.
71 struct isl_sched_node {
72 isl_space *dim;
73 isl_mat *sched;
74 isl_map *sched_map;
75 int rank;
76 isl_mat *cmap;
77 int start;
78 int nvar;
79 int nparam;
81 int scc;
83 int *band;
84 int *band_id;
85 int *zero;
87 /* scc detection */
88 int index;
89 int min_index;
90 int on_stack;
93 static int node_has_dim(const void *entry, const void *val)
95 struct isl_sched_node *node = (struct isl_sched_node *)entry;
96 isl_space *dim = (isl_space *)val;
98 return isl_space_is_equal(node->dim, dim);
101 /* An edge in the dependence graph. An edge may be used to
102 * ensure validity of the generated schedule, to minimize the dependence
103 * distance or both
105 * map is the dependence relation
106 * src is the source node
107 * dst is the sink node
108 * validity is set if the edge is used to ensure correctness
109 * proximity is set if the edge is used to minimize dependence distances
111 * For validity edges, start and end mark the sequence of inequality
112 * constraints in the LP problem that encode the validity constraint
113 * corresponding to this edge.
115 struct isl_sched_edge {
116 isl_map *map;
118 struct isl_sched_node *src;
119 struct isl_sched_node *dst;
121 int validity;
122 int proximity;
124 int start;
125 int end;
128 enum isl_edge_type {
129 isl_edge_validity = 0,
130 isl_edge_proximity,
131 isl_edge_last = isl_edge_proximity
134 /* Internal information about the dependence graph used during
135 * the construction of the schedule.
137 * intra_hmap is a cache, mapping dependence relations to their dual,
138 * for dependences from a node to itself
139 * inter_hmap is a cache, mapping dependence relations to their dual,
140 * for dependences between distinct nodes
142 * n is the number of nodes
143 * node is the list of nodes
144 * maxvar is the maximal number of variables over all nodes
145 * n_row is the current (maximal) number of linearly independent
146 * rows in the node schedules
147 * n_total_row is the current number of rows in the node schedules
148 * n_band is the current number of completed bands
149 * band_start is the starting row in the node schedules of the current band
150 * root is set if this graph is the original dependence graph,
151 * without any splitting
153 * sorted contains a list of node indices sorted according to the
154 * SCC to which a node belongs
156 * n_edge is the number of edges
157 * edge is the list of edges
158 * max_edge contains the maximal number of edges of each type;
159 * in particular, it contains the number of edges in the inital graph.
160 * edge_table contains pointers into the edge array, hashed on the source
161 * and sink spaces; there is one such table for each type;
162 * a given edge may be referenced from more than one table
163 * if the corresponding relation appears in more than of the
164 * sets of dependences
166 * node_table contains pointers into the node array, hashed on the space
168 * region contains a list of variable sequences that should be non-trivial
170 * lp contains the (I)LP problem used to obtain new schedule rows
172 * src_scc and dst_scc are the source and sink SCCs of an edge with
173 * conflicting constraints
175 * scc, sp, index and stack are used during the detection of SCCs
176 * scc is the number of the next SCC
177 * stack contains the nodes on the path from the root to the current node
178 * sp is the stack pointer
179 * index is the index of the last node visited
181 struct isl_sched_graph {
182 isl_hmap_map_basic_set *intra_hmap;
183 isl_hmap_map_basic_set *inter_hmap;
185 struct isl_sched_node *node;
186 int n;
187 int maxvar;
188 int n_row;
190 int *sorted;
192 int n_band;
193 int n_total_row;
194 int band_start;
196 int root;
198 struct isl_sched_edge *edge;
199 int n_edge;
200 int max_edge[isl_edge_last + 1];
201 struct isl_hash_table *edge_table[isl_edge_last + 1];
203 struct isl_hash_table *node_table;
204 struct isl_region *region;
206 isl_basic_set *lp;
208 int src_scc;
209 int dst_scc;
211 /* scc detection */
212 int scc;
213 int sp;
214 int index;
215 int *stack;
218 /* Initialize node_table based on the list of nodes.
220 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
222 int i;
224 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
225 if (!graph->node_table)
226 return -1;
228 for (i = 0; i < graph->n; ++i) {
229 struct isl_hash_table_entry *entry;
230 uint32_t hash;
232 hash = isl_space_get_hash(graph->node[i].dim);
233 entry = isl_hash_table_find(ctx, graph->node_table, hash,
234 &node_has_dim,
235 graph->node[i].dim, 1);
236 if (!entry)
237 return -1;
238 entry->data = &graph->node[i];
241 return 0;
244 /* Return a pointer to the node that lives within the given space,
245 * or NULL if there is no such node.
247 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
248 struct isl_sched_graph *graph, __isl_keep isl_space *dim)
250 struct isl_hash_table_entry *entry;
251 uint32_t hash;
253 hash = isl_space_get_hash(dim);
254 entry = isl_hash_table_find(ctx, graph->node_table, hash,
255 &node_has_dim, dim, 0);
257 return entry ? entry->data : NULL;
260 static int edge_has_src_and_dst(const void *entry, const void *val)
262 const struct isl_sched_edge *edge = entry;
263 const struct isl_sched_edge *temp = val;
265 return edge->src == temp->src && edge->dst == temp->dst;
268 /* Add the given edge to graph->edge_table[type].
270 static int graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph,
271 enum isl_edge_type type, struct isl_sched_edge *edge)
273 struct isl_hash_table_entry *entry;
274 uint32_t hash;
276 hash = isl_hash_init();
277 hash = isl_hash_builtin(hash, edge->src);
278 hash = isl_hash_builtin(hash, edge->dst);
279 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
280 &edge_has_src_and_dst, edge, 1);
281 if (!entry)
282 return -1;
283 entry->data = edge;
285 return 0;
288 /* Allocate the edge_tables based on the maximal number of edges of
289 * each type.
291 static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
293 int i;
295 for (i = 0; i <= isl_edge_last; ++i) {
296 graph->edge_table[i] = isl_hash_table_alloc(ctx,
297 graph->max_edge[i]);
298 if (!graph->edge_table[i])
299 return -1;
302 return 0;
305 /* If graph->edge_table[type] contains an edge from the given source
306 * to the given destination, then return the hash table entry of this edge.
307 * Otherwise, return NULL.
309 static struct isl_hash_table_entry *graph_find_edge_entry(
310 struct isl_sched_graph *graph,
311 enum isl_edge_type type,
312 struct isl_sched_node *src, struct isl_sched_node *dst)
314 isl_ctx *ctx = isl_space_get_ctx(src->dim);
315 uint32_t hash;
316 struct isl_sched_edge temp = { .src = src, .dst = dst };
318 hash = isl_hash_init();
319 hash = isl_hash_builtin(hash, temp.src);
320 hash = isl_hash_builtin(hash, temp.dst);
321 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
322 &edge_has_src_and_dst, &temp, 0);
326 /* If graph->edge_table[type] contains an edge from the given source
327 * to the given destination, then return this edge.
328 * Otherwise, return NULL.
330 static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
331 enum isl_edge_type type,
332 struct isl_sched_node *src, struct isl_sched_node *dst)
334 struct isl_hash_table_entry *entry;
336 entry = graph_find_edge_entry(graph, type, src, dst);
337 if (!entry)
338 return NULL;
340 return entry->data;
343 /* Check whether the dependence graph has an edge of the give type
344 * between the given two nodes.
346 static int graph_has_edge(struct isl_sched_graph *graph,
347 enum isl_edge_type type,
348 struct isl_sched_node *src, struct isl_sched_node *dst)
350 struct isl_sched_edge *edge;
351 int empty;
353 edge = graph_find_edge(graph, type, src, dst);
354 if (!edge)
355 return 0;
357 empty = isl_map_plain_is_empty(edge->map);
358 if (empty < 0)
359 return -1;
361 return !empty;
364 /* If there is an edge from the given source to the given destination
365 * of any type then return this edge.
366 * Otherwise, return NULL.
368 static struct isl_sched_edge *graph_find_any_edge(struct isl_sched_graph *graph,
369 struct isl_sched_node *src, struct isl_sched_node *dst)
371 int i;
372 struct isl_sched_edge *edge;
374 for (i = 0; i <= isl_edge_last; ++i) {
375 edge = graph_find_edge(graph, i, src, dst);
376 if (edge)
377 return edge;
380 return NULL;
383 /* Remove the given edge from all the edge_tables that refer to it.
385 static void graph_remove_edge(struct isl_sched_graph *graph,
386 struct isl_sched_edge *edge)
388 isl_ctx *ctx = isl_map_get_ctx(edge->map);
389 int i;
391 for (i = 0; i <= isl_edge_last; ++i) {
392 struct isl_hash_table_entry *entry;
394 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
395 if (!entry)
396 continue;
397 if (entry->data != edge)
398 continue;
399 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
403 /* Check whether the dependence graph has any edge
404 * between the given two nodes.
406 static int graph_has_any_edge(struct isl_sched_graph *graph,
407 struct isl_sched_node *src, struct isl_sched_node *dst)
409 int i;
410 int r;
412 for (i = 0; i <= isl_edge_last; ++i) {
413 r = graph_has_edge(graph, i, src, dst);
414 if (r < 0 || r)
415 return r;
418 return r;
421 /* Check whether the dependence graph has a validity edge
422 * between the given two nodes.
424 static int graph_has_validity_edge(struct isl_sched_graph *graph,
425 struct isl_sched_node *src, struct isl_sched_node *dst)
427 return graph_has_edge(graph, isl_edge_validity, src, dst);
430 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
431 int n_node, int n_edge)
433 int i;
435 graph->n = n_node;
436 graph->n_edge = n_edge;
437 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
438 graph->sorted = isl_calloc_array(ctx, int, graph->n);
439 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
440 graph->stack = isl_alloc_array(ctx, int, graph->n);
441 graph->edge = isl_calloc_array(ctx,
442 struct isl_sched_edge, graph->n_edge);
444 graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
445 graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
447 if (!graph->node || !graph->region || !graph->stack || !graph->edge ||
448 !graph->sorted)
449 return -1;
451 for(i = 0; i < graph->n; ++i)
452 graph->sorted[i] = i;
454 return 0;
457 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
459 int i;
461 isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
462 isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
464 for (i = 0; i < graph->n; ++i) {
465 isl_space_free(graph->node[i].dim);
466 isl_mat_free(graph->node[i].sched);
467 isl_map_free(graph->node[i].sched_map);
468 isl_mat_free(graph->node[i].cmap);
469 if (graph->root) {
470 free(graph->node[i].band);
471 free(graph->node[i].band_id);
472 free(graph->node[i].zero);
475 free(graph->node);
476 free(graph->sorted);
477 for (i = 0; i < graph->n_edge; ++i)
478 isl_map_free(graph->edge[i].map);
479 free(graph->edge);
480 free(graph->region);
481 free(graph->stack);
482 for (i = 0; i <= isl_edge_last; ++i)
483 isl_hash_table_free(ctx, graph->edge_table[i]);
484 isl_hash_table_free(ctx, graph->node_table);
485 isl_basic_set_free(graph->lp);
488 /* Add a new node to the graph representing the given set.
490 static int extract_node(__isl_take isl_set *set, void *user)
492 int nvar, nparam;
493 isl_ctx *ctx;
494 isl_space *dim;
495 isl_mat *sched;
496 struct isl_sched_graph *graph = user;
497 int *band, *band_id, *zero;
499 ctx = isl_set_get_ctx(set);
500 dim = isl_set_get_space(set);
501 isl_set_free(set);
502 nvar = isl_space_dim(dim, isl_dim_set);
503 nparam = isl_space_dim(dim, isl_dim_param);
504 if (!ctx->opt->schedule_parametric)
505 nparam = 0;
506 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
507 graph->node[graph->n].dim = dim;
508 graph->node[graph->n].nvar = nvar;
509 graph->node[graph->n].nparam = nparam;
510 graph->node[graph->n].sched = sched;
511 graph->node[graph->n].sched_map = NULL;
512 band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
513 graph->node[graph->n].band = band;
514 band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
515 graph->node[graph->n].band_id = band_id;
516 zero = isl_calloc_array(ctx, int, graph->n_edge + nvar);
517 graph->node[graph->n].zero = zero;
518 graph->n++;
520 if (!sched || !band || !band_id || !zero)
521 return -1;
523 return 0;
526 struct isl_extract_edge_data {
527 enum isl_edge_type type;
528 struct isl_sched_graph *graph;
531 /* Add a new edge to the graph based on the given map
532 * and add it to data->graph->edge_table[data->type].
533 * If a dependence relation of a given type happens to be identical
534 * to one of the dependence relations of a type that was added before,
535 * then we don't create a new edge, but instead mark the original edge
536 * as also representing a dependence of the current type.
538 static int extract_edge(__isl_take isl_map *map, void *user)
540 isl_ctx *ctx = isl_map_get_ctx(map);
541 struct isl_extract_edge_data *data = user;
542 struct isl_sched_graph *graph = data->graph;
543 struct isl_sched_node *src, *dst;
544 isl_space *dim;
545 struct isl_sched_edge *edge;
546 int is_equal;
548 dim = isl_space_domain(isl_map_get_space(map));
549 src = graph_find_node(ctx, graph, dim);
550 isl_space_free(dim);
551 dim = isl_space_range(isl_map_get_space(map));
552 dst = graph_find_node(ctx, graph, dim);
553 isl_space_free(dim);
555 if (!src || !dst) {
556 isl_map_free(map);
557 return 0;
560 graph->edge[graph->n_edge].src = src;
561 graph->edge[graph->n_edge].dst = dst;
562 graph->edge[graph->n_edge].map = map;
563 if (data->type == isl_edge_validity) {
564 graph->edge[graph->n_edge].validity = 1;
565 graph->edge[graph->n_edge].proximity = 0;
567 if (data->type == isl_edge_proximity) {
568 graph->edge[graph->n_edge].validity = 0;
569 graph->edge[graph->n_edge].proximity = 1;
571 graph->n_edge++;
573 edge = graph_find_any_edge(graph, src, dst);
574 if (!edge)
575 return graph_edge_table_add(ctx, graph, data->type,
576 &graph->edge[graph->n_edge - 1]);
577 is_equal = isl_map_plain_is_equal(map, edge->map);
578 if (is_equal < 0)
579 return -1;
580 if (!is_equal)
581 return graph_edge_table_add(ctx, graph, data->type,
582 &graph->edge[graph->n_edge - 1]);
584 graph->n_edge--;
585 edge->validity |= graph->edge[graph->n_edge].validity;
586 edge->proximity |= graph->edge[graph->n_edge].proximity;
587 isl_map_free(map);
589 return graph_edge_table_add(ctx, graph, data->type, edge);
592 /* Check whether there is a validity dependence from src to dst,
593 * forcing dst to follow src (if weak is not set).
594 * If weak is set, then check if there is any dependence from src to dst.
596 static int node_follows(struct isl_sched_graph *graph,
597 struct isl_sched_node *dst, struct isl_sched_node *src, int weak)
599 if (weak)
600 return graph_has_any_edge(graph, src, dst);
601 else
602 return graph_has_validity_edge(graph, src, dst);
605 /* Perform Tarjan's algorithm for computing the strongly connected components
606 * in the dependence graph (only validity edges).
607 * If weak is set, we consider the graph to be undirected and
608 * we effectively compute the (weakly) connected components.
609 * Additionally, we also consider other edges when weak is set.
611 static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int weak)
613 int j;
615 g->node[i].index = g->index;
616 g->node[i].min_index = g->index;
617 g->node[i].on_stack = 1;
618 g->index++;
619 g->stack[g->sp++] = i;
621 for (j = g->n - 1; j >= 0; --j) {
622 int f;
624 if (j == i)
625 continue;
626 if (g->node[j].index >= 0 &&
627 (!g->node[j].on_stack ||
628 g->node[j].index > g->node[i].min_index))
629 continue;
631 f = node_follows(g, &g->node[i], &g->node[j], weak);
632 if (f < 0)
633 return -1;
634 if (!f && weak) {
635 f = node_follows(g, &g->node[j], &g->node[i], weak);
636 if (f < 0)
637 return -1;
639 if (!f)
640 continue;
641 if (g->node[j].index < 0) {
642 detect_sccs_tarjan(g, j, weak);
643 if (g->node[j].min_index < g->node[i].min_index)
644 g->node[i].min_index = g->node[j].min_index;
645 } else if (g->node[j].index < g->node[i].min_index)
646 g->node[i].min_index = g->node[j].index;
649 if (g->node[i].index != g->node[i].min_index)
650 return 0;
652 do {
653 j = g->stack[--g->sp];
654 g->node[j].on_stack = 0;
655 g->node[j].scc = g->scc;
656 } while (j != i);
657 g->scc++;
659 return 0;
662 static int detect_ccs(struct isl_sched_graph *graph, int weak)
664 int i;
666 graph->index = 0;
667 graph->sp = 0;
668 graph->scc = 0;
669 for (i = graph->n - 1; i >= 0; --i)
670 graph->node[i].index = -1;
672 for (i = graph->n - 1; i >= 0; --i) {
673 if (graph->node[i].index >= 0)
674 continue;
675 if (detect_sccs_tarjan(graph, i, weak) < 0)
676 return -1;
679 return 0;
682 /* Apply Tarjan's algorithm to detect the strongly connected components
683 * in the dependence graph.
685 static int detect_sccs(struct isl_sched_graph *graph)
687 return detect_ccs(graph, 0);
690 /* Apply Tarjan's algorithm to detect the (weakly) connected components
691 * in the dependence graph.
693 static int detect_wccs(struct isl_sched_graph *graph)
695 return detect_ccs(graph, 1);
698 static int cmp_scc(const void *a, const void *b, void *data)
700 struct isl_sched_graph *graph = data;
701 const int *i1 = a;
702 const int *i2 = b;
704 return graph->node[*i1].scc - graph->node[*i2].scc;
707 /* Sort the elements of graph->sorted according to the corresponding SCCs.
709 static void sort_sccs(struct isl_sched_graph *graph)
711 isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
714 /* Given a dependence relation R from a node to itself,
715 * construct the set of coefficients of valid constraints for elements
716 * in that dependence relation.
717 * In particular, the result contains tuples of coefficients
718 * c_0, c_n, c_x such that
720 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
722 * or, equivalently,
724 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
726 * We choose here to compute the dual of delta R.
727 * Alternatively, we could have computed the dual of R, resulting
728 * in a set of tuples c_0, c_n, c_x, c_y, and then
729 * plugged in (c_0, c_n, c_x, -c_x).
731 static __isl_give isl_basic_set *intra_coefficients(
732 struct isl_sched_graph *graph, __isl_take isl_map *map)
734 isl_ctx *ctx = isl_map_get_ctx(map);
735 isl_set *delta;
736 isl_basic_set *coef;
738 if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
739 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
741 delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
742 coef = isl_set_coefficients(delta);
743 isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
744 isl_basic_set_copy(coef));
746 return coef;
749 /* Given a dependence relation R, * construct the set of coefficients
750 * of valid constraints for elements in that dependence relation.
751 * In particular, the result contains tuples of coefficients
752 * c_0, c_n, c_x, c_y such that
754 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
757 static __isl_give isl_basic_set *inter_coefficients(
758 struct isl_sched_graph *graph, __isl_take isl_map *map)
760 isl_ctx *ctx = isl_map_get_ctx(map);
761 isl_set *set;
762 isl_basic_set *coef;
764 if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
765 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
767 set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
768 coef = isl_set_coefficients(set);
769 isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
770 isl_basic_set_copy(coef));
772 return coef;
775 /* Add constraints to graph->lp that force validity for the given
776 * dependence from a node i to itself.
777 * That is, add constraints that enforce
779 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
780 * = c_i_x (y - x) >= 0
782 * for each (x,y) in R.
783 * We obtain general constraints on coefficients (c_0, c_n, c_x)
784 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
785 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
786 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
788 * Actually, we do not construct constraints for the c_i_x themselves,
789 * but for the coefficients of c_i_x written as a linear combination
790 * of the columns in node->cmap.
792 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
793 struct isl_sched_edge *edge)
795 unsigned total;
796 isl_map *map = isl_map_copy(edge->map);
797 isl_ctx *ctx = isl_map_get_ctx(map);
798 isl_space *dim;
799 isl_dim_map *dim_map;
800 isl_basic_set *coef;
801 struct isl_sched_node *node = edge->src;
803 coef = intra_coefficients(graph, map);
805 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
807 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
808 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
810 total = isl_basic_set_total_dim(graph->lp);
811 dim_map = isl_dim_map_alloc(ctx, total);
812 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
813 isl_space_dim(dim, isl_dim_set), 1,
814 node->nvar, -1);
815 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
816 isl_space_dim(dim, isl_dim_set), 1,
817 node->nvar, 1);
818 graph->lp = isl_basic_set_extend_constraints(graph->lp,
819 coef->n_eq, coef->n_ineq);
820 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
821 coef, dim_map);
822 isl_space_free(dim);
824 return 0;
827 /* Add constraints to graph->lp that force validity for the given
828 * dependence from node i to node j.
829 * That is, add constraints that enforce
831 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
833 * for each (x,y) in R.
834 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
835 * of valid constraints for R and then plug in
836 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
837 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
838 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
839 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
841 * Actually, we do not construct constraints for the c_*_x themselves,
842 * but for the coefficients of c_*_x written as a linear combination
843 * of the columns in node->cmap.
845 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
846 struct isl_sched_edge *edge)
848 unsigned total;
849 isl_map *map = isl_map_copy(edge->map);
850 isl_ctx *ctx = isl_map_get_ctx(map);
851 isl_space *dim;
852 isl_dim_map *dim_map;
853 isl_basic_set *coef;
854 struct isl_sched_node *src = edge->src;
855 struct isl_sched_node *dst = edge->dst;
857 coef = inter_coefficients(graph, map);
859 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
861 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
862 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
863 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
864 isl_space_dim(dim, isl_dim_set) + src->nvar,
865 isl_mat_copy(dst->cmap));
867 total = isl_basic_set_total_dim(graph->lp);
868 dim_map = isl_dim_map_alloc(ctx, total);
870 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
871 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
872 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
873 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
874 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
875 dst->nvar, -1);
876 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
877 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
878 dst->nvar, 1);
880 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
881 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
882 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
883 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
884 isl_space_dim(dim, isl_dim_set), 1,
885 src->nvar, 1);
886 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
887 isl_space_dim(dim, isl_dim_set), 1,
888 src->nvar, -1);
890 edge->start = graph->lp->n_ineq;
891 graph->lp = isl_basic_set_extend_constraints(graph->lp,
892 coef->n_eq, coef->n_ineq);
893 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
894 coef, dim_map);
895 isl_space_free(dim);
896 edge->end = graph->lp->n_ineq;
898 return 0;
901 /* Add constraints to graph->lp that bound the dependence distance for the given
902 * dependence from a node i to itself.
903 * If s = 1, we add the constraint
905 * c_i_x (y - x) <= m_0 + m_n n
907 * or
909 * -c_i_x (y - x) + m_0 + m_n n >= 0
911 * for each (x,y) in R.
912 * If s = -1, we add the constraint
914 * -c_i_x (y - x) <= m_0 + m_n n
916 * or
918 * c_i_x (y - x) + m_0 + m_n n >= 0
920 * for each (x,y) in R.
921 * We obtain general constraints on coefficients (c_0, c_n, c_x)
922 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
923 * with each coefficient (except m_0) represented as a pair of non-negative
924 * coefficients.
926 * Actually, we do not construct constraints for the c_i_x themselves,
927 * but for the coefficients of c_i_x written as a linear combination
928 * of the columns in node->cmap.
930 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
931 struct isl_sched_edge *edge, int s)
933 unsigned total;
934 unsigned nparam;
935 isl_map *map = isl_map_copy(edge->map);
936 isl_ctx *ctx = isl_map_get_ctx(map);
937 isl_space *dim;
938 isl_dim_map *dim_map;
939 isl_basic_set *coef;
940 struct isl_sched_node *node = edge->src;
942 coef = intra_coefficients(graph, map);
944 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
946 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
947 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
949 nparam = isl_space_dim(node->dim, isl_dim_param);
950 total = isl_basic_set_total_dim(graph->lp);
951 dim_map = isl_dim_map_alloc(ctx, total);
952 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
953 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
954 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
955 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
956 isl_space_dim(dim, isl_dim_set), 1,
957 node->nvar, s);
958 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
959 isl_space_dim(dim, isl_dim_set), 1,
960 node->nvar, -s);
961 graph->lp = isl_basic_set_extend_constraints(graph->lp,
962 coef->n_eq, coef->n_ineq);
963 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
964 coef, dim_map);
965 isl_space_free(dim);
967 return 0;
970 /* Add constraints to graph->lp that bound the dependence distance for the given
971 * dependence from node i to node j.
972 * If s = 1, we add the constraint
974 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
975 * <= m_0 + m_n n
977 * or
979 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
980 * m_0 + m_n n >= 0
982 * for each (x,y) in R.
983 * If s = -1, we add the constraint
985 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
986 * <= m_0 + m_n n
988 * or
990 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
991 * m_0 + m_n n >= 0
993 * for each (x,y) in R.
994 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
995 * of valid constraints for R and then plug in
996 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
997 * -s*c_j_x+s*c_i_x)
998 * with each coefficient (except m_0, c_j_0 and c_i_0)
999 * represented as a pair of non-negative coefficients.
1001 * Actually, we do not construct constraints for the c_*_x themselves,
1002 * but for the coefficients of c_*_x written as a linear combination
1003 * of the columns in node->cmap.
1005 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
1006 struct isl_sched_edge *edge, int s)
1008 unsigned total;
1009 unsigned nparam;
1010 isl_map *map = isl_map_copy(edge->map);
1011 isl_ctx *ctx = isl_map_get_ctx(map);
1012 isl_space *dim;
1013 isl_dim_map *dim_map;
1014 isl_basic_set *coef;
1015 struct isl_sched_node *src = edge->src;
1016 struct isl_sched_node *dst = edge->dst;
1018 coef = inter_coefficients(graph, map);
1020 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1022 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1023 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1024 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1025 isl_space_dim(dim, isl_dim_set) + src->nvar,
1026 isl_mat_copy(dst->cmap));
1028 nparam = isl_space_dim(src->dim, isl_dim_param);
1029 total = isl_basic_set_total_dim(graph->lp);
1030 dim_map = isl_dim_map_alloc(ctx, total);
1032 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1033 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1034 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1036 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
1037 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
1038 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
1039 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1040 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1041 dst->nvar, s);
1042 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1043 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1044 dst->nvar, -s);
1046 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
1047 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
1048 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
1049 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1050 isl_space_dim(dim, isl_dim_set), 1,
1051 src->nvar, -s);
1052 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1053 isl_space_dim(dim, isl_dim_set), 1,
1054 src->nvar, s);
1056 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1057 coef->n_eq, coef->n_ineq);
1058 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1059 coef, dim_map);
1060 isl_space_free(dim);
1062 return 0;
1065 static int add_all_validity_constraints(struct isl_sched_graph *graph)
1067 int i;
1069 for (i = 0; i < graph->n_edge; ++i) {
1070 struct isl_sched_edge *edge= &graph->edge[i];
1071 if (!edge->validity)
1072 continue;
1073 if (edge->src != edge->dst)
1074 continue;
1075 if (add_intra_validity_constraints(graph, edge) < 0)
1076 return -1;
1079 for (i = 0; i < graph->n_edge; ++i) {
1080 struct isl_sched_edge *edge = &graph->edge[i];
1081 if (!edge->validity)
1082 continue;
1083 if (edge->src == edge->dst)
1084 continue;
1085 if (add_inter_validity_constraints(graph, edge) < 0)
1086 return -1;
1089 return 0;
1092 /* Add constraints to graph->lp that bound the dependence distance
1093 * for all dependence relations.
1094 * If a given proximity dependence is identical to a validity
1095 * dependence, then the dependence distance is already bounded
1096 * from below (by zero), so we only need to bound the distance
1097 * from above.
1098 * Otherwise, we need to bound the distance both from above and from below.
1100 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
1102 int i;
1104 for (i = 0; i < graph->n_edge; ++i) {
1105 struct isl_sched_edge *edge= &graph->edge[i];
1106 if (!edge->proximity)
1107 continue;
1108 if (edge->src == edge->dst &&
1109 add_intra_proximity_constraints(graph, edge, 1) < 0)
1110 return -1;
1111 if (edge->src != edge->dst &&
1112 add_inter_proximity_constraints(graph, edge, 1) < 0)
1113 return -1;
1114 if (edge->validity)
1115 continue;
1116 if (edge->src == edge->dst &&
1117 add_intra_proximity_constraints(graph, edge, -1) < 0)
1118 return -1;
1119 if (edge->src != edge->dst &&
1120 add_inter_proximity_constraints(graph, edge, -1) < 0)
1121 return -1;
1124 return 0;
1127 /* Compute a basis for the rows in the linear part of the schedule
1128 * and extend this basis to a full basis. The remaining rows
1129 * can then be used to force linear independence from the rows
1130 * in the schedule.
1132 * In particular, given the schedule rows S, we compute
1134 * S = H Q
1136 * with H the Hermite normal form of S. That is, all but the
1137 * first rank columns of Q are zero and so each row in S is
1138 * a linear combination of the first rank rows of Q.
1139 * The matrix Q is then transposed because we will write the
1140 * coefficients of the next schedule row as a column vector s
1141 * and express this s as a linear combination s = Q c of the
1142 * computed basis.
1144 static int node_update_cmap(struct isl_sched_node *node)
1146 isl_mat *H, *Q;
1147 int n_row = isl_mat_rows(node->sched);
1149 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1150 1 + node->nparam, node->nvar);
1152 H = isl_mat_left_hermite(H, 0, NULL, &Q);
1153 isl_mat_free(node->cmap);
1154 node->cmap = isl_mat_transpose(Q);
1155 node->rank = isl_mat_initial_non_zero_cols(H);
1156 isl_mat_free(H);
1158 if (!node->cmap || node->rank < 0)
1159 return -1;
1160 return 0;
1163 /* Count the number of equality and inequality constraints
1164 * that will be added for the given map.
1165 * If carry is set, then we are counting the number of (validity)
1166 * constraints that will be added in setup_carry_lp and we count
1167 * each edge exactly once. Otherwise, we count as follows
1168 * validity -> 1 (>= 0)
1169 * validity+proximity -> 2 (>= 0 and upper bound)
1170 * proximity -> 2 (lower and upper bound)
1172 static int count_map_constraints(struct isl_sched_graph *graph,
1173 struct isl_sched_edge *edge, __isl_take isl_map *map,
1174 int *n_eq, int *n_ineq, int carry)
1176 isl_basic_set *coef;
1177 int f = carry ? 1 : edge->proximity ? 2 : 1;
1179 if (carry && !edge->validity) {
1180 isl_map_free(map);
1181 return 0;
1184 if (edge->src == edge->dst)
1185 coef = intra_coefficients(graph, map);
1186 else
1187 coef = inter_coefficients(graph, map);
1188 if (!coef)
1189 return -1;
1190 *n_eq += f * coef->n_eq;
1191 *n_ineq += f * coef->n_ineq;
1192 isl_basic_set_free(coef);
1194 return 0;
1197 /* Count the number of equality and inequality constraints
1198 * that will be added to the main lp problem.
1199 * We count as follows
1200 * validity -> 1 (>= 0)
1201 * validity+proximity -> 2 (>= 0 and upper bound)
1202 * proximity -> 2 (lower and upper bound)
1204 static int count_constraints(struct isl_sched_graph *graph,
1205 int *n_eq, int *n_ineq)
1207 int i;
1209 *n_eq = *n_ineq = 0;
1210 for (i = 0; i < graph->n_edge; ++i) {
1211 struct isl_sched_edge *edge= &graph->edge[i];
1212 isl_map *map = isl_map_copy(edge->map);
1214 if (count_map_constraints(graph, edge, map,
1215 n_eq, n_ineq, 0) < 0)
1216 return -1;
1219 return 0;
1222 /* Add constraints that bound the values of the variable and parameter
1223 * coefficients of the schedule.
1225 * The maximal value of the coefficients is defined by the option
1226 * 'schedule_max_coefficient'.
1228 static int add_bound_coefficient_constraints(isl_ctx *ctx,
1229 struct isl_sched_graph *graph)
1231 int i, j, k;
1232 int max_coefficient;
1233 int total;
1235 max_coefficient = ctx->opt->schedule_max_coefficient;
1237 if (max_coefficient == -1)
1238 return 0;
1240 total = isl_basic_set_total_dim(graph->lp);
1242 for (i = 0; i < graph->n; ++i) {
1243 struct isl_sched_node *node = &graph->node[i];
1244 for (j = 0; j < 2 * node->nparam + 2 * node->nvar; ++j) {
1245 int dim;
1246 k = isl_basic_set_alloc_inequality(graph->lp);
1247 if (k < 0)
1248 return -1;
1249 dim = 1 + node->start + 1 + j;
1250 isl_seq_clr(graph->lp->ineq[k], 1 + total);
1251 isl_int_set_si(graph->lp->ineq[k][dim], -1);
1252 isl_int_set_si(graph->lp->ineq[k][0], max_coefficient);
1256 return 0;
1259 /* Construct an ILP problem for finding schedule coefficients
1260 * that result in non-negative, but small dependence distances
1261 * over all dependences.
1262 * In particular, the dependence distances over proximity edges
1263 * are bounded by m_0 + m_n n and we compute schedule coefficients
1264 * with small values (preferably zero) of m_n and m_0.
1266 * All variables of the ILP are non-negative. The actual coefficients
1267 * may be negative, so each coefficient is represented as the difference
1268 * of two non-negative variables. The negative part always appears
1269 * immediately before the positive part.
1270 * Other than that, the variables have the following order
1272 * - sum of positive and negative parts of m_n coefficients
1273 * - m_0
1274 * - sum of positive and negative parts of all c_n coefficients
1275 * (unconstrained when computing non-parametric schedules)
1276 * - sum of positive and negative parts of all c_x coefficients
1277 * - positive and negative parts of m_n coefficients
1278 * - for each node
1279 * - c_i_0
1280 * - positive and negative parts of c_i_n (if parametric)
1281 * - positive and negative parts of c_i_x
1283 * The c_i_x are not represented directly, but through the columns of
1284 * node->cmap. That is, the computed values are for variable t_i_x
1285 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1287 * The constraints are those from the edges plus two or three equalities
1288 * to express the sums.
1290 * If force_zero is set, then we add equalities to ensure that
1291 * the sum of the m_n coefficients and m_0 are both zero.
1293 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
1294 int force_zero)
1296 int i, j;
1297 int k;
1298 unsigned nparam;
1299 unsigned total;
1300 isl_space *dim;
1301 int parametric;
1302 int param_pos;
1303 int n_eq, n_ineq;
1304 int max_constant_term;
1305 int max_coefficient;
1307 max_constant_term = ctx->opt->schedule_max_constant_term;
1308 max_coefficient = ctx->opt->schedule_max_coefficient;
1310 parametric = ctx->opt->schedule_parametric;
1311 nparam = isl_space_dim(graph->node[0].dim, isl_dim_param);
1312 param_pos = 4;
1313 total = param_pos + 2 * nparam;
1314 for (i = 0; i < graph->n; ++i) {
1315 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1316 if (node_update_cmap(node) < 0)
1317 return -1;
1318 node->start = total;
1319 total += 1 + 2 * (node->nparam + node->nvar);
1322 if (count_constraints(graph, &n_eq, &n_ineq) < 0)
1323 return -1;
1325 dim = isl_space_set_alloc(ctx, 0, total);
1326 isl_basic_set_free(graph->lp);
1327 n_eq += 2 + parametric + force_zero;
1328 if (max_constant_term != -1)
1329 n_ineq += graph->n;
1330 if (max_coefficient != -1)
1331 for (i = 0; i < graph->n; ++i)
1332 n_ineq += 2 * graph->node[i].nparam +
1333 2 * graph->node[i].nvar;
1335 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
1337 k = isl_basic_set_alloc_equality(graph->lp);
1338 if (k < 0)
1339 return -1;
1340 isl_seq_clr(graph->lp->eq[k], 1 + total);
1341 if (!force_zero)
1342 isl_int_set_si(graph->lp->eq[k][1], -1);
1343 for (i = 0; i < 2 * nparam; ++i)
1344 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1346 if (force_zero) {
1347 k = isl_basic_set_alloc_equality(graph->lp);
1348 if (k < 0)
1349 return -1;
1350 isl_seq_clr(graph->lp->eq[k], 1 + total);
1351 isl_int_set_si(graph->lp->eq[k][2], -1);
1354 if (parametric) {
1355 k = isl_basic_set_alloc_equality(graph->lp);
1356 if (k < 0)
1357 return -1;
1358 isl_seq_clr(graph->lp->eq[k], 1 + total);
1359 isl_int_set_si(graph->lp->eq[k][3], -1);
1360 for (i = 0; i < graph->n; ++i) {
1361 int pos = 1 + graph->node[i].start + 1;
1363 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1364 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1368 k = isl_basic_set_alloc_equality(graph->lp);
1369 if (k < 0)
1370 return -1;
1371 isl_seq_clr(graph->lp->eq[k], 1 + total);
1372 isl_int_set_si(graph->lp->eq[k][4], -1);
1373 for (i = 0; i < graph->n; ++i) {
1374 struct isl_sched_node *node = &graph->node[i];
1375 int pos = 1 + node->start + 1 + 2 * node->nparam;
1377 for (j = 0; j < 2 * node->nvar; ++j)
1378 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1381 if (max_constant_term != -1)
1382 for (i = 0; i < graph->n; ++i) {
1383 struct isl_sched_node *node = &graph->node[i];
1384 k = isl_basic_set_alloc_inequality(graph->lp);
1385 if (k < 0)
1386 return -1;
1387 isl_seq_clr(graph->lp->ineq[k], 1 + total);
1388 isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1);
1389 isl_int_set_si(graph->lp->ineq[k][0], max_constant_term);
1392 if (add_bound_coefficient_constraints(ctx, graph) < 0)
1393 return -1;
1394 if (add_all_validity_constraints(graph) < 0)
1395 return -1;
1396 if (add_all_proximity_constraints(graph) < 0)
1397 return -1;
1399 return 0;
1402 /* Analyze the conflicting constraint found by
1403 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1404 * constraint of one of the edges between distinct nodes, living, moreover
1405 * in distinct SCCs, then record the source and sink SCC as this may
1406 * be a good place to cut between SCCs.
1408 static int check_conflict(int con, void *user)
1410 int i;
1411 struct isl_sched_graph *graph = user;
1413 if (graph->src_scc >= 0)
1414 return 0;
1416 con -= graph->lp->n_eq;
1418 if (con >= graph->lp->n_ineq)
1419 return 0;
1421 for (i = 0; i < graph->n_edge; ++i) {
1422 if (!graph->edge[i].validity)
1423 continue;
1424 if (graph->edge[i].src == graph->edge[i].dst)
1425 continue;
1426 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1427 continue;
1428 if (graph->edge[i].start > con)
1429 continue;
1430 if (graph->edge[i].end <= con)
1431 continue;
1432 graph->src_scc = graph->edge[i].src->scc;
1433 graph->dst_scc = graph->edge[i].dst->scc;
1436 return 0;
1439 /* Check whether the next schedule row of the given node needs to be
1440 * non-trivial. Lower-dimensional domains may have some trivial rows,
1441 * but as soon as the number of remaining required non-trivial rows
1442 * is as large as the number or remaining rows to be computed,
1443 * all remaining rows need to be non-trivial.
1445 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1447 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1450 /* Solve the ILP problem constructed in setup_lp.
1451 * For each node such that all the remaining rows of its schedule
1452 * need to be non-trivial, we construct a non-triviality region.
1453 * This region imposes that the next row is independent of previous rows.
1454 * In particular the coefficients c_i_x are represented by t_i_x
1455 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1456 * its first columns span the rows of the previously computed part
1457 * of the schedule. The non-triviality region enforces that at least
1458 * one of the remaining components of t_i_x is non-zero, i.e.,
1459 * that the new schedule row depends on at least one of the remaining
1460 * columns of Q.
1462 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1464 int i;
1465 isl_vec *sol;
1466 isl_basic_set *lp;
1468 for (i = 0; i < graph->n; ++i) {
1469 struct isl_sched_node *node = &graph->node[i];
1470 int skip = node->rank;
1471 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1472 if (needs_row(graph, node))
1473 graph->region[i].len = 2 * (node->nvar - skip);
1474 else
1475 graph->region[i].len = 0;
1477 lp = isl_basic_set_copy(graph->lp);
1478 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1479 graph->region, &check_conflict, graph);
1480 return sol;
1483 /* Update the schedules of all nodes based on the given solution
1484 * of the LP problem.
1485 * The new row is added to the current band.
1486 * All possibly negative coefficients are encoded as a difference
1487 * of two non-negative variables, so we need to perform the subtraction
1488 * here. Moreover, if use_cmap is set, then the solution does
1489 * not refer to the actual coefficients c_i_x, but instead to variables
1490 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1491 * In this case, we then also need to perform this multiplication
1492 * to obtain the values of c_i_x.
1494 * If check_zero is set, then the first two coordinates of sol are
1495 * assumed to correspond to the dependence distance. If these two
1496 * coordinates are zero, then the corresponding scheduling dimension
1497 * is marked as being zero distance.
1499 static int update_schedule(struct isl_sched_graph *graph,
1500 __isl_take isl_vec *sol, int use_cmap, int check_zero)
1502 int i, j;
1503 int zero = 0;
1504 isl_vec *csol = NULL;
1506 if (!sol)
1507 goto error;
1508 if (sol->size == 0)
1509 isl_die(sol->ctx, isl_error_internal,
1510 "no solution found", goto error);
1512 if (check_zero)
1513 zero = isl_int_is_zero(sol->el[1]) &&
1514 isl_int_is_zero(sol->el[2]);
1516 for (i = 0; i < graph->n; ++i) {
1517 struct isl_sched_node *node = &graph->node[i];
1518 int pos = node->start;
1519 int row = isl_mat_rows(node->sched);
1521 isl_vec_free(csol);
1522 csol = isl_vec_alloc(sol->ctx, node->nvar);
1523 if (!csol)
1524 goto error;
1526 isl_map_free(node->sched_map);
1527 node->sched_map = NULL;
1528 node->sched = isl_mat_add_rows(node->sched, 1);
1529 if (!node->sched)
1530 goto error;
1531 node->sched = isl_mat_set_element(node->sched, row, 0,
1532 sol->el[1 + pos]);
1533 for (j = 0; j < node->nparam + node->nvar; ++j)
1534 isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1535 sol->el[1 + pos + 1 + 2 * j + 1],
1536 sol->el[1 + pos + 1 + 2 * j]);
1537 for (j = 0; j < node->nparam; ++j)
1538 node->sched = isl_mat_set_element(node->sched,
1539 row, 1 + j, sol->el[1+pos+1+2*j+1]);
1540 for (j = 0; j < node->nvar; ++j)
1541 isl_int_set(csol->el[j],
1542 sol->el[1+pos+1+2*(node->nparam+j)+1]);
1543 if (use_cmap)
1544 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1545 csol);
1546 if (!csol)
1547 goto error;
1548 for (j = 0; j < node->nvar; ++j)
1549 node->sched = isl_mat_set_element(node->sched,
1550 row, 1 + node->nparam + j, csol->el[j]);
1551 node->band[graph->n_total_row] = graph->n_band;
1552 node->zero[graph->n_total_row] = zero;
1554 isl_vec_free(sol);
1555 isl_vec_free(csol);
1557 graph->n_row++;
1558 graph->n_total_row++;
1560 return 0;
1561 error:
1562 isl_vec_free(sol);
1563 isl_vec_free(csol);
1564 return -1;
1567 /* Convert node->sched into a multi_aff and return this multi_aff.
1569 static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
1570 struct isl_sched_node *node)
1572 int i, j;
1573 isl_space *space;
1574 isl_local_space *ls;
1575 isl_aff *aff;
1576 isl_multi_aff *ma;
1577 int nrow, ncol;
1578 isl_int v;
1580 nrow = isl_mat_rows(node->sched);
1581 ncol = isl_mat_cols(node->sched) - 1;
1582 space = isl_space_from_domain(isl_space_copy(node->dim));
1583 space = isl_space_add_dims(space, isl_dim_out, nrow);
1584 ma = isl_multi_aff_zero(space);
1585 ls = isl_local_space_from_space(isl_space_copy(node->dim));
1587 isl_int_init(v);
1589 for (i = 0; i < nrow; ++i) {
1590 aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1591 isl_mat_get_element(node->sched, i, 0, &v);
1592 aff = isl_aff_set_constant(aff, v);
1593 for (j = 0; j < node->nparam; ++j) {
1594 isl_mat_get_element(node->sched, i, 1 + j, &v);
1595 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
1597 for (j = 0; j < node->nvar; ++j) {
1598 isl_mat_get_element(node->sched,
1599 i, 1 + node->nparam + j, &v);
1600 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
1602 ma = isl_multi_aff_set_aff(ma, i, aff);
1605 isl_int_clear(v);
1607 isl_local_space_free(ls);
1609 return ma;
1612 /* Convert node->sched into a map and return this map.
1614 * The result is cached in node->sched_map, which needs to be released
1615 * whenever node->sched is updated.
1617 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1619 if (!node->sched_map) {
1620 isl_multi_aff *ma;
1622 ma = node_extract_schedule_multi_aff(node);
1623 node->sched_map = isl_map_from_multi_aff(ma);
1626 return isl_map_copy(node->sched_map);
1629 /* Update the given dependence relation based on the current schedule.
1630 * That is, intersect the dependence relation with a map expressing
1631 * that source and sink are executed within the same iteration of
1632 * the current schedule.
1633 * This is not the most efficient way, but this shouldn't be a critical
1634 * operation.
1636 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1637 struct isl_sched_node *src, struct isl_sched_node *dst)
1639 isl_map *src_sched, *dst_sched, *id;
1641 src_sched = node_extract_schedule(src);
1642 dst_sched = node_extract_schedule(dst);
1643 id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1644 return isl_map_intersect(map, id);
1647 /* Update the dependence relations of all edges based on the current schedule.
1648 * If a dependence is carried completely by the current schedule, then
1649 * it is removed from the edge_tables. It is kept in the list of edges
1650 * as otherwise all edge_tables would have to be recomputed.
1652 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1654 int i;
1656 for (i = graph->n_edge - 1; i >= 0; --i) {
1657 struct isl_sched_edge *edge = &graph->edge[i];
1658 edge->map = specialize(edge->map, edge->src, edge->dst);
1659 if (!edge->map)
1660 return -1;
1662 if (isl_map_plain_is_empty(edge->map))
1663 graph_remove_edge(graph, edge);
1666 return 0;
1669 static void next_band(struct isl_sched_graph *graph)
1671 graph->band_start = graph->n_total_row;
1672 graph->n_band++;
1675 /* Topologically sort statements mapped to the same schedule iteration
1676 * and add a row to the schedule corresponding to this order.
1678 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1680 int i, j;
1682 if (graph->n <= 1)
1683 return 0;
1685 if (update_edges(ctx, graph) < 0)
1686 return -1;
1688 if (graph->n_edge == 0)
1689 return 0;
1691 if (detect_sccs(graph) < 0)
1692 return -1;
1694 for (i = 0; i < graph->n; ++i) {
1695 struct isl_sched_node *node = &graph->node[i];
1696 int row = isl_mat_rows(node->sched);
1697 int cols = isl_mat_cols(node->sched);
1699 isl_map_free(node->sched_map);
1700 node->sched_map = NULL;
1701 node->sched = isl_mat_add_rows(node->sched, 1);
1702 if (!node->sched)
1703 return -1;
1704 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1705 node->scc);
1706 for (j = 1; j < cols; ++j)
1707 node->sched = isl_mat_set_element_si(node->sched,
1708 row, j, 0);
1709 node->band[graph->n_total_row] = graph->n_band;
1712 graph->n_total_row++;
1713 next_band(graph);
1715 return 0;
1718 /* Construct an isl_schedule based on the computed schedule stored
1719 * in graph and with parameters specified by dim.
1721 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1722 __isl_take isl_space *dim)
1724 int i;
1725 isl_ctx *ctx;
1726 isl_schedule *sched = NULL;
1728 if (!dim)
1729 return NULL;
1731 ctx = isl_space_get_ctx(dim);
1732 sched = isl_calloc(ctx, struct isl_schedule,
1733 sizeof(struct isl_schedule) +
1734 (graph->n - 1) * sizeof(struct isl_schedule_node));
1735 if (!sched)
1736 goto error;
1738 sched->ref = 1;
1739 sched->n = graph->n;
1740 sched->n_band = graph->n_band;
1741 sched->n_total_row = graph->n_total_row;
1743 for (i = 0; i < sched->n; ++i) {
1744 int r, b;
1745 int *band_end, *band_id, *zero;
1747 band_end = isl_alloc_array(ctx, int, graph->n_band);
1748 band_id = isl_alloc_array(ctx, int, graph->n_band);
1749 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1750 sched->node[i].sched =
1751 node_extract_schedule_multi_aff(&graph->node[i]);
1752 sched->node[i].band_end = band_end;
1753 sched->node[i].band_id = band_id;
1754 sched->node[i].zero = zero;
1755 if (!band_end || !band_id || !zero)
1756 goto error;
1758 for (r = 0; r < graph->n_total_row; ++r)
1759 zero[r] = graph->node[i].zero[r];
1760 for (r = b = 0; r < graph->n_total_row; ++r) {
1761 if (graph->node[i].band[r] == b)
1762 continue;
1763 band_end[b++] = r;
1764 if (graph->node[i].band[r] == -1)
1765 break;
1767 if (r == graph->n_total_row)
1768 band_end[b++] = r;
1769 sched->node[i].n_band = b;
1770 for (--b; b >= 0; --b)
1771 band_id[b] = graph->node[i].band_id[b];
1774 sched->dim = dim;
1776 return sched;
1777 error:
1778 isl_space_free(dim);
1779 isl_schedule_free(sched);
1780 return NULL;
1783 /* Copy nodes that satisfy node_pred from the src dependence graph
1784 * to the dst dependence graph.
1786 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1787 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1789 int i;
1791 dst->n = 0;
1792 for (i = 0; i < src->n; ++i) {
1793 if (!node_pred(&src->node[i], data))
1794 continue;
1795 dst->node[dst->n].dim = isl_space_copy(src->node[i].dim);
1796 dst->node[dst->n].nvar = src->node[i].nvar;
1797 dst->node[dst->n].nparam = src->node[i].nparam;
1798 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1799 dst->node[dst->n].sched_map =
1800 isl_map_copy(src->node[i].sched_map);
1801 dst->node[dst->n].band = src->node[i].band;
1802 dst->node[dst->n].band_id = src->node[i].band_id;
1803 dst->node[dst->n].zero = src->node[i].zero;
1804 dst->n++;
1807 return 0;
1810 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1811 * to the dst dependence graph.
1812 * If the source or destination node of the edge is not in the destination
1813 * graph, then it must be a backward proximity edge and it should simply
1814 * be ignored.
1816 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1817 struct isl_sched_graph *src,
1818 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1820 int i;
1821 int t;
1823 dst->n_edge = 0;
1824 for (i = 0; i < src->n_edge; ++i) {
1825 struct isl_sched_edge *edge = &src->edge[i];
1826 isl_map *map;
1827 struct isl_sched_node *dst_src, *dst_dst;
1829 if (!edge_pred(edge, data))
1830 continue;
1832 if (isl_map_plain_is_empty(edge->map))
1833 continue;
1835 dst_src = graph_find_node(ctx, dst, edge->src->dim);
1836 dst_dst = graph_find_node(ctx, dst, edge->dst->dim);
1837 if (!dst_src || !dst_dst) {
1838 if (edge->validity)
1839 isl_die(ctx, isl_error_internal,
1840 "backward validity edge", return -1);
1841 continue;
1844 map = isl_map_copy(edge->map);
1846 dst->edge[dst->n_edge].src = dst_src;
1847 dst->edge[dst->n_edge].dst = dst_dst;
1848 dst->edge[dst->n_edge].map = map;
1849 dst->edge[dst->n_edge].validity = edge->validity;
1850 dst->edge[dst->n_edge].proximity = edge->proximity;
1851 dst->n_edge++;
1853 for (t = 0; t <= isl_edge_last; ++t) {
1854 if (edge !=
1855 graph_find_edge(src, t, edge->src, edge->dst))
1856 continue;
1857 if (graph_edge_table_add(ctx, dst, t,
1858 &dst->edge[dst->n_edge - 1]) < 0)
1859 return -1;
1863 return 0;
1866 /* Given a "src" dependence graph that contains the nodes from "dst"
1867 * that satisfy node_pred, copy the schedule computed in "src"
1868 * for those nodes back to "dst".
1870 static int copy_schedule(struct isl_sched_graph *dst,
1871 struct isl_sched_graph *src,
1872 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1874 int i;
1876 src->n = 0;
1877 for (i = 0; i < dst->n; ++i) {
1878 if (!node_pred(&dst->node[i], data))
1879 continue;
1880 isl_mat_free(dst->node[i].sched);
1881 isl_map_free(dst->node[i].sched_map);
1882 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1883 dst->node[i].sched_map =
1884 isl_map_copy(src->node[src->n].sched_map);
1885 src->n++;
1888 dst->n_total_row = src->n_total_row;
1889 dst->n_band = src->n_band;
1891 return 0;
1894 /* Compute the maximal number of variables over all nodes.
1895 * This is the maximal number of linearly independent schedule
1896 * rows that we need to compute.
1897 * Just in case we end up in a part of the dependence graph
1898 * with only lower-dimensional domains, we make sure we will
1899 * compute the required amount of extra linearly independent rows.
1901 static int compute_maxvar(struct isl_sched_graph *graph)
1903 int i;
1905 graph->maxvar = 0;
1906 for (i = 0; i < graph->n; ++i) {
1907 struct isl_sched_node *node = &graph->node[i];
1908 int nvar;
1910 if (node_update_cmap(node) < 0)
1911 return -1;
1912 nvar = node->nvar + graph->n_row - node->rank;
1913 if (nvar > graph->maxvar)
1914 graph->maxvar = nvar;
1917 return 0;
1920 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1921 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1923 /* Compute a schedule for a subgraph of "graph". In particular, for
1924 * the graph composed of nodes that satisfy node_pred and edges that
1925 * that satisfy edge_pred. The caller should precompute the number
1926 * of nodes and edges that satisfy these predicates and pass them along
1927 * as "n" and "n_edge".
1928 * If the subgraph is known to consist of a single component, then wcc should
1929 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1930 * Otherwise, we call compute_schedule, which will check whether the subgraph
1931 * is connected.
1933 static int compute_sub_schedule(isl_ctx *ctx,
1934 struct isl_sched_graph *graph, int n, int n_edge,
1935 int (*node_pred)(struct isl_sched_node *node, int data),
1936 int (*edge_pred)(struct isl_sched_edge *edge, int data),
1937 int data, int wcc)
1939 struct isl_sched_graph split = { 0 };
1940 int t;
1942 if (graph_alloc(ctx, &split, n, n_edge) < 0)
1943 goto error;
1944 if (copy_nodes(&split, graph, node_pred, data) < 0)
1945 goto error;
1946 if (graph_init_table(ctx, &split) < 0)
1947 goto error;
1948 for (t = 0; t <= isl_edge_last; ++t)
1949 split.max_edge[t] = graph->max_edge[t];
1950 if (graph_init_edge_tables(ctx, &split) < 0)
1951 goto error;
1952 if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1953 goto error;
1954 split.n_row = graph->n_row;
1955 split.n_total_row = graph->n_total_row;
1956 split.n_band = graph->n_band;
1957 split.band_start = graph->band_start;
1959 if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1960 goto error;
1961 if (!wcc && compute_schedule(ctx, &split) < 0)
1962 goto error;
1964 copy_schedule(graph, &split, node_pred, data);
1966 graph_free(ctx, &split);
1967 return 0;
1968 error:
1969 graph_free(ctx, &split);
1970 return -1;
1973 static int node_scc_exactly(struct isl_sched_node *node, int scc)
1975 return node->scc == scc;
1978 static int node_scc_at_most(struct isl_sched_node *node, int scc)
1980 return node->scc <= scc;
1983 static int node_scc_at_least(struct isl_sched_node *node, int scc)
1985 return node->scc >= scc;
1988 static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
1990 return edge->src->scc == scc && edge->dst->scc == scc;
1993 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
1995 return edge->dst->scc <= scc;
1998 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
2000 return edge->src->scc >= scc;
2003 /* Pad the schedules of all nodes with zero rows such that in the end
2004 * they all have graph->n_total_row rows.
2005 * The extra rows don't belong to any band, so they get assigned band number -1.
2007 static int pad_schedule(struct isl_sched_graph *graph)
2009 int i, j;
2011 for (i = 0; i < graph->n; ++i) {
2012 struct isl_sched_node *node = &graph->node[i];
2013 int row = isl_mat_rows(node->sched);
2014 if (graph->n_total_row > row) {
2015 isl_map_free(node->sched_map);
2016 node->sched_map = NULL;
2018 node->sched = isl_mat_add_zero_rows(node->sched,
2019 graph->n_total_row - row);
2020 if (!node->sched)
2021 return -1;
2022 for (j = row; j < graph->n_total_row; ++j)
2023 node->band[j] = -1;
2026 return 0;
2029 /* Split the current graph into two parts and compute a schedule for each
2030 * part individually. In particular, one part consists of all SCCs up
2031 * to and including graph->src_scc, while the other part contains the other
2032 * SCCS.
2034 * The split is enforced in the schedule by constant rows with two different
2035 * values (0 and 1). These constant rows replace the previously computed rows
2036 * in the current band.
2037 * It would be possible to reuse them as the first rows in the next
2038 * band, but recomputing them may result in better rows as we are looking
2039 * at a smaller part of the dependence graph.
2040 * compute_split_schedule is only called when no zero-distance schedule row
2041 * could be found on the entire graph, so we wark the splitting row as
2042 * non zero-distance.
2044 * The band_id of the second group is set to n, where n is the number
2045 * of nodes in the first group. This ensures that the band_ids over
2046 * the two groups remain disjoint, even if either or both of the two
2047 * groups contain independent components.
2049 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2051 int i, j, n, e1, e2;
2052 int n_total_row, orig_total_row;
2053 int n_band, orig_band;
2054 int drop;
2056 drop = graph->n_total_row - graph->band_start;
2057 graph->n_total_row -= drop;
2058 graph->n_row -= drop;
2060 n = 0;
2061 for (i = 0; i < graph->n; ++i) {
2062 struct isl_sched_node *node = &graph->node[i];
2063 int row = isl_mat_rows(node->sched) - drop;
2064 int cols = isl_mat_cols(node->sched);
2065 int before = node->scc <= graph->src_scc;
2067 if (before)
2068 n++;
2070 isl_map_free(node->sched_map);
2071 node->sched_map = NULL;
2072 node->sched = isl_mat_drop_rows(node->sched,
2073 graph->band_start, drop);
2074 node->sched = isl_mat_add_rows(node->sched, 1);
2075 if (!node->sched)
2076 return -1;
2077 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2078 !before);
2079 for (j = 1; j < cols; ++j)
2080 node->sched = isl_mat_set_element_si(node->sched,
2081 row, j, 0);
2082 node->band[graph->n_total_row] = graph->n_band;
2083 node->zero[graph->n_total_row] = 0;
2086 e1 = e2 = 0;
2087 for (i = 0; i < graph->n_edge; ++i) {
2088 if (graph->edge[i].dst->scc <= graph->src_scc)
2089 e1++;
2090 if (graph->edge[i].src->scc > graph->src_scc)
2091 e2++;
2094 graph->n_total_row++;
2095 next_band(graph);
2097 for (i = 0; i < graph->n; ++i) {
2098 struct isl_sched_node *node = &graph->node[i];
2099 if (node->scc > graph->src_scc)
2100 node->band_id[graph->n_band] = n;
2103 orig_total_row = graph->n_total_row;
2104 orig_band = graph->n_band;
2105 if (compute_sub_schedule(ctx, graph, n, e1,
2106 &node_scc_at_most, &edge_dst_scc_at_most,
2107 graph->src_scc, 0) < 0)
2108 return -1;
2109 n_total_row = graph->n_total_row;
2110 graph->n_total_row = orig_total_row;
2111 n_band = graph->n_band;
2112 graph->n_band = orig_band;
2113 if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
2114 &node_scc_at_least, &edge_src_scc_at_least,
2115 graph->src_scc + 1, 0) < 0)
2116 return -1;
2117 if (n_total_row > graph->n_total_row)
2118 graph->n_total_row = n_total_row;
2119 if (n_band > graph->n_band)
2120 graph->n_band = n_band;
2122 return pad_schedule(graph);
2125 /* Compute the next band of the schedule after updating the dependence
2126 * relations based on the the current schedule.
2128 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
2130 if (update_edges(ctx, graph) < 0)
2131 return -1;
2132 next_band(graph);
2134 return compute_schedule(ctx, graph);
2137 /* Add constraints to graph->lp that force the dependence "map" (which
2138 * is part of the dependence relation of "edge")
2139 * to be respected and attempt to carry it, where the edge is one from
2140 * a node j to itself. "pos" is the sequence number of the given map.
2141 * That is, add constraints that enforce
2143 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2144 * = c_j_x (y - x) >= e_i
2146 * for each (x,y) in R.
2147 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2148 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2149 * with each coefficient in c_j_x represented as a pair of non-negative
2150 * coefficients.
2152 static int add_intra_constraints(struct isl_sched_graph *graph,
2153 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2155 unsigned total;
2156 isl_ctx *ctx = isl_map_get_ctx(map);
2157 isl_space *dim;
2158 isl_dim_map *dim_map;
2159 isl_basic_set *coef;
2160 struct isl_sched_node *node = edge->src;
2162 coef = intra_coefficients(graph, map);
2164 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2166 total = isl_basic_set_total_dim(graph->lp);
2167 dim_map = isl_dim_map_alloc(ctx, total);
2168 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2169 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
2170 isl_space_dim(dim, isl_dim_set), 1,
2171 node->nvar, -1);
2172 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
2173 isl_space_dim(dim, isl_dim_set), 1,
2174 node->nvar, 1);
2175 graph->lp = isl_basic_set_extend_constraints(graph->lp,
2176 coef->n_eq, coef->n_ineq);
2177 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2178 coef, dim_map);
2179 isl_space_free(dim);
2181 return 0;
2184 /* Add constraints to graph->lp that force the dependence "map" (which
2185 * is part of the dependence relation of "edge")
2186 * to be respected and attempt to carry it, where the edge is one from
2187 * node j to node k. "pos" is the sequence number of the given map.
2188 * That is, add constraints that enforce
2190 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2192 * for each (x,y) in R.
2193 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2194 * of valid constraints for R and then plug in
2195 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2196 * with each coefficient (except e_i, c_k_0 and c_j_0)
2197 * represented as a pair of non-negative coefficients.
2199 static int add_inter_constraints(struct isl_sched_graph *graph,
2200 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2202 unsigned total;
2203 isl_ctx *ctx = isl_map_get_ctx(map);
2204 isl_space *dim;
2205 isl_dim_map *dim_map;
2206 isl_basic_set *coef;
2207 struct isl_sched_node *src = edge->src;
2208 struct isl_sched_node *dst = edge->dst;
2210 coef = inter_coefficients(graph, map);
2212 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2214 total = isl_basic_set_total_dim(graph->lp);
2215 dim_map = isl_dim_map_alloc(ctx, total);
2217 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2219 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
2220 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
2221 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
2222 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
2223 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2224 dst->nvar, -1);
2225 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
2226 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2227 dst->nvar, 1);
2229 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
2230 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
2231 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
2232 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
2233 isl_space_dim(dim, isl_dim_set), 1,
2234 src->nvar, 1);
2235 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
2236 isl_space_dim(dim, isl_dim_set), 1,
2237 src->nvar, -1);
2239 graph->lp = isl_basic_set_extend_constraints(graph->lp,
2240 coef->n_eq, coef->n_ineq);
2241 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2242 coef, dim_map);
2243 isl_space_free(dim);
2245 return 0;
2248 /* Add constraints to graph->lp that force all validity dependences
2249 * to be respected and attempt to carry them.
2251 static int add_all_constraints(struct isl_sched_graph *graph)
2253 int i, j;
2254 int pos;
2256 pos = 0;
2257 for (i = 0; i < graph->n_edge; ++i) {
2258 struct isl_sched_edge *edge= &graph->edge[i];
2260 if (!edge->validity)
2261 continue;
2263 for (j = 0; j < edge->map->n; ++j) {
2264 isl_basic_map *bmap;
2265 isl_map *map;
2267 bmap = isl_basic_map_copy(edge->map->p[j]);
2268 map = isl_map_from_basic_map(bmap);
2270 if (edge->src == edge->dst &&
2271 add_intra_constraints(graph, edge, map, pos) < 0)
2272 return -1;
2273 if (edge->src != edge->dst &&
2274 add_inter_constraints(graph, edge, map, pos) < 0)
2275 return -1;
2276 ++pos;
2280 return 0;
2283 /* Count the number of equality and inequality constraints
2284 * that will be added to the carry_lp problem.
2285 * We count each edge exactly once.
2287 static int count_all_constraints(struct isl_sched_graph *graph,
2288 int *n_eq, int *n_ineq)
2290 int i, j;
2292 *n_eq = *n_ineq = 0;
2293 for (i = 0; i < graph->n_edge; ++i) {
2294 struct isl_sched_edge *edge= &graph->edge[i];
2295 for (j = 0; j < edge->map->n; ++j) {
2296 isl_basic_map *bmap;
2297 isl_map *map;
2299 bmap = isl_basic_map_copy(edge->map->p[j]);
2300 map = isl_map_from_basic_map(bmap);
2302 if (count_map_constraints(graph, edge, map,
2303 n_eq, n_ineq, 1) < 0)
2304 return -1;
2308 return 0;
2311 /* Construct an LP problem for finding schedule coefficients
2312 * such that the schedule carries as many dependences as possible.
2313 * In particular, for each dependence i, we bound the dependence distance
2314 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2315 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2316 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2317 * Note that if the dependence relation is a union of basic maps,
2318 * then we have to consider each basic map individually as it may only
2319 * be possible to carry the dependences expressed by some of those
2320 * basic maps and not all off them.
2321 * Below, we consider each of those basic maps as a separate "edge".
2323 * All variables of the LP are non-negative. The actual coefficients
2324 * may be negative, so each coefficient is represented as the difference
2325 * of two non-negative variables. The negative part always appears
2326 * immediately before the positive part.
2327 * Other than that, the variables have the following order
2329 * - sum of (1 - e_i) over all edges
2330 * - sum of positive and negative parts of all c_n coefficients
2331 * (unconstrained when computing non-parametric schedules)
2332 * - sum of positive and negative parts of all c_x coefficients
2333 * - for each edge
2334 * - e_i
2335 * - for each node
2336 * - c_i_0
2337 * - positive and negative parts of c_i_n (if parametric)
2338 * - positive and negative parts of c_i_x
2340 * The constraints are those from the (validity) edges plus three equalities
2341 * to express the sums and n_edge inequalities to express e_i <= 1.
2343 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2345 int i, j;
2346 int k;
2347 isl_space *dim;
2348 unsigned total;
2349 int n_eq, n_ineq;
2350 int n_edge;
2352 n_edge = 0;
2353 for (i = 0; i < graph->n_edge; ++i)
2354 n_edge += graph->edge[i].map->n;
2356 total = 3 + n_edge;
2357 for (i = 0; i < graph->n; ++i) {
2358 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2359 node->start = total;
2360 total += 1 + 2 * (node->nparam + node->nvar);
2363 if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
2364 return -1;
2366 dim = isl_space_set_alloc(ctx, 0, total);
2367 isl_basic_set_free(graph->lp);
2368 n_eq += 3;
2369 n_ineq += n_edge;
2370 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2371 graph->lp = isl_basic_set_set_rational(graph->lp);
2373 k = isl_basic_set_alloc_equality(graph->lp);
2374 if (k < 0)
2375 return -1;
2376 isl_seq_clr(graph->lp->eq[k], 1 + total);
2377 isl_int_set_si(graph->lp->eq[k][0], -n_edge);
2378 isl_int_set_si(graph->lp->eq[k][1], 1);
2379 for (i = 0; i < n_edge; ++i)
2380 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2382 k = isl_basic_set_alloc_equality(graph->lp);
2383 if (k < 0)
2384 return -1;
2385 isl_seq_clr(graph->lp->eq[k], 1 + total);
2386 isl_int_set_si(graph->lp->eq[k][2], -1);
2387 for (i = 0; i < graph->n; ++i) {
2388 int pos = 1 + graph->node[i].start + 1;
2390 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2391 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2394 k = isl_basic_set_alloc_equality(graph->lp);
2395 if (k < 0)
2396 return -1;
2397 isl_seq_clr(graph->lp->eq[k], 1 + total);
2398 isl_int_set_si(graph->lp->eq[k][3], -1);
2399 for (i = 0; i < graph->n; ++i) {
2400 struct isl_sched_node *node = &graph->node[i];
2401 int pos = 1 + node->start + 1 + 2 * node->nparam;
2403 for (j = 0; j < 2 * node->nvar; ++j)
2404 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2407 for (i = 0; i < n_edge; ++i) {
2408 k = isl_basic_set_alloc_inequality(graph->lp);
2409 if (k < 0)
2410 return -1;
2411 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2412 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2413 isl_int_set_si(graph->lp->ineq[k][0], 1);
2416 if (add_all_constraints(graph) < 0)
2417 return -1;
2419 return 0;
2422 /* If the schedule_split_scaled option is set and if the linear
2423 * parts of the scheduling rows for all nodes in the graphs have
2424 * non-trivial common divisor, then split off the constant term
2425 * from the linear part.
2426 * The constant term is then placed in a separate band and
2427 * the linear part is reduced.
2429 static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph)
2431 int i;
2432 int row;
2433 isl_int gcd, gcd_i;
2435 if (!ctx->opt->schedule_split_scaled)
2436 return 0;
2437 if (graph->n <= 1)
2438 return 0;
2440 isl_int_init(gcd);
2441 isl_int_init(gcd_i);
2443 isl_int_set_si(gcd, 0);
2445 row = isl_mat_rows(graph->node[0].sched) - 1;
2447 for (i = 0; i < graph->n; ++i) {
2448 struct isl_sched_node *node = &graph->node[i];
2449 int cols = isl_mat_cols(node->sched);
2451 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
2452 isl_int_gcd(gcd, gcd, gcd_i);
2455 isl_int_clear(gcd_i);
2457 if (isl_int_cmp_si(gcd, 1) <= 0) {
2458 isl_int_clear(gcd);
2459 return 0;
2462 next_band(graph);
2464 for (i = 0; i < graph->n; ++i) {
2465 struct isl_sched_node *node = &graph->node[i];
2467 isl_map_free(node->sched_map);
2468 node->sched_map = NULL;
2469 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2470 if (!node->sched)
2471 goto error;
2472 isl_int_fdiv_r(node->sched->row[row + 1][0],
2473 node->sched->row[row][0], gcd);
2474 isl_int_fdiv_q(node->sched->row[row][0],
2475 node->sched->row[row][0], gcd);
2476 isl_int_mul(node->sched->row[row][0],
2477 node->sched->row[row][0], gcd);
2478 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
2479 if (!node->sched)
2480 goto error;
2481 node->band[graph->n_total_row] = graph->n_band;
2484 graph->n_total_row++;
2486 isl_int_clear(gcd);
2487 return 0;
2488 error:
2489 isl_int_clear(gcd);
2490 return -1;
2493 /* Construct a schedule row for each node such that as many dependences
2494 * as possible are carried and then continue with the next band.
2496 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2498 int i;
2499 int n_edge;
2500 isl_vec *sol;
2501 isl_basic_set *lp;
2503 n_edge = 0;
2504 for (i = 0; i < graph->n_edge; ++i)
2505 n_edge += graph->edge[i].map->n;
2507 if (setup_carry_lp(ctx, graph) < 0)
2508 return -1;
2510 lp = isl_basic_set_copy(graph->lp);
2511 sol = isl_tab_basic_set_non_neg_lexmin(lp);
2512 if (!sol)
2513 return -1;
2515 if (sol->size == 0) {
2516 isl_vec_free(sol);
2517 isl_die(ctx, isl_error_internal,
2518 "error in schedule construction", return -1);
2521 if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
2522 isl_vec_free(sol);
2523 isl_die(ctx, isl_error_unknown,
2524 "unable to carry dependences", return -1);
2527 if (update_schedule(graph, sol, 0, 0) < 0)
2528 return -1;
2530 if (split_scaled(ctx, graph) < 0)
2531 return -1;
2533 return compute_next_band(ctx, graph);
2536 /* Are there any (non-empty) validity edges in the graph?
2538 static int has_validity_edges(struct isl_sched_graph *graph)
2540 int i;
2542 for (i = 0; i < graph->n_edge; ++i) {
2543 int empty;
2545 empty = isl_map_plain_is_empty(graph->edge[i].map);
2546 if (empty < 0)
2547 return -1;
2548 if (empty)
2549 continue;
2550 if (graph->edge[i].validity)
2551 return 1;
2554 return 0;
2557 /* Should we apply a Feautrier step?
2558 * That is, did the user request the Feautrier algorithm and are
2559 * there any validity dependences (left)?
2561 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
2563 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
2564 return 0;
2566 return has_validity_edges(graph);
2569 /* Compute a schedule for a connected dependence graph using Feautrier's
2570 * multi-dimensional scheduling algorithm.
2571 * The original algorithm is described in [1].
2572 * The main idea is to minimize the number of scheduling dimensions, by
2573 * trying to satisfy as many dependences as possible per scheduling dimension.
2575 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2576 * Problem, Part II: Multi-Dimensional Time.
2577 * In Intl. Journal of Parallel Programming, 1992.
2579 static int compute_schedule_wcc_feautrier(isl_ctx *ctx,
2580 struct isl_sched_graph *graph)
2582 return carry_dependences(ctx, graph);
2585 /* Compute a schedule for a connected dependence graph.
2586 * We try to find a sequence of as many schedule rows as possible that result
2587 * in non-negative dependence distances (independent of the previous rows
2588 * in the sequence, i.e., such that the sequence is tilable).
2589 * If we can't find any more rows we either
2590 * - split between SCCs and start over (assuming we found an interesting
2591 * pair of SCCs between which to split)
2592 * - continue with the next band (assuming the current band has at least
2593 * one row)
2594 * - try to carry as many dependences as possible and continue with the next
2595 * band
2597 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2598 * as many validity dependences as possible. When all validity dependences
2599 * are satisfied we extend the schedule to a full-dimensional schedule.
2601 * If we manage to complete the schedule, we finish off by topologically
2602 * sorting the statements based on the remaining dependences.
2604 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2605 * outermost dimension in the current band to be zero distance. If this
2606 * turns out to be impossible, we fall back on the general scheme above
2607 * and try to carry as many dependences as possible.
2609 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2611 int force_zero = 0;
2613 if (detect_sccs(graph) < 0)
2614 return -1;
2615 sort_sccs(graph);
2617 if (compute_maxvar(graph) < 0)
2618 return -1;
2620 if (need_feautrier_step(ctx, graph))
2621 return compute_schedule_wcc_feautrier(ctx, graph);
2623 if (ctx->opt->schedule_outer_zero_distance)
2624 force_zero = 1;
2626 while (graph->n_row < graph->maxvar) {
2627 isl_vec *sol;
2629 graph->src_scc = -1;
2630 graph->dst_scc = -1;
2632 if (setup_lp(ctx, graph, force_zero) < 0)
2633 return -1;
2634 sol = solve_lp(graph);
2635 if (!sol)
2636 return -1;
2637 if (sol->size == 0) {
2638 isl_vec_free(sol);
2639 if (!ctx->opt->schedule_maximize_band_depth &&
2640 graph->n_total_row > graph->band_start)
2641 return compute_next_band(ctx, graph);
2642 if (graph->src_scc >= 0)
2643 return compute_split_schedule(ctx, graph);
2644 if (graph->n_total_row > graph->band_start)
2645 return compute_next_band(ctx, graph);
2646 return carry_dependences(ctx, graph);
2648 if (update_schedule(graph, sol, 1, 1) < 0)
2649 return -1;
2650 force_zero = 0;
2653 if (graph->n_total_row > graph->band_start)
2654 next_band(graph);
2655 return sort_statements(ctx, graph);
2658 /* Add a row to the schedules that separates the SCCs and move
2659 * to the next band.
2661 static int split_on_scc(struct isl_sched_graph *graph)
2663 int i;
2665 for (i = 0; i < graph->n; ++i) {
2666 struct isl_sched_node *node = &graph->node[i];
2667 int row = isl_mat_rows(node->sched);
2669 isl_map_free(node->sched_map);
2670 node->sched_map = NULL;
2671 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2672 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2673 node->scc);
2674 if (!node->sched)
2675 return -1;
2676 node->band[graph->n_total_row] = graph->n_band;
2679 graph->n_total_row++;
2680 next_band(graph);
2682 return 0;
2685 /* Compute a schedule for each component (identified by node->scc)
2686 * of the dependence graph separately and then combine the results.
2687 * Depending on the setting of schedule_fuse, a component may be
2688 * either weakly or strongly connected.
2690 * The band_id is adjusted such that each component has a separate id.
2691 * Note that the band_id may have already been set to a value different
2692 * from zero by compute_split_schedule.
2694 static int compute_component_schedule(isl_ctx *ctx,
2695 struct isl_sched_graph *graph)
2697 int wcc, i;
2698 int n, n_edge;
2699 int n_total_row, orig_total_row;
2700 int n_band, orig_band;
2702 if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN ||
2703 ctx->opt->schedule_separate_components)
2704 split_on_scc(graph);
2706 n_total_row = 0;
2707 orig_total_row = graph->n_total_row;
2708 n_band = 0;
2709 orig_band = graph->n_band;
2710 for (i = 0; i < graph->n; ++i)
2711 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2712 for (wcc = 0; wcc < graph->scc; ++wcc) {
2713 n = 0;
2714 for (i = 0; i < graph->n; ++i)
2715 if (graph->node[i].scc == wcc)
2716 n++;
2717 n_edge = 0;
2718 for (i = 0; i < graph->n_edge; ++i)
2719 if (graph->edge[i].src->scc == wcc &&
2720 graph->edge[i].dst->scc == wcc)
2721 n_edge++;
2723 if (compute_sub_schedule(ctx, graph, n, n_edge,
2724 &node_scc_exactly,
2725 &edge_scc_exactly, wcc, 1) < 0)
2726 return -1;
2727 if (graph->n_total_row > n_total_row)
2728 n_total_row = graph->n_total_row;
2729 graph->n_total_row = orig_total_row;
2730 if (graph->n_band > n_band)
2731 n_band = graph->n_band;
2732 graph->n_band = orig_band;
2735 graph->n_total_row = n_total_row;
2736 graph->n_band = n_band;
2738 return pad_schedule(graph);
2741 /* Compute a schedule for the given dependence graph.
2742 * We first check if the graph is connected (through validity dependences)
2743 * and, if not, compute a schedule for each component separately.
2744 * If schedule_fuse is set to minimal fusion, then we check for strongly
2745 * connected components instead and compute a separate schedule for
2746 * each such strongly connected component.
2748 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2750 if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) {
2751 if (detect_sccs(graph) < 0)
2752 return -1;
2753 } else {
2754 if (detect_wccs(graph) < 0)
2755 return -1;
2758 if (graph->scc > 1)
2759 return compute_component_schedule(ctx, graph);
2761 return compute_schedule_wcc(ctx, graph);
2764 /* Compute a schedule for the given union of domains that respects
2765 * all the validity dependences.
2766 * If the default isl scheduling algorithm is used, it tries to minimize
2767 * the dependence distances over the proximity dependences.
2768 * If Feautrier's scheduling algorithm is used, the proximity dependence
2769 * distances are only minimized during the extension to a full-dimensional
2770 * schedule.
2772 __isl_give isl_schedule *isl_union_set_compute_schedule(
2773 __isl_take isl_union_set *domain,
2774 __isl_take isl_union_map *validity,
2775 __isl_take isl_union_map *proximity)
2777 isl_ctx *ctx = isl_union_set_get_ctx(domain);
2778 isl_space *dim;
2779 struct isl_sched_graph graph = { 0 };
2780 isl_schedule *sched;
2781 struct isl_extract_edge_data data;
2783 domain = isl_union_set_align_params(domain,
2784 isl_union_map_get_space(validity));
2785 domain = isl_union_set_align_params(domain,
2786 isl_union_map_get_space(proximity));
2787 dim = isl_union_set_get_space(domain);
2788 validity = isl_union_map_align_params(validity, isl_space_copy(dim));
2789 proximity = isl_union_map_align_params(proximity, dim);
2791 if (!domain)
2792 goto error;
2794 graph.n = isl_union_set_n_set(domain);
2795 if (graph.n == 0)
2796 goto empty;
2797 if (graph_alloc(ctx, &graph, graph.n,
2798 isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2799 goto error;
2800 graph.root = 1;
2801 graph.n = 0;
2802 if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2803 goto error;
2804 if (graph_init_table(ctx, &graph) < 0)
2805 goto error;
2806 graph.max_edge[isl_edge_validity] = isl_union_map_n_map(validity);
2807 graph.max_edge[isl_edge_proximity] = isl_union_map_n_map(proximity);
2808 if (graph_init_edge_tables(ctx, &graph) < 0)
2809 goto error;
2810 graph.n_edge = 0;
2811 data.graph = &graph;
2812 data.type = isl_edge_validity;
2813 if (isl_union_map_foreach_map(validity, &extract_edge, &data) < 0)
2814 goto error;
2815 data.type = isl_edge_proximity;
2816 if (isl_union_map_foreach_map(proximity, &extract_edge, &data) < 0)
2817 goto error;
2819 if (compute_schedule(ctx, &graph) < 0)
2820 goto error;
2822 empty:
2823 sched = extract_schedule(&graph, isl_union_set_get_space(domain));
2825 graph_free(ctx, &graph);
2826 isl_union_set_free(domain);
2827 isl_union_map_free(validity);
2828 isl_union_map_free(proximity);
2830 return sched;
2831 error:
2832 graph_free(ctx, &graph);
2833 isl_union_set_free(domain);
2834 isl_union_map_free(validity);
2835 isl_union_map_free(proximity);
2836 return NULL;
2839 void *isl_schedule_free(__isl_take isl_schedule *sched)
2841 int i;
2842 if (!sched)
2843 return NULL;
2845 if (--sched->ref > 0)
2846 return NULL;
2848 for (i = 0; i < sched->n; ++i) {
2849 isl_multi_aff_free(sched->node[i].sched);
2850 free(sched->node[i].band_end);
2851 free(sched->node[i].band_id);
2852 free(sched->node[i].zero);
2854 isl_space_free(sched->dim);
2855 isl_band_list_free(sched->band_forest);
2856 free(sched);
2857 return NULL;
2860 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2862 return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
2865 /* Return an isl_union_map of the schedule. If we have already constructed
2866 * a band forest, then this band forest may have been modified so we need
2867 * to extract the isl_union_map from the forest rather than from
2868 * the originally computed schedule.
2870 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2872 int i;
2873 isl_union_map *umap;
2875 if (!sched)
2876 return NULL;
2878 if (sched->band_forest)
2879 return isl_band_list_get_suffix_schedule(sched->band_forest);
2881 umap = isl_union_map_empty(isl_space_copy(sched->dim));
2882 for (i = 0; i < sched->n; ++i) {
2883 isl_multi_aff *ma;
2885 ma = isl_multi_aff_copy(sched->node[i].sched);
2886 umap = isl_union_map_add_map(umap, isl_map_from_multi_aff(ma));
2889 return umap;
2892 static __isl_give isl_band_list *construct_band_list(
2893 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2894 int band_nr, int *parent_active, int n_active);
2896 /* Construct an isl_band structure for the band in the given schedule
2897 * with sequence number band_nr for the n_active nodes marked by active.
2898 * If the nodes don't have a band with the given sequence number,
2899 * then a band without members is created.
2901 * Because of the way the schedule is constructed, we know that
2902 * the position of the band inside the schedule of a node is the same
2903 * for all active nodes.
2905 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2906 __isl_keep isl_band *parent,
2907 int band_nr, int *active, int n_active)
2909 int i, j;
2910 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2911 isl_band *band;
2912 unsigned start, end;
2914 band = isl_band_alloc(ctx);
2915 if (!band)
2916 return NULL;
2918 band->schedule = schedule;
2919 band->parent = parent;
2921 for (i = 0; i < schedule->n; ++i)
2922 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2923 break;
2925 if (i < schedule->n) {
2926 band->children = construct_band_list(schedule, band,
2927 band_nr + 1, active, n_active);
2928 if (!band->children)
2929 goto error;
2932 for (i = 0; i < schedule->n; ++i)
2933 if (active[i])
2934 break;
2936 if (i >= schedule->n)
2937 isl_die(ctx, isl_error_internal,
2938 "band without active statements", goto error);
2940 start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2941 end = band_nr < schedule->node[i].n_band ?
2942 schedule->node[i].band_end[band_nr] : start;
2943 band->n = end - start;
2945 band->zero = isl_alloc_array(ctx, int, band->n);
2946 if (!band->zero)
2947 goto error;
2949 for (j = 0; j < band->n; ++j)
2950 band->zero[j] = schedule->node[i].zero[start + j];
2952 band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
2953 for (i = 0; i < schedule->n; ++i) {
2954 isl_multi_aff *ma;
2955 isl_pw_multi_aff *pma;
2956 unsigned n_out;
2958 if (!active[i])
2959 continue;
2961 ma = isl_multi_aff_copy(schedule->node[i].sched);
2962 n_out = isl_multi_aff_dim(ma, isl_dim_out);
2963 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end);
2964 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start);
2965 pma = isl_pw_multi_aff_from_multi_aff(ma);
2966 band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma,
2967 pma);
2969 if (!band->pma)
2970 goto error;
2972 return band;
2973 error:
2974 isl_band_free(band);
2975 return NULL;
2978 /* Construct a list of bands that start at the same position (with
2979 * sequence number band_nr) in the schedules of the nodes that
2980 * were active in the parent band.
2982 * A separate isl_band structure is created for each band_id
2983 * and for each node that does not have a band with sequence
2984 * number band_nr. In the latter case, a band without members
2985 * is created.
2986 * This ensures that if a band has any children, then each node
2987 * that was active in the band is active in exactly one of the children.
2989 static __isl_give isl_band_list *construct_band_list(
2990 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2991 int band_nr, int *parent_active, int n_active)
2993 int i, j;
2994 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2995 int *active;
2996 int n_band;
2997 isl_band_list *list;
2999 n_band = 0;
3000 for (i = 0; i < n_active; ++i) {
3001 for (j = 0; j < schedule->n; ++j) {
3002 if (!parent_active[j])
3003 continue;
3004 if (schedule->node[j].n_band <= band_nr)
3005 continue;
3006 if (schedule->node[j].band_id[band_nr] == i) {
3007 n_band++;
3008 break;
3012 for (j = 0; j < schedule->n; ++j)
3013 if (schedule->node[j].n_band <= band_nr)
3014 n_band++;
3016 if (n_band == 1) {
3017 isl_band *band;
3018 list = isl_band_list_alloc(ctx, n_band);
3019 band = construct_band(schedule, parent, band_nr,
3020 parent_active, n_active);
3021 return isl_band_list_add(list, band);
3024 active = isl_alloc_array(ctx, int, schedule->n);
3025 if (!active)
3026 return NULL;
3028 list = isl_band_list_alloc(ctx, n_band);
3030 for (i = 0; i < n_active; ++i) {
3031 int n = 0;
3032 isl_band *band;
3034 for (j = 0; j < schedule->n; ++j) {
3035 active[j] = parent_active[j] &&
3036 schedule->node[j].n_band > band_nr &&
3037 schedule->node[j].band_id[band_nr] == i;
3038 if (active[j])
3039 n++;
3041 if (n == 0)
3042 continue;
3044 band = construct_band(schedule, parent, band_nr, active, n);
3046 list = isl_band_list_add(list, band);
3048 for (i = 0; i < schedule->n; ++i) {
3049 isl_band *band;
3050 if (!parent_active[i])
3051 continue;
3052 if (schedule->node[i].n_band > band_nr)
3053 continue;
3054 for (j = 0; j < schedule->n; ++j)
3055 active[j] = j == i;
3056 band = construct_band(schedule, parent, band_nr, active, 1);
3057 list = isl_band_list_add(list, band);
3060 free(active);
3062 return list;
3065 /* Construct a band forest representation of the schedule and
3066 * return the list of roots.
3068 static __isl_give isl_band_list *construct_forest(
3069 __isl_keep isl_schedule *schedule)
3071 int i;
3072 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
3073 isl_band_list *forest;
3074 int *active;
3076 active = isl_alloc_array(ctx, int, schedule->n);
3077 if (!active)
3078 return NULL;
3080 for (i = 0; i < schedule->n; ++i)
3081 active[i] = 1;
3083 forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
3085 free(active);
3087 return forest;
3090 /* Return the roots of a band forest representation of the schedule.
3092 __isl_give isl_band_list *isl_schedule_get_band_forest(
3093 __isl_keep isl_schedule *schedule)
3095 if (!schedule)
3096 return NULL;
3097 if (!schedule->band_forest)
3098 schedule->band_forest = construct_forest(schedule);
3099 return isl_band_list_dup(schedule->band_forest);
3102 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
3103 __isl_keep isl_band_list *list);
3105 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
3106 __isl_keep isl_band *band)
3108 isl_band_list *children;
3110 p = isl_printer_start_line(p);
3111 p = isl_printer_print_union_pw_multi_aff(p, band->pma);
3112 p = isl_printer_end_line(p);
3114 if (!isl_band_has_children(band))
3115 return p;
3117 children = isl_band_get_children(band);
3119 p = isl_printer_indent(p, 4);
3120 p = print_band_list(p, children);
3121 p = isl_printer_indent(p, -4);
3123 isl_band_list_free(children);
3125 return p;
3128 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
3129 __isl_keep isl_band_list *list)
3131 int i, n;
3133 n = isl_band_list_n_band(list);
3134 for (i = 0; i < n; ++i) {
3135 isl_band *band;
3136 band = isl_band_list_get_band(list, i);
3137 p = print_band(p, band);
3138 isl_band_free(band);
3141 return p;
3144 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
3145 __isl_keep isl_schedule *schedule)
3147 isl_band_list *forest;
3149 forest = isl_schedule_get_band_forest(schedule);
3151 p = print_band_list(p, forest);
3153 isl_band_list_free(forest);
3155 return p;
3158 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
3160 isl_printer *printer;
3162 if (!schedule)
3163 return;
3165 printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
3166 printer = isl_printer_print_schedule(printer, schedule);
3168 isl_printer_free(printer);