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,
11 #include <isl_ctx_private.h>
12 #include <isl_map_private.h>
13 #include <isl_dim_private.h>
15 #include <isl/constraint.h>
16 #include <isl/schedule.h>
17 #include <isl_mat_private.h>
21 #include <isl_dim_map.h>
22 #include <isl_hmap_map_basic_set.h>
23 #include <isl_qsort.h>
24 #include <isl_schedule_private.h>
25 #include <isl_band_private.h>
28 * The scheduling algorithm implemented in this file was inspired by
29 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
30 * Parallelization and Locality Optimization in the Polyhedral Model".
34 /* Internal information about a node that is used during the construction
36 * dim represents the space in which the domain lives
37 * sched is a matrix representation of the schedule being constructed
39 * sched_map is an isl_map representation of the same (partial) schedule
40 * sched_map may be NULL
41 * rank is the number of linearly independent rows in the linear part
43 * the columns of cmap represent a change of basis for the schedule
44 * coefficients; the first rank columns span the linear part of
46 * start is the first variable in the LP problem in the sequences that
47 * represents the schedule coefficients of this node
48 * nvar is the dimension of the domain
49 * nparam is the number of parameters or 0 if we are not constructing
50 * a parametric schedule
52 * scc is the index of SCC (or WCC) this node belongs to
54 * band contains the band index for each of the rows of the schedule.
55 * band_id is used to differentiate between separate bands at the same
56 * level within the same parent band, i.e., bands that are separated
57 * by the parent band or bands that are independent of each other.
58 * parallel contains a boolean for each of the rows of the schedule,
59 * indicating whether the corresponding scheduling dimension is parallel
60 * within its band and with respect to the proximity edges.
62 * index, min_index and on_stack are used during the SCC detection
63 * index represents the order in which nodes are visited.
64 * min_index is the index of the root of a (sub)component.
65 * on_stack indicates whether the node is currently on the stack.
67 struct isl_sched_node {
89 static int node_has_dim(const void *entry, const void *val)
91 struct isl_sched_node *node = (struct isl_sched_node *)entry;
92 isl_dim *dim = (isl_dim *)val;
94 return isl_dim_equal(node->dim, dim);
97 /* An edge in the dependence graph. An edge may be used to
98 * ensure validity of the generated schedule, to minimize the dependence
101 * map is the dependence relation
102 * src is the source node
103 * dst is the sink node
104 * validity is set if the edge is used to ensure correctness
105 * proximity is set if the edge is used to minimize dependence distances
107 * For validity edges, start and end mark the sequence of inequality
108 * constraints in the LP problem that encode the validity constraint
109 * corresponding to this edge.
111 struct isl_sched_edge {
114 struct isl_sched_node *src;
115 struct isl_sched_node *dst;
124 /* Internal information about the dependence graph used during
125 * the construction of the schedule.
127 * intra_hmap is a cache, mapping dependence relations to their dual,
128 * for dependences from a node to itself
129 * inter_hmap is a cache, mapping dependence relations to their dual,
130 * for dependences between distinct nodes
132 * n is the number of nodes
133 * node is the list of nodes
134 * maxvar is the maximal number of variables over all nodes
135 * n_row is the current (maximal) number of linearly independent
136 * rows in the node schedules
137 * n_total_row is the current number of rows in the node schedules
138 * n_band is the current number of completed bands
139 * band_start is the starting row in the node schedules of the current band
140 * root is set if this graph is the original dependence graph,
141 * without any splitting
143 * sorted contains a list of node indices sorted according to the
144 * SCC to which a node belongs
146 * n_edge is the number of edges
147 * edge is the list of edges
148 * edge_table contains pointers into the edge array, hashed on the source
149 * and sink spaces; the table only contains edges that represent
150 * validity constraints (and that may or may not also represent proximity
153 * node_table contains pointers into the node array, hashed on the space
155 * region contains a list of variable sequences that should be non-trivial
157 * lp contains the (I)LP problem used to obtain new schedule rows
159 * src_scc and dst_scc are the source and sink SCCs of an edge with
160 * conflicting constraints
162 * scc, sp, index and stack are used during the detection of SCCs
163 * scc is the number of the next SCC
164 * stack contains the nodes on the path from the root to the current node
165 * sp is the stack pointer
166 * index is the index of the last node visited
168 struct isl_sched_graph {
169 isl_hmap_map_basic_set *intra_hmap;
170 isl_hmap_map_basic_set *inter_hmap;
172 struct isl_sched_node *node;
185 struct isl_sched_edge *edge;
187 struct isl_hash_table *edge_table;
189 struct isl_hash_table *node_table;
190 struct isl_region *region;
204 /* Initialize node_table based on the list of nodes.
206 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
210 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
211 if (!graph->node_table)
214 for (i = 0; i < graph->n; ++i) {
215 struct isl_hash_table_entry *entry;
218 hash = isl_dim_get_hash(graph->node[i].dim);
219 entry = isl_hash_table_find(ctx, graph->node_table, hash,
221 graph->node[i].dim, 1);
224 entry->data = &graph->node[i];
230 /* Return a pointer to the node that lives within the given space,
231 * or NULL if there is no such node.
233 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
234 struct isl_sched_graph *graph, __isl_keep isl_dim *dim)
236 struct isl_hash_table_entry *entry;
239 hash = isl_dim_get_hash(dim);
240 entry = isl_hash_table_find(ctx, graph->node_table, hash,
241 &node_has_dim, dim, 0);
243 return entry ? entry->data : NULL;
246 static int edge_has_src_and_dst(const void *entry, const void *val)
248 const struct isl_sched_edge *edge = entry;
249 const struct isl_sched_edge *temp = val;
251 return edge->src == temp->src && edge->dst == temp->dst;
254 /* Initialize edge_table based on the list of edges.
255 * Only edges with validity set are added to the table.
257 static int graph_init_edge_table(isl_ctx *ctx, struct isl_sched_graph *graph)
261 graph->edge_table = isl_hash_table_alloc(ctx, graph->n_edge);
262 if (!graph->edge_table)
265 for (i = 0; i < graph->n_edge; ++i) {
266 struct isl_hash_table_entry *entry;
269 if (!graph->edge[i].validity)
272 hash = isl_hash_init();
273 hash = isl_hash_builtin(hash, graph->edge[i].src);
274 hash = isl_hash_builtin(hash, graph->edge[i].dst);
275 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
276 &edge_has_src_and_dst,
280 entry->data = &graph->edge[i];
286 /* Check whether the dependence graph has a (validity) edge
287 * between the given two nodes.
289 static int graph_has_edge(struct isl_sched_graph *graph,
290 struct isl_sched_node *src, struct isl_sched_node *dst)
292 isl_ctx *ctx = isl_dim_get_ctx(src->dim);
293 struct isl_hash_table_entry *entry;
295 struct isl_sched_edge temp = { .src = src, .dst = dst };
296 struct isl_sched_edge *edge;
299 hash = isl_hash_init();
300 hash = isl_hash_builtin(hash, temp.src);
301 hash = isl_hash_builtin(hash, temp.dst);
302 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
303 &edge_has_src_and_dst, &temp, 0);
308 empty = isl_map_plain_is_empty(edge->map);
315 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
316 int n_node, int n_edge)
321 graph->n_edge = n_edge;
322 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
323 graph->sorted = isl_calloc_array(ctx, int, graph->n);
324 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
325 graph->stack = isl_alloc_array(ctx, int, graph->n);
326 graph->edge = isl_calloc_array(ctx,
327 struct isl_sched_edge, graph->n_edge);
329 graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
330 graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
332 if (!graph->node || !graph->region || !graph->stack || !graph->edge ||
336 for(i = 0; i < graph->n; ++i)
337 graph->sorted[i] = i;
342 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
346 isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
347 isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
349 for (i = 0; i < graph->n; ++i) {
350 isl_dim_free(graph->node[i].dim);
351 isl_mat_free(graph->node[i].sched);
352 isl_map_free(graph->node[i].sched_map);
353 isl_mat_free(graph->node[i].cmap);
355 free(graph->node[i].band);
356 free(graph->node[i].band_id);
357 free(graph->node[i].parallel);
362 for (i = 0; i < graph->n_edge; ++i)
363 isl_map_free(graph->edge[i].map);
367 isl_hash_table_free(ctx, graph->edge_table);
368 isl_hash_table_free(ctx, graph->node_table);
369 isl_basic_set_free(graph->lp);
372 /* Add a new node to the graph representing the given set.
374 static int extract_node(__isl_take isl_set *set, void *user)
380 struct isl_sched_graph *graph = user;
381 int *band, *band_id, *parallel;
383 ctx = isl_set_get_ctx(set);
384 dim = isl_set_get_dim(set);
386 nvar = isl_dim_size(dim, isl_dim_set);
387 nparam = isl_dim_size(dim, isl_dim_param);
388 if (!ctx->opt->schedule_parametric)
390 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
391 graph->node[graph->n].dim = dim;
392 graph->node[graph->n].nvar = nvar;
393 graph->node[graph->n].nparam = nparam;
394 graph->node[graph->n].sched = sched;
395 graph->node[graph->n].sched_map = NULL;
396 band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
397 graph->node[graph->n].band = band;
398 band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
399 graph->node[graph->n].band_id = band_id;
400 parallel = isl_calloc_array(ctx, int, graph->n_edge + nvar);
401 graph->node[graph->n].parallel = parallel;
404 if (!sched || !band || !band_id || !parallel)
410 /* Add a new edge to the graph based on the given map.
411 * Edges are first extracted from the validity dependences,
412 * from which the edge_table is constructed.
413 * Afterwards, the proximity dependences are added. If a proximity
414 * dependence relation happens to be identical to one of the
415 * validity dependence relations added before, then we don't create
416 * a new edge, but instead mark the original edge as also representing
417 * a proximity dependence.
419 static int extract_edge(__isl_take isl_map *map, void *user)
421 isl_ctx *ctx = isl_map_get_ctx(map);
422 struct isl_sched_graph *graph = user;
423 struct isl_sched_node *src, *dst;
426 dim = isl_dim_domain(isl_map_get_dim(map));
427 src = graph_find_node(ctx, graph, dim);
429 dim = isl_dim_range(isl_map_get_dim(map));
430 dst = graph_find_node(ctx, graph, dim);
438 graph->edge[graph->n_edge].src = src;
439 graph->edge[graph->n_edge].dst = dst;
440 graph->edge[graph->n_edge].map = map;
441 graph->edge[graph->n_edge].validity = !graph->edge_table;
442 graph->edge[graph->n_edge].proximity = !!graph->edge_table;
445 if (graph->edge_table) {
447 struct isl_hash_table_entry *entry;
448 struct isl_sched_edge *edge;
451 hash = isl_hash_init();
452 hash = isl_hash_builtin(hash, src);
453 hash = isl_hash_builtin(hash, dst);
454 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
455 &edge_has_src_and_dst,
456 &graph->edge[graph->n_edge - 1], 0);
460 is_equal = isl_map_plain_is_equal(map, edge->map);
474 /* Check whether there is a validity dependence from src to dst,
475 * forcing dst to follow src.
477 static int node_follows(struct isl_sched_graph *graph,
478 struct isl_sched_node *dst, struct isl_sched_node *src)
480 return graph_has_edge(graph, src, dst);
483 /* Perform Tarjan's algorithm for computing the strongly connected components
484 * in the dependence graph (only validity edges).
485 * If directed is not set, we consider the graph to be undirected and
486 * we effectively compute the (weakly) connected components.
488 static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed)
492 g->node[i].index = g->index;
493 g->node[i].min_index = g->index;
494 g->node[i].on_stack = 1;
496 g->stack[g->sp++] = i;
498 for (j = g->n - 1; j >= 0; --j) {
503 if (g->node[j].index >= 0 &&
504 (!g->node[j].on_stack ||
505 g->node[j].index > g->node[i].min_index))
508 f = node_follows(g, &g->node[i], &g->node[j]);
511 if (!f && !directed) {
512 f = node_follows(g, &g->node[j], &g->node[i]);
518 if (g->node[j].index < 0) {
519 detect_sccs_tarjan(g, j, directed);
520 if (g->node[j].min_index < g->node[i].min_index)
521 g->node[i].min_index = g->node[j].min_index;
522 } else if (g->node[j].index < g->node[i].min_index)
523 g->node[i].min_index = g->node[j].index;
526 if (g->node[i].index != g->node[i].min_index)
530 j = g->stack[--g->sp];
531 g->node[j].on_stack = 0;
532 g->node[j].scc = g->scc;
539 static int detect_ccs(struct isl_sched_graph *graph, int directed)
546 for (i = graph->n - 1; i >= 0; --i)
547 graph->node[i].index = -1;
549 for (i = graph->n - 1; i >= 0; --i) {
550 if (graph->node[i].index >= 0)
552 if (detect_sccs_tarjan(graph, i, directed) < 0)
559 /* Apply Tarjan's algorithm to detect the strongly connected components
560 * in the dependence graph.
562 static int detect_sccs(struct isl_sched_graph *graph)
564 return detect_ccs(graph, 1);
567 /* Apply Tarjan's algorithm to detect the (weakly) connected components
568 * in the dependence graph.
570 static int detect_wccs(struct isl_sched_graph *graph)
572 return detect_ccs(graph, 0);
575 static int cmp_scc(const void *a, const void *b, void *data)
577 struct isl_sched_graph *graph = data;
581 return graph->node[*i1].scc - graph->node[*i2].scc;
584 /* Sort the elements of graph->sorted according to the corresponding SCCs.
586 static void sort_sccs(struct isl_sched_graph *graph)
588 isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
591 /* Given a dependence relation R from a node to itself,
592 * construct the set of coefficients of valid constraints for elements
593 * in that dependence relation.
594 * In particular, the result contains tuples of coefficients
595 * c_0, c_n, c_x such that
597 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
601 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
603 * We choose here to compute the dual of delta R.
604 * Alternatively, we could have computed the dual of R, resulting
605 * in a set of tuples c_0, c_n, c_x, c_y, and then
606 * plugged in (c_0, c_n, c_x, -c_x).
608 static __isl_give isl_basic_set *intra_coefficients(
609 struct isl_sched_graph *graph, __isl_take isl_map *map)
611 isl_ctx *ctx = isl_map_get_ctx(map);
615 if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
616 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
618 delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
619 coef = isl_set_coefficients(delta);
620 isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
621 isl_basic_set_copy(coef));
626 /* Given a dependence relation R, * construct the set of coefficients
627 * of valid constraints for elements in that dependence relation.
628 * In particular, the result contains tuples of coefficients
629 * c_0, c_n, c_x, c_y such that
631 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
634 static __isl_give isl_basic_set *inter_coefficients(
635 struct isl_sched_graph *graph, __isl_take isl_map *map)
637 isl_ctx *ctx = isl_map_get_ctx(map);
641 if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
642 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
644 set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
645 coef = isl_set_coefficients(set);
646 isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
647 isl_basic_set_copy(coef));
652 /* Add constraints to graph->lp that force validity for the given
653 * dependence from a node i to itself.
654 * That is, add constraints that enforce
656 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
657 * = c_i_x (y - x) >= 0
659 * for each (x,y) in R.
660 * We obtain general constraints on coefficients (c_0, c_n, c_x)
661 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
662 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
663 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
665 * Actually, we do not construct constraints for the c_i_x themselves,
666 * but for the coefficients of c_i_x written as a linear combination
667 * of the columns in node->cmap.
669 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
670 struct isl_sched_edge *edge)
673 isl_map *map = isl_map_copy(edge->map);
674 isl_ctx *ctx = isl_map_get_ctx(map);
676 isl_dim_map *dim_map;
678 struct isl_sched_node *node = edge->src;
680 coef = intra_coefficients(graph, map);
682 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
684 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
685 isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap));
687 total = isl_basic_set_total_dim(graph->lp);
688 dim_map = isl_dim_map_alloc(ctx, total);
689 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
690 isl_dim_size(dim, isl_dim_set), 1,
692 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
693 isl_dim_size(dim, isl_dim_set), 1,
695 graph->lp = isl_basic_set_extend_constraints(graph->lp,
696 coef->n_eq, coef->n_ineq);
697 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
704 /* Add constraints to graph->lp that force validity for the given
705 * dependence from node i to node j.
706 * That is, add constraints that enforce
708 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
710 * for each (x,y) in R.
711 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
712 * of valid constraints for R and then plug in
713 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
714 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
715 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
716 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
718 * Actually, we do not construct constraints for the c_*_x themselves,
719 * but for the coefficients of c_*_x written as a linear combination
720 * of the columns in node->cmap.
722 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
723 struct isl_sched_edge *edge)
726 isl_map *map = isl_map_copy(edge->map);
727 isl_ctx *ctx = isl_map_get_ctx(map);
729 isl_dim_map *dim_map;
731 struct isl_sched_node *src = edge->src;
732 struct isl_sched_node *dst = edge->dst;
734 coef = inter_coefficients(graph, map);
736 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
738 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
739 isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap));
740 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
741 isl_dim_size(dim, isl_dim_set) + src->nvar,
742 isl_mat_copy(dst->cmap));
744 total = isl_basic_set_total_dim(graph->lp);
745 dim_map = isl_dim_map_alloc(ctx, total);
747 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
748 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
749 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
750 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
751 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
753 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
754 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
757 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
758 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
759 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
760 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
761 isl_dim_size(dim, isl_dim_set), 1,
763 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
764 isl_dim_size(dim, isl_dim_set), 1,
767 edge->start = graph->lp->n_ineq;
768 graph->lp = isl_basic_set_extend_constraints(graph->lp,
769 coef->n_eq, coef->n_ineq);
770 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
773 edge->end = graph->lp->n_ineq;
778 /* Add constraints to graph->lp that bound the dependence distance for the given
779 * dependence from a node i to itself.
780 * If s = 1, we add the constraint
782 * c_i_x (y - x) <= m_0 + m_n n
786 * -c_i_x (y - x) + m_0 + m_n n >= 0
788 * for each (x,y) in R.
789 * If s = -1, we add the constraint
791 * -c_i_x (y - x) <= m_0 + m_n n
795 * c_i_x (y - x) + m_0 + m_n n >= 0
797 * for each (x,y) in R.
798 * We obtain general constraints on coefficients (c_0, c_n, c_x)
799 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
800 * with each coefficient (except m_0) represented as a pair of non-negative
803 * Actually, we do not construct constraints for the c_i_x themselves,
804 * but for the coefficients of c_i_x written as a linear combination
805 * of the columns in node->cmap.
807 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
808 struct isl_sched_edge *edge, int s)
812 isl_map *map = isl_map_copy(edge->map);
813 isl_ctx *ctx = isl_map_get_ctx(map);
815 isl_dim_map *dim_map;
817 struct isl_sched_node *node = edge->src;
819 coef = intra_coefficients(graph, map);
821 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
823 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
824 isl_dim_size(dim, isl_dim_set), isl_mat_copy(node->cmap));
826 nparam = isl_dim_size(node->dim, isl_dim_param);
827 total = isl_basic_set_total_dim(graph->lp);
828 dim_map = isl_dim_map_alloc(ctx, total);
829 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
830 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
831 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
832 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
833 isl_dim_size(dim, isl_dim_set), 1,
835 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
836 isl_dim_size(dim, isl_dim_set), 1,
838 graph->lp = isl_basic_set_extend_constraints(graph->lp,
839 coef->n_eq, coef->n_ineq);
840 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
847 /* Add constraints to graph->lp that bound the dependence distance for the given
848 * dependence from node i to node j.
849 * If s = 1, we add the constraint
851 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
856 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
859 * for each (x,y) in R.
860 * If s = -1, we add the constraint
862 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
867 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
870 * for each (x,y) in R.
871 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
872 * of valid constraints for R and then plug in
873 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
875 * with each coefficient (except m_0, c_j_0 and c_i_0)
876 * represented as a pair of non-negative coefficients.
878 * Actually, we do not construct constraints for the c_*_x themselves,
879 * but for the coefficients of c_*_x written as a linear combination
880 * of the columns in node->cmap.
882 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
883 struct isl_sched_edge *edge, int s)
887 isl_map *map = isl_map_copy(edge->map);
888 isl_ctx *ctx = isl_map_get_ctx(map);
890 isl_dim_map *dim_map;
892 struct isl_sched_node *src = edge->src;
893 struct isl_sched_node *dst = edge->dst;
895 coef = inter_coefficients(graph, map);
897 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
899 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
900 isl_dim_size(dim, isl_dim_set), isl_mat_copy(src->cmap));
901 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
902 isl_dim_size(dim, isl_dim_set) + src->nvar,
903 isl_mat_copy(dst->cmap));
905 nparam = isl_dim_size(src->dim, isl_dim_param);
906 total = isl_basic_set_total_dim(graph->lp);
907 dim_map = isl_dim_map_alloc(ctx, total);
909 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
910 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
911 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
913 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
914 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
915 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
916 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
917 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
919 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
920 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
923 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
924 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
925 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
926 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
927 isl_dim_size(dim, isl_dim_set), 1,
929 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
930 isl_dim_size(dim, isl_dim_set), 1,
933 graph->lp = isl_basic_set_extend_constraints(graph->lp,
934 coef->n_eq, coef->n_ineq);
935 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
942 static int add_all_validity_constraints(struct isl_sched_graph *graph)
946 for (i = 0; i < graph->n_edge; ++i) {
947 struct isl_sched_edge *edge= &graph->edge[i];
950 if (edge->src != edge->dst)
952 if (add_intra_validity_constraints(graph, edge) < 0)
956 for (i = 0; i < graph->n_edge; ++i) {
957 struct isl_sched_edge *edge = &graph->edge[i];
960 if (edge->src == edge->dst)
962 if (add_inter_validity_constraints(graph, edge) < 0)
969 /* Add constraints to graph->lp that bound the dependence distance
970 * for all dependence relations.
971 * If a given proximity dependence is identical to a validity
972 * dependence, then the dependence distance is already bounded
973 * from below (by zero), so we only need to bound the distance
975 * Otherwise, we need to bound the distance both from above and from below.
977 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
981 for (i = 0; i < graph->n_edge; ++i) {
982 struct isl_sched_edge *edge= &graph->edge[i];
983 if (!edge->proximity)
985 if (edge->src == edge->dst &&
986 add_intra_proximity_constraints(graph, edge, 1) < 0)
988 if (edge->src != edge->dst &&
989 add_inter_proximity_constraints(graph, edge, 1) < 0)
993 if (edge->src == edge->dst &&
994 add_intra_proximity_constraints(graph, edge, -1) < 0)
996 if (edge->src != edge->dst &&
997 add_inter_proximity_constraints(graph, edge, -1) < 0)
1004 /* Compute a basis for the rows in the linear part of the schedule
1005 * and extend this basis to a full basis. The remaining rows
1006 * can then be used to force linear independence from the rows
1009 * In particular, given the schedule rows S, we compute
1013 * with H the Hermite normal form of S. That is, all but the
1014 * first rank columns of Q are zero and so each row in S is
1015 * a linear combination of the first rank rows of Q.
1016 * The matrix Q is then transposed because we will write the
1017 * coefficients of the next schedule row as a column vector s
1018 * and express this s as a linear combination s = Q c of the
1021 static int node_update_cmap(struct isl_sched_node *node)
1024 int n_row = isl_mat_rows(node->sched);
1026 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1027 1 + node->nparam, node->nvar);
1029 H = isl_mat_left_hermite(H, 0, NULL, &Q);
1030 isl_mat_free(node->cmap);
1031 node->cmap = isl_mat_transpose(Q);
1032 node->rank = isl_mat_initial_non_zero_cols(H);
1035 if (!node->cmap || node->rank < 0)
1040 /* Count the number of equality and inequality constraints
1041 * that will be added. If once is set, then we count
1042 * each edge exactly once. Otherwise, we count as follows
1043 * validity -> 1 (>= 0)
1044 * validity+proximity -> 2 (>= 0 and upper bound)
1045 * proximity -> 2 (lower and upper bound)
1047 static int count_constraints(struct isl_sched_graph *graph,
1048 int *n_eq, int *n_ineq, int once)
1051 isl_basic_set *coef;
1053 *n_eq = *n_ineq = 0;
1054 for (i = 0; i < graph->n_edge; ++i) {
1055 struct isl_sched_edge *edge= &graph->edge[i];
1056 isl_map *map = isl_map_copy(edge->map);
1057 int f = once ? 1 : edge->proximity ? 2 : 1;
1059 if (edge->src == edge->dst)
1060 coef = intra_coefficients(graph, map);
1062 coef = inter_coefficients(graph, map);
1065 *n_eq += f * coef->n_eq;
1066 *n_ineq += f * coef->n_ineq;
1067 isl_basic_set_free(coef);
1073 /* Construct an ILP problem for finding schedule coefficients
1074 * that result in non-negative, but small dependence distances
1075 * over all dependences.
1076 * In particular, the dependence distances over proximity edges
1077 * are bounded by m_0 + m_n n and we compute schedule coefficients
1078 * with small values (preferably zero) of m_n and m_0.
1080 * All variables of the ILP are non-negative. The actual coefficients
1081 * may be negative, so each coefficient is represented as the difference
1082 * of two non-negative variables. The negative part always appears
1083 * immediately before the positive part.
1084 * Other than that, the variables have the following order
1086 * - sum of positive and negative parts of m_n coefficients
1088 * - sum of positive and negative parts of all c_n coefficients
1089 * (unconstrained when computing non-parametric schedules)
1090 * - sum of positive and negative parts of all c_x coefficients
1091 * - positive and negative parts of m_n coefficients
1094 * - positive and negative parts of c_i_n (if parametric)
1095 * - positive and negative parts of c_i_x
1097 * The c_i_x are not represented directly, but through the columns of
1098 * node->cmap. That is, the computed values are for variable t_i_x
1099 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1101 * The constraints are those from the edges plus two or three equalities
1102 * to express the sums.
1104 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
1115 parametric = ctx->opt->schedule_parametric;
1116 nparam = isl_dim_size(graph->node[0].dim, isl_dim_param);
1118 total = param_pos + 2 * nparam;
1119 for (i = 0; i < graph->n; ++i) {
1120 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1121 if (node_update_cmap(node) < 0)
1123 node->start = total;
1124 total += 1 + 2 * (node->nparam + node->nvar);
1127 if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0)
1130 dim = isl_dim_set_alloc(ctx, 0, total);
1131 isl_basic_set_free(graph->lp);
1132 n_eq += 2 + parametric;
1133 graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq);
1135 k = isl_basic_set_alloc_equality(graph->lp);
1138 isl_seq_clr(graph->lp->eq[k], 1 + total);
1139 isl_int_set_si(graph->lp->eq[k][1], -1);
1140 for (i = 0; i < 2 * nparam; ++i)
1141 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1144 k = isl_basic_set_alloc_equality(graph->lp);
1147 isl_seq_clr(graph->lp->eq[k], 1 + total);
1148 isl_int_set_si(graph->lp->eq[k][3], -1);
1149 for (i = 0; i < graph->n; ++i) {
1150 int pos = 1 + graph->node[i].start + 1;
1152 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1153 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1157 k = isl_basic_set_alloc_equality(graph->lp);
1160 isl_seq_clr(graph->lp->eq[k], 1 + total);
1161 isl_int_set_si(graph->lp->eq[k][4], -1);
1162 for (i = 0; i < graph->n; ++i) {
1163 struct isl_sched_node *node = &graph->node[i];
1164 int pos = 1 + node->start + 1 + 2 * node->nparam;
1166 for (j = 0; j < 2 * node->nvar; ++j)
1167 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1170 if (add_all_validity_constraints(graph) < 0)
1172 if (add_all_proximity_constraints(graph) < 0)
1178 /* Analyze the conflicting constraint found by
1179 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1180 * constraint of one of the edges between distinct nodes, living, moreover
1181 * in distinct SCCs, then record the source and sink SCC as this may
1182 * be a good place to cut between SCCs.
1184 static int check_conflict(int con, void *user)
1187 struct isl_sched_graph *graph = user;
1189 if (graph->src_scc >= 0)
1192 con -= graph->lp->n_eq;
1194 if (con >= graph->lp->n_ineq)
1197 for (i = 0; i < graph->n_edge; ++i) {
1198 if (!graph->edge[i].validity)
1200 if (graph->edge[i].src == graph->edge[i].dst)
1202 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1204 if (graph->edge[i].start > con)
1206 if (graph->edge[i].end <= con)
1208 graph->src_scc = graph->edge[i].src->scc;
1209 graph->dst_scc = graph->edge[i].dst->scc;
1215 /* Check whether the next schedule row of the given node needs to be
1216 * non-trivial. Lower-dimensional domains may have some trivial rows,
1217 * but as soon as the number of remaining required non-trivial rows
1218 * is as large as the number or remaining rows to be computed,
1219 * all remaining rows need to be non-trivial.
1221 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1223 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1226 /* Solve the ILP problem constructed in setup_lp.
1227 * For each node such that all the remaining rows of its schedule
1228 * need to be non-trivial, we construct a non-triviality region.
1229 * This region imposes that the next row is independent of previous rows.
1230 * In particular the coefficients c_i_x are represented by t_i_x
1231 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1232 * its first columns span the rows of the previously computed part
1233 * of the schedule. The non-triviality region enforces that at least
1234 * one of the remaining components of t_i_x is non-zero, i.e.,
1235 * that the new schedule row depends on at least one of the remaining
1238 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1244 for (i = 0; i < graph->n; ++i) {
1245 struct isl_sched_node *node = &graph->node[i];
1246 int skip = node->rank;
1247 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1248 if (needs_row(graph, node))
1249 graph->region[i].len = 2 * (node->nvar - skip);
1251 graph->region[i].len = 0;
1253 lp = isl_basic_set_copy(graph->lp);
1254 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1255 graph->region, &check_conflict, graph);
1259 /* Update the schedules of all nodes based on the given solution
1260 * of the LP problem.
1261 * The new row is added to the current band.
1262 * All possibly negative coefficients are encoded as a difference
1263 * of two non-negative variables, so we need to perform the subtraction
1264 * here. Moreover, if use_cmap is set, then the solution does
1265 * not refer to the actual coefficients c_i_x, but instead to variables
1266 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1267 * In this case, we then also need to perform this multiplication
1268 * to obtain the values of c_i_x.
1270 * If check_parallel is set, then the first two coordinates of sol are
1271 * assumed to correspond to the dependence distance. If these two
1272 * coordinates are zero, then the corresponding scheduling dimension
1273 * is marked as being parallel.
1275 static int update_schedule(struct isl_sched_graph *graph,
1276 __isl_take isl_vec *sol, int use_cmap, int check_parallel)
1280 isl_vec *csol = NULL;
1285 isl_die(sol->ctx, isl_error_internal,
1286 "no solution found", goto error);
1289 parallel = isl_int_is_zero(sol->el[1]) &&
1290 isl_int_is_zero(sol->el[2]);
1292 for (i = 0; i < graph->n; ++i) {
1293 struct isl_sched_node *node = &graph->node[i];
1294 int pos = node->start;
1295 int row = isl_mat_rows(node->sched);
1298 csol = isl_vec_alloc(sol->ctx, node->nvar);
1302 isl_map_free(node->sched_map);
1303 node->sched_map = NULL;
1304 node->sched = isl_mat_add_rows(node->sched, 1);
1307 node->sched = isl_mat_set_element(node->sched, row, 0,
1309 for (j = 0; j < node->nparam + node->nvar; ++j)
1310 isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1311 sol->el[1 + pos + 1 + 2 * j + 1],
1312 sol->el[1 + pos + 1 + 2 * j]);
1313 for (j = 0; j < node->nparam; ++j)
1314 node->sched = isl_mat_set_element(node->sched,
1315 row, 1 + j, sol->el[1+pos+1+2*j+1]);
1316 for (j = 0; j < node->nvar; ++j)
1317 isl_int_set(csol->el[j],
1318 sol->el[1+pos+1+2*(node->nparam+j)+1]);
1320 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1324 for (j = 0; j < node->nvar; ++j)
1325 node->sched = isl_mat_set_element(node->sched,
1326 row, 1 + node->nparam + j, csol->el[j]);
1327 node->band[graph->n_total_row] = graph->n_band;
1328 node->parallel[graph->n_total_row] = parallel;
1334 graph->n_total_row++;
1343 /* Convert node->sched into a map and return this map.
1344 * We simply add equality constraints that express each output variable
1345 * as the affine combination of parameters and input variables specified
1346 * by the schedule matrix.
1348 * The result is cached in node->sched_map, which needs to be released
1349 * whenever node->sched is updated.
1351 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1355 isl_basic_map *bmap;
1360 if (node->sched_map)
1361 return isl_map_copy(node->sched_map);
1363 nrow = isl_mat_rows(node->sched);
1364 ncol = isl_mat_cols(node->sched) - 1;
1365 dim = isl_dim_from_domain(isl_dim_copy(node->dim));
1366 dim = isl_dim_add(dim, isl_dim_out, nrow);
1367 bmap = isl_basic_map_universe(isl_dim_copy(dim));
1371 for (i = 0; i < nrow; ++i) {
1372 c = isl_equality_alloc(isl_dim_copy(dim));
1373 isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
1374 isl_mat_get_element(node->sched, i, 0, &v);
1375 isl_constraint_set_constant(c, v);
1376 for (j = 0; j < node->nparam; ++j) {
1377 isl_mat_get_element(node->sched, i, 1 + j, &v);
1378 isl_constraint_set_coefficient(c, isl_dim_param, j, v);
1380 for (j = 0; j < node->nvar; ++j) {
1381 isl_mat_get_element(node->sched,
1382 i, 1 + node->nparam + j, &v);
1383 isl_constraint_set_coefficient(c, isl_dim_in, j, v);
1385 bmap = isl_basic_map_add_constraint(bmap, c);
1392 node->sched_map = isl_map_from_basic_map(bmap);
1393 return isl_map_copy(node->sched_map);
1396 /* Update the given dependence relation based on the current schedule.
1397 * That is, intersect the dependence relation with a map expressing
1398 * that source and sink are executed within the same iteration of
1399 * the current schedule.
1400 * This is not the most efficient way, but this shouldn't be a critical
1403 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1404 struct isl_sched_node *src, struct isl_sched_node *dst)
1406 isl_map *src_sched, *dst_sched, *id;
1408 src_sched = node_extract_schedule(src);
1409 dst_sched = node_extract_schedule(dst);
1410 id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1411 return isl_map_intersect(map, id);
1414 /* Update the dependence relations of all edges based on the current schedule.
1415 * If a dependence is carried completely by the current schedule, then
1416 * it is removed and edge_table is updated accordingly.
1418 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1421 int reset_table = 0;
1423 for (i = graph->n_edge - 1; i >= 0; --i) {
1424 struct isl_sched_edge *edge = &graph->edge[i];
1425 edge->map = specialize(edge->map, edge->src, edge->dst);
1429 if (isl_map_plain_is_empty(edge->map)) {
1431 isl_map_free(edge->map);
1432 if (i != graph->n_edge - 1)
1433 graph->edge[i] = graph->edge[graph->n_edge - 1];
1439 isl_hash_table_free(ctx, graph->edge_table);
1440 graph->edge_table = NULL;
1441 return graph_init_edge_table(ctx, graph);
1447 static void next_band(struct isl_sched_graph *graph)
1449 graph->band_start = graph->n_total_row;
1453 /* Topologically sort statements mapped to same schedule iteration
1454 * and add a row to the schedule corresponding to this order.
1456 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1463 if (update_edges(ctx, graph) < 0)
1466 if (graph->n_edge == 0)
1469 if (detect_sccs(graph) < 0)
1472 for (i = 0; i < graph->n; ++i) {
1473 struct isl_sched_node *node = &graph->node[i];
1474 int row = isl_mat_rows(node->sched);
1475 int cols = isl_mat_cols(node->sched);
1477 isl_map_free(node->sched_map);
1478 node->sched_map = NULL;
1479 node->sched = isl_mat_add_rows(node->sched, 1);
1482 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1484 for (j = 1; j < cols; ++j)
1485 node->sched = isl_mat_set_element_si(node->sched,
1487 node->band[graph->n_total_row] = graph->n_band;
1490 graph->n_total_row++;
1496 /* Construct an isl_schedule based on the computed schedule stored
1497 * in graph and with parameters specified by dim.
1499 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1500 __isl_take isl_dim *dim)
1504 isl_schedule *sched = NULL;
1509 ctx = isl_dim_get_ctx(dim);
1510 sched = isl_calloc(ctx, struct isl_schedule,
1511 sizeof(struct isl_schedule) +
1512 (graph->n - 1) * sizeof(struct isl_schedule_node));
1517 sched->n = graph->n;
1518 sched->n_band = graph->n_band;
1519 sched->n_total_row = graph->n_total_row;
1521 for (i = 0; i < sched->n; ++i) {
1523 int *band_end, *band_id, *parallel;
1525 band_end = isl_alloc_array(ctx, int, graph->n_band);
1526 band_id = isl_alloc_array(ctx, int, graph->n_band);
1527 parallel = isl_alloc_array(ctx, int, graph->n_total_row);
1528 sched->node[i].sched = node_extract_schedule(&graph->node[i]);
1529 sched->node[i].band_end = band_end;
1530 sched->node[i].band_id = band_id;
1531 sched->node[i].parallel = parallel;
1532 if (!band_end || !band_id || !parallel)
1535 for (r = 0; r < graph->n_total_row; ++r)
1536 parallel[r] = graph->node[i].parallel[r];
1537 for (r = b = 0; r < graph->n_total_row; ++r) {
1538 if (graph->node[i].band[r] == b)
1541 if (graph->node[i].band[r] == -1)
1544 if (r == graph->n_total_row)
1546 sched->node[i].n_band = b;
1547 for (--b; b >= 0; --b)
1548 band_id[b] = graph->node[i].band_id[b];
1556 isl_schedule_free(sched);
1560 /* Copy nodes that satisfy node_pred from the src dependence graph
1561 * to the dst dependence graph.
1563 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1564 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1569 for (i = 0; i < src->n; ++i) {
1570 if (!node_pred(&src->node[i], data))
1572 dst->node[dst->n].dim = isl_dim_copy(src->node[i].dim);
1573 dst->node[dst->n].nvar = src->node[i].nvar;
1574 dst->node[dst->n].nparam = src->node[i].nparam;
1575 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1576 dst->node[dst->n].sched_map =
1577 isl_map_copy(src->node[i].sched_map);
1578 dst->node[dst->n].band = src->node[i].band;
1579 dst->node[dst->n].band_id = src->node[i].band_id;
1580 dst->node[dst->n].parallel = src->node[i].parallel;
1587 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1588 * to the dst dependence graph.
1590 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1591 struct isl_sched_graph *src,
1592 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1597 for (i = 0; i < src->n_edge; ++i) {
1598 struct isl_sched_edge *edge = &src->edge[i];
1601 if (!edge_pred(edge, data))
1604 if (isl_map_plain_is_empty(edge->map))
1607 map = isl_map_copy(edge->map);
1609 dst->edge[dst->n_edge].src =
1610 graph_find_node(ctx, dst, edge->src->dim);
1611 dst->edge[dst->n_edge].dst =
1612 graph_find_node(ctx, dst, edge->dst->dim);
1613 dst->edge[dst->n_edge].map = map;
1614 dst->edge[dst->n_edge].validity = edge->validity;
1615 dst->edge[dst->n_edge].proximity = edge->proximity;
1622 /* Given a "src" dependence graph that contains the nodes from "dst"
1623 * that satisfy node_pred, copy the schedule computed in "src"
1624 * for those nodes back to "dst".
1626 static int copy_schedule(struct isl_sched_graph *dst,
1627 struct isl_sched_graph *src,
1628 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1633 for (i = 0; i < dst->n; ++i) {
1634 if (!node_pred(&dst->node[i], data))
1636 isl_mat_free(dst->node[i].sched);
1637 isl_map_free(dst->node[i].sched_map);
1638 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1639 dst->node[i].sched_map =
1640 isl_map_copy(src->node[src->n].sched_map);
1644 dst->n_total_row = src->n_total_row;
1645 dst->n_band = src->n_band;
1650 /* Compute the maximal number of variables over all nodes.
1651 * This is the maximal number of linearly independent schedule
1652 * rows that we need to compute.
1653 * Just in case we end up in a part of the dependence graph
1654 * with only lower-dimensional domains, we make sure we will
1655 * compute the required amount of extra linearly independent rows.
1657 static int compute_maxvar(struct isl_sched_graph *graph)
1662 for (i = 0; i < graph->n; ++i) {
1663 struct isl_sched_node *node = &graph->node[i];
1666 if (node_update_cmap(node) < 0)
1668 nvar = node->nvar + graph->n_row - node->rank;
1669 if (nvar > graph->maxvar)
1670 graph->maxvar = nvar;
1676 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1677 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1679 /* Compute a schedule for a subgraph of "graph". In particular, for
1680 * the graph composed of nodes that satisfy node_pred and edges that
1681 * that satisfy edge_pred. The caller should precompute the number
1682 * of nodes and edges that satisfy these predicates and pass them along
1683 * as "n" and "n_edge".
1684 * If the subgraph is known to consist of a single component, then wcc should
1685 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1686 * Otherwise, we call compute_schedule, which will check whether the subgraph
1689 static int compute_sub_schedule(isl_ctx *ctx,
1690 struct isl_sched_graph *graph, int n, int n_edge,
1691 int (*node_pred)(struct isl_sched_node *node, int data),
1692 int (*edge_pred)(struct isl_sched_edge *edge, int data),
1695 struct isl_sched_graph split = { 0 };
1697 if (graph_alloc(ctx, &split, n, n_edge) < 0)
1699 if (copy_nodes(&split, graph, node_pred, data) < 0)
1701 if (graph_init_table(ctx, &split) < 0)
1703 if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1705 if (graph_init_edge_table(ctx, &split) < 0)
1707 split.n_row = graph->n_row;
1708 split.n_total_row = graph->n_total_row;
1709 split.n_band = graph->n_band;
1710 split.band_start = graph->band_start;
1712 if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1714 if (!wcc && compute_schedule(ctx, &split) < 0)
1717 copy_schedule(graph, &split, node_pred, data);
1719 graph_free(ctx, &split);
1722 graph_free(ctx, &split);
1726 static int node_scc_exactly(struct isl_sched_node *node, int scc)
1728 return node->scc == scc;
1731 static int node_scc_at_most(struct isl_sched_node *node, int scc)
1733 return node->scc <= scc;
1736 static int node_scc_at_least(struct isl_sched_node *node, int scc)
1738 return node->scc >= scc;
1741 static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc)
1743 return edge->src->scc == scc;
1746 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
1748 return edge->dst->scc <= scc;
1751 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
1753 return edge->src->scc >= scc;
1756 /* Pad the schedules of all nodes with zero rows such that in the end
1757 * they all have graph->n_total_row rows.
1758 * The extra rows don't belong to any band, so they get assigned band number -1.
1760 static int pad_schedule(struct isl_sched_graph *graph)
1764 for (i = 0; i < graph->n; ++i) {
1765 struct isl_sched_node *node = &graph->node[i];
1766 int row = isl_mat_rows(node->sched);
1767 if (graph->n_total_row > row) {
1768 isl_map_free(node->sched_map);
1769 node->sched_map = NULL;
1771 node->sched = isl_mat_add_zero_rows(node->sched,
1772 graph->n_total_row - row);
1775 for (j = row; j < graph->n_total_row; ++j)
1782 /* Split the current graph into two parts and compute a schedule for each
1783 * part individually. In particular, one part consists of all SCCs up
1784 * to and including graph->src_scc, while the other part contains the other
1787 * The split is enforced in the schedule by constant rows with two different
1788 * values (0 and 1). These constant rows replace the previously computed rows
1789 * in the current band.
1790 * It would be possible to reuse them as the first rows in the next
1791 * band, but recomputing them may result in better rows as we are looking
1792 * at a smaller part of the dependence graph.
1794 * The band_id of the second group is set to n, where n is the number
1795 * of nodes in the first group. This ensures that the band_ids over
1796 * the two groups remain disjoint, even if either or both of the two
1797 * groups contain independent components.
1799 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
1801 int i, j, n, e1, e2;
1802 int n_total_row, orig_total_row;
1803 int n_band, orig_band;
1806 drop = graph->n_total_row - graph->band_start;
1807 graph->n_total_row -= drop;
1808 graph->n_row -= drop;
1811 for (i = 0; i < graph->n; ++i) {
1812 struct isl_sched_node *node = &graph->node[i];
1813 int row = isl_mat_rows(node->sched) - drop;
1814 int cols = isl_mat_cols(node->sched);
1815 int before = node->scc <= graph->src_scc;
1820 isl_map_free(node->sched_map);
1821 node->sched_map = NULL;
1822 node->sched = isl_mat_drop_rows(node->sched,
1823 graph->band_start, drop);
1824 node->sched = isl_mat_add_rows(node->sched, 1);
1827 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1829 for (j = 1; j < cols; ++j)
1830 node->sched = isl_mat_set_element_si(node->sched,
1832 node->band[graph->n_total_row] = graph->n_band;
1836 for (i = 0; i < graph->n_edge; ++i) {
1837 if (graph->edge[i].dst->scc <= graph->src_scc)
1839 if (graph->edge[i].src->scc > graph->src_scc)
1843 graph->n_total_row++;
1846 for (i = 0; i < graph->n; ++i) {
1847 struct isl_sched_node *node = &graph->node[i];
1848 if (node->scc > graph->src_scc)
1849 node->band_id[graph->n_band] = n;
1852 orig_total_row = graph->n_total_row;
1853 orig_band = graph->n_band;
1854 if (compute_sub_schedule(ctx, graph, n, e1,
1855 &node_scc_at_most, &edge_dst_scc_at_most,
1856 graph->src_scc, 0) < 0)
1858 n_total_row = graph->n_total_row;
1859 graph->n_total_row = orig_total_row;
1860 n_band = graph->n_band;
1861 graph->n_band = orig_band;
1862 if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
1863 &node_scc_at_least, &edge_src_scc_at_least,
1864 graph->src_scc + 1, 0) < 0)
1866 if (n_total_row > graph->n_total_row)
1867 graph->n_total_row = n_total_row;
1868 if (n_band > graph->n_band)
1869 graph->n_band = n_band;
1871 return pad_schedule(graph);
1874 /* Compute the next band of the schedule after updating the dependence
1875 * relations based on the the current schedule.
1877 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
1879 if (update_edges(ctx, graph) < 0)
1883 return compute_schedule(ctx, graph);
1886 /* Add constraints to graph->lp that force the dependence of edge i
1887 * to be respected and attempt to carry it, where edge i is one from
1888 * a node j to itself.
1889 * That is, add constraints that enforce
1891 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
1892 * = c_j_x (y - x) >= e_i
1894 * for each (x,y) in R.
1895 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1896 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
1897 * with each coefficient in c_j_x represented as a pair of non-negative
1900 static int add_intra_constraints(struct isl_sched_graph *graph, int i)
1903 struct isl_sched_edge *edge= &graph->edge[i];
1904 isl_map *map = isl_map_copy(edge->map);
1905 isl_ctx *ctx = isl_map_get_ctx(map);
1907 isl_dim_map *dim_map;
1908 isl_basic_set *coef;
1909 struct isl_sched_node *node = edge->src;
1911 coef = intra_coefficients(graph, map);
1913 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
1915 total = isl_basic_set_total_dim(graph->lp);
1916 dim_map = isl_dim_map_alloc(ctx, total);
1917 isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1);
1918 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1919 isl_dim_size(dim, isl_dim_set), 1,
1921 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1922 isl_dim_size(dim, isl_dim_set), 1,
1924 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1925 coef->n_eq, coef->n_ineq);
1926 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1933 /* Add constraints to graph->lp that force the dependence of edge i
1934 * to be respected and attempt to carry it, where edge i is one from
1936 * That is, add constraints that enforce
1938 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
1940 * for each (x,y) in R.
1941 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1942 * of valid constraints for R and then plug in
1943 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
1944 * with each coefficient (except e_i, c_k_0 and c_j_0)
1945 * represented as a pair of non-negative coefficients.
1947 static int add_inter_constraints(struct isl_sched_graph *graph, int i)
1950 struct isl_sched_edge *edge= &graph->edge[i];
1951 isl_map *map = isl_map_copy(edge->map);
1952 isl_ctx *ctx = isl_map_get_ctx(map);
1954 isl_dim_map *dim_map;
1955 isl_basic_set *coef;
1956 struct isl_sched_node *src = edge->src;
1957 struct isl_sched_node *dst = edge->dst;
1959 coef = inter_coefficients(graph, map);
1961 dim = isl_dim_domain(isl_dim_unwrap(isl_basic_set_get_dim(coef)));
1963 total = isl_basic_set_total_dim(graph->lp);
1964 dim_map = isl_dim_map_alloc(ctx, total);
1966 isl_dim_map_range(dim_map, 3 + i, 0, 0, 0, 1, -1);
1968 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
1969 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
1970 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
1971 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1972 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
1974 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1975 isl_dim_size(dim, isl_dim_set) + src->nvar, 1,
1978 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
1979 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
1980 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
1981 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1982 isl_dim_size(dim, isl_dim_set), 1,
1984 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1985 isl_dim_size(dim, isl_dim_set), 1,
1988 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1989 coef->n_eq, coef->n_ineq);
1990 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1997 /* Add constraints to graph->lp that force all dependence
1998 * to be respected and attempt to carry it.
2000 static int add_all_constraints(struct isl_sched_graph *graph)
2004 for (i = 0; i < graph->n_edge; ++i) {
2005 struct isl_sched_edge *edge= &graph->edge[i];
2006 if (edge->src == edge->dst &&
2007 add_intra_constraints(graph, i) < 0)
2009 if (edge->src != edge->dst &&
2010 add_inter_constraints(graph, i) < 0)
2017 /* Construct an LP problem for finding schedule coefficients
2018 * such that the schedule carries as many dependences as possible.
2019 * In particular, for each dependence i, we bound the dependence distance
2020 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2021 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2022 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2024 * All variables of the LP are non-negative. The actual coefficients
2025 * may be negative, so each coefficient is represented as the difference
2026 * of two non-negative variables. The negative part always appears
2027 * immediately before the positive part.
2028 * Other than that, the variables have the following order
2030 * - sum of (1 - e_i) over all edges
2031 * - sum of positive and negative parts of all c_n coefficients
2032 * (unconstrained when computing non-parametric schedules)
2033 * - sum of positive and negative parts of all c_x coefficients
2038 * - positive and negative parts of c_i_n (if parametric)
2039 * - positive and negative parts of c_i_x
2041 * The constraints are those from the edges plus three equalities
2042 * to express the sums and n_edge inequalities to express e_i <= 1.
2044 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2052 total = 3 + graph->n_edge;
2053 for (i = 0; i < graph->n; ++i) {
2054 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2055 node->start = total;
2056 total += 1 + 2 * (node->nparam + node->nvar);
2059 if (count_constraints(graph, &n_eq, &n_ineq, 1) < 0)
2062 dim = isl_dim_set_alloc(ctx, 0, total);
2063 isl_basic_set_free(graph->lp);
2065 n_ineq += graph->n_edge;
2066 graph->lp = isl_basic_set_alloc_dim(dim, 0, n_eq, n_ineq);
2067 graph->lp = isl_basic_set_set_rational(graph->lp);
2069 k = isl_basic_set_alloc_equality(graph->lp);
2072 isl_seq_clr(graph->lp->eq[k], 1 + total);
2073 isl_int_set_si(graph->lp->eq[k][0], -graph->n_edge);
2074 isl_int_set_si(graph->lp->eq[k][1], 1);
2075 for (i = 0; i < graph->n_edge; ++i)
2076 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2078 k = isl_basic_set_alloc_equality(graph->lp);
2081 isl_seq_clr(graph->lp->eq[k], 1 + total);
2082 isl_int_set_si(graph->lp->eq[k][2], -1);
2083 for (i = 0; i < graph->n; ++i) {
2084 int pos = 1 + graph->node[i].start + 1;
2086 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2087 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2090 k = isl_basic_set_alloc_equality(graph->lp);
2093 isl_seq_clr(graph->lp->eq[k], 1 + total);
2094 isl_int_set_si(graph->lp->eq[k][3], -1);
2095 for (i = 0; i < graph->n; ++i) {
2096 struct isl_sched_node *node = &graph->node[i];
2097 int pos = 1 + node->start + 1 + 2 * node->nparam;
2099 for (j = 0; j < 2 * node->nvar; ++j)
2100 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2103 for (i = 0; i < graph->n_edge; ++i) {
2104 k = isl_basic_set_alloc_inequality(graph->lp);
2107 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2108 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2109 isl_int_set_si(graph->lp->ineq[k][0], 1);
2112 if (add_all_constraints(graph) < 0)
2118 /* Construct a schedule row for each node such that as many dependences
2119 * as possible are carried and then continue with the next band.
2121 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2126 if (setup_carry_lp(ctx, graph) < 0)
2129 lp = isl_basic_set_copy(graph->lp);
2130 sol = isl_tab_basic_set_non_neg_lexmin(lp);
2134 if (sol->size == 0) {
2136 isl_die(ctx, isl_error_internal,
2137 "error in schedule construction", return -1);
2140 if (isl_int_cmp_si(sol->el[1], graph->n_edge) >= 0) {
2142 isl_die(ctx, isl_error_unknown,
2143 "unable to carry dependences", return -1);
2146 if (update_schedule(graph, sol, 0, 0) < 0)
2149 return compute_next_band(ctx, graph);
2152 /* Compute a schedule for a connected dependence graph.
2153 * We try to find a sequence of as many schedule rows as possible that result
2154 * in non-negative dependence distances (independent of the previous rows
2155 * in the sequence, i.e., such that the sequence is tilable).
2156 * If we can't find any more rows we either
2157 * - split between SCCs and start over (assuming we found an interesting
2158 * pair of SCCs between which to split)
2159 * - continue with the next band (assuming the current band has at least
2161 * - try to carry as many dependences as possible and continue with the next
2164 * If we manage to complete the schedule, we finish off by topologically
2165 * sorting the statements based on the remaining dependences.
2167 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2169 if (detect_sccs(graph) < 0)
2173 if (compute_maxvar(graph) < 0)
2176 while (graph->n_row < graph->maxvar) {
2179 graph->src_scc = -1;
2180 graph->dst_scc = -1;
2182 if (setup_lp(ctx, graph) < 0)
2184 sol = solve_lp(graph);
2187 if (sol->size == 0) {
2189 if (graph->src_scc >= 0)
2190 return compute_split_schedule(ctx, graph);
2191 if (graph->n_total_row > graph->band_start)
2192 return compute_next_band(ctx, graph);
2193 return carry_dependences(ctx, graph);
2195 if (update_schedule(graph, sol, 1, 1) < 0)
2199 if (graph->n_total_row > graph->band_start)
2201 return sort_statements(ctx, graph);
2204 /* Compute a schedule for each component (identified by node->scc)
2205 * of the dependence graph separately and then combine the results.
2207 * The band_id is adjusted such that each component has a separate id.
2208 * Note that the band_id may have already been set to a value different
2209 * from zero by compute_split_schedule.
2211 static int compute_component_schedule(isl_ctx *ctx,
2212 struct isl_sched_graph *graph)
2216 int n_total_row, orig_total_row;
2217 int n_band, orig_band;
2220 orig_total_row = graph->n_total_row;
2222 orig_band = graph->n_band;
2223 for (i = 0; i < graph->n; ++i)
2224 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2225 for (wcc = 0; wcc < graph->scc; ++wcc) {
2227 for (i = 0; i < graph->n; ++i)
2228 if (graph->node[i].scc == wcc)
2231 for (i = 0; i < graph->n_edge; ++i)
2232 if (graph->edge[i].src->scc == wcc)
2235 if (compute_sub_schedule(ctx, graph, n, n_edge,
2237 &edge_src_scc_exactly, wcc, 1) < 0)
2239 if (graph->n_total_row > n_total_row)
2240 n_total_row = graph->n_total_row;
2241 graph->n_total_row = orig_total_row;
2242 if (graph->n_band > n_band)
2243 n_band = graph->n_band;
2244 graph->n_band = orig_band;
2247 graph->n_total_row = n_total_row;
2248 graph->n_band = n_band;
2250 return pad_schedule(graph);
2253 /* Compute a schedule for the given dependence graph.
2254 * We first check if the graph is connected (through validity dependences)
2255 * and if so compute a schedule for each component separately.
2257 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2259 if (detect_wccs(graph) < 0)
2263 return compute_component_schedule(ctx, graph);
2265 return compute_schedule_wcc(ctx, graph);
2268 /* Compute a schedule for the given union of domains that respects
2269 * all the validity dependences and tries to minimize the dependence
2270 * distances over the proximity dependences.
2272 __isl_give isl_schedule *isl_union_set_compute_schedule(
2273 __isl_take isl_union_set *domain,
2274 __isl_take isl_union_map *validity,
2275 __isl_take isl_union_map *proximity)
2277 isl_ctx *ctx = isl_union_set_get_ctx(domain);
2279 struct isl_sched_graph graph = { 0 };
2280 isl_schedule *sched;
2282 domain = isl_union_set_align_params(domain,
2283 isl_union_map_get_dim(validity));
2284 domain = isl_union_set_align_params(domain,
2285 isl_union_map_get_dim(proximity));
2286 dim = isl_union_set_get_dim(domain);
2287 validity = isl_union_map_align_params(validity, isl_dim_copy(dim));
2288 proximity = isl_union_map_align_params(proximity, dim);
2293 graph.n = isl_union_set_n_set(domain);
2296 if (graph_alloc(ctx, &graph, graph.n,
2297 isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2301 if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2303 if (graph_init_table(ctx, &graph) < 0)
2306 if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0)
2308 if (graph_init_edge_table(ctx, &graph) < 0)
2310 if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0)
2313 if (compute_schedule(ctx, &graph) < 0)
2317 sched = extract_schedule(&graph, isl_union_set_get_dim(domain));
2319 graph_free(ctx, &graph);
2320 isl_union_set_free(domain);
2321 isl_union_map_free(validity);
2322 isl_union_map_free(proximity);
2326 graph_free(ctx, &graph);
2327 isl_union_set_free(domain);
2328 isl_union_map_free(validity);
2329 isl_union_map_free(proximity);
2333 void *isl_schedule_free(__isl_take isl_schedule *sched)
2339 if (--sched->ref > 0)
2342 for (i = 0; i < sched->n; ++i) {
2343 isl_map_free(sched->node[i].sched);
2344 free(sched->node[i].band_end);
2345 free(sched->node[i].band_id);
2346 free(sched->node[i].parallel);
2348 isl_dim_free(sched->dim);
2349 isl_band_list_free(sched->band_forest);
2354 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2356 return schedule ? isl_dim_get_ctx(schedule->dim) : NULL;
2359 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2362 isl_union_map *umap;
2367 umap = isl_union_map_empty(isl_dim_copy(sched->dim));
2368 for (i = 0; i < sched->n; ++i)
2369 umap = isl_union_map_add_map(umap,
2370 isl_map_copy(sched->node[i].sched));
2375 int isl_schedule_n_band(__isl_keep isl_schedule *sched)
2377 return sched ? sched->n_band : 0;
2380 /* Construct a mapping that maps each domain to the band in its schedule
2381 * with the specified band index. Note that bands with the same index
2382 * but for different domains do not need to be related.
2384 __isl_give isl_union_map *isl_schedule_get_band(__isl_keep isl_schedule *sched,
2388 isl_union_map *umap;
2393 umap = isl_union_map_empty(isl_dim_copy(sched->dim));
2394 for (i = 0; i < sched->n; ++i) {
2398 if (band >= sched->node[i].n_band)
2401 start = band > 0 ? sched->node[i].band_end[band - 1] : 0;
2402 end = sched->node[i].band_end[band];
2404 map = isl_map_copy(sched->node[i].sched);
2406 map = isl_map_project_out(map, isl_dim_out, end,
2407 sched->n_total_row - end);
2408 map = isl_map_project_out(map, isl_dim_out, 0, start);
2410 umap = isl_union_map_add_map(umap, map);
2416 static __isl_give isl_band_list *construct_band_list(
2417 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2418 int band_nr, int *parent_active, int n_active);
2420 /* Construct an isl_band structure for the band in the given schedule
2421 * with sequence number band_nr for the n_active nodes marked by active.
2422 * If the nodes don't have a band with the given sequence number,
2423 * then a band without members is created.
2425 * Because of the way the schedule is constructed, we know that
2426 * the position of the band inside the schedule of a node is the same
2427 * for all active nodes.
2429 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2430 __isl_keep isl_band *parent,
2431 int band_nr, int *active, int n_active)
2434 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2436 unsigned start, end;
2438 band = isl_calloc_type(ctx, isl_band);
2443 band->schedule = schedule;
2444 band->parent = parent;
2446 for (i = 0; i < schedule->n; ++i)
2447 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2450 if (i < schedule->n) {
2451 band->children = construct_band_list(schedule, band,
2452 band_nr + 1, active, n_active);
2453 if (!band->children)
2457 for (i = 0; i < schedule->n; ++i)
2461 if (i >= schedule->n)
2462 isl_die(ctx, isl_error_internal,
2463 "band without active statements", goto error);
2465 start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2466 end = band_nr < schedule->node[i].n_band ?
2467 schedule->node[i].band_end[band_nr] : start;
2468 band->n = end - start;
2470 band->parallel = isl_alloc_array(ctx, int, band->n);
2471 if (!band->parallel)
2474 for (j = 0; j < band->n; ++j)
2475 band->parallel[j] = schedule->node[i].parallel[start + j];
2477 band->map = isl_union_map_empty(isl_dim_copy(schedule->dim));
2478 for (i = 0; i < schedule->n; ++i) {
2485 map = isl_map_copy(schedule->node[i].sched);
2486 n_out = isl_map_dim(map, isl_dim_out);
2487 map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
2488 map = isl_map_project_out(map, isl_dim_out, 0, start);
2489 band->map = isl_union_map_union(band->map,
2490 isl_union_map_from_map(map));
2497 isl_band_free(band);
2501 /* Construct a list of bands that start at the same position (with
2502 * sequence number band_nr) in the schedules of the nodes that
2503 * were active in the parent band.
2505 * A separate isl_band structure is created for each band_id
2506 * and for each node that does not have a band with sequence
2507 * number band_nr. In the latter case, a band without members
2509 * This ensures that if a band has any children, then each node
2510 * that was active in the band is active in exactly one of the children.
2512 static __isl_give isl_band_list *construct_band_list(
2513 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2514 int band_nr, int *parent_active, int n_active)
2517 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2520 isl_band_list *list;
2523 for (i = 0; i < n_active; ++i) {
2524 for (j = 0; j < schedule->n; ++j) {
2525 if (!parent_active[j])
2527 if (schedule->node[j].n_band <= band_nr)
2529 if (schedule->node[j].band_id[band_nr] == i) {
2535 for (j = 0; j < schedule->n; ++j)
2536 if (schedule->node[j].n_band <= band_nr)
2541 list = isl_band_list_alloc(ctx, n_band);
2542 band = construct_band(schedule, parent, band_nr,
2543 parent_active, n_active);
2544 return isl_band_list_add(list, band);
2547 active = isl_alloc_array(ctx, int, schedule->n);
2551 list = isl_band_list_alloc(ctx, n_band);
2553 for (i = 0; i < n_active; ++i) {
2557 for (j = 0; j < schedule->n; ++j) {
2558 active[j] = parent_active[j] &&
2559 schedule->node[j].n_band > band_nr &&
2560 schedule->node[j].band_id[band_nr] == i;
2567 band = construct_band(schedule, parent, band_nr, active, n);
2569 list = isl_band_list_add(list, band);
2571 for (i = 0; i < schedule->n; ++i) {
2573 if (!parent_active[i])
2575 if (schedule->node[i].n_band > band_nr)
2577 for (j = 0; j < schedule->n; ++j)
2579 band = construct_band(schedule, parent, band_nr, active, 1);
2580 list = isl_band_list_add(list, band);
2588 /* Construct a band forest representation of the schedule and
2589 * return the list of roots.
2591 static __isl_give isl_band_list *construct_forest(
2592 __isl_keep isl_schedule *schedule)
2595 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2596 isl_band_list *forest;
2599 active = isl_alloc_array(ctx, int, schedule->n);
2603 for (i = 0; i < schedule->n; ++i)
2606 forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
2613 /* Return the roots of a band forest representation of the schedule.
2615 __isl_give isl_band_list *isl_schedule_get_band_forest(
2616 __isl_keep isl_schedule *schedule)
2620 if (!schedule->band_forest)
2621 schedule->band_forest = construct_forest(schedule);
2622 return isl_band_list_copy(schedule->band_forest);