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,
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>
23 #include <isl/constraint.h>
24 #include <isl/schedule.h>
25 #include <isl_schedule_constraints.h>
26 #include <isl/schedule_node.h>
27 #include <isl_mat_private.h>
28 #include <isl_vec_private.h>
30 #include <isl/union_set.h>
33 #include <isl_dim_map.h>
34 #include <isl/map_to_basic_set.h>
36 #include <isl_options_private.h>
37 #include <isl_tarjan.h>
38 #include <isl_morph.h>
40 #include <isl_val_private.h>
43 * The scheduling algorithm implemented in this file was inspired by
44 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
45 * Parallelization and Locality Optimization in the Polyhedral Model".
49 /* Internal information about a node that is used during the construction
51 * space represents the original space in which the domain lives;
52 * that is, the space is not affected by compression
53 * sched is a matrix representation of the schedule being constructed
54 * for this node; if compressed is set, then this schedule is
55 * defined over the compressed domain space
56 * sched_map is an isl_map representation of the same (partial) schedule
57 * sched_map may be NULL; if compressed is set, then this map
58 * is defined over the uncompressed domain space
59 * rank is the number of linearly independent rows in the linear part
61 * the rows of "vmap" represent a change of basis for the node
62 * variables; the first rank rows span the linear part of
63 * the schedule rows; the remaining rows are linearly independent
64 * the rows of "indep" represent linear combinations of the schedule
65 * coefficients that are non-zero when the schedule coefficients are
66 * linearly independent of previously computed schedule rows.
67 * start is the first variable in the LP problem in the sequences that
68 * represents the schedule coefficients of this node
69 * nvar is the dimension of the domain
70 * nparam is the number of parameters or 0 if we are not constructing
71 * a parametric schedule
73 * If compressed is set, then hull represents the constraints
74 * that were used to derive the compression, while compress and
75 * decompress map the original space to the compressed space and
78 * scc is the index of SCC (or WCC) this node belongs to
80 * "cluster" is only used inside extract_clusters and identifies
81 * the cluster of SCCs that the node belongs to.
83 * coincident contains a boolean for each of the rows of the schedule,
84 * indicating whether the corresponding scheduling dimension satisfies
85 * the coincidence constraints in the sense that the corresponding
86 * dependence distances are zero.
88 * If the schedule_treat_coalescing option is set, then
89 * "sizes" contains the sizes of the (compressed) instance set
90 * in each direction. If there is no fixed size in a given direction,
91 * then the corresponding size value is set to infinity.
92 * If the schedule_treat_coalescing option or the schedule_max_coefficient
93 * option is set, then "max" contains the maximal values for
94 * schedule coefficients of the (compressed) variables. If no bound
95 * needs to be imposed on a particular variable, then the corresponding
98 struct isl_sched_node
{
102 isl_multi_aff
*compress
;
103 isl_multi_aff
*decompress
;
118 isl_multi_val
*sizes
;
122 static int node_has_tuples(const void *entry
, const void *val
)
124 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
125 isl_space
*space
= (isl_space
*) val
;
127 return isl_space_has_equal_tuples(node
->space
, space
);
130 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
132 return node
->scc
== scc
;
135 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
137 return node
->scc
<= scc
;
140 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
142 return node
->scc
>= scc
;
145 /* An edge in the dependence graph. An edge may be used to
146 * ensure validity of the generated schedule, to minimize the dependence
149 * map is the dependence relation, with i -> j in the map if j depends on i
150 * tagged_condition and tagged_validity contain the union of all tagged
151 * condition or conditional validity dependence relations that
152 * specialize the dependence relation "map"; that is,
153 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
154 * or "tagged_validity", then i -> j is an element of "map".
155 * If these fields are NULL, then they represent the empty relation.
156 * src is the source node
157 * dst is the sink node
159 * types is a bit vector containing the types of this edge.
160 * validity is set if the edge is used to ensure correctness
161 * coincidence is used to enforce zero dependence distances
162 * proximity is set if the edge is used to minimize dependence distances
163 * condition is set if the edge represents a condition
164 * for a conditional validity schedule constraint
165 * local can only be set for condition edges and indicates that
166 * the dependence distance over the edge should be zero
167 * conditional_validity is set if the edge is used to conditionally
170 * For validity edges, start and end mark the sequence of inequality
171 * constraints in the LP problem that encode the validity constraint
172 * corresponding to this edge.
174 * During clustering, an edge may be marked "no_merge" if it should
175 * not be used to merge clusters.
176 * The weight is also only used during clustering and it is
177 * an indication of how many schedule dimensions on either side
178 * of the schedule constraints can be aligned.
179 * If the weight is negative, then this means that this edge was postponed
180 * by has_bounded_distances or any_no_merge. The original weight can
181 * be retrieved by adding 1 + graph->max_weight, with "graph"
182 * the graph containing this edge.
184 struct isl_sched_edge
{
186 isl_union_map
*tagged_condition
;
187 isl_union_map
*tagged_validity
;
189 struct isl_sched_node
*src
;
190 struct isl_sched_node
*dst
;
201 /* Is "edge" marked as being of type "type"?
203 static int is_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
205 return ISL_FL_ISSET(edge
->types
, 1 << type
);
208 /* Mark "edge" as being of type "type".
210 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
212 ISL_FL_SET(edge
->types
, 1 << type
);
215 /* No longer mark "edge" as being of type "type"?
217 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
219 ISL_FL_CLR(edge
->types
, 1 << type
);
222 /* Is "edge" marked as a validity edge?
224 static int is_validity(struct isl_sched_edge
*edge
)
226 return is_type(edge
, isl_edge_validity
);
229 /* Mark "edge" as a validity edge.
231 static void set_validity(struct isl_sched_edge
*edge
)
233 set_type(edge
, isl_edge_validity
);
236 /* Is "edge" marked as a proximity edge?
238 static int is_proximity(struct isl_sched_edge
*edge
)
240 return is_type(edge
, isl_edge_proximity
);
243 /* Is "edge" marked as a local edge?
245 static int is_local(struct isl_sched_edge
*edge
)
247 return is_type(edge
, isl_edge_local
);
250 /* Mark "edge" as a local edge.
252 static void set_local(struct isl_sched_edge
*edge
)
254 set_type(edge
, isl_edge_local
);
257 /* No longer mark "edge" as a local edge.
259 static void clear_local(struct isl_sched_edge
*edge
)
261 clear_type(edge
, isl_edge_local
);
264 /* Is "edge" marked as a coincidence edge?
266 static int is_coincidence(struct isl_sched_edge
*edge
)
268 return is_type(edge
, isl_edge_coincidence
);
271 /* Is "edge" marked as a condition edge?
273 static int is_condition(struct isl_sched_edge
*edge
)
275 return is_type(edge
, isl_edge_condition
);
278 /* Is "edge" marked as a conditional validity edge?
280 static int is_conditional_validity(struct isl_sched_edge
*edge
)
282 return is_type(edge
, isl_edge_conditional_validity
);
285 /* Internal information about the dependence graph used during
286 * the construction of the schedule.
288 * intra_hmap is a cache, mapping dependence relations to their dual,
289 * for dependences from a node to itself
290 * inter_hmap is a cache, mapping dependence relations to their dual,
291 * for dependences between distinct nodes
292 * if compression is involved then the key for these maps
293 * is the original, uncompressed dependence relation, while
294 * the value is the dual of the compressed dependence relation.
296 * n is the number of nodes
297 * node is the list of nodes
298 * maxvar is the maximal number of variables over all nodes
299 * max_row is the allocated number of rows in the schedule
300 * n_row is the current (maximal) number of linearly independent
301 * rows in the node schedules
302 * n_total_row is the current number of rows in the node schedules
303 * band_start is the starting row in the node schedules of the current band
304 * root is set if this graph is the original dependence graph,
305 * without any splitting
307 * sorted contains a list of node indices sorted according to the
308 * SCC to which a node belongs
310 * n_edge is the number of edges
311 * edge is the list of edges
312 * max_edge contains the maximal number of edges of each type;
313 * in particular, it contains the number of edges in the inital graph.
314 * edge_table contains pointers into the edge array, hashed on the source
315 * and sink spaces; there is one such table for each type;
316 * a given edge may be referenced from more than one table
317 * if the corresponding relation appears in more than one of the
318 * sets of dependences; however, for each type there is only
319 * a single edge between a given pair of source and sink space
320 * in the entire graph
322 * node_table contains pointers into the node array, hashed on the space tuples
324 * region contains a list of variable sequences that should be non-trivial
326 * lp contains the (I)LP problem used to obtain new schedule rows
328 * src_scc and dst_scc are the source and sink SCCs of an edge with
329 * conflicting constraints
331 * scc represents the number of components
332 * weak is set if the components are weakly connected
334 * max_weight is used during clustering and represents the maximal
335 * weight of the relevant proximity edges.
337 struct isl_sched_graph
{
338 isl_map_to_basic_set
*intra_hmap
;
339 isl_map_to_basic_set
*inter_hmap
;
341 struct isl_sched_node
*node
;
354 struct isl_sched_edge
*edge
;
356 int max_edge
[isl_edge_last
+ 1];
357 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
359 struct isl_hash_table
*node_table
;
360 struct isl_trivial_region
*region
;
373 /* Initialize node_table based on the list of nodes.
375 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
379 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
380 if (!graph
->node_table
)
383 for (i
= 0; i
< graph
->n
; ++i
) {
384 struct isl_hash_table_entry
*entry
;
387 hash
= isl_space_get_tuple_hash(graph
->node
[i
].space
);
388 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
390 graph
->node
[i
].space
, 1);
393 entry
->data
= &graph
->node
[i
];
399 /* Return a pointer to the node that lives within the given space,
400 * or NULL if there is no such node.
402 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
403 struct isl_sched_graph
*graph
, __isl_keep isl_space
*space
)
405 struct isl_hash_table_entry
*entry
;
408 hash
= isl_space_get_tuple_hash(space
);
409 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
410 &node_has_tuples
, space
, 0);
412 return entry
? entry
->data
: NULL
;
415 static int edge_has_src_and_dst(const void *entry
, const void *val
)
417 const struct isl_sched_edge
*edge
= entry
;
418 const struct isl_sched_edge
*temp
= val
;
420 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
423 /* Add the given edge to graph->edge_table[type].
425 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
426 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
427 struct isl_sched_edge
*edge
)
429 struct isl_hash_table_entry
*entry
;
432 hash
= isl_hash_init();
433 hash
= isl_hash_builtin(hash
, edge
->src
);
434 hash
= isl_hash_builtin(hash
, edge
->dst
);
435 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
436 &edge_has_src_and_dst
, edge
, 1);
438 return isl_stat_error
;
444 /* Allocate the edge_tables based on the maximal number of edges of
447 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
451 for (i
= 0; i
<= isl_edge_last
; ++i
) {
452 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
454 if (!graph
->edge_table
[i
])
461 /* If graph->edge_table[type] contains an edge from the given source
462 * to the given destination, then return the hash table entry of this edge.
463 * Otherwise, return NULL.
465 static struct isl_hash_table_entry
*graph_find_edge_entry(
466 struct isl_sched_graph
*graph
,
467 enum isl_edge_type type
,
468 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
470 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
472 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
474 hash
= isl_hash_init();
475 hash
= isl_hash_builtin(hash
, temp
.src
);
476 hash
= isl_hash_builtin(hash
, temp
.dst
);
477 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
478 &edge_has_src_and_dst
, &temp
, 0);
482 /* If graph->edge_table[type] contains an edge from the given source
483 * to the given destination, then return this edge.
484 * Otherwise, return NULL.
486 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
487 enum isl_edge_type type
,
488 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
490 struct isl_hash_table_entry
*entry
;
492 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
499 /* Check whether the dependence graph has an edge of the given type
500 * between the given two nodes.
502 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
503 enum isl_edge_type type
,
504 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
506 struct isl_sched_edge
*edge
;
509 edge
= graph_find_edge(graph
, type
, src
, dst
);
513 empty
= isl_map_plain_is_empty(edge
->map
);
515 return isl_bool_error
;
520 /* Look for any edge with the same src, dst and map fields as "model".
522 * Return the matching edge if one can be found.
523 * Return "model" if no matching edge is found.
524 * Return NULL on error.
526 static struct isl_sched_edge
*graph_find_matching_edge(
527 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
529 enum isl_edge_type i
;
530 struct isl_sched_edge
*edge
;
532 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
535 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
538 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
548 /* Remove the given edge from all the edge_tables that refer to it.
550 static void graph_remove_edge(struct isl_sched_graph
*graph
,
551 struct isl_sched_edge
*edge
)
553 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
554 enum isl_edge_type i
;
556 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
557 struct isl_hash_table_entry
*entry
;
559 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
562 if (entry
->data
!= edge
)
564 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
568 /* Check whether the dependence graph has any edge
569 * between the given two nodes.
571 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
572 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
574 enum isl_edge_type i
;
577 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
578 r
= graph_has_edge(graph
, i
, src
, dst
);
586 /* Check whether the dependence graph has a validity edge
587 * between the given two nodes.
589 * Conditional validity edges are essentially validity edges that
590 * can be ignored if the corresponding condition edges are iteration private.
591 * Here, we are only checking for the presence of validity
592 * edges, so we need to consider the conditional validity edges too.
593 * In particular, this function is used during the detection
594 * of strongly connected components and we cannot ignore
595 * conditional validity edges during this detection.
597 static isl_bool
graph_has_validity_edge(struct isl_sched_graph
*graph
,
598 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
602 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
606 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
609 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
610 int n_node
, int n_edge
)
615 graph
->n_edge
= n_edge
;
616 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
617 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
618 graph
->region
= isl_alloc_array(ctx
,
619 struct isl_trivial_region
, graph
->n
);
620 graph
->edge
= isl_calloc_array(ctx
,
621 struct isl_sched_edge
, graph
->n_edge
);
623 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
624 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
626 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
630 for(i
= 0; i
< graph
->n
; ++i
)
631 graph
->sorted
[i
] = i
;
636 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
640 isl_map_to_basic_set_free(graph
->intra_hmap
);
641 isl_map_to_basic_set_free(graph
->inter_hmap
);
644 for (i
= 0; i
< graph
->n
; ++i
) {
645 isl_space_free(graph
->node
[i
].space
);
646 isl_set_free(graph
->node
[i
].hull
);
647 isl_multi_aff_free(graph
->node
[i
].compress
);
648 isl_multi_aff_free(graph
->node
[i
].decompress
);
649 isl_mat_free(graph
->node
[i
].sched
);
650 isl_map_free(graph
->node
[i
].sched_map
);
651 isl_mat_free(graph
->node
[i
].indep
);
652 isl_mat_free(graph
->node
[i
].vmap
);
654 free(graph
->node
[i
].coincident
);
655 isl_multi_val_free(graph
->node
[i
].sizes
);
656 isl_vec_free(graph
->node
[i
].max
);
661 for (i
= 0; i
< graph
->n_edge
; ++i
) {
662 isl_map_free(graph
->edge
[i
].map
);
663 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
664 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
668 for (i
= 0; i
<= isl_edge_last
; ++i
)
669 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
670 isl_hash_table_free(ctx
, graph
->node_table
);
671 isl_basic_set_free(graph
->lp
);
674 /* For each "set" on which this function is called, increment
675 * graph->n by one and update graph->maxvar.
677 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
679 struct isl_sched_graph
*graph
= user
;
680 int nvar
= isl_set_dim(set
, isl_dim_set
);
683 if (nvar
> graph
->maxvar
)
684 graph
->maxvar
= nvar
;
691 /* Compute the number of rows that should be allocated for the schedule.
692 * In particular, we need one row for each variable or one row
693 * for each basic map in the dependences.
694 * Note that it is practically impossible to exhaust both
695 * the number of dependences and the number of variables.
697 static isl_stat
compute_max_row(struct isl_sched_graph
*graph
,
698 __isl_keep isl_schedule_constraints
*sc
)
702 isl_union_set
*domain
;
706 domain
= isl_schedule_constraints_get_domain(sc
);
707 r
= isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
);
708 isl_union_set_free(domain
);
710 return isl_stat_error
;
711 n_edge
= isl_schedule_constraints_n_basic_map(sc
);
713 return isl_stat_error
;
714 graph
->max_row
= n_edge
+ graph
->maxvar
;
719 /* Does "bset" have any defining equalities for its set variables?
721 static isl_bool
has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
726 return isl_bool_error
;
728 n
= isl_basic_set_dim(bset
, isl_dim_set
);
729 for (i
= 0; i
< n
; ++i
) {
732 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
738 return isl_bool_false
;
741 /* Set the entries of node->max to the value of the schedule_max_coefficient
744 static isl_stat
set_max_coefficient(isl_ctx
*ctx
, struct isl_sched_node
*node
)
748 max
= isl_options_get_schedule_max_coefficient(ctx
);
752 node
->max
= isl_vec_alloc(ctx
, node
->nvar
);
753 node
->max
= isl_vec_set_si(node
->max
, max
);
755 return isl_stat_error
;
760 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
761 * option (if set) and half of the minimum of the sizes in the other
762 * dimensions. Round up when computing the half such that
763 * if the minimum of the sizes is one, half of the size is taken to be one
765 * If the global minimum is unbounded (i.e., if both
766 * the schedule_max_coefficient is not set and the sizes in the other
767 * dimensions are unbounded), then store a negative value.
768 * If the schedule coefficient is close to the size of the instance set
769 * in another dimension, then the schedule may represent a loop
770 * coalescing transformation (especially if the coefficient
771 * in that other dimension is one). Forcing the coefficient to be
772 * smaller than or equal to half the minimal size should avoid this
775 static isl_stat
compute_max_coefficient(isl_ctx
*ctx
,
776 struct isl_sched_node
*node
)
782 max
= isl_options_get_schedule_max_coefficient(ctx
);
783 v
= isl_vec_alloc(ctx
, node
->nvar
);
785 return isl_stat_error
;
787 for (i
= 0; i
< node
->nvar
; ++i
) {
788 isl_int_set_si(v
->el
[i
], max
);
789 isl_int_mul_si(v
->el
[i
], v
->el
[i
], 2);
792 for (i
= 0; i
< node
->nvar
; ++i
) {
795 size
= isl_multi_val_get_val(node
->sizes
, i
);
798 if (!isl_val_is_int(size
)) {
802 for (j
= 0; j
< node
->nvar
; ++j
) {
805 if (isl_int_is_neg(v
->el
[j
]) ||
806 isl_int_gt(v
->el
[j
], size
->n
))
807 isl_int_set(v
->el
[j
], size
->n
);
812 for (i
= 0; i
< node
->nvar
; ++i
)
813 isl_int_cdiv_q_ui(v
->el
[i
], v
->el
[i
], 2);
819 return isl_stat_error
;
822 /* Compute and return the size of "set" in dimension "dim".
823 * The size is taken to be the difference in values for that variable
824 * for fixed values of the other variables.
825 * In particular, the variable is first isolated from the other variables
826 * in the range of a map
828 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
830 * and then duplicated
832 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
834 * The shared variables are then projected out and the maximal value
835 * of i_dim' - i_dim is computed.
837 static __isl_give isl_val
*compute_size(__isl_take isl_set
*set
, int dim
)
844 map
= isl_set_project_onto_map(set
, isl_dim_set
, dim
, 1);
845 map
= isl_map_project_out(map
, isl_dim_in
, dim
, 1);
846 map
= isl_map_range_product(map
, isl_map_copy(map
));
847 map
= isl_set_unwrap(isl_map_range(map
));
848 set
= isl_map_deltas(map
);
849 ls
= isl_local_space_from_space(isl_set_get_space(set
));
850 obj
= isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
851 v
= isl_set_max_val(set
, obj
);
858 /* Compute the size of the instance set "set" of "node", after compression,
859 * as well as bounds on the corresponding coefficients, if needed.
861 * The sizes are needed when the schedule_treat_coalescing option is set.
862 * The bounds are needed when the schedule_treat_coalescing option or
863 * the schedule_max_coefficient option is set.
865 * If the schedule_treat_coalescing option is not set, then at most
866 * the bounds need to be set and this is done in set_max_coefficient.
867 * Otherwise, compress the domain if needed, compute the size
868 * in each direction and store the results in node->size.
869 * Finally, set the bounds on the coefficients based on the sizes
870 * and the schedule_max_coefficient option in compute_max_coefficient.
872 static isl_stat
compute_sizes_and_max(isl_ctx
*ctx
, struct isl_sched_node
*node
,
873 __isl_take isl_set
*set
)
878 if (!isl_options_get_schedule_treat_coalescing(ctx
)) {
880 return set_max_coefficient(ctx
, node
);
883 if (node
->compressed
)
884 set
= isl_set_preimage_multi_aff(set
,
885 isl_multi_aff_copy(node
->decompress
));
886 mv
= isl_multi_val_zero(isl_set_get_space(set
));
887 n
= isl_set_dim(set
, isl_dim_set
);
888 for (j
= 0; j
< n
; ++j
) {
891 v
= compute_size(isl_set_copy(set
), j
);
892 mv
= isl_multi_val_set_val(mv
, j
, v
);
897 return isl_stat_error
;
898 return compute_max_coefficient(ctx
, node
);
901 /* Add a new node to the graph representing the given instance set.
902 * "nvar" is the (possibly compressed) number of variables and
903 * may be smaller than then number of set variables in "set"
904 * if "compressed" is set.
905 * If "compressed" is set, then "hull" represents the constraints
906 * that were used to derive the compression, while "compress" and
907 * "decompress" map the original space to the compressed space and
909 * If "compressed" is not set, then "hull", "compress" and "decompress"
912 * Compute the size of the instance set and bounds on the coefficients,
915 static isl_stat
add_node(struct isl_sched_graph
*graph
,
916 __isl_take isl_set
*set
, int nvar
, int compressed
,
917 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
918 __isl_take isl_multi_aff
*decompress
)
925 struct isl_sched_node
*node
;
928 return isl_stat_error
;
930 ctx
= isl_set_get_ctx(set
);
931 nparam
= isl_set_dim(set
, isl_dim_param
);
932 if (!ctx
->opt
->schedule_parametric
)
934 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
935 node
= &graph
->node
[graph
->n
];
937 space
= isl_set_get_space(set
);
940 node
->nparam
= nparam
;
942 node
->sched_map
= NULL
;
943 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
944 node
->coincident
= coincident
;
945 node
->compressed
= compressed
;
947 node
->compress
= compress
;
948 node
->decompress
= decompress
;
949 if (compute_sizes_and_max(ctx
, node
, set
) < 0)
950 return isl_stat_error
;
952 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
953 return isl_stat_error
;
954 if (compressed
&& (!hull
|| !compress
|| !decompress
))
955 return isl_stat_error
;
960 /* Construct an identifier for node "node", which will represent "set".
961 * The name of the identifier is either "compressed" or
962 * "compressed_<name>", with <name> the name of the space of "set".
963 * The user pointer of the identifier points to "node".
965 static __isl_give isl_id
*construct_compressed_id(__isl_keep isl_set
*set
,
966 struct isl_sched_node
*node
)
975 has_name
= isl_set_has_tuple_name(set
);
979 ctx
= isl_set_get_ctx(set
);
981 return isl_id_alloc(ctx
, "compressed", node
);
983 p
= isl_printer_to_str(ctx
);
984 name
= isl_set_get_tuple_name(set
);
985 p
= isl_printer_print_str(p
, "compressed_");
986 p
= isl_printer_print_str(p
, name
);
987 id_name
= isl_printer_get_str(p
);
990 id
= isl_id_alloc(ctx
, id_name
, node
);
996 /* Add a new node to the graph representing the given set.
998 * If any of the set variables is defined by an equality, then
999 * we perform variable compression such that we can perform
1000 * the scheduling on the compressed domain.
1001 * In this case, an identifier is used that references the new node
1002 * such that each compressed space is unique and
1003 * such that the node can be recovered from the compressed space.
1005 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1008 isl_bool has_equality
;
1010 isl_basic_set
*hull
;
1013 isl_multi_aff
*compress
, *decompress
;
1014 struct isl_sched_graph
*graph
= user
;
1016 hull
= isl_set_affine_hull(isl_set_copy(set
));
1017 hull
= isl_basic_set_remove_divs(hull
);
1018 nvar
= isl_set_dim(set
, isl_dim_set
);
1019 has_equality
= has_any_defining_equality(hull
);
1021 if (has_equality
< 0)
1023 if (!has_equality
) {
1024 isl_basic_set_free(hull
);
1025 return add_node(graph
, set
, nvar
, 0, NULL
, NULL
, NULL
);
1028 id
= construct_compressed_id(set
, &graph
->node
[graph
->n
]);
1029 morph
= isl_basic_set_variable_compression_with_id(hull
,
1032 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1033 compress
= isl_morph_get_var_multi_aff(morph
);
1034 morph
= isl_morph_inverse(morph
);
1035 decompress
= isl_morph_get_var_multi_aff(morph
);
1036 isl_morph_free(morph
);
1038 hull_set
= isl_set_from_basic_set(hull
);
1039 return add_node(graph
, set
, nvar
, 1, hull_set
, compress
, decompress
);
1041 isl_basic_set_free(hull
);
1043 return isl_stat_error
;
1046 struct isl_extract_edge_data
{
1047 enum isl_edge_type type
;
1048 struct isl_sched_graph
*graph
;
1051 /* Merge edge2 into edge1, freeing the contents of edge2.
1052 * Return 0 on success and -1 on failure.
1054 * edge1 and edge2 are assumed to have the same value for the map field.
1056 static int merge_edge(struct isl_sched_edge
*edge1
,
1057 struct isl_sched_edge
*edge2
)
1059 edge1
->types
|= edge2
->types
;
1060 isl_map_free(edge2
->map
);
1062 if (is_condition(edge2
)) {
1063 if (!edge1
->tagged_condition
)
1064 edge1
->tagged_condition
= edge2
->tagged_condition
;
1066 edge1
->tagged_condition
=
1067 isl_union_map_union(edge1
->tagged_condition
,
1068 edge2
->tagged_condition
);
1071 if (is_conditional_validity(edge2
)) {
1072 if (!edge1
->tagged_validity
)
1073 edge1
->tagged_validity
= edge2
->tagged_validity
;
1075 edge1
->tagged_validity
=
1076 isl_union_map_union(edge1
->tagged_validity
,
1077 edge2
->tagged_validity
);
1080 if (is_condition(edge2
) && !edge1
->tagged_condition
)
1082 if (is_conditional_validity(edge2
) && !edge1
->tagged_validity
)
1088 /* Insert dummy tags in domain and range of "map".
1090 * In particular, if "map" is of the form
1096 * [A -> dummy_tag] -> [B -> dummy_tag]
1098 * where the dummy_tags are identical and equal to any dummy tags
1099 * introduced by any other call to this function.
1101 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1107 isl_set
*domain
, *range
;
1109 ctx
= isl_map_get_ctx(map
);
1111 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1112 space
= isl_space_params(isl_map_get_space(map
));
1113 space
= isl_space_set_from_params(space
);
1114 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1115 space
= isl_space_map_from_set(space
);
1117 domain
= isl_map_wrap(map
);
1118 range
= isl_map_wrap(isl_map_universe(space
));
1119 map
= isl_map_from_domain_and_range(domain
, range
);
1120 map
= isl_map_zip(map
);
1125 /* Given that at least one of "src" or "dst" is compressed, return
1126 * a map between the spaces of these nodes restricted to the affine
1127 * hull that was used in the compression.
1129 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1130 struct isl_sched_node
*dst
)
1134 if (src
->compressed
)
1135 dom
= isl_set_copy(src
->hull
);
1137 dom
= isl_set_universe(isl_space_copy(src
->space
));
1138 if (dst
->compressed
)
1139 ran
= isl_set_copy(dst
->hull
);
1141 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1143 return isl_map_from_domain_and_range(dom
, ran
);
1146 /* Intersect the domains of the nested relations in domain and range
1147 * of "tagged" with "map".
1149 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1150 __isl_keep isl_map
*map
)
1154 tagged
= isl_map_zip(tagged
);
1155 set
= isl_map_wrap(isl_map_copy(map
));
1156 tagged
= isl_map_intersect_domain(tagged
, set
);
1157 tagged
= isl_map_zip(tagged
);
1161 /* Return a pointer to the node that lives in the domain space of "map"
1162 * or NULL if there is no such node.
1164 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1165 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1167 struct isl_sched_node
*node
;
1170 space
= isl_space_domain(isl_map_get_space(map
));
1171 node
= graph_find_node(ctx
, graph
, space
);
1172 isl_space_free(space
);
1177 /* Return a pointer to the node that lives in the range space of "map"
1178 * or NULL if there is no such node.
1180 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1181 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1183 struct isl_sched_node
*node
;
1186 space
= isl_space_range(isl_map_get_space(map
));
1187 node
= graph_find_node(ctx
, graph
, space
);
1188 isl_space_free(space
);
1193 /* Add a new edge to the graph based on the given map
1194 * and add it to data->graph->edge_table[data->type].
1195 * If a dependence relation of a given type happens to be identical
1196 * to one of the dependence relations of a type that was added before,
1197 * then we don't create a new edge, but instead mark the original edge
1198 * as also representing a dependence of the current type.
1200 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1201 * may be specified as "tagged" dependence relations. That is, "map"
1202 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1203 * the dependence on iterations and a and b are tags.
1204 * edge->map is set to the relation containing the elements i -> j,
1205 * while edge->tagged_condition and edge->tagged_validity contain
1206 * the union of all the "map" relations
1207 * for which extract_edge is called that result in the same edge->map.
1209 * If the source or the destination node is compressed, then
1210 * intersect both "map" and "tagged" with the constraints that
1211 * were used to construct the compression.
1212 * This ensures that there are no schedule constraints defined
1213 * outside of these domains, while the scheduler no longer has
1214 * any control over those outside parts.
1216 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1218 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1219 struct isl_extract_edge_data
*data
= user
;
1220 struct isl_sched_graph
*graph
= data
->graph
;
1221 struct isl_sched_node
*src
, *dst
;
1222 struct isl_sched_edge
*edge
;
1223 isl_map
*tagged
= NULL
;
1225 if (data
->type
== isl_edge_condition
||
1226 data
->type
== isl_edge_conditional_validity
) {
1227 if (isl_map_can_zip(map
)) {
1228 tagged
= isl_map_copy(map
);
1229 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1231 tagged
= insert_dummy_tags(isl_map_copy(map
));
1235 src
= find_domain_node(ctx
, graph
, map
);
1236 dst
= find_range_node(ctx
, graph
, map
);
1240 isl_map_free(tagged
);
1244 if (src
->compressed
|| dst
->compressed
) {
1246 hull
= extract_hull(src
, dst
);
1248 tagged
= map_intersect_domains(tagged
, hull
);
1249 map
= isl_map_intersect(map
, hull
);
1252 graph
->edge
[graph
->n_edge
].src
= src
;
1253 graph
->edge
[graph
->n_edge
].dst
= dst
;
1254 graph
->edge
[graph
->n_edge
].map
= map
;
1255 graph
->edge
[graph
->n_edge
].types
= 0;
1256 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1257 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1258 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1259 if (data
->type
== isl_edge_condition
)
1260 graph
->edge
[graph
->n_edge
].tagged_condition
=
1261 isl_union_map_from_map(tagged
);
1262 if (data
->type
== isl_edge_conditional_validity
)
1263 graph
->edge
[graph
->n_edge
].tagged_validity
=
1264 isl_union_map_from_map(tagged
);
1266 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1269 return isl_stat_error
;
1271 if (edge
== &graph
->edge
[graph
->n_edge
])
1272 return graph_edge_table_add(ctx
, graph
, data
->type
,
1273 &graph
->edge
[graph
->n_edge
++]);
1275 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1278 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1281 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1283 * The context is included in the domain before the nodes of
1284 * the graphs are extracted in order to be able to exploit
1285 * any possible additional equalities.
1286 * Note that this intersection is only performed locally here.
1288 static isl_stat
graph_init(struct isl_sched_graph
*graph
,
1289 __isl_keep isl_schedule_constraints
*sc
)
1292 isl_union_set
*domain
;
1294 struct isl_extract_edge_data data
;
1295 enum isl_edge_type i
;
1299 return isl_stat_error
;
1301 ctx
= isl_schedule_constraints_get_ctx(sc
);
1303 domain
= isl_schedule_constraints_get_domain(sc
);
1304 graph
->n
= isl_union_set_n_set(domain
);
1305 isl_union_set_free(domain
);
1307 if (graph_alloc(ctx
, graph
, graph
->n
,
1308 isl_schedule_constraints_n_map(sc
)) < 0)
1309 return isl_stat_error
;
1311 if (compute_max_row(graph
, sc
) < 0)
1312 return isl_stat_error
;
1315 domain
= isl_schedule_constraints_get_domain(sc
);
1316 domain
= isl_union_set_intersect_params(domain
,
1317 isl_schedule_constraints_get_context(sc
));
1318 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1319 isl_union_set_free(domain
);
1321 return isl_stat_error
;
1322 if (graph_init_table(ctx
, graph
) < 0)
1323 return isl_stat_error
;
1324 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1325 c
= isl_schedule_constraints_get(sc
, i
);
1326 graph
->max_edge
[i
] = isl_union_map_n_map(c
);
1327 isl_union_map_free(c
);
1329 return isl_stat_error
;
1331 if (graph_init_edge_tables(ctx
, graph
) < 0)
1332 return isl_stat_error
;
1335 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1339 c
= isl_schedule_constraints_get(sc
, i
);
1340 r
= isl_union_map_foreach_map(c
, &extract_edge
, &data
);
1341 isl_union_map_free(c
);
1343 return isl_stat_error
;
1349 /* Check whether there is any dependence from node[j] to node[i]
1350 * or from node[i] to node[j].
1352 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1355 struct isl_sched_graph
*graph
= user
;
1357 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1360 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1363 /* Check whether there is a (conditional) validity dependence from node[j]
1364 * to node[i], forcing node[i] to follow node[j].
1366 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1368 struct isl_sched_graph
*graph
= user
;
1370 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1373 /* Use Tarjan's algorithm for computing the strongly connected components
1374 * in the dependence graph only considering those edges defined by "follows".
1376 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1377 isl_bool (*follows
)(int i
, int j
, void *user
))
1380 struct isl_tarjan_graph
*g
= NULL
;
1382 g
= isl_tarjan_graph_init(ctx
, graph
->n
, follows
, graph
);
1390 while (g
->order
[i
] != -1) {
1391 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1399 isl_tarjan_graph_free(g
);
1404 /* Apply Tarjan's algorithm to detect the strongly connected components
1405 * in the dependence graph.
1406 * Only consider the (conditional) validity dependences and clear "weak".
1408 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1411 return detect_ccs(ctx
, graph
, &node_follows_strong
);
1414 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1415 * in the dependence graph.
1416 * Consider all dependences and set "weak".
1418 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1421 return detect_ccs(ctx
, graph
, &node_follows_weak
);
1424 static int cmp_scc(const void *a
, const void *b
, void *data
)
1426 struct isl_sched_graph
*graph
= data
;
1430 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1433 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1435 static int sort_sccs(struct isl_sched_graph
*graph
)
1437 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1440 /* Given a dependence relation R from "node" to itself,
1441 * construct the set of coefficients of valid constraints for elements
1442 * in that dependence relation.
1443 * In particular, the result contains tuples of coefficients
1444 * c_0, c_n, c_x such that
1446 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1450 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1452 * We choose here to compute the dual of delta R.
1453 * Alternatively, we could have computed the dual of R, resulting
1454 * in a set of tuples c_0, c_n, c_x, c_y, and then
1455 * plugged in (c_0, c_n, c_x, -c_x).
1457 * If "node" has been compressed, then the dependence relation
1458 * is also compressed before the set of coefficients is computed.
1460 static __isl_give isl_basic_set
*intra_coefficients(
1461 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1462 __isl_take isl_map
*map
)
1466 isl_basic_set
*coef
;
1467 isl_maybe_isl_basic_set m
;
1469 m
= isl_map_to_basic_set_try_get(graph
->intra_hmap
, map
);
1470 if (m
.valid
< 0 || m
.valid
) {
1475 key
= isl_map_copy(map
);
1476 if (node
->compressed
) {
1477 map
= isl_map_preimage_domain_multi_aff(map
,
1478 isl_multi_aff_copy(node
->decompress
));
1479 map
= isl_map_preimage_range_multi_aff(map
,
1480 isl_multi_aff_copy(node
->decompress
));
1482 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1483 coef
= isl_set_coefficients(delta
);
1484 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1485 isl_basic_set_copy(coef
));
1490 /* Given a dependence relation R, construct the set of coefficients
1491 * of valid constraints for elements in that dependence relation.
1492 * In particular, the result contains tuples of coefficients
1493 * c_0, c_n, c_x, c_y such that
1495 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1497 * If the source or destination nodes of "edge" have been compressed,
1498 * then the dependence relation is also compressed before
1499 * the set of coefficients is computed.
1501 static __isl_give isl_basic_set
*inter_coefficients(
1502 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1503 __isl_take isl_map
*map
)
1507 isl_basic_set
*coef
;
1508 isl_maybe_isl_basic_set m
;
1510 m
= isl_map_to_basic_set_try_get(graph
->inter_hmap
, map
);
1511 if (m
.valid
< 0 || m
.valid
) {
1516 key
= isl_map_copy(map
);
1517 if (edge
->src
->compressed
)
1518 map
= isl_map_preimage_domain_multi_aff(map
,
1519 isl_multi_aff_copy(edge
->src
->decompress
));
1520 if (edge
->dst
->compressed
)
1521 map
= isl_map_preimage_range_multi_aff(map
,
1522 isl_multi_aff_copy(edge
->dst
->decompress
));
1523 set
= isl_map_wrap(isl_map_remove_divs(map
));
1524 coef
= isl_set_coefficients(set
);
1525 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1526 isl_basic_set_copy(coef
));
1531 /* Return the position of the coefficients of the variables in
1532 * the coefficients constraints "coef".
1534 * The space of "coef" is of the form
1536 * { coefficients[[cst, params] -> S] }
1538 * Return the position of S.
1540 static int coef_var_offset(__isl_keep isl_basic_set
*coef
)
1545 space
= isl_space_unwrap(isl_basic_set_get_space(coef
));
1546 offset
= isl_space_dim(space
, isl_dim_in
);
1547 isl_space_free(space
);
1552 /* Return the offset of the coefficient of the constant term of "node"
1555 * Within each node, the coefficients have the following order:
1556 * - positive and negative parts of c_i_x
1557 * - c_i_n (if parametric)
1560 static int node_cst_coef_offset(struct isl_sched_node
*node
)
1562 return node
->start
+ 2 * node
->nvar
+ node
->nparam
;
1565 /* Return the offset of the coefficients of the parameters of "node"
1568 * Within each node, the coefficients have the following order:
1569 * - positive and negative parts of c_i_x
1570 * - c_i_n (if parametric)
1573 static int node_par_coef_offset(struct isl_sched_node
*node
)
1575 return node
->start
+ 2 * node
->nvar
;
1578 /* Return the offset of the coefficients of the variables of "node"
1581 * Within each node, the coefficients have the following order:
1582 * - positive and negative parts of c_i_x
1583 * - c_i_n (if parametric)
1586 static int node_var_coef_offset(struct isl_sched_node
*node
)
1591 /* Return the position of the pair of variables encoding
1592 * coefficient "i" of "node".
1594 * The order of these variable pairs is the opposite of
1595 * that of the coefficients, with 2 variables per coefficient.
1597 static int node_var_coef_pos(struct isl_sched_node
*node
, int i
)
1599 return node_var_coef_offset(node
) + 2 * (node
->nvar
- 1 - i
);
1602 /* Construct an isl_dim_map for mapping constraints on coefficients
1603 * for "node" to the corresponding positions in graph->lp.
1604 * "offset" is the offset of the coefficients for the variables
1605 * in the input constraints.
1606 * "s" is the sign of the mapping.
1608 * The input constraints are given in terms of the coefficients (c_0, c_n, c_x).
1609 * The mapping produced by this function essentially plugs in
1610 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1611 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1612 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1613 * Furthermore, the order of these pairs is the opposite of that
1614 * of the corresponding coefficients.
1616 * The caller can extend the mapping to also map the other coefficients
1617 * (and therefore not plug in 0).
1619 static __isl_give isl_dim_map
*intra_dim_map(isl_ctx
*ctx
,
1620 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1625 isl_dim_map
*dim_map
;
1630 total
= isl_basic_set_total_dim(graph
->lp
);
1631 pos
= node_var_coef_pos(node
, 0);
1632 dim_map
= isl_dim_map_alloc(ctx
, total
);
1633 isl_dim_map_range(dim_map
, pos
, -2, offset
, 1, node
->nvar
, -s
);
1634 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
, 1, node
->nvar
, s
);
1639 /* Construct an isl_dim_map for mapping constraints on coefficients
1640 * for "src" (node i) and "dst" (node j) to the corresponding positions
1642 * "offset" is the offset of the coefficients for the variables of "src"
1643 * in the input constraints.
1644 * "s" is the sign of the mapping.
1646 * The input constraints are given in terms of the coefficients
1647 * (c_0, c_n, c_x, c_y).
1648 * The mapping produced by this function essentially plugs in
1649 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1650 * -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-) if s = 1 and
1651 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1652 * c_i_x^+ - c_i_x^-, -(c_j_x^+ - c_j_x^-)) if s = -1.
1653 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1654 * Furthermore, the order of these pairs is the opposite of that
1655 * of the corresponding coefficients.
1657 * The caller can further extend the mapping.
1659 static __isl_give isl_dim_map
*inter_dim_map(isl_ctx
*ctx
,
1660 struct isl_sched_graph
*graph
, struct isl_sched_node
*src
,
1661 struct isl_sched_node
*dst
, int offset
, int s
)
1665 isl_dim_map
*dim_map
;
1670 total
= isl_basic_set_total_dim(graph
->lp
);
1671 dim_map
= isl_dim_map_alloc(ctx
, total
);
1673 pos
= node_cst_coef_offset(dst
);
1674 isl_dim_map_range(dim_map
, pos
, 0, 0, 0, 1, s
);
1675 pos
= node_par_coef_offset(dst
);
1676 isl_dim_map_range(dim_map
, pos
, 1, 1, 1, dst
->nparam
, s
);
1677 pos
= node_var_coef_pos(dst
, 0);
1678 isl_dim_map_range(dim_map
, pos
, -2, offset
+ src
->nvar
, 1,
1680 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
+ src
->nvar
, 1,
1683 pos
= node_cst_coef_offset(src
);
1684 isl_dim_map_range(dim_map
, pos
, 0, 0, 0, 1, -s
);
1685 pos
= node_par_coef_offset(src
);
1686 isl_dim_map_range(dim_map
, pos
, 1, 1, 1, src
->nparam
, -s
);
1687 pos
= node_var_coef_pos(src
, 0);
1688 isl_dim_map_range(dim_map
, pos
, -2, offset
, 1, src
->nvar
, s
);
1689 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
, 1, src
->nvar
, -s
);
1694 /* Add the constraints from "src" to "dst" using "dim_map",
1695 * after making sure there is enough room in "dst" for the extra constraints.
1697 static __isl_give isl_basic_set
*add_constraints_dim_map(
1698 __isl_take isl_basic_set
*dst
, __isl_take isl_basic_set
*src
,
1699 __isl_take isl_dim_map
*dim_map
)
1703 n_eq
= isl_basic_set_n_equality(src
);
1704 n_ineq
= isl_basic_set_n_inequality(src
);
1705 dst
= isl_basic_set_extend_constraints(dst
, n_eq
, n_ineq
);
1706 dst
= isl_basic_set_add_constraints_dim_map(dst
, src
, dim_map
);
1710 /* Add constraints to graph->lp that force validity for the given
1711 * dependence from a node i to itself.
1712 * That is, add constraints that enforce
1714 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1715 * = c_i_x (y - x) >= 0
1717 * for each (x,y) in R.
1718 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1719 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1720 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1721 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1723 static isl_stat
add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1724 struct isl_sched_edge
*edge
)
1727 isl_map
*map
= isl_map_copy(edge
->map
);
1728 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1729 isl_dim_map
*dim_map
;
1730 isl_basic_set
*coef
;
1731 struct isl_sched_node
*node
= edge
->src
;
1733 coef
= intra_coefficients(graph
, node
, map
);
1735 offset
= coef_var_offset(coef
);
1738 return isl_stat_error
;
1740 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
1741 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1746 /* Add constraints to graph->lp that force validity for the given
1747 * dependence from node i to node j.
1748 * That is, add constraints that enforce
1750 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1752 * for each (x,y) in R.
1753 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1754 * of valid constraints for R and then plug in
1755 * (c_j_0 - c_i_0, c_j_n - c_i_n, -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-),
1756 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1757 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1759 static isl_stat
add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1760 struct isl_sched_edge
*edge
)
1765 isl_dim_map
*dim_map
;
1766 isl_basic_set
*coef
;
1767 struct isl_sched_node
*src
= edge
->src
;
1768 struct isl_sched_node
*dst
= edge
->dst
;
1771 return isl_stat_error
;
1773 map
= isl_map_copy(edge
->map
);
1774 ctx
= isl_map_get_ctx(map
);
1775 coef
= inter_coefficients(graph
, edge
, map
);
1777 offset
= coef_var_offset(coef
);
1780 return isl_stat_error
;
1782 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
1784 edge
->start
= graph
->lp
->n_ineq
;
1785 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1787 return isl_stat_error
;
1788 edge
->end
= graph
->lp
->n_ineq
;
1793 /* Add constraints to graph->lp that bound the dependence distance for the given
1794 * dependence from a node i to itself.
1795 * If s = 1, we add the constraint
1797 * c_i_x (y - x) <= m_0 + m_n n
1801 * -c_i_x (y - x) + m_0 + m_n n >= 0
1803 * for each (x,y) in R.
1804 * If s = -1, we add the constraint
1806 * -c_i_x (y - x) <= m_0 + m_n n
1810 * c_i_x (y - x) + m_0 + m_n n >= 0
1812 * for each (x,y) in R.
1813 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1814 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1815 * with each coefficient (except m_0) represented as a pair of non-negative
1819 * If "local" is set, then we add constraints
1821 * c_i_x (y - x) <= 0
1825 * -c_i_x (y - x) <= 0
1827 * instead, forcing the dependence distance to be (less than or) equal to 0.
1828 * That is, we plug in (0, 0, -s * c_i_x),
1829 * Note that dependences marked local are treated as validity constraints
1830 * by add_all_validity_constraints and therefore also have
1831 * their distances bounded by 0 from below.
1833 static isl_stat
add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1834 struct isl_sched_edge
*edge
, int s
, int local
)
1838 isl_map
*map
= isl_map_copy(edge
->map
);
1839 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1840 isl_dim_map
*dim_map
;
1841 isl_basic_set
*coef
;
1842 struct isl_sched_node
*node
= edge
->src
;
1844 coef
= intra_coefficients(graph
, node
, map
);
1846 offset
= coef_var_offset(coef
);
1849 return isl_stat_error
;
1851 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1852 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, -s
);
1855 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1856 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1857 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1859 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1864 /* Add constraints to graph->lp that bound the dependence distance for the given
1865 * dependence from node i to node j.
1866 * If s = 1, we add the constraint
1868 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1873 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1876 * for each (x,y) in R.
1877 * If s = -1, we add the constraint
1879 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1884 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1887 * for each (x,y) in R.
1888 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1889 * of valid constraints for R and then plug in
1890 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1891 * s*c_i_x, -s*c_j_x)
1892 * with each coefficient (except m_0, c_*_0 and c_*_n)
1893 * represented as a pair of non-negative coefficients.
1896 * If "local" is set (and s = 1), then we add constraints
1898 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1902 * -((c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x)) >= 0
1904 * instead, forcing the dependence distance to be (less than or) equal to 0.
1905 * That is, we plug in
1906 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, s*c_i_x, -s*c_j_x).
1907 * Note that dependences marked local are treated as validity constraints
1908 * by add_all_validity_constraints and therefore also have
1909 * their distances bounded by 0 from below.
1911 static isl_stat
add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1912 struct isl_sched_edge
*edge
, int s
, int local
)
1916 isl_map
*map
= isl_map_copy(edge
->map
);
1917 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1918 isl_dim_map
*dim_map
;
1919 isl_basic_set
*coef
;
1920 struct isl_sched_node
*src
= edge
->src
;
1921 struct isl_sched_node
*dst
= edge
->dst
;
1923 coef
= inter_coefficients(graph
, edge
, map
);
1925 offset
= coef_var_offset(coef
);
1928 return isl_stat_error
;
1930 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1931 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, -s
);
1934 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1935 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1936 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1939 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1944 /* Should the distance over "edge" be forced to zero?
1945 * That is, is it marked as a local edge?
1946 * If "use_coincidence" is set, then coincidence edges are treated
1949 static int force_zero(struct isl_sched_edge
*edge
, int use_coincidence
)
1951 return is_local(edge
) || (use_coincidence
&& is_coincidence(edge
));
1954 /* Add all validity constraints to graph->lp.
1956 * An edge that is forced to be local needs to have its dependence
1957 * distances equal to zero. We take care of bounding them by 0 from below
1958 * here. add_all_proximity_constraints takes care of bounding them by 0
1961 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1962 * Otherwise, we ignore them.
1964 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1965 int use_coincidence
)
1969 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1970 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1973 zero
= force_zero(edge
, use_coincidence
);
1974 if (!is_validity(edge
) && !zero
)
1976 if (edge
->src
!= edge
->dst
)
1978 if (add_intra_validity_constraints(graph
, edge
) < 0)
1982 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1983 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1986 zero
= force_zero(edge
, use_coincidence
);
1987 if (!is_validity(edge
) && !zero
)
1989 if (edge
->src
== edge
->dst
)
1991 if (add_inter_validity_constraints(graph
, edge
) < 0)
1998 /* Add constraints to graph->lp that bound the dependence distance
1999 * for all dependence relations.
2000 * If a given proximity dependence is identical to a validity
2001 * dependence, then the dependence distance is already bounded
2002 * from below (by zero), so we only need to bound the distance
2003 * from above. (This includes the case of "local" dependences
2004 * which are treated as validity dependence by add_all_validity_constraints.)
2005 * Otherwise, we need to bound the distance both from above and from below.
2007 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2008 * Otherwise, we ignore them.
2010 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
2011 int use_coincidence
)
2015 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2016 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2019 zero
= force_zero(edge
, use_coincidence
);
2020 if (!is_proximity(edge
) && !zero
)
2022 if (edge
->src
== edge
->dst
&&
2023 add_intra_proximity_constraints(graph
, edge
, 1, zero
) < 0)
2025 if (edge
->src
!= edge
->dst
&&
2026 add_inter_proximity_constraints(graph
, edge
, 1, zero
) < 0)
2028 if (is_validity(edge
) || zero
)
2030 if (edge
->src
== edge
->dst
&&
2031 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2033 if (edge
->src
!= edge
->dst
&&
2034 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2041 /* Normalize the rows of "indep" such that all rows are lexicographically
2042 * positive and such that each row contains as many final zeros as possible,
2043 * given the choice for the previous rows.
2044 * Do this by performing elementary row operations.
2046 static __isl_give isl_mat
*normalize_independent(__isl_take isl_mat
*indep
)
2048 indep
= isl_mat_reverse_gauss(indep
);
2049 indep
= isl_mat_lexnonneg_rows(indep
);
2053 /* Compute a basis for the rows in the linear part of the schedule
2054 * and extend this basis to a full basis. The remaining rows
2055 * can then be used to force linear independence from the rows
2058 * In particular, given the schedule rows S, we compute
2063 * with H the Hermite normal form of S. That is, all but the
2064 * first rank columns of H are zero and so each row in S is
2065 * a linear combination of the first rank rows of Q.
2066 * The matrix Q can be used as a variable transformation
2067 * that isolates the directions of S in the first rank rows.
2068 * Transposing S U = H yields
2072 * with all but the first rank rows of H^T zero.
2073 * The last rows of U^T are therefore linear combinations
2074 * of schedule coefficients that are all zero on schedule
2075 * coefficients that are linearly dependent on the rows of S.
2076 * At least one of these combinations is non-zero on
2077 * linearly independent schedule coefficients.
2078 * The rows are normalized to involve as few of the last
2079 * coefficients as possible and to have a positive initial value.
2081 static int node_update_vmap(struct isl_sched_node
*node
)
2084 int n_row
= isl_mat_rows(node
->sched
);
2086 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2087 1 + node
->nparam
, node
->nvar
);
2089 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2090 isl_mat_free(node
->indep
);
2091 isl_mat_free(node
->vmap
);
2093 node
->indep
= isl_mat_transpose(U
);
2094 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2095 node
->indep
= isl_mat_drop_rows(node
->indep
, 0, node
->rank
);
2096 node
->indep
= normalize_independent(node
->indep
);
2099 if (!node
->indep
|| !node
->vmap
|| node
->rank
< 0)
2104 /* Is "edge" marked as a validity or a conditional validity edge?
2106 static int is_any_validity(struct isl_sched_edge
*edge
)
2108 return is_validity(edge
) || is_conditional_validity(edge
);
2111 /* How many times should we count the constraints in "edge"?
2113 * We count as follows
2114 * validity -> 1 (>= 0)
2115 * validity+proximity -> 2 (>= 0 and upper bound)
2116 * proximity -> 2 (lower and upper bound)
2117 * local(+any) -> 2 (>= 0 and <= 0)
2119 * If an edge is only marked conditional_validity then it counts
2120 * as zero since it is only checked afterwards.
2122 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2123 * Otherwise, we ignore them.
2125 static int edge_multiplicity(struct isl_sched_edge
*edge
, int use_coincidence
)
2127 if (is_proximity(edge
) || force_zero(edge
, use_coincidence
))
2129 if (is_validity(edge
))
2134 /* How many times should the constraints in "edge" be counted
2135 * as a parametric intra-node constraint?
2137 * Only proximity edges that are not forced zero need
2138 * coefficient constraints that include coefficients for parameters.
2139 * If the edge is also a validity edge, then only
2140 * an upper bound is introduced. Otherwise, both lower and upper bounds
2143 static int parametric_intra_edge_multiplicity(struct isl_sched_edge
*edge
,
2144 int use_coincidence
)
2146 if (edge
->src
!= edge
->dst
)
2148 if (!is_proximity(edge
))
2150 if (force_zero(edge
, use_coincidence
))
2152 if (is_validity(edge
))
2158 /* Add "f" times the number of equality and inequality constraints of "bset"
2159 * to "n_eq" and "n_ineq" and free "bset".
2161 static isl_stat
update_count(__isl_take isl_basic_set
*bset
,
2162 int f
, int *n_eq
, int *n_ineq
)
2165 return isl_stat_error
;
2167 *n_eq
+= isl_basic_set_n_equality(bset
);
2168 *n_ineq
+= isl_basic_set_n_inequality(bset
);
2169 isl_basic_set_free(bset
);
2174 /* Count the number of equality and inequality constraints
2175 * that will be added for the given map.
2177 * The edges that require parameter coefficients are counted separately.
2179 * "use_coincidence" is set if we should take into account coincidence edges.
2181 static isl_stat
count_map_constraints(struct isl_sched_graph
*graph
,
2182 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2183 int *n_eq
, int *n_ineq
, int use_coincidence
)
2186 isl_basic_set
*coef
;
2187 int f
= edge_multiplicity(edge
, use_coincidence
);
2188 int fp
= parametric_intra_edge_multiplicity(edge
, use_coincidence
);
2195 if (edge
->src
!= edge
->dst
) {
2196 coef
= inter_coefficients(graph
, edge
, map
);
2197 return update_count(coef
, f
, n_eq
, n_ineq
);
2201 copy
= isl_map_copy(map
);
2202 coef
= intra_coefficients(graph
, edge
->src
, copy
);
2203 if (update_count(coef
, fp
, n_eq
, n_ineq
) < 0)
2208 copy
= isl_map_copy(map
);
2209 coef
= intra_coefficients(graph
, edge
->src
, copy
);
2210 if (update_count(coef
, f
- fp
, n_eq
, n_ineq
) < 0)
2218 return isl_stat_error
;
2221 /* Count the number of equality and inequality constraints
2222 * that will be added to the main lp problem.
2223 * We count as follows
2224 * validity -> 1 (>= 0)
2225 * validity+proximity -> 2 (>= 0 and upper bound)
2226 * proximity -> 2 (lower and upper bound)
2227 * local(+any) -> 2 (>= 0 and <= 0)
2229 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2230 * Otherwise, we ignore them.
2232 static int count_constraints(struct isl_sched_graph
*graph
,
2233 int *n_eq
, int *n_ineq
, int use_coincidence
)
2237 *n_eq
= *n_ineq
= 0;
2238 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2239 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2240 isl_map
*map
= isl_map_copy(edge
->map
);
2242 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2243 use_coincidence
) < 0)
2250 /* Count the number of constraints that will be added by
2251 * add_bound_constant_constraints to bound the values of the constant terms
2252 * and increment *n_eq and *n_ineq accordingly.
2254 * In practice, add_bound_constant_constraints only adds inequalities.
2256 static isl_stat
count_bound_constant_constraints(isl_ctx
*ctx
,
2257 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2259 if (isl_options_get_schedule_max_constant_term(ctx
) == -1)
2262 *n_ineq
+= graph
->n
;
2267 /* Add constraints to bound the values of the constant terms in the schedule,
2268 * if requested by the user.
2270 * The maximal value of the constant terms is defined by the option
2271 * "schedule_max_constant_term".
2273 static isl_stat
add_bound_constant_constraints(isl_ctx
*ctx
,
2274 struct isl_sched_graph
*graph
)
2280 max
= isl_options_get_schedule_max_constant_term(ctx
);
2284 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2286 for (i
= 0; i
< graph
->n
; ++i
) {
2287 struct isl_sched_node
*node
= &graph
->node
[i
];
2290 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2292 return isl_stat_error
;
2293 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2294 pos
= node_cst_coef_offset(node
);
2295 isl_int_set_si(graph
->lp
->ineq
[k
][1 + pos
], -1);
2296 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2302 /* Count the number of constraints that will be added by
2303 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2306 * In practice, add_bound_coefficient_constraints only adds inequalities.
2308 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2309 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2313 if (isl_options_get_schedule_max_coefficient(ctx
) == -1 &&
2314 !isl_options_get_schedule_treat_coalescing(ctx
))
2317 for (i
= 0; i
< graph
->n
; ++i
)
2318 *n_ineq
+= graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2323 /* Add constraints to graph->lp that bound the values of
2324 * the parameter schedule coefficients of "node" to "max" and
2325 * the variable schedule coefficients to the corresponding entry
2327 * In either case, a negative value means that no bound needs to be imposed.
2329 * For parameter coefficients, this amounts to adding a constraint
2337 * The variables coefficients are, however, not represented directly.
2338 * Instead, the variable coefficients c_x are written as differences
2339 * c_x = c_x^+ - c_x^-.
2342 * -max_i <= c_x_i <= max_i
2346 * -max_i <= c_x_i^+ - c_x_i^- <= max_i
2350 * -(c_x_i^+ - c_x_i^-) + max_i >= 0
2351 * c_x_i^+ - c_x_i^- + max_i >= 0
2353 static isl_stat
node_add_coefficient_constraints(isl_ctx
*ctx
,
2354 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
, int max
)
2360 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2362 for (j
= 0; j
< node
->nparam
; ++j
) {
2368 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2370 return isl_stat_error
;
2371 dim
= 1 + node_par_coef_offset(node
) + j
;
2372 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2373 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2374 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2377 ineq
= isl_vec_alloc(ctx
, 1 + total
);
2378 ineq
= isl_vec_clr(ineq
);
2380 return isl_stat_error
;
2381 for (i
= 0; i
< node
->nvar
; ++i
) {
2382 int pos
= 1 + node_var_coef_pos(node
, i
);
2384 if (isl_int_is_neg(node
->max
->el
[i
]))
2387 isl_int_set_si(ineq
->el
[pos
], 1);
2388 isl_int_set_si(ineq
->el
[pos
+ 1], -1);
2389 isl_int_set(ineq
->el
[0], node
->max
->el
[i
]);
2391 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2394 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2396 isl_seq_neg(ineq
->el
+ pos
, ineq
->el
+ pos
+ 2 * i
, 2);
2397 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2400 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2407 return isl_stat_error
;
2410 /* Add constraints that bound the values of the variable and parameter
2411 * coefficients of the schedule.
2413 * The maximal value of the coefficients is defined by the option
2414 * 'schedule_max_coefficient' and the entries in node->max.
2415 * These latter entries are only set if either the schedule_max_coefficient
2416 * option or the schedule_treat_coalescing option is set.
2418 static isl_stat
add_bound_coefficient_constraints(isl_ctx
*ctx
,
2419 struct isl_sched_graph
*graph
)
2424 max
= isl_options_get_schedule_max_coefficient(ctx
);
2426 if (max
== -1 && !isl_options_get_schedule_treat_coalescing(ctx
))
2429 for (i
= 0; i
< graph
->n
; ++i
) {
2430 struct isl_sched_node
*node
= &graph
->node
[i
];
2432 if (node_add_coefficient_constraints(ctx
, graph
, node
, max
) < 0)
2433 return isl_stat_error
;
2439 /* Add a constraint to graph->lp that equates the value at position
2440 * "sum_pos" to the sum of the "n" values starting at "first".
2442 static isl_stat
add_sum_constraint(struct isl_sched_graph
*graph
,
2443 int sum_pos
, int first
, int n
)
2448 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2450 k
= isl_basic_set_alloc_equality(graph
->lp
);
2452 return isl_stat_error
;
2453 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2454 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2455 for (i
= 0; i
< n
; ++i
)
2456 isl_int_set_si(graph
->lp
->eq
[k
][1 + first
+ i
], 1);
2461 /* Add a constraint to graph->lp that equates the value at position
2462 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2464 static isl_stat
add_param_sum_constraint(struct isl_sched_graph
*graph
,
2470 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2472 k
= isl_basic_set_alloc_equality(graph
->lp
);
2474 return isl_stat_error
;
2475 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2476 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2477 for (i
= 0; i
< graph
->n
; ++i
) {
2478 int pos
= 1 + node_par_coef_offset(&graph
->node
[i
]);
2480 for (j
= 0; j
< graph
->node
[i
].nparam
; ++j
)
2481 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2487 /* Add a constraint to graph->lp that equates the value at position
2488 * "sum_pos" to the sum of the variable coefficients of all nodes.
2490 static isl_stat
add_var_sum_constraint(struct isl_sched_graph
*graph
,
2496 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2498 k
= isl_basic_set_alloc_equality(graph
->lp
);
2500 return isl_stat_error
;
2501 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2502 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2503 for (i
= 0; i
< graph
->n
; ++i
) {
2504 struct isl_sched_node
*node
= &graph
->node
[i
];
2505 int pos
= 1 + node_var_coef_offset(node
);
2507 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2508 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2514 /* Construct an ILP problem for finding schedule coefficients
2515 * that result in non-negative, but small dependence distances
2516 * over all dependences.
2517 * In particular, the dependence distances over proximity edges
2518 * are bounded by m_0 + m_n n and we compute schedule coefficients
2519 * with small values (preferably zero) of m_n and m_0.
2521 * All variables of the ILP are non-negative. The actual coefficients
2522 * may be negative, so each coefficient is represented as the difference
2523 * of two non-negative variables. The negative part always appears
2524 * immediately before the positive part.
2525 * Other than that, the variables have the following order
2527 * - sum of positive and negative parts of m_n coefficients
2529 * - sum of all c_n coefficients
2530 * (unconstrained when computing non-parametric schedules)
2531 * - sum of positive and negative parts of all c_x coefficients
2532 * - positive and negative parts of m_n coefficients
2534 * - positive and negative parts of c_i_x, in opposite order
2535 * - c_i_n (if parametric)
2538 * The constraints are those from the edges plus two or three equalities
2539 * to express the sums.
2541 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2542 * Otherwise, we ignore them.
2544 static isl_stat
setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2545 int use_coincidence
)
2555 parametric
= ctx
->opt
->schedule_parametric
;
2556 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2558 total
= param_pos
+ 2 * nparam
;
2559 for (i
= 0; i
< graph
->n
; ++i
) {
2560 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2561 if (node_update_vmap(node
) < 0)
2562 return isl_stat_error
;
2563 node
->start
= total
;
2564 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
2567 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2568 return isl_stat_error
;
2569 if (count_bound_constant_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2570 return isl_stat_error
;
2571 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2572 return isl_stat_error
;
2574 space
= isl_space_set_alloc(ctx
, 0, total
);
2575 isl_basic_set_free(graph
->lp
);
2576 n_eq
+= 2 + parametric
;
2578 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
2580 if (add_sum_constraint(graph
, 0, param_pos
, 2 * nparam
) < 0)
2581 return isl_stat_error
;
2582 if (parametric
&& add_param_sum_constraint(graph
, 2) < 0)
2583 return isl_stat_error
;
2584 if (add_var_sum_constraint(graph
, 3) < 0)
2585 return isl_stat_error
;
2586 if (add_bound_constant_constraints(ctx
, graph
) < 0)
2587 return isl_stat_error
;
2588 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2589 return isl_stat_error
;
2590 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2591 return isl_stat_error
;
2592 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2593 return isl_stat_error
;
2598 /* Analyze the conflicting constraint found by
2599 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2600 * constraint of one of the edges between distinct nodes, living, moreover
2601 * in distinct SCCs, then record the source and sink SCC as this may
2602 * be a good place to cut between SCCs.
2604 static int check_conflict(int con
, void *user
)
2607 struct isl_sched_graph
*graph
= user
;
2609 if (graph
->src_scc
>= 0)
2612 con
-= graph
->lp
->n_eq
;
2614 if (con
>= graph
->lp
->n_ineq
)
2617 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2618 if (!is_validity(&graph
->edge
[i
]))
2620 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2622 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2624 if (graph
->edge
[i
].start
> con
)
2626 if (graph
->edge
[i
].end
<= con
)
2628 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2629 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2635 /* Check whether the next schedule row of the given node needs to be
2636 * non-trivial. Lower-dimensional domains may have some trivial rows,
2637 * but as soon as the number of remaining required non-trivial rows
2638 * is as large as the number or remaining rows to be computed,
2639 * all remaining rows need to be non-trivial.
2641 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2643 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2646 /* Construct a non-triviality region with triviality directions
2647 * corresponding to the rows of "indep".
2648 * The rows of "indep" are expressed in terms of the schedule coefficients c_i,
2649 * while the triviality directions are expressed in terms of
2650 * pairs of non-negative variables c^+_i - c^-_i, with c^-_i appearing
2651 * before c^+_i. Furthermore,
2652 * the pairs of non-negative variables representing the coefficients
2653 * are stored in the opposite order.
2655 static __isl_give isl_mat
*construct_trivial(__isl_keep isl_mat
*indep
)
2664 ctx
= isl_mat_get_ctx(indep
);
2665 n
= isl_mat_rows(indep
);
2666 n_var
= isl_mat_cols(indep
);
2667 mat
= isl_mat_alloc(ctx
, n
, 2 * n_var
);
2670 for (i
= 0; i
< n
; ++i
) {
2671 for (j
= 0; j
< n_var
; ++j
) {
2672 int nj
= n_var
- 1 - j
;
2673 isl_int_neg(mat
->row
[i
][2 * nj
], indep
->row
[i
][j
]);
2674 isl_int_set(mat
->row
[i
][2 * nj
+ 1], indep
->row
[i
][j
]);
2681 /* Solve the ILP problem constructed in setup_lp.
2682 * For each node such that all the remaining rows of its schedule
2683 * need to be non-trivial, we construct a non-triviality region.
2684 * This region imposes that the next row is independent of previous rows.
2685 * In particular, the non-triviality region enforces that at least
2686 * one of the linear combinations in the rows of node->indep is non-zero.
2688 static __isl_give isl_vec
*solve_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2694 for (i
= 0; i
< graph
->n
; ++i
) {
2695 struct isl_sched_node
*node
= &graph
->node
[i
];
2698 graph
->region
[i
].pos
= node_var_coef_offset(node
);
2699 if (needs_row(graph
, node
))
2700 trivial
= construct_trivial(node
->indep
);
2702 trivial
= isl_mat_zero(ctx
, 0, 0);
2703 graph
->region
[i
].trivial
= trivial
;
2705 lp
= isl_basic_set_copy(graph
->lp
);
2706 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2707 graph
->region
, &check_conflict
, graph
);
2708 for (i
= 0; i
< graph
->n
; ++i
)
2709 isl_mat_free(graph
->region
[i
].trivial
);
2713 /* Extract the coefficients for the variables of "node" from "sol".
2715 * Each schedule coefficient c_i_x is represented as the difference
2716 * between two non-negative variables c_i_x^+ - c_i_x^-.
2717 * The c_i_x^- appear before their c_i_x^+ counterpart.
2718 * Furthermore, the order of these pairs is the opposite of that
2719 * of the corresponding coefficients.
2721 * Return c_i_x = c_i_x^+ - c_i_x^-
2723 static __isl_give isl_vec
*extract_var_coef(struct isl_sched_node
*node
,
2724 __isl_keep isl_vec
*sol
)
2732 csol
= isl_vec_alloc(isl_vec_get_ctx(sol
), node
->nvar
);
2736 pos
= 1 + node_var_coef_offset(node
);
2737 for (i
= 0; i
< node
->nvar
; ++i
)
2738 isl_int_sub(csol
->el
[node
->nvar
- 1 - i
],
2739 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
2744 /* Update the schedules of all nodes based on the given solution
2745 * of the LP problem.
2746 * The new row is added to the current band.
2747 * All possibly negative coefficients are encoded as a difference
2748 * of two non-negative variables, so we need to perform the subtraction
2751 * If coincident is set, then the caller guarantees that the new
2752 * row satisfies the coincidence constraints.
2754 static int update_schedule(struct isl_sched_graph
*graph
,
2755 __isl_take isl_vec
*sol
, int coincident
)
2758 isl_vec
*csol
= NULL
;
2763 isl_die(sol
->ctx
, isl_error_internal
,
2764 "no solution found", goto error
);
2765 if (graph
->n_total_row
>= graph
->max_row
)
2766 isl_die(sol
->ctx
, isl_error_internal
,
2767 "too many schedule rows", goto error
);
2769 for (i
= 0; i
< graph
->n
; ++i
) {
2770 struct isl_sched_node
*node
= &graph
->node
[i
];
2772 int row
= isl_mat_rows(node
->sched
);
2775 csol
= extract_var_coef(node
, sol
);
2779 isl_map_free(node
->sched_map
);
2780 node
->sched_map
= NULL
;
2781 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2784 pos
= node_cst_coef_offset(node
);
2785 node
->sched
= isl_mat_set_element(node
->sched
,
2786 row
, 0, sol
->el
[1 + pos
]);
2787 pos
= node_par_coef_offset(node
);
2788 for (j
= 0; j
< node
->nparam
; ++j
)
2789 node
->sched
= isl_mat_set_element(node
->sched
,
2790 row
, 1 + j
, sol
->el
[1 + pos
+ j
]);
2791 for (j
= 0; j
< node
->nvar
; ++j
)
2792 node
->sched
= isl_mat_set_element(node
->sched
,
2793 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2794 node
->coincident
[graph
->n_total_row
] = coincident
;
2800 graph
->n_total_row
++;
2809 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2810 * and return this isl_aff.
2812 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2813 struct isl_sched_node
*node
, int row
)
2821 aff
= isl_aff_zero_on_domain(ls
);
2822 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2823 aff
= isl_aff_set_constant(aff
, v
);
2824 for (j
= 0; j
< node
->nparam
; ++j
) {
2825 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2826 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2828 for (j
= 0; j
< node
->nvar
; ++j
) {
2829 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2830 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2838 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2839 * and return this multi_aff.
2841 * The result is defined over the uncompressed node domain.
2843 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2844 struct isl_sched_node
*node
, int first
, int n
)
2848 isl_local_space
*ls
;
2855 nrow
= isl_mat_rows(node
->sched
);
2856 if (node
->compressed
)
2857 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2859 space
= isl_space_copy(node
->space
);
2860 ls
= isl_local_space_from_space(isl_space_copy(space
));
2861 space
= isl_space_from_domain(space
);
2862 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2863 ma
= isl_multi_aff_zero(space
);
2865 for (i
= first
; i
< first
+ n
; ++i
) {
2866 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2867 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2870 isl_local_space_free(ls
);
2872 if (node
->compressed
)
2873 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2874 isl_multi_aff_copy(node
->compress
));
2879 /* Convert node->sched into a multi_aff and return this multi_aff.
2881 * The result is defined over the uncompressed node domain.
2883 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2884 struct isl_sched_node
*node
)
2888 nrow
= isl_mat_rows(node
->sched
);
2889 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
2892 /* Convert node->sched into a map and return this map.
2894 * The result is cached in node->sched_map, which needs to be released
2895 * whenever node->sched is updated.
2896 * It is defined over the uncompressed node domain.
2898 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2900 if (!node
->sched_map
) {
2903 ma
= node_extract_schedule_multi_aff(node
);
2904 node
->sched_map
= isl_map_from_multi_aff(ma
);
2907 return isl_map_copy(node
->sched_map
);
2910 /* Construct a map that can be used to update a dependence relation
2911 * based on the current schedule.
2912 * That is, construct a map expressing that source and sink
2913 * are executed within the same iteration of the current schedule.
2914 * This map can then be intersected with the dependence relation.
2915 * This is not the most efficient way, but this shouldn't be a critical
2918 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2919 struct isl_sched_node
*dst
)
2921 isl_map
*src_sched
, *dst_sched
;
2923 src_sched
= node_extract_schedule(src
);
2924 dst_sched
= node_extract_schedule(dst
);
2925 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2928 /* Intersect the domains of the nested relations in domain and range
2929 * of "umap" with "map".
2931 static __isl_give isl_union_map
*intersect_domains(
2932 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2934 isl_union_set
*uset
;
2936 umap
= isl_union_map_zip(umap
);
2937 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2938 umap
= isl_union_map_intersect_domain(umap
, uset
);
2939 umap
= isl_union_map_zip(umap
);
2943 /* Update the dependence relation of the given edge based
2944 * on the current schedule.
2945 * If the dependence is carried completely by the current schedule, then
2946 * it is removed from the edge_tables. It is kept in the list of edges
2947 * as otherwise all edge_tables would have to be recomputed.
2949 static int update_edge(struct isl_sched_graph
*graph
,
2950 struct isl_sched_edge
*edge
)
2955 id
= specializer(edge
->src
, edge
->dst
);
2956 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2960 if (edge
->tagged_condition
) {
2961 edge
->tagged_condition
=
2962 intersect_domains(edge
->tagged_condition
, id
);
2963 if (!edge
->tagged_condition
)
2966 if (edge
->tagged_validity
) {
2967 edge
->tagged_validity
=
2968 intersect_domains(edge
->tagged_validity
, id
);
2969 if (!edge
->tagged_validity
)
2973 empty
= isl_map_plain_is_empty(edge
->map
);
2977 graph_remove_edge(graph
, edge
);
2986 /* Does the domain of "umap" intersect "uset"?
2988 static int domain_intersects(__isl_keep isl_union_map
*umap
,
2989 __isl_keep isl_union_set
*uset
)
2993 umap
= isl_union_map_copy(umap
);
2994 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
2995 empty
= isl_union_map_is_empty(umap
);
2996 isl_union_map_free(umap
);
2998 return empty
< 0 ? -1 : !empty
;
3001 /* Does the range of "umap" intersect "uset"?
3003 static int range_intersects(__isl_keep isl_union_map
*umap
,
3004 __isl_keep isl_union_set
*uset
)
3008 umap
= isl_union_map_copy(umap
);
3009 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3010 empty
= isl_union_map_is_empty(umap
);
3011 isl_union_map_free(umap
);
3013 return empty
< 0 ? -1 : !empty
;
3016 /* Are the condition dependences of "edge" local with respect to
3017 * the current schedule?
3019 * That is, are domain and range of the condition dependences mapped
3020 * to the same point?
3022 * In other words, is the condition false?
3024 static int is_condition_false(struct isl_sched_edge
*edge
)
3026 isl_union_map
*umap
;
3027 isl_map
*map
, *sched
, *test
;
3030 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
3031 if (empty
< 0 || empty
)
3034 umap
= isl_union_map_copy(edge
->tagged_condition
);
3035 umap
= isl_union_map_zip(umap
);
3036 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3037 map
= isl_map_from_union_map(umap
);
3039 sched
= node_extract_schedule(edge
->src
);
3040 map
= isl_map_apply_domain(map
, sched
);
3041 sched
= node_extract_schedule(edge
->dst
);
3042 map
= isl_map_apply_range(map
, sched
);
3044 test
= isl_map_identity(isl_map_get_space(map
));
3045 local
= isl_map_is_subset(map
, test
);
3052 /* For each conditional validity constraint that is adjacent
3053 * to a condition with domain in condition_source or range in condition_sink,
3054 * turn it into an unconditional validity constraint.
3056 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
3057 __isl_take isl_union_set
*condition_source
,
3058 __isl_take isl_union_set
*condition_sink
)
3062 condition_source
= isl_union_set_coalesce(condition_source
);
3063 condition_sink
= isl_union_set_coalesce(condition_sink
);
3065 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3067 isl_union_map
*validity
;
3069 if (!is_conditional_validity(&graph
->edge
[i
]))
3071 if (is_validity(&graph
->edge
[i
]))
3074 validity
= graph
->edge
[i
].tagged_validity
;
3075 adjacent
= domain_intersects(validity
, condition_sink
);
3076 if (adjacent
>= 0 && !adjacent
)
3077 adjacent
= range_intersects(validity
, condition_source
);
3083 set_validity(&graph
->edge
[i
]);
3086 isl_union_set_free(condition_source
);
3087 isl_union_set_free(condition_sink
);
3090 isl_union_set_free(condition_source
);
3091 isl_union_set_free(condition_sink
);
3095 /* Update the dependence relations of all edges based on the current schedule
3096 * and enforce conditional validity constraints that are adjacent
3097 * to satisfied condition constraints.
3099 * First check if any of the condition constraints are satisfied
3100 * (i.e., not local to the outer schedule) and keep track of
3101 * their domain and range.
3102 * Then update all dependence relations (which removes the non-local
3104 * Finally, if any condition constraints turned out to be satisfied,
3105 * then turn all adjacent conditional validity constraints into
3106 * unconditional validity constraints.
3108 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3112 isl_union_set
*source
, *sink
;
3114 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3115 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3116 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3118 isl_union_set
*uset
;
3119 isl_union_map
*umap
;
3121 if (!is_condition(&graph
->edge
[i
]))
3123 if (is_local(&graph
->edge
[i
]))
3125 local
= is_condition_false(&graph
->edge
[i
]);
3133 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3134 uset
= isl_union_map_domain(umap
);
3135 source
= isl_union_set_union(source
, uset
);
3137 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3138 uset
= isl_union_map_range(umap
);
3139 sink
= isl_union_set_union(sink
, uset
);
3142 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
3143 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
3148 return unconditionalize_adjacent_validity(graph
, source
, sink
);
3150 isl_union_set_free(source
);
3151 isl_union_set_free(sink
);
3154 isl_union_set_free(source
);
3155 isl_union_set_free(sink
);
3159 static void next_band(struct isl_sched_graph
*graph
)
3161 graph
->band_start
= graph
->n_total_row
;
3164 /* Return the union of the universe domains of the nodes in "graph"
3165 * that satisfy "pred".
3167 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
3168 struct isl_sched_graph
*graph
,
3169 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
3175 for (i
= 0; i
< graph
->n
; ++i
)
3176 if (pred(&graph
->node
[i
], data
))
3180 isl_die(ctx
, isl_error_internal
,
3181 "empty component", return NULL
);
3183 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3184 dom
= isl_union_set_from_set(set
);
3186 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
3187 if (!pred(&graph
->node
[i
], data
))
3189 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3190 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
3196 /* Return a list of unions of universe domains, where each element
3197 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3199 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
3200 struct isl_sched_graph
*graph
)
3203 isl_union_set_list
*filters
;
3205 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
3206 for (i
= 0; i
< graph
->scc
; ++i
) {
3209 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
3210 filters
= isl_union_set_list_add(filters
, dom
);
3216 /* Return a list of two unions of universe domains, one for the SCCs up
3217 * to and including graph->src_scc and another for the other SCCs.
3219 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
3220 struct isl_sched_graph
*graph
)
3223 isl_union_set_list
*filters
;
3225 filters
= isl_union_set_list_alloc(ctx
, 2);
3226 dom
= isl_sched_graph_domain(ctx
, graph
,
3227 &node_scc_at_most
, graph
->src_scc
);
3228 filters
= isl_union_set_list_add(filters
, dom
);
3229 dom
= isl_sched_graph_domain(ctx
, graph
,
3230 &node_scc_at_least
, graph
->src_scc
+ 1);
3231 filters
= isl_union_set_list_add(filters
, dom
);
3236 /* Copy nodes that satisfy node_pred from the src dependence graph
3237 * to the dst dependence graph.
3239 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
3240 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
3245 for (i
= 0; i
< src
->n
; ++i
) {
3248 if (!node_pred(&src
->node
[i
], data
))
3252 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
3253 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
3254 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
3255 dst
->node
[j
].compress
=
3256 isl_multi_aff_copy(src
->node
[i
].compress
);
3257 dst
->node
[j
].decompress
=
3258 isl_multi_aff_copy(src
->node
[i
].decompress
);
3259 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
3260 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
3261 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
3262 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
3263 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
3264 dst
->node
[j
].sizes
= isl_multi_val_copy(src
->node
[i
].sizes
);
3265 dst
->node
[j
].max
= isl_vec_copy(src
->node
[i
].max
);
3268 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
3270 if (dst
->node
[j
].compressed
&&
3271 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
3272 !dst
->node
[j
].decompress
))
3279 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3280 * to the dst dependence graph.
3281 * If the source or destination node of the edge is not in the destination
3282 * graph, then it must be a backward proximity edge and it should simply
3285 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3286 struct isl_sched_graph
*src
,
3287 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3290 enum isl_edge_type t
;
3293 for (i
= 0; i
< src
->n_edge
; ++i
) {
3294 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3296 isl_union_map
*tagged_condition
;
3297 isl_union_map
*tagged_validity
;
3298 struct isl_sched_node
*dst_src
, *dst_dst
;
3300 if (!edge_pred(edge
, data
))
3303 if (isl_map_plain_is_empty(edge
->map
))
3306 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
3307 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
3308 if (!dst_src
|| !dst_dst
) {
3309 if (is_validity(edge
) || is_conditional_validity(edge
))
3310 isl_die(ctx
, isl_error_internal
,
3311 "backward (conditional) validity edge",
3316 map
= isl_map_copy(edge
->map
);
3317 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3318 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3320 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3321 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3322 dst
->edge
[dst
->n_edge
].map
= map
;
3323 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3324 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3325 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3328 if (edge
->tagged_condition
&& !tagged_condition
)
3330 if (edge
->tagged_validity
&& !tagged_validity
)
3333 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
3335 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
3337 if (graph_edge_table_add(ctx
, dst
, t
,
3338 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3346 /* Compute the maximal number of variables over all nodes.
3347 * This is the maximal number of linearly independent schedule
3348 * rows that we need to compute.
3349 * Just in case we end up in a part of the dependence graph
3350 * with only lower-dimensional domains, we make sure we will
3351 * compute the required amount of extra linearly independent rows.
3353 static int compute_maxvar(struct isl_sched_graph
*graph
)
3358 for (i
= 0; i
< graph
->n
; ++i
) {
3359 struct isl_sched_node
*node
= &graph
->node
[i
];
3362 if (node_update_vmap(node
) < 0)
3364 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3365 if (nvar
> graph
->maxvar
)
3366 graph
->maxvar
= nvar
;
3372 /* Extract the subgraph of "graph" that consists of the node satisfying
3373 * "node_pred" and the edges satisfying "edge_pred" and store
3374 * the result in "sub".
3376 static int extract_sub_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3377 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3378 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3379 int data
, struct isl_sched_graph
*sub
)
3381 int i
, n
= 0, n_edge
= 0;
3384 for (i
= 0; i
< graph
->n
; ++i
)
3385 if (node_pred(&graph
->node
[i
], data
))
3387 for (i
= 0; i
< graph
->n_edge
; ++i
)
3388 if (edge_pred(&graph
->edge
[i
], data
))
3390 if (graph_alloc(ctx
, sub
, n
, n_edge
) < 0)
3392 if (copy_nodes(sub
, graph
, node_pred
, data
) < 0)
3394 if (graph_init_table(ctx
, sub
) < 0)
3396 for (t
= 0; t
<= isl_edge_last
; ++t
)
3397 sub
->max_edge
[t
] = graph
->max_edge
[t
];
3398 if (graph_init_edge_tables(ctx
, sub
) < 0)
3400 if (copy_edges(ctx
, sub
, graph
, edge_pred
, data
) < 0)
3402 sub
->n_row
= graph
->n_row
;
3403 sub
->max_row
= graph
->max_row
;
3404 sub
->n_total_row
= graph
->n_total_row
;
3405 sub
->band_start
= graph
->band_start
;
3410 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3411 struct isl_sched_graph
*graph
);
3412 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3413 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3415 /* Compute a schedule for a subgraph of "graph". In particular, for
3416 * the graph composed of nodes that satisfy node_pred and edges that
3417 * that satisfy edge_pred.
3418 * If the subgraph is known to consist of a single component, then wcc should
3419 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3420 * Otherwise, we call compute_schedule, which will check whether the subgraph
3423 * The schedule is inserted at "node" and the updated schedule node
3426 static __isl_give isl_schedule_node
*compute_sub_schedule(
3427 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3428 struct isl_sched_graph
*graph
,
3429 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3430 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3433 struct isl_sched_graph split
= { 0 };
3435 if (extract_sub_graph(ctx
, graph
, node_pred
, edge_pred
, data
,
3440 node
= compute_schedule_wcc(node
, &split
);
3442 node
= compute_schedule(node
, &split
);
3444 graph_free(ctx
, &split
);
3447 graph_free(ctx
, &split
);
3448 return isl_schedule_node_free(node
);
3451 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3453 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3456 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3458 return edge
->dst
->scc
<= scc
;
3461 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3463 return edge
->src
->scc
>= scc
;
3466 /* Reset the current band by dropping all its schedule rows.
3468 static int reset_band(struct isl_sched_graph
*graph
)
3473 drop
= graph
->n_total_row
- graph
->band_start
;
3474 graph
->n_total_row
-= drop
;
3475 graph
->n_row
-= drop
;
3477 for (i
= 0; i
< graph
->n
; ++i
) {
3478 struct isl_sched_node
*node
= &graph
->node
[i
];
3480 isl_map_free(node
->sched_map
);
3481 node
->sched_map
= NULL
;
3483 node
->sched
= isl_mat_drop_rows(node
->sched
,
3484 graph
->band_start
, drop
);
3493 /* Split the current graph into two parts and compute a schedule for each
3494 * part individually. In particular, one part consists of all SCCs up
3495 * to and including graph->src_scc, while the other part contains the other
3496 * SCCs. The split is enforced by a sequence node inserted at position "node"
3497 * in the schedule tree. Return the updated schedule node.
3498 * If either of these two parts consists of a sequence, then it is spliced
3499 * into the sequence containing the two parts.
3501 * The current band is reset. It would be possible to reuse
3502 * the previously computed rows as the first rows in the next
3503 * band, but recomputing them may result in better rows as we are looking
3504 * at a smaller part of the dependence graph.
3506 static __isl_give isl_schedule_node
*compute_split_schedule(
3507 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3511 isl_union_set_list
*filters
;
3516 if (reset_band(graph
) < 0)
3517 return isl_schedule_node_free(node
);
3521 ctx
= isl_schedule_node_get_ctx(node
);
3522 filters
= extract_split(ctx
, graph
);
3523 node
= isl_schedule_node_insert_sequence(node
, filters
);
3524 node
= isl_schedule_node_child(node
, 1);
3525 node
= isl_schedule_node_child(node
, 0);
3527 node
= compute_sub_schedule(node
, ctx
, graph
,
3528 &node_scc_at_least
, &edge_src_scc_at_least
,
3529 graph
->src_scc
+ 1, 0);
3530 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3531 node
= isl_schedule_node_parent(node
);
3532 node
= isl_schedule_node_parent(node
);
3534 node
= isl_schedule_node_sequence_splice_child(node
, 1);
3535 node
= isl_schedule_node_child(node
, 0);
3536 node
= isl_schedule_node_child(node
, 0);
3537 node
= compute_sub_schedule(node
, ctx
, graph
,
3538 &node_scc_at_most
, &edge_dst_scc_at_most
,
3540 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3541 node
= isl_schedule_node_parent(node
);
3542 node
= isl_schedule_node_parent(node
);
3544 node
= isl_schedule_node_sequence_splice_child(node
, 0);
3549 /* Insert a band node at position "node" in the schedule tree corresponding
3550 * to the current band in "graph". Mark the band node permutable
3551 * if "permutable" is set.
3552 * The partial schedules and the coincidence property are extracted
3553 * from the graph nodes.
3554 * Return the updated schedule node.
3556 static __isl_give isl_schedule_node
*insert_current_band(
3557 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3563 isl_multi_pw_aff
*mpa
;
3564 isl_multi_union_pw_aff
*mupa
;
3570 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3571 "graph should have at least one node",
3572 return isl_schedule_node_free(node
));
3574 start
= graph
->band_start
;
3575 end
= graph
->n_total_row
;
3578 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3579 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3580 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3582 for (i
= 1; i
< graph
->n
; ++i
) {
3583 isl_multi_union_pw_aff
*mupa_i
;
3585 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3587 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3588 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3589 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3591 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3593 for (i
= 0; i
< n
; ++i
)
3594 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3595 graph
->node
[0].coincident
[start
+ i
]);
3596 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3601 /* Update the dependence relations based on the current schedule,
3602 * add the current band to "node" and then continue with the computation
3604 * Return the updated schedule node.
3606 static __isl_give isl_schedule_node
*compute_next_band(
3607 __isl_take isl_schedule_node
*node
,
3608 struct isl_sched_graph
*graph
, int permutable
)
3615 ctx
= isl_schedule_node_get_ctx(node
);
3616 if (update_edges(ctx
, graph
) < 0)
3617 return isl_schedule_node_free(node
);
3618 node
= insert_current_band(node
, graph
, permutable
);
3621 node
= isl_schedule_node_child(node
, 0);
3622 node
= compute_schedule(node
, graph
);
3623 node
= isl_schedule_node_parent(node
);
3628 /* Add the constraints "coef" derived from an edge from "node" to itself
3629 * to graph->lp in order to respect the dependences and to try and carry them.
3630 * "pos" is the sequence number of the edge that needs to be carried.
3631 * "coef" represents general constraints on coefficients (c_0, c_n, c_x)
3632 * of valid constraints for (y - x) with x and y instances of the node.
3634 * The constraints added to graph->lp need to enforce
3636 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3637 * = c_j_x (y - x) >= e_i
3639 * for each (x,y) in the dependence relation of the edge.
3640 * That is, (-e_i, 0, c_j_x) needs to be plugged in for (c_0, c_n, c_x),
3641 * taking into account that each coefficient in c_j_x is represented
3642 * as a pair of non-negative coefficients.
3644 static isl_stat
add_intra_constraints(struct isl_sched_graph
*graph
,
3645 struct isl_sched_node
*node
, __isl_take isl_basic_set
*coef
, int pos
)
3649 isl_dim_map
*dim_map
;
3652 return isl_stat_error
;
3654 ctx
= isl_basic_set_get_ctx(coef
);
3655 offset
= coef_var_offset(coef
);
3656 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
3657 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3658 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
3663 /* Add the constraints "coef" derived from an edge from "src" to "dst"
3664 * to graph->lp in order to respect the dependences and to try and carry them.
3665 * "pos" is the sequence number of the edge that needs to be carried or
3666 * -1 if no attempt should be made to carry the dependences.
3667 * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y)
3668 * of valid constraints for (x, y) with x and y instances of "src" and "dst".
3670 * The constraints added to graph->lp need to enforce
3672 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3674 * for each (x,y) in the dependence relation of the edge or
3676 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= 0
3680 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3682 * (c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3683 * needs to be plugged in for (c_0, c_n, c_x, c_y),
3684 * taking into account that each coefficient in c_j_x and c_k_x is represented
3685 * as a pair of non-negative coefficients.
3687 static isl_stat
add_inter_constraints(struct isl_sched_graph
*graph
,
3688 struct isl_sched_node
*src
, struct isl_sched_node
*dst
,
3689 __isl_take isl_basic_set
*coef
, int pos
)
3693 isl_dim_map
*dim_map
;
3696 return isl_stat_error
;
3698 ctx
= isl_basic_set_get_ctx(coef
);
3699 offset
= coef_var_offset(coef
);
3700 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
3702 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3703 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
3708 /* Data structure collecting information used during the construction
3709 * of an LP for carrying dependences.
3711 * "intra" is a sequence of coefficient constraints for intra-node edges.
3712 * "inter" is a sequence of coefficient constraints for inter-node edges.
3715 isl_basic_set_list
*intra
;
3716 isl_basic_set_list
*inter
;
3719 /* Free all the data stored in "carry".
3721 static void isl_carry_clear(struct isl_carry
*carry
)
3723 isl_basic_set_list_free(carry
->intra
);
3724 isl_basic_set_list_free(carry
->inter
);
3727 /* Return a pointer to the node in "graph" that lives in "space".
3728 * If the requested node has been compressed, then "space"
3729 * corresponds to the compressed space.
3731 * First try and see if "space" is the space of an uncompressed node.
3732 * If so, return that node.
3733 * Otherwise, "space" was constructed by construct_compressed_id and
3734 * contains a user pointer pointing to the node in the tuple id.
3736 static struct isl_sched_node
*graph_find_compressed_node(isl_ctx
*ctx
,
3737 struct isl_sched_graph
*graph
, __isl_keep isl_space
*space
)
3740 struct isl_sched_node
*node
;
3745 node
= graph_find_node(ctx
, graph
, space
);
3749 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
3750 node
= isl_id_get_user(id
);
3756 if (!(node
>= &graph
->node
[0] && node
< &graph
->node
[graph
->n
]))
3757 isl_die(ctx
, isl_error_internal
,
3758 "space points to invalid node", return NULL
);
3763 /* Internal data structure for add_all_constraints.
3765 * "graph" is the schedule constraint graph for which an LP problem
3766 * is being constructed.
3767 * "carry_inter" indicates whether inter-node edges should be carried.
3768 * "pos" is the position of the next edge that needs to be carried.
3770 struct isl_add_all_constraints_data
{
3772 struct isl_sched_graph
*graph
;
3777 /* Add the constraints "coef" derived from an edge from a node to itself
3778 * to data->graph->lp in order to respect the dependences and
3779 * to try and carry them.
3781 * The space of "coef" is of the form
3783 * coefficients[[c_cst, c_n] -> S[c_x]]
3785 * with S[c_x] the (compressed) space of the node.
3786 * Extract the node from the space and call add_intra_constraints.
3788 static isl_stat
lp_add_intra(__isl_take isl_basic_set
*coef
, void *user
)
3790 struct isl_add_all_constraints_data
*data
= user
;
3792 struct isl_sched_node
*node
;
3794 space
= isl_basic_set_get_space(coef
);
3795 space
= isl_space_range(isl_space_unwrap(space
));
3796 node
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
3797 isl_space_free(space
);
3798 return add_intra_constraints(data
->graph
, node
, coef
, data
->pos
++);
3801 /* Add the constraints "coef" derived from an edge from a node j
3802 * to a node k to data->graph->lp in order to respect the dependences and
3803 * to try and carry them (provided data->carry_inter is set).
3805 * The space of "coef" is of the form
3807 * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]]
3809 * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes.
3810 * Extract the nodes from the space and call add_inter_constraints.
3812 static isl_stat
lp_add_inter(__isl_take isl_basic_set
*coef
, void *user
)
3814 struct isl_add_all_constraints_data
*data
= user
;
3815 isl_space
*space
, *dom
;
3816 struct isl_sched_node
*src
, *dst
;
3819 space
= isl_basic_set_get_space(coef
);
3820 space
= isl_space_unwrap(isl_space_range(isl_space_unwrap(space
)));
3821 dom
= isl_space_domain(isl_space_copy(space
));
3822 src
= graph_find_compressed_node(data
->ctx
, data
->graph
, dom
);
3823 isl_space_free(dom
);
3824 space
= isl_space_range(space
);
3825 dst
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
3826 isl_space_free(space
);
3828 pos
= data
->carry_inter
? data
->pos
++ : -1;
3829 return add_inter_constraints(data
->graph
, src
, dst
, coef
, pos
);
3832 /* Add constraints to graph->lp that force all (conditional) validity
3833 * dependences to be respected and attempt to carry them.
3834 * "intra" is the sequence of coefficient constraints for intra-node edges.
3835 * "inter" is the sequence of coefficient constraints for inter-node edges.
3836 * "carry_inter" indicates whether inter-node edges should be carried or
3839 static isl_stat
add_all_constraints(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3840 __isl_keep isl_basic_set_list
*intra
,
3841 __isl_keep isl_basic_set_list
*inter
, int carry_inter
)
3843 struct isl_add_all_constraints_data data
= { ctx
, graph
, carry_inter
};
3846 if (isl_basic_set_list_foreach(intra
, &lp_add_intra
, &data
) < 0)
3847 return isl_stat_error
;
3848 if (isl_basic_set_list_foreach(inter
, &lp_add_inter
, &data
) < 0)
3849 return isl_stat_error
;
3853 /* Internal data structure for count_all_constraints
3854 * for keeping track of the number of equality and inequality constraints.
3856 struct isl_sched_count
{
3861 /* Add the number of equality and inequality constraints of "bset"
3862 * to data->n_eq and data->n_ineq.
3864 static isl_stat
bset_update_count(__isl_take isl_basic_set
*bset
, void *user
)
3866 struct isl_sched_count
*data
= user
;
3868 return update_count(bset
, 1, &data
->n_eq
, &data
->n_ineq
);
3871 /* Count the number of equality and inequality constraints
3872 * that will be added to the carry_lp problem.
3873 * We count each edge exactly once.
3874 * "intra" is the sequence of coefficient constraints for intra-node edges.
3875 * "inter" is the sequence of coefficient constraints for inter-node edges.
3877 static isl_stat
count_all_constraints(__isl_keep isl_basic_set_list
*intra
,
3878 __isl_keep isl_basic_set_list
*inter
, int *n_eq
, int *n_ineq
)
3880 struct isl_sched_count data
;
3882 data
.n_eq
= data
.n_ineq
= 0;
3883 if (isl_basic_set_list_foreach(inter
, &bset_update_count
, &data
) < 0)
3884 return isl_stat_error
;
3885 if (isl_basic_set_list_foreach(intra
, &bset_update_count
, &data
) < 0)
3886 return isl_stat_error
;
3889 *n_ineq
= data
.n_ineq
;
3894 /* Construct an LP problem for finding schedule coefficients
3895 * such that the schedule carries as many validity dependences as possible.
3896 * In particular, for each dependence i, we bound the dependence distance
3897 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3898 * of all e_i's. Dependences with e_i = 0 in the solution are simply
3899 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3900 * "intra" is the sequence of coefficient constraints for intra-node edges.
3901 * "inter" is the sequence of coefficient constraints for inter-node edges.
3902 * "n_edge" is the total number of edges.
3903 * "carry_inter" indicates whether inter-node edges should be carried or
3904 * only respected. That is, if "carry_inter" is not set, then
3905 * no e_i variables are introduced for the inter-node edges.
3907 * All variables of the LP are non-negative. The actual coefficients
3908 * may be negative, so each coefficient is represented as the difference
3909 * of two non-negative variables. The negative part always appears
3910 * immediately before the positive part.
3911 * Other than that, the variables have the following order
3913 * - sum of (1 - e_i) over all edges
3914 * - sum of all c_n coefficients
3915 * (unconstrained when computing non-parametric schedules)
3916 * - sum of positive and negative parts of all c_x coefficients
3920 * - positive and negative parts of c_i_x, in opposite order
3921 * - c_i_n (if parametric)
3924 * The constraints are those from the (validity) edges plus three equalities
3925 * to express the sums and n_edge inequalities to express e_i <= 1.
3927 static isl_stat
setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3928 int n_edge
, __isl_keep isl_basic_set_list
*intra
,
3929 __isl_keep isl_basic_set_list
*inter
, int carry_inter
)
3938 for (i
= 0; i
< graph
->n
; ++i
) {
3939 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3940 node
->start
= total
;
3941 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
3944 if (count_all_constraints(intra
, inter
, &n_eq
, &n_ineq
) < 0)
3945 return isl_stat_error
;
3947 dim
= isl_space_set_alloc(ctx
, 0, total
);
3948 isl_basic_set_free(graph
->lp
);
3951 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3952 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3954 k
= isl_basic_set_alloc_equality(graph
->lp
);
3956 return isl_stat_error
;
3957 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3958 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3959 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3960 for (i
= 0; i
< n_edge
; ++i
)
3961 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3963 if (add_param_sum_constraint(graph
, 1) < 0)
3964 return isl_stat_error
;
3965 if (add_var_sum_constraint(graph
, 2) < 0)
3966 return isl_stat_error
;
3968 for (i
= 0; i
< n_edge
; ++i
) {
3969 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3971 return isl_stat_error
;
3972 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3973 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3974 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3977 if (add_all_constraints(ctx
, graph
, intra
, inter
, carry_inter
) < 0)
3978 return isl_stat_error
;
3983 static __isl_give isl_schedule_node
*compute_component_schedule(
3984 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3987 /* If the schedule_split_scaled option is set and if the linear
3988 * parts of the scheduling rows for all nodes in the graphs have
3989 * a non-trivial common divisor, then remove this
3990 * common divisor from the linear part.
3991 * Otherwise, insert a band node directly and continue with
3992 * the construction of the schedule.
3994 * If a non-trivial common divisor is found, then
3995 * the linear part is reduced and the remainder is ignored.
3996 * The pieces of the graph that are assigned different remainders
3997 * form (groups of) strongly connected components within
3998 * the scaled down band. If needed, they can therefore
3999 * be ordered along this remainder in a sequence node.
4000 * However, this ordering is not enforced here in order to allow
4001 * the scheduler to combine some of the strongly connected components.
4003 static __isl_give isl_schedule_node
*split_scaled(
4004 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4014 ctx
= isl_schedule_node_get_ctx(node
);
4015 if (!ctx
->opt
->schedule_split_scaled
)
4016 return compute_next_band(node
, graph
, 0);
4018 return compute_next_band(node
, graph
, 0);
4021 isl_int_init(gcd_i
);
4023 isl_int_set_si(gcd
, 0);
4025 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
4027 for (i
= 0; i
< graph
->n
; ++i
) {
4028 struct isl_sched_node
*node
= &graph
->node
[i
];
4029 int cols
= isl_mat_cols(node
->sched
);
4031 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
4032 isl_int_gcd(gcd
, gcd
, gcd_i
);
4035 isl_int_clear(gcd_i
);
4037 if (isl_int_cmp_si(gcd
, 1) <= 0) {
4039 return compute_next_band(node
, graph
, 0);
4042 for (i
= 0; i
< graph
->n
; ++i
) {
4043 struct isl_sched_node
*node
= &graph
->node
[i
];
4045 isl_int_fdiv_q(node
->sched
->row
[row
][0],
4046 node
->sched
->row
[row
][0], gcd
);
4047 isl_int_mul(node
->sched
->row
[row
][0],
4048 node
->sched
->row
[row
][0], gcd
);
4049 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
4056 return compute_next_band(node
, graph
, 0);
4059 return isl_schedule_node_free(node
);
4062 /* Is the schedule row "sol" trivial on node "node"?
4063 * That is, is the solution zero on the dimensions linearly independent of
4064 * the previously found solutions?
4065 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
4067 * Each coefficient is represented as the difference between
4068 * two non-negative values in "sol".
4069 * We construct the schedule row s and check if it is linearly
4070 * independent of previously computed schedule rows
4071 * by computing T s, with T the linear combinations that are zero
4072 * on linearly dependent schedule rows.
4073 * If the result consists of all zeros, then the solution is trivial.
4075 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
4082 if (node
->nvar
== node
->rank
)
4085 node_sol
= extract_var_coef(node
, sol
);
4086 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->indep
), node_sol
);
4090 trivial
= isl_seq_first_non_zero(node_sol
->el
,
4091 node
->nvar
- node
->rank
) == -1;
4093 isl_vec_free(node_sol
);
4098 /* Is the schedule row "sol" trivial on any node where it should
4100 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4102 static int is_any_trivial(struct isl_sched_graph
*graph
,
4103 __isl_keep isl_vec
*sol
)
4107 for (i
= 0; i
< graph
->n
; ++i
) {
4108 struct isl_sched_node
*node
= &graph
->node
[i
];
4111 if (!needs_row(graph
, node
))
4113 trivial
= is_trivial(node
, sol
);
4114 if (trivial
< 0 || trivial
)
4121 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
4122 * If so, return the position of the coalesced dimension.
4123 * Otherwise, return node->nvar or -1 on error.
4125 * In particular, look for pairs of coefficients c_i and c_j such that
4126 * |c_j/c_i| > ceil(size_i/2), i.e., |c_j| > |c_i * ceil(size_i/2)|.
4127 * If any such pair is found, then return i.
4128 * If size_i is infinity, then no check on c_i needs to be performed.
4130 static int find_node_coalescing(struct isl_sched_node
*node
,
4131 __isl_keep isl_vec
*sol
)
4137 if (node
->nvar
<= 1)
4140 csol
= extract_var_coef(node
, sol
);
4144 for (i
= 0; i
< node
->nvar
; ++i
) {
4147 if (isl_int_is_zero(csol
->el
[i
]))
4149 v
= isl_multi_val_get_val(node
->sizes
, i
);
4152 if (!isl_val_is_int(v
)) {
4156 v
= isl_val_div_ui(v
, 2);
4157 v
= isl_val_ceil(v
);
4160 isl_int_mul(max
, v
->n
, csol
->el
[i
]);
4163 for (j
= 0; j
< node
->nvar
; ++j
) {
4166 if (isl_int_abs_gt(csol
->el
[j
], max
))
4182 /* Force the schedule coefficient at position "pos" of "node" to be zero
4184 * The coefficient is encoded as the difference between two non-negative
4185 * variables. Force these two variables to have the same value.
4187 static __isl_give isl_tab_lexmin
*zero_out_node_coef(
4188 __isl_take isl_tab_lexmin
*tl
, struct isl_sched_node
*node
, int pos
)
4194 ctx
= isl_space_get_ctx(node
->space
);
4195 dim
= isl_tab_lexmin_dim(tl
);
4197 return isl_tab_lexmin_free(tl
);
4198 eq
= isl_vec_alloc(ctx
, 1 + dim
);
4199 eq
= isl_vec_clr(eq
);
4201 return isl_tab_lexmin_free(tl
);
4203 pos
= 1 + node_var_coef_pos(node
, pos
);
4204 isl_int_set_si(eq
->el
[pos
], 1);
4205 isl_int_set_si(eq
->el
[pos
+ 1], -1);
4206 tl
= isl_tab_lexmin_add_eq(tl
, eq
->el
);
4212 /* Return the lexicographically smallest rational point in the basic set
4213 * from which "tl" was constructed, double checking that this input set
4216 static __isl_give isl_vec
*non_empty_solution(__isl_keep isl_tab_lexmin
*tl
)
4220 sol
= isl_tab_lexmin_get_solution(tl
);
4224 isl_die(isl_vec_get_ctx(sol
), isl_error_internal
,
4225 "error in schedule construction",
4226 return isl_vec_free(sol
));
4230 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4231 * carry any of the "n_edge" groups of dependences?
4232 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4233 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4234 * by the edge are carried by the solution.
4235 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4236 * one of those is carried.
4238 * Note that despite the fact that the problem is solved using a rational
4239 * solver, the solution is guaranteed to be integral.
4240 * Specifically, the dependence distance lower bounds e_i (and therefore
4241 * also their sum) are integers. See Lemma 5 of [1].
4243 * Any potential denominator of the sum is cleared by this function.
4244 * The denominator is not relevant for any of the other elements
4247 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4248 * Problem, Part II: Multi-Dimensional Time.
4249 * In Intl. Journal of Parallel Programming, 1992.
4251 static int carries_dependences(__isl_keep isl_vec
*sol
, int n_edge
)
4253 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
4254 isl_int_set_si(sol
->el
[0], 1);
4255 return isl_int_cmp_si(sol
->el
[1], n_edge
) < 0;
4258 /* Return the lexicographically smallest rational point in "lp",
4259 * assuming that all variables are non-negative and performing some
4260 * additional sanity checks.
4261 * If "want_integral" is set, then compute the lexicographically smallest
4262 * integer point instead.
4263 * In particular, "lp" should not be empty by construction.
4264 * Double check that this is the case.
4265 * If dependences are not carried for any of the "n_edge" edges,
4266 * then return an empty vector.
4268 * If the schedule_treat_coalescing option is set and
4269 * if the computed schedule performs loop coalescing on a given node,
4270 * i.e., if it is of the form
4272 * c_i i + c_j j + ...
4274 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4275 * to cut out this solution. Repeat this process until no more loop
4276 * coalescing occurs or until no more dependences can be carried.
4277 * In the latter case, revert to the previously computed solution.
4279 * If the caller requests an integral solution and if coalescing should
4280 * be treated, then perform the coalescing treatment first as
4281 * an integral solution computed before coalescing treatment
4282 * would carry the same number of edges and would therefore probably
4283 * also be coalescing.
4285 * To allow the coalescing treatment to be performed first,
4286 * the initial solution is allowed to be rational and it is only
4287 * cut out (if needed) in the next iteration, if no coalescing measures
4290 static __isl_give isl_vec
*non_neg_lexmin(struct isl_sched_graph
*graph
,
4291 __isl_take isl_basic_set
*lp
, int n_edge
, int want_integral
)
4296 isl_vec
*sol
, *prev
= NULL
;
4297 int treat_coalescing
;
4301 ctx
= isl_basic_set_get_ctx(lp
);
4302 treat_coalescing
= isl_options_get_schedule_treat_coalescing(ctx
);
4303 tl
= isl_tab_lexmin_from_basic_set(lp
);
4310 tl
= isl_tab_lexmin_cut_to_integer(tl
);
4311 sol
= non_empty_solution(tl
);
4315 integral
= isl_int_is_one(sol
->el
[0]);
4316 if (!carries_dependences(sol
, n_edge
)) {
4318 prev
= isl_vec_alloc(ctx
, 0);
4323 prev
= isl_vec_free(prev
);
4324 cut
= want_integral
&& !integral
;
4327 if (!treat_coalescing
)
4329 for (i
= 0; i
< graph
->n
; ++i
) {
4330 struct isl_sched_node
*node
= &graph
->node
[i
];
4332 pos
= find_node_coalescing(node
, sol
);
4335 if (pos
< node
->nvar
)
4340 tl
= zero_out_node_coef(tl
, &graph
->node
[i
], pos
);
4345 isl_tab_lexmin_free(tl
);
4349 isl_tab_lexmin_free(tl
);
4355 /* If "edge" is an edge from a node to itself, then add the corresponding
4356 * dependence relation to "umap".
4357 * If "node" has been compressed, then the dependence relation
4358 * is also compressed first.
4360 static __isl_give isl_union_map
*add_intra(__isl_take isl_union_map
*umap
,
4361 struct isl_sched_edge
*edge
)
4364 struct isl_sched_node
*node
= edge
->src
;
4366 if (edge
->src
!= edge
->dst
)
4369 map
= isl_map_copy(edge
->map
);
4370 if (node
->compressed
) {
4371 map
= isl_map_preimage_domain_multi_aff(map
,
4372 isl_multi_aff_copy(node
->decompress
));
4373 map
= isl_map_preimage_range_multi_aff(map
,
4374 isl_multi_aff_copy(node
->decompress
));
4376 umap
= isl_union_map_add_map(umap
, map
);
4380 /* If "edge" is an edge from a node to another node, then add the corresponding
4381 * dependence relation to "umap".
4382 * If the source or destination nodes of "edge" have been compressed,
4383 * then the dependence relation is also compressed first.
4385 static __isl_give isl_union_map
*add_inter(__isl_take isl_union_map
*umap
,
4386 struct isl_sched_edge
*edge
)
4390 if (edge
->src
== edge
->dst
)
4393 map
= isl_map_copy(edge
->map
);
4394 if (edge
->src
->compressed
)
4395 map
= isl_map_preimage_domain_multi_aff(map
,
4396 isl_multi_aff_copy(edge
->src
->decompress
));
4397 if (edge
->dst
->compressed
)
4398 map
= isl_map_preimage_range_multi_aff(map
,
4399 isl_multi_aff_copy(edge
->dst
->decompress
));
4400 umap
= isl_union_map_add_map(umap
, map
);
4404 /* For each (conditional) validity edge in "graph",
4405 * add the corresponding dependence relation using "add"
4406 * to a collection of dependence relations and return the result.
4407 * If "coincidence" is set, then coincidence edges are considered as well.
4409 static __isl_give isl_union_map
*collect_validity(struct isl_sched_graph
*graph
,
4410 __isl_give isl_union_map
*(*add
)(__isl_take isl_union_map
*umap
,
4411 struct isl_sched_edge
*edge
), int coincidence
)
4415 isl_union_map
*umap
;
4417 space
= isl_space_copy(graph
->node
[0].space
);
4418 umap
= isl_union_map_empty(space
);
4420 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4421 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4423 if (!is_any_validity(edge
) &&
4424 (!coincidence
|| !is_coincidence(edge
)))
4427 umap
= add(umap
, edge
);
4433 /* For each dependence relation on a (conditional) validity edge
4434 * from a node to itself,
4435 * construct the set of coefficients of valid constraints for elements
4436 * in that dependence relation and collect the results.
4437 * If "coincidence" is set, then coincidence edges are considered as well.
4439 * In particular, for each dependence relation R, constraints
4440 * on coefficients (c_0, c_n, c_x) are constructed such that
4442 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
4444 * This computation is essentially the same as that performed
4445 * by intra_coefficients, except that it operates on multiple
4448 * Note that if a dependence relation is a union of basic maps,
4449 * then each basic map needs to be treated individually as it may only
4450 * be possible to carry the dependences expressed by some of those
4451 * basic maps and not all of them.
4452 * The collected validity constraints are therefore not coalesced and
4453 * it is assumed that they are not coalesced automatically.
4454 * Duplicate basic maps can be removed, however.
4455 * In particular, if the same basic map appears as a disjunct
4456 * in multiple edges, then it only needs to be carried once.
4458 static __isl_give isl_basic_set_list
*collect_intra_validity(
4459 struct isl_sched_graph
*graph
, int coincidence
)
4461 isl_union_map
*intra
;
4462 isl_union_set
*delta
;
4463 isl_basic_set_list
*list
;
4465 intra
= collect_validity(graph
, &add_intra
, coincidence
);
4466 delta
= isl_union_map_deltas(intra
);
4467 delta
= isl_union_set_remove_divs(delta
);
4468 list
= isl_union_set_get_basic_set_list(delta
);
4469 isl_union_set_free(delta
);
4471 return isl_basic_set_list_coefficients(list
);
4474 /* For each dependence relation on a (conditional) validity edge
4475 * from a node to some other node,
4476 * construct the set of coefficients of valid constraints for elements
4477 * in that dependence relation and collect the results.
4478 * If "coincidence" is set, then coincidence edges are considered as well.
4480 * In particular, for each dependence relation R, constraints
4481 * on coefficients (c_0, c_n, c_x, c_y) are constructed such that
4483 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
4485 * This computation is essentially the same as that performed
4486 * by inter_coefficients, except that it operates on multiple
4489 * Note that if a dependence relation is a union of basic maps,
4490 * then each basic map needs to be treated individually as it may only
4491 * be possible to carry the dependences expressed by some of those
4492 * basic maps and not all of them.
4493 * The collected validity constraints are therefore not coalesced and
4494 * it is assumed that they are not coalesced automatically.
4495 * Duplicate basic maps can be removed, however.
4496 * In particular, if the same basic map appears as a disjunct
4497 * in multiple edges, then it only needs to be carried once.
4499 static __isl_give isl_basic_set_list
*collect_inter_validity(
4500 struct isl_sched_graph
*graph
, int coincidence
)
4502 isl_union_map
*inter
;
4503 isl_union_set
*wrap
;
4504 isl_basic_set_list
*list
;
4506 inter
= collect_validity(graph
, &add_inter
, coincidence
);
4507 inter
= isl_union_map_remove_divs(inter
);
4508 wrap
= isl_union_map_wrap(inter
);
4509 list
= isl_union_set_get_basic_set_list(wrap
);
4510 isl_union_set_free(wrap
);
4511 return isl_basic_set_list_coefficients(list
);
4514 /* Construct an LP problem for finding schedule coefficients
4515 * such that the schedule carries as many of the "n_edge" groups of
4516 * dependences as possible based on the corresponding coefficient
4517 * constraints and return the lexicographically smallest non-trivial solution.
4518 * "intra" is the sequence of coefficient constraints for intra-node edges.
4519 * "inter" is the sequence of coefficient constraints for inter-node edges.
4520 * If "want_integral" is set, then compute an integral solution
4521 * for the coefficients rather than using the numerators
4522 * of a rational solution.
4523 * "carry_inter" indicates whether inter-node edges should be carried or
4526 * If none of the "n_edge" groups can be carried
4527 * then return an empty vector.
4529 static __isl_give isl_vec
*compute_carrying_sol_coef(isl_ctx
*ctx
,
4530 struct isl_sched_graph
*graph
, int n_edge
,
4531 __isl_keep isl_basic_set_list
*intra
,
4532 __isl_keep isl_basic_set_list
*inter
, int want_integral
,
4537 if (setup_carry_lp(ctx
, graph
, n_edge
, intra
, inter
, carry_inter
) < 0)
4540 lp
= isl_basic_set_copy(graph
->lp
);
4541 return non_neg_lexmin(graph
, lp
, n_edge
, want_integral
);
4544 /* Construct an LP problem for finding schedule coefficients
4545 * such that the schedule carries as many of the validity dependences
4547 * return the lexicographically smallest non-trivial solution.
4548 * If "fallback" is set, then the carrying is performed as a fallback
4549 * for the Pluto-like scheduler.
4550 * If "coincidence" is set, then try and carry coincidence edges as well.
4552 * The variable "n_edge" stores the number of groups that should be carried.
4553 * If none of the "n_edge" groups can be carried
4554 * then return an empty vector.
4555 * If, moreover, "n_edge" is zero, then the LP problem does not even
4556 * need to be constructed.
4558 * If a fallback solution is being computed, then compute an integral solution
4559 * for the coefficients rather than using the numerators
4560 * of a rational solution.
4562 * If a fallback solution is being computed, if there are any intra-node
4563 * dependences, and if requested by the user, then first try
4564 * to only carry those intra-node dependences.
4565 * If this fails to carry any dependences, then try again
4566 * with the inter-node dependences included.
4568 static __isl_give isl_vec
*compute_carrying_sol(isl_ctx
*ctx
,
4569 struct isl_sched_graph
*graph
, int fallback
, int coincidence
)
4571 int n_intra
, n_inter
;
4573 struct isl_carry carry
= { 0 };
4576 carry
.intra
= collect_intra_validity(graph
, coincidence
);
4577 carry
.inter
= collect_inter_validity(graph
, coincidence
);
4578 if (!carry
.intra
|| !carry
.inter
)
4580 n_intra
= isl_basic_set_list_n_basic_set(carry
.intra
);
4581 n_inter
= isl_basic_set_list_n_basic_set(carry
.inter
);
4583 if (fallback
&& n_intra
> 0 &&
4584 isl_options_get_schedule_carry_self_first(ctx
)) {
4585 sol
= compute_carrying_sol_coef(ctx
, graph
, n_intra
,
4586 carry
.intra
, carry
.inter
, fallback
, 0);
4587 if (!sol
|| sol
->size
!= 0 || n_inter
== 0) {
4588 isl_carry_clear(&carry
);
4594 n_edge
= n_intra
+ n_inter
;
4596 isl_carry_clear(&carry
);
4597 return isl_vec_alloc(ctx
, 0);
4600 sol
= compute_carrying_sol_coef(ctx
, graph
, n_edge
,
4601 carry
.intra
, carry
.inter
, fallback
, 1);
4602 isl_carry_clear(&carry
);
4605 isl_carry_clear(&carry
);
4609 /* Construct a schedule row for each node such that as many validity dependences
4610 * as possible are carried and then continue with the next band.
4611 * If "fallback" is set, then the carrying is performed as a fallback
4612 * for the Pluto-like scheduler.
4613 * If "coincidence" is set, then try and carry coincidence edges as well.
4615 * If there are no validity dependences, then no dependence can be carried and
4616 * the procedure is guaranteed to fail. If there is more than one component,
4617 * then try computing a schedule on each component separately
4618 * to prevent or at least postpone this failure.
4620 * If a schedule row is computed, then check that dependences are carried
4621 * for at least one of the edges.
4623 * If the computed schedule row turns out to be trivial on one or
4624 * more nodes where it should not be trivial, then we throw it away
4625 * and try again on each component separately.
4627 * If there is only one component, then we accept the schedule row anyway,
4628 * but we do not consider it as a complete row and therefore do not
4629 * increment graph->n_row. Note that the ranks of the nodes that
4630 * do get a non-trivial schedule part will get updated regardless and
4631 * graph->maxvar is computed based on these ranks. The test for
4632 * whether more schedule rows are required in compute_schedule_wcc
4633 * is therefore not affected.
4635 * Insert a band corresponding to the schedule row at position "node"
4636 * of the schedule tree and continue with the construction of the schedule.
4637 * This insertion and the continued construction is performed by split_scaled
4638 * after optionally checking for non-trivial common divisors.
4640 static __isl_give isl_schedule_node
*carry(__isl_take isl_schedule_node
*node
,
4641 struct isl_sched_graph
*graph
, int fallback
, int coincidence
)
4650 ctx
= isl_schedule_node_get_ctx(node
);
4651 sol
= compute_carrying_sol(ctx
, graph
, fallback
, coincidence
);
4653 return isl_schedule_node_free(node
);
4654 if (sol
->size
== 0) {
4657 return compute_component_schedule(node
, graph
, 1);
4658 isl_die(ctx
, isl_error_unknown
, "unable to carry dependences",
4659 return isl_schedule_node_free(node
));
4662 trivial
= is_any_trivial(graph
, sol
);
4664 sol
= isl_vec_free(sol
);
4665 } else if (trivial
&& graph
->scc
> 1) {
4667 return compute_component_schedule(node
, graph
, 1);
4670 if (update_schedule(graph
, sol
, 0) < 0)
4671 return isl_schedule_node_free(node
);
4675 return split_scaled(node
, graph
);
4678 /* Construct a schedule row for each node such that as many validity dependences
4679 * as possible are carried and then continue with the next band.
4680 * Do so as a fallback for the Pluto-like scheduler.
4681 * If "coincidence" is set, then try and carry coincidence edges as well.
4683 static __isl_give isl_schedule_node
*carry_fallback(
4684 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4687 return carry(node
, graph
, 1, coincidence
);
4690 /* Construct a schedule row for each node such that as many validity dependences
4691 * as possible are carried and then continue with the next band.
4692 * Do so for the case where the Feautrier scheduler was selected
4695 static __isl_give isl_schedule_node
*carry_feautrier(
4696 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4698 return carry(node
, graph
, 0, 0);
4701 /* Construct a schedule row for each node such that as many validity dependences
4702 * as possible are carried and then continue with the next band.
4703 * Do so as a fallback for the Pluto-like scheduler.
4705 static __isl_give isl_schedule_node
*carry_dependences(
4706 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4708 return carry_fallback(node
, graph
, 0);
4711 /* Construct a schedule row for each node such that as many validity or
4712 * coincidence dependences as possible are carried and
4713 * then continue with the next band.
4714 * Do so as a fallback for the Pluto-like scheduler.
4716 static __isl_give isl_schedule_node
*carry_coincidence(
4717 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4719 return carry_fallback(node
, graph
, 1);
4722 /* Topologically sort statements mapped to the same schedule iteration
4723 * and add insert a sequence node in front of "node"
4724 * corresponding to this order.
4725 * If "initialized" is set, then it may be assumed that compute_maxvar
4726 * has been called on the current band. Otherwise, call
4727 * compute_maxvar if and before carry_dependences gets called.
4729 * If it turns out to be impossible to sort the statements apart,
4730 * because different dependences impose different orderings
4731 * on the statements, then we extend the schedule such that
4732 * it carries at least one more dependence.
4734 static __isl_give isl_schedule_node
*sort_statements(
4735 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4739 isl_union_set_list
*filters
;
4744 ctx
= isl_schedule_node_get_ctx(node
);
4746 isl_die(ctx
, isl_error_internal
,
4747 "graph should have at least one node",
4748 return isl_schedule_node_free(node
));
4753 if (update_edges(ctx
, graph
) < 0)
4754 return isl_schedule_node_free(node
);
4756 if (graph
->n_edge
== 0)
4759 if (detect_sccs(ctx
, graph
) < 0)
4760 return isl_schedule_node_free(node
);
4763 if (graph
->scc
< graph
->n
) {
4764 if (!initialized
&& compute_maxvar(graph
) < 0)
4765 return isl_schedule_node_free(node
);
4766 return carry_dependences(node
, graph
);
4769 filters
= extract_sccs(ctx
, graph
);
4770 node
= isl_schedule_node_insert_sequence(node
, filters
);
4775 /* Are there any (non-empty) (conditional) validity edges in the graph?
4777 static int has_validity_edges(struct isl_sched_graph
*graph
)
4781 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4784 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
4789 if (is_any_validity(&graph
->edge
[i
]))
4796 /* Should we apply a Feautrier step?
4797 * That is, did the user request the Feautrier algorithm and are
4798 * there any validity dependences (left)?
4800 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4802 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
4805 return has_validity_edges(graph
);
4808 /* Compute a schedule for a connected dependence graph using Feautrier's
4809 * multi-dimensional scheduling algorithm and return the updated schedule node.
4811 * The original algorithm is described in [1].
4812 * The main idea is to minimize the number of scheduling dimensions, by
4813 * trying to satisfy as many dependences as possible per scheduling dimension.
4815 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4816 * Problem, Part II: Multi-Dimensional Time.
4817 * In Intl. Journal of Parallel Programming, 1992.
4819 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
4820 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4822 return carry_feautrier(node
, graph
);
4825 /* Turn off the "local" bit on all (condition) edges.
4827 static void clear_local_edges(struct isl_sched_graph
*graph
)
4831 for (i
= 0; i
< graph
->n_edge
; ++i
)
4832 if (is_condition(&graph
->edge
[i
]))
4833 clear_local(&graph
->edge
[i
]);
4836 /* Does "graph" have both condition and conditional validity edges?
4838 static int need_condition_check(struct isl_sched_graph
*graph
)
4841 int any_condition
= 0;
4842 int any_conditional_validity
= 0;
4844 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4845 if (is_condition(&graph
->edge
[i
]))
4847 if (is_conditional_validity(&graph
->edge
[i
]))
4848 any_conditional_validity
= 1;
4851 return any_condition
&& any_conditional_validity
;
4854 /* Does "graph" contain any coincidence edge?
4856 static int has_any_coincidence(struct isl_sched_graph
*graph
)
4860 for (i
= 0; i
< graph
->n_edge
; ++i
)
4861 if (is_coincidence(&graph
->edge
[i
]))
4867 /* Extract the final schedule row as a map with the iteration domain
4868 * of "node" as domain.
4870 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
4875 row
= isl_mat_rows(node
->sched
) - 1;
4876 ma
= node_extract_partial_schedule_multi_aff(node
, row
, 1);
4877 return isl_map_from_multi_aff(ma
);
4880 /* Is the conditional validity dependence in the edge with index "edge_index"
4881 * violated by the latest (i.e., final) row of the schedule?
4882 * That is, is i scheduled after j
4883 * for any conditional validity dependence i -> j?
4885 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
4887 isl_map
*src_sched
, *dst_sched
, *map
;
4888 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
4891 src_sched
= final_row(edge
->src
);
4892 dst_sched
= final_row(edge
->dst
);
4893 map
= isl_map_copy(edge
->map
);
4894 map
= isl_map_apply_domain(map
, src_sched
);
4895 map
= isl_map_apply_range(map
, dst_sched
);
4896 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
4897 empty
= isl_map_is_empty(map
);
4906 /* Does "graph" have any satisfied condition edges that
4907 * are adjacent to the conditional validity constraint with
4908 * domain "conditional_source" and range "conditional_sink"?
4910 * A satisfied condition is one that is not local.
4911 * If a condition was forced to be local already (i.e., marked as local)
4912 * then there is no need to check if it is in fact local.
4914 * Additionally, mark all adjacent condition edges found as local.
4916 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
4917 __isl_keep isl_union_set
*conditional_source
,
4918 __isl_keep isl_union_set
*conditional_sink
)
4923 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4924 int adjacent
, local
;
4925 isl_union_map
*condition
;
4927 if (!is_condition(&graph
->edge
[i
]))
4929 if (is_local(&graph
->edge
[i
]))
4932 condition
= graph
->edge
[i
].tagged_condition
;
4933 adjacent
= domain_intersects(condition
, conditional_sink
);
4934 if (adjacent
>= 0 && !adjacent
)
4935 adjacent
= range_intersects(condition
,
4936 conditional_source
);
4942 set_local(&graph
->edge
[i
]);
4944 local
= is_condition_false(&graph
->edge
[i
]);
4954 /* Are there any violated conditional validity dependences with
4955 * adjacent condition dependences that are not local with respect
4956 * to the current schedule?
4957 * That is, is the conditional validity constraint violated?
4959 * Additionally, mark all those adjacent condition dependences as local.
4960 * We also mark those adjacent condition dependences that were not marked
4961 * as local before, but just happened to be local already. This ensures
4962 * that they remain local if the schedule is recomputed.
4964 * We first collect domain and range of all violated conditional validity
4965 * dependences and then check if there are any adjacent non-local
4966 * condition dependences.
4968 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
4969 struct isl_sched_graph
*graph
)
4973 isl_union_set
*source
, *sink
;
4975 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4976 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4977 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4978 isl_union_set
*uset
;
4979 isl_union_map
*umap
;
4982 if (!is_conditional_validity(&graph
->edge
[i
]))
4985 violated
= is_violated(graph
, i
);
4993 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4994 uset
= isl_union_map_domain(umap
);
4995 source
= isl_union_set_union(source
, uset
);
4996 source
= isl_union_set_coalesce(source
);
4998 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4999 uset
= isl_union_map_range(umap
);
5000 sink
= isl_union_set_union(sink
, uset
);
5001 sink
= isl_union_set_coalesce(sink
);
5005 any
= has_adjacent_true_conditions(graph
, source
, sink
);
5007 isl_union_set_free(source
);
5008 isl_union_set_free(sink
);
5011 isl_union_set_free(source
);
5012 isl_union_set_free(sink
);
5016 /* Examine the current band (the rows between graph->band_start and
5017 * graph->n_total_row), deciding whether to drop it or add it to "node"
5018 * and then continue with the computation of the next band, if any.
5019 * If "initialized" is set, then it may be assumed that compute_maxvar
5020 * has been called on the current band. Otherwise, call
5021 * compute_maxvar if and before carry_dependences gets called.
5023 * The caller keeps looking for a new row as long as
5024 * graph->n_row < graph->maxvar. If the latest attempt to find
5025 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
5027 * - split between SCCs and start over (assuming we found an interesting
5028 * pair of SCCs between which to split)
5029 * - continue with the next band (assuming the current band has at least
5031 * - if there is more than one SCC left, then split along all SCCs
5032 * - if outer coincidence needs to be enforced, then try to carry as many
5033 * validity or coincidence dependences as possible and
5034 * continue with the next band
5035 * - try to carry as many validity dependences as possible and
5036 * continue with the next band
5037 * In each case, we first insert a band node in the schedule tree
5038 * if any rows have been computed.
5040 * If the caller managed to complete the schedule, we insert a band node
5041 * (if any schedule rows were computed) and we finish off by topologically
5042 * sorting the statements based on the remaining dependences.
5044 static __isl_give isl_schedule_node
*compute_schedule_finish_band(
5045 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5053 if (graph
->n_row
< graph
->maxvar
) {
5055 int empty
= graph
->n_total_row
== graph
->band_start
;
5057 ctx
= isl_schedule_node_get_ctx(node
);
5058 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
5059 return compute_next_band(node
, graph
, 1);
5060 if (graph
->src_scc
>= 0)
5061 return compute_split_schedule(node
, graph
);
5063 return compute_next_band(node
, graph
, 1);
5065 return compute_component_schedule(node
, graph
, 1);
5066 if (!initialized
&& compute_maxvar(graph
) < 0)
5067 return isl_schedule_node_free(node
);
5068 if (isl_options_get_schedule_outer_coincidence(ctx
))
5069 return carry_coincidence(node
, graph
);
5070 return carry_dependences(node
, graph
);
5073 insert
= graph
->n_total_row
> graph
->band_start
;
5075 node
= insert_current_band(node
, graph
, 1);
5076 node
= isl_schedule_node_child(node
, 0);
5078 node
= sort_statements(node
, graph
, initialized
);
5080 node
= isl_schedule_node_parent(node
);
5085 /* Construct a band of schedule rows for a connected dependence graph.
5086 * The caller is responsible for determining the strongly connected
5087 * components and calling compute_maxvar first.
5089 * We try to find a sequence of as many schedule rows as possible that result
5090 * in non-negative dependence distances (independent of the previous rows
5091 * in the sequence, i.e., such that the sequence is tilable), with as
5092 * many of the initial rows as possible satisfying the coincidence constraints.
5093 * The computation stops if we can't find any more rows or if we have found
5094 * all the rows we wanted to find.
5096 * If ctx->opt->schedule_outer_coincidence is set, then we force the
5097 * outermost dimension to satisfy the coincidence constraints. If this
5098 * turns out to be impossible, we fall back on the general scheme above
5099 * and try to carry as many dependences as possible.
5101 * If "graph" contains both condition and conditional validity dependences,
5102 * then we need to check that that the conditional schedule constraint
5103 * is satisfied, i.e., there are no violated conditional validity dependences
5104 * that are adjacent to any non-local condition dependences.
5105 * If there are, then we mark all those adjacent condition dependences
5106 * as local and recompute the current band. Those dependences that
5107 * are marked local will then be forced to be local.
5108 * The initial computation is performed with no dependences marked as local.
5109 * If we are lucky, then there will be no violated conditional validity
5110 * dependences adjacent to any non-local condition dependences.
5111 * Otherwise, we mark some additional condition dependences as local and
5112 * recompute. We continue this process until there are no violations left or
5113 * until we are no longer able to compute a schedule.
5114 * Since there are only a finite number of dependences,
5115 * there will only be a finite number of iterations.
5117 static isl_stat
compute_schedule_wcc_band(isl_ctx
*ctx
,
5118 struct isl_sched_graph
*graph
)
5120 int has_coincidence
;
5121 int use_coincidence
;
5122 int force_coincidence
= 0;
5123 int check_conditional
;
5125 if (sort_sccs(graph
) < 0)
5126 return isl_stat_error
;
5128 clear_local_edges(graph
);
5129 check_conditional
= need_condition_check(graph
);
5130 has_coincidence
= has_any_coincidence(graph
);
5132 if (ctx
->opt
->schedule_outer_coincidence
)
5133 force_coincidence
= 1;
5135 use_coincidence
= has_coincidence
;
5136 while (graph
->n_row
< graph
->maxvar
) {
5141 graph
->src_scc
= -1;
5142 graph
->dst_scc
= -1;
5144 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
5145 return isl_stat_error
;
5146 sol
= solve_lp(ctx
, graph
);
5148 return isl_stat_error
;
5149 if (sol
->size
== 0) {
5150 int empty
= graph
->n_total_row
== graph
->band_start
;
5153 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
5154 use_coincidence
= 0;
5159 coincident
= !has_coincidence
|| use_coincidence
;
5160 if (update_schedule(graph
, sol
, coincident
) < 0)
5161 return isl_stat_error
;
5163 if (!check_conditional
)
5165 violated
= has_violated_conditional_constraint(ctx
, graph
);
5167 return isl_stat_error
;
5170 if (reset_band(graph
) < 0)
5171 return isl_stat_error
;
5172 use_coincidence
= has_coincidence
;
5178 /* Compute a schedule for a connected dependence graph by considering
5179 * the graph as a whole and return the updated schedule node.
5181 * The actual schedule rows of the current band are computed by
5182 * compute_schedule_wcc_band. compute_schedule_finish_band takes
5183 * care of integrating the band into "node" and continuing
5186 static __isl_give isl_schedule_node
*compute_schedule_wcc_whole(
5187 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5194 ctx
= isl_schedule_node_get_ctx(node
);
5195 if (compute_schedule_wcc_band(ctx
, graph
) < 0)
5196 return isl_schedule_node_free(node
);
5198 return compute_schedule_finish_band(node
, graph
, 1);
5201 /* Clustering information used by compute_schedule_wcc_clustering.
5203 * "n" is the number of SCCs in the original dependence graph
5204 * "scc" is an array of "n" elements, each representing an SCC
5205 * of the original dependence graph. All entries in the same cluster
5206 * have the same number of schedule rows.
5207 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
5208 * where each cluster is represented by the index of the first SCC
5209 * in the cluster. Initially, each SCC belongs to a cluster containing
5212 * "scc_in_merge" is used by merge_clusters_along_edge to keep
5213 * track of which SCCs need to be merged.
5215 * "cluster" contains the merged clusters of SCCs after the clustering
5218 * "scc_node" is a temporary data structure used inside copy_partial.
5219 * For each SCC, it keeps track of the number of nodes in the SCC
5220 * that have already been copied.
5222 struct isl_clustering
{
5224 struct isl_sched_graph
*scc
;
5225 struct isl_sched_graph
*cluster
;
5231 /* Initialize the clustering data structure "c" from "graph".
5233 * In particular, allocate memory, extract the SCCs from "graph"
5234 * into c->scc, initialize scc_cluster and construct
5235 * a band of schedule rows for each SCC.
5236 * Within each SCC, there is only one SCC by definition.
5237 * Each SCC initially belongs to a cluster containing only that SCC.
5239 static isl_stat
clustering_init(isl_ctx
*ctx
, struct isl_clustering
*c
,
5240 struct isl_sched_graph
*graph
)
5245 c
->scc
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
5246 c
->cluster
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
5247 c
->scc_cluster
= isl_calloc_array(ctx
, int, c
->n
);
5248 c
->scc_node
= isl_calloc_array(ctx
, int, c
->n
);
5249 c
->scc_in_merge
= isl_calloc_array(ctx
, int, c
->n
);
5250 if (!c
->scc
|| !c
->cluster
||
5251 !c
->scc_cluster
|| !c
->scc_node
|| !c
->scc_in_merge
)
5252 return isl_stat_error
;
5254 for (i
= 0; i
< c
->n
; ++i
) {
5255 if (extract_sub_graph(ctx
, graph
, &node_scc_exactly
,
5256 &edge_scc_exactly
, i
, &c
->scc
[i
]) < 0)
5257 return isl_stat_error
;
5259 if (compute_maxvar(&c
->scc
[i
]) < 0)
5260 return isl_stat_error
;
5261 if (compute_schedule_wcc_band(ctx
, &c
->scc
[i
]) < 0)
5262 return isl_stat_error
;
5263 c
->scc_cluster
[i
] = i
;
5269 /* Free all memory allocated for "c".
5271 static void clustering_free(isl_ctx
*ctx
, struct isl_clustering
*c
)
5276 for (i
= 0; i
< c
->n
; ++i
)
5277 graph_free(ctx
, &c
->scc
[i
]);
5280 for (i
= 0; i
< c
->n
; ++i
)
5281 graph_free(ctx
, &c
->cluster
[i
]);
5283 free(c
->scc_cluster
);
5285 free(c
->scc_in_merge
);
5288 /* Should we refrain from merging the cluster in "graph" with
5289 * any other cluster?
5290 * In particular, is its current schedule band empty and incomplete.
5292 static int bad_cluster(struct isl_sched_graph
*graph
)
5294 return graph
->n_row
< graph
->maxvar
&&
5295 graph
->n_total_row
== graph
->band_start
;
5298 /* Is "edge" a proximity edge with a non-empty dependence relation?
5300 static isl_bool
is_non_empty_proximity(struct isl_sched_edge
*edge
)
5302 if (!is_proximity(edge
))
5303 return isl_bool_false
;
5304 return isl_bool_not(isl_map_plain_is_empty(edge
->map
));
5307 /* Return the index of an edge in "graph" that can be used to merge
5308 * two clusters in "c".
5309 * Return graph->n_edge if no such edge can be found.
5310 * Return -1 on error.
5312 * In particular, return a proximity edge between two clusters
5313 * that is not marked "no_merge" and such that neither of the
5314 * two clusters has an incomplete, empty band.
5316 * If there are multiple such edges, then try and find the most
5317 * appropriate edge to use for merging. In particular, pick the edge
5318 * with the greatest weight. If there are multiple of those,
5319 * then pick one with the shortest distance between
5320 * the two cluster representatives.
5322 static int find_proximity(struct isl_sched_graph
*graph
,
5323 struct isl_clustering
*c
)
5325 int i
, best
= graph
->n_edge
, best_dist
, best_weight
;
5327 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5328 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5332 prox
= is_non_empty_proximity(edge
);
5339 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
5340 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
5342 dist
= c
->scc_cluster
[edge
->dst
->scc
] -
5343 c
->scc_cluster
[edge
->src
->scc
];
5346 weight
= edge
->weight
;
5347 if (best
< graph
->n_edge
) {
5348 if (best_weight
> weight
)
5350 if (best_weight
== weight
&& best_dist
<= dist
)
5355 best_weight
= weight
;
5361 /* Internal data structure used in mark_merge_sccs.
5363 * "graph" is the dependence graph in which a strongly connected
5364 * component is constructed.
5365 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
5366 * "src" and "dst" are the indices of the nodes that are being merged.
5368 struct isl_mark_merge_sccs_data
{
5369 struct isl_sched_graph
*graph
;
5375 /* Check whether the cluster containing node "i" depends on the cluster
5376 * containing node "j". If "i" and "j" belong to the same cluster,
5377 * then they are taken to depend on each other to ensure that
5378 * the resulting strongly connected component consists of complete
5379 * clusters. Furthermore, if "i" and "j" are the two nodes that
5380 * are being merged, then they are taken to depend on each other as well.
5381 * Otherwise, check if there is a (conditional) validity dependence
5382 * from node[j] to node[i], forcing node[i] to follow node[j].
5384 static isl_bool
cluster_follows(int i
, int j
, void *user
)
5386 struct isl_mark_merge_sccs_data
*data
= user
;
5387 struct isl_sched_graph
*graph
= data
->graph
;
5388 int *scc_cluster
= data
->scc_cluster
;
5390 if (data
->src
== i
&& data
->dst
== j
)
5391 return isl_bool_true
;
5392 if (data
->src
== j
&& data
->dst
== i
)
5393 return isl_bool_true
;
5394 if (scc_cluster
[graph
->node
[i
].scc
] == scc_cluster
[graph
->node
[j
].scc
])
5395 return isl_bool_true
;
5397 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
5400 /* Mark all SCCs that belong to either of the two clusters in "c"
5401 * connected by the edge in "graph" with index "edge", or to any
5402 * of the intermediate clusters.
5403 * The marking is recorded in c->scc_in_merge.
5405 * The given edge has been selected for merging two clusters,
5406 * meaning that there is at least a proximity edge between the two nodes.
5407 * However, there may also be (indirect) validity dependences
5408 * between the two nodes. When merging the two clusters, all clusters
5409 * containing one or more of the intermediate nodes along the
5410 * indirect validity dependences need to be merged in as well.
5412 * First collect all such nodes by computing the strongly connected
5413 * component (SCC) containing the two nodes connected by the edge, where
5414 * the two nodes are considered to depend on each other to make
5415 * sure they end up in the same SCC. Similarly, each node is considered
5416 * to depend on every other node in the same cluster to ensure
5417 * that the SCC consists of complete clusters.
5419 * Then the original SCCs that contain any of these nodes are marked
5420 * in c->scc_in_merge.
5422 static isl_stat
mark_merge_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5423 int edge
, struct isl_clustering
*c
)
5425 struct isl_mark_merge_sccs_data data
;
5426 struct isl_tarjan_graph
*g
;
5429 for (i
= 0; i
< c
->n
; ++i
)
5430 c
->scc_in_merge
[i
] = 0;
5433 data
.scc_cluster
= c
->scc_cluster
;
5434 data
.src
= graph
->edge
[edge
].src
- graph
->node
;
5435 data
.dst
= graph
->edge
[edge
].dst
- graph
->node
;
5437 g
= isl_tarjan_graph_component(ctx
, graph
->n
, data
.dst
,
5438 &cluster_follows
, &data
);
5444 isl_die(ctx
, isl_error_internal
,
5445 "expecting at least two nodes in component",
5447 if (g
->order
[--i
] != -1)
5448 isl_die(ctx
, isl_error_internal
,
5449 "expecting end of component marker", goto error
);
5451 for (--i
; i
>= 0 && g
->order
[i
] != -1; --i
) {
5452 int scc
= graph
->node
[g
->order
[i
]].scc
;
5453 c
->scc_in_merge
[scc
] = 1;
5456 isl_tarjan_graph_free(g
);
5459 isl_tarjan_graph_free(g
);
5460 return isl_stat_error
;
5463 /* Construct the identifier "cluster_i".
5465 static __isl_give isl_id
*cluster_id(isl_ctx
*ctx
, int i
)
5469 snprintf(name
, sizeof(name
), "cluster_%d", i
);
5470 return isl_id_alloc(ctx
, name
, NULL
);
5473 /* Construct the space of the cluster with index "i" containing
5474 * the strongly connected component "scc".
5476 * In particular, construct a space called cluster_i with dimension equal
5477 * to the number of schedule rows in the current band of "scc".
5479 static __isl_give isl_space
*cluster_space(struct isl_sched_graph
*scc
, int i
)
5485 nvar
= scc
->n_total_row
- scc
->band_start
;
5486 space
= isl_space_copy(scc
->node
[0].space
);
5487 space
= isl_space_params(space
);
5488 space
= isl_space_set_from_params(space
);
5489 space
= isl_space_add_dims(space
, isl_dim_set
, nvar
);
5490 id
= cluster_id(isl_space_get_ctx(space
), i
);
5491 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
5496 /* Collect the domain of the graph for merging clusters.
5498 * In particular, for each cluster with first SCC "i", construct
5499 * a set in the space called cluster_i with dimension equal
5500 * to the number of schedule rows in the current band of the cluster.
5502 static __isl_give isl_union_set
*collect_domain(isl_ctx
*ctx
,
5503 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5507 isl_union_set
*domain
;
5509 space
= isl_space_params_alloc(ctx
, 0);
5510 domain
= isl_union_set_empty(space
);
5512 for (i
= 0; i
< graph
->scc
; ++i
) {
5515 if (!c
->scc_in_merge
[i
])
5517 if (c
->scc_cluster
[i
] != i
)
5519 space
= cluster_space(&c
->scc
[i
], i
);
5520 domain
= isl_union_set_add_set(domain
, isl_set_universe(space
));
5526 /* Construct a map from the original instances to the corresponding
5527 * cluster instance in the current bands of the clusters in "c".
5529 static __isl_give isl_union_map
*collect_cluster_map(isl_ctx
*ctx
,
5530 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5534 isl_union_map
*cluster_map
;
5536 space
= isl_space_params_alloc(ctx
, 0);
5537 cluster_map
= isl_union_map_empty(space
);
5538 for (i
= 0; i
< graph
->scc
; ++i
) {
5542 if (!c
->scc_in_merge
[i
])
5545 id
= cluster_id(ctx
, c
->scc_cluster
[i
]);
5546 start
= c
->scc
[i
].band_start
;
5547 n
= c
->scc
[i
].n_total_row
- start
;
5548 for (j
= 0; j
< c
->scc
[i
].n
; ++j
) {
5551 struct isl_sched_node
*node
= &c
->scc
[i
].node
[j
];
5553 ma
= node_extract_partial_schedule_multi_aff(node
,
5555 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
,
5557 map
= isl_map_from_multi_aff(ma
);
5558 cluster_map
= isl_union_map_add_map(cluster_map
, map
);
5566 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
5567 * that are not isl_edge_condition or isl_edge_conditional_validity.
5569 static __isl_give isl_schedule_constraints
*add_non_conditional_constraints(
5570 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5571 __isl_take isl_schedule_constraints
*sc
)
5573 enum isl_edge_type t
;
5578 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
5579 if (t
== isl_edge_condition
||
5580 t
== isl_edge_conditional_validity
)
5582 if (!is_type(edge
, t
))
5584 sc
= isl_schedule_constraints_add(sc
, t
,
5585 isl_union_map_copy(umap
));
5591 /* Add schedule constraints of types isl_edge_condition and
5592 * isl_edge_conditional_validity to "sc" by applying "umap" to
5593 * the domains of the wrapped relations in domain and range
5594 * of the corresponding tagged constraints of "edge".
5596 static __isl_give isl_schedule_constraints
*add_conditional_constraints(
5597 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5598 __isl_take isl_schedule_constraints
*sc
)
5600 enum isl_edge_type t
;
5601 isl_union_map
*tagged
;
5603 for (t
= isl_edge_condition
; t
<= isl_edge_conditional_validity
; ++t
) {
5604 if (!is_type(edge
, t
))
5606 if (t
== isl_edge_condition
)
5607 tagged
= isl_union_map_copy(edge
->tagged_condition
);
5609 tagged
= isl_union_map_copy(edge
->tagged_validity
);
5610 tagged
= isl_union_map_zip(tagged
);
5611 tagged
= isl_union_map_apply_domain(tagged
,
5612 isl_union_map_copy(umap
));
5613 tagged
= isl_union_map_zip(tagged
);
5614 sc
= isl_schedule_constraints_add(sc
, t
, tagged
);
5622 /* Given a mapping "cluster_map" from the original instances to
5623 * the cluster instances, add schedule constraints on the clusters
5624 * to "sc" corresponding to the original constraints represented by "edge".
5626 * For non-tagged dependence constraints, the cluster constraints
5627 * are obtained by applying "cluster_map" to the edge->map.
5629 * For tagged dependence constraints, "cluster_map" needs to be applied
5630 * to the domains of the wrapped relations in domain and range
5631 * of the tagged dependence constraints. Pick out the mappings
5632 * from these domains from "cluster_map" and construct their product.
5633 * This mapping can then be applied to the pair of domains.
5635 static __isl_give isl_schedule_constraints
*collect_edge_constraints(
5636 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*cluster_map
,
5637 __isl_take isl_schedule_constraints
*sc
)
5639 isl_union_map
*umap
;
5641 isl_union_set
*uset
;
5642 isl_union_map
*umap1
, *umap2
;
5647 umap
= isl_union_map_from_map(isl_map_copy(edge
->map
));
5648 umap
= isl_union_map_apply_domain(umap
,
5649 isl_union_map_copy(cluster_map
));
5650 umap
= isl_union_map_apply_range(umap
,
5651 isl_union_map_copy(cluster_map
));
5652 sc
= add_non_conditional_constraints(edge
, umap
, sc
);
5653 isl_union_map_free(umap
);
5655 if (!sc
|| (!is_condition(edge
) && !is_conditional_validity(edge
)))
5658 space
= isl_space_domain(isl_map_get_space(edge
->map
));
5659 uset
= isl_union_set_from_set(isl_set_universe(space
));
5660 umap1
= isl_union_map_copy(cluster_map
);
5661 umap1
= isl_union_map_intersect_domain(umap1
, uset
);
5662 space
= isl_space_range(isl_map_get_space(edge
->map
));
5663 uset
= isl_union_set_from_set(isl_set_universe(space
));
5664 umap2
= isl_union_map_copy(cluster_map
);
5665 umap2
= isl_union_map_intersect_domain(umap2
, uset
);
5666 umap
= isl_union_map_product(umap1
, umap2
);
5668 sc
= add_conditional_constraints(edge
, umap
, sc
);
5670 isl_union_map_free(umap
);
5674 /* Given a mapping "cluster_map" from the original instances to
5675 * the cluster instances, add schedule constraints on the clusters
5676 * to "sc" corresponding to all edges in "graph" between nodes that
5677 * belong to SCCs that are marked for merging in "scc_in_merge".
5679 static __isl_give isl_schedule_constraints
*collect_constraints(
5680 struct isl_sched_graph
*graph
, int *scc_in_merge
,
5681 __isl_keep isl_union_map
*cluster_map
,
5682 __isl_take isl_schedule_constraints
*sc
)
5686 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5687 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5689 if (!scc_in_merge
[edge
->src
->scc
])
5691 if (!scc_in_merge
[edge
->dst
->scc
])
5693 sc
= collect_edge_constraints(edge
, cluster_map
, sc
);
5699 /* Construct a dependence graph for scheduling clusters with respect
5700 * to each other and store the result in "merge_graph".
5701 * In particular, the nodes of the graph correspond to the schedule
5702 * dimensions of the current bands of those clusters that have been
5703 * marked for merging in "c".
5705 * First construct an isl_schedule_constraints object for this domain
5706 * by transforming the edges in "graph" to the domain.
5707 * Then initialize a dependence graph for scheduling from these
5710 static isl_stat
init_merge_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5711 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
5713 isl_union_set
*domain
;
5714 isl_union_map
*cluster_map
;
5715 isl_schedule_constraints
*sc
;
5718 domain
= collect_domain(ctx
, graph
, c
);
5719 sc
= isl_schedule_constraints_on_domain(domain
);
5721 return isl_stat_error
;
5722 cluster_map
= collect_cluster_map(ctx
, graph
, c
);
5723 sc
= collect_constraints(graph
, c
->scc_in_merge
, cluster_map
, sc
);
5724 isl_union_map_free(cluster_map
);
5726 r
= graph_init(merge_graph
, sc
);
5728 isl_schedule_constraints_free(sc
);
5733 /* Compute the maximal number of remaining schedule rows that still need
5734 * to be computed for the nodes that belong to clusters with the maximal
5735 * dimension for the current band (i.e., the band that is to be merged).
5736 * Only clusters that are about to be merged are considered.
5737 * "maxvar" is the maximal dimension for the current band.
5738 * "c" contains information about the clusters.
5740 * Return the maximal number of remaining schedule rows or -1 on error.
5742 static int compute_maxvar_max_slack(int maxvar
, struct isl_clustering
*c
)
5748 for (i
= 0; i
< c
->n
; ++i
) {
5750 struct isl_sched_graph
*scc
;
5752 if (!c
->scc_in_merge
[i
])
5755 nvar
= scc
->n_total_row
- scc
->band_start
;
5758 for (j
= 0; j
< scc
->n
; ++j
) {
5759 struct isl_sched_node
*node
= &scc
->node
[j
];
5762 if (node_update_vmap(node
) < 0)
5764 slack
= node
->nvar
- node
->rank
;
5765 if (slack
> max_slack
)
5773 /* If there are any clusters where the dimension of the current band
5774 * (i.e., the band that is to be merged) is smaller than "maxvar" and
5775 * if there are any nodes in such a cluster where the number
5776 * of remaining schedule rows that still need to be computed
5777 * is greater than "max_slack", then return the smallest current band
5778 * dimension of all these clusters. Otherwise return the original value
5779 * of "maxvar". Return -1 in case of any error.
5780 * Only clusters that are about to be merged are considered.
5781 * "c" contains information about the clusters.
5783 static int limit_maxvar_to_slack(int maxvar
, int max_slack
,
5784 struct isl_clustering
*c
)
5788 for (i
= 0; i
< c
->n
; ++i
) {
5790 struct isl_sched_graph
*scc
;
5792 if (!c
->scc_in_merge
[i
])
5795 nvar
= scc
->n_total_row
- scc
->band_start
;
5798 for (j
= 0; j
< scc
->n
; ++j
) {
5799 struct isl_sched_node
*node
= &scc
->node
[j
];
5802 if (node_update_vmap(node
) < 0)
5804 slack
= node
->nvar
- node
->rank
;
5805 if (slack
> max_slack
) {
5815 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
5816 * that still need to be computed. In particular, if there is a node
5817 * in a cluster where the dimension of the current band is smaller
5818 * than merge_graph->maxvar, but the number of remaining schedule rows
5819 * is greater than that of any node in a cluster with the maximal
5820 * dimension for the current band (i.e., merge_graph->maxvar),
5821 * then adjust merge_graph->maxvar to the (smallest) current band dimension
5822 * of those clusters. Without this adjustment, the total number of
5823 * schedule dimensions would be increased, resulting in a skewed view
5824 * of the number of coincident dimensions.
5825 * "c" contains information about the clusters.
5827 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
5828 * then there is no point in attempting any merge since it will be rejected
5829 * anyway. Set merge_graph->maxvar to zero in such cases.
5831 static isl_stat
adjust_maxvar_to_slack(isl_ctx
*ctx
,
5832 struct isl_sched_graph
*merge_graph
, struct isl_clustering
*c
)
5834 int max_slack
, maxvar
;
5836 max_slack
= compute_maxvar_max_slack(merge_graph
->maxvar
, c
);
5838 return isl_stat_error
;
5839 maxvar
= limit_maxvar_to_slack(merge_graph
->maxvar
, max_slack
, c
);
5841 return isl_stat_error
;
5843 if (maxvar
< merge_graph
->maxvar
) {
5844 if (isl_options_get_schedule_maximize_band_depth(ctx
))
5845 merge_graph
->maxvar
= 0;
5847 merge_graph
->maxvar
= maxvar
;
5853 /* Return the number of coincident dimensions in the current band of "graph",
5854 * where the nodes of "graph" are assumed to be scheduled by a single band.
5856 static int get_n_coincident(struct isl_sched_graph
*graph
)
5860 for (i
= graph
->band_start
; i
< graph
->n_total_row
; ++i
)
5861 if (!graph
->node
[0].coincident
[i
])
5864 return i
- graph
->band_start
;
5867 /* Should the clusters be merged based on the cluster schedule
5868 * in the current (and only) band of "merge_graph", given that
5869 * coincidence should be maximized?
5871 * If the number of coincident schedule dimensions in the merged band
5872 * would be less than the maximal number of coincident schedule dimensions
5873 * in any of the merged clusters, then the clusters should not be merged.
5875 static isl_bool
ok_to_merge_coincident(struct isl_clustering
*c
,
5876 struct isl_sched_graph
*merge_graph
)
5883 for (i
= 0; i
< c
->n
; ++i
) {
5884 if (!c
->scc_in_merge
[i
])
5886 n_coincident
= get_n_coincident(&c
->scc
[i
]);
5887 if (n_coincident
> max_coincident
)
5888 max_coincident
= n_coincident
;
5891 n_coincident
= get_n_coincident(merge_graph
);
5893 return n_coincident
>= max_coincident
;
5896 /* Return the transformation on "node" expressed by the current (and only)
5897 * band of "merge_graph" applied to the clusters in "c".
5899 * First find the representation of "node" in its SCC in "c" and
5900 * extract the transformation expressed by the current band.
5901 * Then extract the transformation applied by "merge_graph"
5902 * to the cluster to which this SCC belongs.
5903 * Combine the two to obtain the complete transformation on the node.
5905 * Note that the range of the first transformation is an anonymous space,
5906 * while the domain of the second is named "cluster_X". The range
5907 * of the former therefore needs to be adjusted before the two
5910 static __isl_give isl_map
*extract_node_transformation(isl_ctx
*ctx
,
5911 struct isl_sched_node
*node
, struct isl_clustering
*c
,
5912 struct isl_sched_graph
*merge_graph
)
5914 struct isl_sched_node
*scc_node
, *cluster_node
;
5918 isl_multi_aff
*ma
, *ma2
;
5920 scc_node
= graph_find_node(ctx
, &c
->scc
[node
->scc
], node
->space
);
5921 start
= c
->scc
[node
->scc
].band_start
;
5922 n
= c
->scc
[node
->scc
].n_total_row
- start
;
5923 ma
= node_extract_partial_schedule_multi_aff(scc_node
, start
, n
);
5924 space
= cluster_space(&c
->scc
[node
->scc
], c
->scc_cluster
[node
->scc
]);
5925 cluster_node
= graph_find_node(ctx
, merge_graph
, space
);
5926 if (space
&& !cluster_node
)
5927 isl_die(ctx
, isl_error_internal
, "unable to find cluster",
5928 space
= isl_space_free(space
));
5929 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
5930 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
, id
);
5931 isl_space_free(space
);
5932 n
= merge_graph
->n_total_row
;
5933 ma2
= node_extract_partial_schedule_multi_aff(cluster_node
, 0, n
);
5934 ma
= isl_multi_aff_pullback_multi_aff(ma2
, ma
);
5936 return isl_map_from_multi_aff(ma
);
5939 /* Give a set of distances "set", are they bounded by a small constant
5940 * in direction "pos"?
5941 * In practice, check if they are bounded by 2 by checking that there
5942 * are no elements with a value greater than or equal to 3 or
5943 * smaller than or equal to -3.
5945 static isl_bool
distance_is_bounded(__isl_keep isl_set
*set
, int pos
)
5951 return isl_bool_error
;
5953 test
= isl_set_copy(set
);
5954 test
= isl_set_lower_bound_si(test
, isl_dim_set
, pos
, 3);
5955 bounded
= isl_set_is_empty(test
);
5958 if (bounded
< 0 || !bounded
)
5961 test
= isl_set_copy(set
);
5962 test
= isl_set_upper_bound_si(test
, isl_dim_set
, pos
, -3);
5963 bounded
= isl_set_is_empty(test
);
5969 /* Does the set "set" have a fixed (but possible parametric) value
5970 * at dimension "pos"?
5972 static isl_bool
has_single_value(__isl_keep isl_set
*set
, int pos
)
5978 return isl_bool_error
;
5979 set
= isl_set_copy(set
);
5980 n
= isl_set_dim(set
, isl_dim_set
);
5981 set
= isl_set_project_out(set
, isl_dim_set
, pos
+ 1, n
- (pos
+ 1));
5982 set
= isl_set_project_out(set
, isl_dim_set
, 0, pos
);
5983 single
= isl_set_is_singleton(set
);
5989 /* Does "map" have a fixed (but possible parametric) value
5990 * at dimension "pos" of either its domain or its range?
5992 static isl_bool
has_singular_src_or_dst(__isl_keep isl_map
*map
, int pos
)
5997 set
= isl_map_domain(isl_map_copy(map
));
5998 single
= has_single_value(set
, pos
);
6001 if (single
< 0 || single
)
6004 set
= isl_map_range(isl_map_copy(map
));
6005 single
= has_single_value(set
, pos
);
6011 /* Does the edge "edge" from "graph" have bounded dependence distances
6012 * in the merged graph "merge_graph" of a selection of clusters in "c"?
6014 * Extract the complete transformations of the source and destination
6015 * nodes of the edge, apply them to the edge constraints and
6016 * compute the differences. Finally, check if these differences are bounded
6017 * in each direction.
6019 * If the dimension of the band is greater than the number of
6020 * dimensions that can be expected to be optimized by the edge
6021 * (based on its weight), then also allow the differences to be unbounded
6022 * in the remaining dimensions, but only if either the source or
6023 * the destination has a fixed value in that direction.
6024 * This allows a statement that produces values that are used by
6025 * several instances of another statement to be merged with that
6027 * However, merging such clusters will introduce an inherently
6028 * large proximity distance inside the merged cluster, meaning
6029 * that proximity distances will no longer be optimized in
6030 * subsequent merges. These merges are therefore only allowed
6031 * after all other possible merges have been tried.
6032 * The first time such a merge is encountered, the weight of the edge
6033 * is replaced by a negative weight. The second time (i.e., after
6034 * all merges over edges with a non-negative weight have been tried),
6035 * the merge is allowed.
6037 static isl_bool
has_bounded_distances(isl_ctx
*ctx
, struct isl_sched_edge
*edge
,
6038 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
6039 struct isl_sched_graph
*merge_graph
)
6046 map
= isl_map_copy(edge
->map
);
6047 t
= extract_node_transformation(ctx
, edge
->src
, c
, merge_graph
);
6048 map
= isl_map_apply_domain(map
, t
);
6049 t
= extract_node_transformation(ctx
, edge
->dst
, c
, merge_graph
);
6050 map
= isl_map_apply_range(map
, t
);
6051 dist
= isl_map_deltas(isl_map_copy(map
));
6053 bounded
= isl_bool_true
;
6054 n
= isl_set_dim(dist
, isl_dim_set
);
6055 n_slack
= n
- edge
->weight
;
6056 if (edge
->weight
< 0)
6057 n_slack
-= graph
->max_weight
+ 1;
6058 for (i
= 0; i
< n
; ++i
) {
6059 isl_bool bounded_i
, singular_i
;
6061 bounded_i
= distance_is_bounded(dist
, i
);
6066 if (edge
->weight
>= 0)
6067 bounded
= isl_bool_false
;
6071 singular_i
= has_singular_src_or_dst(map
, i
);
6076 bounded
= isl_bool_false
;
6079 if (!bounded
&& i
>= n
&& edge
->weight
>= 0)
6080 edge
->weight
-= graph
->max_weight
+ 1;
6088 return isl_bool_error
;
6091 /* Should the clusters be merged based on the cluster schedule
6092 * in the current (and only) band of "merge_graph"?
6093 * "graph" is the original dependence graph, while "c" records
6094 * which SCCs are involved in the latest merge.
6096 * In particular, is there at least one proximity constraint
6097 * that is optimized by the merge?
6099 * A proximity constraint is considered to be optimized
6100 * if the dependence distances are small.
6102 static isl_bool
ok_to_merge_proximity(isl_ctx
*ctx
,
6103 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
6104 struct isl_sched_graph
*merge_graph
)
6108 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6109 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6112 if (!is_proximity(edge
))
6114 if (!c
->scc_in_merge
[edge
->src
->scc
])
6116 if (!c
->scc_in_merge
[edge
->dst
->scc
])
6118 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6119 c
->scc_cluster
[edge
->src
->scc
])
6121 bounded
= has_bounded_distances(ctx
, edge
, graph
, c
,
6123 if (bounded
< 0 || bounded
)
6127 return isl_bool_false
;
6130 /* Should the clusters be merged based on the cluster schedule
6131 * in the current (and only) band of "merge_graph"?
6132 * "graph" is the original dependence graph, while "c" records
6133 * which SCCs are involved in the latest merge.
6135 * If the current band is empty, then the clusters should not be merged.
6137 * If the band depth should be maximized and the merge schedule
6138 * is incomplete (meaning that the dimension of some of the schedule
6139 * bands in the original schedule will be reduced), then the clusters
6140 * should not be merged.
6142 * If the schedule_maximize_coincidence option is set, then check that
6143 * the number of coincident schedule dimensions is not reduced.
6145 * Finally, only allow the merge if at least one proximity
6146 * constraint is optimized.
6148 static isl_bool
ok_to_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6149 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
6151 if (merge_graph
->n_total_row
== merge_graph
->band_start
)
6152 return isl_bool_false
;
6154 if (isl_options_get_schedule_maximize_band_depth(ctx
) &&
6155 merge_graph
->n_total_row
< merge_graph
->maxvar
)
6156 return isl_bool_false
;
6158 if (isl_options_get_schedule_maximize_coincidence(ctx
)) {
6161 ok
= ok_to_merge_coincident(c
, merge_graph
);
6166 return ok_to_merge_proximity(ctx
, graph
, c
, merge_graph
);
6169 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
6170 * of the schedule in "node" and return the result.
6172 * That is, essentially compute
6174 * T * N(first:first+n-1)
6176 * taking into account the constant term and the parameter coefficients
6179 static __isl_give isl_mat
*node_transformation(isl_ctx
*ctx
,
6180 struct isl_sched_node
*t_node
, struct isl_sched_node
*node
,
6185 int n_row
, n_col
, n_param
, n_var
;
6187 n_param
= node
->nparam
;
6189 n_row
= isl_mat_rows(t_node
->sched
);
6190 n_col
= isl_mat_cols(node
->sched
);
6191 t
= isl_mat_alloc(ctx
, n_row
, n_col
);
6194 for (i
= 0; i
< n_row
; ++i
) {
6195 isl_seq_cpy(t
->row
[i
], t_node
->sched
->row
[i
], 1 + n_param
);
6196 isl_seq_clr(t
->row
[i
] + 1 + n_param
, n_var
);
6197 for (j
= 0; j
< n
; ++j
)
6198 isl_seq_addmul(t
->row
[i
],
6199 t_node
->sched
->row
[i
][1 + n_param
+ j
],
6200 node
->sched
->row
[first
+ j
],
6201 1 + n_param
+ n_var
);
6206 /* Apply the cluster schedule in "t_node" to the current band
6207 * schedule of the nodes in "graph".
6209 * In particular, replace the rows starting at band_start
6210 * by the result of applying the cluster schedule in "t_node"
6211 * to the original rows.
6213 * The coincidence of the schedule is determined by the coincidence
6214 * of the cluster schedule.
6216 static isl_stat
transform(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6217 struct isl_sched_node
*t_node
)
6223 start
= graph
->band_start
;
6224 n
= graph
->n_total_row
- start
;
6226 n_new
= isl_mat_rows(t_node
->sched
);
6227 for (i
= 0; i
< graph
->n
; ++i
) {
6228 struct isl_sched_node
*node
= &graph
->node
[i
];
6231 t
= node_transformation(ctx
, t_node
, node
, start
, n
);
6232 node
->sched
= isl_mat_drop_rows(node
->sched
, start
, n
);
6233 node
->sched
= isl_mat_concat(node
->sched
, t
);
6234 node
->sched_map
= isl_map_free(node
->sched_map
);
6236 return isl_stat_error
;
6237 for (j
= 0; j
< n_new
; ++j
)
6238 node
->coincident
[start
+ j
] = t_node
->coincident
[j
];
6240 graph
->n_total_row
-= n
;
6242 graph
->n_total_row
+= n_new
;
6243 graph
->n_row
+= n_new
;
6248 /* Merge the clusters marked for merging in "c" into a single
6249 * cluster using the cluster schedule in the current band of "merge_graph".
6250 * The representative SCC for the new cluster is the SCC with
6251 * the smallest index.
6253 * The current band schedule of each SCC in the new cluster is obtained
6254 * by applying the schedule of the corresponding original cluster
6255 * to the original band schedule.
6256 * All SCCs in the new cluster have the same number of schedule rows.
6258 static isl_stat
merge(isl_ctx
*ctx
, struct isl_clustering
*c
,
6259 struct isl_sched_graph
*merge_graph
)
6265 for (i
= 0; i
< c
->n
; ++i
) {
6266 struct isl_sched_node
*node
;
6268 if (!c
->scc_in_merge
[i
])
6272 space
= cluster_space(&c
->scc
[i
], c
->scc_cluster
[i
]);
6274 return isl_stat_error
;
6275 node
= graph_find_node(ctx
, merge_graph
, space
);
6276 isl_space_free(space
);
6278 isl_die(ctx
, isl_error_internal
,
6279 "unable to find cluster",
6280 return isl_stat_error
);
6281 if (transform(ctx
, &c
->scc
[i
], node
) < 0)
6282 return isl_stat_error
;
6283 c
->scc_cluster
[i
] = cluster
;
6289 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
6290 * by scheduling the current cluster bands with respect to each other.
6292 * Construct a dependence graph with a space for each cluster and
6293 * with the coordinates of each space corresponding to the schedule
6294 * dimensions of the current band of that cluster.
6295 * Construct a cluster schedule in this cluster dependence graph and
6296 * apply it to the current cluster bands if it is applicable
6297 * according to ok_to_merge.
6299 * If the number of remaining schedule dimensions in a cluster
6300 * with a non-maximal current schedule dimension is greater than
6301 * the number of remaining schedule dimensions in clusters
6302 * with a maximal current schedule dimension, then restrict
6303 * the number of rows to be computed in the cluster schedule
6304 * to the minimal such non-maximal current schedule dimension.
6305 * Do this by adjusting merge_graph.maxvar.
6307 * Return isl_bool_true if the clusters have effectively been merged
6308 * into a single cluster.
6310 * Note that since the standard scheduling algorithm minimizes the maximal
6311 * distance over proximity constraints, the proximity constraints between
6312 * the merged clusters may not be optimized any further than what is
6313 * sufficient to bring the distances within the limits of the internal
6314 * proximity constraints inside the individual clusters.
6315 * It may therefore make sense to perform an additional translation step
6316 * to bring the clusters closer to each other, while maintaining
6317 * the linear part of the merging schedule found using the standard
6318 * scheduling algorithm.
6320 static isl_bool
try_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6321 struct isl_clustering
*c
)
6323 struct isl_sched_graph merge_graph
= { 0 };
6326 if (init_merge_graph(ctx
, graph
, c
, &merge_graph
) < 0)
6329 if (compute_maxvar(&merge_graph
) < 0)
6331 if (adjust_maxvar_to_slack(ctx
, &merge_graph
,c
) < 0)
6333 if (compute_schedule_wcc_band(ctx
, &merge_graph
) < 0)
6335 merged
= ok_to_merge(ctx
, graph
, c
, &merge_graph
);
6336 if (merged
&& merge(ctx
, c
, &merge_graph
) < 0)
6339 graph_free(ctx
, &merge_graph
);
6342 graph_free(ctx
, &merge_graph
);
6343 return isl_bool_error
;
6346 /* Is there any edge marked "no_merge" between two SCCs that are
6347 * about to be merged (i.e., that are set in "scc_in_merge")?
6348 * "merge_edge" is the proximity edge along which the clusters of SCCs
6349 * are going to be merged.
6351 * If there is any edge between two SCCs with a negative weight,
6352 * while the weight of "merge_edge" is non-negative, then this
6353 * means that the edge was postponed. "merge_edge" should then
6354 * also be postponed since merging along the edge with negative weight should
6355 * be postponed until all edges with non-negative weight have been tried.
6356 * Replace the weight of "merge_edge" by a negative weight as well and
6357 * tell the caller not to attempt a merge.
6359 static int any_no_merge(struct isl_sched_graph
*graph
, int *scc_in_merge
,
6360 struct isl_sched_edge
*merge_edge
)
6364 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6365 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6367 if (!scc_in_merge
[edge
->src
->scc
])
6369 if (!scc_in_merge
[edge
->dst
->scc
])
6373 if (merge_edge
->weight
>= 0 && edge
->weight
< 0) {
6374 merge_edge
->weight
-= graph
->max_weight
+ 1;
6382 /* Merge the two clusters in "c" connected by the edge in "graph"
6383 * with index "edge" into a single cluster.
6384 * If it turns out to be impossible to merge these two clusters,
6385 * then mark the edge as "no_merge" such that it will not be
6388 * First mark all SCCs that need to be merged. This includes the SCCs
6389 * in the two clusters, but it may also include the SCCs
6390 * of intermediate clusters.
6391 * If there is already a no_merge edge between any pair of such SCCs,
6392 * then simply mark the current edge as no_merge as well.
6393 * Likewise, if any of those edges was postponed by has_bounded_distances,
6394 * then postpone the current edge as well.
6395 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
6396 * if the clusters did not end up getting merged, unless the non-merge
6397 * is due to the fact that the edge was postponed. This postponement
6398 * can be recognized by a change in weight (from non-negative to negative).
6400 static isl_stat
merge_clusters_along_edge(isl_ctx
*ctx
,
6401 struct isl_sched_graph
*graph
, int edge
, struct isl_clustering
*c
)
6404 int edge_weight
= graph
->edge
[edge
].weight
;
6406 if (mark_merge_sccs(ctx
, graph
, edge
, c
) < 0)
6407 return isl_stat_error
;
6409 if (any_no_merge(graph
, c
->scc_in_merge
, &graph
->edge
[edge
]))
6410 merged
= isl_bool_false
;
6412 merged
= try_merge(ctx
, graph
, c
);
6414 return isl_stat_error
;
6415 if (!merged
&& edge_weight
== graph
->edge
[edge
].weight
)
6416 graph
->edge
[edge
].no_merge
= 1;
6421 /* Does "node" belong to the cluster identified by "cluster"?
6423 static int node_cluster_exactly(struct isl_sched_node
*node
, int cluster
)
6425 return node
->cluster
== cluster
;
6428 /* Does "edge" connect two nodes belonging to the cluster
6429 * identified by "cluster"?
6431 static int edge_cluster_exactly(struct isl_sched_edge
*edge
, int cluster
)
6433 return edge
->src
->cluster
== cluster
&& edge
->dst
->cluster
== cluster
;
6436 /* Swap the schedule of "node1" and "node2".
6437 * Both nodes have been derived from the same node in a common parent graph.
6438 * Since the "coincident" field is shared with that node
6439 * in the parent graph, there is no need to also swap this field.
6441 static void swap_sched(struct isl_sched_node
*node1
,
6442 struct isl_sched_node
*node2
)
6447 sched
= node1
->sched
;
6448 node1
->sched
= node2
->sched
;
6449 node2
->sched
= sched
;
6451 sched_map
= node1
->sched_map
;
6452 node1
->sched_map
= node2
->sched_map
;
6453 node2
->sched_map
= sched_map
;
6456 /* Copy the current band schedule from the SCCs that form the cluster
6457 * with index "pos" to the actual cluster at position "pos".
6458 * By construction, the index of the first SCC that belongs to the cluster
6461 * The order of the nodes inside both the SCCs and the cluster
6462 * is assumed to be same as the order in the original "graph".
6464 * Since the SCC graphs will no longer be used after this function,
6465 * the schedules are actually swapped rather than copied.
6467 static isl_stat
copy_partial(struct isl_sched_graph
*graph
,
6468 struct isl_clustering
*c
, int pos
)
6472 c
->cluster
[pos
].n_total_row
= c
->scc
[pos
].n_total_row
;
6473 c
->cluster
[pos
].n_row
= c
->scc
[pos
].n_row
;
6474 c
->cluster
[pos
].maxvar
= c
->scc
[pos
].maxvar
;
6476 for (i
= 0; i
< graph
->n
; ++i
) {
6480 if (graph
->node
[i
].cluster
!= pos
)
6482 s
= graph
->node
[i
].scc
;
6483 k
= c
->scc_node
[s
]++;
6484 swap_sched(&c
->cluster
[pos
].node
[j
], &c
->scc
[s
].node
[k
]);
6485 if (c
->scc
[s
].maxvar
> c
->cluster
[pos
].maxvar
)
6486 c
->cluster
[pos
].maxvar
= c
->scc
[s
].maxvar
;
6493 /* Is there a (conditional) validity dependence from node[j] to node[i],
6494 * forcing node[i] to follow node[j] or do the nodes belong to the same
6497 static isl_bool
node_follows_strong_or_same_cluster(int i
, int j
, void *user
)
6499 struct isl_sched_graph
*graph
= user
;
6501 if (graph
->node
[i
].cluster
== graph
->node
[j
].cluster
)
6502 return isl_bool_true
;
6503 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
6506 /* Extract the merged clusters of SCCs in "graph", sort them, and
6507 * store them in c->clusters. Update c->scc_cluster accordingly.
6509 * First keep track of the cluster containing the SCC to which a node
6510 * belongs in the node itself.
6511 * Then extract the clusters into c->clusters, copying the current
6512 * band schedule from the SCCs that belong to the cluster.
6513 * Do this only once per cluster.
6515 * Finally, topologically sort the clusters and update c->scc_cluster
6516 * to match the new scc numbering. While the SCCs were originally
6517 * sorted already, some SCCs that depend on some other SCCs may
6518 * have been merged with SCCs that appear before these other SCCs.
6519 * A reordering may therefore be required.
6521 static isl_stat
extract_clusters(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6522 struct isl_clustering
*c
)
6526 for (i
= 0; i
< graph
->n
; ++i
)
6527 graph
->node
[i
].cluster
= c
->scc_cluster
[graph
->node
[i
].scc
];
6529 for (i
= 0; i
< graph
->scc
; ++i
) {
6530 if (c
->scc_cluster
[i
] != i
)
6532 if (extract_sub_graph(ctx
, graph
, &node_cluster_exactly
,
6533 &edge_cluster_exactly
, i
, &c
->cluster
[i
]) < 0)
6534 return isl_stat_error
;
6535 c
->cluster
[i
].src_scc
= -1;
6536 c
->cluster
[i
].dst_scc
= -1;
6537 if (copy_partial(graph
, c
, i
) < 0)
6538 return isl_stat_error
;
6541 if (detect_ccs(ctx
, graph
, &node_follows_strong_or_same_cluster
) < 0)
6542 return isl_stat_error
;
6543 for (i
= 0; i
< graph
->n
; ++i
)
6544 c
->scc_cluster
[graph
->node
[i
].scc
] = graph
->node
[i
].cluster
;
6549 /* Compute weights on the proximity edges of "graph" that can
6550 * be used by find_proximity to find the most appropriate
6551 * proximity edge to use to merge two clusters in "c".
6552 * The weights are also used by has_bounded_distances to determine
6553 * whether the merge should be allowed.
6554 * Store the maximum of the computed weights in graph->max_weight.
6556 * The computed weight is a measure for the number of remaining schedule
6557 * dimensions that can still be completely aligned.
6558 * In particular, compute the number of equalities between
6559 * input dimensions and output dimensions in the proximity constraints.
6560 * The directions that are already handled by outer schedule bands
6561 * are projected out prior to determining this number.
6563 * Edges that will never be considered by find_proximity are ignored.
6565 static isl_stat
compute_weights(struct isl_sched_graph
*graph
,
6566 struct isl_clustering
*c
)
6570 graph
->max_weight
= 0;
6572 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6573 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6574 struct isl_sched_node
*src
= edge
->src
;
6575 struct isl_sched_node
*dst
= edge
->dst
;
6576 isl_basic_map
*hull
;
6580 prox
= is_non_empty_proximity(edge
);
6582 return isl_stat_error
;
6585 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
6586 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
6588 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6589 c
->scc_cluster
[edge
->src
->scc
])
6592 hull
= isl_map_affine_hull(isl_map_copy(edge
->map
));
6593 hull
= isl_basic_map_transform_dims(hull
, isl_dim_in
, 0,
6594 isl_mat_copy(src
->vmap
));
6595 hull
= isl_basic_map_transform_dims(hull
, isl_dim_out
, 0,
6596 isl_mat_copy(dst
->vmap
));
6597 hull
= isl_basic_map_project_out(hull
,
6598 isl_dim_in
, 0, src
->rank
);
6599 hull
= isl_basic_map_project_out(hull
,
6600 isl_dim_out
, 0, dst
->rank
);
6601 hull
= isl_basic_map_remove_divs(hull
);
6602 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
6603 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
6604 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6605 isl_dim_in
, 0, n_in
);
6606 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6607 isl_dim_out
, 0, n_out
);
6609 return isl_stat_error
;
6610 edge
->weight
= isl_basic_map_n_equality(hull
);
6611 isl_basic_map_free(hull
);
6613 if (edge
->weight
> graph
->max_weight
)
6614 graph
->max_weight
= edge
->weight
;
6620 /* Call compute_schedule_finish_band on each of the clusters in "c"
6621 * in their topological order. This order is determined by the scc
6622 * fields of the nodes in "graph".
6623 * Combine the results in a sequence expressing the topological order.
6625 * If there is only one cluster left, then there is no need to introduce
6626 * a sequence node. Also, in this case, the cluster necessarily contains
6627 * the SCC at position 0 in the original graph and is therefore also
6628 * stored in the first cluster of "c".
6630 static __isl_give isl_schedule_node
*finish_bands_clustering(
6631 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6632 struct isl_clustering
*c
)
6636 isl_union_set_list
*filters
;
6638 if (graph
->scc
== 1)
6639 return compute_schedule_finish_band(node
, &c
->cluster
[0], 0);
6641 ctx
= isl_schedule_node_get_ctx(node
);
6643 filters
= extract_sccs(ctx
, graph
);
6644 node
= isl_schedule_node_insert_sequence(node
, filters
);
6646 for (i
= 0; i
< graph
->scc
; ++i
) {
6647 int j
= c
->scc_cluster
[i
];
6648 node
= isl_schedule_node_child(node
, i
);
6649 node
= isl_schedule_node_child(node
, 0);
6650 node
= compute_schedule_finish_band(node
, &c
->cluster
[j
], 0);
6651 node
= isl_schedule_node_parent(node
);
6652 node
= isl_schedule_node_parent(node
);
6658 /* Compute a schedule for a connected dependence graph by first considering
6659 * each strongly connected component (SCC) in the graph separately and then
6660 * incrementally combining them into clusters.
6661 * Return the updated schedule node.
6663 * Initially, each cluster consists of a single SCC, each with its
6664 * own band schedule. The algorithm then tries to merge pairs
6665 * of clusters along a proximity edge until no more suitable
6666 * proximity edges can be found. During this merging, the schedule
6667 * is maintained in the individual SCCs.
6668 * After the merging is completed, the full resulting clusters
6669 * are extracted and in finish_bands_clustering,
6670 * compute_schedule_finish_band is called on each of them to integrate
6671 * the band into "node" and to continue the computation.
6673 * compute_weights initializes the weights that are used by find_proximity.
6675 static __isl_give isl_schedule_node
*compute_schedule_wcc_clustering(
6676 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6679 struct isl_clustering c
;
6682 ctx
= isl_schedule_node_get_ctx(node
);
6684 if (clustering_init(ctx
, &c
, graph
) < 0)
6687 if (compute_weights(graph
, &c
) < 0)
6691 i
= find_proximity(graph
, &c
);
6694 if (i
>= graph
->n_edge
)
6696 if (merge_clusters_along_edge(ctx
, graph
, i
, &c
) < 0)
6700 if (extract_clusters(ctx
, graph
, &c
) < 0)
6703 node
= finish_bands_clustering(node
, graph
, &c
);
6705 clustering_free(ctx
, &c
);
6708 clustering_free(ctx
, &c
);
6709 return isl_schedule_node_free(node
);
6712 /* Compute a schedule for a connected dependence graph and return
6713 * the updated schedule node.
6715 * If Feautrier's algorithm is selected, we first recursively try to satisfy
6716 * as many validity dependences as possible. When all validity dependences
6717 * are satisfied we extend the schedule to a full-dimensional schedule.
6719 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
6720 * depending on whether the user has selected the option to try and
6721 * compute a schedule for the entire (weakly connected) component first.
6722 * If there is only a single strongly connected component (SCC), then
6723 * there is no point in trying to combine SCCs
6724 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
6725 * is called instead.
6727 static __isl_give isl_schedule_node
*compute_schedule_wcc(
6728 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6735 ctx
= isl_schedule_node_get_ctx(node
);
6736 if (detect_sccs(ctx
, graph
) < 0)
6737 return isl_schedule_node_free(node
);
6739 if (compute_maxvar(graph
) < 0)
6740 return isl_schedule_node_free(node
);
6742 if (need_feautrier_step(ctx
, graph
))
6743 return compute_schedule_wcc_feautrier(node
, graph
);
6745 if (graph
->scc
<= 1 || isl_options_get_schedule_whole_component(ctx
))
6746 return compute_schedule_wcc_whole(node
, graph
);
6748 return compute_schedule_wcc_clustering(node
, graph
);
6751 /* Compute a schedule for each group of nodes identified by node->scc
6752 * separately and then combine them in a sequence node (or as set node
6753 * if graph->weak is set) inserted at position "node" of the schedule tree.
6754 * Return the updated schedule node.
6756 * If "wcc" is set then each of the groups belongs to a single
6757 * weakly connected component in the dependence graph so that
6758 * there is no need for compute_sub_schedule to look for weakly
6759 * connected components.
6761 static __isl_give isl_schedule_node
*compute_component_schedule(
6762 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6767 isl_union_set_list
*filters
;
6771 ctx
= isl_schedule_node_get_ctx(node
);
6773 filters
= extract_sccs(ctx
, graph
);
6775 node
= isl_schedule_node_insert_set(node
, filters
);
6777 node
= isl_schedule_node_insert_sequence(node
, filters
);
6779 for (component
= 0; component
< graph
->scc
; ++component
) {
6780 node
= isl_schedule_node_child(node
, component
);
6781 node
= isl_schedule_node_child(node
, 0);
6782 node
= compute_sub_schedule(node
, ctx
, graph
,
6784 &edge_scc_exactly
, component
, wcc
);
6785 node
= isl_schedule_node_parent(node
);
6786 node
= isl_schedule_node_parent(node
);
6792 /* Compute a schedule for the given dependence graph and insert it at "node".
6793 * Return the updated schedule node.
6795 * We first check if the graph is connected (through validity and conditional
6796 * validity dependences) and, if not, compute a schedule
6797 * for each component separately.
6798 * If the schedule_serialize_sccs option is set, then we check for strongly
6799 * connected components instead and compute a separate schedule for
6800 * each such strongly connected component.
6802 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
6803 struct isl_sched_graph
*graph
)
6810 ctx
= isl_schedule_node_get_ctx(node
);
6811 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
6812 if (detect_sccs(ctx
, graph
) < 0)
6813 return isl_schedule_node_free(node
);
6815 if (detect_wccs(ctx
, graph
) < 0)
6816 return isl_schedule_node_free(node
);
6820 return compute_component_schedule(node
, graph
, 1);
6822 return compute_schedule_wcc(node
, graph
);
6825 /* Compute a schedule on sc->domain that respects the given schedule
6828 * In particular, the schedule respects all the validity dependences.
6829 * If the default isl scheduling algorithm is used, it tries to minimize
6830 * the dependence distances over the proximity dependences.
6831 * If Feautrier's scheduling algorithm is used, the proximity dependence
6832 * distances are only minimized during the extension to a full-dimensional
6835 * If there are any condition and conditional validity dependences,
6836 * then the conditional validity dependences may be violated inside
6837 * a tilable band, provided they have no adjacent non-local
6838 * condition dependences.
6840 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
6841 __isl_take isl_schedule_constraints
*sc
)
6843 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
6844 struct isl_sched_graph graph
= { 0 };
6845 isl_schedule
*sched
;
6846 isl_schedule_node
*node
;
6847 isl_union_set
*domain
;
6849 sc
= isl_schedule_constraints_align_params(sc
);
6851 domain
= isl_schedule_constraints_get_domain(sc
);
6852 if (isl_union_set_n_set(domain
) == 0) {
6853 isl_schedule_constraints_free(sc
);
6854 return isl_schedule_from_domain(domain
);
6857 if (graph_init(&graph
, sc
) < 0)
6858 domain
= isl_union_set_free(domain
);
6860 node
= isl_schedule_node_from_domain(domain
);
6861 node
= isl_schedule_node_child(node
, 0);
6863 node
= compute_schedule(node
, &graph
);
6864 sched
= isl_schedule_node_get_schedule(node
);
6865 isl_schedule_node_free(node
);
6867 graph_free(ctx
, &graph
);
6868 isl_schedule_constraints_free(sc
);
6873 /* Compute a schedule for the given union of domains that respects
6874 * all the validity dependences and minimizes
6875 * the dependence distances over the proximity dependences.
6877 * This function is kept for backward compatibility.
6879 __isl_give isl_schedule
*isl_union_set_compute_schedule(
6880 __isl_take isl_union_set
*domain
,
6881 __isl_take isl_union_map
*validity
,
6882 __isl_take isl_union_map
*proximity
)
6884 isl_schedule_constraints
*sc
;
6886 sc
= isl_schedule_constraints_on_domain(domain
);
6887 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
6888 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
6890 return isl_schedule_constraints_compute_schedule(sc
);