add isl_map_order_lt
[isl.git] / isl_schedule.c
blob358467cacb619a8a89c68287353cb37b7693779a
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 * max_row is the allocated number of rows in the schedule
146 * n_row is the current (maximal) number of linearly independent
147 * rows in the node schedules
148 * n_total_row is the current number of rows in the node schedules
149 * n_band is the current number of completed bands
150 * band_start is the starting row in the node schedules of the current band
151 * root is set if this graph is the original dependence graph,
152 * without any splitting
154 * sorted contains a list of node indices sorted according to the
155 * SCC to which a node belongs
157 * n_edge is the number of edges
158 * edge is the list of edges
159 * max_edge contains the maximal number of edges of each type;
160 * in particular, it contains the number of edges in the inital graph.
161 * edge_table contains pointers into the edge array, hashed on the source
162 * and sink spaces; there is one such table for each type;
163 * a given edge may be referenced from more than one table
164 * if the corresponding relation appears in more than of the
165 * sets of dependences
167 * node_table contains pointers into the node array, hashed on the space
169 * region contains a list of variable sequences that should be non-trivial
171 * lp contains the (I)LP problem used to obtain new schedule rows
173 * src_scc and dst_scc are the source and sink SCCs of an edge with
174 * conflicting constraints
176 * scc, sp, index and stack are used during the detection of SCCs
177 * scc is the number of the next SCC
178 * stack contains the nodes on the path from the root to the current node
179 * sp is the stack pointer
180 * index is the index of the last node visited
182 struct isl_sched_graph {
183 isl_hmap_map_basic_set *intra_hmap;
184 isl_hmap_map_basic_set *inter_hmap;
186 struct isl_sched_node *node;
187 int n;
188 int maxvar;
189 int max_row;
190 int n_row;
192 int *sorted;
194 int n_band;
195 int n_total_row;
196 int band_start;
198 int root;
200 struct isl_sched_edge *edge;
201 int n_edge;
202 int max_edge[isl_edge_last + 1];
203 struct isl_hash_table *edge_table[isl_edge_last + 1];
205 struct isl_hash_table *node_table;
206 struct isl_region *region;
208 isl_basic_set *lp;
210 int src_scc;
211 int dst_scc;
213 /* scc detection */
214 int scc;
215 int sp;
216 int index;
217 int *stack;
220 /* Initialize node_table based on the list of nodes.
222 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
224 int i;
226 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
227 if (!graph->node_table)
228 return -1;
230 for (i = 0; i < graph->n; ++i) {
231 struct isl_hash_table_entry *entry;
232 uint32_t hash;
234 hash = isl_space_get_hash(graph->node[i].dim);
235 entry = isl_hash_table_find(ctx, graph->node_table, hash,
236 &node_has_dim,
237 graph->node[i].dim, 1);
238 if (!entry)
239 return -1;
240 entry->data = &graph->node[i];
243 return 0;
246 /* Return a pointer to the node that lives within the given space,
247 * or NULL if there is no such node.
249 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
250 struct isl_sched_graph *graph, __isl_keep isl_space *dim)
252 struct isl_hash_table_entry *entry;
253 uint32_t hash;
255 hash = isl_space_get_hash(dim);
256 entry = isl_hash_table_find(ctx, graph->node_table, hash,
257 &node_has_dim, dim, 0);
259 return entry ? entry->data : NULL;
262 static int edge_has_src_and_dst(const void *entry, const void *val)
264 const struct isl_sched_edge *edge = entry;
265 const struct isl_sched_edge *temp = val;
267 return edge->src == temp->src && edge->dst == temp->dst;
270 /* Add the given edge to graph->edge_table[type].
272 static int graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph,
273 enum isl_edge_type type, struct isl_sched_edge *edge)
275 struct isl_hash_table_entry *entry;
276 uint32_t hash;
278 hash = isl_hash_init();
279 hash = isl_hash_builtin(hash, edge->src);
280 hash = isl_hash_builtin(hash, edge->dst);
281 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
282 &edge_has_src_and_dst, edge, 1);
283 if (!entry)
284 return -1;
285 entry->data = edge;
287 return 0;
290 /* Allocate the edge_tables based on the maximal number of edges of
291 * each type.
293 static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
295 int i;
297 for (i = 0; i <= isl_edge_last; ++i) {
298 graph->edge_table[i] = isl_hash_table_alloc(ctx,
299 graph->max_edge[i]);
300 if (!graph->edge_table[i])
301 return -1;
304 return 0;
307 /* If graph->edge_table[type] contains an edge from the given source
308 * to the given destination, then return the hash table entry of this edge.
309 * Otherwise, return NULL.
311 static struct isl_hash_table_entry *graph_find_edge_entry(
312 struct isl_sched_graph *graph,
313 enum isl_edge_type type,
314 struct isl_sched_node *src, struct isl_sched_node *dst)
316 isl_ctx *ctx = isl_space_get_ctx(src->dim);
317 uint32_t hash;
318 struct isl_sched_edge temp = { .src = src, .dst = dst };
320 hash = isl_hash_init();
321 hash = isl_hash_builtin(hash, temp.src);
322 hash = isl_hash_builtin(hash, temp.dst);
323 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
324 &edge_has_src_and_dst, &temp, 0);
328 /* If graph->edge_table[type] contains an edge from the given source
329 * to the given destination, then return this edge.
330 * Otherwise, return NULL.
332 static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
333 enum isl_edge_type type,
334 struct isl_sched_node *src, struct isl_sched_node *dst)
336 struct isl_hash_table_entry *entry;
338 entry = graph_find_edge_entry(graph, type, src, dst);
339 if (!entry)
340 return NULL;
342 return entry->data;
345 /* Check whether the dependence graph has an edge of the give type
346 * between the given two nodes.
348 static int graph_has_edge(struct isl_sched_graph *graph,
349 enum isl_edge_type type,
350 struct isl_sched_node *src, struct isl_sched_node *dst)
352 struct isl_sched_edge *edge;
353 int empty;
355 edge = graph_find_edge(graph, type, src, dst);
356 if (!edge)
357 return 0;
359 empty = isl_map_plain_is_empty(edge->map);
360 if (empty < 0)
361 return -1;
363 return !empty;
366 /* If there is an edge from the given source to the given destination
367 * of any type then return this edge.
368 * Otherwise, return NULL.
370 static struct isl_sched_edge *graph_find_any_edge(struct isl_sched_graph *graph,
371 struct isl_sched_node *src, struct isl_sched_node *dst)
373 int i;
374 struct isl_sched_edge *edge;
376 for (i = 0; i <= isl_edge_last; ++i) {
377 edge = graph_find_edge(graph, i, src, dst);
378 if (edge)
379 return edge;
382 return NULL;
385 /* Remove the given edge from all the edge_tables that refer to it.
387 static void graph_remove_edge(struct isl_sched_graph *graph,
388 struct isl_sched_edge *edge)
390 isl_ctx *ctx = isl_map_get_ctx(edge->map);
391 int i;
393 for (i = 0; i <= isl_edge_last; ++i) {
394 struct isl_hash_table_entry *entry;
396 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
397 if (!entry)
398 continue;
399 if (entry->data != edge)
400 continue;
401 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
405 /* Check whether the dependence graph has any edge
406 * between the given two nodes.
408 static int graph_has_any_edge(struct isl_sched_graph *graph,
409 struct isl_sched_node *src, struct isl_sched_node *dst)
411 int i;
412 int r;
414 for (i = 0; i <= isl_edge_last; ++i) {
415 r = graph_has_edge(graph, i, src, dst);
416 if (r < 0 || r)
417 return r;
420 return r;
423 /* Check whether the dependence graph has a validity edge
424 * between the given two nodes.
426 static int graph_has_validity_edge(struct isl_sched_graph *graph,
427 struct isl_sched_node *src, struct isl_sched_node *dst)
429 return graph_has_edge(graph, isl_edge_validity, src, dst);
432 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
433 int n_node, int n_edge)
435 int i;
437 graph->n = n_node;
438 graph->n_edge = n_edge;
439 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
440 graph->sorted = isl_calloc_array(ctx, int, graph->n);
441 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
442 graph->stack = isl_alloc_array(ctx, int, graph->n);
443 graph->edge = isl_calloc_array(ctx,
444 struct isl_sched_edge, graph->n_edge);
446 graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
447 graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
449 if (!graph->node || !graph->region || !graph->stack || !graph->edge ||
450 !graph->sorted)
451 return -1;
453 for(i = 0; i < graph->n; ++i)
454 graph->sorted[i] = i;
456 return 0;
459 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
461 int i;
463 isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
464 isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
466 for (i = 0; i < graph->n; ++i) {
467 isl_space_free(graph->node[i].dim);
468 isl_mat_free(graph->node[i].sched);
469 isl_map_free(graph->node[i].sched_map);
470 isl_mat_free(graph->node[i].cmap);
471 if (graph->root) {
472 free(graph->node[i].band);
473 free(graph->node[i].band_id);
474 free(graph->node[i].zero);
477 free(graph->node);
478 free(graph->sorted);
479 for (i = 0; i < graph->n_edge; ++i)
480 isl_map_free(graph->edge[i].map);
481 free(graph->edge);
482 free(graph->region);
483 free(graph->stack);
484 for (i = 0; i <= isl_edge_last; ++i)
485 isl_hash_table_free(ctx, graph->edge_table[i]);
486 isl_hash_table_free(ctx, graph->node_table);
487 isl_basic_set_free(graph->lp);
490 /* For each "set" on which this function is called, increment
491 * graph->n by one and update graph->maxvar.
493 static int init_n_maxvar(__isl_take isl_set *set, void *user)
495 struct isl_sched_graph *graph = user;
496 int nvar = isl_set_dim(set, isl_dim_set);
498 graph->n++;
499 if (nvar > graph->maxvar)
500 graph->maxvar = nvar;
502 isl_set_free(set);
504 return 0;
507 /* Compute the number of rows that should be allocated for the schedule.
508 * The graph can be split at most "n - 1" times, there can be at most
509 * two rows for each dimension in the iteration domains (in particular,
510 * we usually have one row, but it may be split by split_scaled),
511 * and there can be one extra row for ordering the statements.
512 * Note that if we have actually split "n - 1" times, then no ordering
513 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
515 static int compute_max_row(struct isl_sched_graph *graph,
516 __isl_keep isl_union_set *domain)
518 graph->n = 0;
519 graph->maxvar = 0;
520 if (isl_union_set_foreach_set(domain, &init_n_maxvar, graph) < 0)
521 return -1;
522 graph->max_row = graph->n + 2 * graph->maxvar;
524 return 0;
527 /* Add a new node to the graph representing the given set.
529 static int extract_node(__isl_take isl_set *set, void *user)
531 int nvar, nparam;
532 isl_ctx *ctx;
533 isl_space *dim;
534 isl_mat *sched;
535 struct isl_sched_graph *graph = user;
536 int *band, *band_id, *zero;
538 ctx = isl_set_get_ctx(set);
539 dim = isl_set_get_space(set);
540 isl_set_free(set);
541 nvar = isl_space_dim(dim, isl_dim_set);
542 nparam = isl_space_dim(dim, isl_dim_param);
543 if (!ctx->opt->schedule_parametric)
544 nparam = 0;
545 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
546 graph->node[graph->n].dim = dim;
547 graph->node[graph->n].nvar = nvar;
548 graph->node[graph->n].nparam = nparam;
549 graph->node[graph->n].sched = sched;
550 graph->node[graph->n].sched_map = NULL;
551 band = isl_alloc_array(ctx, int, graph->max_row);
552 graph->node[graph->n].band = band;
553 band_id = isl_calloc_array(ctx, int, graph->max_row);
554 graph->node[graph->n].band_id = band_id;
555 zero = isl_calloc_array(ctx, int, graph->max_row);
556 graph->node[graph->n].zero = zero;
557 graph->n++;
559 if (!sched || !band || !band_id || !zero)
560 return -1;
562 return 0;
565 struct isl_extract_edge_data {
566 enum isl_edge_type type;
567 struct isl_sched_graph *graph;
570 /* Add a new edge to the graph based on the given map
571 * and add it to data->graph->edge_table[data->type].
572 * If a dependence relation of a given type happens to be identical
573 * to one of the dependence relations of a type that was added before,
574 * then we don't create a new edge, but instead mark the original edge
575 * as also representing a dependence of the current type.
577 static int extract_edge(__isl_take isl_map *map, void *user)
579 isl_ctx *ctx = isl_map_get_ctx(map);
580 struct isl_extract_edge_data *data = user;
581 struct isl_sched_graph *graph = data->graph;
582 struct isl_sched_node *src, *dst;
583 isl_space *dim;
584 struct isl_sched_edge *edge;
585 int is_equal;
587 dim = isl_space_domain(isl_map_get_space(map));
588 src = graph_find_node(ctx, graph, dim);
589 isl_space_free(dim);
590 dim = isl_space_range(isl_map_get_space(map));
591 dst = graph_find_node(ctx, graph, dim);
592 isl_space_free(dim);
594 if (!src || !dst) {
595 isl_map_free(map);
596 return 0;
599 graph->edge[graph->n_edge].src = src;
600 graph->edge[graph->n_edge].dst = dst;
601 graph->edge[graph->n_edge].map = map;
602 if (data->type == isl_edge_validity) {
603 graph->edge[graph->n_edge].validity = 1;
604 graph->edge[graph->n_edge].proximity = 0;
606 if (data->type == isl_edge_proximity) {
607 graph->edge[graph->n_edge].validity = 0;
608 graph->edge[graph->n_edge].proximity = 1;
610 graph->n_edge++;
612 edge = graph_find_any_edge(graph, src, dst);
613 if (!edge)
614 return graph_edge_table_add(ctx, graph, data->type,
615 &graph->edge[graph->n_edge - 1]);
616 is_equal = isl_map_plain_is_equal(map, edge->map);
617 if (is_equal < 0)
618 return -1;
619 if (!is_equal)
620 return graph_edge_table_add(ctx, graph, data->type,
621 &graph->edge[graph->n_edge - 1]);
623 graph->n_edge--;
624 edge->validity |= graph->edge[graph->n_edge].validity;
625 edge->proximity |= graph->edge[graph->n_edge].proximity;
626 isl_map_free(map);
628 return graph_edge_table_add(ctx, graph, data->type, edge);
631 /* Check whether there is a validity dependence from src to dst,
632 * forcing dst to follow src (if weak is not set).
633 * If weak is set, then check if there is any dependence from src to dst.
635 static int node_follows(struct isl_sched_graph *graph,
636 struct isl_sched_node *dst, struct isl_sched_node *src, int weak)
638 if (weak)
639 return graph_has_any_edge(graph, src, dst);
640 else
641 return graph_has_validity_edge(graph, src, dst);
644 /* Perform Tarjan's algorithm for computing the strongly connected components
645 * in the dependence graph (only validity edges).
646 * If weak is set, we consider the graph to be undirected and
647 * we effectively compute the (weakly) connected components.
648 * Additionally, we also consider other edges when weak is set.
650 static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int weak)
652 int j;
654 g->node[i].index = g->index;
655 g->node[i].min_index = g->index;
656 g->node[i].on_stack = 1;
657 g->index++;
658 g->stack[g->sp++] = i;
660 for (j = g->n - 1; j >= 0; --j) {
661 int f;
663 if (j == i)
664 continue;
665 if (g->node[j].index >= 0 &&
666 (!g->node[j].on_stack ||
667 g->node[j].index > g->node[i].min_index))
668 continue;
670 f = node_follows(g, &g->node[i], &g->node[j], weak);
671 if (f < 0)
672 return -1;
673 if (!f && weak) {
674 f = node_follows(g, &g->node[j], &g->node[i], weak);
675 if (f < 0)
676 return -1;
678 if (!f)
679 continue;
680 if (g->node[j].index < 0) {
681 detect_sccs_tarjan(g, j, weak);
682 if (g->node[j].min_index < g->node[i].min_index)
683 g->node[i].min_index = g->node[j].min_index;
684 } else if (g->node[j].index < g->node[i].min_index)
685 g->node[i].min_index = g->node[j].index;
688 if (g->node[i].index != g->node[i].min_index)
689 return 0;
691 do {
692 j = g->stack[--g->sp];
693 g->node[j].on_stack = 0;
694 g->node[j].scc = g->scc;
695 } while (j != i);
696 g->scc++;
698 return 0;
701 static int detect_ccs(struct isl_sched_graph *graph, int weak)
703 int i;
705 graph->index = 0;
706 graph->sp = 0;
707 graph->scc = 0;
708 for (i = graph->n - 1; i >= 0; --i)
709 graph->node[i].index = -1;
711 for (i = graph->n - 1; i >= 0; --i) {
712 if (graph->node[i].index >= 0)
713 continue;
714 if (detect_sccs_tarjan(graph, i, weak) < 0)
715 return -1;
718 return 0;
721 /* Apply Tarjan's algorithm to detect the strongly connected components
722 * in the dependence graph.
724 static int detect_sccs(struct isl_sched_graph *graph)
726 return detect_ccs(graph, 0);
729 /* Apply Tarjan's algorithm to detect the (weakly) connected components
730 * in the dependence graph.
732 static int detect_wccs(struct isl_sched_graph *graph)
734 return detect_ccs(graph, 1);
737 static int cmp_scc(const void *a, const void *b, void *data)
739 struct isl_sched_graph *graph = data;
740 const int *i1 = a;
741 const int *i2 = b;
743 return graph->node[*i1].scc - graph->node[*i2].scc;
746 /* Sort the elements of graph->sorted according to the corresponding SCCs.
748 static void sort_sccs(struct isl_sched_graph *graph)
750 isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
753 /* Given a dependence relation R from a node to itself,
754 * construct the set of coefficients of valid constraints for elements
755 * in that dependence relation.
756 * In particular, the result contains tuples of coefficients
757 * c_0, c_n, c_x such that
759 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
761 * or, equivalently,
763 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
765 * We choose here to compute the dual of delta R.
766 * Alternatively, we could have computed the dual of R, resulting
767 * in a set of tuples c_0, c_n, c_x, c_y, and then
768 * plugged in (c_0, c_n, c_x, -c_x).
770 static __isl_give isl_basic_set *intra_coefficients(
771 struct isl_sched_graph *graph, __isl_take isl_map *map)
773 isl_ctx *ctx = isl_map_get_ctx(map);
774 isl_set *delta;
775 isl_basic_set *coef;
777 if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
778 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
780 delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
781 coef = isl_set_coefficients(delta);
782 isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
783 isl_basic_set_copy(coef));
785 return coef;
788 /* Given a dependence relation R, * construct the set of coefficients
789 * of valid constraints for elements in that dependence relation.
790 * In particular, the result contains tuples of coefficients
791 * c_0, c_n, c_x, c_y such that
793 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
796 static __isl_give isl_basic_set *inter_coefficients(
797 struct isl_sched_graph *graph, __isl_take isl_map *map)
799 isl_ctx *ctx = isl_map_get_ctx(map);
800 isl_set *set;
801 isl_basic_set *coef;
803 if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
804 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
806 set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
807 coef = isl_set_coefficients(set);
808 isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
809 isl_basic_set_copy(coef));
811 return coef;
814 /* Add constraints to graph->lp that force validity for the given
815 * dependence from a node i to itself.
816 * That is, add constraints that enforce
818 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
819 * = c_i_x (y - x) >= 0
821 * for each (x,y) in R.
822 * We obtain general constraints on coefficients (c_0, c_n, c_x)
823 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
824 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
825 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
827 * Actually, we do not construct constraints for the c_i_x themselves,
828 * but for the coefficients of c_i_x written as a linear combination
829 * of the columns in node->cmap.
831 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
832 struct isl_sched_edge *edge)
834 unsigned total;
835 isl_map *map = isl_map_copy(edge->map);
836 isl_ctx *ctx = isl_map_get_ctx(map);
837 isl_space *dim;
838 isl_dim_map *dim_map;
839 isl_basic_set *coef;
840 struct isl_sched_node *node = edge->src;
842 coef = intra_coefficients(graph, map);
844 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
846 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
847 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
849 total = isl_basic_set_total_dim(graph->lp);
850 dim_map = isl_dim_map_alloc(ctx, total);
851 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
852 isl_space_dim(dim, isl_dim_set), 1,
853 node->nvar, -1);
854 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
855 isl_space_dim(dim, isl_dim_set), 1,
856 node->nvar, 1);
857 graph->lp = isl_basic_set_extend_constraints(graph->lp,
858 coef->n_eq, coef->n_ineq);
859 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
860 coef, dim_map);
861 isl_space_free(dim);
863 return 0;
866 /* Add constraints to graph->lp that force validity for the given
867 * dependence from node i to node j.
868 * That is, add constraints that enforce
870 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
872 * for each (x,y) in R.
873 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
874 * of valid constraints for R and then plug in
875 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
876 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
877 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
878 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
880 * Actually, we do not construct constraints for the c_*_x themselves,
881 * but for the coefficients of c_*_x written as a linear combination
882 * of the columns in node->cmap.
884 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
885 struct isl_sched_edge *edge)
887 unsigned total;
888 isl_map *map = isl_map_copy(edge->map);
889 isl_ctx *ctx = isl_map_get_ctx(map);
890 isl_space *dim;
891 isl_dim_map *dim_map;
892 isl_basic_set *coef;
893 struct isl_sched_node *src = edge->src;
894 struct isl_sched_node *dst = edge->dst;
896 coef = inter_coefficients(graph, map);
898 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
900 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
901 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
902 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
903 isl_space_dim(dim, isl_dim_set) + src->nvar,
904 isl_mat_copy(dst->cmap));
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, dst->start, 0, 0, 0, 1, 1);
910 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
911 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
912 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
913 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
914 dst->nvar, -1);
915 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
916 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
917 dst->nvar, 1);
919 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
920 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
921 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
922 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
923 isl_space_dim(dim, isl_dim_set), 1,
924 src->nvar, 1);
925 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
926 isl_space_dim(dim, isl_dim_set), 1,
927 src->nvar, -1);
929 edge->start = graph->lp->n_ineq;
930 graph->lp = isl_basic_set_extend_constraints(graph->lp,
931 coef->n_eq, coef->n_ineq);
932 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
933 coef, dim_map);
934 isl_space_free(dim);
935 edge->end = graph->lp->n_ineq;
937 return 0;
940 /* Add constraints to graph->lp that bound the dependence distance for the given
941 * dependence from a node i to itself.
942 * If s = 1, we add the constraint
944 * c_i_x (y - x) <= m_0 + m_n n
946 * or
948 * -c_i_x (y - x) + m_0 + m_n n >= 0
950 * for each (x,y) in R.
951 * If s = -1, we add the constraint
953 * -c_i_x (y - x) <= m_0 + m_n n
955 * or
957 * c_i_x (y - x) + m_0 + m_n n >= 0
959 * for each (x,y) in R.
960 * We obtain general constraints on coefficients (c_0, c_n, c_x)
961 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
962 * with each coefficient (except m_0) represented as a pair of non-negative
963 * coefficients.
965 * Actually, we do not construct constraints for the c_i_x themselves,
966 * but for the coefficients of c_i_x written as a linear combination
967 * of the columns in node->cmap.
969 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
970 struct isl_sched_edge *edge, int s)
972 unsigned total;
973 unsigned nparam;
974 isl_map *map = isl_map_copy(edge->map);
975 isl_ctx *ctx = isl_map_get_ctx(map);
976 isl_space *dim;
977 isl_dim_map *dim_map;
978 isl_basic_set *coef;
979 struct isl_sched_node *node = edge->src;
981 coef = intra_coefficients(graph, map);
983 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
985 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
986 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
988 nparam = isl_space_dim(node->dim, isl_dim_param);
989 total = isl_basic_set_total_dim(graph->lp);
990 dim_map = isl_dim_map_alloc(ctx, total);
991 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
992 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
993 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
994 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
995 isl_space_dim(dim, isl_dim_set), 1,
996 node->nvar, s);
997 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
998 isl_space_dim(dim, isl_dim_set), 1,
999 node->nvar, -s);
1000 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1001 coef->n_eq, coef->n_ineq);
1002 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1003 coef, dim_map);
1004 isl_space_free(dim);
1006 return 0;
1009 /* Add constraints to graph->lp that bound the dependence distance for the given
1010 * dependence from node i to node j.
1011 * If s = 1, we add the constraint
1013 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1014 * <= m_0 + m_n n
1016 * or
1018 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1019 * m_0 + m_n n >= 0
1021 * for each (x,y) in R.
1022 * If s = -1, we add the constraint
1024 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1025 * <= m_0 + m_n n
1027 * or
1029 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1030 * m_0 + m_n n >= 0
1032 * for each (x,y) in R.
1033 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1034 * of valid constraints for R and then plug in
1035 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1036 * -s*c_j_x+s*c_i_x)
1037 * with each coefficient (except m_0, c_j_0 and c_i_0)
1038 * represented as a pair of non-negative coefficients.
1040 * Actually, we do not construct constraints for the c_*_x themselves,
1041 * but for the coefficients of c_*_x written as a linear combination
1042 * of the columns in node->cmap.
1044 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
1045 struct isl_sched_edge *edge, int s)
1047 unsigned total;
1048 unsigned nparam;
1049 isl_map *map = isl_map_copy(edge->map);
1050 isl_ctx *ctx = isl_map_get_ctx(map);
1051 isl_space *dim;
1052 isl_dim_map *dim_map;
1053 isl_basic_set *coef;
1054 struct isl_sched_node *src = edge->src;
1055 struct isl_sched_node *dst = edge->dst;
1057 coef = inter_coefficients(graph, map);
1059 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1061 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1062 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1063 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1064 isl_space_dim(dim, isl_dim_set) + src->nvar,
1065 isl_mat_copy(dst->cmap));
1067 nparam = isl_space_dim(src->dim, isl_dim_param);
1068 total = isl_basic_set_total_dim(graph->lp);
1069 dim_map = isl_dim_map_alloc(ctx, total);
1071 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1072 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1073 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1075 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
1076 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
1077 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
1078 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1079 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1080 dst->nvar, s);
1081 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1082 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1083 dst->nvar, -s);
1085 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
1086 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
1087 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
1088 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1089 isl_space_dim(dim, isl_dim_set), 1,
1090 src->nvar, -s);
1091 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1092 isl_space_dim(dim, isl_dim_set), 1,
1093 src->nvar, s);
1095 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1096 coef->n_eq, coef->n_ineq);
1097 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1098 coef, dim_map);
1099 isl_space_free(dim);
1101 return 0;
1104 static int add_all_validity_constraints(struct isl_sched_graph *graph)
1106 int i;
1108 for (i = 0; i < graph->n_edge; ++i) {
1109 struct isl_sched_edge *edge= &graph->edge[i];
1110 if (!edge->validity)
1111 continue;
1112 if (edge->src != edge->dst)
1113 continue;
1114 if (add_intra_validity_constraints(graph, edge) < 0)
1115 return -1;
1118 for (i = 0; i < graph->n_edge; ++i) {
1119 struct isl_sched_edge *edge = &graph->edge[i];
1120 if (!edge->validity)
1121 continue;
1122 if (edge->src == edge->dst)
1123 continue;
1124 if (add_inter_validity_constraints(graph, edge) < 0)
1125 return -1;
1128 return 0;
1131 /* Add constraints to graph->lp that bound the dependence distance
1132 * for all dependence relations.
1133 * If a given proximity dependence is identical to a validity
1134 * dependence, then the dependence distance is already bounded
1135 * from below (by zero), so we only need to bound the distance
1136 * from above.
1137 * Otherwise, we need to bound the distance both from above and from below.
1139 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
1141 int i;
1143 for (i = 0; i < graph->n_edge; ++i) {
1144 struct isl_sched_edge *edge= &graph->edge[i];
1145 if (!edge->proximity)
1146 continue;
1147 if (edge->src == edge->dst &&
1148 add_intra_proximity_constraints(graph, edge, 1) < 0)
1149 return -1;
1150 if (edge->src != edge->dst &&
1151 add_inter_proximity_constraints(graph, edge, 1) < 0)
1152 return -1;
1153 if (edge->validity)
1154 continue;
1155 if (edge->src == edge->dst &&
1156 add_intra_proximity_constraints(graph, edge, -1) < 0)
1157 return -1;
1158 if (edge->src != edge->dst &&
1159 add_inter_proximity_constraints(graph, edge, -1) < 0)
1160 return -1;
1163 return 0;
1166 /* Compute a basis for the rows in the linear part of the schedule
1167 * and extend this basis to a full basis. The remaining rows
1168 * can then be used to force linear independence from the rows
1169 * in the schedule.
1171 * In particular, given the schedule rows S, we compute
1173 * S = H Q
1175 * with H the Hermite normal form of S. That is, all but the
1176 * first rank columns of Q are zero and so each row in S is
1177 * a linear combination of the first rank rows of Q.
1178 * The matrix Q is then transposed because we will write the
1179 * coefficients of the next schedule row as a column vector s
1180 * and express this s as a linear combination s = Q c of the
1181 * computed basis.
1183 static int node_update_cmap(struct isl_sched_node *node)
1185 isl_mat *H, *Q;
1186 int n_row = isl_mat_rows(node->sched);
1188 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1189 1 + node->nparam, node->nvar);
1191 H = isl_mat_left_hermite(H, 0, NULL, &Q);
1192 isl_mat_free(node->cmap);
1193 node->cmap = isl_mat_transpose(Q);
1194 node->rank = isl_mat_initial_non_zero_cols(H);
1195 isl_mat_free(H);
1197 if (!node->cmap || node->rank < 0)
1198 return -1;
1199 return 0;
1202 /* Count the number of equality and inequality constraints
1203 * that will be added for the given map.
1204 * If carry is set, then we are counting the number of (validity)
1205 * constraints that will be added in setup_carry_lp and we count
1206 * each edge exactly once. Otherwise, we count as follows
1207 * validity -> 1 (>= 0)
1208 * validity+proximity -> 2 (>= 0 and upper bound)
1209 * proximity -> 2 (lower and upper bound)
1211 static int count_map_constraints(struct isl_sched_graph *graph,
1212 struct isl_sched_edge *edge, __isl_take isl_map *map,
1213 int *n_eq, int *n_ineq, int carry)
1215 isl_basic_set *coef;
1216 int f = carry ? 1 : edge->proximity ? 2 : 1;
1218 if (carry && !edge->validity) {
1219 isl_map_free(map);
1220 return 0;
1223 if (edge->src == edge->dst)
1224 coef = intra_coefficients(graph, map);
1225 else
1226 coef = inter_coefficients(graph, map);
1227 if (!coef)
1228 return -1;
1229 *n_eq += f * coef->n_eq;
1230 *n_ineq += f * coef->n_ineq;
1231 isl_basic_set_free(coef);
1233 return 0;
1236 /* Count the number of equality and inequality constraints
1237 * that will be added to the main lp problem.
1238 * We count as follows
1239 * validity -> 1 (>= 0)
1240 * validity+proximity -> 2 (>= 0 and upper bound)
1241 * proximity -> 2 (lower and upper bound)
1243 static int count_constraints(struct isl_sched_graph *graph,
1244 int *n_eq, int *n_ineq)
1246 int i;
1248 *n_eq = *n_ineq = 0;
1249 for (i = 0; i < graph->n_edge; ++i) {
1250 struct isl_sched_edge *edge= &graph->edge[i];
1251 isl_map *map = isl_map_copy(edge->map);
1253 if (count_map_constraints(graph, edge, map,
1254 n_eq, n_ineq, 0) < 0)
1255 return -1;
1258 return 0;
1261 /* Add constraints that bound the values of the variable and parameter
1262 * coefficients of the schedule.
1264 * The maximal value of the coefficients is defined by the option
1265 * 'schedule_max_coefficient'.
1267 static int add_bound_coefficient_constraints(isl_ctx *ctx,
1268 struct isl_sched_graph *graph)
1270 int i, j, k;
1271 int max_coefficient;
1272 int total;
1274 max_coefficient = ctx->opt->schedule_max_coefficient;
1276 if (max_coefficient == -1)
1277 return 0;
1279 total = isl_basic_set_total_dim(graph->lp);
1281 for (i = 0; i < graph->n; ++i) {
1282 struct isl_sched_node *node = &graph->node[i];
1283 for (j = 0; j < 2 * node->nparam + 2 * node->nvar; ++j) {
1284 int dim;
1285 k = isl_basic_set_alloc_inequality(graph->lp);
1286 if (k < 0)
1287 return -1;
1288 dim = 1 + node->start + 1 + j;
1289 isl_seq_clr(graph->lp->ineq[k], 1 + total);
1290 isl_int_set_si(graph->lp->ineq[k][dim], -1);
1291 isl_int_set_si(graph->lp->ineq[k][0], max_coefficient);
1295 return 0;
1298 /* Construct an ILP problem for finding schedule coefficients
1299 * that result in non-negative, but small dependence distances
1300 * over all dependences.
1301 * In particular, the dependence distances over proximity edges
1302 * are bounded by m_0 + m_n n and we compute schedule coefficients
1303 * with small values (preferably zero) of m_n and m_0.
1305 * All variables of the ILP are non-negative. The actual coefficients
1306 * may be negative, so each coefficient is represented as the difference
1307 * of two non-negative variables. The negative part always appears
1308 * immediately before the positive part.
1309 * Other than that, the variables have the following order
1311 * - sum of positive and negative parts of m_n coefficients
1312 * - m_0
1313 * - sum of positive and negative parts of all c_n coefficients
1314 * (unconstrained when computing non-parametric schedules)
1315 * - sum of positive and negative parts of all c_x coefficients
1316 * - positive and negative parts of m_n coefficients
1317 * - for each node
1318 * - c_i_0
1319 * - positive and negative parts of c_i_n (if parametric)
1320 * - positive and negative parts of c_i_x
1322 * The c_i_x are not represented directly, but through the columns of
1323 * node->cmap. That is, the computed values are for variable t_i_x
1324 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1326 * The constraints are those from the edges plus two or three equalities
1327 * to express the sums.
1329 * If force_zero is set, then we add equalities to ensure that
1330 * the sum of the m_n coefficients and m_0 are both zero.
1332 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
1333 int force_zero)
1335 int i, j;
1336 int k;
1337 unsigned nparam;
1338 unsigned total;
1339 isl_space *dim;
1340 int parametric;
1341 int param_pos;
1342 int n_eq, n_ineq;
1343 int max_constant_term;
1344 int max_coefficient;
1346 max_constant_term = ctx->opt->schedule_max_constant_term;
1347 max_coefficient = ctx->opt->schedule_max_coefficient;
1349 parametric = ctx->opt->schedule_parametric;
1350 nparam = isl_space_dim(graph->node[0].dim, isl_dim_param);
1351 param_pos = 4;
1352 total = param_pos + 2 * nparam;
1353 for (i = 0; i < graph->n; ++i) {
1354 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1355 if (node_update_cmap(node) < 0)
1356 return -1;
1357 node->start = total;
1358 total += 1 + 2 * (node->nparam + node->nvar);
1361 if (count_constraints(graph, &n_eq, &n_ineq) < 0)
1362 return -1;
1364 dim = isl_space_set_alloc(ctx, 0, total);
1365 isl_basic_set_free(graph->lp);
1366 n_eq += 2 + parametric + force_zero;
1367 if (max_constant_term != -1)
1368 n_ineq += graph->n;
1369 if (max_coefficient != -1)
1370 for (i = 0; i < graph->n; ++i)
1371 n_ineq += 2 * graph->node[i].nparam +
1372 2 * graph->node[i].nvar;
1374 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
1376 k = isl_basic_set_alloc_equality(graph->lp);
1377 if (k < 0)
1378 return -1;
1379 isl_seq_clr(graph->lp->eq[k], 1 + total);
1380 if (!force_zero)
1381 isl_int_set_si(graph->lp->eq[k][1], -1);
1382 for (i = 0; i < 2 * nparam; ++i)
1383 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1385 if (force_zero) {
1386 k = isl_basic_set_alloc_equality(graph->lp);
1387 if (k < 0)
1388 return -1;
1389 isl_seq_clr(graph->lp->eq[k], 1 + total);
1390 isl_int_set_si(graph->lp->eq[k][2], -1);
1393 if (parametric) {
1394 k = isl_basic_set_alloc_equality(graph->lp);
1395 if (k < 0)
1396 return -1;
1397 isl_seq_clr(graph->lp->eq[k], 1 + total);
1398 isl_int_set_si(graph->lp->eq[k][3], -1);
1399 for (i = 0; i < graph->n; ++i) {
1400 int pos = 1 + graph->node[i].start + 1;
1402 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1403 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1407 k = isl_basic_set_alloc_equality(graph->lp);
1408 if (k < 0)
1409 return -1;
1410 isl_seq_clr(graph->lp->eq[k], 1 + total);
1411 isl_int_set_si(graph->lp->eq[k][4], -1);
1412 for (i = 0; i < graph->n; ++i) {
1413 struct isl_sched_node *node = &graph->node[i];
1414 int pos = 1 + node->start + 1 + 2 * node->nparam;
1416 for (j = 0; j < 2 * node->nvar; ++j)
1417 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1420 if (max_constant_term != -1)
1421 for (i = 0; i < graph->n; ++i) {
1422 struct isl_sched_node *node = &graph->node[i];
1423 k = isl_basic_set_alloc_inequality(graph->lp);
1424 if (k < 0)
1425 return -1;
1426 isl_seq_clr(graph->lp->ineq[k], 1 + total);
1427 isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1);
1428 isl_int_set_si(graph->lp->ineq[k][0], max_constant_term);
1431 if (add_bound_coefficient_constraints(ctx, graph) < 0)
1432 return -1;
1433 if (add_all_validity_constraints(graph) < 0)
1434 return -1;
1435 if (add_all_proximity_constraints(graph) < 0)
1436 return -1;
1438 return 0;
1441 /* Analyze the conflicting constraint found by
1442 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1443 * constraint of one of the edges between distinct nodes, living, moreover
1444 * in distinct SCCs, then record the source and sink SCC as this may
1445 * be a good place to cut between SCCs.
1447 static int check_conflict(int con, void *user)
1449 int i;
1450 struct isl_sched_graph *graph = user;
1452 if (graph->src_scc >= 0)
1453 return 0;
1455 con -= graph->lp->n_eq;
1457 if (con >= graph->lp->n_ineq)
1458 return 0;
1460 for (i = 0; i < graph->n_edge; ++i) {
1461 if (!graph->edge[i].validity)
1462 continue;
1463 if (graph->edge[i].src == graph->edge[i].dst)
1464 continue;
1465 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1466 continue;
1467 if (graph->edge[i].start > con)
1468 continue;
1469 if (graph->edge[i].end <= con)
1470 continue;
1471 graph->src_scc = graph->edge[i].src->scc;
1472 graph->dst_scc = graph->edge[i].dst->scc;
1475 return 0;
1478 /* Check whether the next schedule row of the given node needs to be
1479 * non-trivial. Lower-dimensional domains may have some trivial rows,
1480 * but as soon as the number of remaining required non-trivial rows
1481 * is as large as the number or remaining rows to be computed,
1482 * all remaining rows need to be non-trivial.
1484 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1486 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1489 /* Solve the ILP problem constructed in setup_lp.
1490 * For each node such that all the remaining rows of its schedule
1491 * need to be non-trivial, we construct a non-triviality region.
1492 * This region imposes that the next row is independent of previous rows.
1493 * In particular the coefficients c_i_x are represented by t_i_x
1494 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1495 * its first columns span the rows of the previously computed part
1496 * of the schedule. The non-triviality region enforces that at least
1497 * one of the remaining components of t_i_x is non-zero, i.e.,
1498 * that the new schedule row depends on at least one of the remaining
1499 * columns of Q.
1501 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1503 int i;
1504 isl_vec *sol;
1505 isl_basic_set *lp;
1507 for (i = 0; i < graph->n; ++i) {
1508 struct isl_sched_node *node = &graph->node[i];
1509 int skip = node->rank;
1510 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1511 if (needs_row(graph, node))
1512 graph->region[i].len = 2 * (node->nvar - skip);
1513 else
1514 graph->region[i].len = 0;
1516 lp = isl_basic_set_copy(graph->lp);
1517 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1518 graph->region, &check_conflict, graph);
1519 return sol;
1522 /* Update the schedules of all nodes based on the given solution
1523 * of the LP problem.
1524 * The new row is added to the current band.
1525 * All possibly negative coefficients are encoded as a difference
1526 * of two non-negative variables, so we need to perform the subtraction
1527 * here. Moreover, if use_cmap is set, then the solution does
1528 * not refer to the actual coefficients c_i_x, but instead to variables
1529 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1530 * In this case, we then also need to perform this multiplication
1531 * to obtain the values of c_i_x.
1533 * If check_zero is set, then the first two coordinates of sol are
1534 * assumed to correspond to the dependence distance. If these two
1535 * coordinates are zero, then the corresponding scheduling dimension
1536 * is marked as being zero distance.
1538 static int update_schedule(struct isl_sched_graph *graph,
1539 __isl_take isl_vec *sol, int use_cmap, int check_zero)
1541 int i, j;
1542 int zero = 0;
1543 isl_vec *csol = NULL;
1545 if (!sol)
1546 goto error;
1547 if (sol->size == 0)
1548 isl_die(sol->ctx, isl_error_internal,
1549 "no solution found", goto error);
1551 if (check_zero)
1552 zero = isl_int_is_zero(sol->el[1]) &&
1553 isl_int_is_zero(sol->el[2]);
1555 for (i = 0; i < graph->n; ++i) {
1556 struct isl_sched_node *node = &graph->node[i];
1557 int pos = node->start;
1558 int row = isl_mat_rows(node->sched);
1560 isl_vec_free(csol);
1561 csol = isl_vec_alloc(sol->ctx, node->nvar);
1562 if (!csol)
1563 goto error;
1565 isl_map_free(node->sched_map);
1566 node->sched_map = NULL;
1567 node->sched = isl_mat_add_rows(node->sched, 1);
1568 if (!node->sched)
1569 goto error;
1570 node->sched = isl_mat_set_element(node->sched, row, 0,
1571 sol->el[1 + pos]);
1572 for (j = 0; j < node->nparam + node->nvar; ++j)
1573 isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1574 sol->el[1 + pos + 1 + 2 * j + 1],
1575 sol->el[1 + pos + 1 + 2 * j]);
1576 for (j = 0; j < node->nparam; ++j)
1577 node->sched = isl_mat_set_element(node->sched,
1578 row, 1 + j, sol->el[1+pos+1+2*j+1]);
1579 for (j = 0; j < node->nvar; ++j)
1580 isl_int_set(csol->el[j],
1581 sol->el[1+pos+1+2*(node->nparam+j)+1]);
1582 if (use_cmap)
1583 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1584 csol);
1585 if (!csol)
1586 goto error;
1587 for (j = 0; j < node->nvar; ++j)
1588 node->sched = isl_mat_set_element(node->sched,
1589 row, 1 + node->nparam + j, csol->el[j]);
1590 node->band[graph->n_total_row] = graph->n_band;
1591 node->zero[graph->n_total_row] = zero;
1593 isl_vec_free(sol);
1594 isl_vec_free(csol);
1596 graph->n_row++;
1597 graph->n_total_row++;
1599 return 0;
1600 error:
1601 isl_vec_free(sol);
1602 isl_vec_free(csol);
1603 return -1;
1606 /* Convert node->sched into a multi_aff and return this multi_aff.
1608 static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
1609 struct isl_sched_node *node)
1611 int i, j;
1612 isl_space *space;
1613 isl_local_space *ls;
1614 isl_aff *aff;
1615 isl_multi_aff *ma;
1616 int nrow, ncol;
1617 isl_int v;
1619 nrow = isl_mat_rows(node->sched);
1620 ncol = isl_mat_cols(node->sched) - 1;
1621 space = isl_space_from_domain(isl_space_copy(node->dim));
1622 space = isl_space_add_dims(space, isl_dim_out, nrow);
1623 ma = isl_multi_aff_zero(space);
1624 ls = isl_local_space_from_space(isl_space_copy(node->dim));
1626 isl_int_init(v);
1628 for (i = 0; i < nrow; ++i) {
1629 aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1630 isl_mat_get_element(node->sched, i, 0, &v);
1631 aff = isl_aff_set_constant(aff, v);
1632 for (j = 0; j < node->nparam; ++j) {
1633 isl_mat_get_element(node->sched, i, 1 + j, &v);
1634 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
1636 for (j = 0; j < node->nvar; ++j) {
1637 isl_mat_get_element(node->sched,
1638 i, 1 + node->nparam + j, &v);
1639 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
1641 ma = isl_multi_aff_set_aff(ma, i, aff);
1644 isl_int_clear(v);
1646 isl_local_space_free(ls);
1648 return ma;
1651 /* Convert node->sched into a map and return this map.
1653 * The result is cached in node->sched_map, which needs to be released
1654 * whenever node->sched is updated.
1656 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1658 if (!node->sched_map) {
1659 isl_multi_aff *ma;
1661 ma = node_extract_schedule_multi_aff(node);
1662 node->sched_map = isl_map_from_multi_aff(ma);
1665 return isl_map_copy(node->sched_map);
1668 /* Update the given dependence relation based on the current schedule.
1669 * That is, intersect the dependence relation with a map expressing
1670 * that source and sink are executed within the same iteration of
1671 * the current schedule.
1672 * This is not the most efficient way, but this shouldn't be a critical
1673 * operation.
1675 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1676 struct isl_sched_node *src, struct isl_sched_node *dst)
1678 isl_map *src_sched, *dst_sched, *id;
1680 src_sched = node_extract_schedule(src);
1681 dst_sched = node_extract_schedule(dst);
1682 id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1683 return isl_map_intersect(map, id);
1686 /* Update the dependence relations of all edges based on the current schedule.
1687 * If a dependence is carried completely by the current schedule, then
1688 * it is removed from the edge_tables. It is kept in the list of edges
1689 * as otherwise all edge_tables would have to be recomputed.
1691 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1693 int i;
1695 for (i = graph->n_edge - 1; i >= 0; --i) {
1696 struct isl_sched_edge *edge = &graph->edge[i];
1697 edge->map = specialize(edge->map, edge->src, edge->dst);
1698 if (!edge->map)
1699 return -1;
1701 if (isl_map_plain_is_empty(edge->map))
1702 graph_remove_edge(graph, edge);
1705 return 0;
1708 static void next_band(struct isl_sched_graph *graph)
1710 graph->band_start = graph->n_total_row;
1711 graph->n_band++;
1714 /* Topologically sort statements mapped to the same schedule iteration
1715 * and add a row to the schedule corresponding to this order.
1717 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1719 int i, j;
1721 if (graph->n <= 1)
1722 return 0;
1724 if (update_edges(ctx, graph) < 0)
1725 return -1;
1727 if (graph->n_edge == 0)
1728 return 0;
1730 if (detect_sccs(graph) < 0)
1731 return -1;
1733 for (i = 0; i < graph->n; ++i) {
1734 struct isl_sched_node *node = &graph->node[i];
1735 int row = isl_mat_rows(node->sched);
1736 int cols = isl_mat_cols(node->sched);
1738 isl_map_free(node->sched_map);
1739 node->sched_map = NULL;
1740 node->sched = isl_mat_add_rows(node->sched, 1);
1741 if (!node->sched)
1742 return -1;
1743 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1744 node->scc);
1745 for (j = 1; j < cols; ++j)
1746 node->sched = isl_mat_set_element_si(node->sched,
1747 row, j, 0);
1748 node->band[graph->n_total_row] = graph->n_band;
1751 graph->n_total_row++;
1752 next_band(graph);
1754 return 0;
1757 /* Construct an isl_schedule based on the computed schedule stored
1758 * in graph and with parameters specified by dim.
1760 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1761 __isl_take isl_space *dim)
1763 int i;
1764 isl_ctx *ctx;
1765 isl_schedule *sched = NULL;
1767 if (!dim)
1768 return NULL;
1770 ctx = isl_space_get_ctx(dim);
1771 sched = isl_calloc(ctx, struct isl_schedule,
1772 sizeof(struct isl_schedule) +
1773 (graph->n - 1) * sizeof(struct isl_schedule_node));
1774 if (!sched)
1775 goto error;
1777 sched->ref = 1;
1778 sched->n = graph->n;
1779 sched->n_band = graph->n_band;
1780 sched->n_total_row = graph->n_total_row;
1782 for (i = 0; i < sched->n; ++i) {
1783 int r, b;
1784 int *band_end, *band_id, *zero;
1786 band_end = isl_alloc_array(ctx, int, graph->n_band);
1787 band_id = isl_alloc_array(ctx, int, graph->n_band);
1788 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1789 sched->node[i].sched =
1790 node_extract_schedule_multi_aff(&graph->node[i]);
1791 sched->node[i].band_end = band_end;
1792 sched->node[i].band_id = band_id;
1793 sched->node[i].zero = zero;
1794 if (!band_end || !band_id || !zero)
1795 goto error;
1797 for (r = 0; r < graph->n_total_row; ++r)
1798 zero[r] = graph->node[i].zero[r];
1799 for (r = b = 0; r < graph->n_total_row; ++r) {
1800 if (graph->node[i].band[r] == b)
1801 continue;
1802 band_end[b++] = r;
1803 if (graph->node[i].band[r] == -1)
1804 break;
1806 if (r == graph->n_total_row)
1807 band_end[b++] = r;
1808 sched->node[i].n_band = b;
1809 for (--b; b >= 0; --b)
1810 band_id[b] = graph->node[i].band_id[b];
1813 sched->dim = dim;
1815 return sched;
1816 error:
1817 isl_space_free(dim);
1818 isl_schedule_free(sched);
1819 return NULL;
1822 /* Copy nodes that satisfy node_pred from the src dependence graph
1823 * to the dst dependence graph.
1825 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1826 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1828 int i;
1830 dst->n = 0;
1831 for (i = 0; i < src->n; ++i) {
1832 if (!node_pred(&src->node[i], data))
1833 continue;
1834 dst->node[dst->n].dim = isl_space_copy(src->node[i].dim);
1835 dst->node[dst->n].nvar = src->node[i].nvar;
1836 dst->node[dst->n].nparam = src->node[i].nparam;
1837 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1838 dst->node[dst->n].sched_map =
1839 isl_map_copy(src->node[i].sched_map);
1840 dst->node[dst->n].band = src->node[i].band;
1841 dst->node[dst->n].band_id = src->node[i].band_id;
1842 dst->node[dst->n].zero = src->node[i].zero;
1843 dst->n++;
1846 return 0;
1849 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1850 * to the dst dependence graph.
1851 * If the source or destination node of the edge is not in the destination
1852 * graph, then it must be a backward proximity edge and it should simply
1853 * be ignored.
1855 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1856 struct isl_sched_graph *src,
1857 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1859 int i;
1860 int t;
1862 dst->n_edge = 0;
1863 for (i = 0; i < src->n_edge; ++i) {
1864 struct isl_sched_edge *edge = &src->edge[i];
1865 isl_map *map;
1866 struct isl_sched_node *dst_src, *dst_dst;
1868 if (!edge_pred(edge, data))
1869 continue;
1871 if (isl_map_plain_is_empty(edge->map))
1872 continue;
1874 dst_src = graph_find_node(ctx, dst, edge->src->dim);
1875 dst_dst = graph_find_node(ctx, dst, edge->dst->dim);
1876 if (!dst_src || !dst_dst) {
1877 if (edge->validity)
1878 isl_die(ctx, isl_error_internal,
1879 "backward validity edge", return -1);
1880 continue;
1883 map = isl_map_copy(edge->map);
1885 dst->edge[dst->n_edge].src = dst_src;
1886 dst->edge[dst->n_edge].dst = dst_dst;
1887 dst->edge[dst->n_edge].map = map;
1888 dst->edge[dst->n_edge].validity = edge->validity;
1889 dst->edge[dst->n_edge].proximity = edge->proximity;
1890 dst->n_edge++;
1892 for (t = 0; t <= isl_edge_last; ++t) {
1893 if (edge !=
1894 graph_find_edge(src, t, edge->src, edge->dst))
1895 continue;
1896 if (graph_edge_table_add(ctx, dst, t,
1897 &dst->edge[dst->n_edge - 1]) < 0)
1898 return -1;
1902 return 0;
1905 /* Given a "src" dependence graph that contains the nodes from "dst"
1906 * that satisfy node_pred, copy the schedule computed in "src"
1907 * for those nodes back to "dst".
1909 static int copy_schedule(struct isl_sched_graph *dst,
1910 struct isl_sched_graph *src,
1911 int (*node_pred)(struct isl_sched_node *node, int data), int data)
1913 int i;
1915 src->n = 0;
1916 for (i = 0; i < dst->n; ++i) {
1917 if (!node_pred(&dst->node[i], data))
1918 continue;
1919 isl_mat_free(dst->node[i].sched);
1920 isl_map_free(dst->node[i].sched_map);
1921 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1922 dst->node[i].sched_map =
1923 isl_map_copy(src->node[src->n].sched_map);
1924 src->n++;
1927 dst->n_total_row = src->n_total_row;
1928 dst->n_band = src->n_band;
1930 return 0;
1933 /* Compute the maximal number of variables over all nodes.
1934 * This is the maximal number of linearly independent schedule
1935 * rows that we need to compute.
1936 * Just in case we end up in a part of the dependence graph
1937 * with only lower-dimensional domains, we make sure we will
1938 * compute the required amount of extra linearly independent rows.
1940 static int compute_maxvar(struct isl_sched_graph *graph)
1942 int i;
1944 graph->maxvar = 0;
1945 for (i = 0; i < graph->n; ++i) {
1946 struct isl_sched_node *node = &graph->node[i];
1947 int nvar;
1949 if (node_update_cmap(node) < 0)
1950 return -1;
1951 nvar = node->nvar + graph->n_row - node->rank;
1952 if (nvar > graph->maxvar)
1953 graph->maxvar = nvar;
1956 return 0;
1959 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1960 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1962 /* Compute a schedule for a subgraph of "graph". In particular, for
1963 * the graph composed of nodes that satisfy node_pred and edges that
1964 * that satisfy edge_pred. The caller should precompute the number
1965 * of nodes and edges that satisfy these predicates and pass them along
1966 * as "n" and "n_edge".
1967 * If the subgraph is known to consist of a single component, then wcc should
1968 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1969 * Otherwise, we call compute_schedule, which will check whether the subgraph
1970 * is connected.
1972 static int compute_sub_schedule(isl_ctx *ctx,
1973 struct isl_sched_graph *graph, int n, int n_edge,
1974 int (*node_pred)(struct isl_sched_node *node, int data),
1975 int (*edge_pred)(struct isl_sched_edge *edge, int data),
1976 int data, int wcc)
1978 struct isl_sched_graph split = { 0 };
1979 int t;
1981 if (graph_alloc(ctx, &split, n, n_edge) < 0)
1982 goto error;
1983 if (copy_nodes(&split, graph, node_pred, data) < 0)
1984 goto error;
1985 if (graph_init_table(ctx, &split) < 0)
1986 goto error;
1987 for (t = 0; t <= isl_edge_last; ++t)
1988 split.max_edge[t] = graph->max_edge[t];
1989 if (graph_init_edge_tables(ctx, &split) < 0)
1990 goto error;
1991 if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1992 goto error;
1993 split.n_row = graph->n_row;
1994 split.n_total_row = graph->n_total_row;
1995 split.n_band = graph->n_band;
1996 split.band_start = graph->band_start;
1998 if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1999 goto error;
2000 if (!wcc && compute_schedule(ctx, &split) < 0)
2001 goto error;
2003 copy_schedule(graph, &split, node_pred, data);
2005 graph_free(ctx, &split);
2006 return 0;
2007 error:
2008 graph_free(ctx, &split);
2009 return -1;
2012 static int node_scc_exactly(struct isl_sched_node *node, int scc)
2014 return node->scc == scc;
2017 static int node_scc_at_most(struct isl_sched_node *node, int scc)
2019 return node->scc <= scc;
2022 static int node_scc_at_least(struct isl_sched_node *node, int scc)
2024 return node->scc >= scc;
2027 static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
2029 return edge->src->scc == scc && edge->dst->scc == scc;
2032 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
2034 return edge->dst->scc <= scc;
2037 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
2039 return edge->src->scc >= scc;
2042 /* Pad the schedules of all nodes with zero rows such that in the end
2043 * they all have graph->n_total_row rows.
2044 * The extra rows don't belong to any band, so they get assigned band number -1.
2046 static int pad_schedule(struct isl_sched_graph *graph)
2048 int i, j;
2050 for (i = 0; i < graph->n; ++i) {
2051 struct isl_sched_node *node = &graph->node[i];
2052 int row = isl_mat_rows(node->sched);
2053 if (graph->n_total_row > row) {
2054 isl_map_free(node->sched_map);
2055 node->sched_map = NULL;
2057 node->sched = isl_mat_add_zero_rows(node->sched,
2058 graph->n_total_row - row);
2059 if (!node->sched)
2060 return -1;
2061 for (j = row; j < graph->n_total_row; ++j)
2062 node->band[j] = -1;
2065 return 0;
2068 /* Split the current graph into two parts and compute a schedule for each
2069 * part individually. In particular, one part consists of all SCCs up
2070 * to and including graph->src_scc, while the other part contains the other
2071 * SCCS.
2073 * The split is enforced in the schedule by constant rows with two different
2074 * values (0 and 1). These constant rows replace the previously computed rows
2075 * in the current band.
2076 * It would be possible to reuse them as the first rows in the next
2077 * band, but recomputing them may result in better rows as we are looking
2078 * at a smaller part of the dependence graph.
2079 * compute_split_schedule is only called when no zero-distance schedule row
2080 * could be found on the entire graph, so we wark the splitting row as
2081 * non zero-distance.
2083 * The band_id of the second group is set to n, where n is the number
2084 * of nodes in the first group. This ensures that the band_ids over
2085 * the two groups remain disjoint, even if either or both of the two
2086 * groups contain independent components.
2088 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2090 int i, j, n, e1, e2;
2091 int n_total_row, orig_total_row;
2092 int n_band, orig_band;
2093 int drop;
2095 drop = graph->n_total_row - graph->band_start;
2096 graph->n_total_row -= drop;
2097 graph->n_row -= drop;
2099 n = 0;
2100 for (i = 0; i < graph->n; ++i) {
2101 struct isl_sched_node *node = &graph->node[i];
2102 int row = isl_mat_rows(node->sched) - drop;
2103 int cols = isl_mat_cols(node->sched);
2104 int before = node->scc <= graph->src_scc;
2106 if (before)
2107 n++;
2109 isl_map_free(node->sched_map);
2110 node->sched_map = NULL;
2111 node->sched = isl_mat_drop_rows(node->sched,
2112 graph->band_start, drop);
2113 node->sched = isl_mat_add_rows(node->sched, 1);
2114 if (!node->sched)
2115 return -1;
2116 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2117 !before);
2118 for (j = 1; j < cols; ++j)
2119 node->sched = isl_mat_set_element_si(node->sched,
2120 row, j, 0);
2121 node->band[graph->n_total_row] = graph->n_band;
2122 node->zero[graph->n_total_row] = 0;
2125 e1 = e2 = 0;
2126 for (i = 0; i < graph->n_edge; ++i) {
2127 if (graph->edge[i].dst->scc <= graph->src_scc)
2128 e1++;
2129 if (graph->edge[i].src->scc > graph->src_scc)
2130 e2++;
2133 graph->n_total_row++;
2134 next_band(graph);
2136 for (i = 0; i < graph->n; ++i) {
2137 struct isl_sched_node *node = &graph->node[i];
2138 if (node->scc > graph->src_scc)
2139 node->band_id[graph->n_band] = n;
2142 orig_total_row = graph->n_total_row;
2143 orig_band = graph->n_band;
2144 if (compute_sub_schedule(ctx, graph, n, e1,
2145 &node_scc_at_most, &edge_dst_scc_at_most,
2146 graph->src_scc, 0) < 0)
2147 return -1;
2148 n_total_row = graph->n_total_row;
2149 graph->n_total_row = orig_total_row;
2150 n_band = graph->n_band;
2151 graph->n_band = orig_band;
2152 if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
2153 &node_scc_at_least, &edge_src_scc_at_least,
2154 graph->src_scc + 1, 0) < 0)
2155 return -1;
2156 if (n_total_row > graph->n_total_row)
2157 graph->n_total_row = n_total_row;
2158 if (n_band > graph->n_band)
2159 graph->n_band = n_band;
2161 return pad_schedule(graph);
2164 /* Compute the next band of the schedule after updating the dependence
2165 * relations based on the the current schedule.
2167 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
2169 if (update_edges(ctx, graph) < 0)
2170 return -1;
2171 next_band(graph);
2173 return compute_schedule(ctx, graph);
2176 /* Add constraints to graph->lp that force the dependence "map" (which
2177 * is part of the dependence relation of "edge")
2178 * to be respected and attempt to carry it, where the edge is one from
2179 * a node j to itself. "pos" is the sequence number of the given map.
2180 * That is, add constraints that enforce
2182 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2183 * = c_j_x (y - x) >= e_i
2185 * for each (x,y) in R.
2186 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2187 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2188 * with each coefficient in c_j_x represented as a pair of non-negative
2189 * coefficients.
2191 static int add_intra_constraints(struct isl_sched_graph *graph,
2192 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2194 unsigned total;
2195 isl_ctx *ctx = isl_map_get_ctx(map);
2196 isl_space *dim;
2197 isl_dim_map *dim_map;
2198 isl_basic_set *coef;
2199 struct isl_sched_node *node = edge->src;
2201 coef = intra_coefficients(graph, map);
2203 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2205 total = isl_basic_set_total_dim(graph->lp);
2206 dim_map = isl_dim_map_alloc(ctx, total);
2207 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2208 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
2209 isl_space_dim(dim, isl_dim_set), 1,
2210 node->nvar, -1);
2211 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
2212 isl_space_dim(dim, isl_dim_set), 1,
2213 node->nvar, 1);
2214 graph->lp = isl_basic_set_extend_constraints(graph->lp,
2215 coef->n_eq, coef->n_ineq);
2216 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2217 coef, dim_map);
2218 isl_space_free(dim);
2220 return 0;
2223 /* Add constraints to graph->lp that force the dependence "map" (which
2224 * is part of the dependence relation of "edge")
2225 * to be respected and attempt to carry it, where the edge is one from
2226 * node j to node k. "pos" is the sequence number of the given map.
2227 * That is, add constraints that enforce
2229 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2231 * for each (x,y) in R.
2232 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2233 * of valid constraints for R and then plug in
2234 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2235 * with each coefficient (except e_i, c_k_0 and c_j_0)
2236 * represented as a pair of non-negative coefficients.
2238 static int add_inter_constraints(struct isl_sched_graph *graph,
2239 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2241 unsigned total;
2242 isl_ctx *ctx = isl_map_get_ctx(map);
2243 isl_space *dim;
2244 isl_dim_map *dim_map;
2245 isl_basic_set *coef;
2246 struct isl_sched_node *src = edge->src;
2247 struct isl_sched_node *dst = edge->dst;
2249 coef = inter_coefficients(graph, map);
2251 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2253 total = isl_basic_set_total_dim(graph->lp);
2254 dim_map = isl_dim_map_alloc(ctx, total);
2256 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2258 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
2259 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
2260 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
2261 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
2262 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2263 dst->nvar, -1);
2264 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
2265 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2266 dst->nvar, 1);
2268 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
2269 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
2270 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
2271 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
2272 isl_space_dim(dim, isl_dim_set), 1,
2273 src->nvar, 1);
2274 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
2275 isl_space_dim(dim, isl_dim_set), 1,
2276 src->nvar, -1);
2278 graph->lp = isl_basic_set_extend_constraints(graph->lp,
2279 coef->n_eq, coef->n_ineq);
2280 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2281 coef, dim_map);
2282 isl_space_free(dim);
2284 return 0;
2287 /* Add constraints to graph->lp that force all validity dependences
2288 * to be respected and attempt to carry them.
2290 static int add_all_constraints(struct isl_sched_graph *graph)
2292 int i, j;
2293 int pos;
2295 pos = 0;
2296 for (i = 0; i < graph->n_edge; ++i) {
2297 struct isl_sched_edge *edge= &graph->edge[i];
2299 if (!edge->validity)
2300 continue;
2302 for (j = 0; j < edge->map->n; ++j) {
2303 isl_basic_map *bmap;
2304 isl_map *map;
2306 bmap = isl_basic_map_copy(edge->map->p[j]);
2307 map = isl_map_from_basic_map(bmap);
2309 if (edge->src == edge->dst &&
2310 add_intra_constraints(graph, edge, map, pos) < 0)
2311 return -1;
2312 if (edge->src != edge->dst &&
2313 add_inter_constraints(graph, edge, map, pos) < 0)
2314 return -1;
2315 ++pos;
2319 return 0;
2322 /* Count the number of equality and inequality constraints
2323 * that will be added to the carry_lp problem.
2324 * We count each edge exactly once.
2326 static int count_all_constraints(struct isl_sched_graph *graph,
2327 int *n_eq, int *n_ineq)
2329 int i, j;
2331 *n_eq = *n_ineq = 0;
2332 for (i = 0; i < graph->n_edge; ++i) {
2333 struct isl_sched_edge *edge= &graph->edge[i];
2334 for (j = 0; j < edge->map->n; ++j) {
2335 isl_basic_map *bmap;
2336 isl_map *map;
2338 bmap = isl_basic_map_copy(edge->map->p[j]);
2339 map = isl_map_from_basic_map(bmap);
2341 if (count_map_constraints(graph, edge, map,
2342 n_eq, n_ineq, 1) < 0)
2343 return -1;
2347 return 0;
2350 /* Construct an LP problem for finding schedule coefficients
2351 * such that the schedule carries as many dependences as possible.
2352 * In particular, for each dependence i, we bound the dependence distance
2353 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2354 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2355 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2356 * Note that if the dependence relation is a union of basic maps,
2357 * then we have to consider each basic map individually as it may only
2358 * be possible to carry the dependences expressed by some of those
2359 * basic maps and not all off them.
2360 * Below, we consider each of those basic maps as a separate "edge".
2362 * All variables of the LP are non-negative. The actual coefficients
2363 * may be negative, so each coefficient is represented as the difference
2364 * of two non-negative variables. The negative part always appears
2365 * immediately before the positive part.
2366 * Other than that, the variables have the following order
2368 * - sum of (1 - e_i) over all edges
2369 * - sum of positive and negative parts of all c_n coefficients
2370 * (unconstrained when computing non-parametric schedules)
2371 * - sum of positive and negative parts of all c_x coefficients
2372 * - for each edge
2373 * - e_i
2374 * - for each node
2375 * - c_i_0
2376 * - positive and negative parts of c_i_n (if parametric)
2377 * - positive and negative parts of c_i_x
2379 * The constraints are those from the (validity) edges plus three equalities
2380 * to express the sums and n_edge inequalities to express e_i <= 1.
2382 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2384 int i, j;
2385 int k;
2386 isl_space *dim;
2387 unsigned total;
2388 int n_eq, n_ineq;
2389 int n_edge;
2391 n_edge = 0;
2392 for (i = 0; i < graph->n_edge; ++i)
2393 n_edge += graph->edge[i].map->n;
2395 total = 3 + n_edge;
2396 for (i = 0; i < graph->n; ++i) {
2397 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2398 node->start = total;
2399 total += 1 + 2 * (node->nparam + node->nvar);
2402 if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
2403 return -1;
2405 dim = isl_space_set_alloc(ctx, 0, total);
2406 isl_basic_set_free(graph->lp);
2407 n_eq += 3;
2408 n_ineq += n_edge;
2409 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2410 graph->lp = isl_basic_set_set_rational(graph->lp);
2412 k = isl_basic_set_alloc_equality(graph->lp);
2413 if (k < 0)
2414 return -1;
2415 isl_seq_clr(graph->lp->eq[k], 1 + total);
2416 isl_int_set_si(graph->lp->eq[k][0], -n_edge);
2417 isl_int_set_si(graph->lp->eq[k][1], 1);
2418 for (i = 0; i < n_edge; ++i)
2419 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2421 k = isl_basic_set_alloc_equality(graph->lp);
2422 if (k < 0)
2423 return -1;
2424 isl_seq_clr(graph->lp->eq[k], 1 + total);
2425 isl_int_set_si(graph->lp->eq[k][2], -1);
2426 for (i = 0; i < graph->n; ++i) {
2427 int pos = 1 + graph->node[i].start + 1;
2429 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2430 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2433 k = isl_basic_set_alloc_equality(graph->lp);
2434 if (k < 0)
2435 return -1;
2436 isl_seq_clr(graph->lp->eq[k], 1 + total);
2437 isl_int_set_si(graph->lp->eq[k][3], -1);
2438 for (i = 0; i < graph->n; ++i) {
2439 struct isl_sched_node *node = &graph->node[i];
2440 int pos = 1 + node->start + 1 + 2 * node->nparam;
2442 for (j = 0; j < 2 * node->nvar; ++j)
2443 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2446 for (i = 0; i < n_edge; ++i) {
2447 k = isl_basic_set_alloc_inequality(graph->lp);
2448 if (k < 0)
2449 return -1;
2450 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2451 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2452 isl_int_set_si(graph->lp->ineq[k][0], 1);
2455 if (add_all_constraints(graph) < 0)
2456 return -1;
2458 return 0;
2461 /* If the schedule_split_scaled option is set and if the linear
2462 * parts of the scheduling rows for all nodes in the graphs have
2463 * non-trivial common divisor, then split off the constant term
2464 * from the linear part.
2465 * The constant term is then placed in a separate band and
2466 * the linear part is reduced.
2468 static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph)
2470 int i;
2471 int row;
2472 isl_int gcd, gcd_i;
2474 if (!ctx->opt->schedule_split_scaled)
2475 return 0;
2476 if (graph->n <= 1)
2477 return 0;
2479 isl_int_init(gcd);
2480 isl_int_init(gcd_i);
2482 isl_int_set_si(gcd, 0);
2484 row = isl_mat_rows(graph->node[0].sched) - 1;
2486 for (i = 0; i < graph->n; ++i) {
2487 struct isl_sched_node *node = &graph->node[i];
2488 int cols = isl_mat_cols(node->sched);
2490 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
2491 isl_int_gcd(gcd, gcd, gcd_i);
2494 isl_int_clear(gcd_i);
2496 if (isl_int_cmp_si(gcd, 1) <= 0) {
2497 isl_int_clear(gcd);
2498 return 0;
2501 next_band(graph);
2503 for (i = 0; i < graph->n; ++i) {
2504 struct isl_sched_node *node = &graph->node[i];
2506 isl_map_free(node->sched_map);
2507 node->sched_map = NULL;
2508 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2509 if (!node->sched)
2510 goto error;
2511 isl_int_fdiv_r(node->sched->row[row + 1][0],
2512 node->sched->row[row][0], gcd);
2513 isl_int_fdiv_q(node->sched->row[row][0],
2514 node->sched->row[row][0], gcd);
2515 isl_int_mul(node->sched->row[row][0],
2516 node->sched->row[row][0], gcd);
2517 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
2518 if (!node->sched)
2519 goto error;
2520 node->band[graph->n_total_row] = graph->n_band;
2523 graph->n_total_row++;
2525 isl_int_clear(gcd);
2526 return 0;
2527 error:
2528 isl_int_clear(gcd);
2529 return -1;
2532 /* Construct a schedule row for each node such that as many dependences
2533 * as possible are carried and then continue with the next band.
2535 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2537 int i;
2538 int n_edge;
2539 isl_vec *sol;
2540 isl_basic_set *lp;
2542 n_edge = 0;
2543 for (i = 0; i < graph->n_edge; ++i)
2544 n_edge += graph->edge[i].map->n;
2546 if (setup_carry_lp(ctx, graph) < 0)
2547 return -1;
2549 lp = isl_basic_set_copy(graph->lp);
2550 sol = isl_tab_basic_set_non_neg_lexmin(lp);
2551 if (!sol)
2552 return -1;
2554 if (sol->size == 0) {
2555 isl_vec_free(sol);
2556 isl_die(ctx, isl_error_internal,
2557 "error in schedule construction", return -1);
2560 if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
2561 isl_vec_free(sol);
2562 isl_die(ctx, isl_error_unknown,
2563 "unable to carry dependences", return -1);
2566 if (update_schedule(graph, sol, 0, 0) < 0)
2567 return -1;
2569 if (split_scaled(ctx, graph) < 0)
2570 return -1;
2572 return compute_next_band(ctx, graph);
2575 /* Are there any (non-empty) validity edges in the graph?
2577 static int has_validity_edges(struct isl_sched_graph *graph)
2579 int i;
2581 for (i = 0; i < graph->n_edge; ++i) {
2582 int empty;
2584 empty = isl_map_plain_is_empty(graph->edge[i].map);
2585 if (empty < 0)
2586 return -1;
2587 if (empty)
2588 continue;
2589 if (graph->edge[i].validity)
2590 return 1;
2593 return 0;
2596 /* Should we apply a Feautrier step?
2597 * That is, did the user request the Feautrier algorithm and are
2598 * there any validity dependences (left)?
2600 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
2602 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
2603 return 0;
2605 return has_validity_edges(graph);
2608 /* Compute a schedule for a connected dependence graph using Feautrier's
2609 * multi-dimensional scheduling algorithm.
2610 * The original algorithm is described in [1].
2611 * The main idea is to minimize the number of scheduling dimensions, by
2612 * trying to satisfy as many dependences as possible per scheduling dimension.
2614 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2615 * Problem, Part II: Multi-Dimensional Time.
2616 * In Intl. Journal of Parallel Programming, 1992.
2618 static int compute_schedule_wcc_feautrier(isl_ctx *ctx,
2619 struct isl_sched_graph *graph)
2621 return carry_dependences(ctx, graph);
2624 /* Compute a schedule for a connected dependence graph.
2625 * We try to find a sequence of as many schedule rows as possible that result
2626 * in non-negative dependence distances (independent of the previous rows
2627 * in the sequence, i.e., such that the sequence is tilable).
2628 * If we can't find any more rows we either
2629 * - split between SCCs and start over (assuming we found an interesting
2630 * pair of SCCs between which to split)
2631 * - continue with the next band (assuming the current band has at least
2632 * one row)
2633 * - try to carry as many dependences as possible and continue with the next
2634 * band
2636 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2637 * as many validity dependences as possible. When all validity dependences
2638 * are satisfied we extend the schedule to a full-dimensional schedule.
2640 * If we manage to complete the schedule, we finish off by topologically
2641 * sorting the statements based on the remaining dependences.
2643 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2644 * outermost dimension in the current band to be zero distance. If this
2645 * turns out to be impossible, we fall back on the general scheme above
2646 * and try to carry as many dependences as possible.
2648 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2650 int force_zero = 0;
2652 if (detect_sccs(graph) < 0)
2653 return -1;
2654 sort_sccs(graph);
2656 if (compute_maxvar(graph) < 0)
2657 return -1;
2659 if (need_feautrier_step(ctx, graph))
2660 return compute_schedule_wcc_feautrier(ctx, graph);
2662 if (ctx->opt->schedule_outer_zero_distance)
2663 force_zero = 1;
2665 while (graph->n_row < graph->maxvar) {
2666 isl_vec *sol;
2668 graph->src_scc = -1;
2669 graph->dst_scc = -1;
2671 if (setup_lp(ctx, graph, force_zero) < 0)
2672 return -1;
2673 sol = solve_lp(graph);
2674 if (!sol)
2675 return -1;
2676 if (sol->size == 0) {
2677 isl_vec_free(sol);
2678 if (!ctx->opt->schedule_maximize_band_depth &&
2679 graph->n_total_row > graph->band_start)
2680 return compute_next_band(ctx, graph);
2681 if (graph->src_scc >= 0)
2682 return compute_split_schedule(ctx, graph);
2683 if (graph->n_total_row > graph->band_start)
2684 return compute_next_band(ctx, graph);
2685 return carry_dependences(ctx, graph);
2687 if (update_schedule(graph, sol, 1, 1) < 0)
2688 return -1;
2689 force_zero = 0;
2692 if (graph->n_total_row > graph->band_start)
2693 next_band(graph);
2694 return sort_statements(ctx, graph);
2697 /* Add a row to the schedules that separates the SCCs and move
2698 * to the next band.
2700 static int split_on_scc(struct isl_sched_graph *graph)
2702 int i;
2704 for (i = 0; i < graph->n; ++i) {
2705 struct isl_sched_node *node = &graph->node[i];
2706 int row = isl_mat_rows(node->sched);
2708 isl_map_free(node->sched_map);
2709 node->sched_map = NULL;
2710 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2711 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2712 node->scc);
2713 if (!node->sched)
2714 return -1;
2715 node->band[graph->n_total_row] = graph->n_band;
2718 graph->n_total_row++;
2719 next_band(graph);
2721 return 0;
2724 /* Compute a schedule for each component (identified by node->scc)
2725 * of the dependence graph separately and then combine the results.
2726 * Depending on the setting of schedule_fuse, a component may be
2727 * either weakly or strongly connected.
2729 * The band_id is adjusted such that each component has a separate id.
2730 * Note that the band_id may have already been set to a value different
2731 * from zero by compute_split_schedule.
2733 static int compute_component_schedule(isl_ctx *ctx,
2734 struct isl_sched_graph *graph)
2736 int wcc, i;
2737 int n, n_edge;
2738 int n_total_row, orig_total_row;
2739 int n_band, orig_band;
2741 if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN ||
2742 ctx->opt->schedule_separate_components)
2743 split_on_scc(graph);
2745 n_total_row = 0;
2746 orig_total_row = graph->n_total_row;
2747 n_band = 0;
2748 orig_band = graph->n_band;
2749 for (i = 0; i < graph->n; ++i)
2750 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2751 for (wcc = 0; wcc < graph->scc; ++wcc) {
2752 n = 0;
2753 for (i = 0; i < graph->n; ++i)
2754 if (graph->node[i].scc == wcc)
2755 n++;
2756 n_edge = 0;
2757 for (i = 0; i < graph->n_edge; ++i)
2758 if (graph->edge[i].src->scc == wcc &&
2759 graph->edge[i].dst->scc == wcc)
2760 n_edge++;
2762 if (compute_sub_schedule(ctx, graph, n, n_edge,
2763 &node_scc_exactly,
2764 &edge_scc_exactly, wcc, 1) < 0)
2765 return -1;
2766 if (graph->n_total_row > n_total_row)
2767 n_total_row = graph->n_total_row;
2768 graph->n_total_row = orig_total_row;
2769 if (graph->n_band > n_band)
2770 n_band = graph->n_band;
2771 graph->n_band = orig_band;
2774 graph->n_total_row = n_total_row;
2775 graph->n_band = n_band;
2777 return pad_schedule(graph);
2780 /* Compute a schedule for the given dependence graph.
2781 * We first check if the graph is connected (through validity dependences)
2782 * and, if not, compute a schedule for each component separately.
2783 * If schedule_fuse is set to minimal fusion, then we check for strongly
2784 * connected components instead and compute a separate schedule for
2785 * each such strongly connected component.
2787 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2789 if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) {
2790 if (detect_sccs(graph) < 0)
2791 return -1;
2792 } else {
2793 if (detect_wccs(graph) < 0)
2794 return -1;
2797 if (graph->scc > 1)
2798 return compute_component_schedule(ctx, graph);
2800 return compute_schedule_wcc(ctx, graph);
2803 /* Compute a schedule for the given union of domains that respects
2804 * all the validity dependences.
2805 * If the default isl scheduling algorithm is used, it tries to minimize
2806 * the dependence distances over the proximity dependences.
2807 * If Feautrier's scheduling algorithm is used, the proximity dependence
2808 * distances are only minimized during the extension to a full-dimensional
2809 * schedule.
2811 __isl_give isl_schedule *isl_union_set_compute_schedule(
2812 __isl_take isl_union_set *domain,
2813 __isl_take isl_union_map *validity,
2814 __isl_take isl_union_map *proximity)
2816 isl_ctx *ctx = isl_union_set_get_ctx(domain);
2817 isl_space *dim;
2818 struct isl_sched_graph graph = { 0 };
2819 isl_schedule *sched;
2820 struct isl_extract_edge_data data;
2822 domain = isl_union_set_align_params(domain,
2823 isl_union_map_get_space(validity));
2824 domain = isl_union_set_align_params(domain,
2825 isl_union_map_get_space(proximity));
2826 dim = isl_union_set_get_space(domain);
2827 validity = isl_union_map_align_params(validity, isl_space_copy(dim));
2828 proximity = isl_union_map_align_params(proximity, dim);
2830 if (!domain)
2831 goto error;
2833 graph.n = isl_union_set_n_set(domain);
2834 if (graph.n == 0)
2835 goto empty;
2836 if (graph_alloc(ctx, &graph, graph.n,
2837 isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2838 goto error;
2839 if (compute_max_row(&graph, domain) < 0)
2840 goto error;
2841 graph.root = 1;
2842 graph.n = 0;
2843 if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2844 goto error;
2845 if (graph_init_table(ctx, &graph) < 0)
2846 goto error;
2847 graph.max_edge[isl_edge_validity] = isl_union_map_n_map(validity);
2848 graph.max_edge[isl_edge_proximity] = isl_union_map_n_map(proximity);
2849 if (graph_init_edge_tables(ctx, &graph) < 0)
2850 goto error;
2851 graph.n_edge = 0;
2852 data.graph = &graph;
2853 data.type = isl_edge_validity;
2854 if (isl_union_map_foreach_map(validity, &extract_edge, &data) < 0)
2855 goto error;
2856 data.type = isl_edge_proximity;
2857 if (isl_union_map_foreach_map(proximity, &extract_edge, &data) < 0)
2858 goto error;
2860 if (compute_schedule(ctx, &graph) < 0)
2861 goto error;
2863 empty:
2864 sched = extract_schedule(&graph, isl_union_set_get_space(domain));
2866 graph_free(ctx, &graph);
2867 isl_union_set_free(domain);
2868 isl_union_map_free(validity);
2869 isl_union_map_free(proximity);
2871 return sched;
2872 error:
2873 graph_free(ctx, &graph);
2874 isl_union_set_free(domain);
2875 isl_union_map_free(validity);
2876 isl_union_map_free(proximity);
2877 return NULL;
2880 void *isl_schedule_free(__isl_take isl_schedule *sched)
2882 int i;
2883 if (!sched)
2884 return NULL;
2886 if (--sched->ref > 0)
2887 return NULL;
2889 for (i = 0; i < sched->n; ++i) {
2890 isl_multi_aff_free(sched->node[i].sched);
2891 free(sched->node[i].band_end);
2892 free(sched->node[i].band_id);
2893 free(sched->node[i].zero);
2895 isl_space_free(sched->dim);
2896 isl_band_list_free(sched->band_forest);
2897 free(sched);
2898 return NULL;
2901 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2903 return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
2906 /* Return an isl_union_map of the schedule. If we have already constructed
2907 * a band forest, then this band forest may have been modified so we need
2908 * to extract the isl_union_map from the forest rather than from
2909 * the originally computed schedule.
2911 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2913 int i;
2914 isl_union_map *umap;
2916 if (!sched)
2917 return NULL;
2919 if (sched->band_forest)
2920 return isl_band_list_get_suffix_schedule(sched->band_forest);
2922 umap = isl_union_map_empty(isl_space_copy(sched->dim));
2923 for (i = 0; i < sched->n; ++i) {
2924 isl_multi_aff *ma;
2926 ma = isl_multi_aff_copy(sched->node[i].sched);
2927 umap = isl_union_map_add_map(umap, isl_map_from_multi_aff(ma));
2930 return umap;
2933 static __isl_give isl_band_list *construct_band_list(
2934 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2935 int band_nr, int *parent_active, int n_active);
2937 /* Construct an isl_band structure for the band in the given schedule
2938 * with sequence number band_nr for the n_active nodes marked by active.
2939 * If the nodes don't have a band with the given sequence number,
2940 * then a band without members is created.
2942 * Because of the way the schedule is constructed, we know that
2943 * the position of the band inside the schedule of a node is the same
2944 * for all active nodes.
2946 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2947 __isl_keep isl_band *parent,
2948 int band_nr, int *active, int n_active)
2950 int i, j;
2951 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2952 isl_band *band;
2953 unsigned start, end;
2955 band = isl_band_alloc(ctx);
2956 if (!band)
2957 return NULL;
2959 band->schedule = schedule;
2960 band->parent = parent;
2962 for (i = 0; i < schedule->n; ++i)
2963 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2964 break;
2966 if (i < schedule->n) {
2967 band->children = construct_band_list(schedule, band,
2968 band_nr + 1, active, n_active);
2969 if (!band->children)
2970 goto error;
2973 for (i = 0; i < schedule->n; ++i)
2974 if (active[i])
2975 break;
2977 if (i >= schedule->n)
2978 isl_die(ctx, isl_error_internal,
2979 "band without active statements", goto error);
2981 start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2982 end = band_nr < schedule->node[i].n_band ?
2983 schedule->node[i].band_end[band_nr] : start;
2984 band->n = end - start;
2986 band->zero = isl_alloc_array(ctx, int, band->n);
2987 if (!band->zero)
2988 goto error;
2990 for (j = 0; j < band->n; ++j)
2991 band->zero[j] = schedule->node[i].zero[start + j];
2993 band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
2994 for (i = 0; i < schedule->n; ++i) {
2995 isl_multi_aff *ma;
2996 isl_pw_multi_aff *pma;
2997 unsigned n_out;
2999 if (!active[i])
3000 continue;
3002 ma = isl_multi_aff_copy(schedule->node[i].sched);
3003 n_out = isl_multi_aff_dim(ma, isl_dim_out);
3004 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end);
3005 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start);
3006 pma = isl_pw_multi_aff_from_multi_aff(ma);
3007 band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma,
3008 pma);
3010 if (!band->pma)
3011 goto error;
3013 return band;
3014 error:
3015 isl_band_free(band);
3016 return NULL;
3019 /* Construct a list of bands that start at the same position (with
3020 * sequence number band_nr) in the schedules of the nodes that
3021 * were active in the parent band.
3023 * A separate isl_band structure is created for each band_id
3024 * and for each node that does not have a band with sequence
3025 * number band_nr. In the latter case, a band without members
3026 * is created.
3027 * This ensures that if a band has any children, then each node
3028 * that was active in the band is active in exactly one of the children.
3030 static __isl_give isl_band_list *construct_band_list(
3031 __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
3032 int band_nr, int *parent_active, int n_active)
3034 int i, j;
3035 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
3036 int *active;
3037 int n_band;
3038 isl_band_list *list;
3040 n_band = 0;
3041 for (i = 0; i < n_active; ++i) {
3042 for (j = 0; j < schedule->n; ++j) {
3043 if (!parent_active[j])
3044 continue;
3045 if (schedule->node[j].n_band <= band_nr)
3046 continue;
3047 if (schedule->node[j].band_id[band_nr] == i) {
3048 n_band++;
3049 break;
3053 for (j = 0; j < schedule->n; ++j)
3054 if (schedule->node[j].n_band <= band_nr)
3055 n_band++;
3057 if (n_band == 1) {
3058 isl_band *band;
3059 list = isl_band_list_alloc(ctx, n_band);
3060 band = construct_band(schedule, parent, band_nr,
3061 parent_active, n_active);
3062 return isl_band_list_add(list, band);
3065 active = isl_alloc_array(ctx, int, schedule->n);
3066 if (!active)
3067 return NULL;
3069 list = isl_band_list_alloc(ctx, n_band);
3071 for (i = 0; i < n_active; ++i) {
3072 int n = 0;
3073 isl_band *band;
3075 for (j = 0; j < schedule->n; ++j) {
3076 active[j] = parent_active[j] &&
3077 schedule->node[j].n_band > band_nr &&
3078 schedule->node[j].band_id[band_nr] == i;
3079 if (active[j])
3080 n++;
3082 if (n == 0)
3083 continue;
3085 band = construct_band(schedule, parent, band_nr, active, n);
3087 list = isl_band_list_add(list, band);
3089 for (i = 0; i < schedule->n; ++i) {
3090 isl_band *band;
3091 if (!parent_active[i])
3092 continue;
3093 if (schedule->node[i].n_band > band_nr)
3094 continue;
3095 for (j = 0; j < schedule->n; ++j)
3096 active[j] = j == i;
3097 band = construct_band(schedule, parent, band_nr, active, 1);
3098 list = isl_band_list_add(list, band);
3101 free(active);
3103 return list;
3106 /* Construct a band forest representation of the schedule and
3107 * return the list of roots.
3109 static __isl_give isl_band_list *construct_forest(
3110 __isl_keep isl_schedule *schedule)
3112 int i;
3113 isl_ctx *ctx = isl_schedule_get_ctx(schedule);
3114 isl_band_list *forest;
3115 int *active;
3117 active = isl_alloc_array(ctx, int, schedule->n);
3118 if (!active)
3119 return NULL;
3121 for (i = 0; i < schedule->n; ++i)
3122 active[i] = 1;
3124 forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
3126 free(active);
3128 return forest;
3131 /* Return the roots of a band forest representation of the schedule.
3133 __isl_give isl_band_list *isl_schedule_get_band_forest(
3134 __isl_keep isl_schedule *schedule)
3136 if (!schedule)
3137 return NULL;
3138 if (!schedule->band_forest)
3139 schedule->band_forest = construct_forest(schedule);
3140 return isl_band_list_dup(schedule->band_forest);
3143 /* Call "fn" on each band in the schedule in depth-first post-order.
3145 int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
3146 int (*fn)(__isl_keep isl_band *band, void *user), void *user)
3148 int r;
3149 isl_band_list *forest;
3151 if (!sched)
3152 return -1;
3154 forest = isl_schedule_get_band_forest(sched);
3155 r = isl_band_list_foreach_band(forest, fn, user);
3156 isl_band_list_free(forest);
3158 return r;
3161 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
3162 __isl_keep isl_band_list *list);
3164 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
3165 __isl_keep isl_band *band)
3167 isl_band_list *children;
3169 p = isl_printer_start_line(p);
3170 p = isl_printer_print_union_pw_multi_aff(p, band->pma);
3171 p = isl_printer_end_line(p);
3173 if (!isl_band_has_children(band))
3174 return p;
3176 children = isl_band_get_children(band);
3178 p = isl_printer_indent(p, 4);
3179 p = print_band_list(p, children);
3180 p = isl_printer_indent(p, -4);
3182 isl_band_list_free(children);
3184 return p;
3187 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
3188 __isl_keep isl_band_list *list)
3190 int i, n;
3192 n = isl_band_list_n_band(list);
3193 for (i = 0; i < n; ++i) {
3194 isl_band *band;
3195 band = isl_band_list_get_band(list, i);
3196 p = print_band(p, band);
3197 isl_band_free(band);
3200 return p;
3203 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
3204 __isl_keep isl_schedule *schedule)
3206 isl_band_list *forest;
3208 forest = isl_schedule_get_band_forest(schedule);
3210 p = print_band_list(p, forest);
3212 isl_band_list_free(forest);
3214 return p;
3217 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
3219 isl_printer *printer;
3221 if (!schedule)
3222 return;
3224 printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
3225 printer = isl_printer_print_schedule(printer, schedule);
3227 isl_printer_free(printer);