2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015-2016 Sven Verdoolaege
5 * Copyright 2016 INRIA Paris
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
14 * CS 42112, 75589 Paris Cedex 12, France
17 #include <isl_ctx_private.h>
18 #include <isl_map_private.h>
19 #include <isl_space_private.h>
20 #include <isl_aff_private.h>
22 #include <isl/constraint.h>
23 #include <isl/schedule.h>
24 #include <isl_schedule_constraints.h>
25 #include <isl/schedule_node.h>
26 #include <isl_mat_private.h>
27 #include <isl_vec_private.h>
29 #include <isl/union_set.h>
32 #include <isl_dim_map.h>
33 #include <isl/map_to_basic_set.h>
35 #include <isl_options_private.h>
36 #include <isl_tarjan.h>
37 #include <isl_morph.h>
39 #include <isl_val_private.h>
42 * The scheduling algorithm implemented in this file was inspired by
43 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
44 * Parallelization and Locality Optimization in the Polyhedral Model".
48 /* Internal information about a node that is used during the construction
50 * space represents the space in which the domain lives
51 * sched is a matrix representation of the schedule being constructed
52 * for this node; if compressed is set, then this schedule is
53 * defined over the compressed domain space
54 * sched_map is an isl_map representation of the same (partial) schedule
55 * sched_map may be NULL; if compressed is set, then this map
56 * is defined over the uncompressed domain space
57 * rank is the number of linearly independent rows in the linear part
59 * the columns of cmap represent a change of basis for the schedule
60 * coefficients; the first rank columns span the linear part of
62 * cinv is the inverse of cmap.
63 * ctrans is the transpose of cmap.
64 * start is the first variable in the LP problem in the sequences that
65 * represents the schedule coefficients of this node
66 * nvar is the dimension of the domain
67 * nparam is the number of parameters or 0 if we are not constructing
68 * a parametric schedule
70 * If compressed is set, then hull represents the constraints
71 * that were used to derive the compression, while compress and
72 * decompress map the original space to the compressed space and
75 * scc is the index of SCC (or WCC) this node belongs to
77 * "cluster" is only used inside extract_clusters and identifies
78 * the cluster of SCCs that the node belongs to.
80 * coincident contains a boolean for each of the rows of the schedule,
81 * indicating whether the corresponding scheduling dimension satisfies
82 * the coincidence constraints in the sense that the corresponding
83 * dependence distances are zero.
85 * If the schedule_treat_coalescing option is set, then
86 * "sizes" contains the sizes of the (compressed) instance set
87 * in each direction. If there is no fixed size in a given direction,
88 * then the corresponding size value is set to infinity.
89 * If the schedule_treat_coalescing option or the schedule_max_coefficient
90 * option is set, then "max" contains the maximal values for
91 * schedule coefficients of the (compressed) variables. If no bound
92 * needs to be imposed on a particular variable, then the corresponding
95 struct isl_sched_node
{
99 isl_multi_aff
*compress
;
100 isl_multi_aff
*decompress
;
116 isl_multi_val
*sizes
;
120 static int node_has_space(const void *entry
, const void *val
)
122 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
123 isl_space
*dim
= (isl_space
*)val
;
125 return isl_space_is_equal(node
->space
, dim
);
128 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
130 return node
->scc
== scc
;
133 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
135 return node
->scc
<= scc
;
138 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
140 return node
->scc
>= scc
;
143 /* An edge in the dependence graph. An edge may be used to
144 * ensure validity of the generated schedule, to minimize the dependence
147 * map is the dependence relation, with i -> j in the map if j depends on i
148 * tagged_condition and tagged_validity contain the union of all tagged
149 * condition or conditional validity dependence relations that
150 * specialize the dependence relation "map"; that is,
151 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
152 * or "tagged_validity", then i -> j is an element of "map".
153 * If these fields are NULL, then they represent the empty relation.
154 * src is the source node
155 * dst is the sink node
157 * types is a bit vector containing the types of this edge.
158 * validity is set if the edge is used to ensure correctness
159 * coincidence is used to enforce zero dependence distances
160 * proximity is set if the edge is used to minimize dependence distances
161 * condition is set if the edge represents a condition
162 * for a conditional validity schedule constraint
163 * local can only be set for condition edges and indicates that
164 * the dependence distance over the edge should be zero
165 * conditional_validity is set if the edge is used to conditionally
168 * For validity edges, start and end mark the sequence of inequality
169 * constraints in the LP problem that encode the validity constraint
170 * corresponding to this edge.
172 * During clustering, an edge may be marked "no_merge" if it should
173 * not be used to merge clusters.
174 * The weight is also only used during clustering and it is
175 * an indication of how many schedule dimensions on either side
176 * of the schedule constraints can be aligned.
177 * If the weight is negative, then this means that this edge was postponed
178 * by has_bounded_distances or any_no_merge. The original weight can
179 * be retrieved by adding 1 + graph->max_weight, with "graph"
180 * the graph containing this edge.
182 struct isl_sched_edge
{
184 isl_union_map
*tagged_condition
;
185 isl_union_map
*tagged_validity
;
187 struct isl_sched_node
*src
;
188 struct isl_sched_node
*dst
;
199 /* Is "edge" marked as being of type "type"?
201 static int is_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
203 return ISL_FL_ISSET(edge
->types
, 1 << type
);
206 /* Mark "edge" as being of type "type".
208 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
210 ISL_FL_SET(edge
->types
, 1 << type
);
213 /* No longer mark "edge" as being of type "type"?
215 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
217 ISL_FL_CLR(edge
->types
, 1 << type
);
220 /* Is "edge" marked as a validity edge?
222 static int is_validity(struct isl_sched_edge
*edge
)
224 return is_type(edge
, isl_edge_validity
);
227 /* Mark "edge" as a validity edge.
229 static void set_validity(struct isl_sched_edge
*edge
)
231 set_type(edge
, isl_edge_validity
);
234 /* Is "edge" marked as a proximity edge?
236 static int is_proximity(struct isl_sched_edge
*edge
)
238 return is_type(edge
, isl_edge_proximity
);
241 /* Is "edge" marked as a local edge?
243 static int is_local(struct isl_sched_edge
*edge
)
245 return is_type(edge
, isl_edge_local
);
248 /* Mark "edge" as a local edge.
250 static void set_local(struct isl_sched_edge
*edge
)
252 set_type(edge
, isl_edge_local
);
255 /* No longer mark "edge" as a local edge.
257 static void clear_local(struct isl_sched_edge
*edge
)
259 clear_type(edge
, isl_edge_local
);
262 /* Is "edge" marked as a coincidence edge?
264 static int is_coincidence(struct isl_sched_edge
*edge
)
266 return is_type(edge
, isl_edge_coincidence
);
269 /* Is "edge" marked as a condition edge?
271 static int is_condition(struct isl_sched_edge
*edge
)
273 return is_type(edge
, isl_edge_condition
);
276 /* Is "edge" marked as a conditional validity edge?
278 static int is_conditional_validity(struct isl_sched_edge
*edge
)
280 return is_type(edge
, isl_edge_conditional_validity
);
283 /* Is "edge" of a type that can appear multiple times between
284 * the same pair of nodes?
286 * Condition edges and conditional validity edges may have tagged
287 * dependence relations, in which case an edge is added for each
290 static int is_multi_edge_type(struct isl_sched_edge
*edge
)
292 return is_condition(edge
) || is_conditional_validity(edge
);
295 /* Internal information about the dependence graph used during
296 * the construction of the schedule.
298 * intra_hmap is a cache, mapping dependence relations to their dual,
299 * for dependences from a node to itself
300 * inter_hmap is a cache, mapping dependence relations to their dual,
301 * for dependences between distinct nodes
302 * if compression is involved then the key for these maps
303 * is the original, uncompressed dependence relation, while
304 * the value is the dual of the compressed dependence relation.
306 * n is the number of nodes
307 * node is the list of nodes
308 * maxvar is the maximal number of variables over all nodes
309 * max_row is the allocated number of rows in the schedule
310 * n_row is the current (maximal) number of linearly independent
311 * rows in the node schedules
312 * n_total_row is the current number of rows in the node schedules
313 * band_start is the starting row in the node schedules of the current band
314 * root is set if this graph is the original dependence graph,
315 * without any splitting
317 * sorted contains a list of node indices sorted according to the
318 * SCC to which a node belongs
320 * n_edge is the number of edges
321 * edge is the list of edges
322 * max_edge contains the maximal number of edges of each type;
323 * in particular, it contains the number of edges in the inital graph.
324 * edge_table contains pointers into the edge array, hashed on the source
325 * and sink spaces; there is one such table for each type;
326 * a given edge may be referenced from more than one table
327 * if the corresponding relation appears in more than one of the
328 * sets of dependences; however, for each type there is only
329 * a single edge between a given pair of source and sink space
330 * in the entire graph
332 * node_table contains pointers into the node array, hashed on the space
334 * region contains a list of variable sequences that should be non-trivial
336 * lp contains the (I)LP problem used to obtain new schedule rows
338 * src_scc and dst_scc are the source and sink SCCs of an edge with
339 * conflicting constraints
341 * scc represents the number of components
342 * weak is set if the components are weakly connected
344 * max_weight is used during clustering and represents the maximal
345 * weight of the relevant proximity edges.
347 struct isl_sched_graph
{
348 isl_map_to_basic_set
*intra_hmap
;
349 isl_map_to_basic_set
*inter_hmap
;
351 struct isl_sched_node
*node
;
364 struct isl_sched_edge
*edge
;
366 int max_edge
[isl_edge_last
+ 1];
367 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
369 struct isl_hash_table
*node_table
;
370 struct isl_region
*region
;
383 /* Initialize node_table based on the list of nodes.
385 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
389 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
390 if (!graph
->node_table
)
393 for (i
= 0; i
< graph
->n
; ++i
) {
394 struct isl_hash_table_entry
*entry
;
397 hash
= isl_space_get_hash(graph
->node
[i
].space
);
398 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
400 graph
->node
[i
].space
, 1);
403 entry
->data
= &graph
->node
[i
];
409 /* Return a pointer to the node that lives within the given space,
410 * or NULL if there is no such node.
412 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
413 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
415 struct isl_hash_table_entry
*entry
;
418 hash
= isl_space_get_hash(dim
);
419 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
420 &node_has_space
, dim
, 0);
422 return entry
? entry
->data
: NULL
;
425 static int edge_has_src_and_dst(const void *entry
, const void *val
)
427 const struct isl_sched_edge
*edge
= entry
;
428 const struct isl_sched_edge
*temp
= val
;
430 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
433 /* Add the given edge to graph->edge_table[type].
435 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
436 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
437 struct isl_sched_edge
*edge
)
439 struct isl_hash_table_entry
*entry
;
442 hash
= isl_hash_init();
443 hash
= isl_hash_builtin(hash
, edge
->src
);
444 hash
= isl_hash_builtin(hash
, edge
->dst
);
445 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
446 &edge_has_src_and_dst
, edge
, 1);
448 return isl_stat_error
;
454 /* Add "edge" to all relevant edge tables.
455 * That is, for every type of the edge, add it to the corresponding table.
457 static isl_stat
graph_edge_tables_add(isl_ctx
*ctx
,
458 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
)
460 enum isl_edge_type t
;
462 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
463 if (!is_type(edge
, t
))
465 if (graph_edge_table_add(ctx
, graph
, t
, edge
) < 0)
466 return isl_stat_error
;
472 /* Allocate the edge_tables based on the maximal number of edges of
475 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
479 for (i
= 0; i
<= isl_edge_last
; ++i
) {
480 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
482 if (!graph
->edge_table
[i
])
489 /* If graph->edge_table[type] contains an edge from the given source
490 * to the given destination, then return the hash table entry of this edge.
491 * Otherwise, return NULL.
493 static struct isl_hash_table_entry
*graph_find_edge_entry(
494 struct isl_sched_graph
*graph
,
495 enum isl_edge_type type
,
496 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
498 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
500 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
502 hash
= isl_hash_init();
503 hash
= isl_hash_builtin(hash
, temp
.src
);
504 hash
= isl_hash_builtin(hash
, temp
.dst
);
505 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
506 &edge_has_src_and_dst
, &temp
, 0);
510 /* If graph->edge_table[type] contains an edge from the given source
511 * to the given destination, then return this edge.
512 * Otherwise, return NULL.
514 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
515 enum isl_edge_type type
,
516 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
518 struct isl_hash_table_entry
*entry
;
520 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
527 /* Check whether the dependence graph has an edge of the given type
528 * between the given two nodes.
530 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
531 enum isl_edge_type type
,
532 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
534 struct isl_sched_edge
*edge
;
537 edge
= graph_find_edge(graph
, type
, src
, dst
);
541 empty
= isl_map_plain_is_empty(edge
->map
);
543 return isl_bool_error
;
548 /* Look for any edge with the same src, dst and map fields as "model".
550 * Return the matching edge if one can be found.
551 * Return "model" if no matching edge is found.
552 * Return NULL on error.
554 static struct isl_sched_edge
*graph_find_matching_edge(
555 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
557 enum isl_edge_type i
;
558 struct isl_sched_edge
*edge
;
560 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
563 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
566 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
576 /* Remove the given edge from all the edge_tables that refer to it.
578 static void graph_remove_edge(struct isl_sched_graph
*graph
,
579 struct isl_sched_edge
*edge
)
581 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
582 enum isl_edge_type i
;
584 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
585 struct isl_hash_table_entry
*entry
;
587 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
590 if (entry
->data
!= edge
)
592 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
596 /* Check whether the dependence graph has any edge
597 * between the given two nodes.
599 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
600 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
602 enum isl_edge_type i
;
605 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
606 r
= graph_has_edge(graph
, i
, src
, dst
);
614 /* Check whether the dependence graph has a validity edge
615 * between the given two nodes.
617 * Conditional validity edges are essentially validity edges that
618 * can be ignored if the corresponding condition edges are iteration private.
619 * Here, we are only checking for the presence of validity
620 * edges, so we need to consider the conditional validity edges too.
621 * In particular, this function is used during the detection
622 * of strongly connected components and we cannot ignore
623 * conditional validity edges during this detection.
625 static isl_bool
graph_has_validity_edge(struct isl_sched_graph
*graph
,
626 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
630 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
634 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
637 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
638 int n_node
, int n_edge
)
643 graph
->n_edge
= n_edge
;
644 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
645 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
646 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
647 graph
->edge
= isl_calloc_array(ctx
,
648 struct isl_sched_edge
, graph
->n_edge
);
650 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
651 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
653 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
657 for(i
= 0; i
< graph
->n
; ++i
)
658 graph
->sorted
[i
] = i
;
663 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
667 isl_map_to_basic_set_free(graph
->intra_hmap
);
668 isl_map_to_basic_set_free(graph
->inter_hmap
);
671 for (i
= 0; i
< graph
->n
; ++i
) {
672 isl_space_free(graph
->node
[i
].space
);
673 isl_set_free(graph
->node
[i
].hull
);
674 isl_multi_aff_free(graph
->node
[i
].compress
);
675 isl_multi_aff_free(graph
->node
[i
].decompress
);
676 isl_mat_free(graph
->node
[i
].sched
);
677 isl_map_free(graph
->node
[i
].sched_map
);
678 isl_mat_free(graph
->node
[i
].cmap
);
679 isl_mat_free(graph
->node
[i
].cinv
);
680 isl_mat_free(graph
->node
[i
].ctrans
);
682 free(graph
->node
[i
].coincident
);
683 isl_multi_val_free(graph
->node
[i
].sizes
);
684 isl_vec_free(graph
->node
[i
].max
);
689 for (i
= 0; i
< graph
->n_edge
; ++i
) {
690 isl_map_free(graph
->edge
[i
].map
);
691 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
692 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
696 for (i
= 0; i
<= isl_edge_last
; ++i
)
697 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
698 isl_hash_table_free(ctx
, graph
->node_table
);
699 isl_basic_set_free(graph
->lp
);
702 /* For each "set" on which this function is called, increment
703 * graph->n by one and update graph->maxvar.
705 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
707 struct isl_sched_graph
*graph
= user
;
708 int nvar
= isl_set_dim(set
, isl_dim_set
);
711 if (nvar
> graph
->maxvar
)
712 graph
->maxvar
= nvar
;
719 /* Compute the number of rows that should be allocated for the schedule.
720 * In particular, we need one row for each variable or one row
721 * for each basic map in the dependences.
722 * Note that it is practically impossible to exhaust both
723 * the number of dependences and the number of variables.
725 static isl_stat
compute_max_row(struct isl_sched_graph
*graph
,
726 __isl_keep isl_schedule_constraints
*sc
)
730 isl_union_set
*domain
;
734 domain
= isl_schedule_constraints_get_domain(sc
);
735 r
= isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
);
736 isl_union_set_free(domain
);
738 return isl_stat_error
;
739 n_edge
= isl_schedule_constraints_n_basic_map(sc
);
741 return isl_stat_error
;
742 graph
->max_row
= n_edge
+ graph
->maxvar
;
747 /* Does "bset" have any defining equalities for its set variables?
749 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
756 n
= isl_basic_set_dim(bset
, isl_dim_set
);
757 for (i
= 0; i
< n
; ++i
) {
760 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
769 /* Set the entries of node->max to the value of the schedule_max_coefficient
772 static isl_stat
set_max_coefficient(isl_ctx
*ctx
, struct isl_sched_node
*node
)
776 max
= isl_options_get_schedule_max_coefficient(ctx
);
780 node
->max
= isl_vec_alloc(ctx
, node
->nvar
);
781 node
->max
= isl_vec_set_si(node
->max
, max
);
783 return isl_stat_error
;
788 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
789 * option (if set) and half of the minimum of the sizes in the other
790 * dimensions. If the minimum of the sizes is one, half of the size
791 * is zero and this value is reset to one.
792 * If the global minimum is unbounded (i.e., if both
793 * the schedule_max_coefficient is not set and the sizes in the other
794 * dimensions are unbounded), then store a negative value.
795 * If the schedule coefficient is close to the size of the instance set
796 * in another dimension, then the schedule may represent a loop
797 * coalescing transformation (especially if the coefficient
798 * in that other dimension is one). Forcing the coefficient to be
799 * smaller than or equal to half the minimal size should avoid this
802 static isl_stat
compute_max_coefficient(isl_ctx
*ctx
,
803 struct isl_sched_node
*node
)
809 max
= isl_options_get_schedule_max_coefficient(ctx
);
810 v
= isl_vec_alloc(ctx
, node
->nvar
);
812 return isl_stat_error
;
814 for (i
= 0; i
< node
->nvar
; ++i
) {
815 isl_int_set_si(v
->el
[i
], max
);
816 isl_int_mul_si(v
->el
[i
], v
->el
[i
], 2);
819 for (i
= 0; i
< node
->nvar
; ++i
) {
822 size
= isl_multi_val_get_val(node
->sizes
, i
);
825 if (!isl_val_is_int(size
)) {
829 for (j
= 0; j
< node
->nvar
; ++j
) {
832 if (isl_int_is_neg(v
->el
[j
]) ||
833 isl_int_gt(v
->el
[j
], size
->n
))
834 isl_int_set(v
->el
[j
], size
->n
);
839 for (i
= 0; i
< node
->nvar
; ++i
) {
840 isl_int_fdiv_q_ui(v
->el
[i
], v
->el
[i
], 2);
841 if (isl_int_is_zero(v
->el
[i
]))
842 isl_int_set_si(v
->el
[i
], 1);
849 return isl_stat_error
;
852 /* Compute and return the size of "set" in dimension "dim".
853 * The size is taken to be the difference in values for that variable
854 * for fixed values of the other variables.
855 * In particular, the variable is first isolated from the other variables
856 * in the range of a map
858 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
860 * and then duplicated
862 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
864 * The shared variables are then projected out and the maximal value
865 * of i_dim' - i_dim is computed.
867 static __isl_give isl_val
*compute_size(__isl_take isl_set
*set
, int dim
)
874 map
= isl_set_project_onto_map(set
, isl_dim_set
, dim
, 1);
875 map
= isl_map_project_out(map
, isl_dim_in
, dim
, 1);
876 map
= isl_map_range_product(map
, isl_map_copy(map
));
877 map
= isl_set_unwrap(isl_map_range(map
));
878 set
= isl_map_deltas(map
);
879 ls
= isl_local_space_from_space(isl_set_get_space(set
));
880 obj
= isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
881 v
= isl_set_max_val(set
, obj
);
888 /* Compute the size of the instance set "set" of "node", after compression,
889 * as well as bounds on the corresponding coefficients, if needed.
891 * The sizes are needed when the schedule_treat_coalescing option is set.
892 * The bounds are needed when the schedule_treat_coalescing option or
893 * the schedule_max_coefficient option is set.
895 * If the schedule_treat_coalescing option is not set, then at most
896 * the bounds need to be set and this is done in set_max_coefficient.
897 * Otherwise, compress the domain if needed, compute the size
898 * in each direction and store the results in node->size.
899 * Finally, set the bounds on the coefficients based on the sizes
900 * and the schedule_max_coefficient option in compute_max_coefficient.
902 static isl_stat
compute_sizes_and_max(isl_ctx
*ctx
, struct isl_sched_node
*node
,
903 __isl_take isl_set
*set
)
908 if (!isl_options_get_schedule_treat_coalescing(ctx
)) {
910 return set_max_coefficient(ctx
, node
);
913 if (node
->compressed
)
914 set
= isl_set_preimage_multi_aff(set
,
915 isl_multi_aff_copy(node
->decompress
));
916 mv
= isl_multi_val_zero(isl_set_get_space(set
));
917 n
= isl_set_dim(set
, isl_dim_set
);
918 for (j
= 0; j
< n
; ++j
) {
921 v
= compute_size(isl_set_copy(set
), j
);
922 mv
= isl_multi_val_set_val(mv
, j
, v
);
927 return isl_stat_error
;
928 return compute_max_coefficient(ctx
, node
);
931 /* Add a new node to the graph representing the given instance set.
932 * "nvar" is the (possibly compressed) number of variables and
933 * may be smaller than then number of set variables in "set"
934 * if "compressed" is set.
935 * If "compressed" is set, then "hull" represents the constraints
936 * that were used to derive the compression, while "compress" and
937 * "decompress" map the original space to the compressed space and
939 * If "compressed" is not set, then "hull", "compress" and "decompress"
942 * Compute the size of the instance set and bounds on the coefficients,
945 static isl_stat
add_node(struct isl_sched_graph
*graph
,
946 __isl_take isl_set
*set
, int nvar
, int compressed
,
947 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
948 __isl_take isl_multi_aff
*decompress
)
955 struct isl_sched_node
*node
;
958 return isl_stat_error
;
960 ctx
= isl_set_get_ctx(set
);
961 nparam
= isl_set_dim(set
, isl_dim_param
);
962 if (!ctx
->opt
->schedule_parametric
)
964 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
965 node
= &graph
->node
[graph
->n
];
967 space
= isl_set_get_space(set
);
970 node
->nparam
= nparam
;
972 node
->sched_map
= NULL
;
973 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
974 node
->coincident
= coincident
;
975 node
->compressed
= compressed
;
977 node
->compress
= compress
;
978 node
->decompress
= decompress
;
979 if (compute_sizes_and_max(ctx
, node
, set
) < 0)
980 return isl_stat_error
;
982 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
983 return isl_stat_error
;
984 if (compressed
&& (!hull
|| !compress
|| !decompress
))
985 return isl_stat_error
;
990 /* Add a new node to the graph representing the given set.
992 * If any of the set variables is defined by an equality, then
993 * we perform variable compression such that we can perform
994 * the scheduling on the compressed domain.
996 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1000 isl_basic_set
*hull
;
1003 isl_multi_aff
*compress
, *decompress
;
1004 struct isl_sched_graph
*graph
= user
;
1006 hull
= isl_set_affine_hull(isl_set_copy(set
));
1007 hull
= isl_basic_set_remove_divs(hull
);
1008 nvar
= isl_set_dim(set
, isl_dim_set
);
1009 has_equality
= has_any_defining_equality(hull
);
1011 if (has_equality
< 0)
1013 if (!has_equality
) {
1014 isl_basic_set_free(hull
);
1015 return add_node(graph
, set
, nvar
, 0, NULL
, NULL
, NULL
);
1018 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
1019 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1020 compress
= isl_morph_get_var_multi_aff(morph
);
1021 morph
= isl_morph_inverse(morph
);
1022 decompress
= isl_morph_get_var_multi_aff(morph
);
1023 isl_morph_free(morph
);
1025 hull_set
= isl_set_from_basic_set(hull
);
1026 return add_node(graph
, set
, nvar
, 1, hull_set
, compress
, decompress
);
1028 isl_basic_set_free(hull
);
1030 return isl_stat_error
;
1033 struct isl_extract_edge_data
{
1034 enum isl_edge_type type
;
1035 struct isl_sched_graph
*graph
;
1038 /* Merge edge2 into edge1, freeing the contents of edge2.
1039 * Return 0 on success and -1 on failure.
1041 * edge1 and edge2 are assumed to have the same value for the map field.
1043 static int merge_edge(struct isl_sched_edge
*edge1
,
1044 struct isl_sched_edge
*edge2
)
1046 edge1
->types
|= edge2
->types
;
1047 isl_map_free(edge2
->map
);
1049 if (is_condition(edge2
)) {
1050 if (!edge1
->tagged_condition
)
1051 edge1
->tagged_condition
= edge2
->tagged_condition
;
1053 edge1
->tagged_condition
=
1054 isl_union_map_union(edge1
->tagged_condition
,
1055 edge2
->tagged_condition
);
1058 if (is_conditional_validity(edge2
)) {
1059 if (!edge1
->tagged_validity
)
1060 edge1
->tagged_validity
= edge2
->tagged_validity
;
1062 edge1
->tagged_validity
=
1063 isl_union_map_union(edge1
->tagged_validity
,
1064 edge2
->tagged_validity
);
1067 if (is_condition(edge2
) && !edge1
->tagged_condition
)
1069 if (is_conditional_validity(edge2
) && !edge1
->tagged_validity
)
1075 /* Insert dummy tags in domain and range of "map".
1077 * In particular, if "map" is of the form
1083 * [A -> dummy_tag] -> [B -> dummy_tag]
1085 * where the dummy_tags are identical and equal to any dummy tags
1086 * introduced by any other call to this function.
1088 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1094 isl_set
*domain
, *range
;
1096 ctx
= isl_map_get_ctx(map
);
1098 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1099 space
= isl_space_params(isl_map_get_space(map
));
1100 space
= isl_space_set_from_params(space
);
1101 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1102 space
= isl_space_map_from_set(space
);
1104 domain
= isl_map_wrap(map
);
1105 range
= isl_map_wrap(isl_map_universe(space
));
1106 map
= isl_map_from_domain_and_range(domain
, range
);
1107 map
= isl_map_zip(map
);
1112 /* Given that at least one of "src" or "dst" is compressed, return
1113 * a map between the spaces of these nodes restricted to the affine
1114 * hull that was used in the compression.
1116 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1117 struct isl_sched_node
*dst
)
1121 if (src
->compressed
)
1122 dom
= isl_set_copy(src
->hull
);
1124 dom
= isl_set_universe(isl_space_copy(src
->space
));
1125 if (dst
->compressed
)
1126 ran
= isl_set_copy(dst
->hull
);
1128 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1130 return isl_map_from_domain_and_range(dom
, ran
);
1133 /* Intersect the domains of the nested relations in domain and range
1134 * of "tagged" with "map".
1136 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1137 __isl_keep isl_map
*map
)
1141 tagged
= isl_map_zip(tagged
);
1142 set
= isl_map_wrap(isl_map_copy(map
));
1143 tagged
= isl_map_intersect_domain(tagged
, set
);
1144 tagged
= isl_map_zip(tagged
);
1148 /* Return a pointer to the node that lives in the domain space of "map"
1149 * or NULL if there is no such node.
1151 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1152 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1154 struct isl_sched_node
*node
;
1157 space
= isl_space_domain(isl_map_get_space(map
));
1158 node
= graph_find_node(ctx
, graph
, space
);
1159 isl_space_free(space
);
1164 /* Return a pointer to the node that lives in the range space of "map"
1165 * or NULL if there is no such node.
1167 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1168 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1170 struct isl_sched_node
*node
;
1173 space
= isl_space_range(isl_map_get_space(map
));
1174 node
= graph_find_node(ctx
, graph
, space
);
1175 isl_space_free(space
);
1180 /* Refrain from adding a new edge based on "map".
1181 * Instead, just free the map.
1182 * "tagged" is either a copy of "map" with additional tags or NULL.
1184 static isl_stat
skip_edge(__isl_take isl_map
*map
, __isl_take isl_map
*tagged
)
1187 isl_map_free(tagged
);
1192 /* Add a new edge to the graph based on the given map
1193 * and add it to data->graph->edge_table[data->type].
1194 * If a dependence relation of a given type happens to be identical
1195 * to one of the dependence relations of a type that was added before,
1196 * then we don't create a new edge, but instead mark the original edge
1197 * as also representing a dependence of the current type.
1199 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1200 * may be specified as "tagged" dependence relations. That is, "map"
1201 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1202 * the dependence on iterations and a and b are tags.
1203 * edge->map is set to the relation containing the elements i -> j,
1204 * while edge->tagged_condition and edge->tagged_validity contain
1205 * the union of all the "map" relations
1206 * for which extract_edge is called that result in the same edge->map.
1208 * If the source or the destination node is compressed, then
1209 * intersect both "map" and "tagged" with the constraints that
1210 * were used to construct the compression.
1211 * This ensures that there are no schedule constraints defined
1212 * outside of these domains, while the scheduler no longer has
1213 * any control over those outside parts.
1215 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1218 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1219 struct isl_extract_edge_data
*data
= user
;
1220 struct isl_sched_graph
*graph
= data
->graph
;
1221 struct isl_sched_node
*src
, *dst
;
1222 struct isl_sched_edge
*edge
;
1223 isl_map
*tagged
= NULL
;
1225 if (data
->type
== isl_edge_condition
||
1226 data
->type
== isl_edge_conditional_validity
) {
1227 if (isl_map_can_zip(map
)) {
1228 tagged
= isl_map_copy(map
);
1229 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1231 tagged
= insert_dummy_tags(isl_map_copy(map
));
1235 src
= find_domain_node(ctx
, graph
, map
);
1236 dst
= find_range_node(ctx
, graph
, map
);
1239 return skip_edge(map
, tagged
);
1241 if (src
->compressed
|| dst
->compressed
) {
1243 hull
= extract_hull(src
, dst
);
1245 tagged
= map_intersect_domains(tagged
, hull
);
1246 map
= isl_map_intersect(map
, hull
);
1249 empty
= isl_map_plain_is_empty(map
);
1253 return skip_edge(map
, tagged
);
1255 graph
->edge
[graph
->n_edge
].src
= src
;
1256 graph
->edge
[graph
->n_edge
].dst
= dst
;
1257 graph
->edge
[graph
->n_edge
].map
= map
;
1258 graph
->edge
[graph
->n_edge
].types
= 0;
1259 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1260 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1261 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1262 if (data
->type
== isl_edge_condition
)
1263 graph
->edge
[graph
->n_edge
].tagged_condition
=
1264 isl_union_map_from_map(tagged
);
1265 if (data
->type
== isl_edge_conditional_validity
)
1266 graph
->edge
[graph
->n_edge
].tagged_validity
=
1267 isl_union_map_from_map(tagged
);
1269 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1272 return isl_stat_error
;
1274 if (edge
== &graph
->edge
[graph
->n_edge
])
1275 return graph_edge_table_add(ctx
, graph
, data
->type
,
1276 &graph
->edge
[graph
->n_edge
++]);
1278 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1281 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1284 isl_map_free(tagged
);
1285 return isl_stat_error
;
1288 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1290 * The context is included in the domain before the nodes of
1291 * the graphs are extracted in order to be able to exploit
1292 * any possible additional equalities.
1293 * Note that this intersection is only performed locally here.
1295 static isl_stat
graph_init(struct isl_sched_graph
*graph
,
1296 __isl_keep isl_schedule_constraints
*sc
)
1299 isl_union_set
*domain
;
1301 struct isl_extract_edge_data data
;
1302 enum isl_edge_type i
;
1306 return isl_stat_error
;
1308 ctx
= isl_schedule_constraints_get_ctx(sc
);
1310 domain
= isl_schedule_constraints_get_domain(sc
);
1311 graph
->n
= isl_union_set_n_set(domain
);
1312 isl_union_set_free(domain
);
1314 if (graph_alloc(ctx
, graph
, graph
->n
,
1315 isl_schedule_constraints_n_map(sc
)) < 0)
1316 return isl_stat_error
;
1318 if (compute_max_row(graph
, sc
) < 0)
1319 return isl_stat_error
;
1322 domain
= isl_schedule_constraints_get_domain(sc
);
1323 domain
= isl_union_set_intersect_params(domain
,
1324 isl_schedule_constraints_get_context(sc
));
1325 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1326 isl_union_set_free(domain
);
1328 return isl_stat_error
;
1329 if (graph_init_table(ctx
, graph
) < 0)
1330 return isl_stat_error
;
1331 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1332 c
= isl_schedule_constraints_get(sc
, i
);
1333 graph
->max_edge
[i
] = isl_union_map_n_map(c
);
1334 isl_union_map_free(c
);
1336 return isl_stat_error
;
1338 if (graph_init_edge_tables(ctx
, graph
) < 0)
1339 return isl_stat_error
;
1342 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1346 c
= isl_schedule_constraints_get(sc
, i
);
1347 r
= isl_union_map_foreach_map(c
, &extract_edge
, &data
);
1348 isl_union_map_free(c
);
1350 return isl_stat_error
;
1356 /* Check whether there is any dependence from node[j] to node[i]
1357 * or from node[i] to node[j].
1359 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1362 struct isl_sched_graph
*graph
= user
;
1364 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1367 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1370 /* Check whether there is a (conditional) validity dependence from node[j]
1371 * to node[i], forcing node[i] to follow node[j].
1373 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1375 struct isl_sched_graph
*graph
= user
;
1377 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1380 /* Use Tarjan's algorithm for computing the strongly connected components
1381 * in the dependence graph only considering those edges defined by "follows".
1383 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1384 isl_bool (*follows
)(int i
, int j
, void *user
))
1387 struct isl_tarjan_graph
*g
= NULL
;
1389 g
= isl_tarjan_graph_init(ctx
, graph
->n
, follows
, graph
);
1397 while (g
->order
[i
] != -1) {
1398 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1406 isl_tarjan_graph_free(g
);
1411 /* Apply Tarjan's algorithm to detect the strongly connected components
1412 * in the dependence graph.
1413 * Only consider the (conditional) validity dependences and clear "weak".
1415 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1418 return detect_ccs(ctx
, graph
, &node_follows_strong
);
1421 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1422 * in the dependence graph.
1423 * Consider all dependences and set "weak".
1425 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1428 return detect_ccs(ctx
, graph
, &node_follows_weak
);
1431 static int cmp_scc(const void *a
, const void *b
, void *data
)
1433 struct isl_sched_graph
*graph
= data
;
1437 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1440 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1442 static int sort_sccs(struct isl_sched_graph
*graph
)
1444 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1447 /* Given a dependence relation R from "node" to itself,
1448 * construct the set of coefficients of valid constraints for elements
1449 * in that dependence relation.
1450 * In particular, the result contains tuples of coefficients
1451 * c_0, c_n, c_x such that
1453 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1457 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1459 * We choose here to compute the dual of delta R.
1460 * Alternatively, we could have computed the dual of R, resulting
1461 * in a set of tuples c_0, c_n, c_x, c_y, and then
1462 * plugged in (c_0, c_n, c_x, -c_x).
1464 * If "node" has been compressed, then the dependence relation
1465 * is also compressed before the set of coefficients is computed.
1467 static __isl_give isl_basic_set
*intra_coefficients(
1468 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1469 __isl_take isl_map
*map
)
1473 isl_basic_set
*coef
;
1474 isl_maybe_isl_basic_set m
;
1476 m
= isl_map_to_basic_set_try_get(graph
->intra_hmap
, map
);
1477 if (m
.valid
< 0 || m
.valid
) {
1482 key
= isl_map_copy(map
);
1483 if (node
->compressed
) {
1484 map
= isl_map_preimage_domain_multi_aff(map
,
1485 isl_multi_aff_copy(node
->decompress
));
1486 map
= isl_map_preimage_range_multi_aff(map
,
1487 isl_multi_aff_copy(node
->decompress
));
1489 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1490 coef
= isl_set_coefficients(delta
);
1491 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1492 isl_basic_set_copy(coef
));
1497 /* Given a dependence relation R, construct the set of coefficients
1498 * of valid constraints for elements in that dependence relation.
1499 * In particular, the result contains tuples of coefficients
1500 * c_0, c_n, c_x, c_y such that
1502 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1504 * If the source or destination nodes of "edge" have been compressed,
1505 * then the dependence relation is also compressed before
1506 * the set of coefficients is computed.
1508 static __isl_give isl_basic_set
*inter_coefficients(
1509 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1510 __isl_take isl_map
*map
)
1514 isl_basic_set
*coef
;
1515 isl_maybe_isl_basic_set m
;
1517 m
= isl_map_to_basic_set_try_get(graph
->inter_hmap
, map
);
1518 if (m
.valid
< 0 || m
.valid
) {
1523 key
= isl_map_copy(map
);
1524 if (edge
->src
->compressed
)
1525 map
= isl_map_preimage_domain_multi_aff(map
,
1526 isl_multi_aff_copy(edge
->src
->decompress
));
1527 if (edge
->dst
->compressed
)
1528 map
= isl_map_preimage_range_multi_aff(map
,
1529 isl_multi_aff_copy(edge
->dst
->decompress
));
1530 set
= isl_map_wrap(isl_map_remove_divs(map
));
1531 coef
= isl_set_coefficients(set
);
1532 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1533 isl_basic_set_copy(coef
));
1538 /* Return the position of the coefficients of the variables in
1539 * the coefficients constraints "coef".
1541 * The space of "coef" is of the form
1543 * { coefficients[[cst, params] -> S] }
1545 * Return the position of S.
1547 static int coef_var_offset(__isl_keep isl_basic_set
*coef
)
1552 space
= isl_space_unwrap(isl_basic_set_get_space(coef
));
1553 offset
= isl_space_dim(space
, isl_dim_in
);
1554 isl_space_free(space
);
1559 /* Return the offset of the coefficients of the variables of "node"
1562 * Within each node, the coefficients have the following order:
1564 * - c_i_n (if parametric)
1565 * - positive and negative parts of c_i_x
1567 static int node_var_coef_offset(struct isl_sched_node
*node
)
1569 return node
->start
+ 1 + node
->nparam
;
1572 /* Construct an isl_dim_map for mapping constraints on coefficients
1573 * for "node" to the corresponding positions in graph->lp.
1574 * "offset" is the offset of the coefficients for the variables
1575 * in the input constraints.
1576 * "s" is the sign of the mapping.
1578 * The input constraints are given in terms of the coefficients (c_0, c_n, c_x).
1579 * The mapping produced by this function essentially plugs in
1580 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1581 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1582 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1584 * The caller can extend the mapping to also map the other coefficients
1585 * (and therefore not plug in 0).
1587 static __isl_give isl_dim_map
*intra_dim_map(isl_ctx
*ctx
,
1588 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1593 isl_dim_map
*dim_map
;
1595 if (!node
|| !graph
->lp
)
1598 total
= isl_basic_set_total_dim(graph
->lp
);
1599 pos
= node_var_coef_offset(node
);
1600 dim_map
= isl_dim_map_alloc(ctx
, total
);
1601 isl_dim_map_range(dim_map
, pos
, 2, offset
, 1, node
->nvar
, -s
);
1602 isl_dim_map_range(dim_map
, pos
+ 1, 2, offset
, 1, node
->nvar
, s
);
1607 /* Construct an isl_dim_map for mapping constraints on coefficients
1608 * for "src" (node i) and "dst" (node j) to the corresponding positions
1610 * "offset" is the offset of the coefficients for the variables of "src"
1611 * in the input constraints.
1612 * "s" is the sign of the mapping.
1614 * The input constraints are given in terms of the coefficients
1615 * (c_0, c_n, c_x, c_y).
1616 * The mapping produced by this function essentially plugs in
1617 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1618 * c_j_x^+ - c_j_x^-, -(c_i_x^+ - c_i_x^-)) if s = 1 and
1619 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1620 * - (c_j_x^+ - c_j_x^-), c_i_x^+ - c_i_x^-) if s = -1.
1621 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1623 * The caller can further extend the mapping.
1625 static __isl_give isl_dim_map
*inter_dim_map(isl_ctx
*ctx
,
1626 struct isl_sched_graph
*graph
, struct isl_sched_node
*src
,
1627 struct isl_sched_node
*dst
, int offset
, int s
)
1631 isl_dim_map
*dim_map
;
1633 if (!src
|| !dst
|| !graph
->lp
)
1636 total
= isl_basic_set_total_dim(graph
->lp
);
1637 dim_map
= isl_dim_map_alloc(ctx
, total
);
1639 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, s
);
1640 isl_dim_map_range(dim_map
, dst
->start
+ 1, 1, 1, 1, dst
->nparam
, s
);
1641 pos
= node_var_coef_offset(dst
);
1642 isl_dim_map_range(dim_map
, pos
, 2, offset
+ src
->nvar
, 1,
1644 isl_dim_map_range(dim_map
, pos
+ 1, 2, offset
+ src
->nvar
, 1,
1647 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -s
);
1648 isl_dim_map_range(dim_map
, src
->start
+ 1, 1, 1, 1, src
->nparam
, -s
);
1649 pos
= node_var_coef_offset(src
);
1650 isl_dim_map_range(dim_map
, pos
, 2, offset
, 1, src
->nvar
, s
);
1651 isl_dim_map_range(dim_map
, pos
+ 1, 2, offset
, 1, src
->nvar
, -s
);
1656 /* Add constraints to graph->lp that force validity for the given
1657 * dependence from a node i to itself.
1658 * That is, add constraints that enforce
1660 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1661 * = c_i_x (y - x) >= 0
1663 * for each (x,y) in R.
1664 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1665 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1666 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1667 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1669 * Actually, we do not construct constraints for the c_i_x themselves,
1670 * but for the coefficients of c_i_x written as a linear combination
1671 * of the columns in node->cmap.
1673 static isl_stat
add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1674 struct isl_sched_edge
*edge
)
1677 isl_map
*map
= isl_map_copy(edge
->map
);
1678 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1679 isl_dim_map
*dim_map
;
1680 isl_basic_set
*coef
;
1681 struct isl_sched_node
*node
= edge
->src
;
1683 coef
= intra_coefficients(graph
, node
, map
);
1685 offset
= coef_var_offset(coef
);
1687 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1688 offset
, isl_mat_copy(node
->cmap
));
1690 return isl_stat_error
;
1692 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
1693 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1694 coef
->n_eq
, coef
->n_ineq
);
1695 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1701 /* Add constraints to graph->lp that force validity for the given
1702 * dependence from node i to node j.
1703 * That is, add constraints that enforce
1705 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1707 * for each (x,y) in R.
1708 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1709 * of valid constraints for R and then plug in
1710 * (c_j_0 - c_i_0, c_j_n - c_i_n, c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1711 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1712 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1714 * Actually, we do not construct constraints for the c_*_x themselves,
1715 * but for the coefficients of c_*_x written as a linear combination
1716 * of the columns in node->cmap.
1718 static isl_stat
add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1719 struct isl_sched_edge
*edge
)
1724 isl_dim_map
*dim_map
;
1725 isl_basic_set
*coef
;
1726 struct isl_sched_node
*src
= edge
->src
;
1727 struct isl_sched_node
*dst
= edge
->dst
;
1730 return isl_stat_error
;
1732 map
= isl_map_copy(edge
->map
);
1733 ctx
= isl_map_get_ctx(map
);
1734 coef
= inter_coefficients(graph
, edge
, map
);
1736 offset
= coef_var_offset(coef
);
1738 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1739 offset
, isl_mat_copy(src
->cmap
));
1740 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1741 offset
+ src
->nvar
, isl_mat_copy(dst
->cmap
));
1743 return isl_stat_error
;
1745 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
1747 edge
->start
= graph
->lp
->n_ineq
;
1748 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1749 coef
->n_eq
, coef
->n_ineq
);
1750 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1753 return isl_stat_error
;
1754 edge
->end
= graph
->lp
->n_ineq
;
1759 /* Add constraints to graph->lp that bound the dependence distance for the given
1760 * dependence from a node i to itself.
1761 * If s = 1, we add the constraint
1763 * c_i_x (y - x) <= m_0 + m_n n
1767 * -c_i_x (y - x) + m_0 + m_n n >= 0
1769 * for each (x,y) in R.
1770 * If s = -1, we add the constraint
1772 * -c_i_x (y - x) <= m_0 + m_n n
1776 * c_i_x (y - x) + m_0 + m_n n >= 0
1778 * for each (x,y) in R.
1779 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1780 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1781 * with each coefficient (except m_0) represented as a pair of non-negative
1784 * Actually, we do not construct constraints for the c_i_x themselves,
1785 * but for the coefficients of c_i_x written as a linear combination
1786 * of the columns in node->cmap.
1789 * If "local" is set, then we add constraints
1791 * c_i_x (y - x) <= 0
1795 * -c_i_x (y - x) <= 0
1797 * instead, forcing the dependence distance to be (less than or) equal to 0.
1798 * That is, we plug in (0, 0, -s * c_i_x),
1799 * Note that dependences marked local are treated as validity constraints
1800 * by add_all_validity_constraints and therefore also have
1801 * their distances bounded by 0 from below.
1803 static isl_stat
add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1804 struct isl_sched_edge
*edge
, int s
, int local
)
1808 isl_map
*map
= isl_map_copy(edge
->map
);
1809 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1810 isl_dim_map
*dim_map
;
1811 isl_basic_set
*coef
;
1812 struct isl_sched_node
*node
= edge
->src
;
1814 coef
= intra_coefficients(graph
, node
, map
);
1816 offset
= coef_var_offset(coef
);
1818 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1819 offset
, isl_mat_copy(node
->cmap
));
1821 return isl_stat_error
;
1823 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1824 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, -s
);
1827 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1828 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1829 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1831 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1832 coef
->n_eq
, coef
->n_ineq
);
1833 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1839 /* Add constraints to graph->lp that bound the dependence distance for the given
1840 * dependence from node i to node j.
1841 * If s = 1, we add the constraint
1843 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1848 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1851 * for each (x,y) in R.
1852 * If s = -1, we add the constraint
1854 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1859 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1862 * for each (x,y) in R.
1863 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1864 * of valid constraints for R and then plug in
1865 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1867 * with each coefficient (except m_0, c_*_0 and c_*_n)
1868 * represented as a pair of non-negative coefficients.
1870 * Actually, we do not construct constraints for the c_*_x themselves,
1871 * but for the coefficients of c_*_x written as a linear combination
1872 * of the columns in node->cmap.
1875 * If "local" is set, then we add constraints
1877 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1881 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1883 * instead, forcing the dependence distance to be (less than or) equal to 0.
1884 * That is, we plug in
1885 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1886 * Note that dependences marked local are treated as validity constraints
1887 * by add_all_validity_constraints and therefore also have
1888 * their distances bounded by 0 from below.
1890 static isl_stat
add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1891 struct isl_sched_edge
*edge
, int s
, int local
)
1895 isl_map
*map
= isl_map_copy(edge
->map
);
1896 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1897 isl_dim_map
*dim_map
;
1898 isl_basic_set
*coef
;
1899 struct isl_sched_node
*src
= edge
->src
;
1900 struct isl_sched_node
*dst
= edge
->dst
;
1902 coef
= inter_coefficients(graph
, edge
, map
);
1904 offset
= coef_var_offset(coef
);
1906 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1907 offset
, isl_mat_copy(src
->cmap
));
1908 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1909 offset
+ src
->nvar
, isl_mat_copy(dst
->cmap
));
1911 return isl_stat_error
;
1913 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1914 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, -s
);
1917 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1918 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1919 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1922 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1923 coef
->n_eq
, coef
->n_ineq
);
1924 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1930 /* Add all validity constraints to graph->lp.
1932 * An edge that is forced to be local needs to have its dependence
1933 * distances equal to zero. We take care of bounding them by 0 from below
1934 * here. add_all_proximity_constraints takes care of bounding them by 0
1937 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1938 * Otherwise, we ignore them.
1940 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1941 int use_coincidence
)
1945 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1946 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1949 local
= is_local(edge
) ||
1950 (is_coincidence(edge
) && use_coincidence
);
1951 if (!is_validity(edge
) && !local
)
1953 if (edge
->src
!= edge
->dst
)
1955 if (add_intra_validity_constraints(graph
, edge
) < 0)
1959 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1960 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1963 local
= is_local(edge
) ||
1964 (is_coincidence(edge
) && use_coincidence
);
1965 if (!is_validity(edge
) && !local
)
1967 if (edge
->src
== edge
->dst
)
1969 if (add_inter_validity_constraints(graph
, edge
) < 0)
1976 /* Add constraints to graph->lp that bound the dependence distance
1977 * for all dependence relations.
1978 * If a given proximity dependence is identical to a validity
1979 * dependence, then the dependence distance is already bounded
1980 * from below (by zero), so we only need to bound the distance
1981 * from above. (This includes the case of "local" dependences
1982 * which are treated as validity dependence by add_all_validity_constraints.)
1983 * Otherwise, we need to bound the distance both from above and from below.
1985 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1986 * Otherwise, we ignore them.
1988 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
1989 int use_coincidence
)
1993 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1994 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1997 local
= is_local(edge
) ||
1998 (is_coincidence(edge
) && use_coincidence
);
1999 if (!is_proximity(edge
) && !local
)
2001 if (edge
->src
== edge
->dst
&&
2002 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
2004 if (edge
->src
!= edge
->dst
&&
2005 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
2007 if (is_validity(edge
) || local
)
2009 if (edge
->src
== edge
->dst
&&
2010 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2012 if (edge
->src
!= edge
->dst
&&
2013 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2020 /* Compute a basis for the rows in the linear part of the schedule
2021 * and extend this basis to a full basis. The remaining rows
2022 * can then be used to force linear independence from the rows
2025 * In particular, given the schedule rows S, we compute
2030 * with H the Hermite normal form of S. That is, all but the
2031 * first rank columns of H are zero and so each row in S is
2032 * a linear combination of the first rank rows of Q.
2033 * The matrix Q is then transposed because we will write the
2034 * coefficients of the next schedule row as a column vector s
2035 * and express this s as a linear combination s = Q c of the
2037 * Similarly, the matrix U is transposed such that we can
2038 * compute the coefficients c = U s from a schedule row s.
2040 static int node_update_cmap(struct isl_sched_node
*node
)
2043 int n_row
= isl_mat_rows(node
->sched
);
2045 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2046 1 + node
->nparam
, node
->nvar
);
2048 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2049 isl_mat_free(node
->cmap
);
2050 isl_mat_free(node
->cinv
);
2051 isl_mat_free(node
->ctrans
);
2052 node
->ctrans
= isl_mat_copy(Q
);
2053 node
->cmap
= isl_mat_transpose(Q
);
2054 node
->cinv
= isl_mat_transpose(U
);
2055 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2058 if (!node
->cmap
|| !node
->cinv
|| !node
->ctrans
|| node
->rank
< 0)
2063 /* Is "edge" marked as a validity or a conditional validity edge?
2065 static int is_any_validity(struct isl_sched_edge
*edge
)
2067 return is_validity(edge
) || is_conditional_validity(edge
);
2070 /* How many times should we count the constraints in "edge"?
2072 * If carry is set, then we are counting the number of
2073 * (validity or conditional validity) constraints that will be added
2074 * in setup_carry_lp and we count each edge exactly once.
2076 * Otherwise, we count as follows
2077 * validity -> 1 (>= 0)
2078 * validity+proximity -> 2 (>= 0 and upper bound)
2079 * proximity -> 2 (lower and upper bound)
2080 * local(+any) -> 2 (>= 0 and <= 0)
2082 * If an edge is only marked conditional_validity then it counts
2083 * as zero since it is only checked afterwards.
2085 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2086 * Otherwise, we ignore them.
2088 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
2089 int use_coincidence
)
2093 if (is_proximity(edge
) || is_local(edge
))
2095 if (use_coincidence
&& is_coincidence(edge
))
2097 if (is_validity(edge
))
2102 /* Count the number of equality and inequality constraints
2103 * that will be added for the given map.
2105 * "use_coincidence" is set if we should take into account coincidence edges.
2107 static int count_map_constraints(struct isl_sched_graph
*graph
,
2108 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2109 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
2111 isl_basic_set
*coef
;
2112 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
2119 if (edge
->src
== edge
->dst
)
2120 coef
= intra_coefficients(graph
, edge
->src
, map
);
2122 coef
= inter_coefficients(graph
, edge
, map
);
2125 *n_eq
+= f
* coef
->n_eq
;
2126 *n_ineq
+= f
* coef
->n_ineq
;
2127 isl_basic_set_free(coef
);
2132 /* Count the number of equality and inequality constraints
2133 * that will be added to the main lp problem.
2134 * We count as follows
2135 * validity -> 1 (>= 0)
2136 * validity+proximity -> 2 (>= 0 and upper bound)
2137 * proximity -> 2 (lower and upper bound)
2138 * local(+any) -> 2 (>= 0 and <= 0)
2140 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2141 * Otherwise, we ignore them.
2143 static int count_constraints(struct isl_sched_graph
*graph
,
2144 int *n_eq
, int *n_ineq
, int use_coincidence
)
2148 *n_eq
= *n_ineq
= 0;
2149 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2150 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2151 isl_map
*map
= isl_map_copy(edge
->map
);
2153 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2154 0, use_coincidence
) < 0)
2161 /* Count the number of constraints that will be added by
2162 * add_bound_constant_constraints to bound the values of the constant terms
2163 * and increment *n_eq and *n_ineq accordingly.
2165 * In practice, add_bound_constant_constraints only adds inequalities.
2167 static isl_stat
count_bound_constant_constraints(isl_ctx
*ctx
,
2168 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2170 if (isl_options_get_schedule_max_constant_term(ctx
) == -1)
2173 *n_ineq
+= graph
->n
;
2178 /* Add constraints to bound the values of the constant terms in the schedule,
2179 * if requested by the user.
2181 * The maximal value of the constant terms is defined by the option
2182 * "schedule_max_constant_term".
2184 * Within each node, the coefficients have the following order:
2186 * - c_i_n (if parametric)
2187 * - positive and negative parts of c_i_x
2189 static isl_stat
add_bound_constant_constraints(isl_ctx
*ctx
,
2190 struct isl_sched_graph
*graph
)
2196 max
= isl_options_get_schedule_max_constant_term(ctx
);
2200 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2202 for (i
= 0; i
< graph
->n
; ++i
) {
2203 struct isl_sched_node
*node
= &graph
->node
[i
];
2204 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2206 return isl_stat_error
;
2207 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2208 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2209 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2215 /* Count the number of constraints that will be added by
2216 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2219 * In practice, add_bound_coefficient_constraints only adds inequalities.
2221 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2222 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2226 if (isl_options_get_schedule_max_coefficient(ctx
) == -1 &&
2227 !isl_options_get_schedule_treat_coalescing(ctx
))
2230 for (i
= 0; i
< graph
->n
; ++i
)
2231 *n_ineq
+= graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2236 /* Add constraints to graph->lp that bound the values of
2237 * the parameter schedule coefficients of "node" to "max" and
2238 * the variable schedule coefficients to the corresponding entry
2240 * In either case, a negative value means that no bound needs to be imposed.
2242 * For parameter coefficients, this amounts to adding a constraint
2250 * The variables coefficients are, however, not represented directly.
2251 * Instead, the variables coefficients c_x are written as a linear
2252 * combination c_x = cmap c_z of some other coefficients c_z,
2253 * which are in turn encoded as c_z = c_z^+ - c_z^-.
2254 * Let a_j be the elements of row i of node->cmap, then
2256 * -max_i <= c_x_i <= max_i
2260 * -max_i <= \sum_j a_j (c_z_j^+ - c_z_j^-) <= max_i
2264 * -\sum_j a_j (c_z_j^+ - c_z_j^-) + max_i >= 0
2265 * \sum_j a_j (c_z_j^+ - c_z_j^-) + max_i >= 0
2267 static isl_stat
node_add_coefficient_constraints(isl_ctx
*ctx
,
2268 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
, int max
)
2274 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2276 for (j
= 0; j
< node
->nparam
; ++j
) {
2282 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2284 return isl_stat_error
;
2285 dim
= 1 + node
->start
+ 1 + j
;
2286 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2287 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2288 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2291 ineq
= isl_vec_alloc(ctx
, 1 + total
);
2292 ineq
= isl_vec_clr(ineq
);
2294 return isl_stat_error
;
2295 for (i
= 0; i
< node
->nvar
; ++i
) {
2296 int pos
= 1 + node_var_coef_offset(node
);
2298 if (isl_int_is_neg(node
->max
->el
[i
]))
2301 for (j
= 0; j
< node
->nvar
; ++j
) {
2302 isl_int_set(ineq
->el
[pos
+ 2 * j
],
2303 node
->cmap
->row
[i
][j
]);
2304 isl_int_neg(ineq
->el
[pos
+ 2 * j
+ 1],
2305 node
->cmap
->row
[i
][j
]);
2307 isl_int_set(ineq
->el
[0], node
->max
->el
[i
]);
2309 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2312 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2314 isl_seq_neg(ineq
->el
+ pos
, ineq
->el
+ pos
, 2 * node
->nvar
);
2315 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2318 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2325 return isl_stat_error
;
2328 /* Add constraints that bound the values of the variable and parameter
2329 * coefficients of the schedule.
2331 * The maximal value of the coefficients is defined by the option
2332 * 'schedule_max_coefficient' and the entries in node->max.
2333 * These latter entries are only set if either the schedule_max_coefficient
2334 * option or the schedule_treat_coalescing option is set.
2336 static isl_stat
add_bound_coefficient_constraints(isl_ctx
*ctx
,
2337 struct isl_sched_graph
*graph
)
2342 max
= isl_options_get_schedule_max_coefficient(ctx
);
2344 if (max
== -1 && !isl_options_get_schedule_treat_coalescing(ctx
))
2347 for (i
= 0; i
< graph
->n
; ++i
) {
2348 struct isl_sched_node
*node
= &graph
->node
[i
];
2350 if (node_add_coefficient_constraints(ctx
, graph
, node
, max
) < 0)
2351 return isl_stat_error
;
2357 /* Add a constraint to graph->lp that equates the value at position
2358 * "sum_pos" to the sum of the "n" values starting at "first".
2360 static isl_stat
add_sum_constraint(struct isl_sched_graph
*graph
,
2361 int sum_pos
, int first
, int n
)
2366 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2368 k
= isl_basic_set_alloc_equality(graph
->lp
);
2370 return isl_stat_error
;
2371 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2372 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2373 for (i
= 0; i
< n
; ++i
)
2374 isl_int_set_si(graph
->lp
->eq
[k
][1 + first
+ i
], 1);
2379 /* Add a constraint to graph->lp that equates the value at position
2380 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2382 * Within each node, the coefficients have the following order:
2384 * - c_i_n (if parametric)
2385 * - positive and negative parts of c_i_x
2387 static isl_stat
add_param_sum_constraint(struct isl_sched_graph
*graph
,
2393 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2395 k
= isl_basic_set_alloc_equality(graph
->lp
);
2397 return isl_stat_error
;
2398 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2399 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2400 for (i
= 0; i
< graph
->n
; ++i
) {
2401 int pos
= 1 + graph
->node
[i
].start
+ 1;
2403 for (j
= 0; j
< graph
->node
[i
].nparam
; ++j
)
2404 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2410 /* Add a constraint to graph->lp that equates the value at position
2411 * "sum_pos" to the sum of the variable coefficients of all nodes.
2413 * Within each node, the coefficients have the following order:
2415 * - c_i_n (if parametric)
2416 * - positive and negative parts of c_i_x
2418 static isl_stat
add_var_sum_constraint(struct isl_sched_graph
*graph
,
2424 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2426 k
= isl_basic_set_alloc_equality(graph
->lp
);
2428 return isl_stat_error
;
2429 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2430 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2431 for (i
= 0; i
< graph
->n
; ++i
) {
2432 struct isl_sched_node
*node
= &graph
->node
[i
];
2433 int pos
= 1 + node_var_coef_offset(node
);
2435 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2436 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2442 /* Construct an ILP problem for finding schedule coefficients
2443 * that result in non-negative, but small dependence distances
2444 * over all dependences.
2445 * In particular, the dependence distances over proximity edges
2446 * are bounded by m_0 + m_n n and we compute schedule coefficients
2447 * with small values (preferably zero) of m_n and m_0.
2449 * All variables of the ILP are non-negative. The actual coefficients
2450 * may be negative, so each coefficient is represented as the difference
2451 * of two non-negative variables. The negative part always appears
2452 * immediately before the positive part.
2453 * Other than that, the variables have the following order
2455 * - sum of positive and negative parts of m_n coefficients
2457 * - sum of all c_n coefficients
2458 * (unconstrained when computing non-parametric schedules)
2459 * - sum of positive and negative parts of all c_x coefficients
2460 * - positive and negative parts of m_n coefficients
2463 * - c_i_n (if parametric)
2464 * - positive and negative parts of c_i_x
2466 * The c_i_x are not represented directly, but through the columns of
2467 * node->cmap. That is, the computed values are for variable t_i_x
2468 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2470 * The constraints are those from the edges plus two or three equalities
2471 * to express the sums.
2473 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2474 * Otherwise, we ignore them.
2476 static isl_stat
setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2477 int use_coincidence
)
2487 parametric
= ctx
->opt
->schedule_parametric
;
2488 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2490 total
= param_pos
+ 2 * nparam
;
2491 for (i
= 0; i
< graph
->n
; ++i
) {
2492 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2493 if (node_update_cmap(node
) < 0)
2494 return isl_stat_error
;
2495 node
->start
= total
;
2496 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
2499 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2500 return isl_stat_error
;
2501 if (count_bound_constant_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2502 return isl_stat_error
;
2503 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2504 return isl_stat_error
;
2506 space
= isl_space_set_alloc(ctx
, 0, total
);
2507 isl_basic_set_free(graph
->lp
);
2508 n_eq
+= 2 + parametric
;
2510 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
2512 if (add_sum_constraint(graph
, 0, param_pos
, 2 * nparam
) < 0)
2513 return isl_stat_error
;
2514 if (parametric
&& add_param_sum_constraint(graph
, 2) < 0)
2515 return isl_stat_error
;
2516 if (add_var_sum_constraint(graph
, 3) < 0)
2517 return isl_stat_error
;
2518 if (add_bound_constant_constraints(ctx
, graph
) < 0)
2519 return isl_stat_error
;
2520 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2521 return isl_stat_error
;
2522 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2523 return isl_stat_error
;
2524 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2525 return isl_stat_error
;
2530 /* Analyze the conflicting constraint found by
2531 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2532 * constraint of one of the edges between distinct nodes, living, moreover
2533 * in distinct SCCs, then record the source and sink SCC as this may
2534 * be a good place to cut between SCCs.
2536 static int check_conflict(int con
, void *user
)
2539 struct isl_sched_graph
*graph
= user
;
2541 if (graph
->src_scc
>= 0)
2544 con
-= graph
->lp
->n_eq
;
2546 if (con
>= graph
->lp
->n_ineq
)
2549 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2550 if (!is_validity(&graph
->edge
[i
]))
2552 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2554 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2556 if (graph
->edge
[i
].start
> con
)
2558 if (graph
->edge
[i
].end
<= con
)
2560 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2561 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2567 /* Check whether the next schedule row of the given node needs to be
2568 * non-trivial. Lower-dimensional domains may have some trivial rows,
2569 * but as soon as the number of remaining required non-trivial rows
2570 * is as large as the number or remaining rows to be computed,
2571 * all remaining rows need to be non-trivial.
2573 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2575 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2578 /* Solve the ILP problem constructed in setup_lp.
2579 * For each node such that all the remaining rows of its schedule
2580 * need to be non-trivial, we construct a non-triviality region.
2581 * This region imposes that the next row is independent of previous rows.
2582 * In particular the coefficients c_i_x are represented by t_i_x
2583 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2584 * its first columns span the rows of the previously computed part
2585 * of the schedule. The non-triviality region enforces that at least
2586 * one of the remaining components of t_i_x is non-zero, i.e.,
2587 * that the new schedule row depends on at least one of the remaining
2590 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2596 for (i
= 0; i
< graph
->n
; ++i
) {
2597 struct isl_sched_node
*node
= &graph
->node
[i
];
2598 int skip
= node
->rank
;
2599 graph
->region
[i
].pos
= node_var_coef_offset(node
) + 2 * skip
;
2600 if (needs_row(graph
, node
))
2601 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2603 graph
->region
[i
].len
= 0;
2605 lp
= isl_basic_set_copy(graph
->lp
);
2606 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2607 graph
->region
, &check_conflict
, graph
);
2611 /* Extract the coefficients for the variables of "node" from "sol".
2613 * Within each node, the coefficients have the following order:
2615 * - c_i_n (if parametric)
2616 * - positive and negative parts of c_i_x
2618 * The c_i_x^- appear before their c_i_x^+ counterpart.
2620 * Return c_i_x = c_i_x^+ - c_i_x^-
2622 static __isl_give isl_vec
*extract_var_coef(struct isl_sched_node
*node
,
2623 __isl_keep isl_vec
*sol
)
2631 csol
= isl_vec_alloc(isl_vec_get_ctx(sol
), node
->nvar
);
2635 pos
= 1 + node_var_coef_offset(node
);
2636 for (i
= 0; i
< node
->nvar
; ++i
)
2637 isl_int_sub(csol
->el
[i
],
2638 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
2643 /* Update the schedules of all nodes based on the given solution
2644 * of the LP problem.
2645 * The new row is added to the current band.
2646 * All possibly negative coefficients are encoded as a difference
2647 * of two non-negative variables, so we need to perform the subtraction
2648 * here. Moreover, if use_cmap is set, then the solution does
2649 * not refer to the actual coefficients c_i_x, but instead to variables
2650 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2651 * In this case, we then also need to perform this multiplication
2652 * to obtain the values of c_i_x.
2654 * If coincident is set, then the caller guarantees that the new
2655 * row satisfies the coincidence constraints.
2657 static int update_schedule(struct isl_sched_graph
*graph
,
2658 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2661 isl_vec
*csol
= NULL
;
2666 isl_die(sol
->ctx
, isl_error_internal
,
2667 "no solution found", goto error
);
2668 if (graph
->n_total_row
>= graph
->max_row
)
2669 isl_die(sol
->ctx
, isl_error_internal
,
2670 "too many schedule rows", goto error
);
2672 for (i
= 0; i
< graph
->n
; ++i
) {
2673 struct isl_sched_node
*node
= &graph
->node
[i
];
2674 int pos
= node
->start
;
2675 int row
= isl_mat_rows(node
->sched
);
2678 csol
= extract_var_coef(node
, sol
);
2682 isl_map_free(node
->sched_map
);
2683 node
->sched_map
= NULL
;
2684 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2687 for (j
= 0; j
< 1 + node
->nparam
; ++j
)
2688 node
->sched
= isl_mat_set_element(node
->sched
,
2689 row
, j
, sol
->el
[1 + pos
+ j
]);
2691 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2695 for (j
= 0; j
< node
->nvar
; ++j
)
2696 node
->sched
= isl_mat_set_element(node
->sched
,
2697 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2698 node
->coincident
[graph
->n_total_row
] = coincident
;
2704 graph
->n_total_row
++;
2713 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2714 * and return this isl_aff.
2716 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2717 struct isl_sched_node
*node
, int row
)
2725 aff
= isl_aff_zero_on_domain(ls
);
2726 if (isl_mat_get_element(node
->sched
, row
, 0, &v
) < 0)
2728 aff
= isl_aff_set_constant(aff
, v
);
2729 for (j
= 0; j
< node
->nparam
; ++j
) {
2730 if (isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
) < 0)
2732 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2734 for (j
= 0; j
< node
->nvar
; ++j
) {
2735 if (isl_mat_get_element(node
->sched
, row
,
2736 1 + node
->nparam
+ j
, &v
) < 0)
2738 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2750 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2751 * and return this multi_aff.
2753 * The result is defined over the uncompressed node domain.
2755 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2756 struct isl_sched_node
*node
, int first
, int n
)
2760 isl_local_space
*ls
;
2767 nrow
= isl_mat_rows(node
->sched
);
2768 if (node
->compressed
)
2769 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2771 space
= isl_space_copy(node
->space
);
2772 ls
= isl_local_space_from_space(isl_space_copy(space
));
2773 space
= isl_space_from_domain(space
);
2774 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2775 ma
= isl_multi_aff_zero(space
);
2777 for (i
= first
; i
< first
+ n
; ++i
) {
2778 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2779 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2782 isl_local_space_free(ls
);
2784 if (node
->compressed
)
2785 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2786 isl_multi_aff_copy(node
->compress
));
2791 /* Convert node->sched into a multi_aff and return this multi_aff.
2793 * The result is defined over the uncompressed node domain.
2795 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2796 struct isl_sched_node
*node
)
2800 nrow
= isl_mat_rows(node
->sched
);
2801 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
2804 /* Convert node->sched into a map and return this map.
2806 * The result is cached in node->sched_map, which needs to be released
2807 * whenever node->sched is updated.
2808 * It is defined over the uncompressed node domain.
2810 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2812 if (!node
->sched_map
) {
2815 ma
= node_extract_schedule_multi_aff(node
);
2816 node
->sched_map
= isl_map_from_multi_aff(ma
);
2819 return isl_map_copy(node
->sched_map
);
2822 /* Construct a map that can be used to update a dependence relation
2823 * based on the current schedule.
2824 * That is, construct a map expressing that source and sink
2825 * are executed within the same iteration of the current schedule.
2826 * This map can then be intersected with the dependence relation.
2827 * This is not the most efficient way, but this shouldn't be a critical
2830 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2831 struct isl_sched_node
*dst
)
2833 isl_map
*src_sched
, *dst_sched
;
2835 src_sched
= node_extract_schedule(src
);
2836 dst_sched
= node_extract_schedule(dst
);
2837 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2840 /* Intersect the domains of the nested relations in domain and range
2841 * of "umap" with "map".
2843 static __isl_give isl_union_map
*intersect_domains(
2844 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2846 isl_union_set
*uset
;
2848 umap
= isl_union_map_zip(umap
);
2849 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2850 umap
= isl_union_map_intersect_domain(umap
, uset
);
2851 umap
= isl_union_map_zip(umap
);
2855 /* Update the dependence relation of the given edge based
2856 * on the current schedule.
2857 * If the dependence is carried completely by the current schedule, then
2858 * it is removed from the edge_tables. It is kept in the list of edges
2859 * as otherwise all edge_tables would have to be recomputed.
2861 * If the edge is of a type that can appear multiple times
2862 * between the same pair of nodes, then it is added to
2863 * the edge table (again). This prevents the situation
2864 * where none of these edges is referenced from the edge table
2865 * because the one that was referenced turned out to be empty and
2866 * was therefore removed from the table.
2868 static int update_edge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2869 struct isl_sched_edge
*edge
)
2874 id
= specializer(edge
->src
, edge
->dst
);
2875 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2879 if (edge
->tagged_condition
) {
2880 edge
->tagged_condition
=
2881 intersect_domains(edge
->tagged_condition
, id
);
2882 if (!edge
->tagged_condition
)
2885 if (edge
->tagged_validity
) {
2886 edge
->tagged_validity
=
2887 intersect_domains(edge
->tagged_validity
, id
);
2888 if (!edge
->tagged_validity
)
2892 empty
= isl_map_plain_is_empty(edge
->map
);
2896 graph_remove_edge(graph
, edge
);
2897 } else if (is_multi_edge_type(edge
)) {
2898 if (graph_edge_tables_add(ctx
, graph
, edge
) < 0)
2909 /* Does the domain of "umap" intersect "uset"?
2911 static int domain_intersects(__isl_keep isl_union_map
*umap
,
2912 __isl_keep isl_union_set
*uset
)
2916 umap
= isl_union_map_copy(umap
);
2917 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
2918 empty
= isl_union_map_is_empty(umap
);
2919 isl_union_map_free(umap
);
2921 return empty
< 0 ? -1 : !empty
;
2924 /* Does the range of "umap" intersect "uset"?
2926 static int range_intersects(__isl_keep isl_union_map
*umap
,
2927 __isl_keep isl_union_set
*uset
)
2931 umap
= isl_union_map_copy(umap
);
2932 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
2933 empty
= isl_union_map_is_empty(umap
);
2934 isl_union_map_free(umap
);
2936 return empty
< 0 ? -1 : !empty
;
2939 /* Are the condition dependences of "edge" local with respect to
2940 * the current schedule?
2942 * That is, are domain and range of the condition dependences mapped
2943 * to the same point?
2945 * In other words, is the condition false?
2947 static int is_condition_false(struct isl_sched_edge
*edge
)
2949 isl_union_map
*umap
;
2950 isl_map
*map
, *sched
, *test
;
2953 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
2954 if (empty
< 0 || empty
)
2957 umap
= isl_union_map_copy(edge
->tagged_condition
);
2958 umap
= isl_union_map_zip(umap
);
2959 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
2960 map
= isl_map_from_union_map(umap
);
2962 sched
= node_extract_schedule(edge
->src
);
2963 map
= isl_map_apply_domain(map
, sched
);
2964 sched
= node_extract_schedule(edge
->dst
);
2965 map
= isl_map_apply_range(map
, sched
);
2967 test
= isl_map_identity(isl_map_get_space(map
));
2968 local
= isl_map_is_subset(map
, test
);
2975 /* For each conditional validity constraint that is adjacent
2976 * to a condition with domain in condition_source or range in condition_sink,
2977 * turn it into an unconditional validity constraint.
2979 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
2980 __isl_take isl_union_set
*condition_source
,
2981 __isl_take isl_union_set
*condition_sink
)
2985 condition_source
= isl_union_set_coalesce(condition_source
);
2986 condition_sink
= isl_union_set_coalesce(condition_sink
);
2988 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2990 isl_union_map
*validity
;
2992 if (!is_conditional_validity(&graph
->edge
[i
]))
2994 if (is_validity(&graph
->edge
[i
]))
2997 validity
= graph
->edge
[i
].tagged_validity
;
2998 adjacent
= domain_intersects(validity
, condition_sink
);
2999 if (adjacent
>= 0 && !adjacent
)
3000 adjacent
= range_intersects(validity
, condition_source
);
3006 set_validity(&graph
->edge
[i
]);
3009 isl_union_set_free(condition_source
);
3010 isl_union_set_free(condition_sink
);
3013 isl_union_set_free(condition_source
);
3014 isl_union_set_free(condition_sink
);
3018 /* Update the dependence relations of all edges based on the current schedule
3019 * and enforce conditional validity constraints that are adjacent
3020 * to satisfied condition constraints.
3022 * First check if any of the condition constraints are satisfied
3023 * (i.e., not local to the outer schedule) and keep track of
3024 * their domain and range.
3025 * Then update all dependence relations (which removes the non-local
3027 * Finally, if any condition constraints turned out to be satisfied,
3028 * then turn all adjacent conditional validity constraints into
3029 * unconditional validity constraints.
3031 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3035 isl_union_set
*source
, *sink
;
3037 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3038 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3039 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3041 isl_union_set
*uset
;
3042 isl_union_map
*umap
;
3044 if (!is_condition(&graph
->edge
[i
]))
3046 if (is_local(&graph
->edge
[i
]))
3048 local
= is_condition_false(&graph
->edge
[i
]);
3056 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3057 uset
= isl_union_map_domain(umap
);
3058 source
= isl_union_set_union(source
, uset
);
3060 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3061 uset
= isl_union_map_range(umap
);
3062 sink
= isl_union_set_union(sink
, uset
);
3065 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3066 if (update_edge(ctx
, graph
, &graph
->edge
[i
]) < 0)
3071 return unconditionalize_adjacent_validity(graph
, source
, sink
);
3073 isl_union_set_free(source
);
3074 isl_union_set_free(sink
);
3077 isl_union_set_free(source
);
3078 isl_union_set_free(sink
);
3082 static void next_band(struct isl_sched_graph
*graph
)
3084 graph
->band_start
= graph
->n_total_row
;
3087 /* Return the union of the universe domains of the nodes in "graph"
3088 * that satisfy "pred".
3090 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
3091 struct isl_sched_graph
*graph
,
3092 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
3098 for (i
= 0; i
< graph
->n
; ++i
)
3099 if (pred(&graph
->node
[i
], data
))
3103 isl_die(ctx
, isl_error_internal
,
3104 "empty component", return NULL
);
3106 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3107 dom
= isl_union_set_from_set(set
);
3109 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
3110 if (!pred(&graph
->node
[i
], data
))
3112 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3113 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
3119 /* Return a list of unions of universe domains, where each element
3120 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3122 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
3123 struct isl_sched_graph
*graph
)
3126 isl_union_set_list
*filters
;
3128 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
3129 for (i
= 0; i
< graph
->scc
; ++i
) {
3132 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
3133 filters
= isl_union_set_list_add(filters
, dom
);
3139 /* Return a list of two unions of universe domains, one for the SCCs up
3140 * to and including graph->src_scc and another for the other SCCs.
3142 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
3143 struct isl_sched_graph
*graph
)
3146 isl_union_set_list
*filters
;
3148 filters
= isl_union_set_list_alloc(ctx
, 2);
3149 dom
= isl_sched_graph_domain(ctx
, graph
,
3150 &node_scc_at_most
, graph
->src_scc
);
3151 filters
= isl_union_set_list_add(filters
, dom
);
3152 dom
= isl_sched_graph_domain(ctx
, graph
,
3153 &node_scc_at_least
, graph
->src_scc
+ 1);
3154 filters
= isl_union_set_list_add(filters
, dom
);
3159 /* Copy nodes that satisfy node_pred from the src dependence graph
3160 * to the dst dependence graph.
3162 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
3163 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
3168 for (i
= 0; i
< src
->n
; ++i
) {
3171 if (!node_pred(&src
->node
[i
], data
))
3175 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
3176 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
3177 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
3178 dst
->node
[j
].compress
=
3179 isl_multi_aff_copy(src
->node
[i
].compress
);
3180 dst
->node
[j
].decompress
=
3181 isl_multi_aff_copy(src
->node
[i
].decompress
);
3182 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
3183 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
3184 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
3185 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
3186 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
3187 dst
->node
[j
].sizes
= isl_multi_val_copy(src
->node
[i
].sizes
);
3188 dst
->node
[j
].max
= isl_vec_copy(src
->node
[i
].max
);
3191 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
3193 if (dst
->node
[j
].compressed
&&
3194 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
3195 !dst
->node
[j
].decompress
))
3202 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3203 * to the dst dependence graph.
3204 * If the source or destination node of the edge is not in the destination
3205 * graph, then it must be a backward proximity edge and it should simply
3208 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3209 struct isl_sched_graph
*src
,
3210 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3215 for (i
= 0; i
< src
->n_edge
; ++i
) {
3216 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3218 isl_union_map
*tagged_condition
;
3219 isl_union_map
*tagged_validity
;
3220 struct isl_sched_node
*dst_src
, *dst_dst
;
3222 if (!edge_pred(edge
, data
))
3225 if (isl_map_plain_is_empty(edge
->map
))
3228 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
3229 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
3230 if (!dst_src
|| !dst_dst
) {
3231 if (is_validity(edge
) || is_conditional_validity(edge
))
3232 isl_die(ctx
, isl_error_internal
,
3233 "backward (conditional) validity edge",
3238 map
= isl_map_copy(edge
->map
);
3239 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3240 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3242 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3243 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3244 dst
->edge
[dst
->n_edge
].map
= map
;
3245 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3246 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3247 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3250 if (edge
->tagged_condition
&& !tagged_condition
)
3252 if (edge
->tagged_validity
&& !tagged_validity
)
3255 if (graph_edge_tables_add(ctx
, dst
,
3256 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3263 /* Compute the maximal number of variables over all nodes.
3264 * This is the maximal number of linearly independent schedule
3265 * rows that we need to compute.
3266 * Just in case we end up in a part of the dependence graph
3267 * with only lower-dimensional domains, we make sure we will
3268 * compute the required amount of extra linearly independent rows.
3270 static int compute_maxvar(struct isl_sched_graph
*graph
)
3275 for (i
= 0; i
< graph
->n
; ++i
) {
3276 struct isl_sched_node
*node
= &graph
->node
[i
];
3279 if (node_update_cmap(node
) < 0)
3281 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3282 if (nvar
> graph
->maxvar
)
3283 graph
->maxvar
= nvar
;
3289 /* Extract the subgraph of "graph" that consists of the node satisfying
3290 * "node_pred" and the edges satisfying "edge_pred" and store
3291 * the result in "sub".
3293 static int extract_sub_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3294 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3295 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3296 int data
, struct isl_sched_graph
*sub
)
3298 int i
, n
= 0, n_edge
= 0;
3301 for (i
= 0; i
< graph
->n
; ++i
)
3302 if (node_pred(&graph
->node
[i
], data
))
3304 for (i
= 0; i
< graph
->n_edge
; ++i
)
3305 if (edge_pred(&graph
->edge
[i
], data
))
3307 if (graph_alloc(ctx
, sub
, n
, n_edge
) < 0)
3309 if (copy_nodes(sub
, graph
, node_pred
, data
) < 0)
3311 if (graph_init_table(ctx
, sub
) < 0)
3313 for (t
= 0; t
<= isl_edge_last
; ++t
)
3314 sub
->max_edge
[t
] = graph
->max_edge
[t
];
3315 if (graph_init_edge_tables(ctx
, sub
) < 0)
3317 if (copy_edges(ctx
, sub
, graph
, edge_pred
, data
) < 0)
3319 sub
->n_row
= graph
->n_row
;
3320 sub
->max_row
= graph
->max_row
;
3321 sub
->n_total_row
= graph
->n_total_row
;
3322 sub
->band_start
= graph
->band_start
;
3327 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3328 struct isl_sched_graph
*graph
);
3329 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3330 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3332 /* Compute a schedule for a subgraph of "graph". In particular, for
3333 * the graph composed of nodes that satisfy node_pred and edges that
3334 * that satisfy edge_pred.
3335 * If the subgraph is known to consist of a single component, then wcc should
3336 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3337 * Otherwise, we call compute_schedule, which will check whether the subgraph
3340 * The schedule is inserted at "node" and the updated schedule node
3343 static __isl_give isl_schedule_node
*compute_sub_schedule(
3344 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3345 struct isl_sched_graph
*graph
,
3346 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3347 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3350 struct isl_sched_graph split
= { 0 };
3352 if (extract_sub_graph(ctx
, graph
, node_pred
, edge_pred
, data
,
3357 node
= compute_schedule_wcc(node
, &split
);
3359 node
= compute_schedule(node
, &split
);
3361 graph_free(ctx
, &split
);
3364 graph_free(ctx
, &split
);
3365 return isl_schedule_node_free(node
);
3368 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3370 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3373 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3375 return edge
->dst
->scc
<= scc
;
3378 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3380 return edge
->src
->scc
>= scc
;
3383 /* Reset the current band by dropping all its schedule rows.
3385 static int reset_band(struct isl_sched_graph
*graph
)
3390 drop
= graph
->n_total_row
- graph
->band_start
;
3391 graph
->n_total_row
-= drop
;
3392 graph
->n_row
-= drop
;
3394 for (i
= 0; i
< graph
->n
; ++i
) {
3395 struct isl_sched_node
*node
= &graph
->node
[i
];
3397 isl_map_free(node
->sched_map
);
3398 node
->sched_map
= NULL
;
3400 node
->sched
= isl_mat_drop_rows(node
->sched
,
3401 graph
->band_start
, drop
);
3410 /* Split the current graph into two parts and compute a schedule for each
3411 * part individually. In particular, one part consists of all SCCs up
3412 * to and including graph->src_scc, while the other part contains the other
3413 * SCCs. The split is enforced by a sequence node inserted at position "node"
3414 * in the schedule tree. Return the updated schedule node.
3415 * If either of these two parts consists of a sequence, then it is spliced
3416 * into the sequence containing the two parts.
3418 * The current band is reset. It would be possible to reuse
3419 * the previously computed rows as the first rows in the next
3420 * band, but recomputing them may result in better rows as we are looking
3421 * at a smaller part of the dependence graph.
3423 static __isl_give isl_schedule_node
*compute_split_schedule(
3424 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3428 isl_union_set_list
*filters
;
3433 if (reset_band(graph
) < 0)
3434 return isl_schedule_node_free(node
);
3438 ctx
= isl_schedule_node_get_ctx(node
);
3439 filters
= extract_split(ctx
, graph
);
3440 node
= isl_schedule_node_insert_sequence(node
, filters
);
3441 node
= isl_schedule_node_child(node
, 1);
3442 node
= isl_schedule_node_child(node
, 0);
3444 node
= compute_sub_schedule(node
, ctx
, graph
,
3445 &node_scc_at_least
, &edge_src_scc_at_least
,
3446 graph
->src_scc
+ 1, 0);
3447 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3448 node
= isl_schedule_node_parent(node
);
3449 node
= isl_schedule_node_parent(node
);
3451 node
= isl_schedule_node_sequence_splice_child(node
, 1);
3452 node
= isl_schedule_node_child(node
, 0);
3453 node
= isl_schedule_node_child(node
, 0);
3454 node
= compute_sub_schedule(node
, ctx
, graph
,
3455 &node_scc_at_most
, &edge_dst_scc_at_most
,
3457 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3458 node
= isl_schedule_node_parent(node
);
3459 node
= isl_schedule_node_parent(node
);
3461 node
= isl_schedule_node_sequence_splice_child(node
, 0);
3466 /* Insert a band node at position "node" in the schedule tree corresponding
3467 * to the current band in "graph". Mark the band node permutable
3468 * if "permutable" is set.
3469 * The partial schedules and the coincidence property are extracted
3470 * from the graph nodes.
3471 * Return the updated schedule node.
3473 static __isl_give isl_schedule_node
*insert_current_band(
3474 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3480 isl_multi_pw_aff
*mpa
;
3481 isl_multi_union_pw_aff
*mupa
;
3487 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3488 "graph should have at least one node",
3489 return isl_schedule_node_free(node
));
3491 start
= graph
->band_start
;
3492 end
= graph
->n_total_row
;
3495 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3496 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3497 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3499 for (i
= 1; i
< graph
->n
; ++i
) {
3500 isl_multi_union_pw_aff
*mupa_i
;
3502 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3504 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3505 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3506 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3508 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3510 for (i
= 0; i
< n
; ++i
)
3511 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3512 graph
->node
[0].coincident
[start
+ i
]);
3513 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3518 /* Update the dependence relations based on the current schedule,
3519 * add the current band to "node" and then continue with the computation
3521 * Return the updated schedule node.
3523 static __isl_give isl_schedule_node
*compute_next_band(
3524 __isl_take isl_schedule_node
*node
,
3525 struct isl_sched_graph
*graph
, int permutable
)
3532 ctx
= isl_schedule_node_get_ctx(node
);
3533 if (update_edges(ctx
, graph
) < 0)
3534 return isl_schedule_node_free(node
);
3535 node
= insert_current_band(node
, graph
, permutable
);
3538 node
= isl_schedule_node_child(node
, 0);
3539 node
= compute_schedule(node
, graph
);
3540 node
= isl_schedule_node_parent(node
);
3545 /* Add constraints to graph->lp that force the dependence "map" (which
3546 * is part of the dependence relation of "edge")
3547 * to be respected and attempt to carry it, where the edge is one from
3548 * a node j to itself. "pos" is the sequence number of the given map.
3549 * That is, add constraints that enforce
3551 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3552 * = c_j_x (y - x) >= e_i
3554 * for each (x,y) in R.
3555 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3556 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3557 * with each coefficient in c_j_x represented as a pair of non-negative
3560 static int add_intra_constraints(struct isl_sched_graph
*graph
,
3561 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3564 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3565 isl_dim_map
*dim_map
;
3566 isl_basic_set
*coef
;
3567 struct isl_sched_node
*node
= edge
->src
;
3569 coef
= intra_coefficients(graph
, node
, map
);
3573 offset
= coef_var_offset(coef
);
3574 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
3575 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3576 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3577 coef
->n_eq
, coef
->n_ineq
);
3578 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3584 /* Add constraints to graph->lp that force the dependence "map" (which
3585 * is part of the dependence relation of "edge")
3586 * to be respected and attempt to carry it, where the edge is one from
3587 * node j to node k. "pos" is the sequence number of the given map.
3588 * That is, add constraints that enforce
3590 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3592 * for each (x,y) in R.
3593 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3594 * of valid constraints for R and then plug in
3595 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3596 * with each coefficient (except e_i, c_*_0 and c_*_n)
3597 * represented as a pair of non-negative coefficients.
3599 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3600 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3603 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3604 isl_dim_map
*dim_map
;
3605 isl_basic_set
*coef
;
3606 struct isl_sched_node
*src
= edge
->src
;
3607 struct isl_sched_node
*dst
= edge
->dst
;
3609 coef
= inter_coefficients(graph
, edge
, map
);
3613 offset
= coef_var_offset(coef
);
3614 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
3615 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3616 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3617 coef
->n_eq
, coef
->n_ineq
);
3618 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3624 /* Add constraints to graph->lp that force all (conditional) validity
3625 * dependences to be respected and attempt to carry them.
3627 static int add_all_constraints(struct isl_sched_graph
*graph
)
3633 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3634 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3636 if (!is_any_validity(edge
))
3639 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3640 isl_basic_map
*bmap
;
3643 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3644 map
= isl_map_from_basic_map(bmap
);
3646 if (edge
->src
== edge
->dst
&&
3647 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3649 if (edge
->src
!= edge
->dst
&&
3650 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3659 /* Count the number of equality and inequality constraints
3660 * that will be added to the carry_lp problem.
3661 * We count each edge exactly once.
3663 static int count_all_constraints(struct isl_sched_graph
*graph
,
3664 int *n_eq
, int *n_ineq
)
3668 *n_eq
= *n_ineq
= 0;
3669 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3670 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3672 if (!is_any_validity(edge
))
3675 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3676 isl_basic_map
*bmap
;
3679 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3680 map
= isl_map_from_basic_map(bmap
);
3682 if (count_map_constraints(graph
, edge
, map
,
3683 n_eq
, n_ineq
, 1, 0) < 0)
3691 /* Return the total number of (validity) edges that carry_dependences will
3694 static int count_carry_edges(struct isl_sched_graph
*graph
)
3700 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3701 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3703 if (!is_any_validity(edge
))
3706 n_edge
+= isl_map_n_basic_map(edge
->map
);
3712 /* Construct an LP problem for finding schedule coefficients
3713 * such that the schedule carries as many validity dependences as possible.
3714 * In particular, for each dependence i, we bound the dependence distance
3715 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3716 * of all e_i's. Dependences with e_i = 0 in the solution are simply
3717 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3718 * Note that if the dependence relation is a union of basic maps,
3719 * then we have to consider each basic map individually as it may only
3720 * be possible to carry the dependences expressed by some of those
3721 * basic maps and not all of them.
3722 * Below, we consider each of those basic maps as a separate "edge".
3724 * All variables of the LP are non-negative. The actual coefficients
3725 * may be negative, so each coefficient is represented as the difference
3726 * of two non-negative variables. The negative part always appears
3727 * immediately before the positive part.
3728 * Other than that, the variables have the following order
3730 * - sum of (1 - e_i) over all edges
3731 * - sum of all c_n coefficients
3732 * (unconstrained when computing non-parametric schedules)
3733 * - sum of positive and negative parts of all c_x coefficients
3738 * - c_i_n (if parametric)
3739 * - positive and negative parts of c_i_x
3741 * The constraints are those from the (validity) edges plus three equalities
3742 * to express the sums and n_edge inequalities to express e_i <= 1.
3744 static isl_stat
setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3753 n_edge
= count_carry_edges(graph
);
3756 for (i
= 0; i
< graph
->n
; ++i
) {
3757 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3758 node
->start
= total
;
3759 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
3762 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3763 return isl_stat_error
;
3765 dim
= isl_space_set_alloc(ctx
, 0, total
);
3766 isl_basic_set_free(graph
->lp
);
3769 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3770 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3772 k
= isl_basic_set_alloc_equality(graph
->lp
);
3774 return isl_stat_error
;
3775 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3776 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3777 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3778 for (i
= 0; i
< n_edge
; ++i
)
3779 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3781 if (add_param_sum_constraint(graph
, 1) < 0)
3782 return isl_stat_error
;
3783 if (add_var_sum_constraint(graph
, 2) < 0)
3784 return isl_stat_error
;
3786 for (i
= 0; i
< n_edge
; ++i
) {
3787 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3789 return isl_stat_error
;
3790 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3791 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3792 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3795 if (add_all_constraints(graph
) < 0)
3796 return isl_stat_error
;
3801 static __isl_give isl_schedule_node
*compute_component_schedule(
3802 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3805 /* Comparison function for sorting the statements based on
3806 * the corresponding value in "r".
3808 static int smaller_value(const void *a
, const void *b
, void *data
)
3814 return isl_int_cmp(r
->el
[*i1
], r
->el
[*i2
]);
3817 /* If the schedule_split_scaled option is set and if the linear
3818 * parts of the scheduling rows for all nodes in the graphs have
3819 * a non-trivial common divisor, then split off the remainder of the
3820 * constant term modulo this common divisor from the linear part.
3821 * Otherwise, insert a band node directly and continue with
3822 * the construction of the schedule.
3824 * If a non-trivial common divisor is found, then
3825 * the linear part is reduced and the remainder is enforced
3826 * by a sequence node with the children placed in the order
3827 * of this remainder.
3828 * In particular, we assign an scc index based on the remainder and
3829 * then rely on compute_component_schedule to insert the sequence and
3830 * to continue the schedule construction on each part.
3832 static __isl_give isl_schedule_node
*split_scaled(
3833 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3846 ctx
= isl_schedule_node_get_ctx(node
);
3847 if (!ctx
->opt
->schedule_split_scaled
)
3848 return compute_next_band(node
, graph
, 0);
3850 return compute_next_band(node
, graph
, 0);
3853 isl_int_init(gcd_i
);
3855 isl_int_set_si(gcd
, 0);
3857 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3859 for (i
= 0; i
< graph
->n
; ++i
) {
3860 struct isl_sched_node
*node
= &graph
->node
[i
];
3861 int cols
= isl_mat_cols(node
->sched
);
3863 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3864 isl_int_gcd(gcd
, gcd
, gcd_i
);
3867 isl_int_clear(gcd_i
);
3869 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3871 return compute_next_band(node
, graph
, 0);
3874 r
= isl_vec_alloc(ctx
, graph
->n
);
3875 order
= isl_calloc_array(ctx
, int, graph
->n
);
3879 for (i
= 0; i
< graph
->n
; ++i
) {
3880 struct isl_sched_node
*node
= &graph
->node
[i
];
3883 isl_int_fdiv_r(r
->el
[i
], node
->sched
->row
[row
][0], gcd
);
3884 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3885 node
->sched
->row
[row
][0], gcd
);
3886 isl_int_mul(node
->sched
->row
[row
][0],
3887 node
->sched
->row
[row
][0], gcd
);
3888 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3893 if (isl_sort(order
, graph
->n
, sizeof(order
[0]), &smaller_value
, r
) < 0)
3897 for (i
= 0; i
< graph
->n
; ++i
) {
3898 if (i
> 0 && isl_int_ne(r
->el
[order
[i
- 1]], r
->el
[order
[i
]]))
3900 graph
->node
[order
[i
]].scc
= scc
;
3909 if (update_edges(ctx
, graph
) < 0)
3910 return isl_schedule_node_free(node
);
3911 node
= insert_current_band(node
, graph
, 0);
3914 node
= isl_schedule_node_child(node
, 0);
3915 node
= compute_component_schedule(node
, graph
, 0);
3916 node
= isl_schedule_node_parent(node
);
3923 return isl_schedule_node_free(node
);
3926 /* Is the schedule row "sol" trivial on node "node"?
3927 * That is, is the solution zero on the dimensions orthogonal to
3928 * the previously found solutions?
3929 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3931 * Each coefficient is represented as the difference between
3932 * two non-negative values in "sol". "sol" has been computed
3933 * in terms of the original iterators (i.e., without use of cmap).
3934 * We construct the schedule row s and write it as a linear
3935 * combination of (linear combinations of) previously computed schedule rows.
3936 * s = Q c or c = U s.
3937 * If the final entries of c are all zero, then the solution is trivial.
3939 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3946 if (node
->nvar
== node
->rank
)
3949 node_sol
= extract_var_coef(node
, sol
);
3950 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3954 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3955 node
->nvar
- node
->rank
) == -1;
3957 isl_vec_free(node_sol
);
3962 /* Is the schedule row "sol" trivial on any node where it should
3964 * "sol" has been computed in terms of the original iterators
3965 * (i.e., without use of cmap).
3966 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3968 static int is_any_trivial(struct isl_sched_graph
*graph
,
3969 __isl_keep isl_vec
*sol
)
3973 for (i
= 0; i
< graph
->n
; ++i
) {
3974 struct isl_sched_node
*node
= &graph
->node
[i
];
3977 if (!needs_row(graph
, node
))
3979 trivial
= is_trivial(node
, sol
);
3980 if (trivial
< 0 || trivial
)
3987 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
3988 * If so, return the position of the coalesced dimension.
3989 * Otherwise, return node->nvar or -1 on error.
3991 * In particular, look for pairs of coefficients c_i and c_j such that
3992 * |c_j/c_i| >= size_i, i.e., |c_j| >= |c_i * size_i|.
3993 * If any such pair is found, then return i.
3994 * If size_i is infinity, then no check on c_i needs to be performed.
3996 static int find_node_coalescing(struct isl_sched_node
*node
,
3997 __isl_keep isl_vec
*sol
)
4003 if (node
->nvar
<= 1)
4006 csol
= extract_var_coef(node
, sol
);
4010 for (i
= 0; i
< node
->nvar
; ++i
) {
4013 if (isl_int_is_zero(csol
->el
[i
]))
4015 v
= isl_multi_val_get_val(node
->sizes
, i
);
4018 if (!isl_val_is_int(v
)) {
4022 isl_int_mul(max
, v
->n
, csol
->el
[i
]);
4025 for (j
= 0; j
< node
->nvar
; ++j
) {
4028 if (isl_int_abs_ge(csol
->el
[j
], max
))
4044 /* Force the schedule coefficient at position "pos" of "node" to be zero
4046 * The coefficient is encoded as the difference between two non-negative
4047 * variables. Force these two variables to have the same value.
4049 static __isl_give isl_tab_lexmin
*zero_out_node_coef(
4050 __isl_take isl_tab_lexmin
*tl
, struct isl_sched_node
*node
, int pos
)
4056 ctx
= isl_space_get_ctx(node
->space
);
4057 dim
= isl_tab_lexmin_dim(tl
);
4059 return isl_tab_lexmin_free(tl
);
4060 eq
= isl_vec_alloc(ctx
, 1 + dim
);
4061 eq
= isl_vec_clr(eq
);
4063 return isl_tab_lexmin_free(tl
);
4065 pos
= 1 + node_var_coef_offset(node
) + 2 * pos
;
4066 isl_int_set_si(eq
->el
[pos
], 1);
4067 isl_int_set_si(eq
->el
[pos
+ 1], -1);
4068 tl
= isl_tab_lexmin_add_eq(tl
, eq
->el
);
4074 /* Return the lexicographically smallest rational point in the basic set
4075 * from which "tl" was constructed, double checking that this input set
4078 static __isl_give isl_vec
*non_empty_solution(__isl_keep isl_tab_lexmin
*tl
)
4082 sol
= isl_tab_lexmin_get_solution(tl
);
4086 isl_die(isl_vec_get_ctx(sol
), isl_error_internal
,
4087 "error in schedule construction",
4088 return isl_vec_free(sol
));
4092 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4093 * carry any of the "n_edge" groups of dependences?
4094 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4095 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4096 * by the edge are carried by the solution.
4097 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4098 * one of those is carried.
4100 * Note that despite the fact that the problem is solved using a rational
4101 * solver, the solution is guaranteed to be integral.
4102 * Specifically, the dependence distance lower bounds e_i (and therefore
4103 * also their sum) are integers. See Lemma 5 of [1].
4105 * Any potential denominator of the sum is cleared by this function.
4106 * The denominator is not relevant for any of the other elements
4109 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4110 * Problem, Part II: Multi-Dimensional Time.
4111 * In Intl. Journal of Parallel Programming, 1992.
4113 static int carries_dependences(__isl_keep isl_vec
*sol
, int n_edge
)
4115 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
4116 isl_int_set_si(sol
->el
[0], 1);
4117 return isl_int_cmp_si(sol
->el
[1], n_edge
) < 0;
4120 /* Return the lexicographically smallest rational point in "lp",
4121 * assuming that all variables are non-negative and performing some
4122 * additional sanity checks.
4123 * In particular, "lp" should not be empty by construction.
4124 * Double check that this is the case.
4125 * Also, check that dependences are carried for at least one of
4126 * the "n_edge" edges.
4128 * If the computed schedule performs loop coalescing on a given node,
4129 * i.e., if it is of the form
4131 * c_i i + c_j j + ...
4133 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4134 * to cut out this solution. Repeat this process until no more loop
4135 * coalescing occurs or until no more dependences can be carried.
4136 * In the latter case, revert to the previously computed solution.
4138 static __isl_give isl_vec
*non_neg_lexmin(struct isl_sched_graph
*graph
,
4139 __isl_take isl_basic_set
*lp
, int n_edge
)
4144 isl_vec
*sol
, *prev
= NULL
;
4145 int treat_coalescing
;
4149 ctx
= isl_basic_set_get_ctx(lp
);
4150 treat_coalescing
= isl_options_get_schedule_treat_coalescing(ctx
);
4151 tl
= isl_tab_lexmin_from_basic_set(lp
);
4154 sol
= non_empty_solution(tl
);
4158 if (!carries_dependences(sol
, n_edge
)) {
4160 isl_die(ctx
, isl_error_unknown
,
4161 "unable to carry dependences",
4167 prev
= isl_vec_free(prev
);
4168 if (!treat_coalescing
)
4170 for (i
= 0; i
< graph
->n
; ++i
) {
4171 struct isl_sched_node
*node
= &graph
->node
[i
];
4173 pos
= find_node_coalescing(node
, sol
);
4176 if (pos
< node
->nvar
)
4181 tl
= zero_out_node_coef(tl
, &graph
->node
[i
], pos
);
4183 } while (i
< graph
->n
);
4185 isl_tab_lexmin_free(tl
);
4189 isl_tab_lexmin_free(tl
);
4195 /* Construct a schedule row for each node such that as many validity dependences
4196 * as possible are carried and then continue with the next band.
4198 * If there are no validity dependences, then no dependence can be carried and
4199 * the procedure is guaranteed to fail. If there is more than one component,
4200 * then try computing a schedule on each component separately
4201 * to prevent or at least postpone this failure.
4203 * If the computed schedule row turns out to be trivial on one or
4204 * more nodes where it should not be trivial, then we throw it away
4205 * and try again on each component separately.
4207 * If there is only one component, then we accept the schedule row anyway,
4208 * but we do not consider it as a complete row and therefore do not
4209 * increment graph->n_row. Note that the ranks of the nodes that
4210 * do get a non-trivial schedule part will get updated regardless and
4211 * graph->maxvar is computed based on these ranks. The test for
4212 * whether more schedule rows are required in compute_schedule_wcc
4213 * is therefore not affected.
4215 * Insert a band corresponding to the schedule row at position "node"
4216 * of the schedule tree and continue with the construction of the schedule.
4217 * This insertion and the continued construction is performed by split_scaled
4218 * after optionally checking for non-trivial common divisors.
4220 static __isl_give isl_schedule_node
*carry_dependences(
4221 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4232 n_edge
= count_carry_edges(graph
);
4233 if (n_edge
== 0 && graph
->scc
> 1)
4234 return compute_component_schedule(node
, graph
, 1);
4236 ctx
= isl_schedule_node_get_ctx(node
);
4237 if (setup_carry_lp(ctx
, graph
) < 0)
4238 return isl_schedule_node_free(node
);
4240 lp
= isl_basic_set_copy(graph
->lp
);
4241 sol
= non_neg_lexmin(graph
, lp
, n_edge
);
4243 return isl_schedule_node_free(node
);
4245 trivial
= is_any_trivial(graph
, sol
);
4247 sol
= isl_vec_free(sol
);
4248 } else if (trivial
&& graph
->scc
> 1) {
4250 return compute_component_schedule(node
, graph
, 1);
4253 if (update_schedule(graph
, sol
, 0, 0) < 0)
4254 return isl_schedule_node_free(node
);
4258 return split_scaled(node
, graph
);
4261 /* Topologically sort statements mapped to the same schedule iteration
4262 * and add insert a sequence node in front of "node"
4263 * corresponding to this order.
4264 * If "initialized" is set, then it may be assumed that compute_maxvar
4265 * has been called on the current band. Otherwise, call
4266 * compute_maxvar if and before carry_dependences gets called.
4268 * If it turns out to be impossible to sort the statements apart,
4269 * because different dependences impose different orderings
4270 * on the statements, then we extend the schedule such that
4271 * it carries at least one more dependence.
4273 static __isl_give isl_schedule_node
*sort_statements(
4274 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4278 isl_union_set_list
*filters
;
4283 ctx
= isl_schedule_node_get_ctx(node
);
4285 isl_die(ctx
, isl_error_internal
,
4286 "graph should have at least one node",
4287 return isl_schedule_node_free(node
));
4292 if (update_edges(ctx
, graph
) < 0)
4293 return isl_schedule_node_free(node
);
4295 if (graph
->n_edge
== 0)
4298 if (detect_sccs(ctx
, graph
) < 0)
4299 return isl_schedule_node_free(node
);
4302 if (graph
->scc
< graph
->n
) {
4303 if (!initialized
&& compute_maxvar(graph
) < 0)
4304 return isl_schedule_node_free(node
);
4305 return carry_dependences(node
, graph
);
4308 filters
= extract_sccs(ctx
, graph
);
4309 node
= isl_schedule_node_insert_sequence(node
, filters
);
4314 /* Are there any (non-empty) (conditional) validity edges in the graph?
4316 static int has_validity_edges(struct isl_sched_graph
*graph
)
4320 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4323 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
4328 if (is_any_validity(&graph
->edge
[i
]))
4335 /* Should we apply a Feautrier step?
4336 * That is, did the user request the Feautrier algorithm and are
4337 * there any validity dependences (left)?
4339 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4341 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
4344 return has_validity_edges(graph
);
4347 /* Compute a schedule for a connected dependence graph using Feautrier's
4348 * multi-dimensional scheduling algorithm and return the updated schedule node.
4350 * The original algorithm is described in [1].
4351 * The main idea is to minimize the number of scheduling dimensions, by
4352 * trying to satisfy as many dependences as possible per scheduling dimension.
4354 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4355 * Problem, Part II: Multi-Dimensional Time.
4356 * In Intl. Journal of Parallel Programming, 1992.
4358 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
4359 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4361 return carry_dependences(node
, graph
);
4364 /* Turn off the "local" bit on all (condition) edges.
4366 static void clear_local_edges(struct isl_sched_graph
*graph
)
4370 for (i
= 0; i
< graph
->n_edge
; ++i
)
4371 if (is_condition(&graph
->edge
[i
]))
4372 clear_local(&graph
->edge
[i
]);
4375 /* Does "graph" have both condition and conditional validity edges?
4377 static int need_condition_check(struct isl_sched_graph
*graph
)
4380 int any_condition
= 0;
4381 int any_conditional_validity
= 0;
4383 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4384 if (is_condition(&graph
->edge
[i
]))
4386 if (is_conditional_validity(&graph
->edge
[i
]))
4387 any_conditional_validity
= 1;
4390 return any_condition
&& any_conditional_validity
;
4393 /* Does "graph" contain any coincidence edge?
4395 static int has_any_coincidence(struct isl_sched_graph
*graph
)
4399 for (i
= 0; i
< graph
->n_edge
; ++i
)
4400 if (is_coincidence(&graph
->edge
[i
]))
4406 /* Extract the final schedule row as a map with the iteration domain
4407 * of "node" as domain.
4409 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
4414 row
= isl_mat_rows(node
->sched
) - 1;
4415 ma
= node_extract_partial_schedule_multi_aff(node
, row
, 1);
4416 return isl_map_from_multi_aff(ma
);
4419 /* Is the conditional validity dependence in the edge with index "edge_index"
4420 * violated by the latest (i.e., final) row of the schedule?
4421 * That is, is i scheduled after j
4422 * for any conditional validity dependence i -> j?
4424 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
4426 isl_map
*src_sched
, *dst_sched
, *map
;
4427 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
4430 src_sched
= final_row(edge
->src
);
4431 dst_sched
= final_row(edge
->dst
);
4432 map
= isl_map_copy(edge
->map
);
4433 map
= isl_map_apply_domain(map
, src_sched
);
4434 map
= isl_map_apply_range(map
, dst_sched
);
4435 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
4436 empty
= isl_map_is_empty(map
);
4445 /* Does "graph" have any satisfied condition edges that
4446 * are adjacent to the conditional validity constraint with
4447 * domain "conditional_source" and range "conditional_sink"?
4449 * A satisfied condition is one that is not local.
4450 * If a condition was forced to be local already (i.e., marked as local)
4451 * then there is no need to check if it is in fact local.
4453 * Additionally, mark all adjacent condition edges found as local.
4455 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
4456 __isl_keep isl_union_set
*conditional_source
,
4457 __isl_keep isl_union_set
*conditional_sink
)
4462 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4463 int adjacent
, local
;
4464 isl_union_map
*condition
;
4466 if (!is_condition(&graph
->edge
[i
]))
4468 if (is_local(&graph
->edge
[i
]))
4471 condition
= graph
->edge
[i
].tagged_condition
;
4472 adjacent
= domain_intersects(condition
, conditional_sink
);
4473 if (adjacent
>= 0 && !adjacent
)
4474 adjacent
= range_intersects(condition
,
4475 conditional_source
);
4481 set_local(&graph
->edge
[i
]);
4483 local
= is_condition_false(&graph
->edge
[i
]);
4493 /* Are there any violated conditional validity dependences with
4494 * adjacent condition dependences that are not local with respect
4495 * to the current schedule?
4496 * That is, is the conditional validity constraint violated?
4498 * Additionally, mark all those adjacent condition dependences as local.
4499 * We also mark those adjacent condition dependences that were not marked
4500 * as local before, but just happened to be local already. This ensures
4501 * that they remain local if the schedule is recomputed.
4503 * We first collect domain and range of all violated conditional validity
4504 * dependences and then check if there are any adjacent non-local
4505 * condition dependences.
4507 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
4508 struct isl_sched_graph
*graph
)
4512 isl_union_set
*source
, *sink
;
4514 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4515 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4516 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4517 isl_union_set
*uset
;
4518 isl_union_map
*umap
;
4521 if (!is_conditional_validity(&graph
->edge
[i
]))
4524 violated
= is_violated(graph
, i
);
4532 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4533 uset
= isl_union_map_domain(umap
);
4534 source
= isl_union_set_union(source
, uset
);
4535 source
= isl_union_set_coalesce(source
);
4537 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4538 uset
= isl_union_map_range(umap
);
4539 sink
= isl_union_set_union(sink
, uset
);
4540 sink
= isl_union_set_coalesce(sink
);
4544 any
= has_adjacent_true_conditions(graph
, source
, sink
);
4546 isl_union_set_free(source
);
4547 isl_union_set_free(sink
);
4550 isl_union_set_free(source
);
4551 isl_union_set_free(sink
);
4555 /* Examine the current band (the rows between graph->band_start and
4556 * graph->n_total_row), deciding whether to drop it or add it to "node"
4557 * and then continue with the computation of the next band, if any.
4558 * If "initialized" is set, then it may be assumed that compute_maxvar
4559 * has been called on the current band. Otherwise, call
4560 * compute_maxvar if and before carry_dependences gets called.
4562 * The caller keeps looking for a new row as long as
4563 * graph->n_row < graph->maxvar. If the latest attempt to find
4564 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
4566 * - split between SCCs and start over (assuming we found an interesting
4567 * pair of SCCs between which to split)
4568 * - continue with the next band (assuming the current band has at least
4570 * - try to carry as many dependences as possible and continue with the next
4572 * In each case, we first insert a band node in the schedule tree
4573 * if any rows have been computed.
4575 * If the caller managed to complete the schedule, we insert a band node
4576 * (if any schedule rows were computed) and we finish off by topologically
4577 * sorting the statements based on the remaining dependences.
4579 static __isl_give isl_schedule_node
*compute_schedule_finish_band(
4580 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4588 if (graph
->n_row
< graph
->maxvar
) {
4590 int empty
= graph
->n_total_row
== graph
->band_start
;
4592 ctx
= isl_schedule_node_get_ctx(node
);
4593 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
4594 return compute_next_band(node
, graph
, 1);
4595 if (graph
->src_scc
>= 0)
4596 return compute_split_schedule(node
, graph
);
4598 return compute_next_band(node
, graph
, 1);
4599 if (!initialized
&& compute_maxvar(graph
) < 0)
4600 return isl_schedule_node_free(node
);
4601 return carry_dependences(node
, graph
);
4604 insert
= graph
->n_total_row
> graph
->band_start
;
4606 node
= insert_current_band(node
, graph
, 1);
4607 node
= isl_schedule_node_child(node
, 0);
4609 node
= sort_statements(node
, graph
, initialized
);
4611 node
= isl_schedule_node_parent(node
);
4616 /* Construct a band of schedule rows for a connected dependence graph.
4617 * The caller is responsible for determining the strongly connected
4618 * components and calling compute_maxvar first.
4620 * We try to find a sequence of as many schedule rows as possible that result
4621 * in non-negative dependence distances (independent of the previous rows
4622 * in the sequence, i.e., such that the sequence is tilable), with as
4623 * many of the initial rows as possible satisfying the coincidence constraints.
4624 * The computation stops if we can't find any more rows or if we have found
4625 * all the rows we wanted to find.
4627 * If ctx->opt->schedule_outer_coincidence is set, then we force the
4628 * outermost dimension to satisfy the coincidence constraints. If this
4629 * turns out to be impossible, we fall back on the general scheme above
4630 * and try to carry as many dependences as possible.
4632 * If "graph" contains both condition and conditional validity dependences,
4633 * then we need to check that that the conditional schedule constraint
4634 * is satisfied, i.e., there are no violated conditional validity dependences
4635 * that are adjacent to any non-local condition dependences.
4636 * If there are, then we mark all those adjacent condition dependences
4637 * as local and recompute the current band. Those dependences that
4638 * are marked local will then be forced to be local.
4639 * The initial computation is performed with no dependences marked as local.
4640 * If we are lucky, then there will be no violated conditional validity
4641 * dependences adjacent to any non-local condition dependences.
4642 * Otherwise, we mark some additional condition dependences as local and
4643 * recompute. We continue this process until there are no violations left or
4644 * until we are no longer able to compute a schedule.
4645 * Since there are only a finite number of dependences,
4646 * there will only be a finite number of iterations.
4648 static isl_stat
compute_schedule_wcc_band(isl_ctx
*ctx
,
4649 struct isl_sched_graph
*graph
)
4651 int has_coincidence
;
4652 int use_coincidence
;
4653 int force_coincidence
= 0;
4654 int check_conditional
;
4656 if (sort_sccs(graph
) < 0)
4657 return isl_stat_error
;
4659 clear_local_edges(graph
);
4660 check_conditional
= need_condition_check(graph
);
4661 has_coincidence
= has_any_coincidence(graph
);
4663 if (ctx
->opt
->schedule_outer_coincidence
)
4664 force_coincidence
= 1;
4666 use_coincidence
= has_coincidence
;
4667 while (graph
->n_row
< graph
->maxvar
) {
4672 graph
->src_scc
= -1;
4673 graph
->dst_scc
= -1;
4675 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
4676 return isl_stat_error
;
4677 sol
= solve_lp(graph
);
4679 return isl_stat_error
;
4680 if (sol
->size
== 0) {
4681 int empty
= graph
->n_total_row
== graph
->band_start
;
4684 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
4685 use_coincidence
= 0;
4690 coincident
= !has_coincidence
|| use_coincidence
;
4691 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
4692 return isl_stat_error
;
4694 if (!check_conditional
)
4696 violated
= has_violated_conditional_constraint(ctx
, graph
);
4698 return isl_stat_error
;
4701 if (reset_band(graph
) < 0)
4702 return isl_stat_error
;
4703 use_coincidence
= has_coincidence
;
4709 /* Compute a schedule for a connected dependence graph by considering
4710 * the graph as a whole and return the updated schedule node.
4712 * The actual schedule rows of the current band are computed by
4713 * compute_schedule_wcc_band. compute_schedule_finish_band takes
4714 * care of integrating the band into "node" and continuing
4717 static __isl_give isl_schedule_node
*compute_schedule_wcc_whole(
4718 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4725 ctx
= isl_schedule_node_get_ctx(node
);
4726 if (compute_schedule_wcc_band(ctx
, graph
) < 0)
4727 return isl_schedule_node_free(node
);
4729 return compute_schedule_finish_band(node
, graph
, 1);
4732 /* Clustering information used by compute_schedule_wcc_clustering.
4734 * "n" is the number of SCCs in the original dependence graph
4735 * "scc" is an array of "n" elements, each representing an SCC
4736 * of the original dependence graph. All entries in the same cluster
4737 * have the same number of schedule rows.
4738 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
4739 * where each cluster is represented by the index of the first SCC
4740 * in the cluster. Initially, each SCC belongs to a cluster containing
4743 * "scc_in_merge" is used by merge_clusters_along_edge to keep
4744 * track of which SCCs need to be merged.
4746 * "cluster" contains the merged clusters of SCCs after the clustering
4749 * "scc_node" is a temporary data structure used inside copy_partial.
4750 * For each SCC, it keeps track of the number of nodes in the SCC
4751 * that have already been copied.
4753 struct isl_clustering
{
4755 struct isl_sched_graph
*scc
;
4756 struct isl_sched_graph
*cluster
;
4762 /* Initialize the clustering data structure "c" from "graph".
4764 * In particular, allocate memory, extract the SCCs from "graph"
4765 * into c->scc, initialize scc_cluster and construct
4766 * a band of schedule rows for each SCC.
4767 * Within each SCC, there is only one SCC by definition.
4768 * Each SCC initially belongs to a cluster containing only that SCC.
4770 static isl_stat
clustering_init(isl_ctx
*ctx
, struct isl_clustering
*c
,
4771 struct isl_sched_graph
*graph
)
4776 c
->scc
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
4777 c
->cluster
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
4778 c
->scc_cluster
= isl_calloc_array(ctx
, int, c
->n
);
4779 c
->scc_node
= isl_calloc_array(ctx
, int, c
->n
);
4780 c
->scc_in_merge
= isl_calloc_array(ctx
, int, c
->n
);
4781 if (!c
->scc
|| !c
->cluster
||
4782 !c
->scc_cluster
|| !c
->scc_node
|| !c
->scc_in_merge
)
4783 return isl_stat_error
;
4785 for (i
= 0; i
< c
->n
; ++i
) {
4786 if (extract_sub_graph(ctx
, graph
, &node_scc_exactly
,
4787 &edge_scc_exactly
, i
, &c
->scc
[i
]) < 0)
4788 return isl_stat_error
;
4790 if (compute_maxvar(&c
->scc
[i
]) < 0)
4791 return isl_stat_error
;
4792 if (compute_schedule_wcc_band(ctx
, &c
->scc
[i
]) < 0)
4793 return isl_stat_error
;
4794 c
->scc_cluster
[i
] = i
;
4800 /* Free all memory allocated for "c".
4802 static void clustering_free(isl_ctx
*ctx
, struct isl_clustering
*c
)
4807 for (i
= 0; i
< c
->n
; ++i
)
4808 graph_free(ctx
, &c
->scc
[i
]);
4811 for (i
= 0; i
< c
->n
; ++i
)
4812 graph_free(ctx
, &c
->cluster
[i
]);
4814 free(c
->scc_cluster
);
4816 free(c
->scc_in_merge
);
4819 /* Should we refrain from merging the cluster in "graph" with
4820 * any other cluster?
4821 * In particular, is its current schedule band empty and incomplete.
4823 static int bad_cluster(struct isl_sched_graph
*graph
)
4825 return graph
->n_row
< graph
->maxvar
&&
4826 graph
->n_total_row
== graph
->band_start
;
4829 /* Return the index of an edge in "graph" that can be used to merge
4830 * two clusters in "c".
4831 * Return graph->n_edge if no such edge can be found.
4832 * Return -1 on error.
4834 * In particular, return a proximity edge between two clusters
4835 * that is not marked "no_merge" and such that neither of the
4836 * two clusters has an incomplete, empty band.
4838 * If there are multiple such edges, then try and find the most
4839 * appropriate edge to use for merging. In particular, pick the edge
4840 * with the greatest weight. If there are multiple of those,
4841 * then pick one with the shortest distance between
4842 * the two cluster representatives.
4844 static int find_proximity(struct isl_sched_graph
*graph
,
4845 struct isl_clustering
*c
)
4847 int i
, best
= graph
->n_edge
, best_dist
, best_weight
;
4849 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4850 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4853 if (!is_proximity(edge
))
4857 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
4858 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
4860 dist
= c
->scc_cluster
[edge
->dst
->scc
] -
4861 c
->scc_cluster
[edge
->src
->scc
];
4864 weight
= edge
->weight
;
4865 if (best
< graph
->n_edge
) {
4866 if (best_weight
> weight
)
4868 if (best_weight
== weight
&& best_dist
<= dist
)
4873 best_weight
= weight
;
4879 /* Internal data structure used in mark_merge_sccs.
4881 * "graph" is the dependence graph in which a strongly connected
4882 * component is constructed.
4883 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
4884 * "src" and "dst" are the indices of the nodes that are being merged.
4886 struct isl_mark_merge_sccs_data
{
4887 struct isl_sched_graph
*graph
;
4893 /* Check whether the cluster containing node "i" depends on the cluster
4894 * containing node "j". If "i" and "j" belong to the same cluster,
4895 * then they are taken to depend on each other to ensure that
4896 * the resulting strongly connected component consists of complete
4897 * clusters. Furthermore, if "i" and "j" are the two nodes that
4898 * are being merged, then they are taken to depend on each other as well.
4899 * Otherwise, check if there is a (conditional) validity dependence
4900 * from node[j] to node[i], forcing node[i] to follow node[j].
4902 static isl_bool
cluster_follows(int i
, int j
, void *user
)
4904 struct isl_mark_merge_sccs_data
*data
= user
;
4905 struct isl_sched_graph
*graph
= data
->graph
;
4906 int *scc_cluster
= data
->scc_cluster
;
4908 if (data
->src
== i
&& data
->dst
== j
)
4909 return isl_bool_true
;
4910 if (data
->src
== j
&& data
->dst
== i
)
4911 return isl_bool_true
;
4912 if (scc_cluster
[graph
->node
[i
].scc
] == scc_cluster
[graph
->node
[j
].scc
])
4913 return isl_bool_true
;
4915 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
4918 /* Mark all SCCs that belong to either of the two clusters in "c"
4919 * connected by the edge in "graph" with index "edge", or to any
4920 * of the intermediate clusters.
4921 * The marking is recorded in c->scc_in_merge.
4923 * The given edge has been selected for merging two clusters,
4924 * meaning that there is at least a proximity edge between the two nodes.
4925 * However, there may also be (indirect) validity dependences
4926 * between the two nodes. When merging the two clusters, all clusters
4927 * containing one or more of the intermediate nodes along the
4928 * indirect validity dependences need to be merged in as well.
4930 * First collect all such nodes by computing the strongly connected
4931 * component (SCC) containing the two nodes connected by the edge, where
4932 * the two nodes are considered to depend on each other to make
4933 * sure they end up in the same SCC. Similarly, each node is considered
4934 * to depend on every other node in the same cluster to ensure
4935 * that the SCC consists of complete clusters.
4937 * Then the original SCCs that contain any of these nodes are marked
4938 * in c->scc_in_merge.
4940 static isl_stat
mark_merge_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
4941 int edge
, struct isl_clustering
*c
)
4943 struct isl_mark_merge_sccs_data data
;
4944 struct isl_tarjan_graph
*g
;
4947 for (i
= 0; i
< c
->n
; ++i
)
4948 c
->scc_in_merge
[i
] = 0;
4951 data
.scc_cluster
= c
->scc_cluster
;
4952 data
.src
= graph
->edge
[edge
].src
- graph
->node
;
4953 data
.dst
= graph
->edge
[edge
].dst
- graph
->node
;
4955 g
= isl_tarjan_graph_component(ctx
, graph
->n
, data
.dst
,
4956 &cluster_follows
, &data
);
4962 isl_die(ctx
, isl_error_internal
,
4963 "expecting at least two nodes in component",
4965 if (g
->order
[--i
] != -1)
4966 isl_die(ctx
, isl_error_internal
,
4967 "expecting end of component marker", goto error
);
4969 for (--i
; i
>= 0 && g
->order
[i
] != -1; --i
) {
4970 int scc
= graph
->node
[g
->order
[i
]].scc
;
4971 c
->scc_in_merge
[scc
] = 1;
4974 isl_tarjan_graph_free(g
);
4977 isl_tarjan_graph_free(g
);
4978 return isl_stat_error
;
4981 /* Construct the identifier "cluster_i".
4983 static __isl_give isl_id
*cluster_id(isl_ctx
*ctx
, int i
)
4987 snprintf(name
, sizeof(name
), "cluster_%d", i
);
4988 return isl_id_alloc(ctx
, name
, NULL
);
4991 /* Construct the space of the cluster with index "i" containing
4992 * the strongly connected component "scc".
4994 * In particular, construct a space called cluster_i with dimension equal
4995 * to the number of schedule rows in the current band of "scc".
4997 static __isl_give isl_space
*cluster_space(struct isl_sched_graph
*scc
, int i
)
5003 nvar
= scc
->n_total_row
- scc
->band_start
;
5004 space
= isl_space_copy(scc
->node
[0].space
);
5005 space
= isl_space_params(space
);
5006 space
= isl_space_set_from_params(space
);
5007 space
= isl_space_add_dims(space
, isl_dim_set
, nvar
);
5008 id
= cluster_id(isl_space_get_ctx(space
), i
);
5009 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
5014 /* Collect the domain of the graph for merging clusters.
5016 * In particular, for each cluster with first SCC "i", construct
5017 * a set in the space called cluster_i with dimension equal
5018 * to the number of schedule rows in the current band of the cluster.
5020 static __isl_give isl_union_set
*collect_domain(isl_ctx
*ctx
,
5021 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5025 isl_union_set
*domain
;
5027 space
= isl_space_params_alloc(ctx
, 0);
5028 domain
= isl_union_set_empty(space
);
5030 for (i
= 0; i
< graph
->scc
; ++i
) {
5033 if (!c
->scc_in_merge
[i
])
5035 if (c
->scc_cluster
[i
] != i
)
5037 space
= cluster_space(&c
->scc
[i
], i
);
5038 domain
= isl_union_set_add_set(domain
, isl_set_universe(space
));
5044 /* Construct a map from the original instances to the corresponding
5045 * cluster instance in the current bands of the clusters in "c".
5047 static __isl_give isl_union_map
*collect_cluster_map(isl_ctx
*ctx
,
5048 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5052 isl_union_map
*cluster_map
;
5054 space
= isl_space_params_alloc(ctx
, 0);
5055 cluster_map
= isl_union_map_empty(space
);
5056 for (i
= 0; i
< graph
->scc
; ++i
) {
5060 if (!c
->scc_in_merge
[i
])
5063 id
= cluster_id(ctx
, c
->scc_cluster
[i
]);
5064 start
= c
->scc
[i
].band_start
;
5065 n
= c
->scc
[i
].n_total_row
- start
;
5066 for (j
= 0; j
< c
->scc
[i
].n
; ++j
) {
5069 struct isl_sched_node
*node
= &c
->scc
[i
].node
[j
];
5071 ma
= node_extract_partial_schedule_multi_aff(node
,
5073 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
,
5075 map
= isl_map_from_multi_aff(ma
);
5076 cluster_map
= isl_union_map_add_map(cluster_map
, map
);
5084 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
5085 * that are not isl_edge_condition or isl_edge_conditional_validity.
5087 static __isl_give isl_schedule_constraints
*add_non_conditional_constraints(
5088 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5089 __isl_take isl_schedule_constraints
*sc
)
5091 enum isl_edge_type t
;
5096 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
5097 if (t
== isl_edge_condition
||
5098 t
== isl_edge_conditional_validity
)
5100 if (!is_type(edge
, t
))
5102 sc
= isl_schedule_constraints_add(sc
, t
,
5103 isl_union_map_copy(umap
));
5109 /* Add schedule constraints of types isl_edge_condition and
5110 * isl_edge_conditional_validity to "sc" by applying "umap" to
5111 * the domains of the wrapped relations in domain and range
5112 * of the corresponding tagged constraints of "edge".
5114 static __isl_give isl_schedule_constraints
*add_conditional_constraints(
5115 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5116 __isl_take isl_schedule_constraints
*sc
)
5118 enum isl_edge_type t
;
5119 isl_union_map
*tagged
;
5121 for (t
= isl_edge_condition
; t
<= isl_edge_conditional_validity
; ++t
) {
5122 if (!is_type(edge
, t
))
5124 if (t
== isl_edge_condition
)
5125 tagged
= isl_union_map_copy(edge
->tagged_condition
);
5127 tagged
= isl_union_map_copy(edge
->tagged_validity
);
5128 tagged
= isl_union_map_zip(tagged
);
5129 tagged
= isl_union_map_apply_domain(tagged
,
5130 isl_union_map_copy(umap
));
5131 tagged
= isl_union_map_zip(tagged
);
5132 sc
= isl_schedule_constraints_add(sc
, t
, tagged
);
5140 /* Given a mapping "cluster_map" from the original instances to
5141 * the cluster instances, add schedule constraints on the clusters
5142 * to "sc" corresponding to the original constraints represented by "edge".
5144 * For non-tagged dependence constraints, the cluster constraints
5145 * are obtained by applying "cluster_map" to the edge->map.
5147 * For tagged dependence constraints, "cluster_map" needs to be applied
5148 * to the domains of the wrapped relations in domain and range
5149 * of the tagged dependence constraints. Pick out the mappings
5150 * from these domains from "cluster_map" and construct their product.
5151 * This mapping can then be applied to the pair of domains.
5153 static __isl_give isl_schedule_constraints
*collect_edge_constraints(
5154 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*cluster_map
,
5155 __isl_take isl_schedule_constraints
*sc
)
5157 isl_union_map
*umap
;
5159 isl_union_set
*uset
;
5160 isl_union_map
*umap1
, *umap2
;
5165 umap
= isl_union_map_from_map(isl_map_copy(edge
->map
));
5166 umap
= isl_union_map_apply_domain(umap
,
5167 isl_union_map_copy(cluster_map
));
5168 umap
= isl_union_map_apply_range(umap
,
5169 isl_union_map_copy(cluster_map
));
5170 sc
= add_non_conditional_constraints(edge
, umap
, sc
);
5171 isl_union_map_free(umap
);
5173 if (!sc
|| (!is_condition(edge
) && !is_conditional_validity(edge
)))
5176 space
= isl_space_domain(isl_map_get_space(edge
->map
));
5177 uset
= isl_union_set_from_set(isl_set_universe(space
));
5178 umap1
= isl_union_map_copy(cluster_map
);
5179 umap1
= isl_union_map_intersect_domain(umap1
, uset
);
5180 space
= isl_space_range(isl_map_get_space(edge
->map
));
5181 uset
= isl_union_set_from_set(isl_set_universe(space
));
5182 umap2
= isl_union_map_copy(cluster_map
);
5183 umap2
= isl_union_map_intersect_domain(umap2
, uset
);
5184 umap
= isl_union_map_product(umap1
, umap2
);
5186 sc
= add_conditional_constraints(edge
, umap
, sc
);
5188 isl_union_map_free(umap
);
5192 /* Given a mapping "cluster_map" from the original instances to
5193 * the cluster instances, add schedule constraints on the clusters
5194 * to "sc" corresponding to all edges in "graph" between nodes that
5195 * belong to SCCs that are marked for merging in "scc_in_merge".
5197 static __isl_give isl_schedule_constraints
*collect_constraints(
5198 struct isl_sched_graph
*graph
, int *scc_in_merge
,
5199 __isl_keep isl_union_map
*cluster_map
,
5200 __isl_take isl_schedule_constraints
*sc
)
5204 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5205 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5207 if (!scc_in_merge
[edge
->src
->scc
])
5209 if (!scc_in_merge
[edge
->dst
->scc
])
5211 sc
= collect_edge_constraints(edge
, cluster_map
, sc
);
5217 /* Construct a dependence graph for scheduling clusters with respect
5218 * to each other and store the result in "merge_graph".
5219 * In particular, the nodes of the graph correspond to the schedule
5220 * dimensions of the current bands of those clusters that have been
5221 * marked for merging in "c".
5223 * First construct an isl_schedule_constraints object for this domain
5224 * by transforming the edges in "graph" to the domain.
5225 * Then initialize a dependence graph for scheduling from these
5228 static isl_stat
init_merge_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5229 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
5231 isl_union_set
*domain
;
5232 isl_union_map
*cluster_map
;
5233 isl_schedule_constraints
*sc
;
5236 domain
= collect_domain(ctx
, graph
, c
);
5237 sc
= isl_schedule_constraints_on_domain(domain
);
5239 return isl_stat_error
;
5240 cluster_map
= collect_cluster_map(ctx
, graph
, c
);
5241 sc
= collect_constraints(graph
, c
->scc_in_merge
, cluster_map
, sc
);
5242 isl_union_map_free(cluster_map
);
5244 r
= graph_init(merge_graph
, sc
);
5246 isl_schedule_constraints_free(sc
);
5251 /* Compute the maximal number of remaining schedule rows that still need
5252 * to be computed for the nodes that belong to clusters with the maximal
5253 * dimension for the current band (i.e., the band that is to be merged).
5254 * Only clusters that are about to be merged are considered.
5255 * "maxvar" is the maximal dimension for the current band.
5256 * "c" contains information about the clusters.
5258 * Return the maximal number of remaining schedule rows or -1 on error.
5260 static int compute_maxvar_max_slack(int maxvar
, struct isl_clustering
*c
)
5266 for (i
= 0; i
< c
->n
; ++i
) {
5268 struct isl_sched_graph
*scc
;
5270 if (!c
->scc_in_merge
[i
])
5273 nvar
= scc
->n_total_row
- scc
->band_start
;
5276 for (j
= 0; j
< scc
->n
; ++j
) {
5277 struct isl_sched_node
*node
= &scc
->node
[j
];
5280 if (node_update_cmap(node
) < 0)
5282 slack
= node
->nvar
- node
->rank
;
5283 if (slack
> max_slack
)
5291 /* If there are any clusters where the dimension of the current band
5292 * (i.e., the band that is to be merged) is smaller than "maxvar" and
5293 * if there are any nodes in such a cluster where the number
5294 * of remaining schedule rows that still need to be computed
5295 * is greater than "max_slack", then return the smallest current band
5296 * dimension of all these clusters. Otherwise return the original value
5297 * of "maxvar". Return -1 in case of any error.
5298 * Only clusters that are about to be merged are considered.
5299 * "c" contains information about the clusters.
5301 static int limit_maxvar_to_slack(int maxvar
, int max_slack
,
5302 struct isl_clustering
*c
)
5306 for (i
= 0; i
< c
->n
; ++i
) {
5308 struct isl_sched_graph
*scc
;
5310 if (!c
->scc_in_merge
[i
])
5313 nvar
= scc
->n_total_row
- scc
->band_start
;
5316 for (j
= 0; j
< scc
->n
; ++j
) {
5317 struct isl_sched_node
*node
= &scc
->node
[j
];
5320 if (node_update_cmap(node
) < 0)
5322 slack
= node
->nvar
- node
->rank
;
5323 if (slack
> max_slack
) {
5333 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
5334 * that still need to be computed. In particular, if there is a node
5335 * in a cluster where the dimension of the current band is smaller
5336 * than merge_graph->maxvar, but the number of remaining schedule rows
5337 * is greater than that of any node in a cluster with the maximal
5338 * dimension for the current band (i.e., merge_graph->maxvar),
5339 * then adjust merge_graph->maxvar to the (smallest) current band dimension
5340 * of those clusters. Without this adjustment, the total number of
5341 * schedule dimensions would be increased, resulting in a skewed view
5342 * of the number of coincident dimensions.
5343 * "c" contains information about the clusters.
5345 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
5346 * then there is no point in attempting any merge since it will be rejected
5347 * anyway. Set merge_graph->maxvar to zero in such cases.
5349 static isl_stat
adjust_maxvar_to_slack(isl_ctx
*ctx
,
5350 struct isl_sched_graph
*merge_graph
, struct isl_clustering
*c
)
5352 int max_slack
, maxvar
;
5354 max_slack
= compute_maxvar_max_slack(merge_graph
->maxvar
, c
);
5356 return isl_stat_error
;
5357 maxvar
= limit_maxvar_to_slack(merge_graph
->maxvar
, max_slack
, c
);
5359 return isl_stat_error
;
5361 if (maxvar
< merge_graph
->maxvar
) {
5362 if (isl_options_get_schedule_maximize_band_depth(ctx
))
5363 merge_graph
->maxvar
= 0;
5365 merge_graph
->maxvar
= maxvar
;
5371 /* Return the number of coincident dimensions in the current band of "graph",
5372 * where the nodes of "graph" are assumed to be scheduled by a single band.
5374 static int get_n_coincident(struct isl_sched_graph
*graph
)
5378 for (i
= graph
->band_start
; i
< graph
->n_total_row
; ++i
)
5379 if (!graph
->node
[0].coincident
[i
])
5382 return i
- graph
->band_start
;
5385 /* Should the clusters be merged based on the cluster schedule
5386 * in the current (and only) band of "merge_graph", given that
5387 * coincidence should be maximized?
5389 * If the number of coincident schedule dimensions in the merged band
5390 * would be less than the maximal number of coincident schedule dimensions
5391 * in any of the merged clusters, then the clusters should not be merged.
5393 static isl_bool
ok_to_merge_coincident(struct isl_clustering
*c
,
5394 struct isl_sched_graph
*merge_graph
)
5401 for (i
= 0; i
< c
->n
; ++i
) {
5402 if (!c
->scc_in_merge
[i
])
5404 n_coincident
= get_n_coincident(&c
->scc
[i
]);
5405 if (n_coincident
> max_coincident
)
5406 max_coincident
= n_coincident
;
5409 n_coincident
= get_n_coincident(merge_graph
);
5411 return n_coincident
>= max_coincident
;
5414 /* Return the transformation on "node" expressed by the current (and only)
5415 * band of "merge_graph" applied to the clusters in "c".
5417 * First find the representation of "node" in its SCC in "c" and
5418 * extract the transformation expressed by the current band.
5419 * Then extract the transformation applied by "merge_graph"
5420 * to the cluster to which this SCC belongs.
5421 * Combine the two to obtain the complete transformation on the node.
5423 * Note that the range of the first transformation is an anonymous space,
5424 * while the domain of the second is named "cluster_X". The range
5425 * of the former therefore needs to be adjusted before the two
5428 static __isl_give isl_map
*extract_node_transformation(isl_ctx
*ctx
,
5429 struct isl_sched_node
*node
, struct isl_clustering
*c
,
5430 struct isl_sched_graph
*merge_graph
)
5432 struct isl_sched_node
*scc_node
, *cluster_node
;
5436 isl_multi_aff
*ma
, *ma2
;
5438 scc_node
= graph_find_node(ctx
, &c
->scc
[node
->scc
], node
->space
);
5439 start
= c
->scc
[node
->scc
].band_start
;
5440 n
= c
->scc
[node
->scc
].n_total_row
- start
;
5441 ma
= node_extract_partial_schedule_multi_aff(scc_node
, start
, n
);
5442 space
= cluster_space(&c
->scc
[node
->scc
], c
->scc_cluster
[node
->scc
]);
5443 cluster_node
= graph_find_node(ctx
, merge_graph
, space
);
5444 if (space
&& !cluster_node
)
5445 isl_die(ctx
, isl_error_internal
, "unable to find cluster",
5446 space
= isl_space_free(space
));
5447 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
5448 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
, id
);
5449 isl_space_free(space
);
5450 n
= merge_graph
->n_total_row
;
5451 ma2
= node_extract_partial_schedule_multi_aff(cluster_node
, 0, n
);
5452 ma
= isl_multi_aff_pullback_multi_aff(ma2
, ma
);
5454 return isl_map_from_multi_aff(ma
);
5457 /* Give a set of distances "set", are they bounded by a small constant
5458 * in direction "pos"?
5459 * In practice, check if they are bounded by 2 by checking that there
5460 * are no elements with a value greater than or equal to 3 or
5461 * smaller than or equal to -3.
5463 static isl_bool
distance_is_bounded(__isl_keep isl_set
*set
, int pos
)
5469 return isl_bool_error
;
5471 test
= isl_set_copy(set
);
5472 test
= isl_set_lower_bound_si(test
, isl_dim_set
, pos
, 3);
5473 bounded
= isl_set_is_empty(test
);
5476 if (bounded
< 0 || !bounded
)
5479 test
= isl_set_copy(set
);
5480 test
= isl_set_upper_bound_si(test
, isl_dim_set
, pos
, -3);
5481 bounded
= isl_set_is_empty(test
);
5487 /* Does the set "set" have a fixed (but possible parametric) value
5488 * at dimension "pos"?
5490 static isl_bool
has_single_value(__isl_keep isl_set
*set
, int pos
)
5496 return isl_bool_error
;
5497 set
= isl_set_copy(set
);
5498 n
= isl_set_dim(set
, isl_dim_set
);
5499 set
= isl_set_project_out(set
, isl_dim_set
, pos
+ 1, n
- (pos
+ 1));
5500 set
= isl_set_project_out(set
, isl_dim_set
, 0, pos
);
5501 single
= isl_set_is_singleton(set
);
5507 /* Does "map" have a fixed (but possible parametric) value
5508 * at dimension "pos" of either its domain or its range?
5510 static isl_bool
has_singular_src_or_dst(__isl_keep isl_map
*map
, int pos
)
5515 set
= isl_map_domain(isl_map_copy(map
));
5516 single
= has_single_value(set
, pos
);
5519 if (single
< 0 || single
)
5522 set
= isl_map_range(isl_map_copy(map
));
5523 single
= has_single_value(set
, pos
);
5529 /* Does the edge "edge" from "graph" have bounded dependence distances
5530 * in the merged graph "merge_graph" of a selection of clusters in "c"?
5532 * Extract the complete transformations of the source and destination
5533 * nodes of the edge, apply them to the edge constraints and
5534 * compute the differences. Finally, check if these differences are bounded
5535 * in each direction.
5537 * If the dimension of the band is greater than the number of
5538 * dimensions that can be expected to be optimized by the edge
5539 * (based on its weight), then also allow the differences to be unbounded
5540 * in the remaining dimensions, but only if either the source or
5541 * the destination has a fixed value in that direction.
5542 * This allows a statement that produces values that are used by
5543 * several instances of another statement to be merged with that
5545 * However, merging such clusters will introduce an inherently
5546 * large proximity distance inside the merged cluster, meaning
5547 * that proximity distances will no longer be optimized in
5548 * subsequent merges. These merges are therefore only allowed
5549 * after all other possible merges have been tried.
5550 * The first time such a merge is encountered, the weight of the edge
5551 * is replaced by a negative weight. The second time (i.e., after
5552 * all merges over edges with a non-negative weight have been tried),
5553 * the merge is allowed.
5555 static isl_bool
has_bounded_distances(isl_ctx
*ctx
, struct isl_sched_edge
*edge
,
5556 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
5557 struct isl_sched_graph
*merge_graph
)
5564 map
= isl_map_copy(edge
->map
);
5565 t
= extract_node_transformation(ctx
, edge
->src
, c
, merge_graph
);
5566 map
= isl_map_apply_domain(map
, t
);
5567 t
= extract_node_transformation(ctx
, edge
->dst
, c
, merge_graph
);
5568 map
= isl_map_apply_range(map
, t
);
5569 dist
= isl_map_deltas(isl_map_copy(map
));
5571 bounded
= isl_bool_true
;
5572 n
= isl_set_dim(dist
, isl_dim_set
);
5573 n_slack
= n
- edge
->weight
;
5574 if (edge
->weight
< 0)
5575 n_slack
-= graph
->max_weight
+ 1;
5576 for (i
= 0; i
< n
; ++i
) {
5577 isl_bool bounded_i
, singular_i
;
5579 bounded_i
= distance_is_bounded(dist
, i
);
5584 if (edge
->weight
>= 0)
5585 bounded
= isl_bool_false
;
5589 singular_i
= has_singular_src_or_dst(map
, i
);
5594 bounded
= isl_bool_false
;
5597 if (!bounded
&& i
>= n
&& edge
->weight
>= 0)
5598 edge
->weight
-= graph
->max_weight
+ 1;
5606 return isl_bool_error
;
5609 /* Should the clusters be merged based on the cluster schedule
5610 * in the current (and only) band of "merge_graph"?
5611 * "graph" is the original dependence graph, while "c" records
5612 * which SCCs are involved in the latest merge.
5614 * In particular, is there at least one proximity constraint
5615 * that is optimized by the merge?
5617 * A proximity constraint is considered to be optimized
5618 * if the dependence distances are small.
5620 static isl_bool
ok_to_merge_proximity(isl_ctx
*ctx
,
5621 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
5622 struct isl_sched_graph
*merge_graph
)
5626 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5627 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5630 if (!is_proximity(edge
))
5632 if (!c
->scc_in_merge
[edge
->src
->scc
])
5634 if (!c
->scc_in_merge
[edge
->dst
->scc
])
5636 if (c
->scc_cluster
[edge
->dst
->scc
] ==
5637 c
->scc_cluster
[edge
->src
->scc
])
5639 bounded
= has_bounded_distances(ctx
, edge
, graph
, c
,
5641 if (bounded
< 0 || bounded
)
5645 return isl_bool_false
;
5648 /* Should the clusters be merged based on the cluster schedule
5649 * in the current (and only) band of "merge_graph"?
5650 * "graph" is the original dependence graph, while "c" records
5651 * which SCCs are involved in the latest merge.
5653 * If the current band is empty, then the clusters should not be merged.
5655 * If the band depth should be maximized and the merge schedule
5656 * is incomplete (meaning that the dimension of some of the schedule
5657 * bands in the original schedule will be reduced), then the clusters
5658 * should not be merged.
5660 * If the schedule_maximize_coincidence option is set, then check that
5661 * the number of coincident schedule dimensions is not reduced.
5663 * Finally, only allow the merge if at least one proximity
5664 * constraint is optimized.
5666 static isl_bool
ok_to_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5667 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
5669 if (merge_graph
->n_total_row
== merge_graph
->band_start
)
5670 return isl_bool_false
;
5672 if (isl_options_get_schedule_maximize_band_depth(ctx
) &&
5673 merge_graph
->n_total_row
< merge_graph
->maxvar
)
5674 return isl_bool_false
;
5676 if (isl_options_get_schedule_maximize_coincidence(ctx
)) {
5679 ok
= ok_to_merge_coincident(c
, merge_graph
);
5684 return ok_to_merge_proximity(ctx
, graph
, c
, merge_graph
);
5687 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
5688 * of the schedule in "node" and return the result.
5690 * That is, essentially compute
5692 * T * N(first:first+n-1)
5694 * taking into account the constant term and the parameter coefficients
5697 static __isl_give isl_mat
*node_transformation(isl_ctx
*ctx
,
5698 struct isl_sched_node
*t_node
, struct isl_sched_node
*node
,
5703 int n_row
, n_col
, n_param
, n_var
;
5705 n_param
= node
->nparam
;
5707 n_row
= isl_mat_rows(t_node
->sched
);
5708 n_col
= isl_mat_cols(node
->sched
);
5709 t
= isl_mat_alloc(ctx
, n_row
, n_col
);
5712 for (i
= 0; i
< n_row
; ++i
) {
5713 isl_seq_cpy(t
->row
[i
], t_node
->sched
->row
[i
], 1 + n_param
);
5714 isl_seq_clr(t
->row
[i
] + 1 + n_param
, n_var
);
5715 for (j
= 0; j
< n
; ++j
)
5716 isl_seq_addmul(t
->row
[i
],
5717 t_node
->sched
->row
[i
][1 + n_param
+ j
],
5718 node
->sched
->row
[first
+ j
],
5719 1 + n_param
+ n_var
);
5724 /* Apply the cluster schedule in "t_node" to the current band
5725 * schedule of the nodes in "graph".
5727 * In particular, replace the rows starting at band_start
5728 * by the result of applying the cluster schedule in "t_node"
5729 * to the original rows.
5731 * The coincidence of the schedule is determined by the coincidence
5732 * of the cluster schedule.
5734 static isl_stat
transform(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5735 struct isl_sched_node
*t_node
)
5741 start
= graph
->band_start
;
5742 n
= graph
->n_total_row
- start
;
5744 n_new
= isl_mat_rows(t_node
->sched
);
5745 for (i
= 0; i
< graph
->n
; ++i
) {
5746 struct isl_sched_node
*node
= &graph
->node
[i
];
5749 t
= node_transformation(ctx
, t_node
, node
, start
, n
);
5750 node
->sched
= isl_mat_drop_rows(node
->sched
, start
, n
);
5751 node
->sched
= isl_mat_concat(node
->sched
, t
);
5752 node
->sched_map
= isl_map_free(node
->sched_map
);
5754 return isl_stat_error
;
5755 for (j
= 0; j
< n_new
; ++j
)
5756 node
->coincident
[start
+ j
] = t_node
->coincident
[j
];
5758 graph
->n_total_row
-= n
;
5760 graph
->n_total_row
+= n_new
;
5761 graph
->n_row
+= n_new
;
5766 /* Merge the clusters marked for merging in "c" into a single
5767 * cluster using the cluster schedule in the current band of "merge_graph".
5768 * The representative SCC for the new cluster is the SCC with
5769 * the smallest index.
5771 * The current band schedule of each SCC in the new cluster is obtained
5772 * by applying the schedule of the corresponding original cluster
5773 * to the original band schedule.
5774 * All SCCs in the new cluster have the same number of schedule rows.
5776 static isl_stat
merge(isl_ctx
*ctx
, struct isl_clustering
*c
,
5777 struct isl_sched_graph
*merge_graph
)
5783 for (i
= 0; i
< c
->n
; ++i
) {
5784 struct isl_sched_node
*node
;
5786 if (!c
->scc_in_merge
[i
])
5790 space
= cluster_space(&c
->scc
[i
], c
->scc_cluster
[i
]);
5792 return isl_stat_error
;
5793 node
= graph_find_node(ctx
, merge_graph
, space
);
5794 isl_space_free(space
);
5796 isl_die(ctx
, isl_error_internal
,
5797 "unable to find cluster",
5798 return isl_stat_error
);
5799 if (transform(ctx
, &c
->scc
[i
], node
) < 0)
5800 return isl_stat_error
;
5801 c
->scc_cluster
[i
] = cluster
;
5807 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
5808 * by scheduling the current cluster bands with respect to each other.
5810 * Construct a dependence graph with a space for each cluster and
5811 * with the coordinates of each space corresponding to the schedule
5812 * dimensions of the current band of that cluster.
5813 * Construct a cluster schedule in this cluster dependence graph and
5814 * apply it to the current cluster bands if it is applicable
5815 * according to ok_to_merge.
5817 * If the number of remaining schedule dimensions in a cluster
5818 * with a non-maximal current schedule dimension is greater than
5819 * the number of remaining schedule dimensions in clusters
5820 * with a maximal current schedule dimension, then restrict
5821 * the number of rows to be computed in the cluster schedule
5822 * to the minimal such non-maximal current schedule dimension.
5823 * Do this by adjusting merge_graph.maxvar.
5825 * Return isl_bool_true if the clusters have effectively been merged
5826 * into a single cluster.
5828 * Note that since the standard scheduling algorithm minimizes the maximal
5829 * distance over proximity constraints, the proximity constraints between
5830 * the merged clusters may not be optimized any further than what is
5831 * sufficient to bring the distances within the limits of the internal
5832 * proximity constraints inside the individual clusters.
5833 * It may therefore make sense to perform an additional translation step
5834 * to bring the clusters closer to each other, while maintaining
5835 * the linear part of the merging schedule found using the standard
5836 * scheduling algorithm.
5838 static isl_bool
try_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5839 struct isl_clustering
*c
)
5841 struct isl_sched_graph merge_graph
= { 0 };
5844 if (init_merge_graph(ctx
, graph
, c
, &merge_graph
) < 0)
5847 if (compute_maxvar(&merge_graph
) < 0)
5849 if (adjust_maxvar_to_slack(ctx
, &merge_graph
,c
) < 0)
5851 if (compute_schedule_wcc_band(ctx
, &merge_graph
) < 0)
5853 merged
= ok_to_merge(ctx
, graph
, c
, &merge_graph
);
5854 if (merged
&& merge(ctx
, c
, &merge_graph
) < 0)
5857 graph_free(ctx
, &merge_graph
);
5860 graph_free(ctx
, &merge_graph
);
5861 return isl_bool_error
;
5864 /* Is there any edge marked "no_merge" between two SCCs that are
5865 * about to be merged (i.e., that are set in "scc_in_merge")?
5866 * "merge_edge" is the proximity edge along which the clusters of SCCs
5867 * are going to be merged.
5869 * If there is any edge between two SCCs with a negative weight,
5870 * while the weight of "merge_edge" is non-negative, then this
5871 * means that the edge was postponed. "merge_edge" should then
5872 * also be postponed since merging along the edge with negative weight should
5873 * be postponed until all edges with non-negative weight have been tried.
5874 * Replace the weight of "merge_edge" by a negative weight as well and
5875 * tell the caller not to attempt a merge.
5877 static int any_no_merge(struct isl_sched_graph
*graph
, int *scc_in_merge
,
5878 struct isl_sched_edge
*merge_edge
)
5882 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5883 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5885 if (!scc_in_merge
[edge
->src
->scc
])
5887 if (!scc_in_merge
[edge
->dst
->scc
])
5891 if (merge_edge
->weight
>= 0 && edge
->weight
< 0) {
5892 merge_edge
->weight
-= graph
->max_weight
+ 1;
5900 /* Merge the two clusters in "c" connected by the edge in "graph"
5901 * with index "edge" into a single cluster.
5902 * If it turns out to be impossible to merge these two clusters,
5903 * then mark the edge as "no_merge" such that it will not be
5906 * First mark all SCCs that need to be merged. This includes the SCCs
5907 * in the two clusters, but it may also include the SCCs
5908 * of intermediate clusters.
5909 * If there is already a no_merge edge between any pair of such SCCs,
5910 * then simply mark the current edge as no_merge as well.
5911 * Likewise, if any of those edges was postponed by has_bounded_distances,
5912 * then postpone the current edge as well.
5913 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
5914 * if the clusters did not end up getting merged, unless the non-merge
5915 * is due to the fact that the edge was postponed. This postponement
5916 * can be recognized by a change in weight (from non-negative to negative).
5918 static isl_stat
merge_clusters_along_edge(isl_ctx
*ctx
,
5919 struct isl_sched_graph
*graph
, int edge
, struct isl_clustering
*c
)
5922 int edge_weight
= graph
->edge
[edge
].weight
;
5924 if (mark_merge_sccs(ctx
, graph
, edge
, c
) < 0)
5925 return isl_stat_error
;
5927 if (any_no_merge(graph
, c
->scc_in_merge
, &graph
->edge
[edge
]))
5928 merged
= isl_bool_false
;
5930 merged
= try_merge(ctx
, graph
, c
);
5932 return isl_stat_error
;
5933 if (!merged
&& edge_weight
== graph
->edge
[edge
].weight
)
5934 graph
->edge
[edge
].no_merge
= 1;
5939 /* Does "node" belong to the cluster identified by "cluster"?
5941 static int node_cluster_exactly(struct isl_sched_node
*node
, int cluster
)
5943 return node
->cluster
== cluster
;
5946 /* Does "edge" connect two nodes belonging to the cluster
5947 * identified by "cluster"?
5949 static int edge_cluster_exactly(struct isl_sched_edge
*edge
, int cluster
)
5951 return edge
->src
->cluster
== cluster
&& edge
->dst
->cluster
== cluster
;
5954 /* Swap the schedule of "node1" and "node2".
5955 * Both nodes have been derived from the same node in a common parent graph.
5956 * Since the "coincident" field is shared with that node
5957 * in the parent graph, there is no need to also swap this field.
5959 static void swap_sched(struct isl_sched_node
*node1
,
5960 struct isl_sched_node
*node2
)
5965 sched
= node1
->sched
;
5966 node1
->sched
= node2
->sched
;
5967 node2
->sched
= sched
;
5969 sched_map
= node1
->sched_map
;
5970 node1
->sched_map
= node2
->sched_map
;
5971 node2
->sched_map
= sched_map
;
5974 /* Copy the current band schedule from the SCCs that form the cluster
5975 * with index "pos" to the actual cluster at position "pos".
5976 * By construction, the index of the first SCC that belongs to the cluster
5979 * The order of the nodes inside both the SCCs and the cluster
5980 * is assumed to be same as the order in the original "graph".
5982 * Since the SCC graphs will no longer be used after this function,
5983 * the schedules are actually swapped rather than copied.
5985 static isl_stat
copy_partial(struct isl_sched_graph
*graph
,
5986 struct isl_clustering
*c
, int pos
)
5990 c
->cluster
[pos
].n_total_row
= c
->scc
[pos
].n_total_row
;
5991 c
->cluster
[pos
].n_row
= c
->scc
[pos
].n_row
;
5992 c
->cluster
[pos
].maxvar
= c
->scc
[pos
].maxvar
;
5994 for (i
= 0; i
< graph
->n
; ++i
) {
5998 if (graph
->node
[i
].cluster
!= pos
)
6000 s
= graph
->node
[i
].scc
;
6001 k
= c
->scc_node
[s
]++;
6002 swap_sched(&c
->cluster
[pos
].node
[j
], &c
->scc
[s
].node
[k
]);
6003 if (c
->scc
[s
].maxvar
> c
->cluster
[pos
].maxvar
)
6004 c
->cluster
[pos
].maxvar
= c
->scc
[s
].maxvar
;
6011 /* Is there a (conditional) validity dependence from node[j] to node[i],
6012 * forcing node[i] to follow node[j] or do the nodes belong to the same
6015 static isl_bool
node_follows_strong_or_same_cluster(int i
, int j
, void *user
)
6017 struct isl_sched_graph
*graph
= user
;
6019 if (graph
->node
[i
].cluster
== graph
->node
[j
].cluster
)
6020 return isl_bool_true
;
6021 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
6024 /* Extract the merged clusters of SCCs in "graph", sort them, and
6025 * store them in c->clusters. Update c->scc_cluster accordingly.
6027 * First keep track of the cluster containing the SCC to which a node
6028 * belongs in the node itself.
6029 * Then extract the clusters into c->clusters, copying the current
6030 * band schedule from the SCCs that belong to the cluster.
6031 * Do this only once per cluster.
6033 * Finally, topologically sort the clusters and update c->scc_cluster
6034 * to match the new scc numbering. While the SCCs were originally
6035 * sorted already, some SCCs that depend on some other SCCs may
6036 * have been merged with SCCs that appear before these other SCCs.
6037 * A reordering may therefore be required.
6039 static isl_stat
extract_clusters(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6040 struct isl_clustering
*c
)
6044 for (i
= 0; i
< graph
->n
; ++i
)
6045 graph
->node
[i
].cluster
= c
->scc_cluster
[graph
->node
[i
].scc
];
6047 for (i
= 0; i
< graph
->scc
; ++i
) {
6048 if (c
->scc_cluster
[i
] != i
)
6050 if (extract_sub_graph(ctx
, graph
, &node_cluster_exactly
,
6051 &edge_cluster_exactly
, i
, &c
->cluster
[i
]) < 0)
6052 return isl_stat_error
;
6053 c
->cluster
[i
].src_scc
= -1;
6054 c
->cluster
[i
].dst_scc
= -1;
6055 if (copy_partial(graph
, c
, i
) < 0)
6056 return isl_stat_error
;
6059 if (detect_ccs(ctx
, graph
, &node_follows_strong_or_same_cluster
) < 0)
6060 return isl_stat_error
;
6061 for (i
= 0; i
< graph
->n
; ++i
)
6062 c
->scc_cluster
[graph
->node
[i
].scc
] = graph
->node
[i
].cluster
;
6067 /* Compute weights on the proximity edges of "graph" that can
6068 * be used by find_proximity to find the most appropriate
6069 * proximity edge to use to merge two clusters in "c".
6070 * The weights are also used by has_bounded_distances to determine
6071 * whether the merge should be allowed.
6072 * Store the maximum of the computed weights in graph->max_weight.
6074 * The computed weight is a measure for the number of remaining schedule
6075 * dimensions that can still be completely aligned.
6076 * In particular, compute the number of equalities between
6077 * input dimensions and output dimensions in the proximity constraints.
6078 * The directions that are already handled by outer schedule bands
6079 * are projected out prior to determining this number.
6081 * Edges that will never be considered by find_proximity are ignored.
6083 static isl_stat
compute_weights(struct isl_sched_graph
*graph
,
6084 struct isl_clustering
*c
)
6088 graph
->max_weight
= 0;
6090 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6091 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6092 struct isl_sched_node
*src
= edge
->src
;
6093 struct isl_sched_node
*dst
= edge
->dst
;
6094 isl_basic_map
*hull
;
6097 if (!is_proximity(edge
))
6099 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
6100 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
6102 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6103 c
->scc_cluster
[edge
->src
->scc
])
6106 hull
= isl_map_affine_hull(isl_map_copy(edge
->map
));
6107 hull
= isl_basic_map_transform_dims(hull
, isl_dim_in
, 0,
6108 isl_mat_copy(src
->ctrans
));
6109 hull
= isl_basic_map_transform_dims(hull
, isl_dim_out
, 0,
6110 isl_mat_copy(dst
->ctrans
));
6111 hull
= isl_basic_map_project_out(hull
,
6112 isl_dim_in
, 0, src
->rank
);
6113 hull
= isl_basic_map_project_out(hull
,
6114 isl_dim_out
, 0, dst
->rank
);
6115 hull
= isl_basic_map_remove_divs(hull
);
6116 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
6117 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
6118 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6119 isl_dim_in
, 0, n_in
);
6120 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6121 isl_dim_out
, 0, n_out
);
6123 return isl_stat_error
;
6124 edge
->weight
= hull
->n_eq
;
6125 isl_basic_map_free(hull
);
6127 if (edge
->weight
> graph
->max_weight
)
6128 graph
->max_weight
= edge
->weight
;
6134 /* Call compute_schedule_finish_band on each of the clusters in "c"
6135 * in their topological order. This order is determined by the scc
6136 * fields of the nodes in "graph".
6137 * Combine the results in a sequence expressing the topological order.
6139 * If there is only one cluster left, then there is no need to introduce
6140 * a sequence node. Also, in this case, the cluster necessarily contains
6141 * the SCC at position 0 in the original graph and is therefore also
6142 * stored in the first cluster of "c".
6144 static __isl_give isl_schedule_node
*finish_bands_clustering(
6145 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6146 struct isl_clustering
*c
)
6150 isl_union_set_list
*filters
;
6152 if (graph
->scc
== 1)
6153 return compute_schedule_finish_band(node
, &c
->cluster
[0], 0);
6155 ctx
= isl_schedule_node_get_ctx(node
);
6157 filters
= extract_sccs(ctx
, graph
);
6158 node
= isl_schedule_node_insert_sequence(node
, filters
);
6160 for (i
= 0; i
< graph
->scc
; ++i
) {
6161 int j
= c
->scc_cluster
[i
];
6162 node
= isl_schedule_node_child(node
, i
);
6163 node
= isl_schedule_node_child(node
, 0);
6164 node
= compute_schedule_finish_band(node
, &c
->cluster
[j
], 0);
6165 node
= isl_schedule_node_parent(node
);
6166 node
= isl_schedule_node_parent(node
);
6172 /* Compute a schedule for a connected dependence graph by first considering
6173 * each strongly connected component (SCC) in the graph separately and then
6174 * incrementally combining them into clusters.
6175 * Return the updated schedule node.
6177 * Initially, each cluster consists of a single SCC, each with its
6178 * own band schedule. The algorithm then tries to merge pairs
6179 * of clusters along a proximity edge until no more suitable
6180 * proximity edges can be found. During this merging, the schedule
6181 * is maintained in the individual SCCs.
6182 * After the merging is completed, the full resulting clusters
6183 * are extracted and in finish_bands_clustering,
6184 * compute_schedule_finish_band is called on each of them to integrate
6185 * the band into "node" and to continue the computation.
6187 * compute_weights initializes the weights that are used by find_proximity.
6189 static __isl_give isl_schedule_node
*compute_schedule_wcc_clustering(
6190 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6193 struct isl_clustering c
;
6196 ctx
= isl_schedule_node_get_ctx(node
);
6198 if (clustering_init(ctx
, &c
, graph
) < 0)
6201 if (compute_weights(graph
, &c
) < 0)
6205 i
= find_proximity(graph
, &c
);
6208 if (i
>= graph
->n_edge
)
6210 if (merge_clusters_along_edge(ctx
, graph
, i
, &c
) < 0)
6214 if (extract_clusters(ctx
, graph
, &c
) < 0)
6217 node
= finish_bands_clustering(node
, graph
, &c
);
6219 clustering_free(ctx
, &c
);
6222 clustering_free(ctx
, &c
);
6223 return isl_schedule_node_free(node
);
6226 /* Compute a schedule for a connected dependence graph and return
6227 * the updated schedule node.
6229 * If Feautrier's algorithm is selected, we first recursively try to satisfy
6230 * as many validity dependences as possible. When all validity dependences
6231 * are satisfied we extend the schedule to a full-dimensional schedule.
6233 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
6234 * depending on whether the user has selected the option to try and
6235 * compute a schedule for the entire (weakly connected) component first.
6236 * If there is only a single strongly connected component (SCC), then
6237 * there is no point in trying to combine SCCs
6238 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
6239 * is called instead.
6241 static __isl_give isl_schedule_node
*compute_schedule_wcc(
6242 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6249 ctx
= isl_schedule_node_get_ctx(node
);
6250 if (detect_sccs(ctx
, graph
) < 0)
6251 return isl_schedule_node_free(node
);
6253 if (compute_maxvar(graph
) < 0)
6254 return isl_schedule_node_free(node
);
6256 if (need_feautrier_step(ctx
, graph
))
6257 return compute_schedule_wcc_feautrier(node
, graph
);
6259 if (graph
->scc
<= 1 || isl_options_get_schedule_whole_component(ctx
))
6260 return compute_schedule_wcc_whole(node
, graph
);
6262 return compute_schedule_wcc_clustering(node
, graph
);
6265 /* Compute a schedule for each group of nodes identified by node->scc
6266 * separately and then combine them in a sequence node (or as set node
6267 * if graph->weak is set) inserted at position "node" of the schedule tree.
6268 * Return the updated schedule node.
6270 * If "wcc" is set then each of the groups belongs to a single
6271 * weakly connected component in the dependence graph so that
6272 * there is no need for compute_sub_schedule to look for weakly
6273 * connected components.
6275 static __isl_give isl_schedule_node
*compute_component_schedule(
6276 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6281 isl_union_set_list
*filters
;
6285 ctx
= isl_schedule_node_get_ctx(node
);
6287 filters
= extract_sccs(ctx
, graph
);
6289 node
= isl_schedule_node_insert_set(node
, filters
);
6291 node
= isl_schedule_node_insert_sequence(node
, filters
);
6293 for (component
= 0; component
< graph
->scc
; ++component
) {
6294 node
= isl_schedule_node_child(node
, component
);
6295 node
= isl_schedule_node_child(node
, 0);
6296 node
= compute_sub_schedule(node
, ctx
, graph
,
6298 &edge_scc_exactly
, component
, wcc
);
6299 node
= isl_schedule_node_parent(node
);
6300 node
= isl_schedule_node_parent(node
);
6306 /* Compute a schedule for the given dependence graph and insert it at "node".
6307 * Return the updated schedule node.
6309 * We first check if the graph is connected (through validity and conditional
6310 * validity dependences) and, if not, compute a schedule
6311 * for each component separately.
6312 * If the schedule_serialize_sccs option is set, then we check for strongly
6313 * connected components instead and compute a separate schedule for
6314 * each such strongly connected component.
6316 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
6317 struct isl_sched_graph
*graph
)
6324 ctx
= isl_schedule_node_get_ctx(node
);
6325 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
6326 if (detect_sccs(ctx
, graph
) < 0)
6327 return isl_schedule_node_free(node
);
6329 if (detect_wccs(ctx
, graph
) < 0)
6330 return isl_schedule_node_free(node
);
6334 return compute_component_schedule(node
, graph
, 1);
6336 return compute_schedule_wcc(node
, graph
);
6339 /* Compute a schedule on sc->domain that respects the given schedule
6342 * In particular, the schedule respects all the validity dependences.
6343 * If the default isl scheduling algorithm is used, it tries to minimize
6344 * the dependence distances over the proximity dependences.
6345 * If Feautrier's scheduling algorithm is used, the proximity dependence
6346 * distances are only minimized during the extension to a full-dimensional
6349 * If there are any condition and conditional validity dependences,
6350 * then the conditional validity dependences may be violated inside
6351 * a tilable band, provided they have no adjacent non-local
6352 * condition dependences.
6354 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
6355 __isl_take isl_schedule_constraints
*sc
)
6357 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
6358 struct isl_sched_graph graph
= { 0 };
6359 isl_schedule
*sched
;
6360 isl_schedule_node
*node
;
6361 isl_union_set
*domain
;
6363 sc
= isl_schedule_constraints_align_params(sc
);
6365 domain
= isl_schedule_constraints_get_domain(sc
);
6366 if (isl_union_set_n_set(domain
) == 0) {
6367 isl_schedule_constraints_free(sc
);
6368 return isl_schedule_from_domain(domain
);
6371 if (graph_init(&graph
, sc
) < 0)
6372 domain
= isl_union_set_free(domain
);
6374 node
= isl_schedule_node_from_domain(domain
);
6375 node
= isl_schedule_node_child(node
, 0);
6377 node
= compute_schedule(node
, &graph
);
6378 sched
= isl_schedule_node_get_schedule(node
);
6379 isl_schedule_node_free(node
);
6381 graph_free(ctx
, &graph
);
6382 isl_schedule_constraints_free(sc
);
6387 /* Compute a schedule for the given union of domains that respects
6388 * all the validity dependences and minimizes
6389 * the dependence distances over the proximity dependences.
6391 * This function is kept for backward compatibility.
6393 __isl_give isl_schedule
*isl_union_set_compute_schedule(
6394 __isl_take isl_union_set
*domain
,
6395 __isl_take isl_union_map
*validity
,
6396 __isl_take isl_union_map
*proximity
)
6398 isl_schedule_constraints
*sc
;
6400 sc
= isl_schedule_constraints_on_domain(domain
);
6401 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
6402 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
6404 return isl_schedule_constraints_compute_schedule(sc
);