isl_union_*_set_has_dim: rename to isl_union_*_set_has_space
[isl.git] / isl_scheduler.c
blobeee85b7f49d3238814c8823eab91c1e547d61c73
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015-2016 Sven Verdoolaege
5 * Copyright 2016 INRIA Paris
6 * Copyright 2017 Sven Verdoolaege
8 * Use of this software is governed by the MIT license
10 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
11 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 * 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
15 * CS 42112, 75589 Paris Cedex 12, France
18 #include <isl_ctx_private.h>
19 #include <isl_map_private.h>
20 #include <isl_space_private.h>
21 #include <isl_aff_private.h>
22 #include <isl/hash.h>
23 #include <isl/id.h>
24 #include <isl/constraint.h>
25 #include <isl/schedule.h>
26 #include <isl_schedule_constraints.h>
27 #include <isl/schedule_node.h>
28 #include <isl_mat_private.h>
29 #include <isl_vec_private.h>
30 #include <isl/set.h>
31 #include <isl_union_set_private.h>
32 #include <isl_seq.h>
33 #include <isl_tab.h>
34 #include <isl_dim_map.h>
35 #include <isl/map_to_basic_set.h>
36 #include <isl_sort.h>
37 #include <isl_options_private.h>
38 #include <isl_tarjan.h>
39 #include <isl_morph.h>
40 #include <isl/ilp.h>
41 #include <isl_val_private.h>
44 * The scheduling algorithm implemented in this file was inspired by
45 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
46 * Parallelization and Locality Optimization in the Polyhedral Model".
48 * For a detailed description of the variant implemented in isl,
49 * see Verdoolaege and Janssens, "Scheduling for PPCG" (2017).
53 /* Internal information about a node that is used during the construction
54 * of a schedule.
55 * space represents the original space in which the domain lives;
56 * that is, the space is not affected by compression
57 * sched is a matrix representation of the schedule being constructed
58 * for this node; if compressed is set, then this schedule is
59 * defined over the compressed domain space
60 * sched_map is an isl_map representation of the same (partial) schedule
61 * sched_map may be NULL; if compressed is set, then this map
62 * is defined over the uncompressed domain space
63 * rank is the number of linearly independent rows in the linear part
64 * of sched
65 * the rows of "vmap" represent a change of basis for the node
66 * variables; the first rank rows span the linear part of
67 * the schedule rows; the remaining rows are linearly independent
68 * the rows of "indep" represent linear combinations of the schedule
69 * coefficients that are non-zero when the schedule coefficients are
70 * linearly independent of previously computed schedule rows.
71 * start is the first variable in the LP problem in the sequences that
72 * represents the schedule coefficients of this node
73 * nvar is the dimension of the (compressed) domain
74 * nparam is the number of parameters or 0 if we are not constructing
75 * a parametric schedule
77 * If compressed is set, then hull represents the constraints
78 * that were used to derive the compression, while compress and
79 * decompress map the original space to the compressed space and
80 * vice versa.
82 * scc is the index of SCC (or WCC) this node belongs to
84 * "cluster" is only used inside extract_clusters and identifies
85 * the cluster of SCCs that the node belongs to.
87 * coincident contains a boolean for each of the rows of the schedule,
88 * indicating whether the corresponding scheduling dimension satisfies
89 * the coincidence constraints in the sense that the corresponding
90 * dependence distances are zero.
92 * If the schedule_treat_coalescing option is set, then
93 * "sizes" contains the sizes of the (compressed) instance set
94 * in each direction. If there is no fixed size in a given direction,
95 * then the corresponding size value is set to infinity.
96 * If the schedule_treat_coalescing option or the schedule_max_coefficient
97 * option is set, then "max" contains the maximal values for
98 * schedule coefficients of the (compressed) variables. If no bound
99 * needs to be imposed on a particular variable, then the corresponding
100 * value is negative.
101 * If not NULL, then "bounds" contains a non-parametric set
102 * in the compressed space that is bounded by the size in each direction.
104 struct isl_sched_node {
105 isl_space *space;
106 int compressed;
107 isl_set *hull;
108 isl_multi_aff *compress;
109 isl_multi_aff *decompress;
110 isl_mat *sched;
111 isl_map *sched_map;
112 int rank;
113 isl_mat *indep;
114 isl_mat *vmap;
115 int start;
116 int nvar;
117 int nparam;
119 int scc;
120 int cluster;
122 int *coincident;
124 isl_multi_val *sizes;
125 isl_basic_set *bounds;
126 isl_vec *max;
129 static int node_has_tuples(const void *entry, const void *val)
131 struct isl_sched_node *node = (struct isl_sched_node *)entry;
132 isl_space *space = (isl_space *) val;
134 return isl_space_has_equal_tuples(node->space, space);
137 static int node_scc_exactly(struct isl_sched_node *node, int scc)
139 return node->scc == scc;
142 static int node_scc_at_most(struct isl_sched_node *node, int scc)
144 return node->scc <= scc;
147 static int node_scc_at_least(struct isl_sched_node *node, int scc)
149 return node->scc >= scc;
152 /* An edge in the dependence graph. An edge may be used to
153 * ensure validity of the generated schedule, to minimize the dependence
154 * distance or both
156 * map is the dependence relation, with i -> j in the map if j depends on i
157 * tagged_condition and tagged_validity contain the union of all tagged
158 * condition or conditional validity dependence relations that
159 * specialize the dependence relation "map"; that is,
160 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
161 * or "tagged_validity", then i -> j is an element of "map".
162 * If these fields are NULL, then they represent the empty relation.
163 * src is the source node
164 * dst is the sink node
166 * types is a bit vector containing the types of this edge.
167 * validity is set if the edge is used to ensure correctness
168 * coincidence is used to enforce zero dependence distances
169 * proximity is set if the edge is used to minimize dependence distances
170 * condition is set if the edge represents a condition
171 * for a conditional validity schedule constraint
172 * local can only be set for condition edges and indicates that
173 * the dependence distance over the edge should be zero
174 * conditional_validity is set if the edge is used to conditionally
175 * ensure correctness
177 * For validity edges, start and end mark the sequence of inequality
178 * constraints in the LP problem that encode the validity constraint
179 * corresponding to this edge.
181 * During clustering, an edge may be marked "no_merge" if it should
182 * not be used to merge clusters.
183 * The weight is also only used during clustering and it is
184 * an indication of how many schedule dimensions on either side
185 * of the schedule constraints can be aligned.
186 * If the weight is negative, then this means that this edge was postponed
187 * by has_bounded_distances or any_no_merge. The original weight can
188 * be retrieved by adding 1 + graph->max_weight, with "graph"
189 * the graph containing this edge.
191 struct isl_sched_edge {
192 isl_map *map;
193 isl_union_map *tagged_condition;
194 isl_union_map *tagged_validity;
196 struct isl_sched_node *src;
197 struct isl_sched_node *dst;
199 unsigned types;
201 int start;
202 int end;
204 int no_merge;
205 int weight;
208 /* Is "edge" marked as being of type "type"?
210 static int is_type(struct isl_sched_edge *edge, enum isl_edge_type type)
212 return ISL_FL_ISSET(edge->types, 1 << type);
215 /* Mark "edge" as being of type "type".
217 static void set_type(struct isl_sched_edge *edge, enum isl_edge_type type)
219 ISL_FL_SET(edge->types, 1 << type);
222 /* No longer mark "edge" as being of type "type"?
224 static void clear_type(struct isl_sched_edge *edge, enum isl_edge_type type)
226 ISL_FL_CLR(edge->types, 1 << type);
229 /* Is "edge" marked as a validity edge?
231 static int is_validity(struct isl_sched_edge *edge)
233 return is_type(edge, isl_edge_validity);
236 /* Mark "edge" as a validity edge.
238 static void set_validity(struct isl_sched_edge *edge)
240 set_type(edge, isl_edge_validity);
243 /* Is "edge" marked as a proximity edge?
245 static int is_proximity(struct isl_sched_edge *edge)
247 return is_type(edge, isl_edge_proximity);
250 /* Is "edge" marked as a local edge?
252 static int is_local(struct isl_sched_edge *edge)
254 return is_type(edge, isl_edge_local);
257 /* Mark "edge" as a local edge.
259 static void set_local(struct isl_sched_edge *edge)
261 set_type(edge, isl_edge_local);
264 /* No longer mark "edge" as a local edge.
266 static void clear_local(struct isl_sched_edge *edge)
268 clear_type(edge, isl_edge_local);
271 /* Is "edge" marked as a coincidence edge?
273 static int is_coincidence(struct isl_sched_edge *edge)
275 return is_type(edge, isl_edge_coincidence);
278 /* Is "edge" marked as a condition edge?
280 static int is_condition(struct isl_sched_edge *edge)
282 return is_type(edge, isl_edge_condition);
285 /* Is "edge" marked as a conditional validity edge?
287 static int is_conditional_validity(struct isl_sched_edge *edge)
289 return is_type(edge, isl_edge_conditional_validity);
292 /* Is "edge" of a type that can appear multiple times between
293 * the same pair of nodes?
295 * Condition edges and conditional validity edges may have tagged
296 * dependence relations, in which case an edge is added for each
297 * pair of tags.
299 static int is_multi_edge_type(struct isl_sched_edge *edge)
301 return is_condition(edge) || is_conditional_validity(edge);
304 /* Internal information about the dependence graph used during
305 * the construction of the schedule.
307 * intra_hmap is a cache, mapping dependence relations to their dual,
308 * for dependences from a node to itself, possibly without
309 * coefficients for the parameters
310 * intra_hmap_param is a cache, mapping dependence relations to their dual,
311 * for dependences from a node to itself, including coefficients
312 * for the parameters
313 * inter_hmap is a cache, mapping dependence relations to their dual,
314 * for dependences between distinct nodes
315 * if compression is involved then the key for these maps
316 * is the original, uncompressed dependence relation, while
317 * the value is the dual of the compressed dependence relation.
319 * n is the number of nodes
320 * node is the list of nodes
321 * maxvar is the maximal number of variables over all nodes
322 * max_row is the allocated number of rows in the schedule
323 * n_row is the current (maximal) number of linearly independent
324 * rows in the node schedules
325 * n_total_row is the current number of rows in the node schedules
326 * band_start is the starting row in the node schedules of the current band
327 * root is set to the original dependence graph from which this graph
328 * is derived through splitting. If this graph is not the result of
329 * splitting, then the root field points to the graph itself.
331 * sorted contains a list of node indices sorted according to the
332 * SCC to which a node belongs
334 * n_edge is the number of edges
335 * edge is the list of edges
336 * max_edge contains the maximal number of edges of each type;
337 * in particular, it contains the number of edges in the inital graph.
338 * edge_table contains pointers into the edge array, hashed on the source
339 * and sink spaces; there is one such table for each type;
340 * a given edge may be referenced from more than one table
341 * if the corresponding relation appears in more than one of the
342 * sets of dependences; however, for each type there is only
343 * a single edge between a given pair of source and sink space
344 * in the entire graph
346 * node_table contains pointers into the node array, hashed on the space tuples
348 * region contains a list of variable sequences that should be non-trivial
350 * lp contains the (I)LP problem used to obtain new schedule rows
352 * src_scc and dst_scc are the source and sink SCCs of an edge with
353 * conflicting constraints
355 * scc represents the number of components
356 * weak is set if the components are weakly connected
358 * max_weight is used during clustering and represents the maximal
359 * weight of the relevant proximity edges.
361 struct isl_sched_graph {
362 isl_map_to_basic_set *intra_hmap;
363 isl_map_to_basic_set *intra_hmap_param;
364 isl_map_to_basic_set *inter_hmap;
366 struct isl_sched_node *node;
367 int n;
368 int maxvar;
369 int max_row;
370 int n_row;
372 int *sorted;
374 int n_total_row;
375 int band_start;
377 struct isl_sched_graph *root;
379 struct isl_sched_edge *edge;
380 int n_edge;
381 int max_edge[isl_edge_last + 1];
382 struct isl_hash_table *edge_table[isl_edge_last + 1];
384 struct isl_hash_table *node_table;
385 struct isl_trivial_region *region;
387 isl_basic_set *lp;
389 int src_scc;
390 int dst_scc;
392 int scc;
393 int weak;
395 int max_weight;
398 /* Initialize node_table based on the list of nodes.
400 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
402 int i;
404 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
405 if (!graph->node_table)
406 return -1;
408 for (i = 0; i < graph->n; ++i) {
409 struct isl_hash_table_entry *entry;
410 uint32_t hash;
412 hash = isl_space_get_tuple_hash(graph->node[i].space);
413 entry = isl_hash_table_find(ctx, graph->node_table, hash,
414 &node_has_tuples,
415 graph->node[i].space, 1);
416 if (!entry)
417 return -1;
418 entry->data = &graph->node[i];
421 return 0;
424 /* Return a pointer to the node that lives within the given space,
425 * an invalid node if there is no such node, or NULL in case of error.
427 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
428 struct isl_sched_graph *graph, __isl_keep isl_space *space)
430 struct isl_hash_table_entry *entry;
431 uint32_t hash;
433 if (!space)
434 return NULL;
436 hash = isl_space_get_tuple_hash(space);
437 entry = isl_hash_table_find(ctx, graph->node_table, hash,
438 &node_has_tuples, space, 0);
440 return entry ? entry->data : graph->node + graph->n;
443 /* Is "node" a node in "graph"?
445 static int is_node(struct isl_sched_graph *graph,
446 struct isl_sched_node *node)
448 return node && node >= &graph->node[0] && node < &graph->node[graph->n];
451 static int edge_has_src_and_dst(const void *entry, const void *val)
453 const struct isl_sched_edge *edge = entry;
454 const struct isl_sched_edge *temp = val;
456 return edge->src == temp->src && edge->dst == temp->dst;
459 /* Add the given edge to graph->edge_table[type].
461 static isl_stat graph_edge_table_add(isl_ctx *ctx,
462 struct isl_sched_graph *graph, enum isl_edge_type type,
463 struct isl_sched_edge *edge)
465 struct isl_hash_table_entry *entry;
466 uint32_t hash;
468 hash = isl_hash_init();
469 hash = isl_hash_builtin(hash, edge->src);
470 hash = isl_hash_builtin(hash, edge->dst);
471 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
472 &edge_has_src_and_dst, edge, 1);
473 if (!entry)
474 return isl_stat_error;
475 entry->data = edge;
477 return isl_stat_ok;
480 /* Add "edge" to all relevant edge tables.
481 * That is, for every type of the edge, add it to the corresponding table.
483 static isl_stat graph_edge_tables_add(isl_ctx *ctx,
484 struct isl_sched_graph *graph, struct isl_sched_edge *edge)
486 enum isl_edge_type t;
488 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
489 if (!is_type(edge, t))
490 continue;
491 if (graph_edge_table_add(ctx, graph, t, edge) < 0)
492 return isl_stat_error;
495 return isl_stat_ok;
498 /* Allocate the edge_tables based on the maximal number of edges of
499 * each type.
501 static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
503 int i;
505 for (i = 0; i <= isl_edge_last; ++i) {
506 graph->edge_table[i] = isl_hash_table_alloc(ctx,
507 graph->max_edge[i]);
508 if (!graph->edge_table[i])
509 return -1;
512 return 0;
515 /* If graph->edge_table[type] contains an edge from the given source
516 * to the given destination, then return the hash table entry of this edge.
517 * Otherwise, return NULL.
519 static struct isl_hash_table_entry *graph_find_edge_entry(
520 struct isl_sched_graph *graph,
521 enum isl_edge_type type,
522 struct isl_sched_node *src, struct isl_sched_node *dst)
524 isl_ctx *ctx = isl_space_get_ctx(src->space);
525 uint32_t hash;
526 struct isl_sched_edge temp = { .src = src, .dst = dst };
528 hash = isl_hash_init();
529 hash = isl_hash_builtin(hash, temp.src);
530 hash = isl_hash_builtin(hash, temp.dst);
531 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
532 &edge_has_src_and_dst, &temp, 0);
536 /* If graph->edge_table[type] contains an edge from the given source
537 * to the given destination, then return this edge.
538 * Otherwise, return NULL.
540 static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
541 enum isl_edge_type type,
542 struct isl_sched_node *src, struct isl_sched_node *dst)
544 struct isl_hash_table_entry *entry;
546 entry = graph_find_edge_entry(graph, type, src, dst);
547 if (!entry)
548 return NULL;
550 return entry->data;
553 /* Check whether the dependence graph has an edge of the given type
554 * between the given two nodes.
556 static isl_bool graph_has_edge(struct isl_sched_graph *graph,
557 enum isl_edge_type type,
558 struct isl_sched_node *src, struct isl_sched_node *dst)
560 struct isl_sched_edge *edge;
561 isl_bool empty;
563 edge = graph_find_edge(graph, type, src, dst);
564 if (!edge)
565 return isl_bool_false;
567 empty = isl_map_plain_is_empty(edge->map);
568 if (empty < 0)
569 return isl_bool_error;
571 return !empty;
574 /* Look for any edge with the same src, dst and map fields as "model".
576 * Return the matching edge if one can be found.
577 * Return "model" if no matching edge is found.
578 * Return NULL on error.
580 static struct isl_sched_edge *graph_find_matching_edge(
581 struct isl_sched_graph *graph, struct isl_sched_edge *model)
583 enum isl_edge_type i;
584 struct isl_sched_edge *edge;
586 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
587 int is_equal;
589 edge = graph_find_edge(graph, i, model->src, model->dst);
590 if (!edge)
591 continue;
592 is_equal = isl_map_plain_is_equal(model->map, edge->map);
593 if (is_equal < 0)
594 return NULL;
595 if (is_equal)
596 return edge;
599 return model;
602 /* Remove the given edge from all the edge_tables that refer to it.
604 static void graph_remove_edge(struct isl_sched_graph *graph,
605 struct isl_sched_edge *edge)
607 isl_ctx *ctx = isl_map_get_ctx(edge->map);
608 enum isl_edge_type i;
610 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
611 struct isl_hash_table_entry *entry;
613 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
614 if (!entry)
615 continue;
616 if (entry->data != edge)
617 continue;
618 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
622 /* Check whether the dependence graph has any edge
623 * between the given two nodes.
625 static isl_bool graph_has_any_edge(struct isl_sched_graph *graph,
626 struct isl_sched_node *src, struct isl_sched_node *dst)
628 enum isl_edge_type i;
629 isl_bool r;
631 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
632 r = graph_has_edge(graph, i, src, dst);
633 if (r < 0 || r)
634 return r;
637 return r;
640 /* Check whether the dependence graph has a validity edge
641 * between the given two nodes.
643 * Conditional validity edges are essentially validity edges that
644 * can be ignored if the corresponding condition edges are iteration private.
645 * Here, we are only checking for the presence of validity
646 * edges, so we need to consider the conditional validity edges too.
647 * In particular, this function is used during the detection
648 * of strongly connected components and we cannot ignore
649 * conditional validity edges during this detection.
651 static isl_bool graph_has_validity_edge(struct isl_sched_graph *graph,
652 struct isl_sched_node *src, struct isl_sched_node *dst)
654 isl_bool r;
656 r = graph_has_edge(graph, isl_edge_validity, src, dst);
657 if (r < 0 || r)
658 return r;
660 return graph_has_edge(graph, isl_edge_conditional_validity, src, dst);
663 /* Perform all the required memory allocations for a schedule graph "graph"
664 * with "n_node" nodes and "n_edge" edge and initialize the corresponding
665 * fields.
667 static isl_stat graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
668 int n_node, int n_edge)
670 int i;
672 graph->n = n_node;
673 graph->n_edge = n_edge;
674 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
675 graph->sorted = isl_calloc_array(ctx, int, graph->n);
676 graph->region = isl_alloc_array(ctx,
677 struct isl_trivial_region, graph->n);
678 graph->edge = isl_calloc_array(ctx,
679 struct isl_sched_edge, graph->n_edge);
681 graph->intra_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
682 graph->intra_hmap_param = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
683 graph->inter_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
685 if (!graph->node || !graph->region || (graph->n_edge && !graph->edge) ||
686 !graph->sorted)
687 return isl_stat_error;
689 for(i = 0; i < graph->n; ++i)
690 graph->sorted[i] = i;
692 return isl_stat_ok;
695 /* Free the memory associated to node "node" in "graph".
696 * The "coincident" field is shared by nodes in a graph and its subgraph.
697 * It therefore only needs to be freed for the original dependence graph,
698 * i.e., one that is not the result of splitting.
700 static void clear_node(struct isl_sched_graph *graph,
701 struct isl_sched_node *node)
703 isl_space_free(node->space);
704 isl_set_free(node->hull);
705 isl_multi_aff_free(node->compress);
706 isl_multi_aff_free(node->decompress);
707 isl_mat_free(node->sched);
708 isl_map_free(node->sched_map);
709 isl_mat_free(node->indep);
710 isl_mat_free(node->vmap);
711 if (graph->root == graph)
712 free(node->coincident);
713 isl_multi_val_free(node->sizes);
714 isl_basic_set_free(node->bounds);
715 isl_vec_free(node->max);
718 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
720 int i;
722 isl_map_to_basic_set_free(graph->intra_hmap);
723 isl_map_to_basic_set_free(graph->intra_hmap_param);
724 isl_map_to_basic_set_free(graph->inter_hmap);
726 if (graph->node)
727 for (i = 0; i < graph->n; ++i)
728 clear_node(graph, &graph->node[i]);
729 free(graph->node);
730 free(graph->sorted);
731 if (graph->edge)
732 for (i = 0; i < graph->n_edge; ++i) {
733 isl_map_free(graph->edge[i].map);
734 isl_union_map_free(graph->edge[i].tagged_condition);
735 isl_union_map_free(graph->edge[i].tagged_validity);
737 free(graph->edge);
738 free(graph->region);
739 for (i = 0; i <= isl_edge_last; ++i)
740 isl_hash_table_free(ctx, graph->edge_table[i]);
741 isl_hash_table_free(ctx, graph->node_table);
742 isl_basic_set_free(graph->lp);
745 /* For each "set" on which this function is called, increment
746 * graph->n by one and update graph->maxvar.
748 static isl_stat init_n_maxvar(__isl_take isl_set *set, void *user)
750 struct isl_sched_graph *graph = user;
751 int nvar = isl_set_dim(set, isl_dim_set);
753 graph->n++;
754 if (nvar > graph->maxvar)
755 graph->maxvar = nvar;
757 isl_set_free(set);
759 return isl_stat_ok;
762 /* Compute the number of rows that should be allocated for the schedule.
763 * In particular, we need one row for each variable or one row
764 * for each basic map in the dependences.
765 * Note that it is practically impossible to exhaust both
766 * the number of dependences and the number of variables.
768 static isl_stat compute_max_row(struct isl_sched_graph *graph,
769 __isl_keep isl_schedule_constraints *sc)
771 int n_edge;
772 isl_stat r;
773 isl_union_set *domain;
775 graph->n = 0;
776 graph->maxvar = 0;
777 domain = isl_schedule_constraints_get_domain(sc);
778 r = isl_union_set_foreach_set(domain, &init_n_maxvar, graph);
779 isl_union_set_free(domain);
780 if (r < 0)
781 return isl_stat_error;
782 n_edge = isl_schedule_constraints_n_basic_map(sc);
783 if (n_edge < 0)
784 return isl_stat_error;
785 graph->max_row = n_edge + graph->maxvar;
787 return isl_stat_ok;
790 /* Does "bset" have any defining equalities for its set variables?
792 static isl_bool has_any_defining_equality(__isl_keep isl_basic_set *bset)
794 int i, n;
796 if (!bset)
797 return isl_bool_error;
799 n = isl_basic_set_dim(bset, isl_dim_set);
800 for (i = 0; i < n; ++i) {
801 isl_bool has;
803 has = isl_basic_set_has_defining_equality(bset, isl_dim_set, i,
804 NULL);
805 if (has < 0 || has)
806 return has;
809 return isl_bool_false;
812 /* Set the entries of node->max to the value of the schedule_max_coefficient
813 * option, if set.
815 static isl_stat set_max_coefficient(isl_ctx *ctx, struct isl_sched_node *node)
817 int max;
819 max = isl_options_get_schedule_max_coefficient(ctx);
820 if (max == -1)
821 return isl_stat_ok;
823 node->max = isl_vec_alloc(ctx, node->nvar);
824 node->max = isl_vec_set_si(node->max, max);
825 if (!node->max)
826 return isl_stat_error;
828 return isl_stat_ok;
831 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
832 * option (if set) and half of the minimum of the sizes in the other
833 * dimensions. Round up when computing the half such that
834 * if the minimum of the sizes is one, half of the size is taken to be one
835 * rather than zero.
836 * If the global minimum is unbounded (i.e., if both
837 * the schedule_max_coefficient is not set and the sizes in the other
838 * dimensions are unbounded), then store a negative value.
839 * If the schedule coefficient is close to the size of the instance set
840 * in another dimension, then the schedule may represent a loop
841 * coalescing transformation (especially if the coefficient
842 * in that other dimension is one). Forcing the coefficient to be
843 * smaller than or equal to half the minimal size should avoid this
844 * situation.
846 static isl_stat compute_max_coefficient(isl_ctx *ctx,
847 struct isl_sched_node *node)
849 int max;
850 int i, j;
851 isl_vec *v;
853 max = isl_options_get_schedule_max_coefficient(ctx);
854 v = isl_vec_alloc(ctx, node->nvar);
855 if (!v)
856 return isl_stat_error;
858 for (i = 0; i < node->nvar; ++i) {
859 isl_int_set_si(v->el[i], max);
860 isl_int_mul_si(v->el[i], v->el[i], 2);
863 for (i = 0; i < node->nvar; ++i) {
864 isl_val *size;
866 size = isl_multi_val_get_val(node->sizes, i);
867 if (!size)
868 goto error;
869 if (!isl_val_is_int(size)) {
870 isl_val_free(size);
871 continue;
873 for (j = 0; j < node->nvar; ++j) {
874 if (j == i)
875 continue;
876 if (isl_int_is_neg(v->el[j]) ||
877 isl_int_gt(v->el[j], size->n))
878 isl_int_set(v->el[j], size->n);
880 isl_val_free(size);
883 for (i = 0; i < node->nvar; ++i)
884 isl_int_cdiv_q_ui(v->el[i], v->el[i], 2);
886 node->max = v;
887 return isl_stat_ok;
888 error:
889 isl_vec_free(v);
890 return isl_stat_error;
893 /* Compute and return the size of "set" in dimension "dim".
894 * The size is taken to be the difference in values for that variable
895 * for fixed values of the other variables.
896 * This assumes that "set" is convex.
897 * In particular, the variable is first isolated from the other variables
898 * in the range of a map
900 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
902 * and then duplicated
904 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
906 * The shared variables are then projected out and the maximal value
907 * of i_dim' - i_dim is computed.
909 static __isl_give isl_val *compute_size(__isl_take isl_set *set, int dim)
911 isl_map *map;
912 isl_local_space *ls;
913 isl_aff *obj;
914 isl_val *v;
916 map = isl_set_project_onto_map(set, isl_dim_set, dim, 1);
917 map = isl_map_project_out(map, isl_dim_in, dim, 1);
918 map = isl_map_range_product(map, isl_map_copy(map));
919 map = isl_set_unwrap(isl_map_range(map));
920 set = isl_map_deltas(map);
921 ls = isl_local_space_from_space(isl_set_get_space(set));
922 obj = isl_aff_var_on_domain(ls, isl_dim_set, 0);
923 v = isl_set_max_val(set, obj);
924 isl_aff_free(obj);
925 isl_set_free(set);
927 return v;
930 /* Compute the size of the instance set "set" of "node", after compression,
931 * as well as bounds on the corresponding coefficients, if needed.
933 * The sizes are needed when the schedule_treat_coalescing option is set.
934 * The bounds are needed when the schedule_treat_coalescing option or
935 * the schedule_max_coefficient option is set.
937 * If the schedule_treat_coalescing option is not set, then at most
938 * the bounds need to be set and this is done in set_max_coefficient.
939 * Otherwise, compress the domain if needed, compute the size
940 * in each direction and store the results in node->size.
941 * If the domain is not convex, then the sizes are computed
942 * on a convex superset in order to avoid picking up sizes
943 * that are valid for the individual disjuncts, but not for
944 * the domain as a whole.
945 * Finally, set the bounds on the coefficients based on the sizes
946 * and the schedule_max_coefficient option in compute_max_coefficient.
948 static isl_stat compute_sizes_and_max(isl_ctx *ctx, struct isl_sched_node *node,
949 __isl_take isl_set *set)
951 int j, n;
952 isl_multi_val *mv;
954 if (!isl_options_get_schedule_treat_coalescing(ctx)) {
955 isl_set_free(set);
956 return set_max_coefficient(ctx, node);
959 if (node->compressed)
960 set = isl_set_preimage_multi_aff(set,
961 isl_multi_aff_copy(node->decompress));
962 set = isl_set_from_basic_set(isl_set_simple_hull(set));
963 mv = isl_multi_val_zero(isl_set_get_space(set));
964 n = isl_set_dim(set, isl_dim_set);
965 for (j = 0; j < n; ++j) {
966 isl_val *v;
968 v = compute_size(isl_set_copy(set), j);
969 mv = isl_multi_val_set_val(mv, j, v);
971 node->sizes = mv;
972 isl_set_free(set);
973 if (!node->sizes)
974 return isl_stat_error;
975 return compute_max_coefficient(ctx, node);
978 /* Add a new node to the graph representing the given instance set.
979 * "nvar" is the (possibly compressed) number of variables and
980 * may be smaller than then number of set variables in "set"
981 * if "compressed" is set.
982 * If "compressed" is set, then "hull" represents the constraints
983 * that were used to derive the compression, while "compress" and
984 * "decompress" map the original space to the compressed space and
985 * vice versa.
986 * If "compressed" is not set, then "hull", "compress" and "decompress"
987 * should be NULL.
989 * Compute the size of the instance set and bounds on the coefficients,
990 * if needed.
992 static isl_stat add_node(struct isl_sched_graph *graph,
993 __isl_take isl_set *set, int nvar, int compressed,
994 __isl_take isl_set *hull, __isl_take isl_multi_aff *compress,
995 __isl_take isl_multi_aff *decompress)
997 int nparam;
998 isl_ctx *ctx;
999 isl_mat *sched;
1000 isl_space *space;
1001 int *coincident;
1002 struct isl_sched_node *node;
1004 if (!set)
1005 goto error;
1007 ctx = isl_set_get_ctx(set);
1008 nparam = isl_set_dim(set, isl_dim_param);
1009 if (!ctx->opt->schedule_parametric)
1010 nparam = 0;
1011 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
1012 node = &graph->node[graph->n];
1013 graph->n++;
1014 space = isl_set_get_space(set);
1015 node->space = space;
1016 node->nvar = nvar;
1017 node->nparam = nparam;
1018 node->sched = sched;
1019 node->sched_map = NULL;
1020 coincident = isl_calloc_array(ctx, int, graph->max_row);
1021 node->coincident = coincident;
1022 node->compressed = compressed;
1023 node->hull = hull;
1024 node->compress = compress;
1025 node->decompress = decompress;
1026 if (compute_sizes_and_max(ctx, node, set) < 0)
1027 return isl_stat_error;
1029 if (!space || !sched || (graph->max_row && !coincident))
1030 return isl_stat_error;
1031 if (compressed && (!hull || !compress || !decompress))
1032 return isl_stat_error;
1034 return isl_stat_ok;
1035 error:
1036 isl_set_free(set);
1037 isl_set_free(hull);
1038 isl_multi_aff_free(compress);
1039 isl_multi_aff_free(decompress);
1040 return isl_stat_error;
1043 /* Construct an identifier for node "node", which will represent "set".
1044 * The name of the identifier is either "compressed" or
1045 * "compressed_<name>", with <name> the name of the space of "set".
1046 * The user pointer of the identifier points to "node".
1048 static __isl_give isl_id *construct_compressed_id(__isl_keep isl_set *set,
1049 struct isl_sched_node *node)
1051 isl_bool has_name;
1052 isl_ctx *ctx;
1053 isl_id *id;
1054 isl_printer *p;
1055 const char *name;
1056 char *id_name;
1058 has_name = isl_set_has_tuple_name(set);
1059 if (has_name < 0)
1060 return NULL;
1062 ctx = isl_set_get_ctx(set);
1063 if (!has_name)
1064 return isl_id_alloc(ctx, "compressed", node);
1066 p = isl_printer_to_str(ctx);
1067 name = isl_set_get_tuple_name(set);
1068 p = isl_printer_print_str(p, "compressed_");
1069 p = isl_printer_print_str(p, name);
1070 id_name = isl_printer_get_str(p);
1071 isl_printer_free(p);
1073 id = isl_id_alloc(ctx, id_name, node);
1074 free(id_name);
1076 return id;
1079 /* Add a new node to the graph representing the given set.
1081 * If any of the set variables is defined by an equality, then
1082 * we perform variable compression such that we can perform
1083 * the scheduling on the compressed domain.
1084 * In this case, an identifier is used that references the new node
1085 * such that each compressed space is unique and
1086 * such that the node can be recovered from the compressed space.
1088 static isl_stat extract_node(__isl_take isl_set *set, void *user)
1090 int nvar;
1091 isl_bool has_equality;
1092 isl_id *id;
1093 isl_basic_set *hull;
1094 isl_set *hull_set;
1095 isl_morph *morph;
1096 isl_multi_aff *compress, *decompress;
1097 struct isl_sched_graph *graph = user;
1099 hull = isl_set_affine_hull(isl_set_copy(set));
1100 hull = isl_basic_set_remove_divs(hull);
1101 nvar = isl_set_dim(set, isl_dim_set);
1102 has_equality = has_any_defining_equality(hull);
1104 if (has_equality < 0)
1105 goto error;
1106 if (!has_equality) {
1107 isl_basic_set_free(hull);
1108 return add_node(graph, set, nvar, 0, NULL, NULL, NULL);
1111 id = construct_compressed_id(set, &graph->node[graph->n]);
1112 morph = isl_basic_set_variable_compression_with_id(hull,
1113 isl_dim_set, id);
1114 isl_id_free(id);
1115 nvar = isl_morph_ran_dim(morph, isl_dim_set);
1116 compress = isl_morph_get_var_multi_aff(morph);
1117 morph = isl_morph_inverse(morph);
1118 decompress = isl_morph_get_var_multi_aff(morph);
1119 isl_morph_free(morph);
1121 hull_set = isl_set_from_basic_set(hull);
1122 return add_node(graph, set, nvar, 1, hull_set, compress, decompress);
1123 error:
1124 isl_basic_set_free(hull);
1125 isl_set_free(set);
1126 return isl_stat_error;
1129 struct isl_extract_edge_data {
1130 enum isl_edge_type type;
1131 struct isl_sched_graph *graph;
1134 /* Merge edge2 into edge1, freeing the contents of edge2.
1135 * Return 0 on success and -1 on failure.
1137 * edge1 and edge2 are assumed to have the same value for the map field.
1139 static int merge_edge(struct isl_sched_edge *edge1,
1140 struct isl_sched_edge *edge2)
1142 edge1->types |= edge2->types;
1143 isl_map_free(edge2->map);
1145 if (is_condition(edge2)) {
1146 if (!edge1->tagged_condition)
1147 edge1->tagged_condition = edge2->tagged_condition;
1148 else
1149 edge1->tagged_condition =
1150 isl_union_map_union(edge1->tagged_condition,
1151 edge2->tagged_condition);
1154 if (is_conditional_validity(edge2)) {
1155 if (!edge1->tagged_validity)
1156 edge1->tagged_validity = edge2->tagged_validity;
1157 else
1158 edge1->tagged_validity =
1159 isl_union_map_union(edge1->tagged_validity,
1160 edge2->tagged_validity);
1163 if (is_condition(edge2) && !edge1->tagged_condition)
1164 return -1;
1165 if (is_conditional_validity(edge2) && !edge1->tagged_validity)
1166 return -1;
1168 return 0;
1171 /* Insert dummy tags in domain and range of "map".
1173 * In particular, if "map" is of the form
1175 * A -> B
1177 * then return
1179 * [A -> dummy_tag] -> [B -> dummy_tag]
1181 * where the dummy_tags are identical and equal to any dummy tags
1182 * introduced by any other call to this function.
1184 static __isl_give isl_map *insert_dummy_tags(__isl_take isl_map *map)
1186 static char dummy;
1187 isl_ctx *ctx;
1188 isl_id *id;
1189 isl_space *space;
1190 isl_set *domain, *range;
1192 ctx = isl_map_get_ctx(map);
1194 id = isl_id_alloc(ctx, NULL, &dummy);
1195 space = isl_space_params(isl_map_get_space(map));
1196 space = isl_space_set_from_params(space);
1197 space = isl_space_set_tuple_id(space, isl_dim_set, id);
1198 space = isl_space_map_from_set(space);
1200 domain = isl_map_wrap(map);
1201 range = isl_map_wrap(isl_map_universe(space));
1202 map = isl_map_from_domain_and_range(domain, range);
1203 map = isl_map_zip(map);
1205 return map;
1208 /* Given that at least one of "src" or "dst" is compressed, return
1209 * a map between the spaces of these nodes restricted to the affine
1210 * hull that was used in the compression.
1212 static __isl_give isl_map *extract_hull(struct isl_sched_node *src,
1213 struct isl_sched_node *dst)
1215 isl_set *dom, *ran;
1217 if (src->compressed)
1218 dom = isl_set_copy(src->hull);
1219 else
1220 dom = isl_set_universe(isl_space_copy(src->space));
1221 if (dst->compressed)
1222 ran = isl_set_copy(dst->hull);
1223 else
1224 ran = isl_set_universe(isl_space_copy(dst->space));
1226 return isl_map_from_domain_and_range(dom, ran);
1229 /* Intersect the domains of the nested relations in domain and range
1230 * of "tagged" with "map".
1232 static __isl_give isl_map *map_intersect_domains(__isl_take isl_map *tagged,
1233 __isl_keep isl_map *map)
1235 isl_set *set;
1237 tagged = isl_map_zip(tagged);
1238 set = isl_map_wrap(isl_map_copy(map));
1239 tagged = isl_map_intersect_domain(tagged, set);
1240 tagged = isl_map_zip(tagged);
1241 return tagged;
1244 /* Return a pointer to the node that lives in the domain space of "map",
1245 * an invalid node if there is no such node, or NULL in case of error.
1247 static struct isl_sched_node *find_domain_node(isl_ctx *ctx,
1248 struct isl_sched_graph *graph, __isl_keep isl_map *map)
1250 struct isl_sched_node *node;
1251 isl_space *space;
1253 space = isl_space_domain(isl_map_get_space(map));
1254 node = graph_find_node(ctx, graph, space);
1255 isl_space_free(space);
1257 return node;
1260 /* Return a pointer to the node that lives in the range space of "map",
1261 * an invalid node if there is no such node, or NULL in case of error.
1263 static struct isl_sched_node *find_range_node(isl_ctx *ctx,
1264 struct isl_sched_graph *graph, __isl_keep isl_map *map)
1266 struct isl_sched_node *node;
1267 isl_space *space;
1269 space = isl_space_range(isl_map_get_space(map));
1270 node = graph_find_node(ctx, graph, space);
1271 isl_space_free(space);
1273 return node;
1276 /* Refrain from adding a new edge based on "map".
1277 * Instead, just free the map.
1278 * "tagged" is either a copy of "map" with additional tags or NULL.
1280 static isl_stat skip_edge(__isl_take isl_map *map, __isl_take isl_map *tagged)
1282 isl_map_free(map);
1283 isl_map_free(tagged);
1285 return isl_stat_ok;
1288 /* Add a new edge to the graph based on the given map
1289 * and add it to data->graph->edge_table[data->type].
1290 * If a dependence relation of a given type happens to be identical
1291 * to one of the dependence relations of a type that was added before,
1292 * then we don't create a new edge, but instead mark the original edge
1293 * as also representing a dependence of the current type.
1295 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1296 * may be specified as "tagged" dependence relations. That is, "map"
1297 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1298 * the dependence on iterations and a and b are tags.
1299 * edge->map is set to the relation containing the elements i -> j,
1300 * while edge->tagged_condition and edge->tagged_validity contain
1301 * the union of all the "map" relations
1302 * for which extract_edge is called that result in the same edge->map.
1304 * If the source or the destination node is compressed, then
1305 * intersect both "map" and "tagged" with the constraints that
1306 * were used to construct the compression.
1307 * This ensures that there are no schedule constraints defined
1308 * outside of these domains, while the scheduler no longer has
1309 * any control over those outside parts.
1311 static isl_stat extract_edge(__isl_take isl_map *map, void *user)
1313 isl_bool empty;
1314 isl_ctx *ctx = isl_map_get_ctx(map);
1315 struct isl_extract_edge_data *data = user;
1316 struct isl_sched_graph *graph = data->graph;
1317 struct isl_sched_node *src, *dst;
1318 struct isl_sched_edge *edge;
1319 isl_map *tagged = NULL;
1321 if (data->type == isl_edge_condition ||
1322 data->type == isl_edge_conditional_validity) {
1323 if (isl_map_can_zip(map)) {
1324 tagged = isl_map_copy(map);
1325 map = isl_set_unwrap(isl_map_domain(isl_map_zip(map)));
1326 } else {
1327 tagged = insert_dummy_tags(isl_map_copy(map));
1331 src = find_domain_node(ctx, graph, map);
1332 dst = find_range_node(ctx, graph, map);
1334 if (!src || !dst)
1335 goto error;
1336 if (!is_node(graph, src) || !is_node(graph, dst))
1337 return skip_edge(map, tagged);
1339 if (src->compressed || dst->compressed) {
1340 isl_map *hull;
1341 hull = extract_hull(src, dst);
1342 if (tagged)
1343 tagged = map_intersect_domains(tagged, hull);
1344 map = isl_map_intersect(map, hull);
1347 empty = isl_map_plain_is_empty(map);
1348 if (empty < 0)
1349 goto error;
1350 if (empty)
1351 return skip_edge(map, tagged);
1353 graph->edge[graph->n_edge].src = src;
1354 graph->edge[graph->n_edge].dst = dst;
1355 graph->edge[graph->n_edge].map = map;
1356 graph->edge[graph->n_edge].types = 0;
1357 graph->edge[graph->n_edge].tagged_condition = NULL;
1358 graph->edge[graph->n_edge].tagged_validity = NULL;
1359 set_type(&graph->edge[graph->n_edge], data->type);
1360 if (data->type == isl_edge_condition)
1361 graph->edge[graph->n_edge].tagged_condition =
1362 isl_union_map_from_map(tagged);
1363 if (data->type == isl_edge_conditional_validity)
1364 graph->edge[graph->n_edge].tagged_validity =
1365 isl_union_map_from_map(tagged);
1367 edge = graph_find_matching_edge(graph, &graph->edge[graph->n_edge]);
1368 if (!edge) {
1369 graph->n_edge++;
1370 return isl_stat_error;
1372 if (edge == &graph->edge[graph->n_edge])
1373 return graph_edge_table_add(ctx, graph, data->type,
1374 &graph->edge[graph->n_edge++]);
1376 if (merge_edge(edge, &graph->edge[graph->n_edge]) < 0)
1377 return isl_stat_error;
1379 return graph_edge_table_add(ctx, graph, data->type, edge);
1380 error:
1381 isl_map_free(map);
1382 isl_map_free(tagged);
1383 return isl_stat_error;
1386 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1388 * The context is included in the domain before the nodes of
1389 * the graphs are extracted in order to be able to exploit
1390 * any possible additional equalities.
1391 * Note that this intersection is only performed locally here.
1393 static isl_stat graph_init(struct isl_sched_graph *graph,
1394 __isl_keep isl_schedule_constraints *sc)
1396 isl_ctx *ctx;
1397 isl_union_set *domain;
1398 isl_union_map *c;
1399 struct isl_extract_edge_data data;
1400 enum isl_edge_type i;
1401 isl_stat r;
1403 if (!sc)
1404 return isl_stat_error;
1406 ctx = isl_schedule_constraints_get_ctx(sc);
1408 domain = isl_schedule_constraints_get_domain(sc);
1409 graph->n = isl_union_set_n_set(domain);
1410 isl_union_set_free(domain);
1412 if (graph_alloc(ctx, graph, graph->n,
1413 isl_schedule_constraints_n_map(sc)) < 0)
1414 return isl_stat_error;
1416 if (compute_max_row(graph, sc) < 0)
1417 return isl_stat_error;
1418 graph->root = graph;
1419 graph->n = 0;
1420 domain = isl_schedule_constraints_get_domain(sc);
1421 domain = isl_union_set_intersect_params(domain,
1422 isl_schedule_constraints_get_context(sc));
1423 r = isl_union_set_foreach_set(domain, &extract_node, graph);
1424 isl_union_set_free(domain);
1425 if (r < 0)
1426 return isl_stat_error;
1427 if (graph_init_table(ctx, graph) < 0)
1428 return isl_stat_error;
1429 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
1430 c = isl_schedule_constraints_get(sc, i);
1431 graph->max_edge[i] = isl_union_map_n_map(c);
1432 isl_union_map_free(c);
1433 if (!c)
1434 return isl_stat_error;
1436 if (graph_init_edge_tables(ctx, graph) < 0)
1437 return isl_stat_error;
1438 graph->n_edge = 0;
1439 data.graph = graph;
1440 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
1441 isl_stat r;
1443 data.type = i;
1444 c = isl_schedule_constraints_get(sc, i);
1445 r = isl_union_map_foreach_map(c, &extract_edge, &data);
1446 isl_union_map_free(c);
1447 if (r < 0)
1448 return isl_stat_error;
1451 return isl_stat_ok;
1454 /* Check whether there is any dependence from node[j] to node[i]
1455 * or from node[i] to node[j].
1457 static isl_bool node_follows_weak(int i, int j, void *user)
1459 isl_bool f;
1460 struct isl_sched_graph *graph = user;
1462 f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]);
1463 if (f < 0 || f)
1464 return f;
1465 return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]);
1468 /* Check whether there is a (conditional) validity dependence from node[j]
1469 * to node[i], forcing node[i] to follow node[j].
1471 static isl_bool node_follows_strong(int i, int j, void *user)
1473 struct isl_sched_graph *graph = user;
1475 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
1478 /* Use Tarjan's algorithm for computing the strongly connected components
1479 * in the dependence graph only considering those edges defined by "follows".
1481 static isl_stat detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph,
1482 isl_bool (*follows)(int i, int j, void *user))
1484 int i, n;
1485 struct isl_tarjan_graph *g = NULL;
1487 g = isl_tarjan_graph_init(ctx, graph->n, follows, graph);
1488 if (!g)
1489 return isl_stat_error;
1491 graph->scc = 0;
1492 i = 0;
1493 n = graph->n;
1494 while (n) {
1495 while (g->order[i] != -1) {
1496 graph->node[g->order[i]].scc = graph->scc;
1497 --n;
1498 ++i;
1500 ++i;
1501 graph->scc++;
1504 isl_tarjan_graph_free(g);
1506 return isl_stat_ok;
1509 /* Apply Tarjan's algorithm to detect the strongly connected components
1510 * in the dependence graph.
1511 * Only consider the (conditional) validity dependences and clear "weak".
1513 static isl_stat detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1515 graph->weak = 0;
1516 return detect_ccs(ctx, graph, &node_follows_strong);
1519 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1520 * in the dependence graph.
1521 * Consider all dependences and set "weak".
1523 static isl_stat detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1525 graph->weak = 1;
1526 return detect_ccs(ctx, graph, &node_follows_weak);
1529 static int cmp_scc(const void *a, const void *b, void *data)
1531 struct isl_sched_graph *graph = data;
1532 const int *i1 = a;
1533 const int *i2 = b;
1535 return graph->node[*i1].scc - graph->node[*i2].scc;
1538 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1540 static int sort_sccs(struct isl_sched_graph *graph)
1542 return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
1545 /* Return a non-parametric set in the compressed space of "node" that is
1546 * bounded by the size in each direction
1548 * { [x] : -S_i <= x_i <= S_i }
1550 * If S_i is infinity in direction i, then there are no constraints
1551 * in that direction.
1553 * Cache the result in node->bounds.
1555 static __isl_give isl_basic_set *get_size_bounds(struct isl_sched_node *node)
1557 isl_space *space;
1558 isl_basic_set *bounds;
1559 int i;
1560 unsigned nparam;
1562 if (node->bounds)
1563 return isl_basic_set_copy(node->bounds);
1565 if (node->compressed)
1566 space = isl_multi_aff_get_domain_space(node->decompress);
1567 else
1568 space = isl_space_copy(node->space);
1569 nparam = isl_space_dim(space, isl_dim_param);
1570 space = isl_space_drop_dims(space, isl_dim_param, 0, nparam);
1571 bounds = isl_basic_set_universe(space);
1573 for (i = 0; i < node->nvar; ++i) {
1574 isl_val *size;
1576 size = isl_multi_val_get_val(node->sizes, i);
1577 if (!size)
1578 return isl_basic_set_free(bounds);
1579 if (!isl_val_is_int(size)) {
1580 isl_val_free(size);
1581 continue;
1583 bounds = isl_basic_set_upper_bound_val(bounds, isl_dim_set, i,
1584 isl_val_copy(size));
1585 bounds = isl_basic_set_lower_bound_val(bounds, isl_dim_set, i,
1586 isl_val_neg(size));
1589 node->bounds = isl_basic_set_copy(bounds);
1590 return bounds;
1593 /* Drop some constraints from "delta" that could be exploited
1594 * to construct loop coalescing schedules.
1595 * In particular, drop those constraint that bound the difference
1596 * to the size of the domain.
1597 * First project out the parameters to improve the effectiveness.
1599 static __isl_give isl_set *drop_coalescing_constraints(
1600 __isl_take isl_set *delta, struct isl_sched_node *node)
1602 unsigned nparam;
1603 isl_basic_set *bounds;
1605 bounds = get_size_bounds(node);
1607 nparam = isl_set_dim(delta, isl_dim_param);
1608 delta = isl_set_project_out(delta, isl_dim_param, 0, nparam);
1609 delta = isl_set_remove_divs(delta);
1610 delta = isl_set_plain_gist_basic_set(delta, bounds);
1611 return delta;
1614 /* Given a dependence relation R from "node" to itself,
1615 * construct the set of coefficients of valid constraints for elements
1616 * in that dependence relation.
1617 * In particular, the result contains tuples of coefficients
1618 * c_0, c_n, c_x such that
1620 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1622 * or, equivalently,
1624 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1626 * We choose here to compute the dual of delta R.
1627 * Alternatively, we could have computed the dual of R, resulting
1628 * in a set of tuples c_0, c_n, c_x, c_y, and then
1629 * plugged in (c_0, c_n, c_x, -c_x).
1631 * If "need_param" is set, then the resulting coefficients effectively
1632 * include coefficients for the parameters c_n. Otherwise, they may
1633 * have been projected out already.
1634 * Since the constraints may be different for these two cases,
1635 * they are stored in separate caches.
1636 * In particular, if no parameter coefficients are required and
1637 * the schedule_treat_coalescing option is set, then the parameters
1638 * are projected out and some constraints that could be exploited
1639 * to construct coalescing schedules are removed before the dual
1640 * is computed.
1642 * If "node" has been compressed, then the dependence relation
1643 * is also compressed before the set of coefficients is computed.
1645 static __isl_give isl_basic_set *intra_coefficients(
1646 struct isl_sched_graph *graph, struct isl_sched_node *node,
1647 __isl_take isl_map *map, int need_param)
1649 isl_ctx *ctx;
1650 isl_set *delta;
1651 isl_map *key;
1652 isl_basic_set *coef;
1653 isl_maybe_isl_basic_set m;
1654 isl_map_to_basic_set **hmap = &graph->intra_hmap;
1655 int treat;
1657 if (!map)
1658 return NULL;
1660 ctx = isl_map_get_ctx(map);
1661 treat = !need_param && isl_options_get_schedule_treat_coalescing(ctx);
1662 if (!treat)
1663 hmap = &graph->intra_hmap_param;
1664 m = isl_map_to_basic_set_try_get(*hmap, map);
1665 if (m.valid < 0 || m.valid) {
1666 isl_map_free(map);
1667 return m.value;
1670 key = isl_map_copy(map);
1671 if (node->compressed) {
1672 map = isl_map_preimage_domain_multi_aff(map,
1673 isl_multi_aff_copy(node->decompress));
1674 map = isl_map_preimage_range_multi_aff(map,
1675 isl_multi_aff_copy(node->decompress));
1677 delta = isl_map_deltas(map);
1678 if (treat)
1679 delta = drop_coalescing_constraints(delta, node);
1680 delta = isl_set_remove_divs(delta);
1681 coef = isl_set_coefficients(delta);
1682 *hmap = isl_map_to_basic_set_set(*hmap, key, isl_basic_set_copy(coef));
1684 return coef;
1687 /* Given a dependence relation R, construct the set of coefficients
1688 * of valid constraints for elements in that dependence relation.
1689 * In particular, the result contains tuples of coefficients
1690 * c_0, c_n, c_x, c_y such that
1692 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1694 * If the source or destination nodes of "edge" have been compressed,
1695 * then the dependence relation is also compressed before
1696 * the set of coefficients is computed.
1698 static __isl_give isl_basic_set *inter_coefficients(
1699 struct isl_sched_graph *graph, struct isl_sched_edge *edge,
1700 __isl_take isl_map *map)
1702 isl_set *set;
1703 isl_map *key;
1704 isl_basic_set *coef;
1705 isl_maybe_isl_basic_set m;
1707 m = isl_map_to_basic_set_try_get(graph->inter_hmap, map);
1708 if (m.valid < 0 || m.valid) {
1709 isl_map_free(map);
1710 return m.value;
1713 key = isl_map_copy(map);
1714 if (edge->src->compressed)
1715 map = isl_map_preimage_domain_multi_aff(map,
1716 isl_multi_aff_copy(edge->src->decompress));
1717 if (edge->dst->compressed)
1718 map = isl_map_preimage_range_multi_aff(map,
1719 isl_multi_aff_copy(edge->dst->decompress));
1720 set = isl_map_wrap(isl_map_remove_divs(map));
1721 coef = isl_set_coefficients(set);
1722 graph->inter_hmap = isl_map_to_basic_set_set(graph->inter_hmap, key,
1723 isl_basic_set_copy(coef));
1725 return coef;
1728 /* Return the position of the coefficients of the variables in
1729 * the coefficients constraints "coef".
1731 * The space of "coef" is of the form
1733 * { coefficients[[cst, params] -> S] }
1735 * Return the position of S.
1737 static int coef_var_offset(__isl_keep isl_basic_set *coef)
1739 int offset;
1740 isl_space *space;
1742 space = isl_space_unwrap(isl_basic_set_get_space(coef));
1743 offset = isl_space_dim(space, isl_dim_in);
1744 isl_space_free(space);
1746 return offset;
1749 /* Return the offset of the coefficient of the constant term of "node"
1750 * within the (I)LP.
1752 * Within each node, the coefficients have the following order:
1753 * - positive and negative parts of c_i_x
1754 * - c_i_n (if parametric)
1755 * - c_i_0
1757 static int node_cst_coef_offset(struct isl_sched_node *node)
1759 return node->start + 2 * node->nvar + node->nparam;
1762 /* Return the offset of the coefficients of the parameters of "node"
1763 * within the (I)LP.
1765 * Within each node, the coefficients have the following order:
1766 * - positive and negative parts of c_i_x
1767 * - c_i_n (if parametric)
1768 * - c_i_0
1770 static int node_par_coef_offset(struct isl_sched_node *node)
1772 return node->start + 2 * node->nvar;
1775 /* Return the offset of the coefficients of the variables of "node"
1776 * within the (I)LP.
1778 * Within each node, the coefficients have the following order:
1779 * - positive and negative parts of c_i_x
1780 * - c_i_n (if parametric)
1781 * - c_i_0
1783 static int node_var_coef_offset(struct isl_sched_node *node)
1785 return node->start;
1788 /* Return the position of the pair of variables encoding
1789 * coefficient "i" of "node".
1791 * The order of these variable pairs is the opposite of
1792 * that of the coefficients, with 2 variables per coefficient.
1794 static int node_var_coef_pos(struct isl_sched_node *node, int i)
1796 return node_var_coef_offset(node) + 2 * (node->nvar - 1 - i);
1799 /* Construct an isl_dim_map for mapping constraints on coefficients
1800 * for "node" to the corresponding positions in graph->lp.
1801 * "offset" is the offset of the coefficients for the variables
1802 * in the input constraints.
1803 * "s" is the sign of the mapping.
1805 * The input constraints are given in terms of the coefficients
1806 * (c_0, c_x) or (c_0, c_n, c_x).
1807 * The mapping produced by this function essentially plugs in
1808 * (0, c_i_x^+ - c_i_x^-) if s = 1 and
1809 * (0, -c_i_x^+ + c_i_x^-) if s = -1 or
1810 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1811 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1812 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1813 * Furthermore, the order of these pairs is the opposite of that
1814 * of the corresponding coefficients.
1816 * The caller can extend the mapping to also map the other coefficients
1817 * (and therefore not plug in 0).
1819 static __isl_give isl_dim_map *intra_dim_map(isl_ctx *ctx,
1820 struct isl_sched_graph *graph, struct isl_sched_node *node,
1821 int offset, int s)
1823 int pos;
1824 unsigned total;
1825 isl_dim_map *dim_map;
1827 if (!node || !graph->lp)
1828 return NULL;
1830 total = isl_basic_set_total_dim(graph->lp);
1831 pos = node_var_coef_pos(node, 0);
1832 dim_map = isl_dim_map_alloc(ctx, total);
1833 isl_dim_map_range(dim_map, pos, -2, offset, 1, node->nvar, -s);
1834 isl_dim_map_range(dim_map, pos + 1, -2, offset, 1, node->nvar, s);
1836 return dim_map;
1839 /* Construct an isl_dim_map for mapping constraints on coefficients
1840 * for "src" (node i) and "dst" (node j) to the corresponding positions
1841 * in graph->lp.
1842 * "offset" is the offset of the coefficients for the variables of "src"
1843 * in the input constraints.
1844 * "s" is the sign of the mapping.
1846 * The input constraints are given in terms of the coefficients
1847 * (c_0, c_n, c_x, c_y).
1848 * The mapping produced by this function essentially plugs in
1849 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1850 * -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-) if s = 1 and
1851 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1852 * c_i_x^+ - c_i_x^-, -(c_j_x^+ - c_j_x^-)) if s = -1.
1853 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1854 * Furthermore, the order of these pairs is the opposite of that
1855 * of the corresponding coefficients.
1857 * The caller can further extend the mapping.
1859 static __isl_give isl_dim_map *inter_dim_map(isl_ctx *ctx,
1860 struct isl_sched_graph *graph, struct isl_sched_node *src,
1861 struct isl_sched_node *dst, int offset, int s)
1863 int pos;
1864 unsigned total;
1865 isl_dim_map *dim_map;
1867 if (!src || !dst || !graph->lp)
1868 return NULL;
1870 total = isl_basic_set_total_dim(graph->lp);
1871 dim_map = isl_dim_map_alloc(ctx, total);
1873 pos = node_cst_coef_offset(dst);
1874 isl_dim_map_range(dim_map, pos, 0, 0, 0, 1, s);
1875 pos = node_par_coef_offset(dst);
1876 isl_dim_map_range(dim_map, pos, 1, 1, 1, dst->nparam, s);
1877 pos = node_var_coef_pos(dst, 0);
1878 isl_dim_map_range(dim_map, pos, -2, offset + src->nvar, 1,
1879 dst->nvar, -s);
1880 isl_dim_map_range(dim_map, pos + 1, -2, offset + src->nvar, 1,
1881 dst->nvar, s);
1883 pos = node_cst_coef_offset(src);
1884 isl_dim_map_range(dim_map, pos, 0, 0, 0, 1, -s);
1885 pos = node_par_coef_offset(src);
1886 isl_dim_map_range(dim_map, pos, 1, 1, 1, src->nparam, -s);
1887 pos = node_var_coef_pos(src, 0);
1888 isl_dim_map_range(dim_map, pos, -2, offset, 1, src->nvar, s);
1889 isl_dim_map_range(dim_map, pos + 1, -2, offset, 1, src->nvar, -s);
1891 return dim_map;
1894 /* Add the constraints from "src" to "dst" using "dim_map",
1895 * after making sure there is enough room in "dst" for the extra constraints.
1897 static __isl_give isl_basic_set *add_constraints_dim_map(
1898 __isl_take isl_basic_set *dst, __isl_take isl_basic_set *src,
1899 __isl_take isl_dim_map *dim_map)
1901 int n_eq, n_ineq;
1903 n_eq = isl_basic_set_n_equality(src);
1904 n_ineq = isl_basic_set_n_inequality(src);
1905 dst = isl_basic_set_extend_constraints(dst, n_eq, n_ineq);
1906 dst = isl_basic_set_add_constraints_dim_map(dst, src, dim_map);
1907 return dst;
1910 /* Add constraints to graph->lp that force validity for the given
1911 * dependence from a node i to itself.
1912 * That is, add constraints that enforce
1914 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1915 * = c_i_x (y - x) >= 0
1917 * for each (x,y) in R.
1918 * We obtain general constraints on coefficients (c_0, c_x)
1919 * of valid constraints for (y - x) and then plug in (0, c_i_x^+ - c_i_x^-),
1920 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1921 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1922 * Note that the result of intra_coefficients may also contain
1923 * parameter coefficients c_n, in which case 0 is plugged in for them as well.
1925 static isl_stat add_intra_validity_constraints(struct isl_sched_graph *graph,
1926 struct isl_sched_edge *edge)
1928 int offset;
1929 isl_map *map = isl_map_copy(edge->map);
1930 isl_ctx *ctx = isl_map_get_ctx(map);
1931 isl_dim_map *dim_map;
1932 isl_basic_set *coef;
1933 struct isl_sched_node *node = edge->src;
1935 coef = intra_coefficients(graph, node, map, 0);
1937 offset = coef_var_offset(coef);
1939 if (!coef)
1940 return isl_stat_error;
1942 dim_map = intra_dim_map(ctx, graph, node, offset, 1);
1943 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
1945 return isl_stat_ok;
1948 /* Add constraints to graph->lp that force validity for the given
1949 * dependence from node i to node j.
1950 * That is, add constraints that enforce
1952 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1954 * for each (x,y) in R.
1955 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1956 * of valid constraints for R and then plug in
1957 * (c_j_0 - c_i_0, c_j_n - c_i_n, -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-),
1958 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1959 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1961 static isl_stat add_inter_validity_constraints(struct isl_sched_graph *graph,
1962 struct isl_sched_edge *edge)
1964 int offset;
1965 isl_map *map;
1966 isl_ctx *ctx;
1967 isl_dim_map *dim_map;
1968 isl_basic_set *coef;
1969 struct isl_sched_node *src = edge->src;
1970 struct isl_sched_node *dst = edge->dst;
1972 if (!graph->lp)
1973 return isl_stat_error;
1975 map = isl_map_copy(edge->map);
1976 ctx = isl_map_get_ctx(map);
1977 coef = inter_coefficients(graph, edge, map);
1979 offset = coef_var_offset(coef);
1981 if (!coef)
1982 return isl_stat_error;
1984 dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1);
1986 edge->start = graph->lp->n_ineq;
1987 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
1988 if (!graph->lp)
1989 return isl_stat_error;
1990 edge->end = graph->lp->n_ineq;
1992 return isl_stat_ok;
1995 /* Add constraints to graph->lp that bound the dependence distance for the given
1996 * dependence from a node i to itself.
1997 * If s = 1, we add the constraint
1999 * c_i_x (y - x) <= m_0 + m_n n
2001 * or
2003 * -c_i_x (y - x) + m_0 + m_n n >= 0
2005 * for each (x,y) in R.
2006 * If s = -1, we add the constraint
2008 * -c_i_x (y - x) <= m_0 + m_n n
2010 * or
2012 * c_i_x (y - x) + m_0 + m_n n >= 0
2014 * for each (x,y) in R.
2015 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2016 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
2017 * with each coefficient (except m_0) represented as a pair of non-negative
2018 * coefficients.
2021 * If "local" is set, then we add constraints
2023 * c_i_x (y - x) <= 0
2025 * or
2027 * -c_i_x (y - x) <= 0
2029 * instead, forcing the dependence distance to be (less than or) equal to 0.
2030 * That is, we plug in (0, 0, -s * c_i_x),
2031 * intra_coefficients is not required to have c_n in its result when
2032 * "local" is set. If they are missing, then (0, -s * c_i_x) is plugged in.
2033 * Note that dependences marked local are treated as validity constraints
2034 * by add_all_validity_constraints and therefore also have
2035 * their distances bounded by 0 from below.
2037 static isl_stat add_intra_proximity_constraints(struct isl_sched_graph *graph,
2038 struct isl_sched_edge *edge, int s, int local)
2040 int offset;
2041 unsigned nparam;
2042 isl_map *map = isl_map_copy(edge->map);
2043 isl_ctx *ctx = isl_map_get_ctx(map);
2044 isl_dim_map *dim_map;
2045 isl_basic_set *coef;
2046 struct isl_sched_node *node = edge->src;
2048 coef = intra_coefficients(graph, node, map, !local);
2050 offset = coef_var_offset(coef);
2052 if (!coef)
2053 return isl_stat_error;
2055 nparam = isl_space_dim(node->space, isl_dim_param);
2056 dim_map = intra_dim_map(ctx, graph, node, offset, -s);
2058 if (!local) {
2059 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
2060 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
2061 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
2063 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
2065 return isl_stat_ok;
2068 /* Add constraints to graph->lp that bound the dependence distance for the given
2069 * dependence from node i to node j.
2070 * If s = 1, we add the constraint
2072 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
2073 * <= m_0 + m_n n
2075 * or
2077 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
2078 * m_0 + m_n n >= 0
2080 * for each (x,y) in R.
2081 * If s = -1, we add the constraint
2083 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
2084 * <= m_0 + m_n n
2086 * or
2088 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
2089 * m_0 + m_n n >= 0
2091 * for each (x,y) in R.
2092 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
2093 * of valid constraints for R and then plug in
2094 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
2095 * s*c_i_x, -s*c_j_x)
2096 * with each coefficient (except m_0, c_*_0 and c_*_n)
2097 * represented as a pair of non-negative coefficients.
2100 * If "local" is set (and s = 1), then we add constraints
2102 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
2104 * or
2106 * -((c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x)) >= 0
2108 * instead, forcing the dependence distance to be (less than or) equal to 0.
2109 * That is, we plug in
2110 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, s*c_i_x, -s*c_j_x).
2111 * Note that dependences marked local are treated as validity constraints
2112 * by add_all_validity_constraints and therefore also have
2113 * their distances bounded by 0 from below.
2115 static isl_stat add_inter_proximity_constraints(struct isl_sched_graph *graph,
2116 struct isl_sched_edge *edge, int s, int local)
2118 int offset;
2119 unsigned nparam;
2120 isl_map *map = isl_map_copy(edge->map);
2121 isl_ctx *ctx = isl_map_get_ctx(map);
2122 isl_dim_map *dim_map;
2123 isl_basic_set *coef;
2124 struct isl_sched_node *src = edge->src;
2125 struct isl_sched_node *dst = edge->dst;
2127 coef = inter_coefficients(graph, edge, map);
2129 offset = coef_var_offset(coef);
2131 if (!coef)
2132 return isl_stat_error;
2134 nparam = isl_space_dim(src->space, isl_dim_param);
2135 dim_map = inter_dim_map(ctx, graph, src, dst, offset, -s);
2137 if (!local) {
2138 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
2139 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
2140 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
2143 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
2145 return isl_stat_ok;
2148 /* Should the distance over "edge" be forced to zero?
2149 * That is, is it marked as a local edge?
2150 * If "use_coincidence" is set, then coincidence edges are treated
2151 * as local edges.
2153 static int force_zero(struct isl_sched_edge *edge, int use_coincidence)
2155 return is_local(edge) || (use_coincidence && is_coincidence(edge));
2158 /* Add all validity constraints to graph->lp.
2160 * An edge that is forced to be local needs to have its dependence
2161 * distances equal to zero. We take care of bounding them by 0 from below
2162 * here. add_all_proximity_constraints takes care of bounding them by 0
2163 * from above.
2165 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2166 * Otherwise, we ignore them.
2168 static int add_all_validity_constraints(struct isl_sched_graph *graph,
2169 int use_coincidence)
2171 int i;
2173 for (i = 0; i < graph->n_edge; ++i) {
2174 struct isl_sched_edge *edge = &graph->edge[i];
2175 int zero;
2177 zero = force_zero(edge, use_coincidence);
2178 if (!is_validity(edge) && !zero)
2179 continue;
2180 if (edge->src != edge->dst)
2181 continue;
2182 if (add_intra_validity_constraints(graph, edge) < 0)
2183 return -1;
2186 for (i = 0; i < graph->n_edge; ++i) {
2187 struct isl_sched_edge *edge = &graph->edge[i];
2188 int zero;
2190 zero = force_zero(edge, use_coincidence);
2191 if (!is_validity(edge) && !zero)
2192 continue;
2193 if (edge->src == edge->dst)
2194 continue;
2195 if (add_inter_validity_constraints(graph, edge) < 0)
2196 return -1;
2199 return 0;
2202 /* Add constraints to graph->lp that bound the dependence distance
2203 * for all dependence relations.
2204 * If a given proximity dependence is identical to a validity
2205 * dependence, then the dependence distance is already bounded
2206 * from below (by zero), so we only need to bound the distance
2207 * from above. (This includes the case of "local" dependences
2208 * which are treated as validity dependence by add_all_validity_constraints.)
2209 * Otherwise, we need to bound the distance both from above and from below.
2211 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2212 * Otherwise, we ignore them.
2214 static int add_all_proximity_constraints(struct isl_sched_graph *graph,
2215 int use_coincidence)
2217 int i;
2219 for (i = 0; i < graph->n_edge; ++i) {
2220 struct isl_sched_edge *edge = &graph->edge[i];
2221 int zero;
2223 zero = force_zero(edge, use_coincidence);
2224 if (!is_proximity(edge) && !zero)
2225 continue;
2226 if (edge->src == edge->dst &&
2227 add_intra_proximity_constraints(graph, edge, 1, zero) < 0)
2228 return -1;
2229 if (edge->src != edge->dst &&
2230 add_inter_proximity_constraints(graph, edge, 1, zero) < 0)
2231 return -1;
2232 if (is_validity(edge) || zero)
2233 continue;
2234 if (edge->src == edge->dst &&
2235 add_intra_proximity_constraints(graph, edge, -1, 0) < 0)
2236 return -1;
2237 if (edge->src != edge->dst &&
2238 add_inter_proximity_constraints(graph, edge, -1, 0) < 0)
2239 return -1;
2242 return 0;
2245 /* Normalize the rows of "indep" such that all rows are lexicographically
2246 * positive and such that each row contains as many final zeros as possible,
2247 * given the choice for the previous rows.
2248 * Do this by performing elementary row operations.
2250 static __isl_give isl_mat *normalize_independent(__isl_take isl_mat *indep)
2252 indep = isl_mat_reverse_gauss(indep);
2253 indep = isl_mat_lexnonneg_rows(indep);
2254 return indep;
2257 /* Compute a basis for the rows in the linear part of the schedule
2258 * and extend this basis to a full basis. The remaining rows
2259 * can then be used to force linear independence from the rows
2260 * in the schedule.
2262 * In particular, given the schedule rows S, we compute
2264 * S = H Q
2265 * S U = H
2267 * with H the Hermite normal form of S. That is, all but the
2268 * first rank columns of H are zero and so each row in S is
2269 * a linear combination of the first rank rows of Q.
2270 * The matrix Q can be used as a variable transformation
2271 * that isolates the directions of S in the first rank rows.
2272 * Transposing S U = H yields
2274 * U^T S^T = H^T
2276 * with all but the first rank rows of H^T zero.
2277 * The last rows of U^T are therefore linear combinations
2278 * of schedule coefficients that are all zero on schedule
2279 * coefficients that are linearly dependent on the rows of S.
2280 * At least one of these combinations is non-zero on
2281 * linearly independent schedule coefficients.
2282 * The rows are normalized to involve as few of the last
2283 * coefficients as possible and to have a positive initial value.
2285 static int node_update_vmap(struct isl_sched_node *node)
2287 isl_mat *H, *U, *Q;
2288 int n_row = isl_mat_rows(node->sched);
2290 H = isl_mat_sub_alloc(node->sched, 0, n_row,
2291 1 + node->nparam, node->nvar);
2293 H = isl_mat_left_hermite(H, 0, &U, &Q);
2294 isl_mat_free(node->indep);
2295 isl_mat_free(node->vmap);
2296 node->vmap = Q;
2297 node->indep = isl_mat_transpose(U);
2298 node->rank = isl_mat_initial_non_zero_cols(H);
2299 node->indep = isl_mat_drop_rows(node->indep, 0, node->rank);
2300 node->indep = normalize_independent(node->indep);
2301 isl_mat_free(H);
2303 if (!node->indep || !node->vmap || node->rank < 0)
2304 return -1;
2305 return 0;
2308 /* Is "edge" marked as a validity or a conditional validity edge?
2310 static int is_any_validity(struct isl_sched_edge *edge)
2312 return is_validity(edge) || is_conditional_validity(edge);
2315 /* How many times should we count the constraints in "edge"?
2317 * We count as follows
2318 * validity -> 1 (>= 0)
2319 * validity+proximity -> 2 (>= 0 and upper bound)
2320 * proximity -> 2 (lower and upper bound)
2321 * local(+any) -> 2 (>= 0 and <= 0)
2323 * If an edge is only marked conditional_validity then it counts
2324 * as zero since it is only checked afterwards.
2326 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2327 * Otherwise, we ignore them.
2329 static int edge_multiplicity(struct isl_sched_edge *edge, int use_coincidence)
2331 if (is_proximity(edge) || force_zero(edge, use_coincidence))
2332 return 2;
2333 if (is_validity(edge))
2334 return 1;
2335 return 0;
2338 /* How many times should the constraints in "edge" be counted
2339 * as a parametric intra-node constraint?
2341 * Only proximity edges that are not forced zero need
2342 * coefficient constraints that include coefficients for parameters.
2343 * If the edge is also a validity edge, then only
2344 * an upper bound is introduced. Otherwise, both lower and upper bounds
2345 * are introduced.
2347 static int parametric_intra_edge_multiplicity(struct isl_sched_edge *edge,
2348 int use_coincidence)
2350 if (edge->src != edge->dst)
2351 return 0;
2352 if (!is_proximity(edge))
2353 return 0;
2354 if (force_zero(edge, use_coincidence))
2355 return 0;
2356 if (is_validity(edge))
2357 return 1;
2358 else
2359 return 2;
2362 /* Add "f" times the number of equality and inequality constraints of "bset"
2363 * to "n_eq" and "n_ineq" and free "bset".
2365 static isl_stat update_count(__isl_take isl_basic_set *bset,
2366 int f, int *n_eq, int *n_ineq)
2368 if (!bset)
2369 return isl_stat_error;
2371 *n_eq += isl_basic_set_n_equality(bset);
2372 *n_ineq += isl_basic_set_n_inequality(bset);
2373 isl_basic_set_free(bset);
2375 return isl_stat_ok;
2378 /* Count the number of equality and inequality constraints
2379 * that will be added for the given map.
2381 * The edges that require parameter coefficients are counted separately.
2383 * "use_coincidence" is set if we should take into account coincidence edges.
2385 static isl_stat count_map_constraints(struct isl_sched_graph *graph,
2386 struct isl_sched_edge *edge, __isl_take isl_map *map,
2387 int *n_eq, int *n_ineq, int use_coincidence)
2389 isl_map *copy;
2390 isl_basic_set *coef;
2391 int f = edge_multiplicity(edge, use_coincidence);
2392 int fp = parametric_intra_edge_multiplicity(edge, use_coincidence);
2394 if (f == 0) {
2395 isl_map_free(map);
2396 return isl_stat_ok;
2399 if (edge->src != edge->dst) {
2400 coef = inter_coefficients(graph, edge, map);
2401 return update_count(coef, f, n_eq, n_ineq);
2404 if (fp > 0) {
2405 copy = isl_map_copy(map);
2406 coef = intra_coefficients(graph, edge->src, copy, 1);
2407 if (update_count(coef, fp, n_eq, n_ineq) < 0)
2408 goto error;
2411 if (f > fp) {
2412 copy = isl_map_copy(map);
2413 coef = intra_coefficients(graph, edge->src, copy, 0);
2414 if (update_count(coef, f - fp, n_eq, n_ineq) < 0)
2415 goto error;
2418 isl_map_free(map);
2419 return isl_stat_ok;
2420 error:
2421 isl_map_free(map);
2422 return isl_stat_error;
2425 /* Count the number of equality and inequality constraints
2426 * that will be added to the main lp problem.
2427 * We count as follows
2428 * validity -> 1 (>= 0)
2429 * validity+proximity -> 2 (>= 0 and upper bound)
2430 * proximity -> 2 (lower and upper bound)
2431 * local(+any) -> 2 (>= 0 and <= 0)
2433 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2434 * Otherwise, we ignore them.
2436 static int count_constraints(struct isl_sched_graph *graph,
2437 int *n_eq, int *n_ineq, int use_coincidence)
2439 int i;
2441 *n_eq = *n_ineq = 0;
2442 for (i = 0; i < graph->n_edge; ++i) {
2443 struct isl_sched_edge *edge = &graph->edge[i];
2444 isl_map *map = isl_map_copy(edge->map);
2446 if (count_map_constraints(graph, edge, map, n_eq, n_ineq,
2447 use_coincidence) < 0)
2448 return -1;
2451 return 0;
2454 /* Count the number of constraints that will be added by
2455 * add_bound_constant_constraints to bound the values of the constant terms
2456 * and increment *n_eq and *n_ineq accordingly.
2458 * In practice, add_bound_constant_constraints only adds inequalities.
2460 static isl_stat count_bound_constant_constraints(isl_ctx *ctx,
2461 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2463 if (isl_options_get_schedule_max_constant_term(ctx) == -1)
2464 return isl_stat_ok;
2466 *n_ineq += graph->n;
2468 return isl_stat_ok;
2471 /* Add constraints to bound the values of the constant terms in the schedule,
2472 * if requested by the user.
2474 * The maximal value of the constant terms is defined by the option
2475 * "schedule_max_constant_term".
2477 static isl_stat add_bound_constant_constraints(isl_ctx *ctx,
2478 struct isl_sched_graph *graph)
2480 int i, k;
2481 int max;
2482 int total;
2484 max = isl_options_get_schedule_max_constant_term(ctx);
2485 if (max == -1)
2486 return isl_stat_ok;
2488 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2490 for (i = 0; i < graph->n; ++i) {
2491 struct isl_sched_node *node = &graph->node[i];
2492 int pos;
2494 k = isl_basic_set_alloc_inequality(graph->lp);
2495 if (k < 0)
2496 return isl_stat_error;
2497 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2498 pos = node_cst_coef_offset(node);
2499 isl_int_set_si(graph->lp->ineq[k][1 + pos], -1);
2500 isl_int_set_si(graph->lp->ineq[k][0], max);
2503 return isl_stat_ok;
2506 /* Count the number of constraints that will be added by
2507 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2508 * accordingly.
2510 * In practice, add_bound_coefficient_constraints only adds inequalities.
2512 static int count_bound_coefficient_constraints(isl_ctx *ctx,
2513 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2515 int i;
2517 if (isl_options_get_schedule_max_coefficient(ctx) == -1 &&
2518 !isl_options_get_schedule_treat_coalescing(ctx))
2519 return 0;
2521 for (i = 0; i < graph->n; ++i)
2522 *n_ineq += graph->node[i].nparam + 2 * graph->node[i].nvar;
2524 return 0;
2527 /* Add constraints to graph->lp that bound the values of
2528 * the parameter schedule coefficients of "node" to "max" and
2529 * the variable schedule coefficients to the corresponding entry
2530 * in node->max.
2531 * In either case, a negative value means that no bound needs to be imposed.
2533 * For parameter coefficients, this amounts to adding a constraint
2535 * c_n <= max
2537 * i.e.,
2539 * -c_n + max >= 0
2541 * The variables coefficients are, however, not represented directly.
2542 * Instead, the variable coefficients c_x are written as differences
2543 * c_x = c_x^+ - c_x^-.
2544 * That is,
2546 * -max_i <= c_x_i <= max_i
2548 * is encoded as
2550 * -max_i <= c_x_i^+ - c_x_i^- <= max_i
2552 * or
2554 * -(c_x_i^+ - c_x_i^-) + max_i >= 0
2555 * c_x_i^+ - c_x_i^- + max_i >= 0
2557 static isl_stat node_add_coefficient_constraints(isl_ctx *ctx,
2558 struct isl_sched_graph *graph, struct isl_sched_node *node, int max)
2560 int i, j, k;
2561 int total;
2562 isl_vec *ineq;
2564 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2566 for (j = 0; j < node->nparam; ++j) {
2567 int dim;
2569 if (max < 0)
2570 continue;
2572 k = isl_basic_set_alloc_inequality(graph->lp);
2573 if (k < 0)
2574 return isl_stat_error;
2575 dim = 1 + node_par_coef_offset(node) + j;
2576 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2577 isl_int_set_si(graph->lp->ineq[k][dim], -1);
2578 isl_int_set_si(graph->lp->ineq[k][0], max);
2581 ineq = isl_vec_alloc(ctx, 1 + total);
2582 ineq = isl_vec_clr(ineq);
2583 if (!ineq)
2584 return isl_stat_error;
2585 for (i = 0; i < node->nvar; ++i) {
2586 int pos = 1 + node_var_coef_pos(node, i);
2588 if (isl_int_is_neg(node->max->el[i]))
2589 continue;
2591 isl_int_set_si(ineq->el[pos], 1);
2592 isl_int_set_si(ineq->el[pos + 1], -1);
2593 isl_int_set(ineq->el[0], node->max->el[i]);
2595 k = isl_basic_set_alloc_inequality(graph->lp);
2596 if (k < 0)
2597 goto error;
2598 isl_seq_cpy(graph->lp->ineq[k], ineq->el, 1 + total);
2600 isl_seq_neg(ineq->el + pos, ineq->el + pos, 2);
2601 k = isl_basic_set_alloc_inequality(graph->lp);
2602 if (k < 0)
2603 goto error;
2604 isl_seq_cpy(graph->lp->ineq[k], ineq->el, 1 + total);
2606 isl_seq_clr(ineq->el + pos, 2);
2608 isl_vec_free(ineq);
2610 return isl_stat_ok;
2611 error:
2612 isl_vec_free(ineq);
2613 return isl_stat_error;
2616 /* Add constraints that bound the values of the variable and parameter
2617 * coefficients of the schedule.
2619 * The maximal value of the coefficients is defined by the option
2620 * 'schedule_max_coefficient' and the entries in node->max.
2621 * These latter entries are only set if either the schedule_max_coefficient
2622 * option or the schedule_treat_coalescing option is set.
2624 static isl_stat add_bound_coefficient_constraints(isl_ctx *ctx,
2625 struct isl_sched_graph *graph)
2627 int i;
2628 int max;
2630 max = isl_options_get_schedule_max_coefficient(ctx);
2632 if (max == -1 && !isl_options_get_schedule_treat_coalescing(ctx))
2633 return isl_stat_ok;
2635 for (i = 0; i < graph->n; ++i) {
2636 struct isl_sched_node *node = &graph->node[i];
2638 if (node_add_coefficient_constraints(ctx, graph, node, max) < 0)
2639 return isl_stat_error;
2642 return isl_stat_ok;
2645 /* Add a constraint to graph->lp that equates the value at position
2646 * "sum_pos" to the sum of the "n" values starting at "first".
2648 static isl_stat add_sum_constraint(struct isl_sched_graph *graph,
2649 int sum_pos, int first, int n)
2651 int i, k;
2652 int total;
2654 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2656 k = isl_basic_set_alloc_equality(graph->lp);
2657 if (k < 0)
2658 return isl_stat_error;
2659 isl_seq_clr(graph->lp->eq[k], 1 + total);
2660 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1);
2661 for (i = 0; i < n; ++i)
2662 isl_int_set_si(graph->lp->eq[k][1 + first + i], 1);
2664 return isl_stat_ok;
2667 /* Add a constraint to graph->lp that equates the value at position
2668 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2670 static isl_stat add_param_sum_constraint(struct isl_sched_graph *graph,
2671 int sum_pos)
2673 int i, j, k;
2674 int total;
2676 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2678 k = isl_basic_set_alloc_equality(graph->lp);
2679 if (k < 0)
2680 return isl_stat_error;
2681 isl_seq_clr(graph->lp->eq[k], 1 + total);
2682 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1);
2683 for (i = 0; i < graph->n; ++i) {
2684 int pos = 1 + node_par_coef_offset(&graph->node[i]);
2686 for (j = 0; j < graph->node[i].nparam; ++j)
2687 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2690 return isl_stat_ok;
2693 /* Add a constraint to graph->lp that equates the value at position
2694 * "sum_pos" to the sum of the variable coefficients of all nodes.
2696 static isl_stat add_var_sum_constraint(struct isl_sched_graph *graph,
2697 int sum_pos)
2699 int i, j, k;
2700 int total;
2702 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2704 k = isl_basic_set_alloc_equality(graph->lp);
2705 if (k < 0)
2706 return isl_stat_error;
2707 isl_seq_clr(graph->lp->eq[k], 1 + total);
2708 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1);
2709 for (i = 0; i < graph->n; ++i) {
2710 struct isl_sched_node *node = &graph->node[i];
2711 int pos = 1 + node_var_coef_offset(node);
2713 for (j = 0; j < 2 * node->nvar; ++j)
2714 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2717 return isl_stat_ok;
2720 /* Construct an ILP problem for finding schedule coefficients
2721 * that result in non-negative, but small dependence distances
2722 * over all dependences.
2723 * In particular, the dependence distances over proximity edges
2724 * are bounded by m_0 + m_n n and we compute schedule coefficients
2725 * with small values (preferably zero) of m_n and m_0.
2727 * All variables of the ILP are non-negative. The actual coefficients
2728 * may be negative, so each coefficient is represented as the difference
2729 * of two non-negative variables. The negative part always appears
2730 * immediately before the positive part.
2731 * Other than that, the variables have the following order
2733 * - sum of positive and negative parts of m_n coefficients
2734 * - m_0
2735 * - sum of all c_n coefficients
2736 * (unconstrained when computing non-parametric schedules)
2737 * - sum of positive and negative parts of all c_x coefficients
2738 * - positive and negative parts of m_n coefficients
2739 * - for each node
2740 * - positive and negative parts of c_i_x, in opposite order
2741 * - c_i_n (if parametric)
2742 * - c_i_0
2744 * The constraints are those from the edges plus two or three equalities
2745 * to express the sums.
2747 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2748 * Otherwise, we ignore them.
2750 static isl_stat setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
2751 int use_coincidence)
2753 int i;
2754 unsigned nparam;
2755 unsigned total;
2756 isl_space *space;
2757 int parametric;
2758 int param_pos;
2759 int n_eq, n_ineq;
2761 parametric = ctx->opt->schedule_parametric;
2762 nparam = isl_space_dim(graph->node[0].space, isl_dim_param);
2763 param_pos = 4;
2764 total = param_pos + 2 * nparam;
2765 for (i = 0; i < graph->n; ++i) {
2766 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2767 if (node_update_vmap(node) < 0)
2768 return isl_stat_error;
2769 node->start = total;
2770 total += 1 + node->nparam + 2 * node->nvar;
2773 if (count_constraints(graph, &n_eq, &n_ineq, use_coincidence) < 0)
2774 return isl_stat_error;
2775 if (count_bound_constant_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2776 return isl_stat_error;
2777 if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2778 return isl_stat_error;
2780 space = isl_space_set_alloc(ctx, 0, total);
2781 isl_basic_set_free(graph->lp);
2782 n_eq += 2 + parametric;
2784 graph->lp = isl_basic_set_alloc_space(space, 0, n_eq, n_ineq);
2786 if (add_sum_constraint(graph, 0, param_pos, 2 * nparam) < 0)
2787 return isl_stat_error;
2788 if (parametric && add_param_sum_constraint(graph, 2) < 0)
2789 return isl_stat_error;
2790 if (add_var_sum_constraint(graph, 3) < 0)
2791 return isl_stat_error;
2792 if (add_bound_constant_constraints(ctx, graph) < 0)
2793 return isl_stat_error;
2794 if (add_bound_coefficient_constraints(ctx, graph) < 0)
2795 return isl_stat_error;
2796 if (add_all_validity_constraints(graph, use_coincidence) < 0)
2797 return isl_stat_error;
2798 if (add_all_proximity_constraints(graph, use_coincidence) < 0)
2799 return isl_stat_error;
2801 return isl_stat_ok;
2804 /* Analyze the conflicting constraint found by
2805 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2806 * constraint of one of the edges between distinct nodes, living, moreover
2807 * in distinct SCCs, then record the source and sink SCC as this may
2808 * be a good place to cut between SCCs.
2810 static int check_conflict(int con, void *user)
2812 int i;
2813 struct isl_sched_graph *graph = user;
2815 if (graph->src_scc >= 0)
2816 return 0;
2818 con -= graph->lp->n_eq;
2820 if (con >= graph->lp->n_ineq)
2821 return 0;
2823 for (i = 0; i < graph->n_edge; ++i) {
2824 if (!is_validity(&graph->edge[i]))
2825 continue;
2826 if (graph->edge[i].src == graph->edge[i].dst)
2827 continue;
2828 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
2829 continue;
2830 if (graph->edge[i].start > con)
2831 continue;
2832 if (graph->edge[i].end <= con)
2833 continue;
2834 graph->src_scc = graph->edge[i].src->scc;
2835 graph->dst_scc = graph->edge[i].dst->scc;
2838 return 0;
2841 /* Check whether the next schedule row of the given node needs to be
2842 * non-trivial. Lower-dimensional domains may have some trivial rows,
2843 * but as soon as the number of remaining required non-trivial rows
2844 * is as large as the number or remaining rows to be computed,
2845 * all remaining rows need to be non-trivial.
2847 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
2849 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
2852 /* Construct a non-triviality region with triviality directions
2853 * corresponding to the rows of "indep".
2854 * The rows of "indep" are expressed in terms of the schedule coefficients c_i,
2855 * while the triviality directions are expressed in terms of
2856 * pairs of non-negative variables c^+_i - c^-_i, with c^-_i appearing
2857 * before c^+_i. Furthermore,
2858 * the pairs of non-negative variables representing the coefficients
2859 * are stored in the opposite order.
2861 static __isl_give isl_mat *construct_trivial(__isl_keep isl_mat *indep)
2863 isl_ctx *ctx;
2864 isl_mat *mat;
2865 int i, j, n, n_var;
2867 if (!indep)
2868 return NULL;
2870 ctx = isl_mat_get_ctx(indep);
2871 n = isl_mat_rows(indep);
2872 n_var = isl_mat_cols(indep);
2873 mat = isl_mat_alloc(ctx, n, 2 * n_var);
2874 if (!mat)
2875 return NULL;
2876 for (i = 0; i < n; ++i) {
2877 for (j = 0; j < n_var; ++j) {
2878 int nj = n_var - 1 - j;
2879 isl_int_neg(mat->row[i][2 * nj], indep->row[i][j]);
2880 isl_int_set(mat->row[i][2 * nj + 1], indep->row[i][j]);
2884 return mat;
2887 /* Solve the ILP problem constructed in setup_lp.
2888 * For each node such that all the remaining rows of its schedule
2889 * need to be non-trivial, we construct a non-triviality region.
2890 * This region imposes that the next row is independent of previous rows.
2891 * In particular, the non-triviality region enforces that at least
2892 * one of the linear combinations in the rows of node->indep is non-zero.
2894 static __isl_give isl_vec *solve_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2896 int i;
2897 isl_vec *sol;
2898 isl_basic_set *lp;
2900 for (i = 0; i < graph->n; ++i) {
2901 struct isl_sched_node *node = &graph->node[i];
2902 isl_mat *trivial;
2904 graph->region[i].pos = node_var_coef_offset(node);
2905 if (needs_row(graph, node))
2906 trivial = construct_trivial(node->indep);
2907 else
2908 trivial = isl_mat_zero(ctx, 0, 0);
2909 graph->region[i].trivial = trivial;
2911 lp = isl_basic_set_copy(graph->lp);
2912 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
2913 graph->region, &check_conflict, graph);
2914 for (i = 0; i < graph->n; ++i)
2915 isl_mat_free(graph->region[i].trivial);
2916 return sol;
2919 /* Extract the coefficients for the variables of "node" from "sol".
2921 * Each schedule coefficient c_i_x is represented as the difference
2922 * between two non-negative variables c_i_x^+ - c_i_x^-.
2923 * The c_i_x^- appear before their c_i_x^+ counterpart.
2924 * Furthermore, the order of these pairs is the opposite of that
2925 * of the corresponding coefficients.
2927 * Return c_i_x = c_i_x^+ - c_i_x^-
2929 static __isl_give isl_vec *extract_var_coef(struct isl_sched_node *node,
2930 __isl_keep isl_vec *sol)
2932 int i;
2933 int pos;
2934 isl_vec *csol;
2936 if (!sol)
2937 return NULL;
2938 csol = isl_vec_alloc(isl_vec_get_ctx(sol), node->nvar);
2939 if (!csol)
2940 return NULL;
2942 pos = 1 + node_var_coef_offset(node);
2943 for (i = 0; i < node->nvar; ++i)
2944 isl_int_sub(csol->el[node->nvar - 1 - i],
2945 sol->el[pos + 2 * i + 1], sol->el[pos + 2 * i]);
2947 return csol;
2950 /* Update the schedules of all nodes based on the given solution
2951 * of the LP problem.
2952 * The new row is added to the current band.
2953 * All possibly negative coefficients are encoded as a difference
2954 * of two non-negative variables, so we need to perform the subtraction
2955 * here.
2957 * If coincident is set, then the caller guarantees that the new
2958 * row satisfies the coincidence constraints.
2960 static int update_schedule(struct isl_sched_graph *graph,
2961 __isl_take isl_vec *sol, int coincident)
2963 int i, j;
2964 isl_vec *csol = NULL;
2966 if (!sol)
2967 goto error;
2968 if (sol->size == 0)
2969 isl_die(sol->ctx, isl_error_internal,
2970 "no solution found", goto error);
2971 if (graph->n_total_row >= graph->max_row)
2972 isl_die(sol->ctx, isl_error_internal,
2973 "too many schedule rows", goto error);
2975 for (i = 0; i < graph->n; ++i) {
2976 struct isl_sched_node *node = &graph->node[i];
2977 int pos;
2978 int row = isl_mat_rows(node->sched);
2980 isl_vec_free(csol);
2981 csol = extract_var_coef(node, sol);
2982 if (!csol)
2983 goto error;
2985 isl_map_free(node->sched_map);
2986 node->sched_map = NULL;
2987 node->sched = isl_mat_add_rows(node->sched, 1);
2988 if (!node->sched)
2989 goto error;
2990 pos = node_cst_coef_offset(node);
2991 node->sched = isl_mat_set_element(node->sched,
2992 row, 0, sol->el[1 + pos]);
2993 pos = node_par_coef_offset(node);
2994 for (j = 0; j < node->nparam; ++j)
2995 node->sched = isl_mat_set_element(node->sched,
2996 row, 1 + j, sol->el[1 + pos + j]);
2997 for (j = 0; j < node->nvar; ++j)
2998 node->sched = isl_mat_set_element(node->sched,
2999 row, 1 + node->nparam + j, csol->el[j]);
3000 node->coincident[graph->n_total_row] = coincident;
3002 isl_vec_free(sol);
3003 isl_vec_free(csol);
3005 graph->n_row++;
3006 graph->n_total_row++;
3008 return 0;
3009 error:
3010 isl_vec_free(sol);
3011 isl_vec_free(csol);
3012 return -1;
3015 /* Convert row "row" of node->sched into an isl_aff living in "ls"
3016 * and return this isl_aff.
3018 static __isl_give isl_aff *extract_schedule_row(__isl_take isl_local_space *ls,
3019 struct isl_sched_node *node, int row)
3021 int j;
3022 isl_int v;
3023 isl_aff *aff;
3025 isl_int_init(v);
3027 aff = isl_aff_zero_on_domain(ls);
3028 if (isl_mat_get_element(node->sched, row, 0, &v) < 0)
3029 goto error;
3030 aff = isl_aff_set_constant(aff, v);
3031 for (j = 0; j < node->nparam; ++j) {
3032 if (isl_mat_get_element(node->sched, row, 1 + j, &v) < 0)
3033 goto error;
3034 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
3036 for (j = 0; j < node->nvar; ++j) {
3037 if (isl_mat_get_element(node->sched, row,
3038 1 + node->nparam + j, &v) < 0)
3039 goto error;
3040 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
3043 isl_int_clear(v);
3045 return aff;
3046 error:
3047 isl_int_clear(v);
3048 isl_aff_free(aff);
3049 return NULL;
3052 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
3053 * and return this multi_aff.
3055 * The result is defined over the uncompressed node domain.
3057 static __isl_give isl_multi_aff *node_extract_partial_schedule_multi_aff(
3058 struct isl_sched_node *node, int first, int n)
3060 int i;
3061 isl_space *space;
3062 isl_local_space *ls;
3063 isl_aff *aff;
3064 isl_multi_aff *ma;
3065 int nrow;
3067 if (!node)
3068 return NULL;
3069 nrow = isl_mat_rows(node->sched);
3070 if (node->compressed)
3071 space = isl_multi_aff_get_domain_space(node->decompress);
3072 else
3073 space = isl_space_copy(node->space);
3074 ls = isl_local_space_from_space(isl_space_copy(space));
3075 space = isl_space_from_domain(space);
3076 space = isl_space_add_dims(space, isl_dim_out, n);
3077 ma = isl_multi_aff_zero(space);
3079 for (i = first; i < first + n; ++i) {
3080 aff = extract_schedule_row(isl_local_space_copy(ls), node, i);
3081 ma = isl_multi_aff_set_aff(ma, i - first, aff);
3084 isl_local_space_free(ls);
3086 if (node->compressed)
3087 ma = isl_multi_aff_pullback_multi_aff(ma,
3088 isl_multi_aff_copy(node->compress));
3090 return ma;
3093 /* Convert node->sched into a multi_aff and return this multi_aff.
3095 * The result is defined over the uncompressed node domain.
3097 static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
3098 struct isl_sched_node *node)
3100 int nrow;
3102 nrow = isl_mat_rows(node->sched);
3103 return node_extract_partial_schedule_multi_aff(node, 0, nrow);
3106 /* Convert node->sched into a map and return this map.
3108 * The result is cached in node->sched_map, which needs to be released
3109 * whenever node->sched is updated.
3110 * It is defined over the uncompressed node domain.
3112 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
3114 if (!node->sched_map) {
3115 isl_multi_aff *ma;
3117 ma = node_extract_schedule_multi_aff(node);
3118 node->sched_map = isl_map_from_multi_aff(ma);
3121 return isl_map_copy(node->sched_map);
3124 /* Construct a map that can be used to update a dependence relation
3125 * based on the current schedule.
3126 * That is, construct a map expressing that source and sink
3127 * are executed within the same iteration of the current schedule.
3128 * This map can then be intersected with the dependence relation.
3129 * This is not the most efficient way, but this shouldn't be a critical
3130 * operation.
3132 static __isl_give isl_map *specializer(struct isl_sched_node *src,
3133 struct isl_sched_node *dst)
3135 isl_map *src_sched, *dst_sched;
3137 src_sched = node_extract_schedule(src);
3138 dst_sched = node_extract_schedule(dst);
3139 return isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
3142 /* Intersect the domains of the nested relations in domain and range
3143 * of "umap" with "map".
3145 static __isl_give isl_union_map *intersect_domains(
3146 __isl_take isl_union_map *umap, __isl_keep isl_map *map)
3148 isl_union_set *uset;
3150 umap = isl_union_map_zip(umap);
3151 uset = isl_union_set_from_set(isl_map_wrap(isl_map_copy(map)));
3152 umap = isl_union_map_intersect_domain(umap, uset);
3153 umap = isl_union_map_zip(umap);
3154 return umap;
3157 /* Update the dependence relation of the given edge based
3158 * on the current schedule.
3159 * If the dependence is carried completely by the current schedule, then
3160 * it is removed from the edge_tables. It is kept in the list of edges
3161 * as otherwise all edge_tables would have to be recomputed.
3163 * If the edge is of a type that can appear multiple times
3164 * between the same pair of nodes, then it is added to
3165 * the edge table (again). This prevents the situation
3166 * where none of these edges is referenced from the edge table
3167 * because the one that was referenced turned out to be empty and
3168 * was therefore removed from the table.
3170 static isl_stat update_edge(isl_ctx *ctx, struct isl_sched_graph *graph,
3171 struct isl_sched_edge *edge)
3173 int empty;
3174 isl_map *id;
3176 id = specializer(edge->src, edge->dst);
3177 edge->map = isl_map_intersect(edge->map, isl_map_copy(id));
3178 if (!edge->map)
3179 goto error;
3181 if (edge->tagged_condition) {
3182 edge->tagged_condition =
3183 intersect_domains(edge->tagged_condition, id);
3184 if (!edge->tagged_condition)
3185 goto error;
3187 if (edge->tagged_validity) {
3188 edge->tagged_validity =
3189 intersect_domains(edge->tagged_validity, id);
3190 if (!edge->tagged_validity)
3191 goto error;
3194 empty = isl_map_plain_is_empty(edge->map);
3195 if (empty < 0)
3196 goto error;
3197 if (empty) {
3198 graph_remove_edge(graph, edge);
3199 } else if (is_multi_edge_type(edge)) {
3200 if (graph_edge_tables_add(ctx, graph, edge) < 0)
3201 goto error;
3204 isl_map_free(id);
3205 return isl_stat_ok;
3206 error:
3207 isl_map_free(id);
3208 return isl_stat_error;
3211 /* Does the domain of "umap" intersect "uset"?
3213 static int domain_intersects(__isl_keep isl_union_map *umap,
3214 __isl_keep isl_union_set *uset)
3216 int empty;
3218 umap = isl_union_map_copy(umap);
3219 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(uset));
3220 empty = isl_union_map_is_empty(umap);
3221 isl_union_map_free(umap);
3223 return empty < 0 ? -1 : !empty;
3226 /* Does the range of "umap" intersect "uset"?
3228 static int range_intersects(__isl_keep isl_union_map *umap,
3229 __isl_keep isl_union_set *uset)
3231 int empty;
3233 umap = isl_union_map_copy(umap);
3234 umap = isl_union_map_intersect_range(umap, isl_union_set_copy(uset));
3235 empty = isl_union_map_is_empty(umap);
3236 isl_union_map_free(umap);
3238 return empty < 0 ? -1 : !empty;
3241 /* Are the condition dependences of "edge" local with respect to
3242 * the current schedule?
3244 * That is, are domain and range of the condition dependences mapped
3245 * to the same point?
3247 * In other words, is the condition false?
3249 static int is_condition_false(struct isl_sched_edge *edge)
3251 isl_union_map *umap;
3252 isl_map *map, *sched, *test;
3253 int empty, local;
3255 empty = isl_union_map_is_empty(edge->tagged_condition);
3256 if (empty < 0 || empty)
3257 return empty;
3259 umap = isl_union_map_copy(edge->tagged_condition);
3260 umap = isl_union_map_zip(umap);
3261 umap = isl_union_set_unwrap(isl_union_map_domain(umap));
3262 map = isl_map_from_union_map(umap);
3264 sched = node_extract_schedule(edge->src);
3265 map = isl_map_apply_domain(map, sched);
3266 sched = node_extract_schedule(edge->dst);
3267 map = isl_map_apply_range(map, sched);
3269 test = isl_map_identity(isl_map_get_space(map));
3270 local = isl_map_is_subset(map, test);
3271 isl_map_free(map);
3272 isl_map_free(test);
3274 return local;
3277 /* For each conditional validity constraint that is adjacent
3278 * to a condition with domain in condition_source or range in condition_sink,
3279 * turn it into an unconditional validity constraint.
3281 static int unconditionalize_adjacent_validity(struct isl_sched_graph *graph,
3282 __isl_take isl_union_set *condition_source,
3283 __isl_take isl_union_set *condition_sink)
3285 int i;
3287 condition_source = isl_union_set_coalesce(condition_source);
3288 condition_sink = isl_union_set_coalesce(condition_sink);
3290 for (i = 0; i < graph->n_edge; ++i) {
3291 int adjacent;
3292 isl_union_map *validity;
3294 if (!is_conditional_validity(&graph->edge[i]))
3295 continue;
3296 if (is_validity(&graph->edge[i]))
3297 continue;
3299 validity = graph->edge[i].tagged_validity;
3300 adjacent = domain_intersects(validity, condition_sink);
3301 if (adjacent >= 0 && !adjacent)
3302 adjacent = range_intersects(validity, condition_source);
3303 if (adjacent < 0)
3304 goto error;
3305 if (!adjacent)
3306 continue;
3308 set_validity(&graph->edge[i]);
3311 isl_union_set_free(condition_source);
3312 isl_union_set_free(condition_sink);
3313 return 0;
3314 error:
3315 isl_union_set_free(condition_source);
3316 isl_union_set_free(condition_sink);
3317 return -1;
3320 /* Update the dependence relations of all edges based on the current schedule
3321 * and enforce conditional validity constraints that are adjacent
3322 * to satisfied condition constraints.
3324 * First check if any of the condition constraints are satisfied
3325 * (i.e., not local to the outer schedule) and keep track of
3326 * their domain and range.
3327 * Then update all dependence relations (which removes the non-local
3328 * constraints).
3329 * Finally, if any condition constraints turned out to be satisfied,
3330 * then turn all adjacent conditional validity constraints into
3331 * unconditional validity constraints.
3333 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
3335 int i;
3336 int any = 0;
3337 isl_union_set *source, *sink;
3339 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3340 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3341 for (i = 0; i < graph->n_edge; ++i) {
3342 int local;
3343 isl_union_set *uset;
3344 isl_union_map *umap;
3346 if (!is_condition(&graph->edge[i]))
3347 continue;
3348 if (is_local(&graph->edge[i]))
3349 continue;
3350 local = is_condition_false(&graph->edge[i]);
3351 if (local < 0)
3352 goto error;
3353 if (local)
3354 continue;
3356 any = 1;
3358 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
3359 uset = isl_union_map_domain(umap);
3360 source = isl_union_set_union(source, uset);
3362 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
3363 uset = isl_union_map_range(umap);
3364 sink = isl_union_set_union(sink, uset);
3367 for (i = 0; i < graph->n_edge; ++i) {
3368 if (update_edge(ctx, graph, &graph->edge[i]) < 0)
3369 goto error;
3372 if (any)
3373 return unconditionalize_adjacent_validity(graph, source, sink);
3375 isl_union_set_free(source);
3376 isl_union_set_free(sink);
3377 return 0;
3378 error:
3379 isl_union_set_free(source);
3380 isl_union_set_free(sink);
3381 return -1;
3384 static void next_band(struct isl_sched_graph *graph)
3386 graph->band_start = graph->n_total_row;
3389 /* Return the union of the universe domains of the nodes in "graph"
3390 * that satisfy "pred".
3392 static __isl_give isl_union_set *isl_sched_graph_domain(isl_ctx *ctx,
3393 struct isl_sched_graph *graph,
3394 int (*pred)(struct isl_sched_node *node, int data), int data)
3396 int i;
3397 isl_set *set;
3398 isl_union_set *dom;
3400 for (i = 0; i < graph->n; ++i)
3401 if (pred(&graph->node[i], data))
3402 break;
3404 if (i >= graph->n)
3405 isl_die(ctx, isl_error_internal,
3406 "empty component", return NULL);
3408 set = isl_set_universe(isl_space_copy(graph->node[i].space));
3409 dom = isl_union_set_from_set(set);
3411 for (i = i + 1; i < graph->n; ++i) {
3412 if (!pred(&graph->node[i], data))
3413 continue;
3414 set = isl_set_universe(isl_space_copy(graph->node[i].space));
3415 dom = isl_union_set_union(dom, isl_union_set_from_set(set));
3418 return dom;
3421 /* Return a list of unions of universe domains, where each element
3422 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3424 static __isl_give isl_union_set_list *extract_sccs(isl_ctx *ctx,
3425 struct isl_sched_graph *graph)
3427 int i;
3428 isl_union_set_list *filters;
3430 filters = isl_union_set_list_alloc(ctx, graph->scc);
3431 for (i = 0; i < graph->scc; ++i) {
3432 isl_union_set *dom;
3434 dom = isl_sched_graph_domain(ctx, graph, &node_scc_exactly, i);
3435 filters = isl_union_set_list_add(filters, dom);
3438 return filters;
3441 /* Return a list of two unions of universe domains, one for the SCCs up
3442 * to and including graph->src_scc and another for the other SCCs.
3444 static __isl_give isl_union_set_list *extract_split(isl_ctx *ctx,
3445 struct isl_sched_graph *graph)
3447 isl_union_set *dom;
3448 isl_union_set_list *filters;
3450 filters = isl_union_set_list_alloc(ctx, 2);
3451 dom = isl_sched_graph_domain(ctx, graph,
3452 &node_scc_at_most, graph->src_scc);
3453 filters = isl_union_set_list_add(filters, dom);
3454 dom = isl_sched_graph_domain(ctx, graph,
3455 &node_scc_at_least, graph->src_scc + 1);
3456 filters = isl_union_set_list_add(filters, dom);
3458 return filters;
3461 /* Copy nodes that satisfy node_pred from the src dependence graph
3462 * to the dst dependence graph.
3464 static isl_stat copy_nodes(struct isl_sched_graph *dst,
3465 struct isl_sched_graph *src,
3466 int (*node_pred)(struct isl_sched_node *node, int data), int data)
3468 int i;
3470 dst->n = 0;
3471 for (i = 0; i < src->n; ++i) {
3472 int j;
3474 if (!node_pred(&src->node[i], data))
3475 continue;
3477 j = dst->n;
3478 dst->node[j].space = isl_space_copy(src->node[i].space);
3479 dst->node[j].compressed = src->node[i].compressed;
3480 dst->node[j].hull = isl_set_copy(src->node[i].hull);
3481 dst->node[j].compress =
3482 isl_multi_aff_copy(src->node[i].compress);
3483 dst->node[j].decompress =
3484 isl_multi_aff_copy(src->node[i].decompress);
3485 dst->node[j].nvar = src->node[i].nvar;
3486 dst->node[j].nparam = src->node[i].nparam;
3487 dst->node[j].sched = isl_mat_copy(src->node[i].sched);
3488 dst->node[j].sched_map = isl_map_copy(src->node[i].sched_map);
3489 dst->node[j].coincident = src->node[i].coincident;
3490 dst->node[j].sizes = isl_multi_val_copy(src->node[i].sizes);
3491 dst->node[j].bounds = isl_basic_set_copy(src->node[i].bounds);
3492 dst->node[j].max = isl_vec_copy(src->node[i].max);
3493 dst->n++;
3495 if (!dst->node[j].space || !dst->node[j].sched)
3496 return isl_stat_error;
3497 if (dst->node[j].compressed &&
3498 (!dst->node[j].hull || !dst->node[j].compress ||
3499 !dst->node[j].decompress))
3500 return isl_stat_error;
3503 return isl_stat_ok;
3506 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3507 * to the dst dependence graph.
3508 * If the source or destination node of the edge is not in the destination
3509 * graph, then it must be a backward proximity edge and it should simply
3510 * be ignored.
3512 static isl_stat copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
3513 struct isl_sched_graph *src,
3514 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
3516 int i;
3518 dst->n_edge = 0;
3519 for (i = 0; i < src->n_edge; ++i) {
3520 struct isl_sched_edge *edge = &src->edge[i];
3521 isl_map *map;
3522 isl_union_map *tagged_condition;
3523 isl_union_map *tagged_validity;
3524 struct isl_sched_node *dst_src, *dst_dst;
3526 if (!edge_pred(edge, data))
3527 continue;
3529 if (isl_map_plain_is_empty(edge->map))
3530 continue;
3532 dst_src = graph_find_node(ctx, dst, edge->src->space);
3533 dst_dst = graph_find_node(ctx, dst, edge->dst->space);
3534 if (!dst_src || !dst_dst)
3535 return isl_stat_error;
3536 if (!is_node(dst, dst_src) || !is_node(dst, dst_dst)) {
3537 if (is_validity(edge) || is_conditional_validity(edge))
3538 isl_die(ctx, isl_error_internal,
3539 "backward (conditional) validity edge",
3540 return isl_stat_error);
3541 continue;
3544 map = isl_map_copy(edge->map);
3545 tagged_condition = isl_union_map_copy(edge->tagged_condition);
3546 tagged_validity = isl_union_map_copy(edge->tagged_validity);
3548 dst->edge[dst->n_edge].src = dst_src;
3549 dst->edge[dst->n_edge].dst = dst_dst;
3550 dst->edge[dst->n_edge].map = map;
3551 dst->edge[dst->n_edge].tagged_condition = tagged_condition;
3552 dst->edge[dst->n_edge].tagged_validity = tagged_validity;
3553 dst->edge[dst->n_edge].types = edge->types;
3554 dst->n_edge++;
3556 if (edge->tagged_condition && !tagged_condition)
3557 return isl_stat_error;
3558 if (edge->tagged_validity && !tagged_validity)
3559 return isl_stat_error;
3561 if (graph_edge_tables_add(ctx, dst,
3562 &dst->edge[dst->n_edge - 1]) < 0)
3563 return isl_stat_error;
3566 return isl_stat_ok;
3569 /* Compute the maximal number of variables over all nodes.
3570 * This is the maximal number of linearly independent schedule
3571 * rows that we need to compute.
3572 * Just in case we end up in a part of the dependence graph
3573 * with only lower-dimensional domains, we make sure we will
3574 * compute the required amount of extra linearly independent rows.
3576 static int compute_maxvar(struct isl_sched_graph *graph)
3578 int i;
3580 graph->maxvar = 0;
3581 for (i = 0; i < graph->n; ++i) {
3582 struct isl_sched_node *node = &graph->node[i];
3583 int nvar;
3585 if (node_update_vmap(node) < 0)
3586 return -1;
3587 nvar = node->nvar + graph->n_row - node->rank;
3588 if (nvar > graph->maxvar)
3589 graph->maxvar = nvar;
3592 return 0;
3595 /* Extract the subgraph of "graph" that consists of the nodes satisfying
3596 * "node_pred" and the edges satisfying "edge_pred" and store
3597 * the result in "sub".
3599 static isl_stat extract_sub_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
3600 int (*node_pred)(struct isl_sched_node *node, int data),
3601 int (*edge_pred)(struct isl_sched_edge *edge, int data),
3602 int data, struct isl_sched_graph *sub)
3604 int i, n = 0, n_edge = 0;
3605 int t;
3607 for (i = 0; i < graph->n; ++i)
3608 if (node_pred(&graph->node[i], data))
3609 ++n;
3610 for (i = 0; i < graph->n_edge; ++i)
3611 if (edge_pred(&graph->edge[i], data))
3612 ++n_edge;
3613 if (graph_alloc(ctx, sub, n, n_edge) < 0)
3614 return isl_stat_error;
3615 sub->root = graph->root;
3616 if (copy_nodes(sub, graph, node_pred, data) < 0)
3617 return isl_stat_error;
3618 if (graph_init_table(ctx, sub) < 0)
3619 return isl_stat_error;
3620 for (t = 0; t <= isl_edge_last; ++t)
3621 sub->max_edge[t] = graph->max_edge[t];
3622 if (graph_init_edge_tables(ctx, sub) < 0)
3623 return isl_stat_error;
3624 if (copy_edges(ctx, sub, graph, edge_pred, data) < 0)
3625 return isl_stat_error;
3626 sub->n_row = graph->n_row;
3627 sub->max_row = graph->max_row;
3628 sub->n_total_row = graph->n_total_row;
3629 sub->band_start = graph->band_start;
3631 return isl_stat_ok;
3634 static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
3635 struct isl_sched_graph *graph);
3636 static __isl_give isl_schedule_node *compute_schedule_wcc(
3637 isl_schedule_node *node, struct isl_sched_graph *graph);
3639 /* Compute a schedule for a subgraph of "graph". In particular, for
3640 * the graph composed of nodes that satisfy node_pred and edges that
3641 * that satisfy edge_pred.
3642 * If the subgraph is known to consist of a single component, then wcc should
3643 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3644 * Otherwise, we call compute_schedule, which will check whether the subgraph
3645 * is connected.
3647 * The schedule is inserted at "node" and the updated schedule node
3648 * is returned.
3650 static __isl_give isl_schedule_node *compute_sub_schedule(
3651 __isl_take isl_schedule_node *node, isl_ctx *ctx,
3652 struct isl_sched_graph *graph,
3653 int (*node_pred)(struct isl_sched_node *node, int data),
3654 int (*edge_pred)(struct isl_sched_edge *edge, int data),
3655 int data, int wcc)
3657 struct isl_sched_graph split = { 0 };
3659 if (extract_sub_graph(ctx, graph, node_pred, edge_pred, data,
3660 &split) < 0)
3661 goto error;
3663 if (wcc)
3664 node = compute_schedule_wcc(node, &split);
3665 else
3666 node = compute_schedule(node, &split);
3668 graph_free(ctx, &split);
3669 return node;
3670 error:
3671 graph_free(ctx, &split);
3672 return isl_schedule_node_free(node);
3675 static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
3677 return edge->src->scc == scc && edge->dst->scc == scc;
3680 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
3682 return edge->dst->scc <= scc;
3685 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
3687 return edge->src->scc >= scc;
3690 /* Reset the current band by dropping all its schedule rows.
3692 static isl_stat reset_band(struct isl_sched_graph *graph)
3694 int i;
3695 int drop;
3697 drop = graph->n_total_row - graph->band_start;
3698 graph->n_total_row -= drop;
3699 graph->n_row -= drop;
3701 for (i = 0; i < graph->n; ++i) {
3702 struct isl_sched_node *node = &graph->node[i];
3704 isl_map_free(node->sched_map);
3705 node->sched_map = NULL;
3707 node->sched = isl_mat_drop_rows(node->sched,
3708 graph->band_start, drop);
3710 if (!node->sched)
3711 return isl_stat_error;
3714 return isl_stat_ok;
3717 /* Split the current graph into two parts and compute a schedule for each
3718 * part individually. In particular, one part consists of all SCCs up
3719 * to and including graph->src_scc, while the other part contains the other
3720 * SCCs. The split is enforced by a sequence node inserted at position "node"
3721 * in the schedule tree. Return the updated schedule node.
3722 * If either of these two parts consists of a sequence, then it is spliced
3723 * into the sequence containing the two parts.
3725 * The current band is reset. It would be possible to reuse
3726 * the previously computed rows as the first rows in the next
3727 * band, but recomputing them may result in better rows as we are looking
3728 * at a smaller part of the dependence graph.
3730 static __isl_give isl_schedule_node *compute_split_schedule(
3731 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3733 int is_seq;
3734 isl_ctx *ctx;
3735 isl_union_set_list *filters;
3737 if (!node)
3738 return NULL;
3740 if (reset_band(graph) < 0)
3741 return isl_schedule_node_free(node);
3743 next_band(graph);
3745 ctx = isl_schedule_node_get_ctx(node);
3746 filters = extract_split(ctx, graph);
3747 node = isl_schedule_node_insert_sequence(node, filters);
3748 node = isl_schedule_node_child(node, 1);
3749 node = isl_schedule_node_child(node, 0);
3751 node = compute_sub_schedule(node, ctx, graph,
3752 &node_scc_at_least, &edge_src_scc_at_least,
3753 graph->src_scc + 1, 0);
3754 is_seq = isl_schedule_node_get_type(node) == isl_schedule_node_sequence;
3755 node = isl_schedule_node_parent(node);
3756 node = isl_schedule_node_parent(node);
3757 if (is_seq)
3758 node = isl_schedule_node_sequence_splice_child(node, 1);
3759 node = isl_schedule_node_child(node, 0);
3760 node = isl_schedule_node_child(node, 0);
3761 node = compute_sub_schedule(node, ctx, graph,
3762 &node_scc_at_most, &edge_dst_scc_at_most,
3763 graph->src_scc, 0);
3764 is_seq = isl_schedule_node_get_type(node) == isl_schedule_node_sequence;
3765 node = isl_schedule_node_parent(node);
3766 node = isl_schedule_node_parent(node);
3767 if (is_seq)
3768 node = isl_schedule_node_sequence_splice_child(node, 0);
3770 return node;
3773 /* Insert a band node at position "node" in the schedule tree corresponding
3774 * to the current band in "graph". Mark the band node permutable
3775 * if "permutable" is set.
3776 * The partial schedules and the coincidence property are extracted
3777 * from the graph nodes.
3778 * Return the updated schedule node.
3780 static __isl_give isl_schedule_node *insert_current_band(
3781 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
3782 int permutable)
3784 int i;
3785 int start, end, n;
3786 isl_multi_aff *ma;
3787 isl_multi_pw_aff *mpa;
3788 isl_multi_union_pw_aff *mupa;
3790 if (!node)
3791 return NULL;
3793 if (graph->n < 1)
3794 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
3795 "graph should have at least one node",
3796 return isl_schedule_node_free(node));
3798 start = graph->band_start;
3799 end = graph->n_total_row;
3800 n = end - start;
3802 ma = node_extract_partial_schedule_multi_aff(&graph->node[0], start, n);
3803 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3804 mupa = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3806 for (i = 1; i < graph->n; ++i) {
3807 isl_multi_union_pw_aff *mupa_i;
3809 ma = node_extract_partial_schedule_multi_aff(&graph->node[i],
3810 start, n);
3811 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3812 mupa_i = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3813 mupa = isl_multi_union_pw_aff_union_add(mupa, mupa_i);
3815 node = isl_schedule_node_insert_partial_schedule(node, mupa);
3817 for (i = 0; i < n; ++i)
3818 node = isl_schedule_node_band_member_set_coincident(node, i,
3819 graph->node[0].coincident[start + i]);
3820 node = isl_schedule_node_band_set_permutable(node, permutable);
3822 return node;
3825 /* Update the dependence relations based on the current schedule,
3826 * add the current band to "node" and then continue with the computation
3827 * of the next band.
3828 * Return the updated schedule node.
3830 static __isl_give isl_schedule_node *compute_next_band(
3831 __isl_take isl_schedule_node *node,
3832 struct isl_sched_graph *graph, int permutable)
3834 isl_ctx *ctx;
3836 if (!node)
3837 return NULL;
3839 ctx = isl_schedule_node_get_ctx(node);
3840 if (update_edges(ctx, graph) < 0)
3841 return isl_schedule_node_free(node);
3842 node = insert_current_band(node, graph, permutable);
3843 next_band(graph);
3845 node = isl_schedule_node_child(node, 0);
3846 node = compute_schedule(node, graph);
3847 node = isl_schedule_node_parent(node);
3849 return node;
3852 /* Add the constraints "coef" derived from an edge from "node" to itself
3853 * to graph->lp in order to respect the dependences and to try and carry them.
3854 * "pos" is the sequence number of the edge that needs to be carried.
3855 * "coef" represents general constraints on coefficients (c_0, c_x)
3856 * of valid constraints for (y - x) with x and y instances of the node.
3858 * The constraints added to graph->lp need to enforce
3860 * (c_j_0 + c_j_x y) - (c_j_0 + c_j_x x)
3861 * = c_j_x (y - x) >= e_i
3863 * for each (x,y) in the dependence relation of the edge.
3864 * That is, (-e_i, c_j_x) needs to be plugged in for (c_0, c_x),
3865 * taking into account that each coefficient in c_j_x is represented
3866 * as a pair of non-negative coefficients.
3868 static isl_stat add_intra_constraints(struct isl_sched_graph *graph,
3869 struct isl_sched_node *node, __isl_take isl_basic_set *coef, int pos)
3871 int offset;
3872 isl_ctx *ctx;
3873 isl_dim_map *dim_map;
3875 if (!coef)
3876 return isl_stat_error;
3878 ctx = isl_basic_set_get_ctx(coef);
3879 offset = coef_var_offset(coef);
3880 dim_map = intra_dim_map(ctx, graph, node, offset, 1);
3881 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3882 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
3884 return isl_stat_ok;
3887 /* Add the constraints "coef" derived from an edge from "src" to "dst"
3888 * to graph->lp in order to respect the dependences and to try and carry them.
3889 * "pos" is the sequence number of the edge that needs to be carried or
3890 * -1 if no attempt should be made to carry the dependences.
3891 * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y)
3892 * of valid constraints for (x, y) with x and y instances of "src" and "dst".
3894 * The constraints added to graph->lp need to enforce
3896 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3898 * for each (x,y) in the dependence relation of the edge or
3900 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= 0
3902 * if pos is -1.
3903 * That is,
3904 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3905 * or
3906 * (c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3907 * needs to be plugged in for (c_0, c_n, c_x, c_y),
3908 * taking into account that each coefficient in c_j_x and c_k_x is represented
3909 * as a pair of non-negative coefficients.
3911 static isl_stat add_inter_constraints(struct isl_sched_graph *graph,
3912 struct isl_sched_node *src, struct isl_sched_node *dst,
3913 __isl_take isl_basic_set *coef, int pos)
3915 int offset;
3916 isl_ctx *ctx;
3917 isl_dim_map *dim_map;
3919 if (!coef)
3920 return isl_stat_error;
3922 ctx = isl_basic_set_get_ctx(coef);
3923 offset = coef_var_offset(coef);
3924 dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1);
3925 if (pos >= 0)
3926 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3927 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
3929 return isl_stat_ok;
3932 /* Data structure for keeping track of the data needed
3933 * to exploit non-trivial lineality spaces.
3935 * "any_non_trivial" is true if there are any non-trivial lineality spaces.
3936 * If "any_non_trivial" is not true, then "equivalent" and "mask" may be NULL.
3937 * "equivalent" connects instances to other instances on the same line(s).
3938 * "mask" contains the domain spaces of "equivalent".
3939 * Any instance set not in "mask" does not have a non-trivial lineality space.
3941 struct isl_exploit_lineality_data {
3942 isl_bool any_non_trivial;
3943 isl_union_map *equivalent;
3944 isl_union_set *mask;
3947 /* Data structure collecting information used during the construction
3948 * of an LP for carrying dependences.
3950 * "intra" is a sequence of coefficient constraints for intra-node edges.
3951 * "inter" is a sequence of coefficient constraints for inter-node edges.
3952 * "lineality" contains data used to exploit non-trivial lineality spaces.
3954 struct isl_carry {
3955 isl_basic_set_list *intra;
3956 isl_basic_set_list *inter;
3957 struct isl_exploit_lineality_data lineality;
3960 /* Free all the data stored in "carry".
3962 static void isl_carry_clear(struct isl_carry *carry)
3964 isl_basic_set_list_free(carry->intra);
3965 isl_basic_set_list_free(carry->inter);
3966 isl_union_map_free(carry->lineality.equivalent);
3967 isl_union_set_free(carry->lineality.mask);
3970 /* Return a pointer to the node in "graph" that lives in "space".
3971 * If the requested node has been compressed, then "space"
3972 * corresponds to the compressed space.
3973 * The graph is assumed to have such a node.
3974 * Return NULL in case of error.
3976 * First try and see if "space" is the space of an uncompressed node.
3977 * If so, return that node.
3978 * Otherwise, "space" was constructed by construct_compressed_id and
3979 * contains a user pointer pointing to the node in the tuple id.
3980 * However, this node belongs to the original dependence graph.
3981 * If "graph" is a subgraph of this original dependence graph,
3982 * then the node with the same space still needs to be looked up
3983 * in the current graph.
3985 static struct isl_sched_node *graph_find_compressed_node(isl_ctx *ctx,
3986 struct isl_sched_graph *graph, __isl_keep isl_space *space)
3988 isl_id *id;
3989 struct isl_sched_node *node;
3991 if (!space)
3992 return NULL;
3994 node = graph_find_node(ctx, graph, space);
3995 if (!node)
3996 return NULL;
3997 if (is_node(graph, node))
3998 return node;
4000 id = isl_space_get_tuple_id(space, isl_dim_set);
4001 node = isl_id_get_user(id);
4002 isl_id_free(id);
4004 if (!node)
4005 return NULL;
4007 if (!is_node(graph->root, node))
4008 isl_die(ctx, isl_error_internal,
4009 "space points to invalid node", return NULL);
4010 if (graph != graph->root)
4011 node = graph_find_node(ctx, graph, node->space);
4012 if (!is_node(graph, node))
4013 isl_die(ctx, isl_error_internal,
4014 "unable to find node", return NULL);
4016 return node;
4019 /* Internal data structure for add_all_constraints.
4021 * "graph" is the schedule constraint graph for which an LP problem
4022 * is being constructed.
4023 * "carry_inter" indicates whether inter-node edges should be carried.
4024 * "pos" is the position of the next edge that needs to be carried.
4026 struct isl_add_all_constraints_data {
4027 isl_ctx *ctx;
4028 struct isl_sched_graph *graph;
4029 int carry_inter;
4030 int pos;
4033 /* Add the constraints "coef" derived from an edge from a node to itself
4034 * to data->graph->lp in order to respect the dependences and
4035 * to try and carry them.
4037 * The space of "coef" is of the form
4039 * coefficients[[c_cst] -> S[c_x]]
4041 * with S[c_x] the (compressed) space of the node.
4042 * Extract the node from the space and call add_intra_constraints.
4044 static isl_stat lp_add_intra(__isl_take isl_basic_set *coef, void *user)
4046 struct isl_add_all_constraints_data *data = user;
4047 isl_space *space;
4048 struct isl_sched_node *node;
4050 space = isl_basic_set_get_space(coef);
4051 space = isl_space_range(isl_space_unwrap(space));
4052 node = graph_find_compressed_node(data->ctx, data->graph, space);
4053 isl_space_free(space);
4054 return add_intra_constraints(data->graph, node, coef, data->pos++);
4057 /* Add the constraints "coef" derived from an edge from a node j
4058 * to a node k to data->graph->lp in order to respect the dependences and
4059 * to try and carry them (provided data->carry_inter is set).
4061 * The space of "coef" is of the form
4063 * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]]
4065 * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes.
4066 * Extract the nodes from the space and call add_inter_constraints.
4068 static isl_stat lp_add_inter(__isl_take isl_basic_set *coef, void *user)
4070 struct isl_add_all_constraints_data *data = user;
4071 isl_space *space, *dom;
4072 struct isl_sched_node *src, *dst;
4073 int pos;
4075 space = isl_basic_set_get_space(coef);
4076 space = isl_space_unwrap(isl_space_range(isl_space_unwrap(space)));
4077 dom = isl_space_domain(isl_space_copy(space));
4078 src = graph_find_compressed_node(data->ctx, data->graph, dom);
4079 isl_space_free(dom);
4080 space = isl_space_range(space);
4081 dst = graph_find_compressed_node(data->ctx, data->graph, space);
4082 isl_space_free(space);
4084 pos = data->carry_inter ? data->pos++ : -1;
4085 return add_inter_constraints(data->graph, src, dst, coef, pos);
4088 /* Add constraints to graph->lp that force all (conditional) validity
4089 * dependences to be respected and attempt to carry them.
4090 * "intra" is the sequence of coefficient constraints for intra-node edges.
4091 * "inter" is the sequence of coefficient constraints for inter-node edges.
4092 * "carry_inter" indicates whether inter-node edges should be carried or
4093 * only respected.
4095 static isl_stat add_all_constraints(isl_ctx *ctx, struct isl_sched_graph *graph,
4096 __isl_keep isl_basic_set_list *intra,
4097 __isl_keep isl_basic_set_list *inter, int carry_inter)
4099 struct isl_add_all_constraints_data data = { ctx, graph, carry_inter };
4101 data.pos = 0;
4102 if (isl_basic_set_list_foreach(intra, &lp_add_intra, &data) < 0)
4103 return isl_stat_error;
4104 if (isl_basic_set_list_foreach(inter, &lp_add_inter, &data) < 0)
4105 return isl_stat_error;
4106 return isl_stat_ok;
4109 /* Internal data structure for count_all_constraints
4110 * for keeping track of the number of equality and inequality constraints.
4112 struct isl_sched_count {
4113 int n_eq;
4114 int n_ineq;
4117 /* Add the number of equality and inequality constraints of "bset"
4118 * to data->n_eq and data->n_ineq.
4120 static isl_stat bset_update_count(__isl_take isl_basic_set *bset, void *user)
4122 struct isl_sched_count *data = user;
4124 return update_count(bset, 1, &data->n_eq, &data->n_ineq);
4127 /* Count the number of equality and inequality constraints
4128 * that will be added to the carry_lp problem.
4129 * We count each edge exactly once.
4130 * "intra" is the sequence of coefficient constraints for intra-node edges.
4131 * "inter" is the sequence of coefficient constraints for inter-node edges.
4133 static isl_stat count_all_constraints(__isl_keep isl_basic_set_list *intra,
4134 __isl_keep isl_basic_set_list *inter, int *n_eq, int *n_ineq)
4136 struct isl_sched_count data;
4138 data.n_eq = data.n_ineq = 0;
4139 if (isl_basic_set_list_foreach(inter, &bset_update_count, &data) < 0)
4140 return isl_stat_error;
4141 if (isl_basic_set_list_foreach(intra, &bset_update_count, &data) < 0)
4142 return isl_stat_error;
4144 *n_eq = data.n_eq;
4145 *n_ineq = data.n_ineq;
4147 return isl_stat_ok;
4150 /* Construct an LP problem for finding schedule coefficients
4151 * such that the schedule carries as many validity dependences as possible.
4152 * In particular, for each dependence i, we bound the dependence distance
4153 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
4154 * of all e_i's. Dependences with e_i = 0 in the solution are simply
4155 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
4156 * "intra" is the sequence of coefficient constraints for intra-node edges.
4157 * "inter" is the sequence of coefficient constraints for inter-node edges.
4158 * "n_edge" is the total number of edges.
4159 * "carry_inter" indicates whether inter-node edges should be carried or
4160 * only respected. That is, if "carry_inter" is not set, then
4161 * no e_i variables are introduced for the inter-node edges.
4163 * All variables of the LP are non-negative. The actual coefficients
4164 * may be negative, so each coefficient is represented as the difference
4165 * of two non-negative variables. The negative part always appears
4166 * immediately before the positive part.
4167 * Other than that, the variables have the following order
4169 * - sum of (1 - e_i) over all edges
4170 * - sum of all c_n coefficients
4171 * (unconstrained when computing non-parametric schedules)
4172 * - sum of positive and negative parts of all c_x coefficients
4173 * - for each edge
4174 * - e_i
4175 * - for each node
4176 * - positive and negative parts of c_i_x, in opposite order
4177 * - c_i_n (if parametric)
4178 * - c_i_0
4180 * The constraints are those from the (validity) edges plus three equalities
4181 * to express the sums and n_edge inequalities to express e_i <= 1.
4183 static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
4184 int n_edge, __isl_keep isl_basic_set_list *intra,
4185 __isl_keep isl_basic_set_list *inter, int carry_inter)
4187 int i;
4188 int k;
4189 isl_space *dim;
4190 unsigned total;
4191 int n_eq, n_ineq;
4193 total = 3 + n_edge;
4194 for (i = 0; i < graph->n; ++i) {
4195 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
4196 node->start = total;
4197 total += 1 + node->nparam + 2 * node->nvar;
4200 if (count_all_constraints(intra, inter, &n_eq, &n_ineq) < 0)
4201 return isl_stat_error;
4203 dim = isl_space_set_alloc(ctx, 0, total);
4204 isl_basic_set_free(graph->lp);
4205 n_eq += 3;
4206 n_ineq += n_edge;
4207 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
4208 graph->lp = isl_basic_set_set_rational(graph->lp);
4210 k = isl_basic_set_alloc_equality(graph->lp);
4211 if (k < 0)
4212 return isl_stat_error;
4213 isl_seq_clr(graph->lp->eq[k], 1 + total);
4214 isl_int_set_si(graph->lp->eq[k][0], -n_edge);
4215 isl_int_set_si(graph->lp->eq[k][1], 1);
4216 for (i = 0; i < n_edge; ++i)
4217 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
4219 if (add_param_sum_constraint(graph, 1) < 0)
4220 return isl_stat_error;
4221 if (add_var_sum_constraint(graph, 2) < 0)
4222 return isl_stat_error;
4224 for (i = 0; i < n_edge; ++i) {
4225 k = isl_basic_set_alloc_inequality(graph->lp);
4226 if (k < 0)
4227 return isl_stat_error;
4228 isl_seq_clr(graph->lp->ineq[k], 1 + total);
4229 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
4230 isl_int_set_si(graph->lp->ineq[k][0], 1);
4233 if (add_all_constraints(ctx, graph, intra, inter, carry_inter) < 0)
4234 return isl_stat_error;
4236 return isl_stat_ok;
4239 static __isl_give isl_schedule_node *compute_component_schedule(
4240 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
4241 int wcc);
4243 /* If the schedule_split_scaled option is set and if the linear
4244 * parts of the scheduling rows for all nodes in the graphs have
4245 * a non-trivial common divisor, then remove this
4246 * common divisor from the linear part.
4247 * Otherwise, insert a band node directly and continue with
4248 * the construction of the schedule.
4250 * If a non-trivial common divisor is found, then
4251 * the linear part is reduced and the remainder is ignored.
4252 * The pieces of the graph that are assigned different remainders
4253 * form (groups of) strongly connected components within
4254 * the scaled down band. If needed, they can therefore
4255 * be ordered along this remainder in a sequence node.
4256 * However, this ordering is not enforced here in order to allow
4257 * the scheduler to combine some of the strongly connected components.
4259 static __isl_give isl_schedule_node *split_scaled(
4260 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
4262 int i;
4263 int row;
4264 isl_ctx *ctx;
4265 isl_int gcd, gcd_i;
4267 if (!node)
4268 return NULL;
4270 ctx = isl_schedule_node_get_ctx(node);
4271 if (!ctx->opt->schedule_split_scaled)
4272 return compute_next_band(node, graph, 0);
4273 if (graph->n <= 1)
4274 return compute_next_band(node, graph, 0);
4276 isl_int_init(gcd);
4277 isl_int_init(gcd_i);
4279 isl_int_set_si(gcd, 0);
4281 row = isl_mat_rows(graph->node[0].sched) - 1;
4283 for (i = 0; i < graph->n; ++i) {
4284 struct isl_sched_node *node = &graph->node[i];
4285 int cols = isl_mat_cols(node->sched);
4287 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
4288 isl_int_gcd(gcd, gcd, gcd_i);
4291 isl_int_clear(gcd_i);
4293 if (isl_int_cmp_si(gcd, 1) <= 0) {
4294 isl_int_clear(gcd);
4295 return compute_next_band(node, graph, 0);
4298 for (i = 0; i < graph->n; ++i) {
4299 struct isl_sched_node *node = &graph->node[i];
4301 isl_int_fdiv_q(node->sched->row[row][0],
4302 node->sched->row[row][0], gcd);
4303 isl_int_mul(node->sched->row[row][0],
4304 node->sched->row[row][0], gcd);
4305 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
4306 if (!node->sched)
4307 goto error;
4310 isl_int_clear(gcd);
4312 return compute_next_band(node, graph, 0);
4313 error:
4314 isl_int_clear(gcd);
4315 return isl_schedule_node_free(node);
4318 /* Is the schedule row "sol" trivial on node "node"?
4319 * That is, is the solution zero on the dimensions linearly independent of
4320 * the previously found solutions?
4321 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
4323 * Each coefficient is represented as the difference between
4324 * two non-negative values in "sol".
4325 * We construct the schedule row s and check if it is linearly
4326 * independent of previously computed schedule rows
4327 * by computing T s, with T the linear combinations that are zero
4328 * on linearly dependent schedule rows.
4329 * If the result consists of all zeros, then the solution is trivial.
4331 static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
4333 int trivial;
4334 isl_vec *node_sol;
4336 if (!sol)
4337 return -1;
4338 if (node->nvar == node->rank)
4339 return 0;
4341 node_sol = extract_var_coef(node, sol);
4342 node_sol = isl_mat_vec_product(isl_mat_copy(node->indep), node_sol);
4343 if (!node_sol)
4344 return -1;
4346 trivial = isl_seq_first_non_zero(node_sol->el,
4347 node->nvar - node->rank) == -1;
4349 isl_vec_free(node_sol);
4351 return trivial;
4354 /* Is the schedule row "sol" trivial on any node where it should
4355 * not be trivial?
4356 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4358 static int is_any_trivial(struct isl_sched_graph *graph,
4359 __isl_keep isl_vec *sol)
4361 int i;
4363 for (i = 0; i < graph->n; ++i) {
4364 struct isl_sched_node *node = &graph->node[i];
4365 int trivial;
4367 if (!needs_row(graph, node))
4368 continue;
4369 trivial = is_trivial(node, sol);
4370 if (trivial < 0 || trivial)
4371 return trivial;
4374 return 0;
4377 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
4378 * If so, return the position of the coalesced dimension.
4379 * Otherwise, return node->nvar or -1 on error.
4381 * In particular, look for pairs of coefficients c_i and c_j such that
4382 * |c_j/c_i| > ceil(size_i/2), i.e., |c_j| > |c_i * ceil(size_i/2)|.
4383 * If any such pair is found, then return i.
4384 * If size_i is infinity, then no check on c_i needs to be performed.
4386 static int find_node_coalescing(struct isl_sched_node *node,
4387 __isl_keep isl_vec *sol)
4389 int i, j;
4390 isl_int max;
4391 isl_vec *csol;
4393 if (node->nvar <= 1)
4394 return node->nvar;
4396 csol = extract_var_coef(node, sol);
4397 if (!csol)
4398 return -1;
4399 isl_int_init(max);
4400 for (i = 0; i < node->nvar; ++i) {
4401 isl_val *v;
4403 if (isl_int_is_zero(csol->el[i]))
4404 continue;
4405 v = isl_multi_val_get_val(node->sizes, i);
4406 if (!v)
4407 goto error;
4408 if (!isl_val_is_int(v)) {
4409 isl_val_free(v);
4410 continue;
4412 v = isl_val_div_ui(v, 2);
4413 v = isl_val_ceil(v);
4414 if (!v)
4415 goto error;
4416 isl_int_mul(max, v->n, csol->el[i]);
4417 isl_val_free(v);
4419 for (j = 0; j < node->nvar; ++j) {
4420 if (j == i)
4421 continue;
4422 if (isl_int_abs_gt(csol->el[j], max))
4423 break;
4425 if (j < node->nvar)
4426 break;
4429 isl_int_clear(max);
4430 isl_vec_free(csol);
4431 return i;
4432 error:
4433 isl_int_clear(max);
4434 isl_vec_free(csol);
4435 return -1;
4438 /* Force the schedule coefficient at position "pos" of "node" to be zero
4439 * in "tl".
4440 * The coefficient is encoded as the difference between two non-negative
4441 * variables. Force these two variables to have the same value.
4443 static __isl_give isl_tab_lexmin *zero_out_node_coef(
4444 __isl_take isl_tab_lexmin *tl, struct isl_sched_node *node, int pos)
4446 int dim;
4447 isl_ctx *ctx;
4448 isl_vec *eq;
4450 ctx = isl_space_get_ctx(node->space);
4451 dim = isl_tab_lexmin_dim(tl);
4452 if (dim < 0)
4453 return isl_tab_lexmin_free(tl);
4454 eq = isl_vec_alloc(ctx, 1 + dim);
4455 eq = isl_vec_clr(eq);
4456 if (!eq)
4457 return isl_tab_lexmin_free(tl);
4459 pos = 1 + node_var_coef_pos(node, pos);
4460 isl_int_set_si(eq->el[pos], 1);
4461 isl_int_set_si(eq->el[pos + 1], -1);
4462 tl = isl_tab_lexmin_add_eq(tl, eq->el);
4463 isl_vec_free(eq);
4465 return tl;
4468 /* Return the lexicographically smallest rational point in the basic set
4469 * from which "tl" was constructed, double checking that this input set
4470 * was not empty.
4472 static __isl_give isl_vec *non_empty_solution(__isl_keep isl_tab_lexmin *tl)
4474 isl_vec *sol;
4476 sol = isl_tab_lexmin_get_solution(tl);
4477 if (!sol)
4478 return NULL;
4479 if (sol->size == 0)
4480 isl_die(isl_vec_get_ctx(sol), isl_error_internal,
4481 "error in schedule construction",
4482 return isl_vec_free(sol));
4483 return sol;
4486 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4487 * carry any of the "n_edge" groups of dependences?
4488 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4489 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4490 * by the edge are carried by the solution.
4491 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4492 * one of those is carried.
4494 * Note that despite the fact that the problem is solved using a rational
4495 * solver, the solution is guaranteed to be integral.
4496 * Specifically, the dependence distance lower bounds e_i (and therefore
4497 * also their sum) are integers. See Lemma 5 of [1].
4499 * Any potential denominator of the sum is cleared by this function.
4500 * The denominator is not relevant for any of the other elements
4501 * in the solution.
4503 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4504 * Problem, Part II: Multi-Dimensional Time.
4505 * In Intl. Journal of Parallel Programming, 1992.
4507 static int carries_dependences(__isl_keep isl_vec *sol, int n_edge)
4509 isl_int_divexact(sol->el[1], sol->el[1], sol->el[0]);
4510 isl_int_set_si(sol->el[0], 1);
4511 return isl_int_cmp_si(sol->el[1], n_edge) < 0;
4514 /* Return the lexicographically smallest rational point in "lp",
4515 * assuming that all variables are non-negative and performing some
4516 * additional sanity checks.
4517 * If "want_integral" is set, then compute the lexicographically smallest
4518 * integer point instead.
4519 * In particular, "lp" should not be empty by construction.
4520 * Double check that this is the case.
4521 * If dependences are not carried for any of the "n_edge" edges,
4522 * then return an empty vector.
4524 * If the schedule_treat_coalescing option is set and
4525 * if the computed schedule performs loop coalescing on a given node,
4526 * i.e., if it is of the form
4528 * c_i i + c_j j + ...
4530 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4531 * to cut out this solution. Repeat this process until no more loop
4532 * coalescing occurs or until no more dependences can be carried.
4533 * In the latter case, revert to the previously computed solution.
4535 * If the caller requests an integral solution and if coalescing should
4536 * be treated, then perform the coalescing treatment first as
4537 * an integral solution computed before coalescing treatment
4538 * would carry the same number of edges and would therefore probably
4539 * also be coalescing.
4541 * To allow the coalescing treatment to be performed first,
4542 * the initial solution is allowed to be rational and it is only
4543 * cut out (if needed) in the next iteration, if no coalescing measures
4544 * were taken.
4546 static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph,
4547 __isl_take isl_basic_set *lp, int n_edge, int want_integral)
4549 int i, pos, cut;
4550 isl_ctx *ctx;
4551 isl_tab_lexmin *tl;
4552 isl_vec *sol = NULL, *prev;
4553 int treat_coalescing;
4554 int try_again;
4556 if (!lp)
4557 return NULL;
4558 ctx = isl_basic_set_get_ctx(lp);
4559 treat_coalescing = isl_options_get_schedule_treat_coalescing(ctx);
4560 tl = isl_tab_lexmin_from_basic_set(lp);
4562 cut = 0;
4563 do {
4564 int integral;
4566 try_again = 0;
4567 if (cut)
4568 tl = isl_tab_lexmin_cut_to_integer(tl);
4569 prev = sol;
4570 sol = non_empty_solution(tl);
4571 if (!sol)
4572 goto error;
4574 integral = isl_int_is_one(sol->el[0]);
4575 if (!carries_dependences(sol, n_edge)) {
4576 if (!prev)
4577 prev = isl_vec_alloc(ctx, 0);
4578 isl_vec_free(sol);
4579 sol = prev;
4580 break;
4582 prev = isl_vec_free(prev);
4583 cut = want_integral && !integral;
4584 if (cut)
4585 try_again = 1;
4586 if (!treat_coalescing)
4587 continue;
4588 for (i = 0; i < graph->n; ++i) {
4589 struct isl_sched_node *node = &graph->node[i];
4591 pos = find_node_coalescing(node, sol);
4592 if (pos < 0)
4593 goto error;
4594 if (pos < node->nvar)
4595 break;
4597 if (i < graph->n) {
4598 try_again = 1;
4599 tl = zero_out_node_coef(tl, &graph->node[i], pos);
4600 cut = 0;
4602 } while (try_again);
4604 isl_tab_lexmin_free(tl);
4606 return sol;
4607 error:
4608 isl_tab_lexmin_free(tl);
4609 isl_vec_free(prev);
4610 isl_vec_free(sol);
4611 return NULL;
4614 /* If "edge" is an edge from a node to itself, then add the corresponding
4615 * dependence relation to "umap".
4616 * If "node" has been compressed, then the dependence relation
4617 * is also compressed first.
4619 static __isl_give isl_union_map *add_intra(__isl_take isl_union_map *umap,
4620 struct isl_sched_edge *edge)
4622 isl_map *map;
4623 struct isl_sched_node *node = edge->src;
4625 if (edge->src != edge->dst)
4626 return umap;
4628 map = isl_map_copy(edge->map);
4629 if (node->compressed) {
4630 map = isl_map_preimage_domain_multi_aff(map,
4631 isl_multi_aff_copy(node->decompress));
4632 map = isl_map_preimage_range_multi_aff(map,
4633 isl_multi_aff_copy(node->decompress));
4635 umap = isl_union_map_add_map(umap, map);
4636 return umap;
4639 /* If "edge" is an edge from a node to another node, then add the corresponding
4640 * dependence relation to "umap".
4641 * If the source or destination nodes of "edge" have been compressed,
4642 * then the dependence relation is also compressed first.
4644 static __isl_give isl_union_map *add_inter(__isl_take isl_union_map *umap,
4645 struct isl_sched_edge *edge)
4647 isl_map *map;
4649 if (edge->src == edge->dst)
4650 return umap;
4652 map = isl_map_copy(edge->map);
4653 if (edge->src->compressed)
4654 map = isl_map_preimage_domain_multi_aff(map,
4655 isl_multi_aff_copy(edge->src->decompress));
4656 if (edge->dst->compressed)
4657 map = isl_map_preimage_range_multi_aff(map,
4658 isl_multi_aff_copy(edge->dst->decompress));
4659 umap = isl_union_map_add_map(umap, map);
4660 return umap;
4663 /* Internal data structure used by union_drop_coalescing_constraints
4664 * to collect bounds on all relevant statements.
4666 * "graph" is the schedule constraint graph for which an LP problem
4667 * is being constructed.
4668 * "bounds" collects the bounds.
4670 struct isl_collect_bounds_data {
4671 isl_ctx *ctx;
4672 struct isl_sched_graph *graph;
4673 isl_union_set *bounds;
4676 /* Add the size bounds for the node with instance deltas in "set"
4677 * to data->bounds.
4679 static isl_stat collect_bounds(__isl_take isl_set *set, void *user)
4681 struct isl_collect_bounds_data *data = user;
4682 struct isl_sched_node *node;
4683 isl_space *space;
4684 isl_set *bounds;
4686 space = isl_set_get_space(set);
4687 isl_set_free(set);
4689 node = graph_find_compressed_node(data->ctx, data->graph, space);
4690 isl_space_free(space);
4692 bounds = isl_set_from_basic_set(get_size_bounds(node));
4693 data->bounds = isl_union_set_add_set(data->bounds, bounds);
4695 return isl_stat_ok;
4698 /* Drop some constraints from "delta" that could be exploited
4699 * to construct loop coalescing schedules.
4700 * In particular, drop those constraint that bound the difference
4701 * to the size of the domain.
4702 * Do this for each set/node in "delta" separately.
4703 * The parameters are assumed to have been projected out by the caller.
4705 static __isl_give isl_union_set *union_drop_coalescing_constraints(isl_ctx *ctx,
4706 struct isl_sched_graph *graph, __isl_take isl_union_set *delta)
4708 struct isl_collect_bounds_data data = { ctx, graph };
4710 data.bounds = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
4711 if (isl_union_set_foreach_set(delta, &collect_bounds, &data) < 0)
4712 data.bounds = isl_union_set_free(data.bounds);
4713 delta = isl_union_set_plain_gist(delta, data.bounds);
4715 return delta;
4718 /* Given a non-trivial lineality space "lineality", add the corresponding
4719 * universe set to data->mask and add a map from elements to
4720 * other elements along the lines in "lineality" to data->equivalent.
4721 * If this is the first time this function gets called
4722 * (data->any_non_trivial is still false), then set data->any_non_trivial and
4723 * initialize data->mask and data->equivalent.
4725 * In particular, if the lineality space is defined by equality constraints
4727 * E x = 0
4729 * then construct an affine mapping
4731 * f : x -> E x
4733 * and compute the equivalence relation of having the same image under f:
4735 * { x -> x' : E x = E x' }
4737 static isl_stat add_non_trivial_lineality(__isl_take isl_basic_set *lineality,
4738 struct isl_exploit_lineality_data *data)
4740 isl_mat *eq;
4741 isl_space *space;
4742 isl_set *univ;
4743 isl_multi_aff *ma;
4744 isl_multi_pw_aff *mpa;
4745 isl_map *map;
4746 int n;
4748 if (!lineality)
4749 return isl_stat_error;
4750 if (isl_basic_set_dim(lineality, isl_dim_div) != 0)
4751 isl_die(isl_basic_set_get_ctx(lineality), isl_error_internal,
4752 "local variables not allowed", goto error);
4754 space = isl_basic_set_get_space(lineality);
4755 if (!data->any_non_trivial) {
4756 data->equivalent = isl_union_map_empty(isl_space_copy(space));
4757 data->mask = isl_union_set_empty(isl_space_copy(space));
4759 data->any_non_trivial = isl_bool_true;
4761 univ = isl_set_universe(isl_space_copy(space));
4762 data->mask = isl_union_set_add_set(data->mask, univ);
4764 eq = isl_basic_set_extract_equalities(lineality);
4765 n = isl_mat_rows(eq);
4766 eq = isl_mat_insert_zero_rows(eq, 0, 1);
4767 eq = isl_mat_set_element_si(eq, 0, 0, 1);
4768 space = isl_space_from_domain(space);
4769 space = isl_space_add_dims(space, isl_dim_out, n);
4770 ma = isl_multi_aff_from_aff_mat(space, eq);
4771 mpa = isl_multi_pw_aff_from_multi_aff(ma);
4772 map = isl_multi_pw_aff_eq_map(mpa, isl_multi_pw_aff_copy(mpa));
4773 data->equivalent = isl_union_map_add_map(data->equivalent, map);
4775 isl_basic_set_free(lineality);
4776 return isl_stat_ok;
4777 error:
4778 isl_basic_set_free(lineality);
4779 return isl_stat_error;
4782 /* Check if the lineality space "set" is non-trivial (i.e., is not just
4783 * the origin or, in other words, satisfies a number of equality constraints
4784 * that is smaller than the dimension of the set).
4785 * If so, extend data->mask and data->equivalent accordingly.
4787 * The input should not have any local variables already, but
4788 * isl_set_remove_divs is called to make sure it does not.
4790 static isl_stat add_lineality(__isl_take isl_set *set, void *user)
4792 struct isl_exploit_lineality_data *data = user;
4793 isl_basic_set *hull;
4794 int dim, n_eq;
4796 set = isl_set_remove_divs(set);
4797 hull = isl_set_unshifted_simple_hull(set);
4798 dim = isl_basic_set_dim(hull, isl_dim_set);
4799 n_eq = isl_basic_set_n_equality(hull);
4800 if (!hull)
4801 return isl_stat_error;
4802 if (dim != n_eq)
4803 return add_non_trivial_lineality(hull, data);
4804 isl_basic_set_free(hull);
4805 return isl_stat_ok;
4808 /* Check if the difference set on intra-node schedule constraints "intra"
4809 * has any non-trivial lineality space.
4810 * If so, then extend the difference set to a difference set
4811 * on equivalent elements. That is, if "intra" is
4813 * { y - x : (x,y) \in V }
4815 * and elements are equivalent if they have the same image under f,
4816 * then return
4818 * { y' - x' : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4820 * or, since f is linear,
4822 * { y' - x' : (x,y) \in V and f(y - x) = f(y' - x') }
4824 * The results of the search for non-trivial lineality spaces is stored
4825 * in "data".
4827 static __isl_give isl_union_set *exploit_intra_lineality(
4828 __isl_take isl_union_set *intra,
4829 struct isl_exploit_lineality_data *data)
4831 isl_union_set *lineality;
4832 isl_union_set *uset;
4834 data->any_non_trivial = isl_bool_false;
4835 lineality = isl_union_set_copy(intra);
4836 lineality = isl_union_set_combined_lineality_space(lineality);
4837 if (isl_union_set_foreach_set(lineality, &add_lineality, data) < 0)
4838 data->any_non_trivial = isl_bool_error;
4839 isl_union_set_free(lineality);
4841 if (data->any_non_trivial < 0)
4842 return isl_union_set_free(intra);
4843 if (!data->any_non_trivial)
4844 return intra;
4846 uset = isl_union_set_copy(intra);
4847 intra = isl_union_set_subtract(intra, isl_union_set_copy(data->mask));
4848 uset = isl_union_set_apply(uset, isl_union_map_copy(data->equivalent));
4849 intra = isl_union_set_union(intra, uset);
4851 intra = isl_union_set_remove_divs(intra);
4853 return intra;
4856 /* If the difference set on intra-node schedule constraints was found to have
4857 * any non-trivial lineality space by exploit_intra_lineality,
4858 * as recorded in "data", then extend the inter-node
4859 * schedule constraints "inter" to schedule constraints on equivalent elements.
4860 * That is, if "inter" is V and
4861 * elements are equivalent if they have the same image under f, then return
4863 * { (x', y') : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4865 static __isl_give isl_union_map *exploit_inter_lineality(
4866 __isl_take isl_union_map *inter,
4867 struct isl_exploit_lineality_data *data)
4869 isl_union_map *umap;
4871 if (data->any_non_trivial < 0)
4872 return isl_union_map_free(inter);
4873 if (!data->any_non_trivial)
4874 return inter;
4876 umap = isl_union_map_copy(inter);
4877 inter = isl_union_map_subtract_range(inter,
4878 isl_union_set_copy(data->mask));
4879 umap = isl_union_map_apply_range(umap,
4880 isl_union_map_copy(data->equivalent));
4881 inter = isl_union_map_union(inter, umap);
4882 umap = isl_union_map_copy(inter);
4883 inter = isl_union_map_subtract_domain(inter,
4884 isl_union_set_copy(data->mask));
4885 umap = isl_union_map_apply_range(isl_union_map_copy(data->equivalent),
4886 umap);
4887 inter = isl_union_map_union(inter, umap);
4889 inter = isl_union_map_remove_divs(inter);
4891 return inter;
4894 /* For each (conditional) validity edge in "graph",
4895 * add the corresponding dependence relation using "add"
4896 * to a collection of dependence relations and return the result.
4897 * If "coincidence" is set, then coincidence edges are considered as well.
4899 static __isl_give isl_union_map *collect_validity(struct isl_sched_graph *graph,
4900 __isl_give isl_union_map *(*add)(__isl_take isl_union_map *umap,
4901 struct isl_sched_edge *edge), int coincidence)
4903 int i;
4904 isl_space *space;
4905 isl_union_map *umap;
4907 space = isl_space_copy(graph->node[0].space);
4908 umap = isl_union_map_empty(space);
4910 for (i = 0; i < graph->n_edge; ++i) {
4911 struct isl_sched_edge *edge = &graph->edge[i];
4913 if (!is_any_validity(edge) &&
4914 (!coincidence || !is_coincidence(edge)))
4915 continue;
4917 umap = add(umap, edge);
4920 return umap;
4923 /* Project out all parameters from "uset" and return the result.
4925 static __isl_give isl_union_set *union_set_drop_parameters(
4926 __isl_take isl_union_set *uset)
4928 unsigned nparam;
4930 nparam = isl_union_set_dim(uset, isl_dim_param);
4931 return isl_union_set_project_out(uset, isl_dim_param, 0, nparam);
4934 /* For each dependence relation on a (conditional) validity edge
4935 * from a node to itself,
4936 * construct the set of coefficients of valid constraints for elements
4937 * in that dependence relation and collect the results.
4938 * If "coincidence" is set, then coincidence edges are considered as well.
4940 * In particular, for each dependence relation R, constraints
4941 * on coefficients (c_0, c_x) are constructed such that
4943 * c_0 + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
4945 * If the schedule_treat_coalescing option is set, then some constraints
4946 * that could be exploited to construct coalescing schedules
4947 * are removed before the dual is computed, but after the parameters
4948 * have been projected out.
4949 * The entire computation is essentially the same as that performed
4950 * by intra_coefficients, except that it operates on multiple
4951 * edges together and that the parameters are always projected out.
4953 * Additionally, exploit any non-trivial lineality space
4954 * in the difference set after removing coalescing constraints and
4955 * store the results of the non-trivial lineality space detection in "data".
4956 * The procedure is currently run unconditionally, but it is unlikely
4957 * to find any non-trivial lineality spaces if no coalescing constraints
4958 * have been removed.
4960 * Note that if a dependence relation is a union of basic maps,
4961 * then each basic map needs to be treated individually as it may only
4962 * be possible to carry the dependences expressed by some of those
4963 * basic maps and not all of them.
4964 * The collected validity constraints are therefore not coalesced and
4965 * it is assumed that they are not coalesced automatically.
4966 * Duplicate basic maps can be removed, however.
4967 * In particular, if the same basic map appears as a disjunct
4968 * in multiple edges, then it only needs to be carried once.
4970 static __isl_give isl_basic_set_list *collect_intra_validity(isl_ctx *ctx,
4971 struct isl_sched_graph *graph, int coincidence,
4972 struct isl_exploit_lineality_data *data)
4974 isl_union_map *intra;
4975 isl_union_set *delta;
4976 isl_basic_set_list *list;
4978 intra = collect_validity(graph, &add_intra, coincidence);
4979 delta = isl_union_map_deltas(intra);
4980 delta = union_set_drop_parameters(delta);
4981 delta = isl_union_set_remove_divs(delta);
4982 if (isl_options_get_schedule_treat_coalescing(ctx))
4983 delta = union_drop_coalescing_constraints(ctx, graph, delta);
4984 delta = exploit_intra_lineality(delta, data);
4985 list = isl_union_set_get_basic_set_list(delta);
4986 isl_union_set_free(delta);
4988 return isl_basic_set_list_coefficients(list);
4991 /* For each dependence relation on a (conditional) validity edge
4992 * from a node to some other node,
4993 * construct the set of coefficients of valid constraints for elements
4994 * in that dependence relation and collect the results.
4995 * If "coincidence" is set, then coincidence edges are considered as well.
4997 * In particular, for each dependence relation R, constraints
4998 * on coefficients (c_0, c_n, c_x, c_y) are constructed such that
5000 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
5002 * This computation is essentially the same as that performed
5003 * by inter_coefficients, except that it operates on multiple
5004 * edges together.
5006 * Additionally, exploit any non-trivial lineality space
5007 * that may have been discovered by collect_intra_validity
5008 * (as stored in "data").
5010 * Note that if a dependence relation is a union of basic maps,
5011 * then each basic map needs to be treated individually as it may only
5012 * be possible to carry the dependences expressed by some of those
5013 * basic maps and not all of them.
5014 * The collected validity constraints are therefore not coalesced and
5015 * it is assumed that they are not coalesced automatically.
5016 * Duplicate basic maps can be removed, however.
5017 * In particular, if the same basic map appears as a disjunct
5018 * in multiple edges, then it only needs to be carried once.
5020 static __isl_give isl_basic_set_list *collect_inter_validity(
5021 struct isl_sched_graph *graph, int coincidence,
5022 struct isl_exploit_lineality_data *data)
5024 isl_union_map *inter;
5025 isl_union_set *wrap;
5026 isl_basic_set_list *list;
5028 inter = collect_validity(graph, &add_inter, coincidence);
5029 inter = exploit_inter_lineality(inter, data);
5030 inter = isl_union_map_remove_divs(inter);
5031 wrap = isl_union_map_wrap(inter);
5032 list = isl_union_set_get_basic_set_list(wrap);
5033 isl_union_set_free(wrap);
5034 return isl_basic_set_list_coefficients(list);
5037 /* Construct an LP problem for finding schedule coefficients
5038 * such that the schedule carries as many of the "n_edge" groups of
5039 * dependences as possible based on the corresponding coefficient
5040 * constraints and return the lexicographically smallest non-trivial solution.
5041 * "intra" is the sequence of coefficient constraints for intra-node edges.
5042 * "inter" is the sequence of coefficient constraints for inter-node edges.
5043 * If "want_integral" is set, then compute an integral solution
5044 * for the coefficients rather than using the numerators
5045 * of a rational solution.
5046 * "carry_inter" indicates whether inter-node edges should be carried or
5047 * only respected.
5049 * If none of the "n_edge" groups can be carried
5050 * then return an empty vector.
5052 static __isl_give isl_vec *compute_carrying_sol_coef(isl_ctx *ctx,
5053 struct isl_sched_graph *graph, int n_edge,
5054 __isl_keep isl_basic_set_list *intra,
5055 __isl_keep isl_basic_set_list *inter, int want_integral,
5056 int carry_inter)
5058 isl_basic_set *lp;
5060 if (setup_carry_lp(ctx, graph, n_edge, intra, inter, carry_inter) < 0)
5061 return NULL;
5063 lp = isl_basic_set_copy(graph->lp);
5064 return non_neg_lexmin(graph, lp, n_edge, want_integral);
5067 /* Construct an LP problem for finding schedule coefficients
5068 * such that the schedule carries as many of the validity dependences
5069 * as possible and
5070 * return the lexicographically smallest non-trivial solution.
5071 * If "fallback" is set, then the carrying is performed as a fallback
5072 * for the Pluto-like scheduler.
5073 * If "coincidence" is set, then try and carry coincidence edges as well.
5075 * The variable "n_edge" stores the number of groups that should be carried.
5076 * If none of the "n_edge" groups can be carried
5077 * then return an empty vector.
5078 * If, moreover, "n_edge" is zero, then the LP problem does not even
5079 * need to be constructed.
5081 * If a fallback solution is being computed, then compute an integral solution
5082 * for the coefficients rather than using the numerators
5083 * of a rational solution.
5085 * If a fallback solution is being computed, if there are any intra-node
5086 * dependences, and if requested by the user, then first try
5087 * to only carry those intra-node dependences.
5088 * If this fails to carry any dependences, then try again
5089 * with the inter-node dependences included.
5091 static __isl_give isl_vec *compute_carrying_sol(isl_ctx *ctx,
5092 struct isl_sched_graph *graph, int fallback, int coincidence)
5094 int n_intra, n_inter;
5095 int n_edge;
5096 struct isl_carry carry = { 0 };
5097 isl_vec *sol;
5099 carry.intra = collect_intra_validity(ctx, graph, coincidence,
5100 &carry.lineality);
5101 carry.inter = collect_inter_validity(graph, coincidence,
5102 &carry.lineality);
5103 if (!carry.intra || !carry.inter)
5104 goto error;
5105 n_intra = isl_basic_set_list_n_basic_set(carry.intra);
5106 n_inter = isl_basic_set_list_n_basic_set(carry.inter);
5108 if (fallback && n_intra > 0 &&
5109 isl_options_get_schedule_carry_self_first(ctx)) {
5110 sol = compute_carrying_sol_coef(ctx, graph, n_intra,
5111 carry.intra, carry.inter, fallback, 0);
5112 if (!sol || sol->size != 0 || n_inter == 0) {
5113 isl_carry_clear(&carry);
5114 return sol;
5116 isl_vec_free(sol);
5119 n_edge = n_intra + n_inter;
5120 if (n_edge == 0) {
5121 isl_carry_clear(&carry);
5122 return isl_vec_alloc(ctx, 0);
5125 sol = compute_carrying_sol_coef(ctx, graph, n_edge,
5126 carry.intra, carry.inter, fallback, 1);
5127 isl_carry_clear(&carry);
5128 return sol;
5129 error:
5130 isl_carry_clear(&carry);
5131 return NULL;
5134 /* Construct a schedule row for each node such that as many validity dependences
5135 * as possible are carried and then continue with the next band.
5136 * If "fallback" is set, then the carrying is performed as a fallback
5137 * for the Pluto-like scheduler.
5138 * If "coincidence" is set, then try and carry coincidence edges as well.
5140 * If there are no validity dependences, then no dependence can be carried and
5141 * the procedure is guaranteed to fail. If there is more than one component,
5142 * then try computing a schedule on each component separately
5143 * to prevent or at least postpone this failure.
5145 * If a schedule row is computed, then check that dependences are carried
5146 * for at least one of the edges.
5148 * If the computed schedule row turns out to be trivial on one or
5149 * more nodes where it should not be trivial, then we throw it away
5150 * and try again on each component separately.
5152 * If there is only one component, then we accept the schedule row anyway,
5153 * but we do not consider it as a complete row and therefore do not
5154 * increment graph->n_row. Note that the ranks of the nodes that
5155 * do get a non-trivial schedule part will get updated regardless and
5156 * graph->maxvar is computed based on these ranks. The test for
5157 * whether more schedule rows are required in compute_schedule_wcc
5158 * is therefore not affected.
5160 * Insert a band corresponding to the schedule row at position "node"
5161 * of the schedule tree and continue with the construction of the schedule.
5162 * This insertion and the continued construction is performed by split_scaled
5163 * after optionally checking for non-trivial common divisors.
5165 static __isl_give isl_schedule_node *carry(__isl_take isl_schedule_node *node,
5166 struct isl_sched_graph *graph, int fallback, int coincidence)
5168 int trivial;
5169 isl_ctx *ctx;
5170 isl_vec *sol;
5172 if (!node)
5173 return NULL;
5175 ctx = isl_schedule_node_get_ctx(node);
5176 sol = compute_carrying_sol(ctx, graph, fallback, coincidence);
5177 if (!sol)
5178 return isl_schedule_node_free(node);
5179 if (sol->size == 0) {
5180 isl_vec_free(sol);
5181 if (graph->scc > 1)
5182 return compute_component_schedule(node, graph, 1);
5183 isl_die(ctx, isl_error_unknown, "unable to carry dependences",
5184 return isl_schedule_node_free(node));
5187 trivial = is_any_trivial(graph, sol);
5188 if (trivial < 0) {
5189 sol = isl_vec_free(sol);
5190 } else if (trivial && graph->scc > 1) {
5191 isl_vec_free(sol);
5192 return compute_component_schedule(node, graph, 1);
5195 if (update_schedule(graph, sol, 0) < 0)
5196 return isl_schedule_node_free(node);
5197 if (trivial)
5198 graph->n_row--;
5200 return split_scaled(node, graph);
5203 /* Construct a schedule row for each node such that as many validity dependences
5204 * as possible are carried and then continue with the next band.
5205 * Do so as a fallback for the Pluto-like scheduler.
5206 * If "coincidence" is set, then try and carry coincidence edges as well.
5208 static __isl_give isl_schedule_node *carry_fallback(
5209 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
5210 int coincidence)
5212 return carry(node, graph, 1, coincidence);
5215 /* Construct a schedule row for each node such that as many validity dependences
5216 * as possible are carried and then continue with the next band.
5217 * Do so for the case where the Feautrier scheduler was selected
5218 * by the user.
5220 static __isl_give isl_schedule_node *carry_feautrier(
5221 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5223 return carry(node, graph, 0, 0);
5226 /* Construct a schedule row for each node such that as many validity dependences
5227 * as possible are carried and then continue with the next band.
5228 * Do so as a fallback for the Pluto-like scheduler.
5230 static __isl_give isl_schedule_node *carry_dependences(
5231 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5233 return carry_fallback(node, graph, 0);
5236 /* Construct a schedule row for each node such that as many validity or
5237 * coincidence dependences as possible are carried and
5238 * then continue with the next band.
5239 * Do so as a fallback for the Pluto-like scheduler.
5241 static __isl_give isl_schedule_node *carry_coincidence(
5242 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5244 return carry_fallback(node, graph, 1);
5247 /* Topologically sort statements mapped to the same schedule iteration
5248 * and add insert a sequence node in front of "node"
5249 * corresponding to this order.
5250 * If "initialized" is set, then it may be assumed that compute_maxvar
5251 * has been called on the current band. Otherwise, call
5252 * compute_maxvar if and before carry_dependences gets called.
5254 * If it turns out to be impossible to sort the statements apart,
5255 * because different dependences impose different orderings
5256 * on the statements, then we extend the schedule such that
5257 * it carries at least one more dependence.
5259 static __isl_give isl_schedule_node *sort_statements(
5260 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
5261 int initialized)
5263 isl_ctx *ctx;
5264 isl_union_set_list *filters;
5266 if (!node)
5267 return NULL;
5269 ctx = isl_schedule_node_get_ctx(node);
5270 if (graph->n < 1)
5271 isl_die(ctx, isl_error_internal,
5272 "graph should have at least one node",
5273 return isl_schedule_node_free(node));
5275 if (graph->n == 1)
5276 return node;
5278 if (update_edges(ctx, graph) < 0)
5279 return isl_schedule_node_free(node);
5281 if (graph->n_edge == 0)
5282 return node;
5284 if (detect_sccs(ctx, graph) < 0)
5285 return isl_schedule_node_free(node);
5287 next_band(graph);
5288 if (graph->scc < graph->n) {
5289 if (!initialized && compute_maxvar(graph) < 0)
5290 return isl_schedule_node_free(node);
5291 return carry_dependences(node, graph);
5294 filters = extract_sccs(ctx, graph);
5295 node = isl_schedule_node_insert_sequence(node, filters);
5297 return node;
5300 /* Are there any (non-empty) (conditional) validity edges in the graph?
5302 static int has_validity_edges(struct isl_sched_graph *graph)
5304 int i;
5306 for (i = 0; i < graph->n_edge; ++i) {
5307 int empty;
5309 empty = isl_map_plain_is_empty(graph->edge[i].map);
5310 if (empty < 0)
5311 return -1;
5312 if (empty)
5313 continue;
5314 if (is_any_validity(&graph->edge[i]))
5315 return 1;
5318 return 0;
5321 /* Should we apply a Feautrier step?
5322 * That is, did the user request the Feautrier algorithm and are
5323 * there any validity dependences (left)?
5325 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
5327 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
5328 return 0;
5330 return has_validity_edges(graph);
5333 /* Compute a schedule for a connected dependence graph using Feautrier's
5334 * multi-dimensional scheduling algorithm and return the updated schedule node.
5336 * The original algorithm is described in [1].
5337 * The main idea is to minimize the number of scheduling dimensions, by
5338 * trying to satisfy as many dependences as possible per scheduling dimension.
5340 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
5341 * Problem, Part II: Multi-Dimensional Time.
5342 * In Intl. Journal of Parallel Programming, 1992.
5344 static __isl_give isl_schedule_node *compute_schedule_wcc_feautrier(
5345 isl_schedule_node *node, struct isl_sched_graph *graph)
5347 return carry_feautrier(node, graph);
5350 /* Turn off the "local" bit on all (condition) edges.
5352 static void clear_local_edges(struct isl_sched_graph *graph)
5354 int i;
5356 for (i = 0; i < graph->n_edge; ++i)
5357 if (is_condition(&graph->edge[i]))
5358 clear_local(&graph->edge[i]);
5361 /* Does "graph" have both condition and conditional validity edges?
5363 static int need_condition_check(struct isl_sched_graph *graph)
5365 int i;
5366 int any_condition = 0;
5367 int any_conditional_validity = 0;
5369 for (i = 0; i < graph->n_edge; ++i) {
5370 if (is_condition(&graph->edge[i]))
5371 any_condition = 1;
5372 if (is_conditional_validity(&graph->edge[i]))
5373 any_conditional_validity = 1;
5376 return any_condition && any_conditional_validity;
5379 /* Does "graph" contain any coincidence edge?
5381 static int has_any_coincidence(struct isl_sched_graph *graph)
5383 int i;
5385 for (i = 0; i < graph->n_edge; ++i)
5386 if (is_coincidence(&graph->edge[i]))
5387 return 1;
5389 return 0;
5392 /* Extract the final schedule row as a map with the iteration domain
5393 * of "node" as domain.
5395 static __isl_give isl_map *final_row(struct isl_sched_node *node)
5397 isl_multi_aff *ma;
5398 int row;
5400 row = isl_mat_rows(node->sched) - 1;
5401 ma = node_extract_partial_schedule_multi_aff(node, row, 1);
5402 return isl_map_from_multi_aff(ma);
5405 /* Is the conditional validity dependence in the edge with index "edge_index"
5406 * violated by the latest (i.e., final) row of the schedule?
5407 * That is, is i scheduled after j
5408 * for any conditional validity dependence i -> j?
5410 static int is_violated(struct isl_sched_graph *graph, int edge_index)
5412 isl_map *src_sched, *dst_sched, *map;
5413 struct isl_sched_edge *edge = &graph->edge[edge_index];
5414 int empty;
5416 src_sched = final_row(edge->src);
5417 dst_sched = final_row(edge->dst);
5418 map = isl_map_copy(edge->map);
5419 map = isl_map_apply_domain(map, src_sched);
5420 map = isl_map_apply_range(map, dst_sched);
5421 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);
5422 empty = isl_map_is_empty(map);
5423 isl_map_free(map);
5425 if (empty < 0)
5426 return -1;
5428 return !empty;
5431 /* Does "graph" have any satisfied condition edges that
5432 * are adjacent to the conditional validity constraint with
5433 * domain "conditional_source" and range "conditional_sink"?
5435 * A satisfied condition is one that is not local.
5436 * If a condition was forced to be local already (i.e., marked as local)
5437 * then there is no need to check if it is in fact local.
5439 * Additionally, mark all adjacent condition edges found as local.
5441 static int has_adjacent_true_conditions(struct isl_sched_graph *graph,
5442 __isl_keep isl_union_set *conditional_source,
5443 __isl_keep isl_union_set *conditional_sink)
5445 int i;
5446 int any = 0;
5448 for (i = 0; i < graph->n_edge; ++i) {
5449 int adjacent, local;
5450 isl_union_map *condition;
5452 if (!is_condition(&graph->edge[i]))
5453 continue;
5454 if (is_local(&graph->edge[i]))
5455 continue;
5457 condition = graph->edge[i].tagged_condition;
5458 adjacent = domain_intersects(condition, conditional_sink);
5459 if (adjacent >= 0 && !adjacent)
5460 adjacent = range_intersects(condition,
5461 conditional_source);
5462 if (adjacent < 0)
5463 return -1;
5464 if (!adjacent)
5465 continue;
5467 set_local(&graph->edge[i]);
5469 local = is_condition_false(&graph->edge[i]);
5470 if (local < 0)
5471 return -1;
5472 if (!local)
5473 any = 1;
5476 return any;
5479 /* Are there any violated conditional validity dependences with
5480 * adjacent condition dependences that are not local with respect
5481 * to the current schedule?
5482 * That is, is the conditional validity constraint violated?
5484 * Additionally, mark all those adjacent condition dependences as local.
5485 * We also mark those adjacent condition dependences that were not marked
5486 * as local before, but just happened to be local already. This ensures
5487 * that they remain local if the schedule is recomputed.
5489 * We first collect domain and range of all violated conditional validity
5490 * dependences and then check if there are any adjacent non-local
5491 * condition dependences.
5493 static int has_violated_conditional_constraint(isl_ctx *ctx,
5494 struct isl_sched_graph *graph)
5496 int i;
5497 int any = 0;
5498 isl_union_set *source, *sink;
5500 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
5501 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
5502 for (i = 0; i < graph->n_edge; ++i) {
5503 isl_union_set *uset;
5504 isl_union_map *umap;
5505 int violated;
5507 if (!is_conditional_validity(&graph->edge[i]))
5508 continue;
5510 violated = is_violated(graph, i);
5511 if (violated < 0)
5512 goto error;
5513 if (!violated)
5514 continue;
5516 any = 1;
5518 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
5519 uset = isl_union_map_domain(umap);
5520 source = isl_union_set_union(source, uset);
5521 source = isl_union_set_coalesce(source);
5523 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
5524 uset = isl_union_map_range(umap);
5525 sink = isl_union_set_union(sink, uset);
5526 sink = isl_union_set_coalesce(sink);
5529 if (any)
5530 any = has_adjacent_true_conditions(graph, source, sink);
5532 isl_union_set_free(source);
5533 isl_union_set_free(sink);
5534 return any;
5535 error:
5536 isl_union_set_free(source);
5537 isl_union_set_free(sink);
5538 return -1;
5541 /* Examine the current band (the rows between graph->band_start and
5542 * graph->n_total_row), deciding whether to drop it or add it to "node"
5543 * and then continue with the computation of the next band, if any.
5544 * If "initialized" is set, then it may be assumed that compute_maxvar
5545 * has been called on the current band. Otherwise, call
5546 * compute_maxvar if and before carry_dependences gets called.
5548 * The caller keeps looking for a new row as long as
5549 * graph->n_row < graph->maxvar. If the latest attempt to find
5550 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
5551 * then we either
5552 * - split between SCCs and start over (assuming we found an interesting
5553 * pair of SCCs between which to split)
5554 * - continue with the next band (assuming the current band has at least
5555 * one row)
5556 * - if there is more than one SCC left, then split along all SCCs
5557 * - if outer coincidence needs to be enforced, then try to carry as many
5558 * validity or coincidence dependences as possible and
5559 * continue with the next band
5560 * - try to carry as many validity dependences as possible and
5561 * continue with the next band
5562 * In each case, we first insert a band node in the schedule tree
5563 * if any rows have been computed.
5565 * If the caller managed to complete the schedule and the current band
5566 * is empty, then finish off by topologically
5567 * sorting the statements based on the remaining dependences.
5568 * If, on the other hand, the current band has at least one row,
5569 * then continue with the next band. Note that this next band
5570 * will necessarily be empty, but the graph may still be split up
5571 * into weakly connected components before arriving back here.
5573 static __isl_give isl_schedule_node *compute_schedule_finish_band(
5574 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
5575 int initialized)
5577 int empty;
5579 if (!node)
5580 return NULL;
5582 empty = graph->n_total_row == graph->band_start;
5583 if (graph->n_row < graph->maxvar) {
5584 isl_ctx *ctx;
5586 ctx = isl_schedule_node_get_ctx(node);
5587 if (!ctx->opt->schedule_maximize_band_depth && !empty)
5588 return compute_next_band(node, graph, 1);
5589 if (graph->src_scc >= 0)
5590 return compute_split_schedule(node, graph);
5591 if (!empty)
5592 return compute_next_band(node, graph, 1);
5593 if (graph->scc > 1)
5594 return compute_component_schedule(node, graph, 1);
5595 if (!initialized && compute_maxvar(graph) < 0)
5596 return isl_schedule_node_free(node);
5597 if (isl_options_get_schedule_outer_coincidence(ctx))
5598 return carry_coincidence(node, graph);
5599 return carry_dependences(node, graph);
5602 if (!empty)
5603 return compute_next_band(node, graph, 1);
5604 return sort_statements(node, graph, initialized);
5607 /* Construct a band of schedule rows for a connected dependence graph.
5608 * The caller is responsible for determining the strongly connected
5609 * components and calling compute_maxvar first.
5611 * We try to find a sequence of as many schedule rows as possible that result
5612 * in non-negative dependence distances (independent of the previous rows
5613 * in the sequence, i.e., such that the sequence is tilable), with as
5614 * many of the initial rows as possible satisfying the coincidence constraints.
5615 * The computation stops if we can't find any more rows or if we have found
5616 * all the rows we wanted to find.
5618 * If ctx->opt->schedule_outer_coincidence is set, then we force the
5619 * outermost dimension to satisfy the coincidence constraints. If this
5620 * turns out to be impossible, we fall back on the general scheme above
5621 * and try to carry as many dependences as possible.
5623 * If "graph" contains both condition and conditional validity dependences,
5624 * then we need to check that that the conditional schedule constraint
5625 * is satisfied, i.e., there are no violated conditional validity dependences
5626 * that are adjacent to any non-local condition dependences.
5627 * If there are, then we mark all those adjacent condition dependences
5628 * as local and recompute the current band. Those dependences that
5629 * are marked local will then be forced to be local.
5630 * The initial computation is performed with no dependences marked as local.
5631 * If we are lucky, then there will be no violated conditional validity
5632 * dependences adjacent to any non-local condition dependences.
5633 * Otherwise, we mark some additional condition dependences as local and
5634 * recompute. We continue this process until there are no violations left or
5635 * until we are no longer able to compute a schedule.
5636 * Since there are only a finite number of dependences,
5637 * there will only be a finite number of iterations.
5639 static isl_stat compute_schedule_wcc_band(isl_ctx *ctx,
5640 struct isl_sched_graph *graph)
5642 int has_coincidence;
5643 int use_coincidence;
5644 int force_coincidence = 0;
5645 int check_conditional;
5647 if (sort_sccs(graph) < 0)
5648 return isl_stat_error;
5650 clear_local_edges(graph);
5651 check_conditional = need_condition_check(graph);
5652 has_coincidence = has_any_coincidence(graph);
5654 if (ctx->opt->schedule_outer_coincidence)
5655 force_coincidence = 1;
5657 use_coincidence = has_coincidence;
5658 while (graph->n_row < graph->maxvar) {
5659 isl_vec *sol;
5660 int violated;
5661 int coincident;
5663 graph->src_scc = -1;
5664 graph->dst_scc = -1;
5666 if (setup_lp(ctx, graph, use_coincidence) < 0)
5667 return isl_stat_error;
5668 sol = solve_lp(ctx, graph);
5669 if (!sol)
5670 return isl_stat_error;
5671 if (sol->size == 0) {
5672 int empty = graph->n_total_row == graph->band_start;
5674 isl_vec_free(sol);
5675 if (use_coincidence && (!force_coincidence || !empty)) {
5676 use_coincidence = 0;
5677 continue;
5679 return isl_stat_ok;
5681 coincident = !has_coincidence || use_coincidence;
5682 if (update_schedule(graph, sol, coincident) < 0)
5683 return isl_stat_error;
5685 if (!check_conditional)
5686 continue;
5687 violated = has_violated_conditional_constraint(ctx, graph);
5688 if (violated < 0)
5689 return isl_stat_error;
5690 if (!violated)
5691 continue;
5692 if (reset_band(graph) < 0)
5693 return isl_stat_error;
5694 use_coincidence = has_coincidence;
5697 return isl_stat_ok;
5700 /* Compute a schedule for a connected dependence graph by considering
5701 * the graph as a whole and return the updated schedule node.
5703 * The actual schedule rows of the current band are computed by
5704 * compute_schedule_wcc_band. compute_schedule_finish_band takes
5705 * care of integrating the band into "node" and continuing
5706 * the computation.
5708 static __isl_give isl_schedule_node *compute_schedule_wcc_whole(
5709 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5711 isl_ctx *ctx;
5713 if (!node)
5714 return NULL;
5716 ctx = isl_schedule_node_get_ctx(node);
5717 if (compute_schedule_wcc_band(ctx, graph) < 0)
5718 return isl_schedule_node_free(node);
5720 return compute_schedule_finish_band(node, graph, 1);
5723 /* Clustering information used by compute_schedule_wcc_clustering.
5725 * "n" is the number of SCCs in the original dependence graph
5726 * "scc" is an array of "n" elements, each representing an SCC
5727 * of the original dependence graph. All entries in the same cluster
5728 * have the same number of schedule rows.
5729 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
5730 * where each cluster is represented by the index of the first SCC
5731 * in the cluster. Initially, each SCC belongs to a cluster containing
5732 * only that SCC.
5734 * "scc_in_merge" is used by merge_clusters_along_edge to keep
5735 * track of which SCCs need to be merged.
5737 * "cluster" contains the merged clusters of SCCs after the clustering
5738 * has completed.
5740 * "scc_node" is a temporary data structure used inside copy_partial.
5741 * For each SCC, it keeps track of the number of nodes in the SCC
5742 * that have already been copied.
5744 struct isl_clustering {
5745 int n;
5746 struct isl_sched_graph *scc;
5747 struct isl_sched_graph *cluster;
5748 int *scc_cluster;
5749 int *scc_node;
5750 int *scc_in_merge;
5753 /* Initialize the clustering data structure "c" from "graph".
5755 * In particular, allocate memory, extract the SCCs from "graph"
5756 * into c->scc, initialize scc_cluster and construct
5757 * a band of schedule rows for each SCC.
5758 * Within each SCC, there is only one SCC by definition.
5759 * Each SCC initially belongs to a cluster containing only that SCC.
5761 static isl_stat clustering_init(isl_ctx *ctx, struct isl_clustering *c,
5762 struct isl_sched_graph *graph)
5764 int i;
5766 c->n = graph->scc;
5767 c->scc = isl_calloc_array(ctx, struct isl_sched_graph, c->n);
5768 c->cluster = isl_calloc_array(ctx, struct isl_sched_graph, c->n);
5769 c->scc_cluster = isl_calloc_array(ctx, int, c->n);
5770 c->scc_node = isl_calloc_array(ctx, int, c->n);
5771 c->scc_in_merge = isl_calloc_array(ctx, int, c->n);
5772 if (!c->scc || !c->cluster ||
5773 !c->scc_cluster || !c->scc_node || !c->scc_in_merge)
5774 return isl_stat_error;
5776 for (i = 0; i < c->n; ++i) {
5777 if (extract_sub_graph(ctx, graph, &node_scc_exactly,
5778 &edge_scc_exactly, i, &c->scc[i]) < 0)
5779 return isl_stat_error;
5780 c->scc[i].scc = 1;
5781 if (compute_maxvar(&c->scc[i]) < 0)
5782 return isl_stat_error;
5783 if (compute_schedule_wcc_band(ctx, &c->scc[i]) < 0)
5784 return isl_stat_error;
5785 c->scc_cluster[i] = i;
5788 return isl_stat_ok;
5791 /* Free all memory allocated for "c".
5793 static void clustering_free(isl_ctx *ctx, struct isl_clustering *c)
5795 int i;
5797 if (c->scc)
5798 for (i = 0; i < c->n; ++i)
5799 graph_free(ctx, &c->scc[i]);
5800 free(c->scc);
5801 if (c->cluster)
5802 for (i = 0; i < c->n; ++i)
5803 graph_free(ctx, &c->cluster[i]);
5804 free(c->cluster);
5805 free(c->scc_cluster);
5806 free(c->scc_node);
5807 free(c->scc_in_merge);
5810 /* Should we refrain from merging the cluster in "graph" with
5811 * any other cluster?
5812 * In particular, is its current schedule band empty and incomplete.
5814 static int bad_cluster(struct isl_sched_graph *graph)
5816 return graph->n_row < graph->maxvar &&
5817 graph->n_total_row == graph->band_start;
5820 /* Is "edge" a proximity edge with a non-empty dependence relation?
5822 static isl_bool is_non_empty_proximity(struct isl_sched_edge *edge)
5824 if (!is_proximity(edge))
5825 return isl_bool_false;
5826 return isl_bool_not(isl_map_plain_is_empty(edge->map));
5829 /* Return the index of an edge in "graph" that can be used to merge
5830 * two clusters in "c".
5831 * Return graph->n_edge if no such edge can be found.
5832 * Return -1 on error.
5834 * In particular, return a proximity edge between two clusters
5835 * that is not marked "no_merge" and such that neither of the
5836 * two clusters has an incomplete, empty band.
5838 * If there are multiple such edges, then try and find the most
5839 * appropriate edge to use for merging. In particular, pick the edge
5840 * with the greatest weight. If there are multiple of those,
5841 * then pick one with the shortest distance between
5842 * the two cluster representatives.
5844 static int find_proximity(struct isl_sched_graph *graph,
5845 struct isl_clustering *c)
5847 int i, best = graph->n_edge, best_dist, best_weight;
5849 for (i = 0; i < graph->n_edge; ++i) {
5850 struct isl_sched_edge *edge = &graph->edge[i];
5851 int dist, weight;
5852 isl_bool prox;
5854 prox = is_non_empty_proximity(edge);
5855 if (prox < 0)
5856 return -1;
5857 if (!prox)
5858 continue;
5859 if (edge->no_merge)
5860 continue;
5861 if (bad_cluster(&c->scc[edge->src->scc]) ||
5862 bad_cluster(&c->scc[edge->dst->scc]))
5863 continue;
5864 dist = c->scc_cluster[edge->dst->scc] -
5865 c->scc_cluster[edge->src->scc];
5866 if (dist == 0)
5867 continue;
5868 weight = edge->weight;
5869 if (best < graph->n_edge) {
5870 if (best_weight > weight)
5871 continue;
5872 if (best_weight == weight && best_dist <= dist)
5873 continue;
5875 best = i;
5876 best_dist = dist;
5877 best_weight = weight;
5880 return best;
5883 /* Internal data structure used in mark_merge_sccs.
5885 * "graph" is the dependence graph in which a strongly connected
5886 * component is constructed.
5887 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
5888 * "src" and "dst" are the indices of the nodes that are being merged.
5890 struct isl_mark_merge_sccs_data {
5891 struct isl_sched_graph *graph;
5892 int *scc_cluster;
5893 int src;
5894 int dst;
5897 /* Check whether the cluster containing node "i" depends on the cluster
5898 * containing node "j". If "i" and "j" belong to the same cluster,
5899 * then they are taken to depend on each other to ensure that
5900 * the resulting strongly connected component consists of complete
5901 * clusters. Furthermore, if "i" and "j" are the two nodes that
5902 * are being merged, then they are taken to depend on each other as well.
5903 * Otherwise, check if there is a (conditional) validity dependence
5904 * from node[j] to node[i], forcing node[i] to follow node[j].
5906 static isl_bool cluster_follows(int i, int j, void *user)
5908 struct isl_mark_merge_sccs_data *data = user;
5909 struct isl_sched_graph *graph = data->graph;
5910 int *scc_cluster = data->scc_cluster;
5912 if (data->src == i && data->dst == j)
5913 return isl_bool_true;
5914 if (data->src == j && data->dst == i)
5915 return isl_bool_true;
5916 if (scc_cluster[graph->node[i].scc] == scc_cluster[graph->node[j].scc])
5917 return isl_bool_true;
5919 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
5922 /* Mark all SCCs that belong to either of the two clusters in "c"
5923 * connected by the edge in "graph" with index "edge", or to any
5924 * of the intermediate clusters.
5925 * The marking is recorded in c->scc_in_merge.
5927 * The given edge has been selected for merging two clusters,
5928 * meaning that there is at least a proximity edge between the two nodes.
5929 * However, there may also be (indirect) validity dependences
5930 * between the two nodes. When merging the two clusters, all clusters
5931 * containing one or more of the intermediate nodes along the
5932 * indirect validity dependences need to be merged in as well.
5934 * First collect all such nodes by computing the strongly connected
5935 * component (SCC) containing the two nodes connected by the edge, where
5936 * the two nodes are considered to depend on each other to make
5937 * sure they end up in the same SCC. Similarly, each node is considered
5938 * to depend on every other node in the same cluster to ensure
5939 * that the SCC consists of complete clusters.
5941 * Then the original SCCs that contain any of these nodes are marked
5942 * in c->scc_in_merge.
5944 static isl_stat mark_merge_sccs(isl_ctx *ctx, struct isl_sched_graph *graph,
5945 int edge, struct isl_clustering *c)
5947 struct isl_mark_merge_sccs_data data;
5948 struct isl_tarjan_graph *g;
5949 int i;
5951 for (i = 0; i < c->n; ++i)
5952 c->scc_in_merge[i] = 0;
5954 data.graph = graph;
5955 data.scc_cluster = c->scc_cluster;
5956 data.src = graph->edge[edge].src - graph->node;
5957 data.dst = graph->edge[edge].dst - graph->node;
5959 g = isl_tarjan_graph_component(ctx, graph->n, data.dst,
5960 &cluster_follows, &data);
5961 if (!g)
5962 goto error;
5964 i = g->op;
5965 if (i < 3)
5966 isl_die(ctx, isl_error_internal,
5967 "expecting at least two nodes in component",
5968 goto error);
5969 if (g->order[--i] != -1)
5970 isl_die(ctx, isl_error_internal,
5971 "expecting end of component marker", goto error);
5973 for (--i; i >= 0 && g->order[i] != -1; --i) {
5974 int scc = graph->node[g->order[i]].scc;
5975 c->scc_in_merge[scc] = 1;
5978 isl_tarjan_graph_free(g);
5979 return isl_stat_ok;
5980 error:
5981 isl_tarjan_graph_free(g);
5982 return isl_stat_error;
5985 /* Construct the identifier "cluster_i".
5987 static __isl_give isl_id *cluster_id(isl_ctx *ctx, int i)
5989 char name[40];
5991 snprintf(name, sizeof(name), "cluster_%d", i);
5992 return isl_id_alloc(ctx, name, NULL);
5995 /* Construct the space of the cluster with index "i" containing
5996 * the strongly connected component "scc".
5998 * In particular, construct a space called cluster_i with dimension equal
5999 * to the number of schedule rows in the current band of "scc".
6001 static __isl_give isl_space *cluster_space(struct isl_sched_graph *scc, int i)
6003 int nvar;
6004 isl_space *space;
6005 isl_id *id;
6007 nvar = scc->n_total_row - scc->band_start;
6008 space = isl_space_copy(scc->node[0].space);
6009 space = isl_space_params(space);
6010 space = isl_space_set_from_params(space);
6011 space = isl_space_add_dims(space, isl_dim_set, nvar);
6012 id = cluster_id(isl_space_get_ctx(space), i);
6013 space = isl_space_set_tuple_id(space, isl_dim_set, id);
6015 return space;
6018 /* Collect the domain of the graph for merging clusters.
6020 * In particular, for each cluster with first SCC "i", construct
6021 * a set in the space called cluster_i with dimension equal
6022 * to the number of schedule rows in the current band of the cluster.
6024 static __isl_give isl_union_set *collect_domain(isl_ctx *ctx,
6025 struct isl_sched_graph *graph, struct isl_clustering *c)
6027 int i;
6028 isl_space *space;
6029 isl_union_set *domain;
6031 space = isl_space_params_alloc(ctx, 0);
6032 domain = isl_union_set_empty(space);
6034 for (i = 0; i < graph->scc; ++i) {
6035 isl_space *space;
6037 if (!c->scc_in_merge[i])
6038 continue;
6039 if (c->scc_cluster[i] != i)
6040 continue;
6041 space = cluster_space(&c->scc[i], i);
6042 domain = isl_union_set_add_set(domain, isl_set_universe(space));
6045 return domain;
6048 /* Construct a map from the original instances to the corresponding
6049 * cluster instance in the current bands of the clusters in "c".
6051 static __isl_give isl_union_map *collect_cluster_map(isl_ctx *ctx,
6052 struct isl_sched_graph *graph, struct isl_clustering *c)
6054 int i, j;
6055 isl_space *space;
6056 isl_union_map *cluster_map;
6058 space = isl_space_params_alloc(ctx, 0);
6059 cluster_map = isl_union_map_empty(space);
6060 for (i = 0; i < graph->scc; ++i) {
6061 int start, n;
6062 isl_id *id;
6064 if (!c->scc_in_merge[i])
6065 continue;
6067 id = cluster_id(ctx, c->scc_cluster[i]);
6068 start = c->scc[i].band_start;
6069 n = c->scc[i].n_total_row - start;
6070 for (j = 0; j < c->scc[i].n; ++j) {
6071 isl_multi_aff *ma;
6072 isl_map *map;
6073 struct isl_sched_node *node = &c->scc[i].node[j];
6075 ma = node_extract_partial_schedule_multi_aff(node,
6076 start, n);
6077 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out,
6078 isl_id_copy(id));
6079 map = isl_map_from_multi_aff(ma);
6080 cluster_map = isl_union_map_add_map(cluster_map, map);
6082 isl_id_free(id);
6085 return cluster_map;
6088 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
6089 * that are not isl_edge_condition or isl_edge_conditional_validity.
6091 static __isl_give isl_schedule_constraints *add_non_conditional_constraints(
6092 struct isl_sched_edge *edge, __isl_keep isl_union_map *umap,
6093 __isl_take isl_schedule_constraints *sc)
6095 enum isl_edge_type t;
6097 if (!sc)
6098 return NULL;
6100 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
6101 if (t == isl_edge_condition ||
6102 t == isl_edge_conditional_validity)
6103 continue;
6104 if (!is_type(edge, t))
6105 continue;
6106 sc = isl_schedule_constraints_add(sc, t,
6107 isl_union_map_copy(umap));
6110 return sc;
6113 /* Add schedule constraints of types isl_edge_condition and
6114 * isl_edge_conditional_validity to "sc" by applying "umap" to
6115 * the domains of the wrapped relations in domain and range
6116 * of the corresponding tagged constraints of "edge".
6118 static __isl_give isl_schedule_constraints *add_conditional_constraints(
6119 struct isl_sched_edge *edge, __isl_keep isl_union_map *umap,
6120 __isl_take isl_schedule_constraints *sc)
6122 enum isl_edge_type t;
6123 isl_union_map *tagged;
6125 for (t = isl_edge_condition; t <= isl_edge_conditional_validity; ++t) {
6126 if (!is_type(edge, t))
6127 continue;
6128 if (t == isl_edge_condition)
6129 tagged = isl_union_map_copy(edge->tagged_condition);
6130 else
6131 tagged = isl_union_map_copy(edge->tagged_validity);
6132 tagged = isl_union_map_zip(tagged);
6133 tagged = isl_union_map_apply_domain(tagged,
6134 isl_union_map_copy(umap));
6135 tagged = isl_union_map_zip(tagged);
6136 sc = isl_schedule_constraints_add(sc, t, tagged);
6137 if (!sc)
6138 return NULL;
6141 return sc;
6144 /* Given a mapping "cluster_map" from the original instances to
6145 * the cluster instances, add schedule constraints on the clusters
6146 * to "sc" corresponding to the original constraints represented by "edge".
6148 * For non-tagged dependence constraints, the cluster constraints
6149 * are obtained by applying "cluster_map" to the edge->map.
6151 * For tagged dependence constraints, "cluster_map" needs to be applied
6152 * to the domains of the wrapped relations in domain and range
6153 * of the tagged dependence constraints. Pick out the mappings
6154 * from these domains from "cluster_map" and construct their product.
6155 * This mapping can then be applied to the pair of domains.
6157 static __isl_give isl_schedule_constraints *collect_edge_constraints(
6158 struct isl_sched_edge *edge, __isl_keep isl_union_map *cluster_map,
6159 __isl_take isl_schedule_constraints *sc)
6161 isl_union_map *umap;
6162 isl_space *space;
6163 isl_union_set *uset;
6164 isl_union_map *umap1, *umap2;
6166 if (!sc)
6167 return NULL;
6169 umap = isl_union_map_from_map(isl_map_copy(edge->map));
6170 umap = isl_union_map_apply_domain(umap,
6171 isl_union_map_copy(cluster_map));
6172 umap = isl_union_map_apply_range(umap,
6173 isl_union_map_copy(cluster_map));
6174 sc = add_non_conditional_constraints(edge, umap, sc);
6175 isl_union_map_free(umap);
6177 if (!sc || (!is_condition(edge) && !is_conditional_validity(edge)))
6178 return sc;
6180 space = isl_space_domain(isl_map_get_space(edge->map));
6181 uset = isl_union_set_from_set(isl_set_universe(space));
6182 umap1 = isl_union_map_copy(cluster_map);
6183 umap1 = isl_union_map_intersect_domain(umap1, uset);
6184 space = isl_space_range(isl_map_get_space(edge->map));
6185 uset = isl_union_set_from_set(isl_set_universe(space));
6186 umap2 = isl_union_map_copy(cluster_map);
6187 umap2 = isl_union_map_intersect_domain(umap2, uset);
6188 umap = isl_union_map_product(umap1, umap2);
6190 sc = add_conditional_constraints(edge, umap, sc);
6192 isl_union_map_free(umap);
6193 return sc;
6196 /* Given a mapping "cluster_map" from the original instances to
6197 * the cluster instances, add schedule constraints on the clusters
6198 * to "sc" corresponding to all edges in "graph" between nodes that
6199 * belong to SCCs that are marked for merging in "scc_in_merge".
6201 static __isl_give isl_schedule_constraints *collect_constraints(
6202 struct isl_sched_graph *graph, int *scc_in_merge,
6203 __isl_keep isl_union_map *cluster_map,
6204 __isl_take isl_schedule_constraints *sc)
6206 int i;
6208 for (i = 0; i < graph->n_edge; ++i) {
6209 struct isl_sched_edge *edge = &graph->edge[i];
6211 if (!scc_in_merge[edge->src->scc])
6212 continue;
6213 if (!scc_in_merge[edge->dst->scc])
6214 continue;
6215 sc = collect_edge_constraints(edge, cluster_map, sc);
6218 return sc;
6221 /* Construct a dependence graph for scheduling clusters with respect
6222 * to each other and store the result in "merge_graph".
6223 * In particular, the nodes of the graph correspond to the schedule
6224 * dimensions of the current bands of those clusters that have been
6225 * marked for merging in "c".
6227 * First construct an isl_schedule_constraints object for this domain
6228 * by transforming the edges in "graph" to the domain.
6229 * Then initialize a dependence graph for scheduling from these
6230 * constraints.
6232 static isl_stat init_merge_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
6233 struct isl_clustering *c, struct isl_sched_graph *merge_graph)
6235 isl_union_set *domain;
6236 isl_union_map *cluster_map;
6237 isl_schedule_constraints *sc;
6238 isl_stat r;
6240 domain = collect_domain(ctx, graph, c);
6241 sc = isl_schedule_constraints_on_domain(domain);
6242 if (!sc)
6243 return isl_stat_error;
6244 cluster_map = collect_cluster_map(ctx, graph, c);
6245 sc = collect_constraints(graph, c->scc_in_merge, cluster_map, sc);
6246 isl_union_map_free(cluster_map);
6248 r = graph_init(merge_graph, sc);
6250 isl_schedule_constraints_free(sc);
6252 return r;
6255 /* Compute the maximal number of remaining schedule rows that still need
6256 * to be computed for the nodes that belong to clusters with the maximal
6257 * dimension for the current band (i.e., the band that is to be merged).
6258 * Only clusters that are about to be merged are considered.
6259 * "maxvar" is the maximal dimension for the current band.
6260 * "c" contains information about the clusters.
6262 * Return the maximal number of remaining schedule rows or -1 on error.
6264 static int compute_maxvar_max_slack(int maxvar, struct isl_clustering *c)
6266 int i, j;
6267 int max_slack;
6269 max_slack = 0;
6270 for (i = 0; i < c->n; ++i) {
6271 int nvar;
6272 struct isl_sched_graph *scc;
6274 if (!c->scc_in_merge[i])
6275 continue;
6276 scc = &c->scc[i];
6277 nvar = scc->n_total_row - scc->band_start;
6278 if (nvar != maxvar)
6279 continue;
6280 for (j = 0; j < scc->n; ++j) {
6281 struct isl_sched_node *node = &scc->node[j];
6282 int slack;
6284 if (node_update_vmap(node) < 0)
6285 return -1;
6286 slack = node->nvar - node->rank;
6287 if (slack > max_slack)
6288 max_slack = slack;
6292 return max_slack;
6295 /* If there are any clusters where the dimension of the current band
6296 * (i.e., the band that is to be merged) is smaller than "maxvar" and
6297 * if there are any nodes in such a cluster where the number
6298 * of remaining schedule rows that still need to be computed
6299 * is greater than "max_slack", then return the smallest current band
6300 * dimension of all these clusters. Otherwise return the original value
6301 * of "maxvar". Return -1 in case of any error.
6302 * Only clusters that are about to be merged are considered.
6303 * "c" contains information about the clusters.
6305 static int limit_maxvar_to_slack(int maxvar, int max_slack,
6306 struct isl_clustering *c)
6308 int i, j;
6310 for (i = 0; i < c->n; ++i) {
6311 int nvar;
6312 struct isl_sched_graph *scc;
6314 if (!c->scc_in_merge[i])
6315 continue;
6316 scc = &c->scc[i];
6317 nvar = scc->n_total_row - scc->band_start;
6318 if (nvar >= maxvar)
6319 continue;
6320 for (j = 0; j < scc->n; ++j) {
6321 struct isl_sched_node *node = &scc->node[j];
6322 int slack;
6324 if (node_update_vmap(node) < 0)
6325 return -1;
6326 slack = node->nvar - node->rank;
6327 if (slack > max_slack) {
6328 maxvar = nvar;
6329 break;
6334 return maxvar;
6337 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
6338 * that still need to be computed. In particular, if there is a node
6339 * in a cluster where the dimension of the current band is smaller
6340 * than merge_graph->maxvar, but the number of remaining schedule rows
6341 * is greater than that of any node in a cluster with the maximal
6342 * dimension for the current band (i.e., merge_graph->maxvar),
6343 * then adjust merge_graph->maxvar to the (smallest) current band dimension
6344 * of those clusters. Without this adjustment, the total number of
6345 * schedule dimensions would be increased, resulting in a skewed view
6346 * of the number of coincident dimensions.
6347 * "c" contains information about the clusters.
6349 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
6350 * then there is no point in attempting any merge since it will be rejected
6351 * anyway. Set merge_graph->maxvar to zero in such cases.
6353 static isl_stat adjust_maxvar_to_slack(isl_ctx *ctx,
6354 struct isl_sched_graph *merge_graph, struct isl_clustering *c)
6356 int max_slack, maxvar;
6358 max_slack = compute_maxvar_max_slack(merge_graph->maxvar, c);
6359 if (max_slack < 0)
6360 return isl_stat_error;
6361 maxvar = limit_maxvar_to_slack(merge_graph->maxvar, max_slack, c);
6362 if (maxvar < 0)
6363 return isl_stat_error;
6365 if (maxvar < merge_graph->maxvar) {
6366 if (isl_options_get_schedule_maximize_band_depth(ctx))
6367 merge_graph->maxvar = 0;
6368 else
6369 merge_graph->maxvar = maxvar;
6372 return isl_stat_ok;
6375 /* Return the number of coincident dimensions in the current band of "graph",
6376 * where the nodes of "graph" are assumed to be scheduled by a single band.
6378 static int get_n_coincident(struct isl_sched_graph *graph)
6380 int i;
6382 for (i = graph->band_start; i < graph->n_total_row; ++i)
6383 if (!graph->node[0].coincident[i])
6384 break;
6386 return i - graph->band_start;
6389 /* Should the clusters be merged based on the cluster schedule
6390 * in the current (and only) band of "merge_graph", given that
6391 * coincidence should be maximized?
6393 * If the number of coincident schedule dimensions in the merged band
6394 * would be less than the maximal number of coincident schedule dimensions
6395 * in any of the merged clusters, then the clusters should not be merged.
6397 static isl_bool ok_to_merge_coincident(struct isl_clustering *c,
6398 struct isl_sched_graph *merge_graph)
6400 int i;
6401 int n_coincident;
6402 int max_coincident;
6404 max_coincident = 0;
6405 for (i = 0; i < c->n; ++i) {
6406 if (!c->scc_in_merge[i])
6407 continue;
6408 n_coincident = get_n_coincident(&c->scc[i]);
6409 if (n_coincident > max_coincident)
6410 max_coincident = n_coincident;
6413 n_coincident = get_n_coincident(merge_graph);
6415 return n_coincident >= max_coincident;
6418 /* Return the transformation on "node" expressed by the current (and only)
6419 * band of "merge_graph" applied to the clusters in "c".
6421 * First find the representation of "node" in its SCC in "c" and
6422 * extract the transformation expressed by the current band.
6423 * Then extract the transformation applied by "merge_graph"
6424 * to the cluster to which this SCC belongs.
6425 * Combine the two to obtain the complete transformation on the node.
6427 * Note that the range of the first transformation is an anonymous space,
6428 * while the domain of the second is named "cluster_X". The range
6429 * of the former therefore needs to be adjusted before the two
6430 * can be combined.
6432 static __isl_give isl_map *extract_node_transformation(isl_ctx *ctx,
6433 struct isl_sched_node *node, struct isl_clustering *c,
6434 struct isl_sched_graph *merge_graph)
6436 struct isl_sched_node *scc_node, *cluster_node;
6437 int start, n;
6438 isl_id *id;
6439 isl_space *space;
6440 isl_multi_aff *ma, *ma2;
6442 scc_node = graph_find_node(ctx, &c->scc[node->scc], node->space);
6443 if (scc_node && !is_node(&c->scc[node->scc], scc_node))
6444 isl_die(ctx, isl_error_internal, "unable to find node",
6445 return NULL);
6446 start = c->scc[node->scc].band_start;
6447 n = c->scc[node->scc].n_total_row - start;
6448 ma = node_extract_partial_schedule_multi_aff(scc_node, start, n);
6449 space = cluster_space(&c->scc[node->scc], c->scc_cluster[node->scc]);
6450 cluster_node = graph_find_node(ctx, merge_graph, space);
6451 if (cluster_node && !is_node(merge_graph, cluster_node))
6452 isl_die(ctx, isl_error_internal, "unable to find cluster",
6453 space = isl_space_free(space));
6454 id = isl_space_get_tuple_id(space, isl_dim_set);
6455 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out, id);
6456 isl_space_free(space);
6457 n = merge_graph->n_total_row;
6458 ma2 = node_extract_partial_schedule_multi_aff(cluster_node, 0, n);
6459 ma = isl_multi_aff_pullback_multi_aff(ma2, ma);
6461 return isl_map_from_multi_aff(ma);
6464 /* Give a set of distances "set", are they bounded by a small constant
6465 * in direction "pos"?
6466 * In practice, check if they are bounded by 2 by checking that there
6467 * are no elements with a value greater than or equal to 3 or
6468 * smaller than or equal to -3.
6470 static isl_bool distance_is_bounded(__isl_keep isl_set *set, int pos)
6472 isl_bool bounded;
6473 isl_set *test;
6475 if (!set)
6476 return isl_bool_error;
6478 test = isl_set_copy(set);
6479 test = isl_set_lower_bound_si(test, isl_dim_set, pos, 3);
6480 bounded = isl_set_is_empty(test);
6481 isl_set_free(test);
6483 if (bounded < 0 || !bounded)
6484 return bounded;
6486 test = isl_set_copy(set);
6487 test = isl_set_upper_bound_si(test, isl_dim_set, pos, -3);
6488 bounded = isl_set_is_empty(test);
6489 isl_set_free(test);
6491 return bounded;
6494 /* Does the set "set" have a fixed (but possible parametric) value
6495 * at dimension "pos"?
6497 static isl_bool has_single_value(__isl_keep isl_set *set, int pos)
6499 int n;
6500 isl_bool single;
6502 if (!set)
6503 return isl_bool_error;
6504 set = isl_set_copy(set);
6505 n = isl_set_dim(set, isl_dim_set);
6506 set = isl_set_project_out(set, isl_dim_set, pos + 1, n - (pos + 1));
6507 set = isl_set_project_out(set, isl_dim_set, 0, pos);
6508 single = isl_set_is_singleton(set);
6509 isl_set_free(set);
6511 return single;
6514 /* Does "map" have a fixed (but possible parametric) value
6515 * at dimension "pos" of either its domain or its range?
6517 static isl_bool has_singular_src_or_dst(__isl_keep isl_map *map, int pos)
6519 isl_set *set;
6520 isl_bool single;
6522 set = isl_map_domain(isl_map_copy(map));
6523 single = has_single_value(set, pos);
6524 isl_set_free(set);
6526 if (single < 0 || single)
6527 return single;
6529 set = isl_map_range(isl_map_copy(map));
6530 single = has_single_value(set, pos);
6531 isl_set_free(set);
6533 return single;
6536 /* Does the edge "edge" from "graph" have bounded dependence distances
6537 * in the merged graph "merge_graph" of a selection of clusters in "c"?
6539 * Extract the complete transformations of the source and destination
6540 * nodes of the edge, apply them to the edge constraints and
6541 * compute the differences. Finally, check if these differences are bounded
6542 * in each direction.
6544 * If the dimension of the band is greater than the number of
6545 * dimensions that can be expected to be optimized by the edge
6546 * (based on its weight), then also allow the differences to be unbounded
6547 * in the remaining dimensions, but only if either the source or
6548 * the destination has a fixed value in that direction.
6549 * This allows a statement that produces values that are used by
6550 * several instances of another statement to be merged with that
6551 * other statement.
6552 * However, merging such clusters will introduce an inherently
6553 * large proximity distance inside the merged cluster, meaning
6554 * that proximity distances will no longer be optimized in
6555 * subsequent merges. These merges are therefore only allowed
6556 * after all other possible merges have been tried.
6557 * The first time such a merge is encountered, the weight of the edge
6558 * is replaced by a negative weight. The second time (i.e., after
6559 * all merges over edges with a non-negative weight have been tried),
6560 * the merge is allowed.
6562 static isl_bool has_bounded_distances(isl_ctx *ctx, struct isl_sched_edge *edge,
6563 struct isl_sched_graph *graph, struct isl_clustering *c,
6564 struct isl_sched_graph *merge_graph)
6566 int i, n, n_slack;
6567 isl_bool bounded;
6568 isl_map *map, *t;
6569 isl_set *dist;
6571 map = isl_map_copy(edge->map);
6572 t = extract_node_transformation(ctx, edge->src, c, merge_graph);
6573 map = isl_map_apply_domain(map, t);
6574 t = extract_node_transformation(ctx, edge->dst, c, merge_graph);
6575 map = isl_map_apply_range(map, t);
6576 dist = isl_map_deltas(isl_map_copy(map));
6578 bounded = isl_bool_true;
6579 n = isl_set_dim(dist, isl_dim_set);
6580 n_slack = n - edge->weight;
6581 if (edge->weight < 0)
6582 n_slack -= graph->max_weight + 1;
6583 for (i = 0; i < n; ++i) {
6584 isl_bool bounded_i, singular_i;
6586 bounded_i = distance_is_bounded(dist, i);
6587 if (bounded_i < 0)
6588 goto error;
6589 if (bounded_i)
6590 continue;
6591 if (edge->weight >= 0)
6592 bounded = isl_bool_false;
6593 n_slack--;
6594 if (n_slack < 0)
6595 break;
6596 singular_i = has_singular_src_or_dst(map, i);
6597 if (singular_i < 0)
6598 goto error;
6599 if (singular_i)
6600 continue;
6601 bounded = isl_bool_false;
6602 break;
6604 if (!bounded && i >= n && edge->weight >= 0)
6605 edge->weight -= graph->max_weight + 1;
6606 isl_map_free(map);
6607 isl_set_free(dist);
6609 return bounded;
6610 error:
6611 isl_map_free(map);
6612 isl_set_free(dist);
6613 return isl_bool_error;
6616 /* Should the clusters be merged based on the cluster schedule
6617 * in the current (and only) band of "merge_graph"?
6618 * "graph" is the original dependence graph, while "c" records
6619 * which SCCs are involved in the latest merge.
6621 * In particular, is there at least one proximity constraint
6622 * that is optimized by the merge?
6624 * A proximity constraint is considered to be optimized
6625 * if the dependence distances are small.
6627 static isl_bool ok_to_merge_proximity(isl_ctx *ctx,
6628 struct isl_sched_graph *graph, struct isl_clustering *c,
6629 struct isl_sched_graph *merge_graph)
6631 int i;
6633 for (i = 0; i < graph->n_edge; ++i) {
6634 struct isl_sched_edge *edge = &graph->edge[i];
6635 isl_bool bounded;
6637 if (!is_proximity(edge))
6638 continue;
6639 if (!c->scc_in_merge[edge->src->scc])
6640 continue;
6641 if (!c->scc_in_merge[edge->dst->scc])
6642 continue;
6643 if (c->scc_cluster[edge->dst->scc] ==
6644 c->scc_cluster[edge->src->scc])
6645 continue;
6646 bounded = has_bounded_distances(ctx, edge, graph, c,
6647 merge_graph);
6648 if (bounded < 0 || bounded)
6649 return bounded;
6652 return isl_bool_false;
6655 /* Should the clusters be merged based on the cluster schedule
6656 * in the current (and only) band of "merge_graph"?
6657 * "graph" is the original dependence graph, while "c" records
6658 * which SCCs are involved in the latest merge.
6660 * If the current band is empty, then the clusters should not be merged.
6662 * If the band depth should be maximized and the merge schedule
6663 * is incomplete (meaning that the dimension of some of the schedule
6664 * bands in the original schedule will be reduced), then the clusters
6665 * should not be merged.
6667 * If the schedule_maximize_coincidence option is set, then check that
6668 * the number of coincident schedule dimensions is not reduced.
6670 * Finally, only allow the merge if at least one proximity
6671 * constraint is optimized.
6673 static isl_bool ok_to_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
6674 struct isl_clustering *c, struct isl_sched_graph *merge_graph)
6676 if (merge_graph->n_total_row == merge_graph->band_start)
6677 return isl_bool_false;
6679 if (isl_options_get_schedule_maximize_band_depth(ctx) &&
6680 merge_graph->n_total_row < merge_graph->maxvar)
6681 return isl_bool_false;
6683 if (isl_options_get_schedule_maximize_coincidence(ctx)) {
6684 isl_bool ok;
6686 ok = ok_to_merge_coincident(c, merge_graph);
6687 if (ok < 0 || !ok)
6688 return ok;
6691 return ok_to_merge_proximity(ctx, graph, c, merge_graph);
6694 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
6695 * of the schedule in "node" and return the result.
6697 * That is, essentially compute
6699 * T * N(first:first+n-1)
6701 * taking into account the constant term and the parameter coefficients
6702 * in "t_node".
6704 static __isl_give isl_mat *node_transformation(isl_ctx *ctx,
6705 struct isl_sched_node *t_node, struct isl_sched_node *node,
6706 int first, int n)
6708 int i, j;
6709 isl_mat *t;
6710 int n_row, n_col, n_param, n_var;
6712 n_param = node->nparam;
6713 n_var = node->nvar;
6714 n_row = isl_mat_rows(t_node->sched);
6715 n_col = isl_mat_cols(node->sched);
6716 t = isl_mat_alloc(ctx, n_row, n_col);
6717 if (!t)
6718 return NULL;
6719 for (i = 0; i < n_row; ++i) {
6720 isl_seq_cpy(t->row[i], t_node->sched->row[i], 1 + n_param);
6721 isl_seq_clr(t->row[i] + 1 + n_param, n_var);
6722 for (j = 0; j < n; ++j)
6723 isl_seq_addmul(t->row[i],
6724 t_node->sched->row[i][1 + n_param + j],
6725 node->sched->row[first + j],
6726 1 + n_param + n_var);
6728 return t;
6731 /* Apply the cluster schedule in "t_node" to the current band
6732 * schedule of the nodes in "graph".
6734 * In particular, replace the rows starting at band_start
6735 * by the result of applying the cluster schedule in "t_node"
6736 * to the original rows.
6738 * The coincidence of the schedule is determined by the coincidence
6739 * of the cluster schedule.
6741 static isl_stat transform(isl_ctx *ctx, struct isl_sched_graph *graph,
6742 struct isl_sched_node *t_node)
6744 int i, j;
6745 int n_new;
6746 int start, n;
6748 start = graph->band_start;
6749 n = graph->n_total_row - start;
6751 n_new = isl_mat_rows(t_node->sched);
6752 for (i = 0; i < graph->n; ++i) {
6753 struct isl_sched_node *node = &graph->node[i];
6754 isl_mat *t;
6756 t = node_transformation(ctx, t_node, node, start, n);
6757 node->sched = isl_mat_drop_rows(node->sched, start, n);
6758 node->sched = isl_mat_concat(node->sched, t);
6759 node->sched_map = isl_map_free(node->sched_map);
6760 if (!node->sched)
6761 return isl_stat_error;
6762 for (j = 0; j < n_new; ++j)
6763 node->coincident[start + j] = t_node->coincident[j];
6765 graph->n_total_row -= n;
6766 graph->n_row -= n;
6767 graph->n_total_row += n_new;
6768 graph->n_row += n_new;
6770 return isl_stat_ok;
6773 /* Merge the clusters marked for merging in "c" into a single
6774 * cluster using the cluster schedule in the current band of "merge_graph".
6775 * The representative SCC for the new cluster is the SCC with
6776 * the smallest index.
6778 * The current band schedule of each SCC in the new cluster is obtained
6779 * by applying the schedule of the corresponding original cluster
6780 * to the original band schedule.
6781 * All SCCs in the new cluster have the same number of schedule rows.
6783 static isl_stat merge(isl_ctx *ctx, struct isl_clustering *c,
6784 struct isl_sched_graph *merge_graph)
6786 int i;
6787 int cluster = -1;
6788 isl_space *space;
6790 for (i = 0; i < c->n; ++i) {
6791 struct isl_sched_node *node;
6793 if (!c->scc_in_merge[i])
6794 continue;
6795 if (cluster < 0)
6796 cluster = i;
6797 space = cluster_space(&c->scc[i], c->scc_cluster[i]);
6798 node = graph_find_node(ctx, merge_graph, space);
6799 isl_space_free(space);
6800 if (!node)
6801 return isl_stat_error;
6802 if (!is_node(merge_graph, node))
6803 isl_die(ctx, isl_error_internal,
6804 "unable to find cluster",
6805 return isl_stat_error);
6806 if (transform(ctx, &c->scc[i], node) < 0)
6807 return isl_stat_error;
6808 c->scc_cluster[i] = cluster;
6811 return isl_stat_ok;
6814 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
6815 * by scheduling the current cluster bands with respect to each other.
6817 * Construct a dependence graph with a space for each cluster and
6818 * with the coordinates of each space corresponding to the schedule
6819 * dimensions of the current band of that cluster.
6820 * Construct a cluster schedule in this cluster dependence graph and
6821 * apply it to the current cluster bands if it is applicable
6822 * according to ok_to_merge.
6824 * If the number of remaining schedule dimensions in a cluster
6825 * with a non-maximal current schedule dimension is greater than
6826 * the number of remaining schedule dimensions in clusters
6827 * with a maximal current schedule dimension, then restrict
6828 * the number of rows to be computed in the cluster schedule
6829 * to the minimal such non-maximal current schedule dimension.
6830 * Do this by adjusting merge_graph.maxvar.
6832 * Return isl_bool_true if the clusters have effectively been merged
6833 * into a single cluster.
6835 * Note that since the standard scheduling algorithm minimizes the maximal
6836 * distance over proximity constraints, the proximity constraints between
6837 * the merged clusters may not be optimized any further than what is
6838 * sufficient to bring the distances within the limits of the internal
6839 * proximity constraints inside the individual clusters.
6840 * It may therefore make sense to perform an additional translation step
6841 * to bring the clusters closer to each other, while maintaining
6842 * the linear part of the merging schedule found using the standard
6843 * scheduling algorithm.
6845 static isl_bool try_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
6846 struct isl_clustering *c)
6848 struct isl_sched_graph merge_graph = { 0 };
6849 isl_bool merged;
6851 if (init_merge_graph(ctx, graph, c, &merge_graph) < 0)
6852 goto error;
6854 if (compute_maxvar(&merge_graph) < 0)
6855 goto error;
6856 if (adjust_maxvar_to_slack(ctx, &merge_graph,c) < 0)
6857 goto error;
6858 if (compute_schedule_wcc_band(ctx, &merge_graph) < 0)
6859 goto error;
6860 merged = ok_to_merge(ctx, graph, c, &merge_graph);
6861 if (merged && merge(ctx, c, &merge_graph) < 0)
6862 goto error;
6864 graph_free(ctx, &merge_graph);
6865 return merged;
6866 error:
6867 graph_free(ctx, &merge_graph);
6868 return isl_bool_error;
6871 /* Is there any edge marked "no_merge" between two SCCs that are
6872 * about to be merged (i.e., that are set in "scc_in_merge")?
6873 * "merge_edge" is the proximity edge along which the clusters of SCCs
6874 * are going to be merged.
6876 * If there is any edge between two SCCs with a negative weight,
6877 * while the weight of "merge_edge" is non-negative, then this
6878 * means that the edge was postponed. "merge_edge" should then
6879 * also be postponed since merging along the edge with negative weight should
6880 * be postponed until all edges with non-negative weight have been tried.
6881 * Replace the weight of "merge_edge" by a negative weight as well and
6882 * tell the caller not to attempt a merge.
6884 static int any_no_merge(struct isl_sched_graph *graph, int *scc_in_merge,
6885 struct isl_sched_edge *merge_edge)
6887 int i;
6889 for (i = 0; i < graph->n_edge; ++i) {
6890 struct isl_sched_edge *edge = &graph->edge[i];
6892 if (!scc_in_merge[edge->src->scc])
6893 continue;
6894 if (!scc_in_merge[edge->dst->scc])
6895 continue;
6896 if (edge->no_merge)
6897 return 1;
6898 if (merge_edge->weight >= 0 && edge->weight < 0) {
6899 merge_edge->weight -= graph->max_weight + 1;
6900 return 1;
6904 return 0;
6907 /* Merge the two clusters in "c" connected by the edge in "graph"
6908 * with index "edge" into a single cluster.
6909 * If it turns out to be impossible to merge these two clusters,
6910 * then mark the edge as "no_merge" such that it will not be
6911 * considered again.
6913 * First mark all SCCs that need to be merged. This includes the SCCs
6914 * in the two clusters, but it may also include the SCCs
6915 * of intermediate clusters.
6916 * If there is already a no_merge edge between any pair of such SCCs,
6917 * then simply mark the current edge as no_merge as well.
6918 * Likewise, if any of those edges was postponed by has_bounded_distances,
6919 * then postpone the current edge as well.
6920 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
6921 * if the clusters did not end up getting merged, unless the non-merge
6922 * is due to the fact that the edge was postponed. This postponement
6923 * can be recognized by a change in weight (from non-negative to negative).
6925 static isl_stat merge_clusters_along_edge(isl_ctx *ctx,
6926 struct isl_sched_graph *graph, int edge, struct isl_clustering *c)
6928 isl_bool merged;
6929 int edge_weight = graph->edge[edge].weight;
6931 if (mark_merge_sccs(ctx, graph, edge, c) < 0)
6932 return isl_stat_error;
6934 if (any_no_merge(graph, c->scc_in_merge, &graph->edge[edge]))
6935 merged = isl_bool_false;
6936 else
6937 merged = try_merge(ctx, graph, c);
6938 if (merged < 0)
6939 return isl_stat_error;
6940 if (!merged && edge_weight == graph->edge[edge].weight)
6941 graph->edge[edge].no_merge = 1;
6943 return isl_stat_ok;
6946 /* Does "node" belong to the cluster identified by "cluster"?
6948 static int node_cluster_exactly(struct isl_sched_node *node, int cluster)
6950 return node->cluster == cluster;
6953 /* Does "edge" connect two nodes belonging to the cluster
6954 * identified by "cluster"?
6956 static int edge_cluster_exactly(struct isl_sched_edge *edge, int cluster)
6958 return edge->src->cluster == cluster && edge->dst->cluster == cluster;
6961 /* Swap the schedule of "node1" and "node2".
6962 * Both nodes have been derived from the same node in a common parent graph.
6963 * Since the "coincident" field is shared with that node
6964 * in the parent graph, there is no need to also swap this field.
6966 static void swap_sched(struct isl_sched_node *node1,
6967 struct isl_sched_node *node2)
6969 isl_mat *sched;
6970 isl_map *sched_map;
6972 sched = node1->sched;
6973 node1->sched = node2->sched;
6974 node2->sched = sched;
6976 sched_map = node1->sched_map;
6977 node1->sched_map = node2->sched_map;
6978 node2->sched_map = sched_map;
6981 /* Copy the current band schedule from the SCCs that form the cluster
6982 * with index "pos" to the actual cluster at position "pos".
6983 * By construction, the index of the first SCC that belongs to the cluster
6984 * is also "pos".
6986 * The order of the nodes inside both the SCCs and the cluster
6987 * is assumed to be same as the order in the original "graph".
6989 * Since the SCC graphs will no longer be used after this function,
6990 * the schedules are actually swapped rather than copied.
6992 static isl_stat copy_partial(struct isl_sched_graph *graph,
6993 struct isl_clustering *c, int pos)
6995 int i, j;
6997 c->cluster[pos].n_total_row = c->scc[pos].n_total_row;
6998 c->cluster[pos].n_row = c->scc[pos].n_row;
6999 c->cluster[pos].maxvar = c->scc[pos].maxvar;
7000 j = 0;
7001 for (i = 0; i < graph->n; ++i) {
7002 int k;
7003 int s;
7005 if (graph->node[i].cluster != pos)
7006 continue;
7007 s = graph->node[i].scc;
7008 k = c->scc_node[s]++;
7009 swap_sched(&c->cluster[pos].node[j], &c->scc[s].node[k]);
7010 if (c->scc[s].maxvar > c->cluster[pos].maxvar)
7011 c->cluster[pos].maxvar = c->scc[s].maxvar;
7012 ++j;
7015 return isl_stat_ok;
7018 /* Is there a (conditional) validity dependence from node[j] to node[i],
7019 * forcing node[i] to follow node[j] or do the nodes belong to the same
7020 * cluster?
7022 static isl_bool node_follows_strong_or_same_cluster(int i, int j, void *user)
7024 struct isl_sched_graph *graph = user;
7026 if (graph->node[i].cluster == graph->node[j].cluster)
7027 return isl_bool_true;
7028 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
7031 /* Extract the merged clusters of SCCs in "graph", sort them, and
7032 * store them in c->clusters. Update c->scc_cluster accordingly.
7034 * First keep track of the cluster containing the SCC to which a node
7035 * belongs in the node itself.
7036 * Then extract the clusters into c->clusters, copying the current
7037 * band schedule from the SCCs that belong to the cluster.
7038 * Do this only once per cluster.
7040 * Finally, topologically sort the clusters and update c->scc_cluster
7041 * to match the new scc numbering. While the SCCs were originally
7042 * sorted already, some SCCs that depend on some other SCCs may
7043 * have been merged with SCCs that appear before these other SCCs.
7044 * A reordering may therefore be required.
7046 static isl_stat extract_clusters(isl_ctx *ctx, struct isl_sched_graph *graph,
7047 struct isl_clustering *c)
7049 int i;
7051 for (i = 0; i < graph->n; ++i)
7052 graph->node[i].cluster = c->scc_cluster[graph->node[i].scc];
7054 for (i = 0; i < graph->scc; ++i) {
7055 if (c->scc_cluster[i] != i)
7056 continue;
7057 if (extract_sub_graph(ctx, graph, &node_cluster_exactly,
7058 &edge_cluster_exactly, i, &c->cluster[i]) < 0)
7059 return isl_stat_error;
7060 c->cluster[i].src_scc = -1;
7061 c->cluster[i].dst_scc = -1;
7062 if (copy_partial(graph, c, i) < 0)
7063 return isl_stat_error;
7066 if (detect_ccs(ctx, graph, &node_follows_strong_or_same_cluster) < 0)
7067 return isl_stat_error;
7068 for (i = 0; i < graph->n; ++i)
7069 c->scc_cluster[graph->node[i].scc] = graph->node[i].cluster;
7071 return isl_stat_ok;
7074 /* Compute weights on the proximity edges of "graph" that can
7075 * be used by find_proximity to find the most appropriate
7076 * proximity edge to use to merge two clusters in "c".
7077 * The weights are also used by has_bounded_distances to determine
7078 * whether the merge should be allowed.
7079 * Store the maximum of the computed weights in graph->max_weight.
7081 * The computed weight is a measure for the number of remaining schedule
7082 * dimensions that can still be completely aligned.
7083 * In particular, compute the number of equalities between
7084 * input dimensions and output dimensions in the proximity constraints.
7085 * The directions that are already handled by outer schedule bands
7086 * are projected out prior to determining this number.
7088 * Edges that will never be considered by find_proximity are ignored.
7090 static isl_stat compute_weights(struct isl_sched_graph *graph,
7091 struct isl_clustering *c)
7093 int i;
7095 graph->max_weight = 0;
7097 for (i = 0; i < graph->n_edge; ++i) {
7098 struct isl_sched_edge *edge = &graph->edge[i];
7099 struct isl_sched_node *src = edge->src;
7100 struct isl_sched_node *dst = edge->dst;
7101 isl_basic_map *hull;
7102 isl_bool prox;
7103 int n_in, n_out;
7105 prox = is_non_empty_proximity(edge);
7106 if (prox < 0)
7107 return isl_stat_error;
7108 if (!prox)
7109 continue;
7110 if (bad_cluster(&c->scc[edge->src->scc]) ||
7111 bad_cluster(&c->scc[edge->dst->scc]))
7112 continue;
7113 if (c->scc_cluster[edge->dst->scc] ==
7114 c->scc_cluster[edge->src->scc])
7115 continue;
7117 hull = isl_map_affine_hull(isl_map_copy(edge->map));
7118 hull = isl_basic_map_transform_dims(hull, isl_dim_in, 0,
7119 isl_mat_copy(src->vmap));
7120 hull = isl_basic_map_transform_dims(hull, isl_dim_out, 0,
7121 isl_mat_copy(dst->vmap));
7122 hull = isl_basic_map_project_out(hull,
7123 isl_dim_in, 0, src->rank);
7124 hull = isl_basic_map_project_out(hull,
7125 isl_dim_out, 0, dst->rank);
7126 hull = isl_basic_map_remove_divs(hull);
7127 n_in = isl_basic_map_dim(hull, isl_dim_in);
7128 n_out = isl_basic_map_dim(hull, isl_dim_out);
7129 hull = isl_basic_map_drop_constraints_not_involving_dims(hull,
7130 isl_dim_in, 0, n_in);
7131 hull = isl_basic_map_drop_constraints_not_involving_dims(hull,
7132 isl_dim_out, 0, n_out);
7133 if (!hull)
7134 return isl_stat_error;
7135 edge->weight = isl_basic_map_n_equality(hull);
7136 isl_basic_map_free(hull);
7138 if (edge->weight > graph->max_weight)
7139 graph->max_weight = edge->weight;
7142 return isl_stat_ok;
7145 /* Call compute_schedule_finish_band on each of the clusters in "c"
7146 * in their topological order. This order is determined by the scc
7147 * fields of the nodes in "graph".
7148 * Combine the results in a sequence expressing the topological order.
7150 * If there is only one cluster left, then there is no need to introduce
7151 * a sequence node. Also, in this case, the cluster necessarily contains
7152 * the SCC at position 0 in the original graph and is therefore also
7153 * stored in the first cluster of "c".
7155 static __isl_give isl_schedule_node *finish_bands_clustering(
7156 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
7157 struct isl_clustering *c)
7159 int i;
7160 isl_ctx *ctx;
7161 isl_union_set_list *filters;
7163 if (graph->scc == 1)
7164 return compute_schedule_finish_band(node, &c->cluster[0], 0);
7166 ctx = isl_schedule_node_get_ctx(node);
7168 filters = extract_sccs(ctx, graph);
7169 node = isl_schedule_node_insert_sequence(node, filters);
7171 for (i = 0; i < graph->scc; ++i) {
7172 int j = c->scc_cluster[i];
7173 node = isl_schedule_node_child(node, i);
7174 node = isl_schedule_node_child(node, 0);
7175 node = compute_schedule_finish_band(node, &c->cluster[j], 0);
7176 node = isl_schedule_node_parent(node);
7177 node = isl_schedule_node_parent(node);
7180 return node;
7183 /* Compute a schedule for a connected dependence graph by first considering
7184 * each strongly connected component (SCC) in the graph separately and then
7185 * incrementally combining them into clusters.
7186 * Return the updated schedule node.
7188 * Initially, each cluster consists of a single SCC, each with its
7189 * own band schedule. The algorithm then tries to merge pairs
7190 * of clusters along a proximity edge until no more suitable
7191 * proximity edges can be found. During this merging, the schedule
7192 * is maintained in the individual SCCs.
7193 * After the merging is completed, the full resulting clusters
7194 * are extracted and in finish_bands_clustering,
7195 * compute_schedule_finish_band is called on each of them to integrate
7196 * the band into "node" and to continue the computation.
7198 * compute_weights initializes the weights that are used by find_proximity.
7200 static __isl_give isl_schedule_node *compute_schedule_wcc_clustering(
7201 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
7203 isl_ctx *ctx;
7204 struct isl_clustering c;
7205 int i;
7207 ctx = isl_schedule_node_get_ctx(node);
7209 if (clustering_init(ctx, &c, graph) < 0)
7210 goto error;
7212 if (compute_weights(graph, &c) < 0)
7213 goto error;
7215 for (;;) {
7216 i = find_proximity(graph, &c);
7217 if (i < 0)
7218 goto error;
7219 if (i >= graph->n_edge)
7220 break;
7221 if (merge_clusters_along_edge(ctx, graph, i, &c) < 0)
7222 goto error;
7225 if (extract_clusters(ctx, graph, &c) < 0)
7226 goto error;
7228 node = finish_bands_clustering(node, graph, &c);
7230 clustering_free(ctx, &c);
7231 return node;
7232 error:
7233 clustering_free(ctx, &c);
7234 return isl_schedule_node_free(node);
7237 /* Compute a schedule for a connected dependence graph and return
7238 * the updated schedule node.
7240 * If Feautrier's algorithm is selected, we first recursively try to satisfy
7241 * as many validity dependences as possible. When all validity dependences
7242 * are satisfied we extend the schedule to a full-dimensional schedule.
7244 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
7245 * depending on whether the user has selected the option to try and
7246 * compute a schedule for the entire (weakly connected) component first.
7247 * If there is only a single strongly connected component (SCC), then
7248 * there is no point in trying to combine SCCs
7249 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
7250 * is called instead.
7252 static __isl_give isl_schedule_node *compute_schedule_wcc(
7253 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
7255 isl_ctx *ctx;
7257 if (!node)
7258 return NULL;
7260 ctx = isl_schedule_node_get_ctx(node);
7261 if (detect_sccs(ctx, graph) < 0)
7262 return isl_schedule_node_free(node);
7264 if (compute_maxvar(graph) < 0)
7265 return isl_schedule_node_free(node);
7267 if (need_feautrier_step(ctx, graph))
7268 return compute_schedule_wcc_feautrier(node, graph);
7270 if (graph->scc <= 1 || isl_options_get_schedule_whole_component(ctx))
7271 return compute_schedule_wcc_whole(node, graph);
7272 else
7273 return compute_schedule_wcc_clustering(node, graph);
7276 /* Compute a schedule for each group of nodes identified by node->scc
7277 * separately and then combine them in a sequence node (or as set node
7278 * if graph->weak is set) inserted at position "node" of the schedule tree.
7279 * Return the updated schedule node.
7281 * If "wcc" is set then each of the groups belongs to a single
7282 * weakly connected component in the dependence graph so that
7283 * there is no need for compute_sub_schedule to look for weakly
7284 * connected components.
7286 * If a set node would be introduced and if the number of components
7287 * is equal to the number of nodes, then check if the schedule
7288 * is already complete. If so, a redundant set node would be introduced
7289 * (without any further descendants) stating that the statements
7290 * can be executed in arbitrary order, which is also expressed
7291 * by the absence of any node. Refrain from inserting any nodes
7292 * in this case and simply return.
7294 static __isl_give isl_schedule_node *compute_component_schedule(
7295 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
7296 int wcc)
7298 int component;
7299 isl_ctx *ctx;
7300 isl_union_set_list *filters;
7302 if (!node)
7303 return NULL;
7305 if (graph->weak && graph->scc == graph->n) {
7306 if (compute_maxvar(graph) < 0)
7307 return isl_schedule_node_free(node);
7308 if (graph->n_row >= graph->maxvar)
7309 return node;
7312 ctx = isl_schedule_node_get_ctx(node);
7313 filters = extract_sccs(ctx, graph);
7314 if (graph->weak)
7315 node = isl_schedule_node_insert_set(node, filters);
7316 else
7317 node = isl_schedule_node_insert_sequence(node, filters);
7319 for (component = 0; component < graph->scc; ++component) {
7320 node = isl_schedule_node_child(node, component);
7321 node = isl_schedule_node_child(node, 0);
7322 node = compute_sub_schedule(node, ctx, graph,
7323 &node_scc_exactly,
7324 &edge_scc_exactly, component, wcc);
7325 node = isl_schedule_node_parent(node);
7326 node = isl_schedule_node_parent(node);
7329 return node;
7332 /* Compute a schedule for the given dependence graph and insert it at "node".
7333 * Return the updated schedule node.
7335 * We first check if the graph is connected (through validity and conditional
7336 * validity dependences) and, if not, compute a schedule
7337 * for each component separately.
7338 * If the schedule_serialize_sccs option is set, then we check for strongly
7339 * connected components instead and compute a separate schedule for
7340 * each such strongly connected component.
7342 static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
7343 struct isl_sched_graph *graph)
7345 isl_ctx *ctx;
7347 if (!node)
7348 return NULL;
7350 ctx = isl_schedule_node_get_ctx(node);
7351 if (isl_options_get_schedule_serialize_sccs(ctx)) {
7352 if (detect_sccs(ctx, graph) < 0)
7353 return isl_schedule_node_free(node);
7354 } else {
7355 if (detect_wccs(ctx, graph) < 0)
7356 return isl_schedule_node_free(node);
7359 if (graph->scc > 1)
7360 return compute_component_schedule(node, graph, 1);
7362 return compute_schedule_wcc(node, graph);
7365 /* Compute a schedule on sc->domain that respects the given schedule
7366 * constraints.
7368 * In particular, the schedule respects all the validity dependences.
7369 * If the default isl scheduling algorithm is used, it tries to minimize
7370 * the dependence distances over the proximity dependences.
7371 * If Feautrier's scheduling algorithm is used, the proximity dependence
7372 * distances are only minimized during the extension to a full-dimensional
7373 * schedule.
7375 * If there are any condition and conditional validity dependences,
7376 * then the conditional validity dependences may be violated inside
7377 * a tilable band, provided they have no adjacent non-local
7378 * condition dependences.
7380 __isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
7381 __isl_take isl_schedule_constraints *sc)
7383 isl_ctx *ctx = isl_schedule_constraints_get_ctx(sc);
7384 struct isl_sched_graph graph = { 0 };
7385 isl_schedule *sched;
7386 isl_schedule_node *node;
7387 isl_union_set *domain;
7389 sc = isl_schedule_constraints_align_params(sc);
7391 domain = isl_schedule_constraints_get_domain(sc);
7392 if (isl_union_set_n_set(domain) == 0) {
7393 isl_schedule_constraints_free(sc);
7394 return isl_schedule_from_domain(domain);
7397 if (graph_init(&graph, sc) < 0)
7398 domain = isl_union_set_free(domain);
7400 node = isl_schedule_node_from_domain(domain);
7401 node = isl_schedule_node_child(node, 0);
7402 if (graph.n > 0)
7403 node = compute_schedule(node, &graph);
7404 sched = isl_schedule_node_get_schedule(node);
7405 isl_schedule_node_free(node);
7407 graph_free(ctx, &graph);
7408 isl_schedule_constraints_free(sc);
7410 return sched;
7413 /* Compute a schedule for the given union of domains that respects
7414 * all the validity dependences and minimizes
7415 * the dependence distances over the proximity dependences.
7417 * This function is kept for backward compatibility.
7419 __isl_give isl_schedule *isl_union_set_compute_schedule(
7420 __isl_take isl_union_set *domain,
7421 __isl_take isl_union_map *validity,
7422 __isl_take isl_union_map *proximity)
7424 isl_schedule_constraints *sc;
7426 sc = isl_schedule_constraints_on_domain(domain);
7427 sc = isl_schedule_constraints_set_validity(sc, validity);
7428 sc = isl_schedule_constraints_set_proximity(sc, proximity);
7430 return isl_schedule_constraints_compute_schedule(sc);