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_private.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
97 * If not NULL, then "bounds" contains a non-parametric set
98 * in the compressed space that is bounded by the size in each direction.
100 struct isl_sched_node
{
104 isl_multi_aff
*compress
;
105 isl_multi_aff
*decompress
;
120 isl_multi_val
*sizes
;
121 isl_basic_set
*bounds
;
125 static int node_has_tuples(const void *entry
, const void *val
)
127 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
128 isl_space
*space
= (isl_space
*) val
;
130 return isl_space_has_equal_tuples(node
->space
, space
);
133 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
135 return node
->scc
== scc
;
138 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
140 return node
->scc
<= scc
;
143 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
145 return node
->scc
>= scc
;
148 /* An edge in the dependence graph. An edge may be used to
149 * ensure validity of the generated schedule, to minimize the dependence
152 * map is the dependence relation, with i -> j in the map if j depends on i
153 * tagged_condition and tagged_validity contain the union of all tagged
154 * condition or conditional validity dependence relations that
155 * specialize the dependence relation "map"; that is,
156 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
157 * or "tagged_validity", then i -> j is an element of "map".
158 * If these fields are NULL, then they represent the empty relation.
159 * src is the source node
160 * dst is the sink node
162 * types is a bit vector containing the types of this edge.
163 * validity is set if the edge is used to ensure correctness
164 * coincidence is used to enforce zero dependence distances
165 * proximity is set if the edge is used to minimize dependence distances
166 * condition is set if the edge represents a condition
167 * for a conditional validity schedule constraint
168 * local can only be set for condition edges and indicates that
169 * the dependence distance over the edge should be zero
170 * conditional_validity is set if the edge is used to conditionally
173 * For validity edges, start and end mark the sequence of inequality
174 * constraints in the LP problem that encode the validity constraint
175 * corresponding to this edge.
177 * During clustering, an edge may be marked "no_merge" if it should
178 * not be used to merge clusters.
179 * The weight is also only used during clustering and it is
180 * an indication of how many schedule dimensions on either side
181 * of the schedule constraints can be aligned.
182 * If the weight is negative, then this means that this edge was postponed
183 * by has_bounded_distances or any_no_merge. The original weight can
184 * be retrieved by adding 1 + graph->max_weight, with "graph"
185 * the graph containing this edge.
187 struct isl_sched_edge
{
189 isl_union_map
*tagged_condition
;
190 isl_union_map
*tagged_validity
;
192 struct isl_sched_node
*src
;
193 struct isl_sched_node
*dst
;
204 /* Is "edge" marked as being of type "type"?
206 static int is_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
208 return ISL_FL_ISSET(edge
->types
, 1 << type
);
211 /* Mark "edge" as being of type "type".
213 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
215 ISL_FL_SET(edge
->types
, 1 << type
);
218 /* No longer mark "edge" as being of type "type"?
220 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
222 ISL_FL_CLR(edge
->types
, 1 << type
);
225 /* Is "edge" marked as a validity edge?
227 static int is_validity(struct isl_sched_edge
*edge
)
229 return is_type(edge
, isl_edge_validity
);
232 /* Mark "edge" as a validity edge.
234 static void set_validity(struct isl_sched_edge
*edge
)
236 set_type(edge
, isl_edge_validity
);
239 /* Is "edge" marked as a proximity edge?
241 static int is_proximity(struct isl_sched_edge
*edge
)
243 return is_type(edge
, isl_edge_proximity
);
246 /* Is "edge" marked as a local edge?
248 static int is_local(struct isl_sched_edge
*edge
)
250 return is_type(edge
, isl_edge_local
);
253 /* Mark "edge" as a local edge.
255 static void set_local(struct isl_sched_edge
*edge
)
257 set_type(edge
, isl_edge_local
);
260 /* No longer mark "edge" as a local edge.
262 static void clear_local(struct isl_sched_edge
*edge
)
264 clear_type(edge
, isl_edge_local
);
267 /* Is "edge" marked as a coincidence edge?
269 static int is_coincidence(struct isl_sched_edge
*edge
)
271 return is_type(edge
, isl_edge_coincidence
);
274 /* Is "edge" marked as a condition edge?
276 static int is_condition(struct isl_sched_edge
*edge
)
278 return is_type(edge
, isl_edge_condition
);
281 /* Is "edge" marked as a conditional validity edge?
283 static int is_conditional_validity(struct isl_sched_edge
*edge
)
285 return is_type(edge
, isl_edge_conditional_validity
);
288 /* Internal information about the dependence graph used during
289 * the construction of the schedule.
291 * intra_hmap is a cache, mapping dependence relations to their dual,
292 * for dependences from a node to itself, possibly without
293 * coefficients for the parameters
294 * intra_hmap_param is a cache, mapping dependence relations to their dual,
295 * for dependences from a node to itself, including coefficients
297 * inter_hmap is a cache, mapping dependence relations to their dual,
298 * for dependences between distinct nodes
299 * if compression is involved then the key for these maps
300 * is the original, uncompressed dependence relation, while
301 * the value is the dual of the compressed dependence relation.
303 * n is the number of nodes
304 * node is the list of nodes
305 * maxvar is the maximal number of variables over all nodes
306 * max_row is the allocated number of rows in the schedule
307 * n_row is the current (maximal) number of linearly independent
308 * rows in the node schedules
309 * n_total_row is the current number of rows in the node schedules
310 * band_start is the starting row in the node schedules of the current band
311 * root is set if this graph is the original dependence graph,
312 * without any splitting
314 * sorted contains a list of node indices sorted according to the
315 * SCC to which a node belongs
317 * n_edge is the number of edges
318 * edge is the list of edges
319 * max_edge contains the maximal number of edges of each type;
320 * in particular, it contains the number of edges in the inital graph.
321 * edge_table contains pointers into the edge array, hashed on the source
322 * and sink spaces; there is one such table for each type;
323 * a given edge may be referenced from more than one table
324 * if the corresponding relation appears in more than one of the
325 * sets of dependences; however, for each type there is only
326 * a single edge between a given pair of source and sink space
327 * in the entire graph
329 * node_table contains pointers into the node array, hashed on the space tuples
331 * region contains a list of variable sequences that should be non-trivial
333 * lp contains the (I)LP problem used to obtain new schedule rows
335 * src_scc and dst_scc are the source and sink SCCs of an edge with
336 * conflicting constraints
338 * scc represents the number of components
339 * weak is set if the components are weakly connected
341 * max_weight is used during clustering and represents the maximal
342 * weight of the relevant proximity edges.
344 struct isl_sched_graph
{
345 isl_map_to_basic_set
*intra_hmap
;
346 isl_map_to_basic_set
*intra_hmap_param
;
347 isl_map_to_basic_set
*inter_hmap
;
349 struct isl_sched_node
*node
;
362 struct isl_sched_edge
*edge
;
364 int max_edge
[isl_edge_last
+ 1];
365 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
367 struct isl_hash_table
*node_table
;
368 struct isl_trivial_region
*region
;
381 /* Initialize node_table based on the list of nodes.
383 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
387 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
388 if (!graph
->node_table
)
391 for (i
= 0; i
< graph
->n
; ++i
) {
392 struct isl_hash_table_entry
*entry
;
395 hash
= isl_space_get_tuple_hash(graph
->node
[i
].space
);
396 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
398 graph
->node
[i
].space
, 1);
401 entry
->data
= &graph
->node
[i
];
407 /* Return a pointer to the node that lives within the given space,
408 * or NULL if there is no such node.
410 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
411 struct isl_sched_graph
*graph
, __isl_keep isl_space
*space
)
413 struct isl_hash_table_entry
*entry
;
416 hash
= isl_space_get_tuple_hash(space
);
417 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
418 &node_has_tuples
, space
, 0);
420 return entry
? entry
->data
: NULL
;
423 static int edge_has_src_and_dst(const void *entry
, const void *val
)
425 const struct isl_sched_edge
*edge
= entry
;
426 const struct isl_sched_edge
*temp
= val
;
428 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
431 /* Add the given edge to graph->edge_table[type].
433 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
434 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
435 struct isl_sched_edge
*edge
)
437 struct isl_hash_table_entry
*entry
;
440 hash
= isl_hash_init();
441 hash
= isl_hash_builtin(hash
, edge
->src
);
442 hash
= isl_hash_builtin(hash
, edge
->dst
);
443 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
444 &edge_has_src_and_dst
, edge
, 1);
446 return isl_stat_error
;
452 /* Allocate the edge_tables based on the maximal number of edges of
455 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
459 for (i
= 0; i
<= isl_edge_last
; ++i
) {
460 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
462 if (!graph
->edge_table
[i
])
469 /* If graph->edge_table[type] contains an edge from the given source
470 * to the given destination, then return the hash table entry of this edge.
471 * Otherwise, return NULL.
473 static struct isl_hash_table_entry
*graph_find_edge_entry(
474 struct isl_sched_graph
*graph
,
475 enum isl_edge_type type
,
476 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
478 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
480 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
482 hash
= isl_hash_init();
483 hash
= isl_hash_builtin(hash
, temp
.src
);
484 hash
= isl_hash_builtin(hash
, temp
.dst
);
485 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
486 &edge_has_src_and_dst
, &temp
, 0);
490 /* If graph->edge_table[type] contains an edge from the given source
491 * to the given destination, then return this edge.
492 * Otherwise, return NULL.
494 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
495 enum isl_edge_type type
,
496 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
498 struct isl_hash_table_entry
*entry
;
500 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
507 /* Check whether the dependence graph has an edge of the given type
508 * between the given two nodes.
510 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
511 enum isl_edge_type type
,
512 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
514 struct isl_sched_edge
*edge
;
517 edge
= graph_find_edge(graph
, type
, src
, dst
);
521 empty
= isl_map_plain_is_empty(edge
->map
);
523 return isl_bool_error
;
528 /* Look for any edge with the same src, dst and map fields as "model".
530 * Return the matching edge if one can be found.
531 * Return "model" if no matching edge is found.
532 * Return NULL on error.
534 static struct isl_sched_edge
*graph_find_matching_edge(
535 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
537 enum isl_edge_type i
;
538 struct isl_sched_edge
*edge
;
540 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
543 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
546 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
556 /* Remove the given edge from all the edge_tables that refer to it.
558 static void graph_remove_edge(struct isl_sched_graph
*graph
,
559 struct isl_sched_edge
*edge
)
561 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
562 enum isl_edge_type i
;
564 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
565 struct isl_hash_table_entry
*entry
;
567 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
570 if (entry
->data
!= edge
)
572 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
576 /* Check whether the dependence graph has any edge
577 * between the given two nodes.
579 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
580 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
582 enum isl_edge_type i
;
585 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
586 r
= graph_has_edge(graph
, i
, src
, dst
);
594 /* Check whether the dependence graph has a validity edge
595 * between the given two nodes.
597 * Conditional validity edges are essentially validity edges that
598 * can be ignored if the corresponding condition edges are iteration private.
599 * Here, we are only checking for the presence of validity
600 * edges, so we need to consider the conditional validity edges too.
601 * In particular, this function is used during the detection
602 * of strongly connected components and we cannot ignore
603 * conditional validity edges during this detection.
605 static isl_bool
graph_has_validity_edge(struct isl_sched_graph
*graph
,
606 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
610 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
614 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
617 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
618 int n_node
, int n_edge
)
623 graph
->n_edge
= n_edge
;
624 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
625 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
626 graph
->region
= isl_alloc_array(ctx
,
627 struct isl_trivial_region
, graph
->n
);
628 graph
->edge
= isl_calloc_array(ctx
,
629 struct isl_sched_edge
, graph
->n_edge
);
631 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
632 graph
->intra_hmap_param
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
633 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
635 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
639 for(i
= 0; i
< graph
->n
; ++i
)
640 graph
->sorted
[i
] = i
;
645 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
649 isl_map_to_basic_set_free(graph
->intra_hmap
);
650 isl_map_to_basic_set_free(graph
->intra_hmap_param
);
651 isl_map_to_basic_set_free(graph
->inter_hmap
);
654 for (i
= 0; i
< graph
->n
; ++i
) {
655 isl_space_free(graph
->node
[i
].space
);
656 isl_set_free(graph
->node
[i
].hull
);
657 isl_multi_aff_free(graph
->node
[i
].compress
);
658 isl_multi_aff_free(graph
->node
[i
].decompress
);
659 isl_mat_free(graph
->node
[i
].sched
);
660 isl_map_free(graph
->node
[i
].sched_map
);
661 isl_mat_free(graph
->node
[i
].indep
);
662 isl_mat_free(graph
->node
[i
].vmap
);
664 free(graph
->node
[i
].coincident
);
665 isl_multi_val_free(graph
->node
[i
].sizes
);
666 isl_basic_set_free(graph
->node
[i
].bounds
);
667 isl_vec_free(graph
->node
[i
].max
);
672 for (i
= 0; i
< graph
->n_edge
; ++i
) {
673 isl_map_free(graph
->edge
[i
].map
);
674 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
675 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
679 for (i
= 0; i
<= isl_edge_last
; ++i
)
680 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
681 isl_hash_table_free(ctx
, graph
->node_table
);
682 isl_basic_set_free(graph
->lp
);
685 /* For each "set" on which this function is called, increment
686 * graph->n by one and update graph->maxvar.
688 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
690 struct isl_sched_graph
*graph
= user
;
691 int nvar
= isl_set_dim(set
, isl_dim_set
);
694 if (nvar
> graph
->maxvar
)
695 graph
->maxvar
= nvar
;
702 /* Compute the number of rows that should be allocated for the schedule.
703 * In particular, we need one row for each variable or one row
704 * for each basic map in the dependences.
705 * Note that it is practically impossible to exhaust both
706 * the number of dependences and the number of variables.
708 static isl_stat
compute_max_row(struct isl_sched_graph
*graph
,
709 __isl_keep isl_schedule_constraints
*sc
)
713 isl_union_set
*domain
;
717 domain
= isl_schedule_constraints_get_domain(sc
);
718 r
= isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
);
719 isl_union_set_free(domain
);
721 return isl_stat_error
;
722 n_edge
= isl_schedule_constraints_n_basic_map(sc
);
724 return isl_stat_error
;
725 graph
->max_row
= n_edge
+ graph
->maxvar
;
730 /* Does "bset" have any defining equalities for its set variables?
732 static isl_bool
has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
737 return isl_bool_error
;
739 n
= isl_basic_set_dim(bset
, isl_dim_set
);
740 for (i
= 0; i
< n
; ++i
) {
743 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
749 return isl_bool_false
;
752 /* Set the entries of node->max to the value of the schedule_max_coefficient
755 static isl_stat
set_max_coefficient(isl_ctx
*ctx
, struct isl_sched_node
*node
)
759 max
= isl_options_get_schedule_max_coefficient(ctx
);
763 node
->max
= isl_vec_alloc(ctx
, node
->nvar
);
764 node
->max
= isl_vec_set_si(node
->max
, max
);
766 return isl_stat_error
;
771 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
772 * option (if set) and half of the minimum of the sizes in the other
773 * dimensions. Round up when computing the half such that
774 * if the minimum of the sizes is one, half of the size is taken to be one
776 * If the global minimum is unbounded (i.e., if both
777 * the schedule_max_coefficient is not set and the sizes in the other
778 * dimensions are unbounded), then store a negative value.
779 * If the schedule coefficient is close to the size of the instance set
780 * in another dimension, then the schedule may represent a loop
781 * coalescing transformation (especially if the coefficient
782 * in that other dimension is one). Forcing the coefficient to be
783 * smaller than or equal to half the minimal size should avoid this
786 static isl_stat
compute_max_coefficient(isl_ctx
*ctx
,
787 struct isl_sched_node
*node
)
793 max
= isl_options_get_schedule_max_coefficient(ctx
);
794 v
= isl_vec_alloc(ctx
, node
->nvar
);
796 return isl_stat_error
;
798 for (i
= 0; i
< node
->nvar
; ++i
) {
799 isl_int_set_si(v
->el
[i
], max
);
800 isl_int_mul_si(v
->el
[i
], v
->el
[i
], 2);
803 for (i
= 0; i
< node
->nvar
; ++i
) {
806 size
= isl_multi_val_get_val(node
->sizes
, i
);
809 if (!isl_val_is_int(size
)) {
813 for (j
= 0; j
< node
->nvar
; ++j
) {
816 if (isl_int_is_neg(v
->el
[j
]) ||
817 isl_int_gt(v
->el
[j
], size
->n
))
818 isl_int_set(v
->el
[j
], size
->n
);
823 for (i
= 0; i
< node
->nvar
; ++i
)
824 isl_int_cdiv_q_ui(v
->el
[i
], v
->el
[i
], 2);
830 return isl_stat_error
;
833 /* Compute and return the size of "set" in dimension "dim".
834 * The size is taken to be the difference in values for that variable
835 * for fixed values of the other variables.
836 * In particular, the variable is first isolated from the other variables
837 * in the range of a map
839 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
841 * and then duplicated
843 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
845 * The shared variables are then projected out and the maximal value
846 * of i_dim' - i_dim is computed.
848 static __isl_give isl_val
*compute_size(__isl_take isl_set
*set
, int dim
)
855 map
= isl_set_project_onto_map(set
, isl_dim_set
, dim
, 1);
856 map
= isl_map_project_out(map
, isl_dim_in
, dim
, 1);
857 map
= isl_map_range_product(map
, isl_map_copy(map
));
858 map
= isl_set_unwrap(isl_map_range(map
));
859 set
= isl_map_deltas(map
);
860 ls
= isl_local_space_from_space(isl_set_get_space(set
));
861 obj
= isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
862 v
= isl_set_max_val(set
, obj
);
869 /* Compute the size of the instance set "set" of "node", after compression,
870 * as well as bounds on the corresponding coefficients, if needed.
872 * The sizes are needed when the schedule_treat_coalescing option is set.
873 * The bounds are needed when the schedule_treat_coalescing option or
874 * the schedule_max_coefficient option is set.
876 * If the schedule_treat_coalescing option is not set, then at most
877 * the bounds need to be set and this is done in set_max_coefficient.
878 * Otherwise, compress the domain if needed, compute the size
879 * in each direction and store the results in node->size.
880 * Finally, set the bounds on the coefficients based on the sizes
881 * and the schedule_max_coefficient option in compute_max_coefficient.
883 static isl_stat
compute_sizes_and_max(isl_ctx
*ctx
, struct isl_sched_node
*node
,
884 __isl_take isl_set
*set
)
889 if (!isl_options_get_schedule_treat_coalescing(ctx
)) {
891 return set_max_coefficient(ctx
, node
);
894 if (node
->compressed
)
895 set
= isl_set_preimage_multi_aff(set
,
896 isl_multi_aff_copy(node
->decompress
));
897 mv
= isl_multi_val_zero(isl_set_get_space(set
));
898 n
= isl_set_dim(set
, isl_dim_set
);
899 for (j
= 0; j
< n
; ++j
) {
902 v
= compute_size(isl_set_copy(set
), j
);
903 mv
= isl_multi_val_set_val(mv
, j
, v
);
908 return isl_stat_error
;
909 return compute_max_coefficient(ctx
, node
);
912 /* Add a new node to the graph representing the given instance set.
913 * "nvar" is the (possibly compressed) number of variables and
914 * may be smaller than then number of set variables in "set"
915 * if "compressed" is set.
916 * If "compressed" is set, then "hull" represents the constraints
917 * that were used to derive the compression, while "compress" and
918 * "decompress" map the original space to the compressed space and
920 * If "compressed" is not set, then "hull", "compress" and "decompress"
923 * Compute the size of the instance set and bounds on the coefficients,
926 static isl_stat
add_node(struct isl_sched_graph
*graph
,
927 __isl_take isl_set
*set
, int nvar
, int compressed
,
928 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
929 __isl_take isl_multi_aff
*decompress
)
936 struct isl_sched_node
*node
;
939 return isl_stat_error
;
941 ctx
= isl_set_get_ctx(set
);
942 nparam
= isl_set_dim(set
, isl_dim_param
);
943 if (!ctx
->opt
->schedule_parametric
)
945 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
946 node
= &graph
->node
[graph
->n
];
948 space
= isl_set_get_space(set
);
951 node
->nparam
= nparam
;
953 node
->sched_map
= NULL
;
954 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
955 node
->coincident
= coincident
;
956 node
->compressed
= compressed
;
958 node
->compress
= compress
;
959 node
->decompress
= decompress
;
960 if (compute_sizes_and_max(ctx
, node
, set
) < 0)
961 return isl_stat_error
;
963 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
964 return isl_stat_error
;
965 if (compressed
&& (!hull
|| !compress
|| !decompress
))
966 return isl_stat_error
;
971 /* Construct an identifier for node "node", which will represent "set".
972 * The name of the identifier is either "compressed" or
973 * "compressed_<name>", with <name> the name of the space of "set".
974 * The user pointer of the identifier points to "node".
976 static __isl_give isl_id
*construct_compressed_id(__isl_keep isl_set
*set
,
977 struct isl_sched_node
*node
)
986 has_name
= isl_set_has_tuple_name(set
);
990 ctx
= isl_set_get_ctx(set
);
992 return isl_id_alloc(ctx
, "compressed", node
);
994 p
= isl_printer_to_str(ctx
);
995 name
= isl_set_get_tuple_name(set
);
996 p
= isl_printer_print_str(p
, "compressed_");
997 p
= isl_printer_print_str(p
, name
);
998 id_name
= isl_printer_get_str(p
);
1001 id
= isl_id_alloc(ctx
, id_name
, node
);
1007 /* Add a new node to the graph representing the given set.
1009 * If any of the set variables is defined by an equality, then
1010 * we perform variable compression such that we can perform
1011 * the scheduling on the compressed domain.
1012 * In this case, an identifier is used that references the new node
1013 * such that each compressed space is unique and
1014 * such that the node can be recovered from the compressed space.
1016 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1019 isl_bool has_equality
;
1021 isl_basic_set
*hull
;
1024 isl_multi_aff
*compress
, *decompress
;
1025 struct isl_sched_graph
*graph
= user
;
1027 hull
= isl_set_affine_hull(isl_set_copy(set
));
1028 hull
= isl_basic_set_remove_divs(hull
);
1029 nvar
= isl_set_dim(set
, isl_dim_set
);
1030 has_equality
= has_any_defining_equality(hull
);
1032 if (has_equality
< 0)
1034 if (!has_equality
) {
1035 isl_basic_set_free(hull
);
1036 return add_node(graph
, set
, nvar
, 0, NULL
, NULL
, NULL
);
1039 id
= construct_compressed_id(set
, &graph
->node
[graph
->n
]);
1040 morph
= isl_basic_set_variable_compression_with_id(hull
,
1043 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1044 compress
= isl_morph_get_var_multi_aff(morph
);
1045 morph
= isl_morph_inverse(morph
);
1046 decompress
= isl_morph_get_var_multi_aff(morph
);
1047 isl_morph_free(morph
);
1049 hull_set
= isl_set_from_basic_set(hull
);
1050 return add_node(graph
, set
, nvar
, 1, hull_set
, compress
, decompress
);
1052 isl_basic_set_free(hull
);
1054 return isl_stat_error
;
1057 struct isl_extract_edge_data
{
1058 enum isl_edge_type type
;
1059 struct isl_sched_graph
*graph
;
1062 /* Merge edge2 into edge1, freeing the contents of edge2.
1063 * Return 0 on success and -1 on failure.
1065 * edge1 and edge2 are assumed to have the same value for the map field.
1067 static int merge_edge(struct isl_sched_edge
*edge1
,
1068 struct isl_sched_edge
*edge2
)
1070 edge1
->types
|= edge2
->types
;
1071 isl_map_free(edge2
->map
);
1073 if (is_condition(edge2
)) {
1074 if (!edge1
->tagged_condition
)
1075 edge1
->tagged_condition
= edge2
->tagged_condition
;
1077 edge1
->tagged_condition
=
1078 isl_union_map_union(edge1
->tagged_condition
,
1079 edge2
->tagged_condition
);
1082 if (is_conditional_validity(edge2
)) {
1083 if (!edge1
->tagged_validity
)
1084 edge1
->tagged_validity
= edge2
->tagged_validity
;
1086 edge1
->tagged_validity
=
1087 isl_union_map_union(edge1
->tagged_validity
,
1088 edge2
->tagged_validity
);
1091 if (is_condition(edge2
) && !edge1
->tagged_condition
)
1093 if (is_conditional_validity(edge2
) && !edge1
->tagged_validity
)
1099 /* Insert dummy tags in domain and range of "map".
1101 * In particular, if "map" is of the form
1107 * [A -> dummy_tag] -> [B -> dummy_tag]
1109 * where the dummy_tags are identical and equal to any dummy tags
1110 * introduced by any other call to this function.
1112 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1118 isl_set
*domain
, *range
;
1120 ctx
= isl_map_get_ctx(map
);
1122 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1123 space
= isl_space_params(isl_map_get_space(map
));
1124 space
= isl_space_set_from_params(space
);
1125 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1126 space
= isl_space_map_from_set(space
);
1128 domain
= isl_map_wrap(map
);
1129 range
= isl_map_wrap(isl_map_universe(space
));
1130 map
= isl_map_from_domain_and_range(domain
, range
);
1131 map
= isl_map_zip(map
);
1136 /* Given that at least one of "src" or "dst" is compressed, return
1137 * a map between the spaces of these nodes restricted to the affine
1138 * hull that was used in the compression.
1140 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1141 struct isl_sched_node
*dst
)
1145 if (src
->compressed
)
1146 dom
= isl_set_copy(src
->hull
);
1148 dom
= isl_set_universe(isl_space_copy(src
->space
));
1149 if (dst
->compressed
)
1150 ran
= isl_set_copy(dst
->hull
);
1152 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1154 return isl_map_from_domain_and_range(dom
, ran
);
1157 /* Intersect the domains of the nested relations in domain and range
1158 * of "tagged" with "map".
1160 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1161 __isl_keep isl_map
*map
)
1165 tagged
= isl_map_zip(tagged
);
1166 set
= isl_map_wrap(isl_map_copy(map
));
1167 tagged
= isl_map_intersect_domain(tagged
, set
);
1168 tagged
= isl_map_zip(tagged
);
1172 /* Return a pointer to the node that lives in the domain space of "map"
1173 * or NULL if there is no such node.
1175 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1176 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1178 struct isl_sched_node
*node
;
1181 space
= isl_space_domain(isl_map_get_space(map
));
1182 node
= graph_find_node(ctx
, graph
, space
);
1183 isl_space_free(space
);
1188 /* Return a pointer to the node that lives in the range space of "map"
1189 * or NULL if there is no such node.
1191 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1192 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1194 struct isl_sched_node
*node
;
1197 space
= isl_space_range(isl_map_get_space(map
));
1198 node
= graph_find_node(ctx
, graph
, space
);
1199 isl_space_free(space
);
1204 /* Add a new edge to the graph based on the given map
1205 * and add it to data->graph->edge_table[data->type].
1206 * If a dependence relation of a given type happens to be identical
1207 * to one of the dependence relations of a type that was added before,
1208 * then we don't create a new edge, but instead mark the original edge
1209 * as also representing a dependence of the current type.
1211 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1212 * may be specified as "tagged" dependence relations. That is, "map"
1213 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1214 * the dependence on iterations and a and b are tags.
1215 * edge->map is set to the relation containing the elements i -> j,
1216 * while edge->tagged_condition and edge->tagged_validity contain
1217 * the union of all the "map" relations
1218 * for which extract_edge is called that result in the same edge->map.
1220 * If the source or the destination node is compressed, then
1221 * intersect both "map" and "tagged" with the constraints that
1222 * were used to construct the compression.
1223 * This ensures that there are no schedule constraints defined
1224 * outside of these domains, while the scheduler no longer has
1225 * any control over those outside parts.
1227 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1229 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1230 struct isl_extract_edge_data
*data
= user
;
1231 struct isl_sched_graph
*graph
= data
->graph
;
1232 struct isl_sched_node
*src
, *dst
;
1233 struct isl_sched_edge
*edge
;
1234 isl_map
*tagged
= NULL
;
1236 if (data
->type
== isl_edge_condition
||
1237 data
->type
== isl_edge_conditional_validity
) {
1238 if (isl_map_can_zip(map
)) {
1239 tagged
= isl_map_copy(map
);
1240 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1242 tagged
= insert_dummy_tags(isl_map_copy(map
));
1246 src
= find_domain_node(ctx
, graph
, map
);
1247 dst
= find_range_node(ctx
, graph
, map
);
1251 isl_map_free(tagged
);
1255 if (src
->compressed
|| dst
->compressed
) {
1257 hull
= extract_hull(src
, dst
);
1259 tagged
= map_intersect_domains(tagged
, hull
);
1260 map
= isl_map_intersect(map
, hull
);
1263 graph
->edge
[graph
->n_edge
].src
= src
;
1264 graph
->edge
[graph
->n_edge
].dst
= dst
;
1265 graph
->edge
[graph
->n_edge
].map
= map
;
1266 graph
->edge
[graph
->n_edge
].types
= 0;
1267 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1268 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1269 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1270 if (data
->type
== isl_edge_condition
)
1271 graph
->edge
[graph
->n_edge
].tagged_condition
=
1272 isl_union_map_from_map(tagged
);
1273 if (data
->type
== isl_edge_conditional_validity
)
1274 graph
->edge
[graph
->n_edge
].tagged_validity
=
1275 isl_union_map_from_map(tagged
);
1277 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1280 return isl_stat_error
;
1282 if (edge
== &graph
->edge
[graph
->n_edge
])
1283 return graph_edge_table_add(ctx
, graph
, data
->type
,
1284 &graph
->edge
[graph
->n_edge
++]);
1286 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1289 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1292 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1294 * The context is included in the domain before the nodes of
1295 * the graphs are extracted in order to be able to exploit
1296 * any possible additional equalities.
1297 * Note that this intersection is only performed locally here.
1299 static isl_stat
graph_init(struct isl_sched_graph
*graph
,
1300 __isl_keep isl_schedule_constraints
*sc
)
1303 isl_union_set
*domain
;
1305 struct isl_extract_edge_data data
;
1306 enum isl_edge_type i
;
1310 return isl_stat_error
;
1312 ctx
= isl_schedule_constraints_get_ctx(sc
);
1314 domain
= isl_schedule_constraints_get_domain(sc
);
1315 graph
->n
= isl_union_set_n_set(domain
);
1316 isl_union_set_free(domain
);
1318 if (graph_alloc(ctx
, graph
, graph
->n
,
1319 isl_schedule_constraints_n_map(sc
)) < 0)
1320 return isl_stat_error
;
1322 if (compute_max_row(graph
, sc
) < 0)
1323 return isl_stat_error
;
1326 domain
= isl_schedule_constraints_get_domain(sc
);
1327 domain
= isl_union_set_intersect_params(domain
,
1328 isl_schedule_constraints_get_context(sc
));
1329 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1330 isl_union_set_free(domain
);
1332 return isl_stat_error
;
1333 if (graph_init_table(ctx
, graph
) < 0)
1334 return isl_stat_error
;
1335 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1336 c
= isl_schedule_constraints_get(sc
, i
);
1337 graph
->max_edge
[i
] = isl_union_map_n_map(c
);
1338 isl_union_map_free(c
);
1340 return isl_stat_error
;
1342 if (graph_init_edge_tables(ctx
, graph
) < 0)
1343 return isl_stat_error
;
1346 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1350 c
= isl_schedule_constraints_get(sc
, i
);
1351 r
= isl_union_map_foreach_map(c
, &extract_edge
, &data
);
1352 isl_union_map_free(c
);
1354 return isl_stat_error
;
1360 /* Check whether there is any dependence from node[j] to node[i]
1361 * or from node[i] to node[j].
1363 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1366 struct isl_sched_graph
*graph
= user
;
1368 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1371 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1374 /* Check whether there is a (conditional) validity dependence from node[j]
1375 * to node[i], forcing node[i] to follow node[j].
1377 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1379 struct isl_sched_graph
*graph
= user
;
1381 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1384 /* Use Tarjan's algorithm for computing the strongly connected components
1385 * in the dependence graph only considering those edges defined by "follows".
1387 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1388 isl_bool (*follows
)(int i
, int j
, void *user
))
1391 struct isl_tarjan_graph
*g
= NULL
;
1393 g
= isl_tarjan_graph_init(ctx
, graph
->n
, follows
, graph
);
1401 while (g
->order
[i
] != -1) {
1402 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1410 isl_tarjan_graph_free(g
);
1415 /* Apply Tarjan's algorithm to detect the strongly connected components
1416 * in the dependence graph.
1417 * Only consider the (conditional) validity dependences and clear "weak".
1419 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1422 return detect_ccs(ctx
, graph
, &node_follows_strong
);
1425 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1426 * in the dependence graph.
1427 * Consider all dependences and set "weak".
1429 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1432 return detect_ccs(ctx
, graph
, &node_follows_weak
);
1435 static int cmp_scc(const void *a
, const void *b
, void *data
)
1437 struct isl_sched_graph
*graph
= data
;
1441 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1444 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1446 static int sort_sccs(struct isl_sched_graph
*graph
)
1448 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1451 /* Return a non-parametric set in the compressed space of "node" that is
1452 * bounded by the size in each direction
1454 * { [x] : -S_i <= x_i <= S_i }
1456 * If S_i is infinity in direction i, then there are no constraints
1457 * in that direction.
1459 * Cache the result in node->bounds.
1461 static __isl_give isl_basic_set
*get_size_bounds(struct isl_sched_node
*node
)
1464 isl_basic_set
*bounds
;
1469 return isl_basic_set_copy(node
->bounds
);
1471 if (node
->compressed
)
1472 space
= isl_multi_aff_get_domain_space(node
->decompress
);
1474 space
= isl_space_copy(node
->space
);
1475 nparam
= isl_space_dim(space
, isl_dim_param
);
1476 space
= isl_space_drop_dims(space
, isl_dim_param
, 0, nparam
);
1477 bounds
= isl_basic_set_universe(space
);
1479 for (i
= 0; i
< node
->nvar
; ++i
) {
1482 size
= isl_multi_val_get_val(node
->sizes
, i
);
1484 return isl_basic_set_free(bounds
);
1485 if (!isl_val_is_int(size
)) {
1489 bounds
= isl_basic_set_upper_bound_val(bounds
, isl_dim_set
, i
,
1490 isl_val_copy(size
));
1491 bounds
= isl_basic_set_lower_bound_val(bounds
, isl_dim_set
, i
,
1495 node
->bounds
= isl_basic_set_copy(bounds
);
1499 /* Drop some constraints from "delta" that could be exploited
1500 * to construct loop coalescing schedules.
1501 * In particular, drop those constraint that bound the difference
1502 * to the size of the domain.
1503 * First project out the parameters to improve the effectiveness.
1505 static __isl_give isl_set
*drop_coalescing_constraints(
1506 __isl_take isl_set
*delta
, struct isl_sched_node
*node
)
1509 isl_basic_set
*bounds
;
1511 bounds
= get_size_bounds(node
);
1513 nparam
= isl_set_dim(delta
, isl_dim_param
);
1514 delta
= isl_set_project_out(delta
, isl_dim_param
, 0, nparam
);
1515 delta
= isl_set_remove_divs(delta
);
1516 delta
= isl_set_plain_gist_basic_set(delta
, bounds
);
1520 /* Given a dependence relation R from "node" to itself,
1521 * construct the set of coefficients of valid constraints for elements
1522 * in that dependence relation.
1523 * In particular, the result contains tuples of coefficients
1524 * c_0, c_n, c_x such that
1526 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1530 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1532 * We choose here to compute the dual of delta R.
1533 * Alternatively, we could have computed the dual of R, resulting
1534 * in a set of tuples c_0, c_n, c_x, c_y, and then
1535 * plugged in (c_0, c_n, c_x, -c_x).
1537 * If "need_param" is set, then the resulting coefficients effectively
1538 * include coefficients for the parameters c_n. Otherwise, they may
1539 * have been projected out already.
1540 * Since the constraints may be different for these two cases,
1541 * they are stored in separate caches.
1542 * In particular, if no parameter coefficients are required and
1543 * the schedule_treat_coalescing option is set, then the parameters
1544 * are projected out and some constraints that could be exploited
1545 * to construct coalescing schedules are removed before the dual
1548 * If "node" has been compressed, then the dependence relation
1549 * is also compressed before the set of coefficients is computed.
1551 static __isl_give isl_basic_set
*intra_coefficients(
1552 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1553 __isl_take isl_map
*map
, int need_param
)
1558 isl_basic_set
*coef
;
1559 isl_maybe_isl_basic_set m
;
1560 isl_map_to_basic_set
**hmap
= &graph
->intra_hmap
;
1566 ctx
= isl_map_get_ctx(map
);
1567 treat
= !need_param
&& isl_options_get_schedule_treat_coalescing(ctx
);
1569 hmap
= &graph
->intra_hmap_param
;
1570 m
= isl_map_to_basic_set_try_get(*hmap
, map
);
1571 if (m
.valid
< 0 || m
.valid
) {
1576 key
= isl_map_copy(map
);
1577 if (node
->compressed
) {
1578 map
= isl_map_preimage_domain_multi_aff(map
,
1579 isl_multi_aff_copy(node
->decompress
));
1580 map
= isl_map_preimage_range_multi_aff(map
,
1581 isl_multi_aff_copy(node
->decompress
));
1583 delta
= isl_map_deltas(map
);
1585 delta
= drop_coalescing_constraints(delta
, node
);
1586 delta
= isl_set_remove_divs(delta
);
1587 coef
= isl_set_coefficients(delta
);
1588 *hmap
= isl_map_to_basic_set_set(*hmap
, key
, isl_basic_set_copy(coef
));
1593 /* Given a dependence relation R, construct the set of coefficients
1594 * of valid constraints for elements in that dependence relation.
1595 * In particular, the result contains tuples of coefficients
1596 * c_0, c_n, c_x, c_y such that
1598 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1600 * If the source or destination nodes of "edge" have been compressed,
1601 * then the dependence relation is also compressed before
1602 * the set of coefficients is computed.
1604 static __isl_give isl_basic_set
*inter_coefficients(
1605 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1606 __isl_take isl_map
*map
)
1610 isl_basic_set
*coef
;
1611 isl_maybe_isl_basic_set m
;
1613 m
= isl_map_to_basic_set_try_get(graph
->inter_hmap
, map
);
1614 if (m
.valid
< 0 || m
.valid
) {
1619 key
= isl_map_copy(map
);
1620 if (edge
->src
->compressed
)
1621 map
= isl_map_preimage_domain_multi_aff(map
,
1622 isl_multi_aff_copy(edge
->src
->decompress
));
1623 if (edge
->dst
->compressed
)
1624 map
= isl_map_preimage_range_multi_aff(map
,
1625 isl_multi_aff_copy(edge
->dst
->decompress
));
1626 set
= isl_map_wrap(isl_map_remove_divs(map
));
1627 coef
= isl_set_coefficients(set
);
1628 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1629 isl_basic_set_copy(coef
));
1634 /* Return the position of the coefficients of the variables in
1635 * the coefficients constraints "coef".
1637 * The space of "coef" is of the form
1639 * { coefficients[[cst, params] -> S] }
1641 * Return the position of S.
1643 static int coef_var_offset(__isl_keep isl_basic_set
*coef
)
1648 space
= isl_space_unwrap(isl_basic_set_get_space(coef
));
1649 offset
= isl_space_dim(space
, isl_dim_in
);
1650 isl_space_free(space
);
1655 /* Return the offset of the coefficient of the constant term of "node"
1658 * Within each node, the coefficients have the following order:
1659 * - positive and negative parts of c_i_x
1660 * - c_i_n (if parametric)
1663 static int node_cst_coef_offset(struct isl_sched_node
*node
)
1665 return node
->start
+ 2 * node
->nvar
+ node
->nparam
;
1668 /* Return the offset of the coefficients of the parameters of "node"
1671 * Within each node, the coefficients have the following order:
1672 * - positive and negative parts of c_i_x
1673 * - c_i_n (if parametric)
1676 static int node_par_coef_offset(struct isl_sched_node
*node
)
1678 return node
->start
+ 2 * node
->nvar
;
1681 /* Return the offset of the coefficients of the variables of "node"
1684 * Within each node, the coefficients have the following order:
1685 * - positive and negative parts of c_i_x
1686 * - c_i_n (if parametric)
1689 static int node_var_coef_offset(struct isl_sched_node
*node
)
1694 /* Return the position of the pair of variables encoding
1695 * coefficient "i" of "node".
1697 * The order of these variable pairs is the opposite of
1698 * that of the coefficients, with 2 variables per coefficient.
1700 static int node_var_coef_pos(struct isl_sched_node
*node
, int i
)
1702 return node_var_coef_offset(node
) + 2 * (node
->nvar
- 1 - i
);
1705 /* Construct an isl_dim_map for mapping constraints on coefficients
1706 * for "node" to the corresponding positions in graph->lp.
1707 * "offset" is the offset of the coefficients for the variables
1708 * in the input constraints.
1709 * "s" is the sign of the mapping.
1711 * The input constraints are given in terms of the coefficients
1712 * (c_0, c_x) or (c_0, c_n, c_x).
1713 * The mapping produced by this function essentially plugs in
1714 * (0, c_i_x^+ - c_i_x^-) if s = 1 and
1715 * (0, -c_i_x^+ + c_i_x^-) if s = -1 or
1716 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1717 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1718 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1719 * Furthermore, the order of these pairs is the opposite of that
1720 * of the corresponding coefficients.
1722 * The caller can extend the mapping to also map the other coefficients
1723 * (and therefore not plug in 0).
1725 static __isl_give isl_dim_map
*intra_dim_map(isl_ctx
*ctx
,
1726 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1731 isl_dim_map
*dim_map
;
1736 total
= isl_basic_set_total_dim(graph
->lp
);
1737 pos
= node_var_coef_pos(node
, 0);
1738 dim_map
= isl_dim_map_alloc(ctx
, total
);
1739 isl_dim_map_range(dim_map
, pos
, -2, offset
, 1, node
->nvar
, -s
);
1740 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
, 1, node
->nvar
, s
);
1745 /* Construct an isl_dim_map for mapping constraints on coefficients
1746 * for "src" (node i) and "dst" (node j) to the corresponding positions
1748 * "offset" is the offset of the coefficients for the variables of "src"
1749 * in the input constraints.
1750 * "s" is the sign of the mapping.
1752 * The input constraints are given in terms of the coefficients
1753 * (c_0, c_n, c_x, c_y).
1754 * The mapping produced by this function essentially plugs in
1755 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1756 * -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-) if s = 1 and
1757 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1758 * c_i_x^+ - c_i_x^-, -(c_j_x^+ - c_j_x^-)) if s = -1.
1759 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1760 * Furthermore, the order of these pairs is the opposite of that
1761 * of the corresponding coefficients.
1763 * The caller can further extend the mapping.
1765 static __isl_give isl_dim_map
*inter_dim_map(isl_ctx
*ctx
,
1766 struct isl_sched_graph
*graph
, struct isl_sched_node
*src
,
1767 struct isl_sched_node
*dst
, int offset
, int s
)
1771 isl_dim_map
*dim_map
;
1776 total
= isl_basic_set_total_dim(graph
->lp
);
1777 dim_map
= isl_dim_map_alloc(ctx
, total
);
1779 pos
= node_cst_coef_offset(dst
);
1780 isl_dim_map_range(dim_map
, pos
, 0, 0, 0, 1, s
);
1781 pos
= node_par_coef_offset(dst
);
1782 isl_dim_map_range(dim_map
, pos
, 1, 1, 1, dst
->nparam
, s
);
1783 pos
= node_var_coef_pos(dst
, 0);
1784 isl_dim_map_range(dim_map
, pos
, -2, offset
+ src
->nvar
, 1,
1786 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
+ src
->nvar
, 1,
1789 pos
= node_cst_coef_offset(src
);
1790 isl_dim_map_range(dim_map
, pos
, 0, 0, 0, 1, -s
);
1791 pos
= node_par_coef_offset(src
);
1792 isl_dim_map_range(dim_map
, pos
, 1, 1, 1, src
->nparam
, -s
);
1793 pos
= node_var_coef_pos(src
, 0);
1794 isl_dim_map_range(dim_map
, pos
, -2, offset
, 1, src
->nvar
, s
);
1795 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
, 1, src
->nvar
, -s
);
1800 /* Add the constraints from "src" to "dst" using "dim_map",
1801 * after making sure there is enough room in "dst" for the extra constraints.
1803 static __isl_give isl_basic_set
*add_constraints_dim_map(
1804 __isl_take isl_basic_set
*dst
, __isl_take isl_basic_set
*src
,
1805 __isl_take isl_dim_map
*dim_map
)
1809 n_eq
= isl_basic_set_n_equality(src
);
1810 n_ineq
= isl_basic_set_n_inequality(src
);
1811 dst
= isl_basic_set_extend_constraints(dst
, n_eq
, n_ineq
);
1812 dst
= isl_basic_set_add_constraints_dim_map(dst
, src
, dim_map
);
1816 /* Add constraints to graph->lp that force validity for the given
1817 * dependence from a node i to itself.
1818 * That is, add constraints that enforce
1820 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1821 * = c_i_x (y - x) >= 0
1823 * for each (x,y) in R.
1824 * We obtain general constraints on coefficients (c_0, c_x)
1825 * of valid constraints for (y - x) and then plug in (0, c_i_x^+ - c_i_x^-),
1826 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1827 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1828 * Note that the result of intra_coefficients may also contain
1829 * parameter coefficients c_n, in which case 0 is plugged in for them as well.
1831 static isl_stat
add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1832 struct isl_sched_edge
*edge
)
1835 isl_map
*map
= isl_map_copy(edge
->map
);
1836 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1837 isl_dim_map
*dim_map
;
1838 isl_basic_set
*coef
;
1839 struct isl_sched_node
*node
= edge
->src
;
1841 coef
= intra_coefficients(graph
, node
, map
, 0);
1843 offset
= coef_var_offset(coef
);
1846 return isl_stat_error
;
1848 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
1849 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1854 /* Add constraints to graph->lp that force validity for the given
1855 * dependence from node i to node j.
1856 * That is, add constraints that enforce
1858 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1860 * for each (x,y) in R.
1861 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1862 * of valid constraints for R and then plug in
1863 * (c_j_0 - c_i_0, c_j_n - c_i_n, -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-),
1864 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1865 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1867 static isl_stat
add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1868 struct isl_sched_edge
*edge
)
1873 isl_dim_map
*dim_map
;
1874 isl_basic_set
*coef
;
1875 struct isl_sched_node
*src
= edge
->src
;
1876 struct isl_sched_node
*dst
= edge
->dst
;
1879 return isl_stat_error
;
1881 map
= isl_map_copy(edge
->map
);
1882 ctx
= isl_map_get_ctx(map
);
1883 coef
= inter_coefficients(graph
, edge
, map
);
1885 offset
= coef_var_offset(coef
);
1888 return isl_stat_error
;
1890 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
1892 edge
->start
= graph
->lp
->n_ineq
;
1893 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1895 return isl_stat_error
;
1896 edge
->end
= graph
->lp
->n_ineq
;
1901 /* Add constraints to graph->lp that bound the dependence distance for the given
1902 * dependence from a node i to itself.
1903 * If s = 1, we add the constraint
1905 * c_i_x (y - x) <= m_0 + m_n n
1909 * -c_i_x (y - x) + m_0 + m_n n >= 0
1911 * for each (x,y) in R.
1912 * If s = -1, we add the constraint
1914 * -c_i_x (y - x) <= m_0 + m_n n
1918 * c_i_x (y - x) + m_0 + m_n n >= 0
1920 * for each (x,y) in R.
1921 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1922 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1923 * with each coefficient (except m_0) represented as a pair of non-negative
1927 * If "local" is set, then we add constraints
1929 * c_i_x (y - x) <= 0
1933 * -c_i_x (y - x) <= 0
1935 * instead, forcing the dependence distance to be (less than or) equal to 0.
1936 * That is, we plug in (0, 0, -s * c_i_x),
1937 * intra_coefficients is not required to have c_n in its result when
1938 * "local" is set. If they are missing, then (0, -s * c_i_x) is plugged in.
1939 * Note that dependences marked local are treated as validity constraints
1940 * by add_all_validity_constraints and therefore also have
1941 * their distances bounded by 0 from below.
1943 static isl_stat
add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1944 struct isl_sched_edge
*edge
, int s
, int local
)
1948 isl_map
*map
= isl_map_copy(edge
->map
);
1949 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1950 isl_dim_map
*dim_map
;
1951 isl_basic_set
*coef
;
1952 struct isl_sched_node
*node
= edge
->src
;
1954 coef
= intra_coefficients(graph
, node
, map
, !local
);
1956 offset
= coef_var_offset(coef
);
1959 return isl_stat_error
;
1961 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1962 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, -s
);
1965 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1966 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1967 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1969 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1974 /* Add constraints to graph->lp that bound the dependence distance for the given
1975 * dependence from node i to node j.
1976 * If s = 1, we add the constraint
1978 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1983 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1986 * for each (x,y) in R.
1987 * If s = -1, we add the constraint
1989 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1994 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1997 * for each (x,y) in R.
1998 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1999 * of valid constraints for R and then plug in
2000 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
2001 * s*c_i_x, -s*c_j_x)
2002 * with each coefficient (except m_0, c_*_0 and c_*_n)
2003 * represented as a pair of non-negative coefficients.
2006 * If "local" is set (and s = 1), then we add constraints
2008 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
2012 * -((c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x)) >= 0
2014 * instead, forcing the dependence distance to be (less than or) equal to 0.
2015 * That is, we plug in
2016 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, s*c_i_x, -s*c_j_x).
2017 * Note that dependences marked local are treated as validity constraints
2018 * by add_all_validity_constraints and therefore also have
2019 * their distances bounded by 0 from below.
2021 static isl_stat
add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
2022 struct isl_sched_edge
*edge
, int s
, int local
)
2026 isl_map
*map
= isl_map_copy(edge
->map
);
2027 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2028 isl_dim_map
*dim_map
;
2029 isl_basic_set
*coef
;
2030 struct isl_sched_node
*src
= edge
->src
;
2031 struct isl_sched_node
*dst
= edge
->dst
;
2033 coef
= inter_coefficients(graph
, edge
, map
);
2035 offset
= coef_var_offset(coef
);
2038 return isl_stat_error
;
2040 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
2041 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, -s
);
2044 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
2045 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
2046 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
2049 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
2054 /* Should the distance over "edge" be forced to zero?
2055 * That is, is it marked as a local edge?
2056 * If "use_coincidence" is set, then coincidence edges are treated
2059 static int force_zero(struct isl_sched_edge
*edge
, int use_coincidence
)
2061 return is_local(edge
) || (use_coincidence
&& is_coincidence(edge
));
2064 /* Add all validity constraints to graph->lp.
2066 * An edge that is forced to be local needs to have its dependence
2067 * distances equal to zero. We take care of bounding them by 0 from below
2068 * here. add_all_proximity_constraints takes care of bounding them by 0
2071 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2072 * Otherwise, we ignore them.
2074 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
2075 int use_coincidence
)
2079 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2080 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2083 zero
= force_zero(edge
, use_coincidence
);
2084 if (!is_validity(edge
) && !zero
)
2086 if (edge
->src
!= edge
->dst
)
2088 if (add_intra_validity_constraints(graph
, edge
) < 0)
2092 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2093 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2096 zero
= force_zero(edge
, use_coincidence
);
2097 if (!is_validity(edge
) && !zero
)
2099 if (edge
->src
== edge
->dst
)
2101 if (add_inter_validity_constraints(graph
, edge
) < 0)
2108 /* Add constraints to graph->lp that bound the dependence distance
2109 * for all dependence relations.
2110 * If a given proximity dependence is identical to a validity
2111 * dependence, then the dependence distance is already bounded
2112 * from below (by zero), so we only need to bound the distance
2113 * from above. (This includes the case of "local" dependences
2114 * which are treated as validity dependence by add_all_validity_constraints.)
2115 * Otherwise, we need to bound the distance both from above and from below.
2117 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2118 * Otherwise, we ignore them.
2120 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
2121 int use_coincidence
)
2125 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2126 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2129 zero
= force_zero(edge
, use_coincidence
);
2130 if (!is_proximity(edge
) && !zero
)
2132 if (edge
->src
== edge
->dst
&&
2133 add_intra_proximity_constraints(graph
, edge
, 1, zero
) < 0)
2135 if (edge
->src
!= edge
->dst
&&
2136 add_inter_proximity_constraints(graph
, edge
, 1, zero
) < 0)
2138 if (is_validity(edge
) || zero
)
2140 if (edge
->src
== edge
->dst
&&
2141 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2143 if (edge
->src
!= edge
->dst
&&
2144 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2151 /* Normalize the rows of "indep" such that all rows are lexicographically
2152 * positive and such that each row contains as many final zeros as possible,
2153 * given the choice for the previous rows.
2154 * Do this by performing elementary row operations.
2156 static __isl_give isl_mat
*normalize_independent(__isl_take isl_mat
*indep
)
2158 indep
= isl_mat_reverse_gauss(indep
);
2159 indep
= isl_mat_lexnonneg_rows(indep
);
2163 /* Compute a basis for the rows in the linear part of the schedule
2164 * and extend this basis to a full basis. The remaining rows
2165 * can then be used to force linear independence from the rows
2168 * In particular, given the schedule rows S, we compute
2173 * with H the Hermite normal form of S. That is, all but the
2174 * first rank columns of H are zero and so each row in S is
2175 * a linear combination of the first rank rows of Q.
2176 * The matrix Q can be used as a variable transformation
2177 * that isolates the directions of S in the first rank rows.
2178 * Transposing S U = H yields
2182 * with all but the first rank rows of H^T zero.
2183 * The last rows of U^T are therefore linear combinations
2184 * of schedule coefficients that are all zero on schedule
2185 * coefficients that are linearly dependent on the rows of S.
2186 * At least one of these combinations is non-zero on
2187 * linearly independent schedule coefficients.
2188 * The rows are normalized to involve as few of the last
2189 * coefficients as possible and to have a positive initial value.
2191 static int node_update_vmap(struct isl_sched_node
*node
)
2194 int n_row
= isl_mat_rows(node
->sched
);
2196 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2197 1 + node
->nparam
, node
->nvar
);
2199 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2200 isl_mat_free(node
->indep
);
2201 isl_mat_free(node
->vmap
);
2203 node
->indep
= isl_mat_transpose(U
);
2204 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2205 node
->indep
= isl_mat_drop_rows(node
->indep
, 0, node
->rank
);
2206 node
->indep
= normalize_independent(node
->indep
);
2209 if (!node
->indep
|| !node
->vmap
|| node
->rank
< 0)
2214 /* Is "edge" marked as a validity or a conditional validity edge?
2216 static int is_any_validity(struct isl_sched_edge
*edge
)
2218 return is_validity(edge
) || is_conditional_validity(edge
);
2221 /* How many times should we count the constraints in "edge"?
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 an edge is only marked conditional_validity then it counts
2230 * as zero since it is only checked afterwards.
2232 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2233 * Otherwise, we ignore them.
2235 static int edge_multiplicity(struct isl_sched_edge
*edge
, int use_coincidence
)
2237 if (is_proximity(edge
) || force_zero(edge
, use_coincidence
))
2239 if (is_validity(edge
))
2244 /* How many times should the constraints in "edge" be counted
2245 * as a parametric intra-node constraint?
2247 * Only proximity edges that are not forced zero need
2248 * coefficient constraints that include coefficients for parameters.
2249 * If the edge is also a validity edge, then only
2250 * an upper bound is introduced. Otherwise, both lower and upper bounds
2253 static int parametric_intra_edge_multiplicity(struct isl_sched_edge
*edge
,
2254 int use_coincidence
)
2256 if (edge
->src
!= edge
->dst
)
2258 if (!is_proximity(edge
))
2260 if (force_zero(edge
, use_coincidence
))
2262 if (is_validity(edge
))
2268 /* Add "f" times the number of equality and inequality constraints of "bset"
2269 * to "n_eq" and "n_ineq" and free "bset".
2271 static isl_stat
update_count(__isl_take isl_basic_set
*bset
,
2272 int f
, int *n_eq
, int *n_ineq
)
2275 return isl_stat_error
;
2277 *n_eq
+= isl_basic_set_n_equality(bset
);
2278 *n_ineq
+= isl_basic_set_n_inequality(bset
);
2279 isl_basic_set_free(bset
);
2284 /* Count the number of equality and inequality constraints
2285 * that will be added for the given map.
2287 * The edges that require parameter coefficients are counted separately.
2289 * "use_coincidence" is set if we should take into account coincidence edges.
2291 static isl_stat
count_map_constraints(struct isl_sched_graph
*graph
,
2292 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2293 int *n_eq
, int *n_ineq
, int use_coincidence
)
2296 isl_basic_set
*coef
;
2297 int f
= edge_multiplicity(edge
, use_coincidence
);
2298 int fp
= parametric_intra_edge_multiplicity(edge
, use_coincidence
);
2305 if (edge
->src
!= edge
->dst
) {
2306 coef
= inter_coefficients(graph
, edge
, map
);
2307 return update_count(coef
, f
, n_eq
, n_ineq
);
2311 copy
= isl_map_copy(map
);
2312 coef
= intra_coefficients(graph
, edge
->src
, copy
, 1);
2313 if (update_count(coef
, fp
, n_eq
, n_ineq
) < 0)
2318 copy
= isl_map_copy(map
);
2319 coef
= intra_coefficients(graph
, edge
->src
, copy
, 0);
2320 if (update_count(coef
, f
- fp
, n_eq
, n_ineq
) < 0)
2328 return isl_stat_error
;
2331 /* Count the number of equality and inequality constraints
2332 * that will be added to the main lp problem.
2333 * We count as follows
2334 * validity -> 1 (>= 0)
2335 * validity+proximity -> 2 (>= 0 and upper bound)
2336 * proximity -> 2 (lower and upper bound)
2337 * local(+any) -> 2 (>= 0 and <= 0)
2339 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2340 * Otherwise, we ignore them.
2342 static int count_constraints(struct isl_sched_graph
*graph
,
2343 int *n_eq
, int *n_ineq
, int use_coincidence
)
2347 *n_eq
= *n_ineq
= 0;
2348 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2349 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2350 isl_map
*map
= isl_map_copy(edge
->map
);
2352 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2353 use_coincidence
) < 0)
2360 /* Count the number of constraints that will be added by
2361 * add_bound_constant_constraints to bound the values of the constant terms
2362 * and increment *n_eq and *n_ineq accordingly.
2364 * In practice, add_bound_constant_constraints only adds inequalities.
2366 static isl_stat
count_bound_constant_constraints(isl_ctx
*ctx
,
2367 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2369 if (isl_options_get_schedule_max_constant_term(ctx
) == -1)
2372 *n_ineq
+= graph
->n
;
2377 /* Add constraints to bound the values of the constant terms in the schedule,
2378 * if requested by the user.
2380 * The maximal value of the constant terms is defined by the option
2381 * "schedule_max_constant_term".
2383 static isl_stat
add_bound_constant_constraints(isl_ctx
*ctx
,
2384 struct isl_sched_graph
*graph
)
2390 max
= isl_options_get_schedule_max_constant_term(ctx
);
2394 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2396 for (i
= 0; i
< graph
->n
; ++i
) {
2397 struct isl_sched_node
*node
= &graph
->node
[i
];
2400 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2402 return isl_stat_error
;
2403 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2404 pos
= node_cst_coef_offset(node
);
2405 isl_int_set_si(graph
->lp
->ineq
[k
][1 + pos
], -1);
2406 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2412 /* Count the number of constraints that will be added by
2413 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2416 * In practice, add_bound_coefficient_constraints only adds inequalities.
2418 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2419 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2423 if (isl_options_get_schedule_max_coefficient(ctx
) == -1 &&
2424 !isl_options_get_schedule_treat_coalescing(ctx
))
2427 for (i
= 0; i
< graph
->n
; ++i
)
2428 *n_ineq
+= graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2433 /* Add constraints to graph->lp that bound the values of
2434 * the parameter schedule coefficients of "node" to "max" and
2435 * the variable schedule coefficients to the corresponding entry
2437 * In either case, a negative value means that no bound needs to be imposed.
2439 * For parameter coefficients, this amounts to adding a constraint
2447 * The variables coefficients are, however, not represented directly.
2448 * Instead, the variable coefficients c_x are written as differences
2449 * c_x = c_x^+ - c_x^-.
2452 * -max_i <= c_x_i <= max_i
2456 * -max_i <= c_x_i^+ - c_x_i^- <= max_i
2460 * -(c_x_i^+ - c_x_i^-) + max_i >= 0
2461 * c_x_i^+ - c_x_i^- + max_i >= 0
2463 static isl_stat
node_add_coefficient_constraints(isl_ctx
*ctx
,
2464 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
, int max
)
2470 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2472 for (j
= 0; j
< node
->nparam
; ++j
) {
2478 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2480 return isl_stat_error
;
2481 dim
= 1 + node_par_coef_offset(node
) + j
;
2482 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2483 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2484 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2487 ineq
= isl_vec_alloc(ctx
, 1 + total
);
2488 ineq
= isl_vec_clr(ineq
);
2490 return isl_stat_error
;
2491 for (i
= 0; i
< node
->nvar
; ++i
) {
2492 int pos
= 1 + node_var_coef_pos(node
, i
);
2494 if (isl_int_is_neg(node
->max
->el
[i
]))
2497 isl_int_set_si(ineq
->el
[pos
], 1);
2498 isl_int_set_si(ineq
->el
[pos
+ 1], -1);
2499 isl_int_set(ineq
->el
[0], node
->max
->el
[i
]);
2501 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2504 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2506 isl_seq_neg(ineq
->el
+ pos
, ineq
->el
+ pos
, 2);
2507 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2510 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2512 isl_seq_clr(ineq
->el
+ pos
, 2);
2519 return isl_stat_error
;
2522 /* Add constraints that bound the values of the variable and parameter
2523 * coefficients of the schedule.
2525 * The maximal value of the coefficients is defined by the option
2526 * 'schedule_max_coefficient' and the entries in node->max.
2527 * These latter entries are only set if either the schedule_max_coefficient
2528 * option or the schedule_treat_coalescing option is set.
2530 static isl_stat
add_bound_coefficient_constraints(isl_ctx
*ctx
,
2531 struct isl_sched_graph
*graph
)
2536 max
= isl_options_get_schedule_max_coefficient(ctx
);
2538 if (max
== -1 && !isl_options_get_schedule_treat_coalescing(ctx
))
2541 for (i
= 0; i
< graph
->n
; ++i
) {
2542 struct isl_sched_node
*node
= &graph
->node
[i
];
2544 if (node_add_coefficient_constraints(ctx
, graph
, node
, max
) < 0)
2545 return isl_stat_error
;
2551 /* Add a constraint to graph->lp that equates the value at position
2552 * "sum_pos" to the sum of the "n" values starting at "first".
2554 static isl_stat
add_sum_constraint(struct isl_sched_graph
*graph
,
2555 int sum_pos
, int first
, int n
)
2560 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2562 k
= isl_basic_set_alloc_equality(graph
->lp
);
2564 return isl_stat_error
;
2565 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2566 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2567 for (i
= 0; i
< n
; ++i
)
2568 isl_int_set_si(graph
->lp
->eq
[k
][1 + first
+ i
], 1);
2573 /* Add a constraint to graph->lp that equates the value at position
2574 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2576 static isl_stat
add_param_sum_constraint(struct isl_sched_graph
*graph
,
2582 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2584 k
= isl_basic_set_alloc_equality(graph
->lp
);
2586 return isl_stat_error
;
2587 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2588 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2589 for (i
= 0; i
< graph
->n
; ++i
) {
2590 int pos
= 1 + node_par_coef_offset(&graph
->node
[i
]);
2592 for (j
= 0; j
< graph
->node
[i
].nparam
; ++j
)
2593 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2599 /* Add a constraint to graph->lp that equates the value at position
2600 * "sum_pos" to the sum of the variable coefficients of all nodes.
2602 static isl_stat
add_var_sum_constraint(struct isl_sched_graph
*graph
,
2608 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2610 k
= isl_basic_set_alloc_equality(graph
->lp
);
2612 return isl_stat_error
;
2613 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2614 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2615 for (i
= 0; i
< graph
->n
; ++i
) {
2616 struct isl_sched_node
*node
= &graph
->node
[i
];
2617 int pos
= 1 + node_var_coef_offset(node
);
2619 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2620 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2626 /* Construct an ILP problem for finding schedule coefficients
2627 * that result in non-negative, but small dependence distances
2628 * over all dependences.
2629 * In particular, the dependence distances over proximity edges
2630 * are bounded by m_0 + m_n n and we compute schedule coefficients
2631 * with small values (preferably zero) of m_n and m_0.
2633 * All variables of the ILP are non-negative. The actual coefficients
2634 * may be negative, so each coefficient is represented as the difference
2635 * of two non-negative variables. The negative part always appears
2636 * immediately before the positive part.
2637 * Other than that, the variables have the following order
2639 * - sum of positive and negative parts of m_n coefficients
2641 * - sum of all c_n coefficients
2642 * (unconstrained when computing non-parametric schedules)
2643 * - sum of positive and negative parts of all c_x coefficients
2644 * - positive and negative parts of m_n coefficients
2646 * - positive and negative parts of c_i_x, in opposite order
2647 * - c_i_n (if parametric)
2650 * The constraints are those from the edges plus two or three equalities
2651 * to express the sums.
2653 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2654 * Otherwise, we ignore them.
2656 static isl_stat
setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2657 int use_coincidence
)
2667 parametric
= ctx
->opt
->schedule_parametric
;
2668 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2670 total
= param_pos
+ 2 * nparam
;
2671 for (i
= 0; i
< graph
->n
; ++i
) {
2672 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2673 if (node_update_vmap(node
) < 0)
2674 return isl_stat_error
;
2675 node
->start
= total
;
2676 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
2679 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2680 return isl_stat_error
;
2681 if (count_bound_constant_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2682 return isl_stat_error
;
2683 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2684 return isl_stat_error
;
2686 space
= isl_space_set_alloc(ctx
, 0, total
);
2687 isl_basic_set_free(graph
->lp
);
2688 n_eq
+= 2 + parametric
;
2690 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
2692 if (add_sum_constraint(graph
, 0, param_pos
, 2 * nparam
) < 0)
2693 return isl_stat_error
;
2694 if (parametric
&& add_param_sum_constraint(graph
, 2) < 0)
2695 return isl_stat_error
;
2696 if (add_var_sum_constraint(graph
, 3) < 0)
2697 return isl_stat_error
;
2698 if (add_bound_constant_constraints(ctx
, graph
) < 0)
2699 return isl_stat_error
;
2700 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2701 return isl_stat_error
;
2702 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2703 return isl_stat_error
;
2704 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2705 return isl_stat_error
;
2710 /* Analyze the conflicting constraint found by
2711 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2712 * constraint of one of the edges between distinct nodes, living, moreover
2713 * in distinct SCCs, then record the source and sink SCC as this may
2714 * be a good place to cut between SCCs.
2716 static int check_conflict(int con
, void *user
)
2719 struct isl_sched_graph
*graph
= user
;
2721 if (graph
->src_scc
>= 0)
2724 con
-= graph
->lp
->n_eq
;
2726 if (con
>= graph
->lp
->n_ineq
)
2729 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2730 if (!is_validity(&graph
->edge
[i
]))
2732 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2734 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2736 if (graph
->edge
[i
].start
> con
)
2738 if (graph
->edge
[i
].end
<= con
)
2740 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2741 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2747 /* Check whether the next schedule row of the given node needs to be
2748 * non-trivial. Lower-dimensional domains may have some trivial rows,
2749 * but as soon as the number of remaining required non-trivial rows
2750 * is as large as the number or remaining rows to be computed,
2751 * all remaining rows need to be non-trivial.
2753 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2755 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2758 /* Construct a non-triviality region with triviality directions
2759 * corresponding to the rows of "indep".
2760 * The rows of "indep" are expressed in terms of the schedule coefficients c_i,
2761 * while the triviality directions are expressed in terms of
2762 * pairs of non-negative variables c^+_i - c^-_i, with c^-_i appearing
2763 * before c^+_i. Furthermore,
2764 * the pairs of non-negative variables representing the coefficients
2765 * are stored in the opposite order.
2767 static __isl_give isl_mat
*construct_trivial(__isl_keep isl_mat
*indep
)
2776 ctx
= isl_mat_get_ctx(indep
);
2777 n
= isl_mat_rows(indep
);
2778 n_var
= isl_mat_cols(indep
);
2779 mat
= isl_mat_alloc(ctx
, n
, 2 * n_var
);
2782 for (i
= 0; i
< n
; ++i
) {
2783 for (j
= 0; j
< n_var
; ++j
) {
2784 int nj
= n_var
- 1 - j
;
2785 isl_int_neg(mat
->row
[i
][2 * nj
], indep
->row
[i
][j
]);
2786 isl_int_set(mat
->row
[i
][2 * nj
+ 1], indep
->row
[i
][j
]);
2793 /* Solve the ILP problem constructed in setup_lp.
2794 * For each node such that all the remaining rows of its schedule
2795 * need to be non-trivial, we construct a non-triviality region.
2796 * This region imposes that the next row is independent of previous rows.
2797 * In particular, the non-triviality region enforces that at least
2798 * one of the linear combinations in the rows of node->indep is non-zero.
2800 static __isl_give isl_vec
*solve_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2806 for (i
= 0; i
< graph
->n
; ++i
) {
2807 struct isl_sched_node
*node
= &graph
->node
[i
];
2810 graph
->region
[i
].pos
= node_var_coef_offset(node
);
2811 if (needs_row(graph
, node
))
2812 trivial
= construct_trivial(node
->indep
);
2814 trivial
= isl_mat_zero(ctx
, 0, 0);
2815 graph
->region
[i
].trivial
= trivial
;
2817 lp
= isl_basic_set_copy(graph
->lp
);
2818 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2819 graph
->region
, &check_conflict
, graph
);
2820 for (i
= 0; i
< graph
->n
; ++i
)
2821 isl_mat_free(graph
->region
[i
].trivial
);
2825 /* Extract the coefficients for the variables of "node" from "sol".
2827 * Each schedule coefficient c_i_x is represented as the difference
2828 * between two non-negative variables c_i_x^+ - c_i_x^-.
2829 * The c_i_x^- appear before their c_i_x^+ counterpart.
2830 * Furthermore, the order of these pairs is the opposite of that
2831 * of the corresponding coefficients.
2833 * Return c_i_x = c_i_x^+ - c_i_x^-
2835 static __isl_give isl_vec
*extract_var_coef(struct isl_sched_node
*node
,
2836 __isl_keep isl_vec
*sol
)
2844 csol
= isl_vec_alloc(isl_vec_get_ctx(sol
), node
->nvar
);
2848 pos
= 1 + node_var_coef_offset(node
);
2849 for (i
= 0; i
< node
->nvar
; ++i
)
2850 isl_int_sub(csol
->el
[node
->nvar
- 1 - i
],
2851 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
2856 /* Update the schedules of all nodes based on the given solution
2857 * of the LP problem.
2858 * The new row is added to the current band.
2859 * All possibly negative coefficients are encoded as a difference
2860 * of two non-negative variables, so we need to perform the subtraction
2863 * If coincident is set, then the caller guarantees that the new
2864 * row satisfies the coincidence constraints.
2866 static int update_schedule(struct isl_sched_graph
*graph
,
2867 __isl_take isl_vec
*sol
, int coincident
)
2870 isl_vec
*csol
= NULL
;
2875 isl_die(sol
->ctx
, isl_error_internal
,
2876 "no solution found", goto error
);
2877 if (graph
->n_total_row
>= graph
->max_row
)
2878 isl_die(sol
->ctx
, isl_error_internal
,
2879 "too many schedule rows", goto error
);
2881 for (i
= 0; i
< graph
->n
; ++i
) {
2882 struct isl_sched_node
*node
= &graph
->node
[i
];
2884 int row
= isl_mat_rows(node
->sched
);
2887 csol
= extract_var_coef(node
, sol
);
2891 isl_map_free(node
->sched_map
);
2892 node
->sched_map
= NULL
;
2893 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2896 pos
= node_cst_coef_offset(node
);
2897 node
->sched
= isl_mat_set_element(node
->sched
,
2898 row
, 0, sol
->el
[1 + pos
]);
2899 pos
= node_par_coef_offset(node
);
2900 for (j
= 0; j
< node
->nparam
; ++j
)
2901 node
->sched
= isl_mat_set_element(node
->sched
,
2902 row
, 1 + j
, sol
->el
[1 + pos
+ j
]);
2903 for (j
= 0; j
< node
->nvar
; ++j
)
2904 node
->sched
= isl_mat_set_element(node
->sched
,
2905 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2906 node
->coincident
[graph
->n_total_row
] = coincident
;
2912 graph
->n_total_row
++;
2921 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2922 * and return this isl_aff.
2924 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2925 struct isl_sched_node
*node
, int row
)
2933 aff
= isl_aff_zero_on_domain(ls
);
2934 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2935 aff
= isl_aff_set_constant(aff
, v
);
2936 for (j
= 0; j
< node
->nparam
; ++j
) {
2937 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2938 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2940 for (j
= 0; j
< node
->nvar
; ++j
) {
2941 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2942 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2950 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2951 * and return this multi_aff.
2953 * The result is defined over the uncompressed node domain.
2955 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2956 struct isl_sched_node
*node
, int first
, int n
)
2960 isl_local_space
*ls
;
2967 nrow
= isl_mat_rows(node
->sched
);
2968 if (node
->compressed
)
2969 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2971 space
= isl_space_copy(node
->space
);
2972 ls
= isl_local_space_from_space(isl_space_copy(space
));
2973 space
= isl_space_from_domain(space
);
2974 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2975 ma
= isl_multi_aff_zero(space
);
2977 for (i
= first
; i
< first
+ n
; ++i
) {
2978 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2979 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2982 isl_local_space_free(ls
);
2984 if (node
->compressed
)
2985 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2986 isl_multi_aff_copy(node
->compress
));
2991 /* Convert node->sched into a multi_aff and return this multi_aff.
2993 * The result is defined over the uncompressed node domain.
2995 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2996 struct isl_sched_node
*node
)
3000 nrow
= isl_mat_rows(node
->sched
);
3001 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
3004 /* Convert node->sched into a map and return this map.
3006 * The result is cached in node->sched_map, which needs to be released
3007 * whenever node->sched is updated.
3008 * It is defined over the uncompressed node domain.
3010 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
3012 if (!node
->sched_map
) {
3015 ma
= node_extract_schedule_multi_aff(node
);
3016 node
->sched_map
= isl_map_from_multi_aff(ma
);
3019 return isl_map_copy(node
->sched_map
);
3022 /* Construct a map that can be used to update a dependence relation
3023 * based on the current schedule.
3024 * That is, construct a map expressing that source and sink
3025 * are executed within the same iteration of the current schedule.
3026 * This map can then be intersected with the dependence relation.
3027 * This is not the most efficient way, but this shouldn't be a critical
3030 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
3031 struct isl_sched_node
*dst
)
3033 isl_map
*src_sched
, *dst_sched
;
3035 src_sched
= node_extract_schedule(src
);
3036 dst_sched
= node_extract_schedule(dst
);
3037 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
3040 /* Intersect the domains of the nested relations in domain and range
3041 * of "umap" with "map".
3043 static __isl_give isl_union_map
*intersect_domains(
3044 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
3046 isl_union_set
*uset
;
3048 umap
= isl_union_map_zip(umap
);
3049 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
3050 umap
= isl_union_map_intersect_domain(umap
, uset
);
3051 umap
= isl_union_map_zip(umap
);
3055 /* Update the dependence relation of the given edge based
3056 * on the current schedule.
3057 * If the dependence is carried completely by the current schedule, then
3058 * it is removed from the edge_tables. It is kept in the list of edges
3059 * as otherwise all edge_tables would have to be recomputed.
3061 static int update_edge(struct isl_sched_graph
*graph
,
3062 struct isl_sched_edge
*edge
)
3067 id
= specializer(edge
->src
, edge
->dst
);
3068 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
3072 if (edge
->tagged_condition
) {
3073 edge
->tagged_condition
=
3074 intersect_domains(edge
->tagged_condition
, id
);
3075 if (!edge
->tagged_condition
)
3078 if (edge
->tagged_validity
) {
3079 edge
->tagged_validity
=
3080 intersect_domains(edge
->tagged_validity
, id
);
3081 if (!edge
->tagged_validity
)
3085 empty
= isl_map_plain_is_empty(edge
->map
);
3089 graph_remove_edge(graph
, edge
);
3098 /* Does the domain of "umap" intersect "uset"?
3100 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3101 __isl_keep isl_union_set
*uset
)
3105 umap
= isl_union_map_copy(umap
);
3106 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3107 empty
= isl_union_map_is_empty(umap
);
3108 isl_union_map_free(umap
);
3110 return empty
< 0 ? -1 : !empty
;
3113 /* Does the range of "umap" intersect "uset"?
3115 static int range_intersects(__isl_keep isl_union_map
*umap
,
3116 __isl_keep isl_union_set
*uset
)
3120 umap
= isl_union_map_copy(umap
);
3121 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3122 empty
= isl_union_map_is_empty(umap
);
3123 isl_union_map_free(umap
);
3125 return empty
< 0 ? -1 : !empty
;
3128 /* Are the condition dependences of "edge" local with respect to
3129 * the current schedule?
3131 * That is, are domain and range of the condition dependences mapped
3132 * to the same point?
3134 * In other words, is the condition false?
3136 static int is_condition_false(struct isl_sched_edge
*edge
)
3138 isl_union_map
*umap
;
3139 isl_map
*map
, *sched
, *test
;
3142 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
3143 if (empty
< 0 || empty
)
3146 umap
= isl_union_map_copy(edge
->tagged_condition
);
3147 umap
= isl_union_map_zip(umap
);
3148 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3149 map
= isl_map_from_union_map(umap
);
3151 sched
= node_extract_schedule(edge
->src
);
3152 map
= isl_map_apply_domain(map
, sched
);
3153 sched
= node_extract_schedule(edge
->dst
);
3154 map
= isl_map_apply_range(map
, sched
);
3156 test
= isl_map_identity(isl_map_get_space(map
));
3157 local
= isl_map_is_subset(map
, test
);
3164 /* For each conditional validity constraint that is adjacent
3165 * to a condition with domain in condition_source or range in condition_sink,
3166 * turn it into an unconditional validity constraint.
3168 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
3169 __isl_take isl_union_set
*condition_source
,
3170 __isl_take isl_union_set
*condition_sink
)
3174 condition_source
= isl_union_set_coalesce(condition_source
);
3175 condition_sink
= isl_union_set_coalesce(condition_sink
);
3177 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3179 isl_union_map
*validity
;
3181 if (!is_conditional_validity(&graph
->edge
[i
]))
3183 if (is_validity(&graph
->edge
[i
]))
3186 validity
= graph
->edge
[i
].tagged_validity
;
3187 adjacent
= domain_intersects(validity
, condition_sink
);
3188 if (adjacent
>= 0 && !adjacent
)
3189 adjacent
= range_intersects(validity
, condition_source
);
3195 set_validity(&graph
->edge
[i
]);
3198 isl_union_set_free(condition_source
);
3199 isl_union_set_free(condition_sink
);
3202 isl_union_set_free(condition_source
);
3203 isl_union_set_free(condition_sink
);
3207 /* Update the dependence relations of all edges based on the current schedule
3208 * and enforce conditional validity constraints that are adjacent
3209 * to satisfied condition constraints.
3211 * First check if any of the condition constraints are satisfied
3212 * (i.e., not local to the outer schedule) and keep track of
3213 * their domain and range.
3214 * Then update all dependence relations (which removes the non-local
3216 * Finally, if any condition constraints turned out to be satisfied,
3217 * then turn all adjacent conditional validity constraints into
3218 * unconditional validity constraints.
3220 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3224 isl_union_set
*source
, *sink
;
3226 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3227 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3228 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3230 isl_union_set
*uset
;
3231 isl_union_map
*umap
;
3233 if (!is_condition(&graph
->edge
[i
]))
3235 if (is_local(&graph
->edge
[i
]))
3237 local
= is_condition_false(&graph
->edge
[i
]);
3245 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3246 uset
= isl_union_map_domain(umap
);
3247 source
= isl_union_set_union(source
, uset
);
3249 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3250 uset
= isl_union_map_range(umap
);
3251 sink
= isl_union_set_union(sink
, uset
);
3254 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
3255 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
3260 return unconditionalize_adjacent_validity(graph
, source
, sink
);
3262 isl_union_set_free(source
);
3263 isl_union_set_free(sink
);
3266 isl_union_set_free(source
);
3267 isl_union_set_free(sink
);
3271 static void next_band(struct isl_sched_graph
*graph
)
3273 graph
->band_start
= graph
->n_total_row
;
3276 /* Return the union of the universe domains of the nodes in "graph"
3277 * that satisfy "pred".
3279 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
3280 struct isl_sched_graph
*graph
,
3281 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
3287 for (i
= 0; i
< graph
->n
; ++i
)
3288 if (pred(&graph
->node
[i
], data
))
3292 isl_die(ctx
, isl_error_internal
,
3293 "empty component", return NULL
);
3295 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3296 dom
= isl_union_set_from_set(set
);
3298 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
3299 if (!pred(&graph
->node
[i
], data
))
3301 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3302 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
3308 /* Return a list of unions of universe domains, where each element
3309 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3311 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
3312 struct isl_sched_graph
*graph
)
3315 isl_union_set_list
*filters
;
3317 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
3318 for (i
= 0; i
< graph
->scc
; ++i
) {
3321 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
3322 filters
= isl_union_set_list_add(filters
, dom
);
3328 /* Return a list of two unions of universe domains, one for the SCCs up
3329 * to and including graph->src_scc and another for the other SCCs.
3331 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
3332 struct isl_sched_graph
*graph
)
3335 isl_union_set_list
*filters
;
3337 filters
= isl_union_set_list_alloc(ctx
, 2);
3338 dom
= isl_sched_graph_domain(ctx
, graph
,
3339 &node_scc_at_most
, graph
->src_scc
);
3340 filters
= isl_union_set_list_add(filters
, dom
);
3341 dom
= isl_sched_graph_domain(ctx
, graph
,
3342 &node_scc_at_least
, graph
->src_scc
+ 1);
3343 filters
= isl_union_set_list_add(filters
, dom
);
3348 /* Copy nodes that satisfy node_pred from the src dependence graph
3349 * to the dst dependence graph.
3351 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
3352 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
3357 for (i
= 0; i
< src
->n
; ++i
) {
3360 if (!node_pred(&src
->node
[i
], data
))
3364 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
3365 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
3366 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
3367 dst
->node
[j
].compress
=
3368 isl_multi_aff_copy(src
->node
[i
].compress
);
3369 dst
->node
[j
].decompress
=
3370 isl_multi_aff_copy(src
->node
[i
].decompress
);
3371 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
3372 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
3373 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
3374 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
3375 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
3376 dst
->node
[j
].sizes
= isl_multi_val_copy(src
->node
[i
].sizes
);
3377 dst
->node
[j
].bounds
= isl_basic_set_copy(src
->node
[i
].bounds
);
3378 dst
->node
[j
].max
= isl_vec_copy(src
->node
[i
].max
);
3381 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
3383 if (dst
->node
[j
].compressed
&&
3384 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
3385 !dst
->node
[j
].decompress
))
3392 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3393 * to the dst dependence graph.
3394 * If the source or destination node of the edge is not in the destination
3395 * graph, then it must be a backward proximity edge and it should simply
3398 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3399 struct isl_sched_graph
*src
,
3400 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3403 enum isl_edge_type t
;
3406 for (i
= 0; i
< src
->n_edge
; ++i
) {
3407 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3409 isl_union_map
*tagged_condition
;
3410 isl_union_map
*tagged_validity
;
3411 struct isl_sched_node
*dst_src
, *dst_dst
;
3413 if (!edge_pred(edge
, data
))
3416 if (isl_map_plain_is_empty(edge
->map
))
3419 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
3420 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
3421 if (!dst_src
|| !dst_dst
) {
3422 if (is_validity(edge
) || is_conditional_validity(edge
))
3423 isl_die(ctx
, isl_error_internal
,
3424 "backward (conditional) validity edge",
3429 map
= isl_map_copy(edge
->map
);
3430 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3431 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3433 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3434 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3435 dst
->edge
[dst
->n_edge
].map
= map
;
3436 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3437 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3438 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3441 if (edge
->tagged_condition
&& !tagged_condition
)
3443 if (edge
->tagged_validity
&& !tagged_validity
)
3446 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
3448 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
3450 if (graph_edge_table_add(ctx
, dst
, t
,
3451 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3459 /* Compute the maximal number of variables over all nodes.
3460 * This is the maximal number of linearly independent schedule
3461 * rows that we need to compute.
3462 * Just in case we end up in a part of the dependence graph
3463 * with only lower-dimensional domains, we make sure we will
3464 * compute the required amount of extra linearly independent rows.
3466 static int compute_maxvar(struct isl_sched_graph
*graph
)
3471 for (i
= 0; i
< graph
->n
; ++i
) {
3472 struct isl_sched_node
*node
= &graph
->node
[i
];
3475 if (node_update_vmap(node
) < 0)
3477 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3478 if (nvar
> graph
->maxvar
)
3479 graph
->maxvar
= nvar
;
3485 /* Extract the subgraph of "graph" that consists of the node satisfying
3486 * "node_pred" and the edges satisfying "edge_pred" and store
3487 * the result in "sub".
3489 static int extract_sub_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3490 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3491 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3492 int data
, struct isl_sched_graph
*sub
)
3494 int i
, n
= 0, n_edge
= 0;
3497 for (i
= 0; i
< graph
->n
; ++i
)
3498 if (node_pred(&graph
->node
[i
], data
))
3500 for (i
= 0; i
< graph
->n_edge
; ++i
)
3501 if (edge_pred(&graph
->edge
[i
], data
))
3503 if (graph_alloc(ctx
, sub
, n
, n_edge
) < 0)
3505 if (copy_nodes(sub
, graph
, node_pred
, data
) < 0)
3507 if (graph_init_table(ctx
, sub
) < 0)
3509 for (t
= 0; t
<= isl_edge_last
; ++t
)
3510 sub
->max_edge
[t
] = graph
->max_edge
[t
];
3511 if (graph_init_edge_tables(ctx
, sub
) < 0)
3513 if (copy_edges(ctx
, sub
, graph
, edge_pred
, data
) < 0)
3515 sub
->n_row
= graph
->n_row
;
3516 sub
->max_row
= graph
->max_row
;
3517 sub
->n_total_row
= graph
->n_total_row
;
3518 sub
->band_start
= graph
->band_start
;
3523 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3524 struct isl_sched_graph
*graph
);
3525 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3526 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3528 /* Compute a schedule for a subgraph of "graph". In particular, for
3529 * the graph composed of nodes that satisfy node_pred and edges that
3530 * that satisfy edge_pred.
3531 * If the subgraph is known to consist of a single component, then wcc should
3532 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3533 * Otherwise, we call compute_schedule, which will check whether the subgraph
3536 * The schedule is inserted at "node" and the updated schedule node
3539 static __isl_give isl_schedule_node
*compute_sub_schedule(
3540 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3541 struct isl_sched_graph
*graph
,
3542 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3543 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3546 struct isl_sched_graph split
= { 0 };
3548 if (extract_sub_graph(ctx
, graph
, node_pred
, edge_pred
, data
,
3553 node
= compute_schedule_wcc(node
, &split
);
3555 node
= compute_schedule(node
, &split
);
3557 graph_free(ctx
, &split
);
3560 graph_free(ctx
, &split
);
3561 return isl_schedule_node_free(node
);
3564 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3566 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3569 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3571 return edge
->dst
->scc
<= scc
;
3574 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3576 return edge
->src
->scc
>= scc
;
3579 /* Reset the current band by dropping all its schedule rows.
3581 static int reset_band(struct isl_sched_graph
*graph
)
3586 drop
= graph
->n_total_row
- graph
->band_start
;
3587 graph
->n_total_row
-= drop
;
3588 graph
->n_row
-= drop
;
3590 for (i
= 0; i
< graph
->n
; ++i
) {
3591 struct isl_sched_node
*node
= &graph
->node
[i
];
3593 isl_map_free(node
->sched_map
);
3594 node
->sched_map
= NULL
;
3596 node
->sched
= isl_mat_drop_rows(node
->sched
,
3597 graph
->band_start
, drop
);
3606 /* Split the current graph into two parts and compute a schedule for each
3607 * part individually. In particular, one part consists of all SCCs up
3608 * to and including graph->src_scc, while the other part contains the other
3609 * SCCs. The split is enforced by a sequence node inserted at position "node"
3610 * in the schedule tree. Return the updated schedule node.
3611 * If either of these two parts consists of a sequence, then it is spliced
3612 * into the sequence containing the two parts.
3614 * The current band is reset. It would be possible to reuse
3615 * the previously computed rows as the first rows in the next
3616 * band, but recomputing them may result in better rows as we are looking
3617 * at a smaller part of the dependence graph.
3619 static __isl_give isl_schedule_node
*compute_split_schedule(
3620 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3624 isl_union_set_list
*filters
;
3629 if (reset_band(graph
) < 0)
3630 return isl_schedule_node_free(node
);
3634 ctx
= isl_schedule_node_get_ctx(node
);
3635 filters
= extract_split(ctx
, graph
);
3636 node
= isl_schedule_node_insert_sequence(node
, filters
);
3637 node
= isl_schedule_node_child(node
, 1);
3638 node
= isl_schedule_node_child(node
, 0);
3640 node
= compute_sub_schedule(node
, ctx
, graph
,
3641 &node_scc_at_least
, &edge_src_scc_at_least
,
3642 graph
->src_scc
+ 1, 0);
3643 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3644 node
= isl_schedule_node_parent(node
);
3645 node
= isl_schedule_node_parent(node
);
3647 node
= isl_schedule_node_sequence_splice_child(node
, 1);
3648 node
= isl_schedule_node_child(node
, 0);
3649 node
= isl_schedule_node_child(node
, 0);
3650 node
= compute_sub_schedule(node
, ctx
, graph
,
3651 &node_scc_at_most
, &edge_dst_scc_at_most
,
3653 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3654 node
= isl_schedule_node_parent(node
);
3655 node
= isl_schedule_node_parent(node
);
3657 node
= isl_schedule_node_sequence_splice_child(node
, 0);
3662 /* Insert a band node at position "node" in the schedule tree corresponding
3663 * to the current band in "graph". Mark the band node permutable
3664 * if "permutable" is set.
3665 * The partial schedules and the coincidence property are extracted
3666 * from the graph nodes.
3667 * Return the updated schedule node.
3669 static __isl_give isl_schedule_node
*insert_current_band(
3670 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3676 isl_multi_pw_aff
*mpa
;
3677 isl_multi_union_pw_aff
*mupa
;
3683 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3684 "graph should have at least one node",
3685 return isl_schedule_node_free(node
));
3687 start
= graph
->band_start
;
3688 end
= graph
->n_total_row
;
3691 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3692 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3693 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3695 for (i
= 1; i
< graph
->n
; ++i
) {
3696 isl_multi_union_pw_aff
*mupa_i
;
3698 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3700 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3701 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3702 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3704 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3706 for (i
= 0; i
< n
; ++i
)
3707 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3708 graph
->node
[0].coincident
[start
+ i
]);
3709 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3714 /* Update the dependence relations based on the current schedule,
3715 * add the current band to "node" and then continue with the computation
3717 * Return the updated schedule node.
3719 static __isl_give isl_schedule_node
*compute_next_band(
3720 __isl_take isl_schedule_node
*node
,
3721 struct isl_sched_graph
*graph
, int permutable
)
3728 ctx
= isl_schedule_node_get_ctx(node
);
3729 if (update_edges(ctx
, graph
) < 0)
3730 return isl_schedule_node_free(node
);
3731 node
= insert_current_band(node
, graph
, permutable
);
3734 node
= isl_schedule_node_child(node
, 0);
3735 node
= compute_schedule(node
, graph
);
3736 node
= isl_schedule_node_parent(node
);
3741 /* Add the constraints "coef" derived from an edge from "node" to itself
3742 * to graph->lp in order to respect the dependences and to try and carry them.
3743 * "pos" is the sequence number of the edge that needs to be carried.
3744 * "coef" represents general constraints on coefficients (c_0, c_x)
3745 * of valid constraints for (y - x) with x and y instances of the node.
3747 * The constraints added to graph->lp need to enforce
3749 * (c_j_0 + c_j_x y) - (c_j_0 + c_j_x x)
3750 * = c_j_x (y - x) >= e_i
3752 * for each (x,y) in the dependence relation of the edge.
3753 * That is, (-e_i, c_j_x) needs to be plugged in for (c_0, c_x),
3754 * taking into account that each coefficient in c_j_x is represented
3755 * as a pair of non-negative coefficients.
3757 static isl_stat
add_intra_constraints(struct isl_sched_graph
*graph
,
3758 struct isl_sched_node
*node
, __isl_take isl_basic_set
*coef
, int pos
)
3762 isl_dim_map
*dim_map
;
3765 return isl_stat_error
;
3767 ctx
= isl_basic_set_get_ctx(coef
);
3768 offset
= coef_var_offset(coef
);
3769 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
3770 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3771 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
3776 /* Add the constraints "coef" derived from an edge from "src" to "dst"
3777 * to graph->lp in order to respect the dependences and to try and carry them.
3778 * "pos" is the sequence number of the edge that needs to be carried or
3779 * -1 if no attempt should be made to carry the dependences.
3780 * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y)
3781 * of valid constraints for (x, y) with x and y instances of "src" and "dst".
3783 * The constraints added to graph->lp need to enforce
3785 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3787 * for each (x,y) in the dependence relation of the edge or
3789 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= 0
3793 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3795 * (c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3796 * needs to be plugged in for (c_0, c_n, c_x, c_y),
3797 * taking into account that each coefficient in c_j_x and c_k_x is represented
3798 * as a pair of non-negative coefficients.
3800 static isl_stat
add_inter_constraints(struct isl_sched_graph
*graph
,
3801 struct isl_sched_node
*src
, struct isl_sched_node
*dst
,
3802 __isl_take isl_basic_set
*coef
, int pos
)
3806 isl_dim_map
*dim_map
;
3809 return isl_stat_error
;
3811 ctx
= isl_basic_set_get_ctx(coef
);
3812 offset
= coef_var_offset(coef
);
3813 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
3815 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3816 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
3821 /* Data structure for keeping track of the data needed
3822 * to exploit non-trivial lineality spaces.
3824 * "any_non_trivial" is true if there are any non-trivial lineality spaces.
3825 * If "any_non_trivial" is not true, then "equivalent" and "mask" may be NULL.
3826 * "equivalent" connects instances to other instances on the same line(s).
3827 * "mask" contains the domain spaces of "equivalent".
3828 * Any instance set not in "mask" does not have a non-trivial lineality space.
3830 struct isl_exploit_lineality_data
{
3831 isl_bool any_non_trivial
;
3832 isl_union_map
*equivalent
;
3833 isl_union_set
*mask
;
3836 /* Data structure collecting information used during the construction
3837 * of an LP for carrying dependences.
3839 * "intra" is a sequence of coefficient constraints for intra-node edges.
3840 * "inter" is a sequence of coefficient constraints for inter-node edges.
3841 * "lineality" contains data used to exploit non-trivial lineality spaces.
3844 isl_basic_set_list
*intra
;
3845 isl_basic_set_list
*inter
;
3846 struct isl_exploit_lineality_data lineality
;
3849 /* Free all the data stored in "carry".
3851 static void isl_carry_clear(struct isl_carry
*carry
)
3853 isl_basic_set_list_free(carry
->intra
);
3854 isl_basic_set_list_free(carry
->inter
);
3855 isl_union_map_free(carry
->lineality
.equivalent
);
3856 isl_union_set_free(carry
->lineality
.mask
);
3859 /* Return a pointer to the node in "graph" that lives in "space".
3860 * If the requested node has been compressed, then "space"
3861 * corresponds to the compressed space.
3863 * First try and see if "space" is the space of an uncompressed node.
3864 * If so, return that node.
3865 * Otherwise, "space" was constructed by construct_compressed_id and
3866 * contains a user pointer pointing to the node in the tuple id.
3868 static struct isl_sched_node
*graph_find_compressed_node(isl_ctx
*ctx
,
3869 struct isl_sched_graph
*graph
, __isl_keep isl_space
*space
)
3872 struct isl_sched_node
*node
;
3877 node
= graph_find_node(ctx
, graph
, space
);
3881 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
3882 node
= isl_id_get_user(id
);
3888 if (!(node
>= &graph
->node
[0] && node
< &graph
->node
[graph
->n
]))
3889 isl_die(ctx
, isl_error_internal
,
3890 "space points to invalid node", return NULL
);
3895 /* Internal data structure for add_all_constraints.
3897 * "graph" is the schedule constraint graph for which an LP problem
3898 * is being constructed.
3899 * "carry_inter" indicates whether inter-node edges should be carried.
3900 * "pos" is the position of the next edge that needs to be carried.
3902 struct isl_add_all_constraints_data
{
3904 struct isl_sched_graph
*graph
;
3909 /* Add the constraints "coef" derived from an edge from a node to itself
3910 * to data->graph->lp in order to respect the dependences and
3911 * to try and carry them.
3913 * The space of "coef" is of the form
3915 * coefficients[[c_cst] -> S[c_x]]
3917 * with S[c_x] the (compressed) space of the node.
3918 * Extract the node from the space and call add_intra_constraints.
3920 static isl_stat
lp_add_intra(__isl_take isl_basic_set
*coef
, void *user
)
3922 struct isl_add_all_constraints_data
*data
= user
;
3924 struct isl_sched_node
*node
;
3926 space
= isl_basic_set_get_space(coef
);
3927 space
= isl_space_range(isl_space_unwrap(space
));
3928 node
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
3929 isl_space_free(space
);
3930 return add_intra_constraints(data
->graph
, node
, coef
, data
->pos
++);
3933 /* Add the constraints "coef" derived from an edge from a node j
3934 * to a node k to data->graph->lp in order to respect the dependences and
3935 * to try and carry them (provided data->carry_inter is set).
3937 * The space of "coef" is of the form
3939 * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]]
3941 * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes.
3942 * Extract the nodes from the space and call add_inter_constraints.
3944 static isl_stat
lp_add_inter(__isl_take isl_basic_set
*coef
, void *user
)
3946 struct isl_add_all_constraints_data
*data
= user
;
3947 isl_space
*space
, *dom
;
3948 struct isl_sched_node
*src
, *dst
;
3951 space
= isl_basic_set_get_space(coef
);
3952 space
= isl_space_unwrap(isl_space_range(isl_space_unwrap(space
)));
3953 dom
= isl_space_domain(isl_space_copy(space
));
3954 src
= graph_find_compressed_node(data
->ctx
, data
->graph
, dom
);
3955 isl_space_free(dom
);
3956 space
= isl_space_range(space
);
3957 dst
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
3958 isl_space_free(space
);
3960 pos
= data
->carry_inter
? data
->pos
++ : -1;
3961 return add_inter_constraints(data
->graph
, src
, dst
, coef
, pos
);
3964 /* Add constraints to graph->lp that force all (conditional) validity
3965 * dependences to be respected and attempt to carry them.
3966 * "intra" is the sequence of coefficient constraints for intra-node edges.
3967 * "inter" is the sequence of coefficient constraints for inter-node edges.
3968 * "carry_inter" indicates whether inter-node edges should be carried or
3971 static isl_stat
add_all_constraints(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3972 __isl_keep isl_basic_set_list
*intra
,
3973 __isl_keep isl_basic_set_list
*inter
, int carry_inter
)
3975 struct isl_add_all_constraints_data data
= { ctx
, graph
, carry_inter
};
3978 if (isl_basic_set_list_foreach(intra
, &lp_add_intra
, &data
) < 0)
3979 return isl_stat_error
;
3980 if (isl_basic_set_list_foreach(inter
, &lp_add_inter
, &data
) < 0)
3981 return isl_stat_error
;
3985 /* Internal data structure for count_all_constraints
3986 * for keeping track of the number of equality and inequality constraints.
3988 struct isl_sched_count
{
3993 /* Add the number of equality and inequality constraints of "bset"
3994 * to data->n_eq and data->n_ineq.
3996 static isl_stat
bset_update_count(__isl_take isl_basic_set
*bset
, void *user
)
3998 struct isl_sched_count
*data
= user
;
4000 return update_count(bset
, 1, &data
->n_eq
, &data
->n_ineq
);
4003 /* Count the number of equality and inequality constraints
4004 * that will be added to the carry_lp problem.
4005 * We count each edge exactly once.
4006 * "intra" is the sequence of coefficient constraints for intra-node edges.
4007 * "inter" is the sequence of coefficient constraints for inter-node edges.
4009 static isl_stat
count_all_constraints(__isl_keep isl_basic_set_list
*intra
,
4010 __isl_keep isl_basic_set_list
*inter
, int *n_eq
, int *n_ineq
)
4012 struct isl_sched_count data
;
4014 data
.n_eq
= data
.n_ineq
= 0;
4015 if (isl_basic_set_list_foreach(inter
, &bset_update_count
, &data
) < 0)
4016 return isl_stat_error
;
4017 if (isl_basic_set_list_foreach(intra
, &bset_update_count
, &data
) < 0)
4018 return isl_stat_error
;
4021 *n_ineq
= data
.n_ineq
;
4026 /* Construct an LP problem for finding schedule coefficients
4027 * such that the schedule carries as many validity dependences as possible.
4028 * In particular, for each dependence i, we bound the dependence distance
4029 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
4030 * of all e_i's. Dependences with e_i = 0 in the solution are simply
4031 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
4032 * "intra" is the sequence of coefficient constraints for intra-node edges.
4033 * "inter" is the sequence of coefficient constraints for inter-node edges.
4034 * "n_edge" is the total number of edges.
4035 * "carry_inter" indicates whether inter-node edges should be carried or
4036 * only respected. That is, if "carry_inter" is not set, then
4037 * no e_i variables are introduced for the inter-node edges.
4039 * All variables of the LP are non-negative. The actual coefficients
4040 * may be negative, so each coefficient is represented as the difference
4041 * of two non-negative variables. The negative part always appears
4042 * immediately before the positive part.
4043 * Other than that, the variables have the following order
4045 * - sum of (1 - e_i) over all edges
4046 * - sum of all c_n coefficients
4047 * (unconstrained when computing non-parametric schedules)
4048 * - sum of positive and negative parts of all c_x coefficients
4052 * - positive and negative parts of c_i_x, in opposite order
4053 * - c_i_n (if parametric)
4056 * The constraints are those from the (validity) edges plus three equalities
4057 * to express the sums and n_edge inequalities to express e_i <= 1.
4059 static isl_stat
setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
4060 int n_edge
, __isl_keep isl_basic_set_list
*intra
,
4061 __isl_keep isl_basic_set_list
*inter
, int carry_inter
)
4070 for (i
= 0; i
< graph
->n
; ++i
) {
4071 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
4072 node
->start
= total
;
4073 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
4076 if (count_all_constraints(intra
, inter
, &n_eq
, &n_ineq
) < 0)
4077 return isl_stat_error
;
4079 dim
= isl_space_set_alloc(ctx
, 0, total
);
4080 isl_basic_set_free(graph
->lp
);
4083 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
4084 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
4086 k
= isl_basic_set_alloc_equality(graph
->lp
);
4088 return isl_stat_error
;
4089 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
4090 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
4091 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
4092 for (i
= 0; i
< n_edge
; ++i
)
4093 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
4095 if (add_param_sum_constraint(graph
, 1) < 0)
4096 return isl_stat_error
;
4097 if (add_var_sum_constraint(graph
, 2) < 0)
4098 return isl_stat_error
;
4100 for (i
= 0; i
< n_edge
; ++i
) {
4101 k
= isl_basic_set_alloc_inequality(graph
->lp
);
4103 return isl_stat_error
;
4104 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
4105 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
4106 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
4109 if (add_all_constraints(ctx
, graph
, intra
, inter
, carry_inter
) < 0)
4110 return isl_stat_error
;
4115 static __isl_give isl_schedule_node
*compute_component_schedule(
4116 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4119 /* If the schedule_split_scaled option is set and if the linear
4120 * parts of the scheduling rows for all nodes in the graphs have
4121 * a non-trivial common divisor, then remove this
4122 * common divisor from the linear part.
4123 * Otherwise, insert a band node directly and continue with
4124 * the construction of the schedule.
4126 * If a non-trivial common divisor is found, then
4127 * the linear part is reduced and the remainder is ignored.
4128 * The pieces of the graph that are assigned different remainders
4129 * form (groups of) strongly connected components within
4130 * the scaled down band. If needed, they can therefore
4131 * be ordered along this remainder in a sequence node.
4132 * However, this ordering is not enforced here in order to allow
4133 * the scheduler to combine some of the strongly connected components.
4135 static __isl_give isl_schedule_node
*split_scaled(
4136 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4146 ctx
= isl_schedule_node_get_ctx(node
);
4147 if (!ctx
->opt
->schedule_split_scaled
)
4148 return compute_next_band(node
, graph
, 0);
4150 return compute_next_band(node
, graph
, 0);
4153 isl_int_init(gcd_i
);
4155 isl_int_set_si(gcd
, 0);
4157 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
4159 for (i
= 0; i
< graph
->n
; ++i
) {
4160 struct isl_sched_node
*node
= &graph
->node
[i
];
4161 int cols
= isl_mat_cols(node
->sched
);
4163 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
4164 isl_int_gcd(gcd
, gcd
, gcd_i
);
4167 isl_int_clear(gcd_i
);
4169 if (isl_int_cmp_si(gcd
, 1) <= 0) {
4171 return compute_next_band(node
, graph
, 0);
4174 for (i
= 0; i
< graph
->n
; ++i
) {
4175 struct isl_sched_node
*node
= &graph
->node
[i
];
4177 isl_int_fdiv_q(node
->sched
->row
[row
][0],
4178 node
->sched
->row
[row
][0], gcd
);
4179 isl_int_mul(node
->sched
->row
[row
][0],
4180 node
->sched
->row
[row
][0], gcd
);
4181 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
4188 return compute_next_band(node
, graph
, 0);
4191 return isl_schedule_node_free(node
);
4194 /* Is the schedule row "sol" trivial on node "node"?
4195 * That is, is the solution zero on the dimensions linearly independent of
4196 * the previously found solutions?
4197 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
4199 * Each coefficient is represented as the difference between
4200 * two non-negative values in "sol".
4201 * We construct the schedule row s and check if it is linearly
4202 * independent of previously computed schedule rows
4203 * by computing T s, with T the linear combinations that are zero
4204 * on linearly dependent schedule rows.
4205 * If the result consists of all zeros, then the solution is trivial.
4207 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
4214 if (node
->nvar
== node
->rank
)
4217 node_sol
= extract_var_coef(node
, sol
);
4218 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->indep
), node_sol
);
4222 trivial
= isl_seq_first_non_zero(node_sol
->el
,
4223 node
->nvar
- node
->rank
) == -1;
4225 isl_vec_free(node_sol
);
4230 /* Is the schedule row "sol" trivial on any node where it should
4232 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4234 static int is_any_trivial(struct isl_sched_graph
*graph
,
4235 __isl_keep isl_vec
*sol
)
4239 for (i
= 0; i
< graph
->n
; ++i
) {
4240 struct isl_sched_node
*node
= &graph
->node
[i
];
4243 if (!needs_row(graph
, node
))
4245 trivial
= is_trivial(node
, sol
);
4246 if (trivial
< 0 || trivial
)
4253 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
4254 * If so, return the position of the coalesced dimension.
4255 * Otherwise, return node->nvar or -1 on error.
4257 * In particular, look for pairs of coefficients c_i and c_j such that
4258 * |c_j/c_i| > ceil(size_i/2), i.e., |c_j| > |c_i * ceil(size_i/2)|.
4259 * If any such pair is found, then return i.
4260 * If size_i is infinity, then no check on c_i needs to be performed.
4262 static int find_node_coalescing(struct isl_sched_node
*node
,
4263 __isl_keep isl_vec
*sol
)
4269 if (node
->nvar
<= 1)
4272 csol
= extract_var_coef(node
, sol
);
4276 for (i
= 0; i
< node
->nvar
; ++i
) {
4279 if (isl_int_is_zero(csol
->el
[i
]))
4281 v
= isl_multi_val_get_val(node
->sizes
, i
);
4284 if (!isl_val_is_int(v
)) {
4288 v
= isl_val_div_ui(v
, 2);
4289 v
= isl_val_ceil(v
);
4292 isl_int_mul(max
, v
->n
, csol
->el
[i
]);
4295 for (j
= 0; j
< node
->nvar
; ++j
) {
4298 if (isl_int_abs_gt(csol
->el
[j
], max
))
4314 /* Force the schedule coefficient at position "pos" of "node" to be zero
4316 * The coefficient is encoded as the difference between two non-negative
4317 * variables. Force these two variables to have the same value.
4319 static __isl_give isl_tab_lexmin
*zero_out_node_coef(
4320 __isl_take isl_tab_lexmin
*tl
, struct isl_sched_node
*node
, int pos
)
4326 ctx
= isl_space_get_ctx(node
->space
);
4327 dim
= isl_tab_lexmin_dim(tl
);
4329 return isl_tab_lexmin_free(tl
);
4330 eq
= isl_vec_alloc(ctx
, 1 + dim
);
4331 eq
= isl_vec_clr(eq
);
4333 return isl_tab_lexmin_free(tl
);
4335 pos
= 1 + node_var_coef_pos(node
, pos
);
4336 isl_int_set_si(eq
->el
[pos
], 1);
4337 isl_int_set_si(eq
->el
[pos
+ 1], -1);
4338 tl
= isl_tab_lexmin_add_eq(tl
, eq
->el
);
4344 /* Return the lexicographically smallest rational point in the basic set
4345 * from which "tl" was constructed, double checking that this input set
4348 static __isl_give isl_vec
*non_empty_solution(__isl_keep isl_tab_lexmin
*tl
)
4352 sol
= isl_tab_lexmin_get_solution(tl
);
4356 isl_die(isl_vec_get_ctx(sol
), isl_error_internal
,
4357 "error in schedule construction",
4358 return isl_vec_free(sol
));
4362 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4363 * carry any of the "n_edge" groups of dependences?
4364 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4365 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4366 * by the edge are carried by the solution.
4367 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4368 * one of those is carried.
4370 * Note that despite the fact that the problem is solved using a rational
4371 * solver, the solution is guaranteed to be integral.
4372 * Specifically, the dependence distance lower bounds e_i (and therefore
4373 * also their sum) are integers. See Lemma 5 of [1].
4375 * Any potential denominator of the sum is cleared by this function.
4376 * The denominator is not relevant for any of the other elements
4379 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4380 * Problem, Part II: Multi-Dimensional Time.
4381 * In Intl. Journal of Parallel Programming, 1992.
4383 static int carries_dependences(__isl_keep isl_vec
*sol
, int n_edge
)
4385 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
4386 isl_int_set_si(sol
->el
[0], 1);
4387 return isl_int_cmp_si(sol
->el
[1], n_edge
) < 0;
4390 /* Return the lexicographically smallest rational point in "lp",
4391 * assuming that all variables are non-negative and performing some
4392 * additional sanity checks.
4393 * If "want_integral" is set, then compute the lexicographically smallest
4394 * integer point instead.
4395 * In particular, "lp" should not be empty by construction.
4396 * Double check that this is the case.
4397 * If dependences are not carried for any of the "n_edge" edges,
4398 * then return an empty vector.
4400 * If the schedule_treat_coalescing option is set and
4401 * if the computed schedule performs loop coalescing on a given node,
4402 * i.e., if it is of the form
4404 * c_i i + c_j j + ...
4406 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4407 * to cut out this solution. Repeat this process until no more loop
4408 * coalescing occurs or until no more dependences can be carried.
4409 * In the latter case, revert to the previously computed solution.
4411 * If the caller requests an integral solution and if coalescing should
4412 * be treated, then perform the coalescing treatment first as
4413 * an integral solution computed before coalescing treatment
4414 * would carry the same number of edges and would therefore probably
4415 * also be coalescing.
4417 * To allow the coalescing treatment to be performed first,
4418 * the initial solution is allowed to be rational and it is only
4419 * cut out (if needed) in the next iteration, if no coalescing measures
4422 static __isl_give isl_vec
*non_neg_lexmin(struct isl_sched_graph
*graph
,
4423 __isl_take isl_basic_set
*lp
, int n_edge
, int want_integral
)
4428 isl_vec
*sol
, *prev
= NULL
;
4429 int treat_coalescing
;
4433 ctx
= isl_basic_set_get_ctx(lp
);
4434 treat_coalescing
= isl_options_get_schedule_treat_coalescing(ctx
);
4435 tl
= isl_tab_lexmin_from_basic_set(lp
);
4442 tl
= isl_tab_lexmin_cut_to_integer(tl
);
4443 sol
= non_empty_solution(tl
);
4447 integral
= isl_int_is_one(sol
->el
[0]);
4448 if (!carries_dependences(sol
, n_edge
)) {
4450 prev
= isl_vec_alloc(ctx
, 0);
4455 prev
= isl_vec_free(prev
);
4456 cut
= want_integral
&& !integral
;
4459 if (!treat_coalescing
)
4461 for (i
= 0; i
< graph
->n
; ++i
) {
4462 struct isl_sched_node
*node
= &graph
->node
[i
];
4464 pos
= find_node_coalescing(node
, sol
);
4467 if (pos
< node
->nvar
)
4472 tl
= zero_out_node_coef(tl
, &graph
->node
[i
], pos
);
4477 isl_tab_lexmin_free(tl
);
4481 isl_tab_lexmin_free(tl
);
4487 /* If "edge" is an edge from a node to itself, then add the corresponding
4488 * dependence relation to "umap".
4489 * If "node" has been compressed, then the dependence relation
4490 * is also compressed first.
4492 static __isl_give isl_union_map
*add_intra(__isl_take isl_union_map
*umap
,
4493 struct isl_sched_edge
*edge
)
4496 struct isl_sched_node
*node
= edge
->src
;
4498 if (edge
->src
!= edge
->dst
)
4501 map
= isl_map_copy(edge
->map
);
4502 if (node
->compressed
) {
4503 map
= isl_map_preimage_domain_multi_aff(map
,
4504 isl_multi_aff_copy(node
->decompress
));
4505 map
= isl_map_preimage_range_multi_aff(map
,
4506 isl_multi_aff_copy(node
->decompress
));
4508 umap
= isl_union_map_add_map(umap
, map
);
4512 /* If "edge" is an edge from a node to another node, then add the corresponding
4513 * dependence relation to "umap".
4514 * If the source or destination nodes of "edge" have been compressed,
4515 * then the dependence relation is also compressed first.
4517 static __isl_give isl_union_map
*add_inter(__isl_take isl_union_map
*umap
,
4518 struct isl_sched_edge
*edge
)
4522 if (edge
->src
== edge
->dst
)
4525 map
= isl_map_copy(edge
->map
);
4526 if (edge
->src
->compressed
)
4527 map
= isl_map_preimage_domain_multi_aff(map
,
4528 isl_multi_aff_copy(edge
->src
->decompress
));
4529 if (edge
->dst
->compressed
)
4530 map
= isl_map_preimage_range_multi_aff(map
,
4531 isl_multi_aff_copy(edge
->dst
->decompress
));
4532 umap
= isl_union_map_add_map(umap
, map
);
4536 /* Internal data structure used by union_drop_coalescing_constraints
4537 * to collect bounds on all relevant statements.
4539 * "graph" is the schedule constraint graph for which an LP problem
4540 * is being constructed.
4541 * "bounds" collects the bounds.
4543 struct isl_collect_bounds_data
{
4545 struct isl_sched_graph
*graph
;
4546 isl_union_set
*bounds
;
4549 /* Add the size bounds for the node with instance deltas in "set"
4552 static isl_stat
collect_bounds(__isl_take isl_set
*set
, void *user
)
4554 struct isl_collect_bounds_data
*data
= user
;
4555 struct isl_sched_node
*node
;
4559 space
= isl_set_get_space(set
);
4562 node
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
4563 isl_space_free(space
);
4565 bounds
= isl_set_from_basic_set(get_size_bounds(node
));
4566 data
->bounds
= isl_union_set_add_set(data
->bounds
, bounds
);
4571 /* Drop some constraints from "delta" that could be exploited
4572 * to construct loop coalescing schedules.
4573 * In particular, drop those constraint that bound the difference
4574 * to the size of the domain.
4575 * Do this for each set/node in "delta" separately.
4576 * The parameters are assumed to have been projected out by the caller.
4578 static __isl_give isl_union_set
*union_drop_coalescing_constraints(isl_ctx
*ctx
,
4579 struct isl_sched_graph
*graph
, __isl_take isl_union_set
*delta
)
4581 struct isl_collect_bounds_data data
= { ctx
, graph
};
4583 data
.bounds
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4584 if (isl_union_set_foreach_set(delta
, &collect_bounds
, &data
) < 0)
4585 data
.bounds
= isl_union_set_free(data
.bounds
);
4586 delta
= isl_union_set_plain_gist(delta
, data
.bounds
);
4591 /* Given a non-trivial lineality space "lineality", add the corresponding
4592 * universe set to data->mask and add a map from elements to
4593 * other elements along the lines in "lineality" to data->equivalent.
4594 * If this is the first time this function gets called
4595 * (data->any_non_trivial is still false), then set data->any_non_trivial and
4596 * initialize data->mask and data->equivalent.
4598 * In particular, if the lineality space is defined by equality constraints
4602 * then construct an affine mapping
4606 * and compute the equivalence relation of having the same image under f:
4608 * { x -> x' : E x = E x' }
4610 static isl_stat
add_non_trivial_lineality(__isl_take isl_basic_set
*lineality
,
4611 struct isl_exploit_lineality_data
*data
)
4617 isl_multi_pw_aff
*mpa
;
4622 return isl_stat_error
;
4623 if (isl_basic_set_dim(lineality
, isl_dim_div
) != 0)
4624 isl_die(isl_basic_set_get_ctx(lineality
), isl_error_internal
,
4625 "local variables not allowed", goto error
);
4627 space
= isl_basic_set_get_space(lineality
);
4628 if (!data
->any_non_trivial
) {
4629 data
->equivalent
= isl_union_map_empty(isl_space_copy(space
));
4630 data
->mask
= isl_union_set_empty(isl_space_copy(space
));
4632 data
->any_non_trivial
= isl_bool_true
;
4634 univ
= isl_set_universe(isl_space_copy(space
));
4635 data
->mask
= isl_union_set_add_set(data
->mask
, univ
);
4637 eq
= isl_basic_set_extract_equalities(lineality
);
4638 n
= isl_mat_rows(eq
);
4639 eq
= isl_mat_insert_zero_rows(eq
, 0, 1);
4640 eq
= isl_mat_set_element_si(eq
, 0, 0, 1);
4641 space
= isl_space_from_domain(space
);
4642 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
4643 ma
= isl_multi_aff_from_aff_mat(space
, eq
);
4644 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
4645 map
= isl_multi_pw_aff_eq_map(mpa
, isl_multi_pw_aff_copy(mpa
));
4646 data
->equivalent
= isl_union_map_add_map(data
->equivalent
, map
);
4648 isl_basic_set_free(lineality
);
4651 isl_basic_set_free(lineality
);
4652 return isl_stat_error
;
4655 /* Check if the lineality space "set" is non-trivial (i.e., is not just
4656 * the origin or, in other words, satisfies a number of equality constraints
4657 * that is smaller than the dimension of the set).
4658 * If so, extend data->mask and data->equivalent accordingly.
4660 * The input should not have any local variables already, but
4661 * isl_set_remove_divs is called to make sure it does not.
4663 static isl_stat
add_lineality(__isl_take isl_set
*set
, void *user
)
4665 struct isl_exploit_lineality_data
*data
= user
;
4666 isl_basic_set
*hull
;
4669 set
= isl_set_remove_divs(set
);
4670 hull
= isl_set_unshifted_simple_hull(set
);
4671 dim
= isl_basic_set_dim(hull
, isl_dim_set
);
4672 n_eq
= isl_basic_set_n_equality(hull
);
4674 return isl_stat_error
;
4676 return add_non_trivial_lineality(hull
, data
);
4677 isl_basic_set_free(hull
);
4681 /* Check if the difference set on intra-node schedule constraints "intra"
4682 * has any non-trivial lineality space.
4683 * If so, then extend the difference set to a difference set
4684 * on equivalent elements. That is, if "intra" is
4686 * { y - x : (x,y) \in V }
4688 * and elements are equivalent if they have the same image under f,
4691 * { y' - x' : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4693 * or, since f is linear,
4695 * { y' - x' : (x,y) \in V and f(y - x) = f(y' - x') }
4697 * The results of the search for non-trivial lineality spaces is stored
4700 static __isl_give isl_union_set
*exploit_intra_lineality(
4701 __isl_take isl_union_set
*intra
,
4702 struct isl_exploit_lineality_data
*data
)
4704 isl_union_set
*lineality
;
4705 isl_union_set
*uset
;
4707 data
->any_non_trivial
= isl_bool_false
;
4708 lineality
= isl_union_set_copy(intra
);
4709 lineality
= isl_union_set_combined_lineality_space(lineality
);
4710 if (isl_union_set_foreach_set(lineality
, &add_lineality
, data
) < 0)
4711 data
->any_non_trivial
= isl_bool_error
;
4712 isl_union_set_free(lineality
);
4714 if (data
->any_non_trivial
< 0)
4715 return isl_union_set_free(intra
);
4716 if (!data
->any_non_trivial
)
4719 uset
= isl_union_set_copy(intra
);
4720 intra
= isl_union_set_subtract(intra
, isl_union_set_copy(data
->mask
));
4721 uset
= isl_union_set_apply(uset
, isl_union_map_copy(data
->equivalent
));
4722 intra
= isl_union_set_union(intra
, uset
);
4724 intra
= isl_union_set_remove_divs(intra
);
4729 /* If the difference set on intra-node schedule constraints was found to have
4730 * any non-trivial lineality space by exploit_intra_lineality,
4731 * as recorded in "data", then extend the inter-node
4732 * schedule constraints "inter" to schedule constraints on equivalent elements.
4733 * That is, if "inter" is V and
4734 * elements are equivalent if they have the same image under f, then return
4736 * { (x', y') : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4738 static __isl_give isl_union_map
*exploit_inter_lineality(
4739 __isl_take isl_union_map
*inter
,
4740 struct isl_exploit_lineality_data
*data
)
4742 isl_union_map
*umap
;
4744 if (data
->any_non_trivial
< 0)
4745 return isl_union_map_free(inter
);
4746 if (!data
->any_non_trivial
)
4749 umap
= isl_union_map_copy(inter
);
4750 inter
= isl_union_map_subtract_range(inter
,
4751 isl_union_set_copy(data
->mask
));
4752 umap
= isl_union_map_apply_range(umap
,
4753 isl_union_map_copy(data
->equivalent
));
4754 inter
= isl_union_map_union(inter
, umap
);
4755 umap
= isl_union_map_copy(inter
);
4756 inter
= isl_union_map_subtract_domain(inter
,
4757 isl_union_set_copy(data
->mask
));
4758 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->equivalent
),
4760 inter
= isl_union_map_union(inter
, umap
);
4762 inter
= isl_union_map_remove_divs(inter
);
4767 /* For each (conditional) validity edge in "graph",
4768 * add the corresponding dependence relation using "add"
4769 * to a collection of dependence relations and return the result.
4770 * If "coincidence" is set, then coincidence edges are considered as well.
4772 static __isl_give isl_union_map
*collect_validity(struct isl_sched_graph
*graph
,
4773 __isl_give isl_union_map
*(*add
)(__isl_take isl_union_map
*umap
,
4774 struct isl_sched_edge
*edge
), int coincidence
)
4778 isl_union_map
*umap
;
4780 space
= isl_space_copy(graph
->node
[0].space
);
4781 umap
= isl_union_map_empty(space
);
4783 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4784 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4786 if (!is_any_validity(edge
) &&
4787 (!coincidence
|| !is_coincidence(edge
)))
4790 umap
= add(umap
, edge
);
4796 /* Project out all parameters from "uset" and return the result.
4798 static __isl_give isl_union_set
*union_set_drop_parameters(
4799 __isl_take isl_union_set
*uset
)
4803 nparam
= isl_union_set_dim(uset
, isl_dim_param
);
4804 return isl_union_set_project_out(uset
, isl_dim_param
, 0, nparam
);
4807 /* For each dependence relation on a (conditional) validity edge
4808 * from a node to itself,
4809 * construct the set of coefficients of valid constraints for elements
4810 * in that dependence relation and collect the results.
4811 * If "coincidence" is set, then coincidence edges are considered as well.
4813 * In particular, for each dependence relation R, constraints
4814 * on coefficients (c_0, c_x) are constructed such that
4816 * c_0 + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
4818 * If the schedule_treat_coalescing option is set, then some constraints
4819 * that could be exploited to construct coalescing schedules
4820 * are removed before the dual is computed, but after the parameters
4821 * have been projected out.
4822 * The entire computation is essentially the same as that performed
4823 * by intra_coefficients, except that it operates on multiple
4824 * edges together and that the parameters are always projected out.
4826 * Additionally, exploit any non-trivial lineality space
4827 * in the difference set after removing coalescing constraints and
4828 * store the results of the non-trivial lineality space detection in "data".
4829 * The procedure is currently run unconditionally, but it is unlikely
4830 * to find any non-trivial lineality spaces if no coalescing constraints
4831 * have been removed.
4833 * Note that if a dependence relation is a union of basic maps,
4834 * then each basic map needs to be treated individually as it may only
4835 * be possible to carry the dependences expressed by some of those
4836 * basic maps and not all of them.
4837 * The collected validity constraints are therefore not coalesced and
4838 * it is assumed that they are not coalesced automatically.
4839 * Duplicate basic maps can be removed, however.
4840 * In particular, if the same basic map appears as a disjunct
4841 * in multiple edges, then it only needs to be carried once.
4843 static __isl_give isl_basic_set_list
*collect_intra_validity(isl_ctx
*ctx
,
4844 struct isl_sched_graph
*graph
, int coincidence
,
4845 struct isl_exploit_lineality_data
*data
)
4847 isl_union_map
*intra
;
4848 isl_union_set
*delta
;
4849 isl_basic_set_list
*list
;
4851 intra
= collect_validity(graph
, &add_intra
, coincidence
);
4852 delta
= isl_union_map_deltas(intra
);
4853 delta
= union_set_drop_parameters(delta
);
4854 delta
= isl_union_set_remove_divs(delta
);
4855 if (isl_options_get_schedule_treat_coalescing(ctx
))
4856 delta
= union_drop_coalescing_constraints(ctx
, graph
, delta
);
4857 delta
= exploit_intra_lineality(delta
, data
);
4858 list
= isl_union_set_get_basic_set_list(delta
);
4859 isl_union_set_free(delta
);
4861 return isl_basic_set_list_coefficients(list
);
4864 /* For each dependence relation on a (conditional) validity edge
4865 * from a node to some other node,
4866 * construct the set of coefficients of valid constraints for elements
4867 * in that dependence relation and collect the results.
4868 * If "coincidence" is set, then coincidence edges are considered as well.
4870 * In particular, for each dependence relation R, constraints
4871 * on coefficients (c_0, c_n, c_x, c_y) are constructed such that
4873 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
4875 * This computation is essentially the same as that performed
4876 * by inter_coefficients, except that it operates on multiple
4879 * Additionally, exploit any non-trivial lineality space
4880 * that may have been discovered by collect_intra_validity
4881 * (as stored in "data").
4883 * Note that if a dependence relation is a union of basic maps,
4884 * then each basic map needs to be treated individually as it may only
4885 * be possible to carry the dependences expressed by some of those
4886 * basic maps and not all of them.
4887 * The collected validity constraints are therefore not coalesced and
4888 * it is assumed that they are not coalesced automatically.
4889 * Duplicate basic maps can be removed, however.
4890 * In particular, if the same basic map appears as a disjunct
4891 * in multiple edges, then it only needs to be carried once.
4893 static __isl_give isl_basic_set_list
*collect_inter_validity(
4894 struct isl_sched_graph
*graph
, int coincidence
,
4895 struct isl_exploit_lineality_data
*data
)
4897 isl_union_map
*inter
;
4898 isl_union_set
*wrap
;
4899 isl_basic_set_list
*list
;
4901 inter
= collect_validity(graph
, &add_inter
, coincidence
);
4902 inter
= exploit_inter_lineality(inter
, data
);
4903 inter
= isl_union_map_remove_divs(inter
);
4904 wrap
= isl_union_map_wrap(inter
);
4905 list
= isl_union_set_get_basic_set_list(wrap
);
4906 isl_union_set_free(wrap
);
4907 return isl_basic_set_list_coefficients(list
);
4910 /* Construct an LP problem for finding schedule coefficients
4911 * such that the schedule carries as many of the "n_edge" groups of
4912 * dependences as possible based on the corresponding coefficient
4913 * constraints and return the lexicographically smallest non-trivial solution.
4914 * "intra" is the sequence of coefficient constraints for intra-node edges.
4915 * "inter" is the sequence of coefficient constraints for inter-node edges.
4916 * If "want_integral" is set, then compute an integral solution
4917 * for the coefficients rather than using the numerators
4918 * of a rational solution.
4919 * "carry_inter" indicates whether inter-node edges should be carried or
4922 * If none of the "n_edge" groups can be carried
4923 * then return an empty vector.
4925 static __isl_give isl_vec
*compute_carrying_sol_coef(isl_ctx
*ctx
,
4926 struct isl_sched_graph
*graph
, int n_edge
,
4927 __isl_keep isl_basic_set_list
*intra
,
4928 __isl_keep isl_basic_set_list
*inter
, int want_integral
,
4933 if (setup_carry_lp(ctx
, graph
, n_edge
, intra
, inter
, carry_inter
) < 0)
4936 lp
= isl_basic_set_copy(graph
->lp
);
4937 return non_neg_lexmin(graph
, lp
, n_edge
, want_integral
);
4940 /* Construct an LP problem for finding schedule coefficients
4941 * such that the schedule carries as many of the validity dependences
4943 * return the lexicographically smallest non-trivial solution.
4944 * If "fallback" is set, then the carrying is performed as a fallback
4945 * for the Pluto-like scheduler.
4946 * If "coincidence" is set, then try and carry coincidence edges as well.
4948 * The variable "n_edge" stores the number of groups that should be carried.
4949 * If none of the "n_edge" groups can be carried
4950 * then return an empty vector.
4951 * If, moreover, "n_edge" is zero, then the LP problem does not even
4952 * need to be constructed.
4954 * If a fallback solution is being computed, then compute an integral solution
4955 * for the coefficients rather than using the numerators
4956 * of a rational solution.
4958 * If a fallback solution is being computed, if there are any intra-node
4959 * dependences, and if requested by the user, then first try
4960 * to only carry those intra-node dependences.
4961 * If this fails to carry any dependences, then try again
4962 * with the inter-node dependences included.
4964 static __isl_give isl_vec
*compute_carrying_sol(isl_ctx
*ctx
,
4965 struct isl_sched_graph
*graph
, int fallback
, int coincidence
)
4967 int n_intra
, n_inter
;
4969 struct isl_carry carry
= { 0 };
4972 carry
.intra
= collect_intra_validity(ctx
, graph
, coincidence
,
4974 carry
.inter
= collect_inter_validity(graph
, coincidence
,
4976 if (!carry
.intra
|| !carry
.inter
)
4978 n_intra
= isl_basic_set_list_n_basic_set(carry
.intra
);
4979 n_inter
= isl_basic_set_list_n_basic_set(carry
.inter
);
4981 if (fallback
&& n_intra
> 0 &&
4982 isl_options_get_schedule_carry_self_first(ctx
)) {
4983 sol
= compute_carrying_sol_coef(ctx
, graph
, n_intra
,
4984 carry
.intra
, carry
.inter
, fallback
, 0);
4985 if (!sol
|| sol
->size
!= 0 || n_inter
== 0) {
4986 isl_carry_clear(&carry
);
4992 n_edge
= n_intra
+ n_inter
;
4994 isl_carry_clear(&carry
);
4995 return isl_vec_alloc(ctx
, 0);
4998 sol
= compute_carrying_sol_coef(ctx
, graph
, n_edge
,
4999 carry
.intra
, carry
.inter
, fallback
, 1);
5000 isl_carry_clear(&carry
);
5003 isl_carry_clear(&carry
);
5007 /* Construct a schedule row for each node such that as many validity dependences
5008 * as possible are carried and then continue with the next band.
5009 * If "fallback" is set, then the carrying is performed as a fallback
5010 * for the Pluto-like scheduler.
5011 * If "coincidence" is set, then try and carry coincidence edges as well.
5013 * If there are no validity dependences, then no dependence can be carried and
5014 * the procedure is guaranteed to fail. If there is more than one component,
5015 * then try computing a schedule on each component separately
5016 * to prevent or at least postpone this failure.
5018 * If a schedule row is computed, then check that dependences are carried
5019 * for at least one of the edges.
5021 * If the computed schedule row turns out to be trivial on one or
5022 * more nodes where it should not be trivial, then we throw it away
5023 * and try again on each component separately.
5025 * If there is only one component, then we accept the schedule row anyway,
5026 * but we do not consider it as a complete row and therefore do not
5027 * increment graph->n_row. Note that the ranks of the nodes that
5028 * do get a non-trivial schedule part will get updated regardless and
5029 * graph->maxvar is computed based on these ranks. The test for
5030 * whether more schedule rows are required in compute_schedule_wcc
5031 * is therefore not affected.
5033 * Insert a band corresponding to the schedule row at position "node"
5034 * of the schedule tree and continue with the construction of the schedule.
5035 * This insertion and the continued construction is performed by split_scaled
5036 * after optionally checking for non-trivial common divisors.
5038 static __isl_give isl_schedule_node
*carry(__isl_take isl_schedule_node
*node
,
5039 struct isl_sched_graph
*graph
, int fallback
, int coincidence
)
5048 ctx
= isl_schedule_node_get_ctx(node
);
5049 sol
= compute_carrying_sol(ctx
, graph
, fallback
, coincidence
);
5051 return isl_schedule_node_free(node
);
5052 if (sol
->size
== 0) {
5055 return compute_component_schedule(node
, graph
, 1);
5056 isl_die(ctx
, isl_error_unknown
, "unable to carry dependences",
5057 return isl_schedule_node_free(node
));
5060 trivial
= is_any_trivial(graph
, sol
);
5062 sol
= isl_vec_free(sol
);
5063 } else if (trivial
&& graph
->scc
> 1) {
5065 return compute_component_schedule(node
, graph
, 1);
5068 if (update_schedule(graph
, sol
, 0) < 0)
5069 return isl_schedule_node_free(node
);
5073 return split_scaled(node
, graph
);
5076 /* Construct a schedule row for each node such that as many validity dependences
5077 * as possible are carried and then continue with the next band.
5078 * Do so as a fallback for the Pluto-like scheduler.
5079 * If "coincidence" is set, then try and carry coincidence edges as well.
5081 static __isl_give isl_schedule_node
*carry_fallback(
5082 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5085 return carry(node
, graph
, 1, coincidence
);
5088 /* Construct a schedule row for each node such that as many validity dependences
5089 * as possible are carried and then continue with the next band.
5090 * Do so for the case where the Feautrier scheduler was selected
5093 static __isl_give isl_schedule_node
*carry_feautrier(
5094 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5096 return carry(node
, graph
, 0, 0);
5099 /* Construct a schedule row for each node such that as many validity dependences
5100 * as possible are carried and then continue with the next band.
5101 * Do so as a fallback for the Pluto-like scheduler.
5103 static __isl_give isl_schedule_node
*carry_dependences(
5104 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5106 return carry_fallback(node
, graph
, 0);
5109 /* Construct a schedule row for each node such that as many validity or
5110 * coincidence dependences as possible are carried and
5111 * then continue with the next band.
5112 * Do so as a fallback for the Pluto-like scheduler.
5114 static __isl_give isl_schedule_node
*carry_coincidence(
5115 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5117 return carry_fallback(node
, graph
, 1);
5120 /* Topologically sort statements mapped to the same schedule iteration
5121 * and add insert a sequence node in front of "node"
5122 * corresponding to this order.
5123 * If "initialized" is set, then it may be assumed that compute_maxvar
5124 * has been called on the current band. Otherwise, call
5125 * compute_maxvar if and before carry_dependences gets called.
5127 * If it turns out to be impossible to sort the statements apart,
5128 * because different dependences impose different orderings
5129 * on the statements, then we extend the schedule such that
5130 * it carries at least one more dependence.
5132 static __isl_give isl_schedule_node
*sort_statements(
5133 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5137 isl_union_set_list
*filters
;
5142 ctx
= isl_schedule_node_get_ctx(node
);
5144 isl_die(ctx
, isl_error_internal
,
5145 "graph should have at least one node",
5146 return isl_schedule_node_free(node
));
5151 if (update_edges(ctx
, graph
) < 0)
5152 return isl_schedule_node_free(node
);
5154 if (graph
->n_edge
== 0)
5157 if (detect_sccs(ctx
, graph
) < 0)
5158 return isl_schedule_node_free(node
);
5161 if (graph
->scc
< graph
->n
) {
5162 if (!initialized
&& compute_maxvar(graph
) < 0)
5163 return isl_schedule_node_free(node
);
5164 return carry_dependences(node
, graph
);
5167 filters
= extract_sccs(ctx
, graph
);
5168 node
= isl_schedule_node_insert_sequence(node
, filters
);
5173 /* Are there any (non-empty) (conditional) validity edges in the graph?
5175 static int has_validity_edges(struct isl_sched_graph
*graph
)
5179 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5182 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
5187 if (is_any_validity(&graph
->edge
[i
]))
5194 /* Should we apply a Feautrier step?
5195 * That is, did the user request the Feautrier algorithm and are
5196 * there any validity dependences (left)?
5198 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
5200 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
5203 return has_validity_edges(graph
);
5206 /* Compute a schedule for a connected dependence graph using Feautrier's
5207 * multi-dimensional scheduling algorithm and return the updated schedule node.
5209 * The original algorithm is described in [1].
5210 * The main idea is to minimize the number of scheduling dimensions, by
5211 * trying to satisfy as many dependences as possible per scheduling dimension.
5213 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
5214 * Problem, Part II: Multi-Dimensional Time.
5215 * In Intl. Journal of Parallel Programming, 1992.
5217 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
5218 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5220 return carry_feautrier(node
, graph
);
5223 /* Turn off the "local" bit on all (condition) edges.
5225 static void clear_local_edges(struct isl_sched_graph
*graph
)
5229 for (i
= 0; i
< graph
->n_edge
; ++i
)
5230 if (is_condition(&graph
->edge
[i
]))
5231 clear_local(&graph
->edge
[i
]);
5234 /* Does "graph" have both condition and conditional validity edges?
5236 static int need_condition_check(struct isl_sched_graph
*graph
)
5239 int any_condition
= 0;
5240 int any_conditional_validity
= 0;
5242 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5243 if (is_condition(&graph
->edge
[i
]))
5245 if (is_conditional_validity(&graph
->edge
[i
]))
5246 any_conditional_validity
= 1;
5249 return any_condition
&& any_conditional_validity
;
5252 /* Does "graph" contain any coincidence edge?
5254 static int has_any_coincidence(struct isl_sched_graph
*graph
)
5258 for (i
= 0; i
< graph
->n_edge
; ++i
)
5259 if (is_coincidence(&graph
->edge
[i
]))
5265 /* Extract the final schedule row as a map with the iteration domain
5266 * of "node" as domain.
5268 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
5273 row
= isl_mat_rows(node
->sched
) - 1;
5274 ma
= node_extract_partial_schedule_multi_aff(node
, row
, 1);
5275 return isl_map_from_multi_aff(ma
);
5278 /* Is the conditional validity dependence in the edge with index "edge_index"
5279 * violated by the latest (i.e., final) row of the schedule?
5280 * That is, is i scheduled after j
5281 * for any conditional validity dependence i -> j?
5283 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
5285 isl_map
*src_sched
, *dst_sched
, *map
;
5286 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
5289 src_sched
= final_row(edge
->src
);
5290 dst_sched
= final_row(edge
->dst
);
5291 map
= isl_map_copy(edge
->map
);
5292 map
= isl_map_apply_domain(map
, src_sched
);
5293 map
= isl_map_apply_range(map
, dst_sched
);
5294 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
5295 empty
= isl_map_is_empty(map
);
5304 /* Does "graph" have any satisfied condition edges that
5305 * are adjacent to the conditional validity constraint with
5306 * domain "conditional_source" and range "conditional_sink"?
5308 * A satisfied condition is one that is not local.
5309 * If a condition was forced to be local already (i.e., marked as local)
5310 * then there is no need to check if it is in fact local.
5312 * Additionally, mark all adjacent condition edges found as local.
5314 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
5315 __isl_keep isl_union_set
*conditional_source
,
5316 __isl_keep isl_union_set
*conditional_sink
)
5321 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5322 int adjacent
, local
;
5323 isl_union_map
*condition
;
5325 if (!is_condition(&graph
->edge
[i
]))
5327 if (is_local(&graph
->edge
[i
]))
5330 condition
= graph
->edge
[i
].tagged_condition
;
5331 adjacent
= domain_intersects(condition
, conditional_sink
);
5332 if (adjacent
>= 0 && !adjacent
)
5333 adjacent
= range_intersects(condition
,
5334 conditional_source
);
5340 set_local(&graph
->edge
[i
]);
5342 local
= is_condition_false(&graph
->edge
[i
]);
5352 /* Are there any violated conditional validity dependences with
5353 * adjacent condition dependences that are not local with respect
5354 * to the current schedule?
5355 * That is, is the conditional validity constraint violated?
5357 * Additionally, mark all those adjacent condition dependences as local.
5358 * We also mark those adjacent condition dependences that were not marked
5359 * as local before, but just happened to be local already. This ensures
5360 * that they remain local if the schedule is recomputed.
5362 * We first collect domain and range of all violated conditional validity
5363 * dependences and then check if there are any adjacent non-local
5364 * condition dependences.
5366 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
5367 struct isl_sched_graph
*graph
)
5371 isl_union_set
*source
, *sink
;
5373 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
5374 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
5375 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5376 isl_union_set
*uset
;
5377 isl_union_map
*umap
;
5380 if (!is_conditional_validity(&graph
->edge
[i
]))
5383 violated
= is_violated(graph
, i
);
5391 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
5392 uset
= isl_union_map_domain(umap
);
5393 source
= isl_union_set_union(source
, uset
);
5394 source
= isl_union_set_coalesce(source
);
5396 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
5397 uset
= isl_union_map_range(umap
);
5398 sink
= isl_union_set_union(sink
, uset
);
5399 sink
= isl_union_set_coalesce(sink
);
5403 any
= has_adjacent_true_conditions(graph
, source
, sink
);
5405 isl_union_set_free(source
);
5406 isl_union_set_free(sink
);
5409 isl_union_set_free(source
);
5410 isl_union_set_free(sink
);
5414 /* Examine the current band (the rows between graph->band_start and
5415 * graph->n_total_row), deciding whether to drop it or add it to "node"
5416 * and then continue with the computation of the next band, if any.
5417 * If "initialized" is set, then it may be assumed that compute_maxvar
5418 * has been called on the current band. Otherwise, call
5419 * compute_maxvar if and before carry_dependences gets called.
5421 * The caller keeps looking for a new row as long as
5422 * graph->n_row < graph->maxvar. If the latest attempt to find
5423 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
5425 * - split between SCCs and start over (assuming we found an interesting
5426 * pair of SCCs between which to split)
5427 * - continue with the next band (assuming the current band has at least
5429 * - if there is more than one SCC left, then split along all SCCs
5430 * - if outer coincidence needs to be enforced, then try to carry as many
5431 * validity or coincidence dependences as possible and
5432 * continue with the next band
5433 * - try to carry as many validity dependences as possible and
5434 * continue with the next band
5435 * In each case, we first insert a band node in the schedule tree
5436 * if any rows have been computed.
5438 * If the caller managed to complete the schedule, we insert a band node
5439 * (if any schedule rows were computed) and we finish off by topologically
5440 * sorting the statements based on the remaining dependences.
5442 static __isl_give isl_schedule_node
*compute_schedule_finish_band(
5443 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5451 if (graph
->n_row
< graph
->maxvar
) {
5453 int empty
= graph
->n_total_row
== graph
->band_start
;
5455 ctx
= isl_schedule_node_get_ctx(node
);
5456 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
5457 return compute_next_band(node
, graph
, 1);
5458 if (graph
->src_scc
>= 0)
5459 return compute_split_schedule(node
, graph
);
5461 return compute_next_band(node
, graph
, 1);
5463 return compute_component_schedule(node
, graph
, 1);
5464 if (!initialized
&& compute_maxvar(graph
) < 0)
5465 return isl_schedule_node_free(node
);
5466 if (isl_options_get_schedule_outer_coincidence(ctx
))
5467 return carry_coincidence(node
, graph
);
5468 return carry_dependences(node
, graph
);
5471 insert
= graph
->n_total_row
> graph
->band_start
;
5473 node
= insert_current_band(node
, graph
, 1);
5474 node
= isl_schedule_node_child(node
, 0);
5476 node
= sort_statements(node
, graph
, initialized
);
5478 node
= isl_schedule_node_parent(node
);
5483 /* Construct a band of schedule rows for a connected dependence graph.
5484 * The caller is responsible for determining the strongly connected
5485 * components and calling compute_maxvar first.
5487 * We try to find a sequence of as many schedule rows as possible that result
5488 * in non-negative dependence distances (independent of the previous rows
5489 * in the sequence, i.e., such that the sequence is tilable), with as
5490 * many of the initial rows as possible satisfying the coincidence constraints.
5491 * The computation stops if we can't find any more rows or if we have found
5492 * all the rows we wanted to find.
5494 * If ctx->opt->schedule_outer_coincidence is set, then we force the
5495 * outermost dimension to satisfy the coincidence constraints. If this
5496 * turns out to be impossible, we fall back on the general scheme above
5497 * and try to carry as many dependences as possible.
5499 * If "graph" contains both condition and conditional validity dependences,
5500 * then we need to check that that the conditional schedule constraint
5501 * is satisfied, i.e., there are no violated conditional validity dependences
5502 * that are adjacent to any non-local condition dependences.
5503 * If there are, then we mark all those adjacent condition dependences
5504 * as local and recompute the current band. Those dependences that
5505 * are marked local will then be forced to be local.
5506 * The initial computation is performed with no dependences marked as local.
5507 * If we are lucky, then there will be no violated conditional validity
5508 * dependences adjacent to any non-local condition dependences.
5509 * Otherwise, we mark some additional condition dependences as local and
5510 * recompute. We continue this process until there are no violations left or
5511 * until we are no longer able to compute a schedule.
5512 * Since there are only a finite number of dependences,
5513 * there will only be a finite number of iterations.
5515 static isl_stat
compute_schedule_wcc_band(isl_ctx
*ctx
,
5516 struct isl_sched_graph
*graph
)
5518 int has_coincidence
;
5519 int use_coincidence
;
5520 int force_coincidence
= 0;
5521 int check_conditional
;
5523 if (sort_sccs(graph
) < 0)
5524 return isl_stat_error
;
5526 clear_local_edges(graph
);
5527 check_conditional
= need_condition_check(graph
);
5528 has_coincidence
= has_any_coincidence(graph
);
5530 if (ctx
->opt
->schedule_outer_coincidence
)
5531 force_coincidence
= 1;
5533 use_coincidence
= has_coincidence
;
5534 while (graph
->n_row
< graph
->maxvar
) {
5539 graph
->src_scc
= -1;
5540 graph
->dst_scc
= -1;
5542 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
5543 return isl_stat_error
;
5544 sol
= solve_lp(ctx
, graph
);
5546 return isl_stat_error
;
5547 if (sol
->size
== 0) {
5548 int empty
= graph
->n_total_row
== graph
->band_start
;
5551 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
5552 use_coincidence
= 0;
5557 coincident
= !has_coincidence
|| use_coincidence
;
5558 if (update_schedule(graph
, sol
, coincident
) < 0)
5559 return isl_stat_error
;
5561 if (!check_conditional
)
5563 violated
= has_violated_conditional_constraint(ctx
, graph
);
5565 return isl_stat_error
;
5568 if (reset_band(graph
) < 0)
5569 return isl_stat_error
;
5570 use_coincidence
= has_coincidence
;
5576 /* Compute a schedule for a connected dependence graph by considering
5577 * the graph as a whole and return the updated schedule node.
5579 * The actual schedule rows of the current band are computed by
5580 * compute_schedule_wcc_band. compute_schedule_finish_band takes
5581 * care of integrating the band into "node" and continuing
5584 static __isl_give isl_schedule_node
*compute_schedule_wcc_whole(
5585 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5592 ctx
= isl_schedule_node_get_ctx(node
);
5593 if (compute_schedule_wcc_band(ctx
, graph
) < 0)
5594 return isl_schedule_node_free(node
);
5596 return compute_schedule_finish_band(node
, graph
, 1);
5599 /* Clustering information used by compute_schedule_wcc_clustering.
5601 * "n" is the number of SCCs in the original dependence graph
5602 * "scc" is an array of "n" elements, each representing an SCC
5603 * of the original dependence graph. All entries in the same cluster
5604 * have the same number of schedule rows.
5605 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
5606 * where each cluster is represented by the index of the first SCC
5607 * in the cluster. Initially, each SCC belongs to a cluster containing
5610 * "scc_in_merge" is used by merge_clusters_along_edge to keep
5611 * track of which SCCs need to be merged.
5613 * "cluster" contains the merged clusters of SCCs after the clustering
5616 * "scc_node" is a temporary data structure used inside copy_partial.
5617 * For each SCC, it keeps track of the number of nodes in the SCC
5618 * that have already been copied.
5620 struct isl_clustering
{
5622 struct isl_sched_graph
*scc
;
5623 struct isl_sched_graph
*cluster
;
5629 /* Initialize the clustering data structure "c" from "graph".
5631 * In particular, allocate memory, extract the SCCs from "graph"
5632 * into c->scc, initialize scc_cluster and construct
5633 * a band of schedule rows for each SCC.
5634 * Within each SCC, there is only one SCC by definition.
5635 * Each SCC initially belongs to a cluster containing only that SCC.
5637 static isl_stat
clustering_init(isl_ctx
*ctx
, struct isl_clustering
*c
,
5638 struct isl_sched_graph
*graph
)
5643 c
->scc
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
5644 c
->cluster
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
5645 c
->scc_cluster
= isl_calloc_array(ctx
, int, c
->n
);
5646 c
->scc_node
= isl_calloc_array(ctx
, int, c
->n
);
5647 c
->scc_in_merge
= isl_calloc_array(ctx
, int, c
->n
);
5648 if (!c
->scc
|| !c
->cluster
||
5649 !c
->scc_cluster
|| !c
->scc_node
|| !c
->scc_in_merge
)
5650 return isl_stat_error
;
5652 for (i
= 0; i
< c
->n
; ++i
) {
5653 if (extract_sub_graph(ctx
, graph
, &node_scc_exactly
,
5654 &edge_scc_exactly
, i
, &c
->scc
[i
]) < 0)
5655 return isl_stat_error
;
5657 if (compute_maxvar(&c
->scc
[i
]) < 0)
5658 return isl_stat_error
;
5659 if (compute_schedule_wcc_band(ctx
, &c
->scc
[i
]) < 0)
5660 return isl_stat_error
;
5661 c
->scc_cluster
[i
] = i
;
5667 /* Free all memory allocated for "c".
5669 static void clustering_free(isl_ctx
*ctx
, struct isl_clustering
*c
)
5674 for (i
= 0; i
< c
->n
; ++i
)
5675 graph_free(ctx
, &c
->scc
[i
]);
5678 for (i
= 0; i
< c
->n
; ++i
)
5679 graph_free(ctx
, &c
->cluster
[i
]);
5681 free(c
->scc_cluster
);
5683 free(c
->scc_in_merge
);
5686 /* Should we refrain from merging the cluster in "graph" with
5687 * any other cluster?
5688 * In particular, is its current schedule band empty and incomplete.
5690 static int bad_cluster(struct isl_sched_graph
*graph
)
5692 return graph
->n_row
< graph
->maxvar
&&
5693 graph
->n_total_row
== graph
->band_start
;
5696 /* Is "edge" a proximity edge with a non-empty dependence relation?
5698 static isl_bool
is_non_empty_proximity(struct isl_sched_edge
*edge
)
5700 if (!is_proximity(edge
))
5701 return isl_bool_false
;
5702 return isl_bool_not(isl_map_plain_is_empty(edge
->map
));
5705 /* Return the index of an edge in "graph" that can be used to merge
5706 * two clusters in "c".
5707 * Return graph->n_edge if no such edge can be found.
5708 * Return -1 on error.
5710 * In particular, return a proximity edge between two clusters
5711 * that is not marked "no_merge" and such that neither of the
5712 * two clusters has an incomplete, empty band.
5714 * If there are multiple such edges, then try and find the most
5715 * appropriate edge to use for merging. In particular, pick the edge
5716 * with the greatest weight. If there are multiple of those,
5717 * then pick one with the shortest distance between
5718 * the two cluster representatives.
5720 static int find_proximity(struct isl_sched_graph
*graph
,
5721 struct isl_clustering
*c
)
5723 int i
, best
= graph
->n_edge
, best_dist
, best_weight
;
5725 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5726 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5730 prox
= is_non_empty_proximity(edge
);
5737 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
5738 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
5740 dist
= c
->scc_cluster
[edge
->dst
->scc
] -
5741 c
->scc_cluster
[edge
->src
->scc
];
5744 weight
= edge
->weight
;
5745 if (best
< graph
->n_edge
) {
5746 if (best_weight
> weight
)
5748 if (best_weight
== weight
&& best_dist
<= dist
)
5753 best_weight
= weight
;
5759 /* Internal data structure used in mark_merge_sccs.
5761 * "graph" is the dependence graph in which a strongly connected
5762 * component is constructed.
5763 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
5764 * "src" and "dst" are the indices of the nodes that are being merged.
5766 struct isl_mark_merge_sccs_data
{
5767 struct isl_sched_graph
*graph
;
5773 /* Check whether the cluster containing node "i" depends on the cluster
5774 * containing node "j". If "i" and "j" belong to the same cluster,
5775 * then they are taken to depend on each other to ensure that
5776 * the resulting strongly connected component consists of complete
5777 * clusters. Furthermore, if "i" and "j" are the two nodes that
5778 * are being merged, then they are taken to depend on each other as well.
5779 * Otherwise, check if there is a (conditional) validity dependence
5780 * from node[j] to node[i], forcing node[i] to follow node[j].
5782 static isl_bool
cluster_follows(int i
, int j
, void *user
)
5784 struct isl_mark_merge_sccs_data
*data
= user
;
5785 struct isl_sched_graph
*graph
= data
->graph
;
5786 int *scc_cluster
= data
->scc_cluster
;
5788 if (data
->src
== i
&& data
->dst
== j
)
5789 return isl_bool_true
;
5790 if (data
->src
== j
&& data
->dst
== i
)
5791 return isl_bool_true
;
5792 if (scc_cluster
[graph
->node
[i
].scc
] == scc_cluster
[graph
->node
[j
].scc
])
5793 return isl_bool_true
;
5795 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
5798 /* Mark all SCCs that belong to either of the two clusters in "c"
5799 * connected by the edge in "graph" with index "edge", or to any
5800 * of the intermediate clusters.
5801 * The marking is recorded in c->scc_in_merge.
5803 * The given edge has been selected for merging two clusters,
5804 * meaning that there is at least a proximity edge between the two nodes.
5805 * However, there may also be (indirect) validity dependences
5806 * between the two nodes. When merging the two clusters, all clusters
5807 * containing one or more of the intermediate nodes along the
5808 * indirect validity dependences need to be merged in as well.
5810 * First collect all such nodes by computing the strongly connected
5811 * component (SCC) containing the two nodes connected by the edge, where
5812 * the two nodes are considered to depend on each other to make
5813 * sure they end up in the same SCC. Similarly, each node is considered
5814 * to depend on every other node in the same cluster to ensure
5815 * that the SCC consists of complete clusters.
5817 * Then the original SCCs that contain any of these nodes are marked
5818 * in c->scc_in_merge.
5820 static isl_stat
mark_merge_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5821 int edge
, struct isl_clustering
*c
)
5823 struct isl_mark_merge_sccs_data data
;
5824 struct isl_tarjan_graph
*g
;
5827 for (i
= 0; i
< c
->n
; ++i
)
5828 c
->scc_in_merge
[i
] = 0;
5831 data
.scc_cluster
= c
->scc_cluster
;
5832 data
.src
= graph
->edge
[edge
].src
- graph
->node
;
5833 data
.dst
= graph
->edge
[edge
].dst
- graph
->node
;
5835 g
= isl_tarjan_graph_component(ctx
, graph
->n
, data
.dst
,
5836 &cluster_follows
, &data
);
5842 isl_die(ctx
, isl_error_internal
,
5843 "expecting at least two nodes in component",
5845 if (g
->order
[--i
] != -1)
5846 isl_die(ctx
, isl_error_internal
,
5847 "expecting end of component marker", goto error
);
5849 for (--i
; i
>= 0 && g
->order
[i
] != -1; --i
) {
5850 int scc
= graph
->node
[g
->order
[i
]].scc
;
5851 c
->scc_in_merge
[scc
] = 1;
5854 isl_tarjan_graph_free(g
);
5857 isl_tarjan_graph_free(g
);
5858 return isl_stat_error
;
5861 /* Construct the identifier "cluster_i".
5863 static __isl_give isl_id
*cluster_id(isl_ctx
*ctx
, int i
)
5867 snprintf(name
, sizeof(name
), "cluster_%d", i
);
5868 return isl_id_alloc(ctx
, name
, NULL
);
5871 /* Construct the space of the cluster with index "i" containing
5872 * the strongly connected component "scc".
5874 * In particular, construct a space called cluster_i with dimension equal
5875 * to the number of schedule rows in the current band of "scc".
5877 static __isl_give isl_space
*cluster_space(struct isl_sched_graph
*scc
, int i
)
5883 nvar
= scc
->n_total_row
- scc
->band_start
;
5884 space
= isl_space_copy(scc
->node
[0].space
);
5885 space
= isl_space_params(space
);
5886 space
= isl_space_set_from_params(space
);
5887 space
= isl_space_add_dims(space
, isl_dim_set
, nvar
);
5888 id
= cluster_id(isl_space_get_ctx(space
), i
);
5889 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
5894 /* Collect the domain of the graph for merging clusters.
5896 * In particular, for each cluster with first SCC "i", construct
5897 * a set in the space called cluster_i with dimension equal
5898 * to the number of schedule rows in the current band of the cluster.
5900 static __isl_give isl_union_set
*collect_domain(isl_ctx
*ctx
,
5901 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5905 isl_union_set
*domain
;
5907 space
= isl_space_params_alloc(ctx
, 0);
5908 domain
= isl_union_set_empty(space
);
5910 for (i
= 0; i
< graph
->scc
; ++i
) {
5913 if (!c
->scc_in_merge
[i
])
5915 if (c
->scc_cluster
[i
] != i
)
5917 space
= cluster_space(&c
->scc
[i
], i
);
5918 domain
= isl_union_set_add_set(domain
, isl_set_universe(space
));
5924 /* Construct a map from the original instances to the corresponding
5925 * cluster instance in the current bands of the clusters in "c".
5927 static __isl_give isl_union_map
*collect_cluster_map(isl_ctx
*ctx
,
5928 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5932 isl_union_map
*cluster_map
;
5934 space
= isl_space_params_alloc(ctx
, 0);
5935 cluster_map
= isl_union_map_empty(space
);
5936 for (i
= 0; i
< graph
->scc
; ++i
) {
5940 if (!c
->scc_in_merge
[i
])
5943 id
= cluster_id(ctx
, c
->scc_cluster
[i
]);
5944 start
= c
->scc
[i
].band_start
;
5945 n
= c
->scc
[i
].n_total_row
- start
;
5946 for (j
= 0; j
< c
->scc
[i
].n
; ++j
) {
5949 struct isl_sched_node
*node
= &c
->scc
[i
].node
[j
];
5951 ma
= node_extract_partial_schedule_multi_aff(node
,
5953 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
,
5955 map
= isl_map_from_multi_aff(ma
);
5956 cluster_map
= isl_union_map_add_map(cluster_map
, map
);
5964 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
5965 * that are not isl_edge_condition or isl_edge_conditional_validity.
5967 static __isl_give isl_schedule_constraints
*add_non_conditional_constraints(
5968 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5969 __isl_take isl_schedule_constraints
*sc
)
5971 enum isl_edge_type t
;
5976 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
5977 if (t
== isl_edge_condition
||
5978 t
== isl_edge_conditional_validity
)
5980 if (!is_type(edge
, t
))
5982 sc
= isl_schedule_constraints_add(sc
, t
,
5983 isl_union_map_copy(umap
));
5989 /* Add schedule constraints of types isl_edge_condition and
5990 * isl_edge_conditional_validity to "sc" by applying "umap" to
5991 * the domains of the wrapped relations in domain and range
5992 * of the corresponding tagged constraints of "edge".
5994 static __isl_give isl_schedule_constraints
*add_conditional_constraints(
5995 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5996 __isl_take isl_schedule_constraints
*sc
)
5998 enum isl_edge_type t
;
5999 isl_union_map
*tagged
;
6001 for (t
= isl_edge_condition
; t
<= isl_edge_conditional_validity
; ++t
) {
6002 if (!is_type(edge
, t
))
6004 if (t
== isl_edge_condition
)
6005 tagged
= isl_union_map_copy(edge
->tagged_condition
);
6007 tagged
= isl_union_map_copy(edge
->tagged_validity
);
6008 tagged
= isl_union_map_zip(tagged
);
6009 tagged
= isl_union_map_apply_domain(tagged
,
6010 isl_union_map_copy(umap
));
6011 tagged
= isl_union_map_zip(tagged
);
6012 sc
= isl_schedule_constraints_add(sc
, t
, tagged
);
6020 /* Given a mapping "cluster_map" from the original instances to
6021 * the cluster instances, add schedule constraints on the clusters
6022 * to "sc" corresponding to the original constraints represented by "edge".
6024 * For non-tagged dependence constraints, the cluster constraints
6025 * are obtained by applying "cluster_map" to the edge->map.
6027 * For tagged dependence constraints, "cluster_map" needs to be applied
6028 * to the domains of the wrapped relations in domain and range
6029 * of the tagged dependence constraints. Pick out the mappings
6030 * from these domains from "cluster_map" and construct their product.
6031 * This mapping can then be applied to the pair of domains.
6033 static __isl_give isl_schedule_constraints
*collect_edge_constraints(
6034 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*cluster_map
,
6035 __isl_take isl_schedule_constraints
*sc
)
6037 isl_union_map
*umap
;
6039 isl_union_set
*uset
;
6040 isl_union_map
*umap1
, *umap2
;
6045 umap
= isl_union_map_from_map(isl_map_copy(edge
->map
));
6046 umap
= isl_union_map_apply_domain(umap
,
6047 isl_union_map_copy(cluster_map
));
6048 umap
= isl_union_map_apply_range(umap
,
6049 isl_union_map_copy(cluster_map
));
6050 sc
= add_non_conditional_constraints(edge
, umap
, sc
);
6051 isl_union_map_free(umap
);
6053 if (!sc
|| (!is_condition(edge
) && !is_conditional_validity(edge
)))
6056 space
= isl_space_domain(isl_map_get_space(edge
->map
));
6057 uset
= isl_union_set_from_set(isl_set_universe(space
));
6058 umap1
= isl_union_map_copy(cluster_map
);
6059 umap1
= isl_union_map_intersect_domain(umap1
, uset
);
6060 space
= isl_space_range(isl_map_get_space(edge
->map
));
6061 uset
= isl_union_set_from_set(isl_set_universe(space
));
6062 umap2
= isl_union_map_copy(cluster_map
);
6063 umap2
= isl_union_map_intersect_domain(umap2
, uset
);
6064 umap
= isl_union_map_product(umap1
, umap2
);
6066 sc
= add_conditional_constraints(edge
, umap
, sc
);
6068 isl_union_map_free(umap
);
6072 /* Given a mapping "cluster_map" from the original instances to
6073 * the cluster instances, add schedule constraints on the clusters
6074 * to "sc" corresponding to all edges in "graph" between nodes that
6075 * belong to SCCs that are marked for merging in "scc_in_merge".
6077 static __isl_give isl_schedule_constraints
*collect_constraints(
6078 struct isl_sched_graph
*graph
, int *scc_in_merge
,
6079 __isl_keep isl_union_map
*cluster_map
,
6080 __isl_take isl_schedule_constraints
*sc
)
6084 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6085 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6087 if (!scc_in_merge
[edge
->src
->scc
])
6089 if (!scc_in_merge
[edge
->dst
->scc
])
6091 sc
= collect_edge_constraints(edge
, cluster_map
, sc
);
6097 /* Construct a dependence graph for scheduling clusters with respect
6098 * to each other and store the result in "merge_graph".
6099 * In particular, the nodes of the graph correspond to the schedule
6100 * dimensions of the current bands of those clusters that have been
6101 * marked for merging in "c".
6103 * First construct an isl_schedule_constraints object for this domain
6104 * by transforming the edges in "graph" to the domain.
6105 * Then initialize a dependence graph for scheduling from these
6108 static isl_stat
init_merge_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6109 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
6111 isl_union_set
*domain
;
6112 isl_union_map
*cluster_map
;
6113 isl_schedule_constraints
*sc
;
6116 domain
= collect_domain(ctx
, graph
, c
);
6117 sc
= isl_schedule_constraints_on_domain(domain
);
6119 return isl_stat_error
;
6120 cluster_map
= collect_cluster_map(ctx
, graph
, c
);
6121 sc
= collect_constraints(graph
, c
->scc_in_merge
, cluster_map
, sc
);
6122 isl_union_map_free(cluster_map
);
6124 r
= graph_init(merge_graph
, sc
);
6126 isl_schedule_constraints_free(sc
);
6131 /* Compute the maximal number of remaining schedule rows that still need
6132 * to be computed for the nodes that belong to clusters with the maximal
6133 * dimension for the current band (i.e., the band that is to be merged).
6134 * Only clusters that are about to be merged are considered.
6135 * "maxvar" is the maximal dimension for the current band.
6136 * "c" contains information about the clusters.
6138 * Return the maximal number of remaining schedule rows or -1 on error.
6140 static int compute_maxvar_max_slack(int maxvar
, struct isl_clustering
*c
)
6146 for (i
= 0; i
< c
->n
; ++i
) {
6148 struct isl_sched_graph
*scc
;
6150 if (!c
->scc_in_merge
[i
])
6153 nvar
= scc
->n_total_row
- scc
->band_start
;
6156 for (j
= 0; j
< scc
->n
; ++j
) {
6157 struct isl_sched_node
*node
= &scc
->node
[j
];
6160 if (node_update_vmap(node
) < 0)
6162 slack
= node
->nvar
- node
->rank
;
6163 if (slack
> max_slack
)
6171 /* If there are any clusters where the dimension of the current band
6172 * (i.e., the band that is to be merged) is smaller than "maxvar" and
6173 * if there are any nodes in such a cluster where the number
6174 * of remaining schedule rows that still need to be computed
6175 * is greater than "max_slack", then return the smallest current band
6176 * dimension of all these clusters. Otherwise return the original value
6177 * of "maxvar". Return -1 in case of any error.
6178 * Only clusters that are about to be merged are considered.
6179 * "c" contains information about the clusters.
6181 static int limit_maxvar_to_slack(int maxvar
, int max_slack
,
6182 struct isl_clustering
*c
)
6186 for (i
= 0; i
< c
->n
; ++i
) {
6188 struct isl_sched_graph
*scc
;
6190 if (!c
->scc_in_merge
[i
])
6193 nvar
= scc
->n_total_row
- scc
->band_start
;
6196 for (j
= 0; j
< scc
->n
; ++j
) {
6197 struct isl_sched_node
*node
= &scc
->node
[j
];
6200 if (node_update_vmap(node
) < 0)
6202 slack
= node
->nvar
- node
->rank
;
6203 if (slack
> max_slack
) {
6213 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
6214 * that still need to be computed. In particular, if there is a node
6215 * in a cluster where the dimension of the current band is smaller
6216 * than merge_graph->maxvar, but the number of remaining schedule rows
6217 * is greater than that of any node in a cluster with the maximal
6218 * dimension for the current band (i.e., merge_graph->maxvar),
6219 * then adjust merge_graph->maxvar to the (smallest) current band dimension
6220 * of those clusters. Without this adjustment, the total number of
6221 * schedule dimensions would be increased, resulting in a skewed view
6222 * of the number of coincident dimensions.
6223 * "c" contains information about the clusters.
6225 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
6226 * then there is no point in attempting any merge since it will be rejected
6227 * anyway. Set merge_graph->maxvar to zero in such cases.
6229 static isl_stat
adjust_maxvar_to_slack(isl_ctx
*ctx
,
6230 struct isl_sched_graph
*merge_graph
, struct isl_clustering
*c
)
6232 int max_slack
, maxvar
;
6234 max_slack
= compute_maxvar_max_slack(merge_graph
->maxvar
, c
);
6236 return isl_stat_error
;
6237 maxvar
= limit_maxvar_to_slack(merge_graph
->maxvar
, max_slack
, c
);
6239 return isl_stat_error
;
6241 if (maxvar
< merge_graph
->maxvar
) {
6242 if (isl_options_get_schedule_maximize_band_depth(ctx
))
6243 merge_graph
->maxvar
= 0;
6245 merge_graph
->maxvar
= maxvar
;
6251 /* Return the number of coincident dimensions in the current band of "graph",
6252 * where the nodes of "graph" are assumed to be scheduled by a single band.
6254 static int get_n_coincident(struct isl_sched_graph
*graph
)
6258 for (i
= graph
->band_start
; i
< graph
->n_total_row
; ++i
)
6259 if (!graph
->node
[0].coincident
[i
])
6262 return i
- graph
->band_start
;
6265 /* Should the clusters be merged based on the cluster schedule
6266 * in the current (and only) band of "merge_graph", given that
6267 * coincidence should be maximized?
6269 * If the number of coincident schedule dimensions in the merged band
6270 * would be less than the maximal number of coincident schedule dimensions
6271 * in any of the merged clusters, then the clusters should not be merged.
6273 static isl_bool
ok_to_merge_coincident(struct isl_clustering
*c
,
6274 struct isl_sched_graph
*merge_graph
)
6281 for (i
= 0; i
< c
->n
; ++i
) {
6282 if (!c
->scc_in_merge
[i
])
6284 n_coincident
= get_n_coincident(&c
->scc
[i
]);
6285 if (n_coincident
> max_coincident
)
6286 max_coincident
= n_coincident
;
6289 n_coincident
= get_n_coincident(merge_graph
);
6291 return n_coincident
>= max_coincident
;
6294 /* Return the transformation on "node" expressed by the current (and only)
6295 * band of "merge_graph" applied to the clusters in "c".
6297 * First find the representation of "node" in its SCC in "c" and
6298 * extract the transformation expressed by the current band.
6299 * Then extract the transformation applied by "merge_graph"
6300 * to the cluster to which this SCC belongs.
6301 * Combine the two to obtain the complete transformation on the node.
6303 * Note that the range of the first transformation is an anonymous space,
6304 * while the domain of the second is named "cluster_X". The range
6305 * of the former therefore needs to be adjusted before the two
6308 static __isl_give isl_map
*extract_node_transformation(isl_ctx
*ctx
,
6309 struct isl_sched_node
*node
, struct isl_clustering
*c
,
6310 struct isl_sched_graph
*merge_graph
)
6312 struct isl_sched_node
*scc_node
, *cluster_node
;
6316 isl_multi_aff
*ma
, *ma2
;
6318 scc_node
= graph_find_node(ctx
, &c
->scc
[node
->scc
], node
->space
);
6319 start
= c
->scc
[node
->scc
].band_start
;
6320 n
= c
->scc
[node
->scc
].n_total_row
- start
;
6321 ma
= node_extract_partial_schedule_multi_aff(scc_node
, start
, n
);
6322 space
= cluster_space(&c
->scc
[node
->scc
], c
->scc_cluster
[node
->scc
]);
6323 cluster_node
= graph_find_node(ctx
, merge_graph
, space
);
6324 if (space
&& !cluster_node
)
6325 isl_die(ctx
, isl_error_internal
, "unable to find cluster",
6326 space
= isl_space_free(space
));
6327 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
6328 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
, id
);
6329 isl_space_free(space
);
6330 n
= merge_graph
->n_total_row
;
6331 ma2
= node_extract_partial_schedule_multi_aff(cluster_node
, 0, n
);
6332 ma
= isl_multi_aff_pullback_multi_aff(ma2
, ma
);
6334 return isl_map_from_multi_aff(ma
);
6337 /* Give a set of distances "set", are they bounded by a small constant
6338 * in direction "pos"?
6339 * In practice, check if they are bounded by 2 by checking that there
6340 * are no elements with a value greater than or equal to 3 or
6341 * smaller than or equal to -3.
6343 static isl_bool
distance_is_bounded(__isl_keep isl_set
*set
, int pos
)
6349 return isl_bool_error
;
6351 test
= isl_set_copy(set
);
6352 test
= isl_set_lower_bound_si(test
, isl_dim_set
, pos
, 3);
6353 bounded
= isl_set_is_empty(test
);
6356 if (bounded
< 0 || !bounded
)
6359 test
= isl_set_copy(set
);
6360 test
= isl_set_upper_bound_si(test
, isl_dim_set
, pos
, -3);
6361 bounded
= isl_set_is_empty(test
);
6367 /* Does the set "set" have a fixed (but possible parametric) value
6368 * at dimension "pos"?
6370 static isl_bool
has_single_value(__isl_keep isl_set
*set
, int pos
)
6376 return isl_bool_error
;
6377 set
= isl_set_copy(set
);
6378 n
= isl_set_dim(set
, isl_dim_set
);
6379 set
= isl_set_project_out(set
, isl_dim_set
, pos
+ 1, n
- (pos
+ 1));
6380 set
= isl_set_project_out(set
, isl_dim_set
, 0, pos
);
6381 single
= isl_set_is_singleton(set
);
6387 /* Does "map" have a fixed (but possible parametric) value
6388 * at dimension "pos" of either its domain or its range?
6390 static isl_bool
has_singular_src_or_dst(__isl_keep isl_map
*map
, int pos
)
6395 set
= isl_map_domain(isl_map_copy(map
));
6396 single
= has_single_value(set
, pos
);
6399 if (single
< 0 || single
)
6402 set
= isl_map_range(isl_map_copy(map
));
6403 single
= has_single_value(set
, pos
);
6409 /* Does the edge "edge" from "graph" have bounded dependence distances
6410 * in the merged graph "merge_graph" of a selection of clusters in "c"?
6412 * Extract the complete transformations of the source and destination
6413 * nodes of the edge, apply them to the edge constraints and
6414 * compute the differences. Finally, check if these differences are bounded
6415 * in each direction.
6417 * If the dimension of the band is greater than the number of
6418 * dimensions that can be expected to be optimized by the edge
6419 * (based on its weight), then also allow the differences to be unbounded
6420 * in the remaining dimensions, but only if either the source or
6421 * the destination has a fixed value in that direction.
6422 * This allows a statement that produces values that are used by
6423 * several instances of another statement to be merged with that
6425 * However, merging such clusters will introduce an inherently
6426 * large proximity distance inside the merged cluster, meaning
6427 * that proximity distances will no longer be optimized in
6428 * subsequent merges. These merges are therefore only allowed
6429 * after all other possible merges have been tried.
6430 * The first time such a merge is encountered, the weight of the edge
6431 * is replaced by a negative weight. The second time (i.e., after
6432 * all merges over edges with a non-negative weight have been tried),
6433 * the merge is allowed.
6435 static isl_bool
has_bounded_distances(isl_ctx
*ctx
, struct isl_sched_edge
*edge
,
6436 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
6437 struct isl_sched_graph
*merge_graph
)
6444 map
= isl_map_copy(edge
->map
);
6445 t
= extract_node_transformation(ctx
, edge
->src
, c
, merge_graph
);
6446 map
= isl_map_apply_domain(map
, t
);
6447 t
= extract_node_transformation(ctx
, edge
->dst
, c
, merge_graph
);
6448 map
= isl_map_apply_range(map
, t
);
6449 dist
= isl_map_deltas(isl_map_copy(map
));
6451 bounded
= isl_bool_true
;
6452 n
= isl_set_dim(dist
, isl_dim_set
);
6453 n_slack
= n
- edge
->weight
;
6454 if (edge
->weight
< 0)
6455 n_slack
-= graph
->max_weight
+ 1;
6456 for (i
= 0; i
< n
; ++i
) {
6457 isl_bool bounded_i
, singular_i
;
6459 bounded_i
= distance_is_bounded(dist
, i
);
6464 if (edge
->weight
>= 0)
6465 bounded
= isl_bool_false
;
6469 singular_i
= has_singular_src_or_dst(map
, i
);
6474 bounded
= isl_bool_false
;
6477 if (!bounded
&& i
>= n
&& edge
->weight
>= 0)
6478 edge
->weight
-= graph
->max_weight
+ 1;
6486 return isl_bool_error
;
6489 /* Should the clusters be merged based on the cluster schedule
6490 * in the current (and only) band of "merge_graph"?
6491 * "graph" is the original dependence graph, while "c" records
6492 * which SCCs are involved in the latest merge.
6494 * In particular, is there at least one proximity constraint
6495 * that is optimized by the merge?
6497 * A proximity constraint is considered to be optimized
6498 * if the dependence distances are small.
6500 static isl_bool
ok_to_merge_proximity(isl_ctx
*ctx
,
6501 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
6502 struct isl_sched_graph
*merge_graph
)
6506 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6507 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6510 if (!is_proximity(edge
))
6512 if (!c
->scc_in_merge
[edge
->src
->scc
])
6514 if (!c
->scc_in_merge
[edge
->dst
->scc
])
6516 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6517 c
->scc_cluster
[edge
->src
->scc
])
6519 bounded
= has_bounded_distances(ctx
, edge
, graph
, c
,
6521 if (bounded
< 0 || bounded
)
6525 return isl_bool_false
;
6528 /* Should the clusters be merged based on the cluster schedule
6529 * in the current (and only) band of "merge_graph"?
6530 * "graph" is the original dependence graph, while "c" records
6531 * which SCCs are involved in the latest merge.
6533 * If the current band is empty, then the clusters should not be merged.
6535 * If the band depth should be maximized and the merge schedule
6536 * is incomplete (meaning that the dimension of some of the schedule
6537 * bands in the original schedule will be reduced), then the clusters
6538 * should not be merged.
6540 * If the schedule_maximize_coincidence option is set, then check that
6541 * the number of coincident schedule dimensions is not reduced.
6543 * Finally, only allow the merge if at least one proximity
6544 * constraint is optimized.
6546 static isl_bool
ok_to_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6547 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
6549 if (merge_graph
->n_total_row
== merge_graph
->band_start
)
6550 return isl_bool_false
;
6552 if (isl_options_get_schedule_maximize_band_depth(ctx
) &&
6553 merge_graph
->n_total_row
< merge_graph
->maxvar
)
6554 return isl_bool_false
;
6556 if (isl_options_get_schedule_maximize_coincidence(ctx
)) {
6559 ok
= ok_to_merge_coincident(c
, merge_graph
);
6564 return ok_to_merge_proximity(ctx
, graph
, c
, merge_graph
);
6567 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
6568 * of the schedule in "node" and return the result.
6570 * That is, essentially compute
6572 * T * N(first:first+n-1)
6574 * taking into account the constant term and the parameter coefficients
6577 static __isl_give isl_mat
*node_transformation(isl_ctx
*ctx
,
6578 struct isl_sched_node
*t_node
, struct isl_sched_node
*node
,
6583 int n_row
, n_col
, n_param
, n_var
;
6585 n_param
= node
->nparam
;
6587 n_row
= isl_mat_rows(t_node
->sched
);
6588 n_col
= isl_mat_cols(node
->sched
);
6589 t
= isl_mat_alloc(ctx
, n_row
, n_col
);
6592 for (i
= 0; i
< n_row
; ++i
) {
6593 isl_seq_cpy(t
->row
[i
], t_node
->sched
->row
[i
], 1 + n_param
);
6594 isl_seq_clr(t
->row
[i
] + 1 + n_param
, n_var
);
6595 for (j
= 0; j
< n
; ++j
)
6596 isl_seq_addmul(t
->row
[i
],
6597 t_node
->sched
->row
[i
][1 + n_param
+ j
],
6598 node
->sched
->row
[first
+ j
],
6599 1 + n_param
+ n_var
);
6604 /* Apply the cluster schedule in "t_node" to the current band
6605 * schedule of the nodes in "graph".
6607 * In particular, replace the rows starting at band_start
6608 * by the result of applying the cluster schedule in "t_node"
6609 * to the original rows.
6611 * The coincidence of the schedule is determined by the coincidence
6612 * of the cluster schedule.
6614 static isl_stat
transform(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6615 struct isl_sched_node
*t_node
)
6621 start
= graph
->band_start
;
6622 n
= graph
->n_total_row
- start
;
6624 n_new
= isl_mat_rows(t_node
->sched
);
6625 for (i
= 0; i
< graph
->n
; ++i
) {
6626 struct isl_sched_node
*node
= &graph
->node
[i
];
6629 t
= node_transformation(ctx
, t_node
, node
, start
, n
);
6630 node
->sched
= isl_mat_drop_rows(node
->sched
, start
, n
);
6631 node
->sched
= isl_mat_concat(node
->sched
, t
);
6632 node
->sched_map
= isl_map_free(node
->sched_map
);
6634 return isl_stat_error
;
6635 for (j
= 0; j
< n_new
; ++j
)
6636 node
->coincident
[start
+ j
] = t_node
->coincident
[j
];
6638 graph
->n_total_row
-= n
;
6640 graph
->n_total_row
+= n_new
;
6641 graph
->n_row
+= n_new
;
6646 /* Merge the clusters marked for merging in "c" into a single
6647 * cluster using the cluster schedule in the current band of "merge_graph".
6648 * The representative SCC for the new cluster is the SCC with
6649 * the smallest index.
6651 * The current band schedule of each SCC in the new cluster is obtained
6652 * by applying the schedule of the corresponding original cluster
6653 * to the original band schedule.
6654 * All SCCs in the new cluster have the same number of schedule rows.
6656 static isl_stat
merge(isl_ctx
*ctx
, struct isl_clustering
*c
,
6657 struct isl_sched_graph
*merge_graph
)
6663 for (i
= 0; i
< c
->n
; ++i
) {
6664 struct isl_sched_node
*node
;
6666 if (!c
->scc_in_merge
[i
])
6670 space
= cluster_space(&c
->scc
[i
], c
->scc_cluster
[i
]);
6672 return isl_stat_error
;
6673 node
= graph_find_node(ctx
, merge_graph
, space
);
6674 isl_space_free(space
);
6676 isl_die(ctx
, isl_error_internal
,
6677 "unable to find cluster",
6678 return isl_stat_error
);
6679 if (transform(ctx
, &c
->scc
[i
], node
) < 0)
6680 return isl_stat_error
;
6681 c
->scc_cluster
[i
] = cluster
;
6687 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
6688 * by scheduling the current cluster bands with respect to each other.
6690 * Construct a dependence graph with a space for each cluster and
6691 * with the coordinates of each space corresponding to the schedule
6692 * dimensions of the current band of that cluster.
6693 * Construct a cluster schedule in this cluster dependence graph and
6694 * apply it to the current cluster bands if it is applicable
6695 * according to ok_to_merge.
6697 * If the number of remaining schedule dimensions in a cluster
6698 * with a non-maximal current schedule dimension is greater than
6699 * the number of remaining schedule dimensions in clusters
6700 * with a maximal current schedule dimension, then restrict
6701 * the number of rows to be computed in the cluster schedule
6702 * to the minimal such non-maximal current schedule dimension.
6703 * Do this by adjusting merge_graph.maxvar.
6705 * Return isl_bool_true if the clusters have effectively been merged
6706 * into a single cluster.
6708 * Note that since the standard scheduling algorithm minimizes the maximal
6709 * distance over proximity constraints, the proximity constraints between
6710 * the merged clusters may not be optimized any further than what is
6711 * sufficient to bring the distances within the limits of the internal
6712 * proximity constraints inside the individual clusters.
6713 * It may therefore make sense to perform an additional translation step
6714 * to bring the clusters closer to each other, while maintaining
6715 * the linear part of the merging schedule found using the standard
6716 * scheduling algorithm.
6718 static isl_bool
try_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6719 struct isl_clustering
*c
)
6721 struct isl_sched_graph merge_graph
= { 0 };
6724 if (init_merge_graph(ctx
, graph
, c
, &merge_graph
) < 0)
6727 if (compute_maxvar(&merge_graph
) < 0)
6729 if (adjust_maxvar_to_slack(ctx
, &merge_graph
,c
) < 0)
6731 if (compute_schedule_wcc_band(ctx
, &merge_graph
) < 0)
6733 merged
= ok_to_merge(ctx
, graph
, c
, &merge_graph
);
6734 if (merged
&& merge(ctx
, c
, &merge_graph
) < 0)
6737 graph_free(ctx
, &merge_graph
);
6740 graph_free(ctx
, &merge_graph
);
6741 return isl_bool_error
;
6744 /* Is there any edge marked "no_merge" between two SCCs that are
6745 * about to be merged (i.e., that are set in "scc_in_merge")?
6746 * "merge_edge" is the proximity edge along which the clusters of SCCs
6747 * are going to be merged.
6749 * If there is any edge between two SCCs with a negative weight,
6750 * while the weight of "merge_edge" is non-negative, then this
6751 * means that the edge was postponed. "merge_edge" should then
6752 * also be postponed since merging along the edge with negative weight should
6753 * be postponed until all edges with non-negative weight have been tried.
6754 * Replace the weight of "merge_edge" by a negative weight as well and
6755 * tell the caller not to attempt a merge.
6757 static int any_no_merge(struct isl_sched_graph
*graph
, int *scc_in_merge
,
6758 struct isl_sched_edge
*merge_edge
)
6762 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6763 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6765 if (!scc_in_merge
[edge
->src
->scc
])
6767 if (!scc_in_merge
[edge
->dst
->scc
])
6771 if (merge_edge
->weight
>= 0 && edge
->weight
< 0) {
6772 merge_edge
->weight
-= graph
->max_weight
+ 1;
6780 /* Merge the two clusters in "c" connected by the edge in "graph"
6781 * with index "edge" into a single cluster.
6782 * If it turns out to be impossible to merge these two clusters,
6783 * then mark the edge as "no_merge" such that it will not be
6786 * First mark all SCCs that need to be merged. This includes the SCCs
6787 * in the two clusters, but it may also include the SCCs
6788 * of intermediate clusters.
6789 * If there is already a no_merge edge between any pair of such SCCs,
6790 * then simply mark the current edge as no_merge as well.
6791 * Likewise, if any of those edges was postponed by has_bounded_distances,
6792 * then postpone the current edge as well.
6793 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
6794 * if the clusters did not end up getting merged, unless the non-merge
6795 * is due to the fact that the edge was postponed. This postponement
6796 * can be recognized by a change in weight (from non-negative to negative).
6798 static isl_stat
merge_clusters_along_edge(isl_ctx
*ctx
,
6799 struct isl_sched_graph
*graph
, int edge
, struct isl_clustering
*c
)
6802 int edge_weight
= graph
->edge
[edge
].weight
;
6804 if (mark_merge_sccs(ctx
, graph
, edge
, c
) < 0)
6805 return isl_stat_error
;
6807 if (any_no_merge(graph
, c
->scc_in_merge
, &graph
->edge
[edge
]))
6808 merged
= isl_bool_false
;
6810 merged
= try_merge(ctx
, graph
, c
);
6812 return isl_stat_error
;
6813 if (!merged
&& edge_weight
== graph
->edge
[edge
].weight
)
6814 graph
->edge
[edge
].no_merge
= 1;
6819 /* Does "node" belong to the cluster identified by "cluster"?
6821 static int node_cluster_exactly(struct isl_sched_node
*node
, int cluster
)
6823 return node
->cluster
== cluster
;
6826 /* Does "edge" connect two nodes belonging to the cluster
6827 * identified by "cluster"?
6829 static int edge_cluster_exactly(struct isl_sched_edge
*edge
, int cluster
)
6831 return edge
->src
->cluster
== cluster
&& edge
->dst
->cluster
== cluster
;
6834 /* Swap the schedule of "node1" and "node2".
6835 * Both nodes have been derived from the same node in a common parent graph.
6836 * Since the "coincident" field is shared with that node
6837 * in the parent graph, there is no need to also swap this field.
6839 static void swap_sched(struct isl_sched_node
*node1
,
6840 struct isl_sched_node
*node2
)
6845 sched
= node1
->sched
;
6846 node1
->sched
= node2
->sched
;
6847 node2
->sched
= sched
;
6849 sched_map
= node1
->sched_map
;
6850 node1
->sched_map
= node2
->sched_map
;
6851 node2
->sched_map
= sched_map
;
6854 /* Copy the current band schedule from the SCCs that form the cluster
6855 * with index "pos" to the actual cluster at position "pos".
6856 * By construction, the index of the first SCC that belongs to the cluster
6859 * The order of the nodes inside both the SCCs and the cluster
6860 * is assumed to be same as the order in the original "graph".
6862 * Since the SCC graphs will no longer be used after this function,
6863 * the schedules are actually swapped rather than copied.
6865 static isl_stat
copy_partial(struct isl_sched_graph
*graph
,
6866 struct isl_clustering
*c
, int pos
)
6870 c
->cluster
[pos
].n_total_row
= c
->scc
[pos
].n_total_row
;
6871 c
->cluster
[pos
].n_row
= c
->scc
[pos
].n_row
;
6872 c
->cluster
[pos
].maxvar
= c
->scc
[pos
].maxvar
;
6874 for (i
= 0; i
< graph
->n
; ++i
) {
6878 if (graph
->node
[i
].cluster
!= pos
)
6880 s
= graph
->node
[i
].scc
;
6881 k
= c
->scc_node
[s
]++;
6882 swap_sched(&c
->cluster
[pos
].node
[j
], &c
->scc
[s
].node
[k
]);
6883 if (c
->scc
[s
].maxvar
> c
->cluster
[pos
].maxvar
)
6884 c
->cluster
[pos
].maxvar
= c
->scc
[s
].maxvar
;
6891 /* Is there a (conditional) validity dependence from node[j] to node[i],
6892 * forcing node[i] to follow node[j] or do the nodes belong to the same
6895 static isl_bool
node_follows_strong_or_same_cluster(int i
, int j
, void *user
)
6897 struct isl_sched_graph
*graph
= user
;
6899 if (graph
->node
[i
].cluster
== graph
->node
[j
].cluster
)
6900 return isl_bool_true
;
6901 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
6904 /* Extract the merged clusters of SCCs in "graph", sort them, and
6905 * store them in c->clusters. Update c->scc_cluster accordingly.
6907 * First keep track of the cluster containing the SCC to which a node
6908 * belongs in the node itself.
6909 * Then extract the clusters into c->clusters, copying the current
6910 * band schedule from the SCCs that belong to the cluster.
6911 * Do this only once per cluster.
6913 * Finally, topologically sort the clusters and update c->scc_cluster
6914 * to match the new scc numbering. While the SCCs were originally
6915 * sorted already, some SCCs that depend on some other SCCs may
6916 * have been merged with SCCs that appear before these other SCCs.
6917 * A reordering may therefore be required.
6919 static isl_stat
extract_clusters(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6920 struct isl_clustering
*c
)
6924 for (i
= 0; i
< graph
->n
; ++i
)
6925 graph
->node
[i
].cluster
= c
->scc_cluster
[graph
->node
[i
].scc
];
6927 for (i
= 0; i
< graph
->scc
; ++i
) {
6928 if (c
->scc_cluster
[i
] != i
)
6930 if (extract_sub_graph(ctx
, graph
, &node_cluster_exactly
,
6931 &edge_cluster_exactly
, i
, &c
->cluster
[i
]) < 0)
6932 return isl_stat_error
;
6933 c
->cluster
[i
].src_scc
= -1;
6934 c
->cluster
[i
].dst_scc
= -1;
6935 if (copy_partial(graph
, c
, i
) < 0)
6936 return isl_stat_error
;
6939 if (detect_ccs(ctx
, graph
, &node_follows_strong_or_same_cluster
) < 0)
6940 return isl_stat_error
;
6941 for (i
= 0; i
< graph
->n
; ++i
)
6942 c
->scc_cluster
[graph
->node
[i
].scc
] = graph
->node
[i
].cluster
;
6947 /* Compute weights on the proximity edges of "graph" that can
6948 * be used by find_proximity to find the most appropriate
6949 * proximity edge to use to merge two clusters in "c".
6950 * The weights are also used by has_bounded_distances to determine
6951 * whether the merge should be allowed.
6952 * Store the maximum of the computed weights in graph->max_weight.
6954 * The computed weight is a measure for the number of remaining schedule
6955 * dimensions that can still be completely aligned.
6956 * In particular, compute the number of equalities between
6957 * input dimensions and output dimensions in the proximity constraints.
6958 * The directions that are already handled by outer schedule bands
6959 * are projected out prior to determining this number.
6961 * Edges that will never be considered by find_proximity are ignored.
6963 static isl_stat
compute_weights(struct isl_sched_graph
*graph
,
6964 struct isl_clustering
*c
)
6968 graph
->max_weight
= 0;
6970 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6971 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6972 struct isl_sched_node
*src
= edge
->src
;
6973 struct isl_sched_node
*dst
= edge
->dst
;
6974 isl_basic_map
*hull
;
6978 prox
= is_non_empty_proximity(edge
);
6980 return isl_stat_error
;
6983 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
6984 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
6986 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6987 c
->scc_cluster
[edge
->src
->scc
])
6990 hull
= isl_map_affine_hull(isl_map_copy(edge
->map
));
6991 hull
= isl_basic_map_transform_dims(hull
, isl_dim_in
, 0,
6992 isl_mat_copy(src
->vmap
));
6993 hull
= isl_basic_map_transform_dims(hull
, isl_dim_out
, 0,
6994 isl_mat_copy(dst
->vmap
));
6995 hull
= isl_basic_map_project_out(hull
,
6996 isl_dim_in
, 0, src
->rank
);
6997 hull
= isl_basic_map_project_out(hull
,
6998 isl_dim_out
, 0, dst
->rank
);
6999 hull
= isl_basic_map_remove_divs(hull
);
7000 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
7001 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
7002 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
7003 isl_dim_in
, 0, n_in
);
7004 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
7005 isl_dim_out
, 0, n_out
);
7007 return isl_stat_error
;
7008 edge
->weight
= isl_basic_map_n_equality(hull
);
7009 isl_basic_map_free(hull
);
7011 if (edge
->weight
> graph
->max_weight
)
7012 graph
->max_weight
= edge
->weight
;
7018 /* Call compute_schedule_finish_band on each of the clusters in "c"
7019 * in their topological order. This order is determined by the scc
7020 * fields of the nodes in "graph".
7021 * Combine the results in a sequence expressing the topological order.
7023 * If there is only one cluster left, then there is no need to introduce
7024 * a sequence node. Also, in this case, the cluster necessarily contains
7025 * the SCC at position 0 in the original graph and is therefore also
7026 * stored in the first cluster of "c".
7028 static __isl_give isl_schedule_node
*finish_bands_clustering(
7029 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
7030 struct isl_clustering
*c
)
7034 isl_union_set_list
*filters
;
7036 if (graph
->scc
== 1)
7037 return compute_schedule_finish_band(node
, &c
->cluster
[0], 0);
7039 ctx
= isl_schedule_node_get_ctx(node
);
7041 filters
= extract_sccs(ctx
, graph
);
7042 node
= isl_schedule_node_insert_sequence(node
, filters
);
7044 for (i
= 0; i
< graph
->scc
; ++i
) {
7045 int j
= c
->scc_cluster
[i
];
7046 node
= isl_schedule_node_child(node
, i
);
7047 node
= isl_schedule_node_child(node
, 0);
7048 node
= compute_schedule_finish_band(node
, &c
->cluster
[j
], 0);
7049 node
= isl_schedule_node_parent(node
);
7050 node
= isl_schedule_node_parent(node
);
7056 /* Compute a schedule for a connected dependence graph by first considering
7057 * each strongly connected component (SCC) in the graph separately and then
7058 * incrementally combining them into clusters.
7059 * Return the updated schedule node.
7061 * Initially, each cluster consists of a single SCC, each with its
7062 * own band schedule. The algorithm then tries to merge pairs
7063 * of clusters along a proximity edge until no more suitable
7064 * proximity edges can be found. During this merging, the schedule
7065 * is maintained in the individual SCCs.
7066 * After the merging is completed, the full resulting clusters
7067 * are extracted and in finish_bands_clustering,
7068 * compute_schedule_finish_band is called on each of them to integrate
7069 * the band into "node" and to continue the computation.
7071 * compute_weights initializes the weights that are used by find_proximity.
7073 static __isl_give isl_schedule_node
*compute_schedule_wcc_clustering(
7074 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
7077 struct isl_clustering c
;
7080 ctx
= isl_schedule_node_get_ctx(node
);
7082 if (clustering_init(ctx
, &c
, graph
) < 0)
7085 if (compute_weights(graph
, &c
) < 0)
7089 i
= find_proximity(graph
, &c
);
7092 if (i
>= graph
->n_edge
)
7094 if (merge_clusters_along_edge(ctx
, graph
, i
, &c
) < 0)
7098 if (extract_clusters(ctx
, graph
, &c
) < 0)
7101 node
= finish_bands_clustering(node
, graph
, &c
);
7103 clustering_free(ctx
, &c
);
7106 clustering_free(ctx
, &c
);
7107 return isl_schedule_node_free(node
);
7110 /* Compute a schedule for a connected dependence graph and return
7111 * the updated schedule node.
7113 * If Feautrier's algorithm is selected, we first recursively try to satisfy
7114 * as many validity dependences as possible. When all validity dependences
7115 * are satisfied we extend the schedule to a full-dimensional schedule.
7117 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
7118 * depending on whether the user has selected the option to try and
7119 * compute a schedule for the entire (weakly connected) component first.
7120 * If there is only a single strongly connected component (SCC), then
7121 * there is no point in trying to combine SCCs
7122 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
7123 * is called instead.
7125 static __isl_give isl_schedule_node
*compute_schedule_wcc(
7126 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
7133 ctx
= isl_schedule_node_get_ctx(node
);
7134 if (detect_sccs(ctx
, graph
) < 0)
7135 return isl_schedule_node_free(node
);
7137 if (compute_maxvar(graph
) < 0)
7138 return isl_schedule_node_free(node
);
7140 if (need_feautrier_step(ctx
, graph
))
7141 return compute_schedule_wcc_feautrier(node
, graph
);
7143 if (graph
->scc
<= 1 || isl_options_get_schedule_whole_component(ctx
))
7144 return compute_schedule_wcc_whole(node
, graph
);
7146 return compute_schedule_wcc_clustering(node
, graph
);
7149 /* Compute a schedule for each group of nodes identified by node->scc
7150 * separately and then combine them in a sequence node (or as set node
7151 * if graph->weak is set) inserted at position "node" of the schedule tree.
7152 * Return the updated schedule node.
7154 * If "wcc" is set then each of the groups belongs to a single
7155 * weakly connected component in the dependence graph so that
7156 * there is no need for compute_sub_schedule to look for weakly
7157 * connected components.
7159 static __isl_give isl_schedule_node
*compute_component_schedule(
7160 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
7165 isl_union_set_list
*filters
;
7169 ctx
= isl_schedule_node_get_ctx(node
);
7171 filters
= extract_sccs(ctx
, graph
);
7173 node
= isl_schedule_node_insert_set(node
, filters
);
7175 node
= isl_schedule_node_insert_sequence(node
, filters
);
7177 for (component
= 0; component
< graph
->scc
; ++component
) {
7178 node
= isl_schedule_node_child(node
, component
);
7179 node
= isl_schedule_node_child(node
, 0);
7180 node
= compute_sub_schedule(node
, ctx
, graph
,
7182 &edge_scc_exactly
, component
, wcc
);
7183 node
= isl_schedule_node_parent(node
);
7184 node
= isl_schedule_node_parent(node
);
7190 /* Compute a schedule for the given dependence graph and insert it at "node".
7191 * Return the updated schedule node.
7193 * We first check if the graph is connected (through validity and conditional
7194 * validity dependences) and, if not, compute a schedule
7195 * for each component separately.
7196 * If the schedule_serialize_sccs option is set, then we check for strongly
7197 * connected components instead and compute a separate schedule for
7198 * each such strongly connected component.
7200 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
7201 struct isl_sched_graph
*graph
)
7208 ctx
= isl_schedule_node_get_ctx(node
);
7209 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
7210 if (detect_sccs(ctx
, graph
) < 0)
7211 return isl_schedule_node_free(node
);
7213 if (detect_wccs(ctx
, graph
) < 0)
7214 return isl_schedule_node_free(node
);
7218 return compute_component_schedule(node
, graph
, 1);
7220 return compute_schedule_wcc(node
, graph
);
7223 /* Compute a schedule on sc->domain that respects the given schedule
7226 * In particular, the schedule respects all the validity dependences.
7227 * If the default isl scheduling algorithm is used, it tries to minimize
7228 * the dependence distances over the proximity dependences.
7229 * If Feautrier's scheduling algorithm is used, the proximity dependence
7230 * distances are only minimized during the extension to a full-dimensional
7233 * If there are any condition and conditional validity dependences,
7234 * then the conditional validity dependences may be violated inside
7235 * a tilable band, provided they have no adjacent non-local
7236 * condition dependences.
7238 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
7239 __isl_take isl_schedule_constraints
*sc
)
7241 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
7242 struct isl_sched_graph graph
= { 0 };
7243 isl_schedule
*sched
;
7244 isl_schedule_node
*node
;
7245 isl_union_set
*domain
;
7247 sc
= isl_schedule_constraints_align_params(sc
);
7249 domain
= isl_schedule_constraints_get_domain(sc
);
7250 if (isl_union_set_n_set(domain
) == 0) {
7251 isl_schedule_constraints_free(sc
);
7252 return isl_schedule_from_domain(domain
);
7255 if (graph_init(&graph
, sc
) < 0)
7256 domain
= isl_union_set_free(domain
);
7258 node
= isl_schedule_node_from_domain(domain
);
7259 node
= isl_schedule_node_child(node
, 0);
7261 node
= compute_schedule(node
, &graph
);
7262 sched
= isl_schedule_node_get_schedule(node
);
7263 isl_schedule_node_free(node
);
7265 graph_free(ctx
, &graph
);
7266 isl_schedule_constraints_free(sc
);
7271 /* Compute a schedule for the given union of domains that respects
7272 * all the validity dependences and minimizes
7273 * the dependence distances over the proximity dependences.
7275 * This function is kept for backward compatibility.
7277 __isl_give isl_schedule
*isl_union_set_compute_schedule(
7278 __isl_take isl_union_set
*domain
,
7279 __isl_take isl_union_map
*validity
,
7280 __isl_take isl_union_map
*proximity
)
7282 isl_schedule_constraints
*sc
;
7284 sc
= isl_schedule_constraints_on_domain(domain
);
7285 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
7286 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
7288 return isl_schedule_constraints_compute_schedule(sc
);