2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015-2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <isl_ctx_private.h>
15 #include <isl_map_private.h>
16 #include <isl_space_private.h>
17 #include <isl_aff_private.h>
19 #include <isl/constraint.h>
20 #include <isl/schedule.h>
21 #include <isl/schedule_node.h>
22 #include <isl_mat_private.h>
23 #include <isl_vec_private.h>
25 #include <isl/union_set.h>
28 #include <isl_dim_map.h>
29 #include <isl/map_to_basic_set.h>
31 #include <isl_options_private.h>
32 #include <isl_tarjan.h>
33 #include <isl_morph.h>
36 * The scheduling algorithm implemented in this file was inspired by
37 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
38 * Parallelization and Locality Optimization in the Polyhedral Model".
42 isl_edge_validity
= 0,
43 isl_edge_first
= isl_edge_validity
,
46 isl_edge_conditional_validity
,
48 isl_edge_last
= isl_edge_proximity
,
52 /* The constraints that need to be satisfied by a schedule on "domain".
54 * "context" specifies extra constraints on the parameters.
56 * "validity" constraints map domain elements i to domain elements
57 * that should be scheduled after i. (Hard constraint)
58 * "proximity" constraints map domain elements i to domains elements
59 * that should be scheduled as early as possible after i (or before i).
62 * "condition" and "conditional_validity" constraints map possibly "tagged"
63 * domain elements i -> s to "tagged" domain elements j -> t.
64 * The elements of the "conditional_validity" constraints, but without the
65 * tags (i.e., the elements i -> j) are treated as validity constraints,
66 * except that during the construction of a tilable band,
67 * the elements of the "conditional_validity" constraints may be violated
68 * provided that all adjacent elements of the "condition" constraints
69 * are local within the band.
70 * A dependence is local within a band if domain and range are mapped
71 * to the same schedule point by the band.
73 struct isl_schedule_constraints
{
74 isl_union_set
*domain
;
77 isl_union_map
*constraint
[isl_edge_last
+ 1];
80 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
81 __isl_keep isl_schedule_constraints
*sc
)
84 isl_schedule_constraints
*sc_copy
;
87 ctx
= isl_union_set_get_ctx(sc
->domain
);
88 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
92 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
93 sc_copy
->context
= isl_set_copy(sc
->context
);
94 if (!sc_copy
->domain
|| !sc_copy
->context
)
95 return isl_schedule_constraints_free(sc_copy
);
97 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
98 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
99 if (!sc_copy
->constraint
[i
])
100 return isl_schedule_constraints_free(sc_copy
);
107 /* Construct an isl_schedule_constraints object for computing a schedule
108 * on "domain". The initial object does not impose any constraints.
110 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
111 __isl_take isl_union_set
*domain
)
115 isl_schedule_constraints
*sc
;
116 isl_union_map
*empty
;
117 enum isl_edge_type i
;
122 ctx
= isl_union_set_get_ctx(domain
);
123 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
127 space
= isl_union_set_get_space(domain
);
129 sc
->context
= isl_set_universe(isl_space_copy(space
));
130 empty
= isl_union_map_empty(space
);
131 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
132 sc
->constraint
[i
] = isl_union_map_copy(empty
);
133 if (!sc
->constraint
[i
])
134 sc
->domain
= isl_union_set_free(sc
->domain
);
136 isl_union_map_free(empty
);
138 if (!sc
->domain
|| !sc
->context
)
139 return isl_schedule_constraints_free(sc
);
143 isl_union_set_free(domain
);
147 /* Replace the context of "sc" by "context".
149 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_context(
150 __isl_take isl_schedule_constraints
*sc
, __isl_take isl_set
*context
)
155 isl_set_free(sc
->context
);
156 sc
->context
= context
;
160 isl_schedule_constraints_free(sc
);
161 isl_set_free(context
);
165 /* Replace the validity constraints of "sc" by "validity".
167 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
168 __isl_take isl_schedule_constraints
*sc
,
169 __isl_take isl_union_map
*validity
)
171 if (!sc
|| !validity
)
174 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
175 sc
->constraint
[isl_edge_validity
] = validity
;
179 isl_schedule_constraints_free(sc
);
180 isl_union_map_free(validity
);
184 /* Replace the coincidence constraints of "sc" by "coincidence".
186 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
187 __isl_take isl_schedule_constraints
*sc
,
188 __isl_take isl_union_map
*coincidence
)
190 if (!sc
|| !coincidence
)
193 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
194 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
198 isl_schedule_constraints_free(sc
);
199 isl_union_map_free(coincidence
);
203 /* Replace the proximity constraints of "sc" by "proximity".
205 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
206 __isl_take isl_schedule_constraints
*sc
,
207 __isl_take isl_union_map
*proximity
)
209 if (!sc
|| !proximity
)
212 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
213 sc
->constraint
[isl_edge_proximity
] = proximity
;
217 isl_schedule_constraints_free(sc
);
218 isl_union_map_free(proximity
);
222 /* Replace the conditional validity constraints of "sc" by "condition"
225 __isl_give isl_schedule_constraints
*
226 isl_schedule_constraints_set_conditional_validity(
227 __isl_take isl_schedule_constraints
*sc
,
228 __isl_take isl_union_map
*condition
,
229 __isl_take isl_union_map
*validity
)
231 if (!sc
|| !condition
|| !validity
)
234 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
235 sc
->constraint
[isl_edge_condition
] = condition
;
236 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
237 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
241 isl_schedule_constraints_free(sc
);
242 isl_union_map_free(condition
);
243 isl_union_map_free(validity
);
247 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
248 __isl_take isl_schedule_constraints
*sc
)
250 enum isl_edge_type i
;
255 isl_union_set_free(sc
->domain
);
256 isl_set_free(sc
->context
);
257 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
258 isl_union_map_free(sc
->constraint
[i
]);
265 isl_ctx
*isl_schedule_constraints_get_ctx(
266 __isl_keep isl_schedule_constraints
*sc
)
268 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
271 /* Return the domain of "sc".
273 __isl_give isl_union_set
*isl_schedule_constraints_get_domain(
274 __isl_keep isl_schedule_constraints
*sc
)
279 return isl_union_set_copy(sc
->domain
);
282 /* Return the validity constraints of "sc".
284 __isl_give isl_union_map
*isl_schedule_constraints_get_validity(
285 __isl_keep isl_schedule_constraints
*sc
)
290 return isl_union_map_copy(sc
->constraint
[isl_edge_validity
]);
293 /* Return the coincidence constraints of "sc".
295 __isl_give isl_union_map
*isl_schedule_constraints_get_coincidence(
296 __isl_keep isl_schedule_constraints
*sc
)
301 return isl_union_map_copy(sc
->constraint
[isl_edge_coincidence
]);
304 /* Return the proximity constraints of "sc".
306 __isl_give isl_union_map
*isl_schedule_constraints_get_proximity(
307 __isl_keep isl_schedule_constraints
*sc
)
312 return isl_union_map_copy(sc
->constraint
[isl_edge_proximity
]);
315 /* Return the conditional validity constraints of "sc".
317 __isl_give isl_union_map
*isl_schedule_constraints_get_conditional_validity(
318 __isl_keep isl_schedule_constraints
*sc
)
324 isl_union_map_copy(sc
->constraint
[isl_edge_conditional_validity
]);
327 /* Return the conditions for the conditional validity constraints of "sc".
329 __isl_give isl_union_map
*
330 isl_schedule_constraints_get_conditional_validity_condition(
331 __isl_keep isl_schedule_constraints
*sc
)
336 return isl_union_map_copy(sc
->constraint
[isl_edge_condition
]);
339 /* Can a schedule constraint of type "type" be tagged?
341 static int may_be_tagged(enum isl_edge_type type
)
343 if (type
== isl_edge_condition
|| type
== isl_edge_conditional_validity
)
348 /* Apply "umap" to the domains of the wrapped relations
349 * inside the domain and range of "c".
351 * That is, for each map of the form
353 * [D -> S] -> [E -> T]
355 * in "c", apply "umap" to D and E.
357 * D is exposed by currying the relation to
359 * D -> [S -> [E -> T]]
361 * E is exposed by doing the same to the inverse of "c".
363 static __isl_give isl_union_map
*apply_factor_domain(
364 __isl_take isl_union_map
*c
, __isl_keep isl_union_map
*umap
)
366 c
= isl_union_map_curry(c
);
367 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
368 c
= isl_union_map_uncurry(c
);
370 c
= isl_union_map_reverse(c
);
371 c
= isl_union_map_curry(c
);
372 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
373 c
= isl_union_map_uncurry(c
);
374 c
= isl_union_map_reverse(c
);
379 /* Apply "umap" to domain and range of "c".
380 * If "tag" is set, then "c" may contain tags and then "umap"
381 * needs to be applied to the domains of the wrapped relations
382 * inside the domain and range of "c".
384 static __isl_give isl_union_map
*apply(__isl_take isl_union_map
*c
,
385 __isl_keep isl_union_map
*umap
, int tag
)
390 t
= isl_union_map_copy(c
);
391 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
392 c
= isl_union_map_apply_range(c
, isl_union_map_copy(umap
));
395 t
= apply_factor_domain(t
, umap
);
396 c
= isl_union_map_union(c
, t
);
400 /* Apply "umap" to the domain of the schedule constraints "sc".
402 * The two sides of the various schedule constraints are adjusted
405 __isl_give isl_schedule_constraints
*isl_schedule_constraints_apply(
406 __isl_take isl_schedule_constraints
*sc
,
407 __isl_take isl_union_map
*umap
)
409 enum isl_edge_type i
;
414 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
415 int tag
= may_be_tagged(i
);
417 sc
->constraint
[i
] = apply(sc
->constraint
[i
], umap
, tag
);
418 if (!sc
->constraint
[i
])
421 sc
->domain
= isl_union_set_apply(sc
->domain
, umap
);
423 return isl_schedule_constraints_free(sc
);
427 isl_schedule_constraints_free(sc
);
428 isl_union_map_free(umap
);
432 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
437 fprintf(stderr
, "domain: ");
438 isl_union_set_dump(sc
->domain
);
439 fprintf(stderr
, "context: ");
440 isl_set_dump(sc
->context
);
441 fprintf(stderr
, "validity: ");
442 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
443 fprintf(stderr
, "proximity: ");
444 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
445 fprintf(stderr
, "coincidence: ");
446 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
447 fprintf(stderr
, "condition: ");
448 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
449 fprintf(stderr
, "conditional_validity: ");
450 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
453 /* Align the parameters of the fields of "sc".
455 static __isl_give isl_schedule_constraints
*
456 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
459 enum isl_edge_type i
;
464 space
= isl_union_set_get_space(sc
->domain
);
465 space
= isl_space_align_params(space
, isl_set_get_space(sc
->context
));
466 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
467 space
= isl_space_align_params(space
,
468 isl_union_map_get_space(sc
->constraint
[i
]));
470 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
471 sc
->constraint
[i
] = isl_union_map_align_params(
472 sc
->constraint
[i
], isl_space_copy(space
));
473 if (!sc
->constraint
[i
])
474 space
= isl_space_free(space
);
476 sc
->context
= isl_set_align_params(sc
->context
, isl_space_copy(space
));
477 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
478 if (!sc
->context
|| !sc
->domain
)
479 return isl_schedule_constraints_free(sc
);
484 /* Return the total number of isl_maps in the constraints of "sc".
486 static __isl_give
int isl_schedule_constraints_n_map(
487 __isl_keep isl_schedule_constraints
*sc
)
489 enum isl_edge_type i
;
492 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
493 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
498 /* Internal information about a node that is used during the construction
500 * space represents the space in which the domain lives
501 * sched is a matrix representation of the schedule being constructed
502 * for this node; if compressed is set, then this schedule is
503 * defined over the compressed domain space
504 * sched_map is an isl_map representation of the same (partial) schedule
505 * sched_map may be NULL; if compressed is set, then this map
506 * is defined over the uncompressed domain space
507 * rank is the number of linearly independent rows in the linear part
509 * the columns of cmap represent a change of basis for the schedule
510 * coefficients; the first rank columns span the linear part of
512 * cinv is the inverse of cmap.
513 * ctrans is the transpose of cmap.
514 * start is the first variable in the LP problem in the sequences that
515 * represents the schedule coefficients of this node
516 * nvar is the dimension of the domain
517 * nparam is the number of parameters or 0 if we are not constructing
518 * a parametric schedule
520 * If compressed is set, then hull represents the constraints
521 * that were used to derive the compression, while compress and
522 * decompress map the original space to the compressed space and
525 * scc is the index of SCC (or WCC) this node belongs to
527 * "cluster" is only used inside extract_clusters and identifies
528 * the cluster of SCCs that the node belongs to.
530 * coincident contains a boolean for each of the rows of the schedule,
531 * indicating whether the corresponding scheduling dimension satisfies
532 * the coincidence constraints in the sense that the corresponding
533 * dependence distances are zero.
535 struct isl_sched_node
{
539 isl_multi_aff
*compress
;
540 isl_multi_aff
*decompress
;
557 static int node_has_space(const void *entry
, const void *val
)
559 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
560 isl_space
*dim
= (isl_space
*)val
;
562 return isl_space_is_equal(node
->space
, dim
);
565 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
567 return node
->scc
== scc
;
570 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
572 return node
->scc
<= scc
;
575 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
577 return node
->scc
>= scc
;
580 /* An edge in the dependence graph. An edge may be used to
581 * ensure validity of the generated schedule, to minimize the dependence
584 * map is the dependence relation, with i -> j in the map if j depends on i
585 * tagged_condition and tagged_validity contain the union of all tagged
586 * condition or conditional validity dependence relations that
587 * specialize the dependence relation "map"; that is,
588 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
589 * or "tagged_validity", then i -> j is an element of "map".
590 * If these fields are NULL, then they represent the empty relation.
591 * src is the source node
592 * dst is the sink node
594 * types is a bit vector containing the types of this edge.
595 * validity is set if the edge is used to ensure correctness
596 * coincidence is used to enforce zero dependence distances
597 * proximity is set if the edge is used to minimize dependence distances
598 * condition is set if the edge represents a condition
599 * for a conditional validity schedule constraint
600 * local can only be set for condition edges and indicates that
601 * the dependence distance over the edge should be zero
602 * conditional_validity is set if the edge is used to conditionally
605 * For validity edges, start and end mark the sequence of inequality
606 * constraints in the LP problem that encode the validity constraint
607 * corresponding to this edge.
609 * During clustering, an edge may be marked "no_merge" if it should
610 * not be used to merge clusters.
611 * The weight is also only used during clustering and it is
612 * an indication of how many schedule dimensions on either side
613 * of the schedule constraints can be aligned.
614 * If the weight is negative, then this means that this edge was postponed
615 * by has_bounded_distances or any_no_merge. The original weight can
616 * be retrieved by adding 1 + graph->max_weight, with "graph"
617 * the graph containing this edge.
619 struct isl_sched_edge
{
621 isl_union_map
*tagged_condition
;
622 isl_union_map
*tagged_validity
;
624 struct isl_sched_node
*src
;
625 struct isl_sched_node
*dst
;
636 /* Is "edge" marked as being of type "type"?
638 static int is_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
640 return ISL_FL_ISSET(edge
->types
, 1 << type
);
643 /* Mark "edge" as being of type "type".
645 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
647 ISL_FL_SET(edge
->types
, 1 << type
);
650 /* No longer mark "edge" as being of type "type"?
652 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
654 ISL_FL_CLR(edge
->types
, 1 << type
);
657 /* Is "edge" marked as a validity edge?
659 static int is_validity(struct isl_sched_edge
*edge
)
661 return is_type(edge
, isl_edge_validity
);
664 /* Mark "edge" as a validity edge.
666 static void set_validity(struct isl_sched_edge
*edge
)
668 set_type(edge
, isl_edge_validity
);
671 /* Is "edge" marked as a proximity edge?
673 static int is_proximity(struct isl_sched_edge
*edge
)
675 return is_type(edge
, isl_edge_proximity
);
678 /* Is "edge" marked as a local edge?
680 static int is_local(struct isl_sched_edge
*edge
)
682 return is_type(edge
, isl_edge_local
);
685 /* Mark "edge" as a local edge.
687 static void set_local(struct isl_sched_edge
*edge
)
689 set_type(edge
, isl_edge_local
);
692 /* No longer mark "edge" as a local edge.
694 static void clear_local(struct isl_sched_edge
*edge
)
696 clear_type(edge
, isl_edge_local
);
699 /* Is "edge" marked as a coincidence edge?
701 static int is_coincidence(struct isl_sched_edge
*edge
)
703 return is_type(edge
, isl_edge_coincidence
);
706 /* Is "edge" marked as a condition edge?
708 static int is_condition(struct isl_sched_edge
*edge
)
710 return is_type(edge
, isl_edge_condition
);
713 /* Is "edge" marked as a conditional validity edge?
715 static int is_conditional_validity(struct isl_sched_edge
*edge
)
717 return is_type(edge
, isl_edge_conditional_validity
);
720 /* Internal information about the dependence graph used during
721 * the construction of the schedule.
723 * intra_hmap is a cache, mapping dependence relations to their dual,
724 * for dependences from a node to itself
725 * inter_hmap is a cache, mapping dependence relations to their dual,
726 * for dependences between distinct nodes
727 * if compression is involved then the key for these maps
728 * is the original, uncompressed dependence relation, while
729 * the value is the dual of the compressed dependence relation.
731 * n is the number of nodes
732 * node is the list of nodes
733 * maxvar is the maximal number of variables over all nodes
734 * max_row is the allocated number of rows in the schedule
735 * n_row is the current (maximal) number of linearly independent
736 * rows in the node schedules
737 * n_total_row is the current number of rows in the node schedules
738 * band_start is the starting row in the node schedules of the current band
739 * root is set if this graph is the original dependence graph,
740 * without any splitting
742 * sorted contains a list of node indices sorted according to the
743 * SCC to which a node belongs
745 * n_edge is the number of edges
746 * edge is the list of edges
747 * max_edge contains the maximal number of edges of each type;
748 * in particular, it contains the number of edges in the inital graph.
749 * edge_table contains pointers into the edge array, hashed on the source
750 * and sink spaces; there is one such table for each type;
751 * a given edge may be referenced from more than one table
752 * if the corresponding relation appears in more than one of the
753 * sets of dependences; however, for each type there is only
754 * a single edge between a given pair of source and sink space
755 * in the entire graph
757 * node_table contains pointers into the node array, hashed on the space
759 * region contains a list of variable sequences that should be non-trivial
761 * lp contains the (I)LP problem used to obtain new schedule rows
763 * src_scc and dst_scc are the source and sink SCCs of an edge with
764 * conflicting constraints
766 * scc represents the number of components
767 * weak is set if the components are weakly connected
769 * max_weight is used during clustering and represents the maximal
770 * weight of the relevant proximity edges.
772 struct isl_sched_graph
{
773 isl_map_to_basic_set
*intra_hmap
;
774 isl_map_to_basic_set
*inter_hmap
;
776 struct isl_sched_node
*node
;
789 struct isl_sched_edge
*edge
;
791 int max_edge
[isl_edge_last
+ 1];
792 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
794 struct isl_hash_table
*node_table
;
795 struct isl_region
*region
;
808 /* Initialize node_table based on the list of nodes.
810 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
814 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
815 if (!graph
->node_table
)
818 for (i
= 0; i
< graph
->n
; ++i
) {
819 struct isl_hash_table_entry
*entry
;
822 hash
= isl_space_get_hash(graph
->node
[i
].space
);
823 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
825 graph
->node
[i
].space
, 1);
828 entry
->data
= &graph
->node
[i
];
834 /* Return a pointer to the node that lives within the given space,
835 * or NULL if there is no such node.
837 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
838 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
840 struct isl_hash_table_entry
*entry
;
843 hash
= isl_space_get_hash(dim
);
844 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
845 &node_has_space
, dim
, 0);
847 return entry
? entry
->data
: NULL
;
850 static int edge_has_src_and_dst(const void *entry
, const void *val
)
852 const struct isl_sched_edge
*edge
= entry
;
853 const struct isl_sched_edge
*temp
= val
;
855 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
858 /* Add the given edge to graph->edge_table[type].
860 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
861 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
862 struct isl_sched_edge
*edge
)
864 struct isl_hash_table_entry
*entry
;
867 hash
= isl_hash_init();
868 hash
= isl_hash_builtin(hash
, edge
->src
);
869 hash
= isl_hash_builtin(hash
, edge
->dst
);
870 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
871 &edge_has_src_and_dst
, edge
, 1);
873 return isl_stat_error
;
879 /* Allocate the edge_tables based on the maximal number of edges of
882 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
886 for (i
= 0; i
<= isl_edge_last
; ++i
) {
887 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
889 if (!graph
->edge_table
[i
])
896 /* If graph->edge_table[type] contains an edge from the given source
897 * to the given destination, then return the hash table entry of this edge.
898 * Otherwise, return NULL.
900 static struct isl_hash_table_entry
*graph_find_edge_entry(
901 struct isl_sched_graph
*graph
,
902 enum isl_edge_type type
,
903 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
905 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
907 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
909 hash
= isl_hash_init();
910 hash
= isl_hash_builtin(hash
, temp
.src
);
911 hash
= isl_hash_builtin(hash
, temp
.dst
);
912 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
913 &edge_has_src_and_dst
, &temp
, 0);
917 /* If graph->edge_table[type] contains an edge from the given source
918 * to the given destination, then return this edge.
919 * Otherwise, return NULL.
921 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
922 enum isl_edge_type type
,
923 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
925 struct isl_hash_table_entry
*entry
;
927 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
934 /* Check whether the dependence graph has an edge of the given type
935 * between the given two nodes.
937 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
938 enum isl_edge_type type
,
939 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
941 struct isl_sched_edge
*edge
;
944 edge
= graph_find_edge(graph
, type
, src
, dst
);
948 empty
= isl_map_plain_is_empty(edge
->map
);
950 return isl_bool_error
;
955 /* Look for any edge with the same src, dst and map fields as "model".
957 * Return the matching edge if one can be found.
958 * Return "model" if no matching edge is found.
959 * Return NULL on error.
961 static struct isl_sched_edge
*graph_find_matching_edge(
962 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
964 enum isl_edge_type i
;
965 struct isl_sched_edge
*edge
;
967 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
970 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
973 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
983 /* Remove the given edge from all the edge_tables that refer to it.
985 static void graph_remove_edge(struct isl_sched_graph
*graph
,
986 struct isl_sched_edge
*edge
)
988 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
989 enum isl_edge_type i
;
991 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
992 struct isl_hash_table_entry
*entry
;
994 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
997 if (entry
->data
!= edge
)
999 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
1003 /* Check whether the dependence graph has any edge
1004 * between the given two nodes.
1006 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
1007 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1009 enum isl_edge_type i
;
1012 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1013 r
= graph_has_edge(graph
, i
, src
, dst
);
1021 /* Check whether the dependence graph has a validity edge
1022 * between the given two nodes.
1024 * Conditional validity edges are essentially validity edges that
1025 * can be ignored if the corresponding condition edges are iteration private.
1026 * Here, we are only checking for the presence of validity
1027 * edges, so we need to consider the conditional validity edges too.
1028 * In particular, this function is used during the detection
1029 * of strongly connected components and we cannot ignore
1030 * conditional validity edges during this detection.
1032 static isl_bool
graph_has_validity_edge(struct isl_sched_graph
*graph
,
1033 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1037 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
1041 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
1044 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1045 int n_node
, int n_edge
)
1050 graph
->n_edge
= n_edge
;
1051 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
1052 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
1053 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
1054 graph
->edge
= isl_calloc_array(ctx
,
1055 struct isl_sched_edge
, graph
->n_edge
);
1057 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
1058 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
1060 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
1064 for(i
= 0; i
< graph
->n
; ++i
)
1065 graph
->sorted
[i
] = i
;
1070 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1074 isl_map_to_basic_set_free(graph
->intra_hmap
);
1075 isl_map_to_basic_set_free(graph
->inter_hmap
);
1078 for (i
= 0; i
< graph
->n
; ++i
) {
1079 isl_space_free(graph
->node
[i
].space
);
1080 isl_set_free(graph
->node
[i
].hull
);
1081 isl_multi_aff_free(graph
->node
[i
].compress
);
1082 isl_multi_aff_free(graph
->node
[i
].decompress
);
1083 isl_mat_free(graph
->node
[i
].sched
);
1084 isl_map_free(graph
->node
[i
].sched_map
);
1085 isl_mat_free(graph
->node
[i
].cmap
);
1086 isl_mat_free(graph
->node
[i
].cinv
);
1087 isl_mat_free(graph
->node
[i
].ctrans
);
1089 free(graph
->node
[i
].coincident
);
1092 free(graph
->sorted
);
1094 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1095 isl_map_free(graph
->edge
[i
].map
);
1096 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
1097 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
1100 free(graph
->region
);
1101 for (i
= 0; i
<= isl_edge_last
; ++i
)
1102 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
1103 isl_hash_table_free(ctx
, graph
->node_table
);
1104 isl_basic_set_free(graph
->lp
);
1107 /* For each "set" on which this function is called, increment
1108 * graph->n by one and update graph->maxvar.
1110 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
1112 struct isl_sched_graph
*graph
= user
;
1113 int nvar
= isl_set_dim(set
, isl_dim_set
);
1116 if (nvar
> graph
->maxvar
)
1117 graph
->maxvar
= nvar
;
1124 /* Add the number of basic maps in "map" to *n.
1126 static isl_stat
add_n_basic_map(__isl_take isl_map
*map
, void *user
)
1130 *n
+= isl_map_n_basic_map(map
);
1136 /* Compute the number of rows that should be allocated for the schedule.
1137 * In particular, we need one row for each variable or one row
1138 * for each basic map in the dependences.
1139 * Note that it is practically impossible to exhaust both
1140 * the number of dependences and the number of variables.
1142 static int compute_max_row(struct isl_sched_graph
*graph
,
1143 __isl_keep isl_schedule_constraints
*sc
)
1145 enum isl_edge_type i
;
1150 if (isl_union_set_foreach_set(sc
->domain
, &init_n_maxvar
, graph
) < 0)
1153 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
1154 if (isl_union_map_foreach_map(sc
->constraint
[i
],
1155 &add_n_basic_map
, &n_edge
) < 0)
1157 graph
->max_row
= n_edge
+ graph
->maxvar
;
1162 /* Does "bset" have any defining equalities for its set variables?
1164 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
1171 n
= isl_basic_set_dim(bset
, isl_dim_set
);
1172 for (i
= 0; i
< n
; ++i
) {
1175 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
1184 /* Add a new node to the graph representing the given space.
1185 * "nvar" is the (possibly compressed) number of variables and
1186 * may be smaller than then number of set variables in "space"
1187 * if "compressed" is set.
1188 * If "compressed" is set, then "hull" represents the constraints
1189 * that were used to derive the compression, while "compress" and
1190 * "decompress" map the original space to the compressed space and
1192 * If "compressed" is not set, then "hull", "compress" and "decompress"
1195 static isl_stat
add_node(struct isl_sched_graph
*graph
,
1196 __isl_take isl_space
*space
, int nvar
, int compressed
,
1197 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
1198 __isl_take isl_multi_aff
*decompress
)
1206 return isl_stat_error
;
1208 ctx
= isl_space_get_ctx(space
);
1209 nparam
= isl_space_dim(space
, isl_dim_param
);
1210 if (!ctx
->opt
->schedule_parametric
)
1212 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
1213 graph
->node
[graph
->n
].space
= space
;
1214 graph
->node
[graph
->n
].nvar
= nvar
;
1215 graph
->node
[graph
->n
].nparam
= nparam
;
1216 graph
->node
[graph
->n
].sched
= sched
;
1217 graph
->node
[graph
->n
].sched_map
= NULL
;
1218 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
1219 graph
->node
[graph
->n
].coincident
= coincident
;
1220 graph
->node
[graph
->n
].compressed
= compressed
;
1221 graph
->node
[graph
->n
].hull
= hull
;
1222 graph
->node
[graph
->n
].compress
= compress
;
1223 graph
->node
[graph
->n
].decompress
= decompress
;
1226 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
1227 return isl_stat_error
;
1228 if (compressed
&& (!hull
|| !compress
|| !decompress
))
1229 return isl_stat_error
;
1234 /* Add a new node to the graph representing the given set.
1236 * If any of the set variables is defined by an equality, then
1237 * we perform variable compression such that we can perform
1238 * the scheduling on the compressed domain.
1240 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1245 isl_basic_set
*hull
;
1248 isl_multi_aff
*compress
, *decompress
;
1249 struct isl_sched_graph
*graph
= user
;
1251 space
= isl_set_get_space(set
);
1252 hull
= isl_set_affine_hull(set
);
1253 hull
= isl_basic_set_remove_divs(hull
);
1254 nvar
= isl_space_dim(space
, isl_dim_set
);
1255 has_equality
= has_any_defining_equality(hull
);
1257 if (has_equality
< 0)
1259 if (!has_equality
) {
1260 isl_basic_set_free(hull
);
1261 return add_node(graph
, space
, nvar
, 0, NULL
, NULL
, NULL
);
1264 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
1265 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1266 compress
= isl_morph_get_var_multi_aff(morph
);
1267 morph
= isl_morph_inverse(morph
);
1268 decompress
= isl_morph_get_var_multi_aff(morph
);
1269 isl_morph_free(morph
);
1271 hull_set
= isl_set_from_basic_set(hull
);
1272 return add_node(graph
, space
, nvar
, 1, hull_set
, compress
, decompress
);
1274 isl_basic_set_free(hull
);
1275 isl_space_free(space
);
1276 return isl_stat_error
;
1279 struct isl_extract_edge_data
{
1280 enum isl_edge_type type
;
1281 struct isl_sched_graph
*graph
;
1284 /* Merge edge2 into edge1, freeing the contents of edge2.
1285 * Return 0 on success and -1 on failure.
1287 * edge1 and edge2 are assumed to have the same value for the map field.
1289 static int merge_edge(struct isl_sched_edge
*edge1
,
1290 struct isl_sched_edge
*edge2
)
1292 edge1
->types
|= edge2
->types
;
1293 isl_map_free(edge2
->map
);
1295 if (is_condition(edge2
)) {
1296 if (!edge1
->tagged_condition
)
1297 edge1
->tagged_condition
= edge2
->tagged_condition
;
1299 edge1
->tagged_condition
=
1300 isl_union_map_union(edge1
->tagged_condition
,
1301 edge2
->tagged_condition
);
1304 if (is_conditional_validity(edge2
)) {
1305 if (!edge1
->tagged_validity
)
1306 edge1
->tagged_validity
= edge2
->tagged_validity
;
1308 edge1
->tagged_validity
=
1309 isl_union_map_union(edge1
->tagged_validity
,
1310 edge2
->tagged_validity
);
1313 if (is_condition(edge2
) && !edge1
->tagged_condition
)
1315 if (is_conditional_validity(edge2
) && !edge1
->tagged_validity
)
1321 /* Insert dummy tags in domain and range of "map".
1323 * In particular, if "map" is of the form
1329 * [A -> dummy_tag] -> [B -> dummy_tag]
1331 * where the dummy_tags are identical and equal to any dummy tags
1332 * introduced by any other call to this function.
1334 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1340 isl_set
*domain
, *range
;
1342 ctx
= isl_map_get_ctx(map
);
1344 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1345 space
= isl_space_params(isl_map_get_space(map
));
1346 space
= isl_space_set_from_params(space
);
1347 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1348 space
= isl_space_map_from_set(space
);
1350 domain
= isl_map_wrap(map
);
1351 range
= isl_map_wrap(isl_map_universe(space
));
1352 map
= isl_map_from_domain_and_range(domain
, range
);
1353 map
= isl_map_zip(map
);
1358 /* Given that at least one of "src" or "dst" is compressed, return
1359 * a map between the spaces of these nodes restricted to the affine
1360 * hull that was used in the compression.
1362 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1363 struct isl_sched_node
*dst
)
1367 if (src
->compressed
)
1368 dom
= isl_set_copy(src
->hull
);
1370 dom
= isl_set_universe(isl_space_copy(src
->space
));
1371 if (dst
->compressed
)
1372 ran
= isl_set_copy(dst
->hull
);
1374 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1376 return isl_map_from_domain_and_range(dom
, ran
);
1379 /* Intersect the domains of the nested relations in domain and range
1380 * of "tagged" with "map".
1382 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1383 __isl_keep isl_map
*map
)
1387 tagged
= isl_map_zip(tagged
);
1388 set
= isl_map_wrap(isl_map_copy(map
));
1389 tagged
= isl_map_intersect_domain(tagged
, set
);
1390 tagged
= isl_map_zip(tagged
);
1394 /* Return a pointer to the node that lives in the domain space of "map"
1395 * or NULL if there is no such node.
1397 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1398 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1400 struct isl_sched_node
*node
;
1403 space
= isl_space_domain(isl_map_get_space(map
));
1404 node
= graph_find_node(ctx
, graph
, space
);
1405 isl_space_free(space
);
1410 /* Return a pointer to the node that lives in the range space of "map"
1411 * or NULL if there is no such node.
1413 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1414 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1416 struct isl_sched_node
*node
;
1419 space
= isl_space_range(isl_map_get_space(map
));
1420 node
= graph_find_node(ctx
, graph
, space
);
1421 isl_space_free(space
);
1426 /* Add a new edge to the graph based on the given map
1427 * and add it to data->graph->edge_table[data->type].
1428 * If a dependence relation of a given type happens to be identical
1429 * to one of the dependence relations of a type that was added before,
1430 * then we don't create a new edge, but instead mark the original edge
1431 * as also representing a dependence of the current type.
1433 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1434 * may be specified as "tagged" dependence relations. That is, "map"
1435 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1436 * the dependence on iterations and a and b are tags.
1437 * edge->map is set to the relation containing the elements i -> j,
1438 * while edge->tagged_condition and edge->tagged_validity contain
1439 * the union of all the "map" relations
1440 * for which extract_edge is called that result in the same edge->map.
1442 * If the source or the destination node is compressed, then
1443 * intersect both "map" and "tagged" with the constraints that
1444 * were used to construct the compression.
1445 * This ensures that there are no schedule constraints defined
1446 * outside of these domains, while the scheduler no longer has
1447 * any control over those outside parts.
1449 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1451 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1452 struct isl_extract_edge_data
*data
= user
;
1453 struct isl_sched_graph
*graph
= data
->graph
;
1454 struct isl_sched_node
*src
, *dst
;
1455 struct isl_sched_edge
*edge
;
1456 isl_map
*tagged
= NULL
;
1458 if (data
->type
== isl_edge_condition
||
1459 data
->type
== isl_edge_conditional_validity
) {
1460 if (isl_map_can_zip(map
)) {
1461 tagged
= isl_map_copy(map
);
1462 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1464 tagged
= insert_dummy_tags(isl_map_copy(map
));
1468 src
= find_domain_node(ctx
, graph
, map
);
1469 dst
= find_range_node(ctx
, graph
, map
);
1473 isl_map_free(tagged
);
1477 if (src
->compressed
|| dst
->compressed
) {
1479 hull
= extract_hull(src
, dst
);
1481 tagged
= map_intersect_domains(tagged
, hull
);
1482 map
= isl_map_intersect(map
, hull
);
1485 graph
->edge
[graph
->n_edge
].src
= src
;
1486 graph
->edge
[graph
->n_edge
].dst
= dst
;
1487 graph
->edge
[graph
->n_edge
].map
= map
;
1488 graph
->edge
[graph
->n_edge
].types
= 0;
1489 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1490 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1491 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1492 if (data
->type
== isl_edge_condition
)
1493 graph
->edge
[graph
->n_edge
].tagged_condition
=
1494 isl_union_map_from_map(tagged
);
1495 if (data
->type
== isl_edge_conditional_validity
)
1496 graph
->edge
[graph
->n_edge
].tagged_validity
=
1497 isl_union_map_from_map(tagged
);
1499 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1502 return isl_stat_error
;
1504 if (edge
== &graph
->edge
[graph
->n_edge
])
1505 return graph_edge_table_add(ctx
, graph
, data
->type
,
1506 &graph
->edge
[graph
->n_edge
++]);
1508 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1511 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1514 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1516 * The context is included in the domain before the nodes of
1517 * the graphs are extracted in order to be able to exploit
1518 * any possible additional equalities.
1519 * Note that this intersection is only performed locally here.
1521 static isl_stat
graph_init(struct isl_sched_graph
*graph
,
1522 __isl_keep isl_schedule_constraints
*sc
)
1525 isl_union_set
*domain
;
1526 struct isl_extract_edge_data data
;
1527 enum isl_edge_type i
;
1531 return isl_stat_error
;
1533 ctx
= isl_schedule_constraints_get_ctx(sc
);
1535 domain
= isl_schedule_constraints_get_domain(sc
);
1536 graph
->n
= isl_union_set_n_set(domain
);
1537 isl_union_set_free(domain
);
1539 if (graph_alloc(ctx
, graph
, graph
->n
,
1540 isl_schedule_constraints_n_map(sc
)) < 0)
1541 return isl_stat_error
;
1543 if (compute_max_row(graph
, sc
) < 0)
1544 return isl_stat_error
;
1547 domain
= isl_schedule_constraints_get_domain(sc
);
1548 domain
= isl_union_set_intersect_params(domain
,
1549 isl_set_copy(sc
->context
));
1550 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1551 isl_union_set_free(domain
);
1553 return isl_stat_error
;
1554 if (graph_init_table(ctx
, graph
) < 0)
1555 return isl_stat_error
;
1556 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
1557 graph
->max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
1558 if (graph_init_edge_tables(ctx
, graph
) < 0)
1559 return isl_stat_error
;
1562 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1564 if (isl_union_map_foreach_map(sc
->constraint
[i
],
1565 &extract_edge
, &data
) < 0)
1566 return isl_stat_error
;
1572 /* Check whether there is any dependence from node[j] to node[i]
1573 * or from node[i] to node[j].
1575 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1578 struct isl_sched_graph
*graph
= user
;
1580 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1583 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1586 /* Check whether there is a (conditional) validity dependence from node[j]
1587 * to node[i], forcing node[i] to follow node[j].
1589 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1591 struct isl_sched_graph
*graph
= user
;
1593 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1596 /* Use Tarjan's algorithm for computing the strongly connected components
1597 * in the dependence graph only considering those edges defined by "follows".
1599 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1600 isl_bool (*follows
)(int i
, int j
, void *user
))
1603 struct isl_tarjan_graph
*g
= NULL
;
1605 g
= isl_tarjan_graph_init(ctx
, graph
->n
, follows
, graph
);
1613 while (g
->order
[i
] != -1) {
1614 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1622 isl_tarjan_graph_free(g
);
1627 /* Apply Tarjan's algorithm to detect the strongly connected components
1628 * in the dependence graph.
1629 * Only consider the (conditional) validity dependences and clear "weak".
1631 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1634 return detect_ccs(ctx
, graph
, &node_follows_strong
);
1637 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1638 * in the dependence graph.
1639 * Consider all dependences and set "weak".
1641 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1644 return detect_ccs(ctx
, graph
, &node_follows_weak
);
1647 static int cmp_scc(const void *a
, const void *b
, void *data
)
1649 struct isl_sched_graph
*graph
= data
;
1653 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1656 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1658 static int sort_sccs(struct isl_sched_graph
*graph
)
1660 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1663 /* Given a dependence relation R from "node" to itself,
1664 * construct the set of coefficients of valid constraints for elements
1665 * in that dependence relation.
1666 * In particular, the result contains tuples of coefficients
1667 * c_0, c_n, c_x such that
1669 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1673 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1675 * We choose here to compute the dual of delta R.
1676 * Alternatively, we could have computed the dual of R, resulting
1677 * in a set of tuples c_0, c_n, c_x, c_y, and then
1678 * plugged in (c_0, c_n, c_x, -c_x).
1680 * If "node" has been compressed, then the dependence relation
1681 * is also compressed before the set of coefficients is computed.
1683 static __isl_give isl_basic_set
*intra_coefficients(
1684 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1685 __isl_take isl_map
*map
)
1689 isl_basic_set
*coef
;
1690 isl_maybe_isl_basic_set m
;
1692 m
= isl_map_to_basic_set_try_get(graph
->intra_hmap
, map
);
1693 if (m
.valid
< 0 || m
.valid
) {
1698 key
= isl_map_copy(map
);
1699 if (node
->compressed
) {
1700 map
= isl_map_preimage_domain_multi_aff(map
,
1701 isl_multi_aff_copy(node
->decompress
));
1702 map
= isl_map_preimage_range_multi_aff(map
,
1703 isl_multi_aff_copy(node
->decompress
));
1705 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1706 coef
= isl_set_coefficients(delta
);
1707 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1708 isl_basic_set_copy(coef
));
1713 /* Given a dependence relation R, construct the set of coefficients
1714 * of valid constraints for elements in that dependence relation.
1715 * In particular, the result contains tuples of coefficients
1716 * c_0, c_n, c_x, c_y such that
1718 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1720 * If the source or destination nodes of "edge" have been compressed,
1721 * then the dependence relation is also compressed before
1722 * the set of coefficients is computed.
1724 static __isl_give isl_basic_set
*inter_coefficients(
1725 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1726 __isl_take isl_map
*map
)
1730 isl_basic_set
*coef
;
1731 isl_maybe_isl_basic_set m
;
1733 m
= isl_map_to_basic_set_try_get(graph
->inter_hmap
, map
);
1734 if (m
.valid
< 0 || m
.valid
) {
1739 key
= isl_map_copy(map
);
1740 if (edge
->src
->compressed
)
1741 map
= isl_map_preimage_domain_multi_aff(map
,
1742 isl_multi_aff_copy(edge
->src
->decompress
));
1743 if (edge
->dst
->compressed
)
1744 map
= isl_map_preimage_range_multi_aff(map
,
1745 isl_multi_aff_copy(edge
->dst
->decompress
));
1746 set
= isl_map_wrap(isl_map_remove_divs(map
));
1747 coef
= isl_set_coefficients(set
);
1748 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1749 isl_basic_set_copy(coef
));
1754 /* Add constraints to graph->lp that force validity for the given
1755 * dependence from a node i to itself.
1756 * That is, add constraints that enforce
1758 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1759 * = c_i_x (y - x) >= 0
1761 * for each (x,y) in R.
1762 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1763 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1764 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1765 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1767 * Actually, we do not construct constraints for the c_i_x themselves,
1768 * but for the coefficients of c_i_x written as a linear combination
1769 * of the columns in node->cmap.
1771 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1772 struct isl_sched_edge
*edge
)
1775 isl_map
*map
= isl_map_copy(edge
->map
);
1776 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1778 isl_dim_map
*dim_map
;
1779 isl_basic_set
*coef
;
1780 struct isl_sched_node
*node
= edge
->src
;
1782 coef
= intra_coefficients(graph
, node
, map
);
1784 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1786 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1787 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1791 total
= isl_basic_set_total_dim(graph
->lp
);
1792 dim_map
= isl_dim_map_alloc(ctx
, total
);
1793 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1794 isl_space_dim(dim
, isl_dim_set
), 1,
1796 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1797 isl_space_dim(dim
, isl_dim_set
), 1,
1799 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1800 coef
->n_eq
, coef
->n_ineq
);
1801 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1803 isl_space_free(dim
);
1807 isl_space_free(dim
);
1811 /* Add constraints to graph->lp that force validity for the given
1812 * dependence from node i to node j.
1813 * That is, add constraints that enforce
1815 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1817 * for each (x,y) in R.
1818 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1819 * of valid constraints for R and then plug in
1820 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1821 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1822 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1823 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1825 * Actually, we do not construct constraints for the c_*_x themselves,
1826 * but for the coefficients of c_*_x written as a linear combination
1827 * of the columns in node->cmap.
1829 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1830 struct isl_sched_edge
*edge
)
1833 isl_map
*map
= isl_map_copy(edge
->map
);
1834 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1836 isl_dim_map
*dim_map
;
1837 isl_basic_set
*coef
;
1838 struct isl_sched_node
*src
= edge
->src
;
1839 struct isl_sched_node
*dst
= edge
->dst
;
1841 coef
= inter_coefficients(graph
, edge
, map
);
1843 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1845 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1846 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1847 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1848 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1849 isl_mat_copy(dst
->cmap
));
1853 total
= isl_basic_set_total_dim(graph
->lp
);
1854 dim_map
= isl_dim_map_alloc(ctx
, total
);
1856 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1857 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1858 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1859 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1860 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1862 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1863 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1866 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1867 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1868 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1869 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1870 isl_space_dim(dim
, isl_dim_set
), 1,
1872 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1873 isl_space_dim(dim
, isl_dim_set
), 1,
1876 edge
->start
= graph
->lp
->n_ineq
;
1877 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1878 coef
->n_eq
, coef
->n_ineq
);
1879 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1883 isl_space_free(dim
);
1884 edge
->end
= graph
->lp
->n_ineq
;
1888 isl_space_free(dim
);
1892 /* Add constraints to graph->lp that bound the dependence distance for the given
1893 * dependence from a node i to itself.
1894 * If s = 1, we add the constraint
1896 * c_i_x (y - x) <= m_0 + m_n n
1900 * -c_i_x (y - x) + m_0 + m_n n >= 0
1902 * for each (x,y) in R.
1903 * If s = -1, we add the constraint
1905 * -c_i_x (y - x) <= m_0 + m_n n
1909 * c_i_x (y - x) + m_0 + m_n n >= 0
1911 * for each (x,y) in R.
1912 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1913 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1914 * with each coefficient (except m_0) represented as a pair of non-negative
1917 * Actually, we do not construct constraints for the c_i_x themselves,
1918 * but for the coefficients of c_i_x written as a linear combination
1919 * of the columns in node->cmap.
1922 * If "local" is set, then we add constraints
1924 * c_i_x (y - x) <= 0
1928 * -c_i_x (y - x) <= 0
1930 * instead, forcing the dependence distance to be (less than or) equal to 0.
1931 * That is, we plug in (0, 0, -s * c_i_x),
1932 * Note that dependences marked local are treated as validity constraints
1933 * by add_all_validity_constraints and therefore also have
1934 * their distances bounded by 0 from below.
1936 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1937 struct isl_sched_edge
*edge
, int s
, int local
)
1941 isl_map
*map
= isl_map_copy(edge
->map
);
1942 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1944 isl_dim_map
*dim_map
;
1945 isl_basic_set
*coef
;
1946 struct isl_sched_node
*node
= edge
->src
;
1948 coef
= intra_coefficients(graph
, node
, map
);
1950 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1952 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1953 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1957 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1958 total
= isl_basic_set_total_dim(graph
->lp
);
1959 dim_map
= isl_dim_map_alloc(ctx
, total
);
1962 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1963 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1964 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1966 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1967 isl_space_dim(dim
, isl_dim_set
), 1,
1969 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1970 isl_space_dim(dim
, isl_dim_set
), 1,
1972 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1973 coef
->n_eq
, coef
->n_ineq
);
1974 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1976 isl_space_free(dim
);
1980 isl_space_free(dim
);
1984 /* Add constraints to graph->lp that bound the dependence distance for the given
1985 * dependence from node i to node j.
1986 * If s = 1, we add the constraint
1988 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1993 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1996 * for each (x,y) in R.
1997 * If s = -1, we add the constraint
1999 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
2004 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
2007 * for each (x,y) in R.
2008 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
2009 * of valid constraints for R and then plug in
2010 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
2012 * with each coefficient (except m_0, c_j_0 and c_i_0)
2013 * represented as a pair of non-negative coefficients.
2015 * Actually, we do not construct constraints for the c_*_x themselves,
2016 * but for the coefficients of c_*_x written as a linear combination
2017 * of the columns in node->cmap.
2020 * If "local" is set, then we add constraints
2022 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
2026 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
2028 * instead, forcing the dependence distance to be (less than or) equal to 0.
2029 * That is, we plug in
2030 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
2031 * Note that dependences marked local are treated as validity constraints
2032 * by add_all_validity_constraints and therefore also have
2033 * their distances bounded by 0 from below.
2035 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
2036 struct isl_sched_edge
*edge
, int s
, int local
)
2040 isl_map
*map
= isl_map_copy(edge
->map
);
2041 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2043 isl_dim_map
*dim_map
;
2044 isl_basic_set
*coef
;
2045 struct isl_sched_node
*src
= edge
->src
;
2046 struct isl_sched_node
*dst
= edge
->dst
;
2048 coef
= inter_coefficients(graph
, edge
, map
);
2050 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2052 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2053 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
2054 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2055 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
2056 isl_mat_copy(dst
->cmap
));
2060 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
2061 total
= isl_basic_set_total_dim(graph
->lp
);
2062 dim_map
= isl_dim_map_alloc(ctx
, total
);
2065 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
2066 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
2067 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
2070 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
2071 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
2072 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
2073 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2074 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2076 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2077 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2080 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
2081 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
2082 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
2083 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2084 isl_space_dim(dim
, isl_dim_set
), 1,
2086 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2087 isl_space_dim(dim
, isl_dim_set
), 1,
2090 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2091 coef
->n_eq
, coef
->n_ineq
);
2092 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2094 isl_space_free(dim
);
2098 isl_space_free(dim
);
2102 /* Add all validity constraints to graph->lp.
2104 * An edge that is forced to be local needs to have its dependence
2105 * distances equal to zero. We take care of bounding them by 0 from below
2106 * here. add_all_proximity_constraints takes care of bounding them by 0
2109 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2110 * Otherwise, we ignore them.
2112 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
2113 int use_coincidence
)
2117 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2118 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2121 local
= is_local(edge
) ||
2122 (is_coincidence(edge
) && use_coincidence
);
2123 if (!is_validity(edge
) && !local
)
2125 if (edge
->src
!= edge
->dst
)
2127 if (add_intra_validity_constraints(graph
, edge
) < 0)
2131 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2132 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2135 local
= is_local(edge
) ||
2136 (is_coincidence(edge
) && use_coincidence
);
2137 if (!is_validity(edge
) && !local
)
2139 if (edge
->src
== edge
->dst
)
2141 if (add_inter_validity_constraints(graph
, edge
) < 0)
2148 /* Add constraints to graph->lp that bound the dependence distance
2149 * for all dependence relations.
2150 * If a given proximity dependence is identical to a validity
2151 * dependence, then the dependence distance is already bounded
2152 * from below (by zero), so we only need to bound the distance
2153 * from above. (This includes the case of "local" dependences
2154 * which are treated as validity dependence by add_all_validity_constraints.)
2155 * Otherwise, we need to bound the distance both from above and from below.
2157 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2158 * Otherwise, we ignore them.
2160 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
2161 int use_coincidence
)
2165 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2166 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2169 local
= is_local(edge
) ||
2170 (is_coincidence(edge
) && use_coincidence
);
2171 if (!is_proximity(edge
) && !local
)
2173 if (edge
->src
== edge
->dst
&&
2174 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
2176 if (edge
->src
!= edge
->dst
&&
2177 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
2179 if (is_validity(edge
) || local
)
2181 if (edge
->src
== edge
->dst
&&
2182 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2184 if (edge
->src
!= edge
->dst
&&
2185 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2192 /* Compute a basis for the rows in the linear part of the schedule
2193 * and extend this basis to a full basis. The remaining rows
2194 * can then be used to force linear independence from the rows
2197 * In particular, given the schedule rows S, we compute
2202 * with H the Hermite normal form of S. That is, all but the
2203 * first rank columns of H are zero and so each row in S is
2204 * a linear combination of the first rank rows of Q.
2205 * The matrix Q is then transposed because we will write the
2206 * coefficients of the next schedule row as a column vector s
2207 * and express this s as a linear combination s = Q c of the
2209 * Similarly, the matrix U is transposed such that we can
2210 * compute the coefficients c = U s from a schedule row s.
2212 static int node_update_cmap(struct isl_sched_node
*node
)
2215 int n_row
= isl_mat_rows(node
->sched
);
2217 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2218 1 + node
->nparam
, node
->nvar
);
2220 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2221 isl_mat_free(node
->cmap
);
2222 isl_mat_free(node
->cinv
);
2223 isl_mat_free(node
->ctrans
);
2224 node
->ctrans
= isl_mat_copy(Q
);
2225 node
->cmap
= isl_mat_transpose(Q
);
2226 node
->cinv
= isl_mat_transpose(U
);
2227 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2230 if (!node
->cmap
|| !node
->cinv
|| !node
->ctrans
|| node
->rank
< 0)
2235 /* How many times should we count the constraints in "edge"?
2237 * If carry is set, then we are counting the number of
2238 * (validity or conditional validity) constraints that will be added
2239 * in setup_carry_lp and we count each edge exactly once.
2241 * Otherwise, we count as follows
2242 * validity -> 1 (>= 0)
2243 * validity+proximity -> 2 (>= 0 and upper bound)
2244 * proximity -> 2 (lower and upper bound)
2245 * local(+any) -> 2 (>= 0 and <= 0)
2247 * If an edge is only marked conditional_validity then it counts
2248 * as zero since it is only checked afterwards.
2250 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2251 * Otherwise, we ignore them.
2253 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
2254 int use_coincidence
)
2256 if (carry
&& !is_validity(edge
) && !is_conditional_validity(edge
))
2260 if (is_proximity(edge
) || is_local(edge
))
2262 if (use_coincidence
&& is_coincidence(edge
))
2264 if (is_validity(edge
))
2269 /* Count the number of equality and inequality constraints
2270 * that will be added for the given map.
2272 * "use_coincidence" is set if we should take into account coincidence edges.
2274 static int count_map_constraints(struct isl_sched_graph
*graph
,
2275 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2276 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
2278 isl_basic_set
*coef
;
2279 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
2286 if (edge
->src
== edge
->dst
)
2287 coef
= intra_coefficients(graph
, edge
->src
, map
);
2289 coef
= inter_coefficients(graph
, edge
, map
);
2292 *n_eq
+= f
* coef
->n_eq
;
2293 *n_ineq
+= f
* coef
->n_ineq
;
2294 isl_basic_set_free(coef
);
2299 /* Count the number of equality and inequality constraints
2300 * that will be added to the main lp problem.
2301 * We count as follows
2302 * validity -> 1 (>= 0)
2303 * validity+proximity -> 2 (>= 0 and upper bound)
2304 * proximity -> 2 (lower and upper bound)
2305 * local(+any) -> 2 (>= 0 and <= 0)
2307 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2308 * Otherwise, we ignore them.
2310 static int count_constraints(struct isl_sched_graph
*graph
,
2311 int *n_eq
, int *n_ineq
, int use_coincidence
)
2315 *n_eq
= *n_ineq
= 0;
2316 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2317 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2318 isl_map
*map
= isl_map_copy(edge
->map
);
2320 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2321 0, use_coincidence
) < 0)
2328 /* Count the number of constraints that will be added by
2329 * add_bound_constant_constraints to bound the values of the constant terms
2330 * and increment *n_eq and *n_ineq accordingly.
2332 * In practice, add_bound_constant_constraints only adds inequalities.
2334 static isl_stat
count_bound_constant_constraints(isl_ctx
*ctx
,
2335 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2337 if (isl_options_get_schedule_max_constant_term(ctx
) == -1)
2340 *n_ineq
+= graph
->n
;
2345 /* Add constraints to bound the values of the constant terms in the schedule,
2346 * if requested by the user.
2348 * The maximal value of the constant terms is defined by the option
2349 * "schedule_max_constant_term".
2351 * Within each node, the coefficients have the following order:
2353 * - positive and negative parts of c_i_n (if parametric)
2354 * - positive and negative parts of c_i_x
2356 static isl_stat
add_bound_constant_constraints(isl_ctx
*ctx
,
2357 struct isl_sched_graph
*graph
)
2363 max
= isl_options_get_schedule_max_constant_term(ctx
);
2367 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2369 for (i
= 0; i
< graph
->n
; ++i
) {
2370 struct isl_sched_node
*node
= &graph
->node
[i
];
2371 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2373 return isl_stat_error
;
2374 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2375 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2376 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2382 /* Count the number of constraints that will be added by
2383 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2386 * In practice, add_bound_coefficient_constraints only adds inequalities.
2388 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2389 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2393 if (ctx
->opt
->schedule_max_coefficient
== -1)
2396 for (i
= 0; i
< graph
->n
; ++i
)
2397 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2402 /* Add constraints that bound the values of the variable and parameter
2403 * coefficients of the schedule.
2405 * The maximal value of the coefficients is defined by the option
2406 * 'schedule_max_coefficient'.
2408 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
2409 struct isl_sched_graph
*graph
)
2412 int max_coefficient
;
2415 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
2417 if (max_coefficient
== -1)
2420 total
= isl_basic_set_total_dim(graph
->lp
);
2422 for (i
= 0; i
< graph
->n
; ++i
) {
2423 struct isl_sched_node
*node
= &graph
->node
[i
];
2424 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
2426 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2429 dim
= 1 + node
->start
+ 1 + j
;
2430 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2431 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2432 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
2439 /* Add a constraint to graph->lp that equates the value at position
2440 * "sum_pos" to the sum of the "n" values starting at "first".
2442 static isl_stat
add_sum_constraint(struct isl_sched_graph
*graph
,
2443 int sum_pos
, int first
, int n
)
2448 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2450 k
= isl_basic_set_alloc_equality(graph
->lp
);
2452 return isl_stat_error
;
2453 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2454 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2455 for (i
= 0; i
< n
; ++i
)
2456 isl_int_set_si(graph
->lp
->eq
[k
][1 + first
+ i
], 1);
2461 /* Add a constraint to graph->lp that equates the value at position
2462 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2464 * Within each node, the coefficients have the following order:
2466 * - positive and negative parts of c_i_n (if parametric)
2467 * - positive and negative parts of c_i_x
2469 static isl_stat
add_param_sum_constraint(struct isl_sched_graph
*graph
,
2475 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2477 k
= isl_basic_set_alloc_equality(graph
->lp
);
2479 return isl_stat_error
;
2480 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2481 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2482 for (i
= 0; i
< graph
->n
; ++i
) {
2483 int pos
= 1 + graph
->node
[i
].start
+ 1;
2485 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2486 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2492 /* Add a constraint to graph->lp that equates the value at position
2493 * "sum_pos" to the sum of the variable coefficients of all nodes.
2495 * Within each node, the coefficients have the following order:
2497 * - positive and negative parts of c_i_n (if parametric)
2498 * - positive and negative parts of c_i_x
2500 static isl_stat
add_var_sum_constraint(struct isl_sched_graph
*graph
,
2506 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2508 k
= isl_basic_set_alloc_equality(graph
->lp
);
2510 return isl_stat_error
;
2511 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2512 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2513 for (i
= 0; i
< graph
->n
; ++i
) {
2514 struct isl_sched_node
*node
= &graph
->node
[i
];
2515 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2517 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2518 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2524 /* Construct an ILP problem for finding schedule coefficients
2525 * that result in non-negative, but small dependence distances
2526 * over all dependences.
2527 * In particular, the dependence distances over proximity edges
2528 * are bounded by m_0 + m_n n and we compute schedule coefficients
2529 * with small values (preferably zero) of m_n and m_0.
2531 * All variables of the ILP are non-negative. The actual coefficients
2532 * may be negative, so each coefficient is represented as the difference
2533 * of two non-negative variables. The negative part always appears
2534 * immediately before the positive part.
2535 * Other than that, the variables have the following order
2537 * - sum of positive and negative parts of m_n coefficients
2539 * - sum of positive and negative parts of all c_n coefficients
2540 * (unconstrained when computing non-parametric schedules)
2541 * - sum of positive and negative parts of all c_x coefficients
2542 * - positive and negative parts of m_n coefficients
2545 * - positive and negative parts of c_i_n (if parametric)
2546 * - positive and negative parts of c_i_x
2548 * The c_i_x are not represented directly, but through the columns of
2549 * node->cmap. That is, the computed values are for variable t_i_x
2550 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2552 * The constraints are those from the edges plus two or three equalities
2553 * to express the sums.
2555 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2556 * Otherwise, we ignore them.
2558 static isl_stat
setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2559 int use_coincidence
)
2569 parametric
= ctx
->opt
->schedule_parametric
;
2570 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2572 total
= param_pos
+ 2 * nparam
;
2573 for (i
= 0; i
< graph
->n
; ++i
) {
2574 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2575 if (node_update_cmap(node
) < 0)
2576 return isl_stat_error
;
2577 node
->start
= total
;
2578 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2581 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2582 return isl_stat_error
;
2583 if (count_bound_constant_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2584 return isl_stat_error
;
2585 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2586 return isl_stat_error
;
2588 space
= isl_space_set_alloc(ctx
, 0, total
);
2589 isl_basic_set_free(graph
->lp
);
2590 n_eq
+= 2 + parametric
;
2592 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
2594 if (add_sum_constraint(graph
, 0, param_pos
, 2 * nparam
) < 0)
2595 return isl_stat_error
;
2596 if (parametric
&& add_param_sum_constraint(graph
, 2) < 0)
2597 return isl_stat_error
;
2598 if (add_var_sum_constraint(graph
, 3) < 0)
2599 return isl_stat_error
;
2600 if (add_bound_constant_constraints(ctx
, graph
) < 0)
2601 return isl_stat_error
;
2602 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2603 return isl_stat_error
;
2604 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2605 return isl_stat_error
;
2606 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2607 return isl_stat_error
;
2612 /* Analyze the conflicting constraint found by
2613 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2614 * constraint of one of the edges between distinct nodes, living, moreover
2615 * in distinct SCCs, then record the source and sink SCC as this may
2616 * be a good place to cut between SCCs.
2618 static int check_conflict(int con
, void *user
)
2621 struct isl_sched_graph
*graph
= user
;
2623 if (graph
->src_scc
>= 0)
2626 con
-= graph
->lp
->n_eq
;
2628 if (con
>= graph
->lp
->n_ineq
)
2631 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2632 if (!is_validity(&graph
->edge
[i
]))
2634 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2636 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2638 if (graph
->edge
[i
].start
> con
)
2640 if (graph
->edge
[i
].end
<= con
)
2642 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2643 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2649 /* Check whether the next schedule row of the given node needs to be
2650 * non-trivial. Lower-dimensional domains may have some trivial rows,
2651 * but as soon as the number of remaining required non-trivial rows
2652 * is as large as the number or remaining rows to be computed,
2653 * all remaining rows need to be non-trivial.
2655 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2657 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2660 /* Solve the ILP problem constructed in setup_lp.
2661 * For each node such that all the remaining rows of its schedule
2662 * need to be non-trivial, we construct a non-triviality region.
2663 * This region imposes that the next row is independent of previous rows.
2664 * In particular the coefficients c_i_x are represented by t_i_x
2665 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2666 * its first columns span the rows of the previously computed part
2667 * of the schedule. The non-triviality region enforces that at least
2668 * one of the remaining components of t_i_x is non-zero, i.e.,
2669 * that the new schedule row depends on at least one of the remaining
2672 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2678 for (i
= 0; i
< graph
->n
; ++i
) {
2679 struct isl_sched_node
*node
= &graph
->node
[i
];
2680 int skip
= node
->rank
;
2681 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
2682 if (needs_row(graph
, node
))
2683 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2685 graph
->region
[i
].len
= 0;
2687 lp
= isl_basic_set_copy(graph
->lp
);
2688 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2689 graph
->region
, &check_conflict
, graph
);
2693 /* Update the schedules of all nodes based on the given solution
2694 * of the LP problem.
2695 * The new row is added to the current band.
2696 * All possibly negative coefficients are encoded as a difference
2697 * of two non-negative variables, so we need to perform the subtraction
2698 * here. Moreover, if use_cmap is set, then the solution does
2699 * not refer to the actual coefficients c_i_x, but instead to variables
2700 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2701 * In this case, we then also need to perform this multiplication
2702 * to obtain the values of c_i_x.
2704 * If coincident is set, then the caller guarantees that the new
2705 * row satisfies the coincidence constraints.
2707 static int update_schedule(struct isl_sched_graph
*graph
,
2708 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2711 isl_vec
*csol
= NULL
;
2716 isl_die(sol
->ctx
, isl_error_internal
,
2717 "no solution found", goto error
);
2718 if (graph
->n_total_row
>= graph
->max_row
)
2719 isl_die(sol
->ctx
, isl_error_internal
,
2720 "too many schedule rows", goto error
);
2722 for (i
= 0; i
< graph
->n
; ++i
) {
2723 struct isl_sched_node
*node
= &graph
->node
[i
];
2724 int pos
= node
->start
;
2725 int row
= isl_mat_rows(node
->sched
);
2728 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2732 isl_map_free(node
->sched_map
);
2733 node
->sched_map
= NULL
;
2734 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2737 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2739 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2740 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2741 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2742 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2743 for (j
= 0; j
< node
->nparam
; ++j
)
2744 node
->sched
= isl_mat_set_element(node
->sched
,
2745 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2746 for (j
= 0; j
< node
->nvar
; ++j
)
2747 isl_int_set(csol
->el
[j
],
2748 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2750 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2754 for (j
= 0; j
< node
->nvar
; ++j
)
2755 node
->sched
= isl_mat_set_element(node
->sched
,
2756 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2757 node
->coincident
[graph
->n_total_row
] = coincident
;
2763 graph
->n_total_row
++;
2772 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2773 * and return this isl_aff.
2775 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2776 struct isl_sched_node
*node
, int row
)
2784 aff
= isl_aff_zero_on_domain(ls
);
2785 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2786 aff
= isl_aff_set_constant(aff
, v
);
2787 for (j
= 0; j
< node
->nparam
; ++j
) {
2788 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2789 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2791 for (j
= 0; j
< node
->nvar
; ++j
) {
2792 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2793 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2801 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2802 * and return this multi_aff.
2804 * The result is defined over the uncompressed node domain.
2806 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2807 struct isl_sched_node
*node
, int first
, int n
)
2811 isl_local_space
*ls
;
2818 nrow
= isl_mat_rows(node
->sched
);
2819 if (node
->compressed
)
2820 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2822 space
= isl_space_copy(node
->space
);
2823 ls
= isl_local_space_from_space(isl_space_copy(space
));
2824 space
= isl_space_from_domain(space
);
2825 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2826 ma
= isl_multi_aff_zero(space
);
2828 for (i
= first
; i
< first
+ n
; ++i
) {
2829 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2830 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2833 isl_local_space_free(ls
);
2835 if (node
->compressed
)
2836 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2837 isl_multi_aff_copy(node
->compress
));
2842 /* Convert node->sched into a multi_aff and return this multi_aff.
2844 * The result is defined over the uncompressed node domain.
2846 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2847 struct isl_sched_node
*node
)
2851 nrow
= isl_mat_rows(node
->sched
);
2852 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
2855 /* Convert node->sched into a map and return this map.
2857 * The result is cached in node->sched_map, which needs to be released
2858 * whenever node->sched is updated.
2859 * It is defined over the uncompressed node domain.
2861 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2863 if (!node
->sched_map
) {
2866 ma
= node_extract_schedule_multi_aff(node
);
2867 node
->sched_map
= isl_map_from_multi_aff(ma
);
2870 return isl_map_copy(node
->sched_map
);
2873 /* Construct a map that can be used to update a dependence relation
2874 * based on the current schedule.
2875 * That is, construct a map expressing that source and sink
2876 * are executed within the same iteration of the current schedule.
2877 * This map can then be intersected with the dependence relation.
2878 * This is not the most efficient way, but this shouldn't be a critical
2881 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2882 struct isl_sched_node
*dst
)
2884 isl_map
*src_sched
, *dst_sched
;
2886 src_sched
= node_extract_schedule(src
);
2887 dst_sched
= node_extract_schedule(dst
);
2888 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2891 /* Intersect the domains of the nested relations in domain and range
2892 * of "umap" with "map".
2894 static __isl_give isl_union_map
*intersect_domains(
2895 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2897 isl_union_set
*uset
;
2899 umap
= isl_union_map_zip(umap
);
2900 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2901 umap
= isl_union_map_intersect_domain(umap
, uset
);
2902 umap
= isl_union_map_zip(umap
);
2906 /* Update the dependence relation of the given edge based
2907 * on the current schedule.
2908 * If the dependence is carried completely by the current schedule, then
2909 * it is removed from the edge_tables. It is kept in the list of edges
2910 * as otherwise all edge_tables would have to be recomputed.
2912 static int update_edge(struct isl_sched_graph
*graph
,
2913 struct isl_sched_edge
*edge
)
2918 id
= specializer(edge
->src
, edge
->dst
);
2919 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2923 if (edge
->tagged_condition
) {
2924 edge
->tagged_condition
=
2925 intersect_domains(edge
->tagged_condition
, id
);
2926 if (!edge
->tagged_condition
)
2929 if (edge
->tagged_validity
) {
2930 edge
->tagged_validity
=
2931 intersect_domains(edge
->tagged_validity
, id
);
2932 if (!edge
->tagged_validity
)
2936 empty
= isl_map_plain_is_empty(edge
->map
);
2940 graph_remove_edge(graph
, edge
);
2949 /* Does the domain of "umap" intersect "uset"?
2951 static int domain_intersects(__isl_keep isl_union_map
*umap
,
2952 __isl_keep isl_union_set
*uset
)
2956 umap
= isl_union_map_copy(umap
);
2957 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
2958 empty
= isl_union_map_is_empty(umap
);
2959 isl_union_map_free(umap
);
2961 return empty
< 0 ? -1 : !empty
;
2964 /* Does the range of "umap" intersect "uset"?
2966 static int range_intersects(__isl_keep isl_union_map
*umap
,
2967 __isl_keep isl_union_set
*uset
)
2971 umap
= isl_union_map_copy(umap
);
2972 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
2973 empty
= isl_union_map_is_empty(umap
);
2974 isl_union_map_free(umap
);
2976 return empty
< 0 ? -1 : !empty
;
2979 /* Are the condition dependences of "edge" local with respect to
2980 * the current schedule?
2982 * That is, are domain and range of the condition dependences mapped
2983 * to the same point?
2985 * In other words, is the condition false?
2987 static int is_condition_false(struct isl_sched_edge
*edge
)
2989 isl_union_map
*umap
;
2990 isl_map
*map
, *sched
, *test
;
2993 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
2994 if (empty
< 0 || empty
)
2997 umap
= isl_union_map_copy(edge
->tagged_condition
);
2998 umap
= isl_union_map_zip(umap
);
2999 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3000 map
= isl_map_from_union_map(umap
);
3002 sched
= node_extract_schedule(edge
->src
);
3003 map
= isl_map_apply_domain(map
, sched
);
3004 sched
= node_extract_schedule(edge
->dst
);
3005 map
= isl_map_apply_range(map
, sched
);
3007 test
= isl_map_identity(isl_map_get_space(map
));
3008 local
= isl_map_is_subset(map
, test
);
3015 /* For each conditional validity constraint that is adjacent
3016 * to a condition with domain in condition_source or range in condition_sink,
3017 * turn it into an unconditional validity constraint.
3019 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
3020 __isl_take isl_union_set
*condition_source
,
3021 __isl_take isl_union_set
*condition_sink
)
3025 condition_source
= isl_union_set_coalesce(condition_source
);
3026 condition_sink
= isl_union_set_coalesce(condition_sink
);
3028 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3030 isl_union_map
*validity
;
3032 if (!is_conditional_validity(&graph
->edge
[i
]))
3034 if (is_validity(&graph
->edge
[i
]))
3037 validity
= graph
->edge
[i
].tagged_validity
;
3038 adjacent
= domain_intersects(validity
, condition_sink
);
3039 if (adjacent
>= 0 && !adjacent
)
3040 adjacent
= range_intersects(validity
, condition_source
);
3046 set_validity(&graph
->edge
[i
]);
3049 isl_union_set_free(condition_source
);
3050 isl_union_set_free(condition_sink
);
3053 isl_union_set_free(condition_source
);
3054 isl_union_set_free(condition_sink
);
3058 /* Update the dependence relations of all edges based on the current schedule
3059 * and enforce conditional validity constraints that are adjacent
3060 * to satisfied condition constraints.
3062 * First check if any of the condition constraints are satisfied
3063 * (i.e., not local to the outer schedule) and keep track of
3064 * their domain and range.
3065 * Then update all dependence relations (which removes the non-local
3067 * Finally, if any condition constraints turned out to be satisfied,
3068 * then turn all adjacent conditional validity constraints into
3069 * unconditional validity constraints.
3071 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3075 isl_union_set
*source
, *sink
;
3077 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3078 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3079 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3081 isl_union_set
*uset
;
3082 isl_union_map
*umap
;
3084 if (!is_condition(&graph
->edge
[i
]))
3086 if (is_local(&graph
->edge
[i
]))
3088 local
= is_condition_false(&graph
->edge
[i
]);
3096 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3097 uset
= isl_union_map_domain(umap
);
3098 source
= isl_union_set_union(source
, uset
);
3100 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3101 uset
= isl_union_map_range(umap
);
3102 sink
= isl_union_set_union(sink
, uset
);
3105 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
3106 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
3111 return unconditionalize_adjacent_validity(graph
, source
, sink
);
3113 isl_union_set_free(source
);
3114 isl_union_set_free(sink
);
3117 isl_union_set_free(source
);
3118 isl_union_set_free(sink
);
3122 static void next_band(struct isl_sched_graph
*graph
)
3124 graph
->band_start
= graph
->n_total_row
;
3127 /* Return the union of the universe domains of the nodes in "graph"
3128 * that satisfy "pred".
3130 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
3131 struct isl_sched_graph
*graph
,
3132 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
3138 for (i
= 0; i
< graph
->n
; ++i
)
3139 if (pred(&graph
->node
[i
], data
))
3143 isl_die(ctx
, isl_error_internal
,
3144 "empty component", return NULL
);
3146 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3147 dom
= isl_union_set_from_set(set
);
3149 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
3150 if (!pred(&graph
->node
[i
], data
))
3152 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3153 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
3159 /* Return a list of unions of universe domains, where each element
3160 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3162 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
3163 struct isl_sched_graph
*graph
)
3166 isl_union_set_list
*filters
;
3168 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
3169 for (i
= 0; i
< graph
->scc
; ++i
) {
3172 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
3173 filters
= isl_union_set_list_add(filters
, dom
);
3179 /* Return a list of two unions of universe domains, one for the SCCs up
3180 * to and including graph->src_scc and another for the other SCCs.
3182 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
3183 struct isl_sched_graph
*graph
)
3186 isl_union_set_list
*filters
;
3188 filters
= isl_union_set_list_alloc(ctx
, 2);
3189 dom
= isl_sched_graph_domain(ctx
, graph
,
3190 &node_scc_at_most
, graph
->src_scc
);
3191 filters
= isl_union_set_list_add(filters
, dom
);
3192 dom
= isl_sched_graph_domain(ctx
, graph
,
3193 &node_scc_at_least
, graph
->src_scc
+ 1);
3194 filters
= isl_union_set_list_add(filters
, dom
);
3199 /* Copy nodes that satisfy node_pred from the src dependence graph
3200 * to the dst dependence graph.
3202 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
3203 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
3208 for (i
= 0; i
< src
->n
; ++i
) {
3211 if (!node_pred(&src
->node
[i
], data
))
3215 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
3216 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
3217 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
3218 dst
->node
[j
].compress
=
3219 isl_multi_aff_copy(src
->node
[i
].compress
);
3220 dst
->node
[j
].decompress
=
3221 isl_multi_aff_copy(src
->node
[i
].decompress
);
3222 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
3223 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
3224 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
3225 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
3226 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
3229 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
3231 if (dst
->node
[j
].compressed
&&
3232 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
3233 !dst
->node
[j
].decompress
))
3240 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3241 * to the dst dependence graph.
3242 * If the source or destination node of the edge is not in the destination
3243 * graph, then it must be a backward proximity edge and it should simply
3246 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3247 struct isl_sched_graph
*src
,
3248 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3251 enum isl_edge_type t
;
3254 for (i
= 0; i
< src
->n_edge
; ++i
) {
3255 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3257 isl_union_map
*tagged_condition
;
3258 isl_union_map
*tagged_validity
;
3259 struct isl_sched_node
*dst_src
, *dst_dst
;
3261 if (!edge_pred(edge
, data
))
3264 if (isl_map_plain_is_empty(edge
->map
))
3267 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
3268 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
3269 if (!dst_src
|| !dst_dst
) {
3270 if (is_validity(edge
) || is_conditional_validity(edge
))
3271 isl_die(ctx
, isl_error_internal
,
3272 "backward (conditional) validity edge",
3277 map
= isl_map_copy(edge
->map
);
3278 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3279 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3281 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3282 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3283 dst
->edge
[dst
->n_edge
].map
= map
;
3284 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3285 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3286 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3289 if (edge
->tagged_condition
&& !tagged_condition
)
3291 if (edge
->tagged_validity
&& !tagged_validity
)
3294 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
3296 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
3298 if (graph_edge_table_add(ctx
, dst
, t
,
3299 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3307 /* Compute the maximal number of variables over all nodes.
3308 * This is the maximal number of linearly independent schedule
3309 * rows that we need to compute.
3310 * Just in case we end up in a part of the dependence graph
3311 * with only lower-dimensional domains, we make sure we will
3312 * compute the required amount of extra linearly independent rows.
3314 static int compute_maxvar(struct isl_sched_graph
*graph
)
3319 for (i
= 0; i
< graph
->n
; ++i
) {
3320 struct isl_sched_node
*node
= &graph
->node
[i
];
3323 if (node_update_cmap(node
) < 0)
3325 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3326 if (nvar
> graph
->maxvar
)
3327 graph
->maxvar
= nvar
;
3333 /* Extract the subgraph of "graph" that consists of the node satisfying
3334 * "node_pred" and the edges satisfying "edge_pred" and store
3335 * the result in "sub".
3337 static int extract_sub_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3338 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3339 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3340 int data
, struct isl_sched_graph
*sub
)
3342 int i
, n
= 0, n_edge
= 0;
3345 for (i
= 0; i
< graph
->n
; ++i
)
3346 if (node_pred(&graph
->node
[i
], data
))
3348 for (i
= 0; i
< graph
->n_edge
; ++i
)
3349 if (edge_pred(&graph
->edge
[i
], data
))
3351 if (graph_alloc(ctx
, sub
, n
, n_edge
) < 0)
3353 if (copy_nodes(sub
, graph
, node_pred
, data
) < 0)
3355 if (graph_init_table(ctx
, sub
) < 0)
3357 for (t
= 0; t
<= isl_edge_last
; ++t
)
3358 sub
->max_edge
[t
] = graph
->max_edge
[t
];
3359 if (graph_init_edge_tables(ctx
, sub
) < 0)
3361 if (copy_edges(ctx
, sub
, graph
, edge_pred
, data
) < 0)
3363 sub
->n_row
= graph
->n_row
;
3364 sub
->max_row
= graph
->max_row
;
3365 sub
->n_total_row
= graph
->n_total_row
;
3366 sub
->band_start
= graph
->band_start
;
3371 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3372 struct isl_sched_graph
*graph
);
3373 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3374 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3376 /* Compute a schedule for a subgraph of "graph". In particular, for
3377 * the graph composed of nodes that satisfy node_pred and edges that
3378 * that satisfy edge_pred.
3379 * If the subgraph is known to consist of a single component, then wcc should
3380 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3381 * Otherwise, we call compute_schedule, which will check whether the subgraph
3384 * The schedule is inserted at "node" and the updated schedule node
3387 static __isl_give isl_schedule_node
*compute_sub_schedule(
3388 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3389 struct isl_sched_graph
*graph
,
3390 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3391 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3394 struct isl_sched_graph split
= { 0 };
3396 if (extract_sub_graph(ctx
, graph
, node_pred
, edge_pred
, data
,
3401 node
= compute_schedule_wcc(node
, &split
);
3403 node
= compute_schedule(node
, &split
);
3405 graph_free(ctx
, &split
);
3408 graph_free(ctx
, &split
);
3409 return isl_schedule_node_free(node
);
3412 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3414 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3417 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3419 return edge
->dst
->scc
<= scc
;
3422 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3424 return edge
->src
->scc
>= scc
;
3427 /* Reset the current band by dropping all its schedule rows.
3429 static int reset_band(struct isl_sched_graph
*graph
)
3434 drop
= graph
->n_total_row
- graph
->band_start
;
3435 graph
->n_total_row
-= drop
;
3436 graph
->n_row
-= drop
;
3438 for (i
= 0; i
< graph
->n
; ++i
) {
3439 struct isl_sched_node
*node
= &graph
->node
[i
];
3441 isl_map_free(node
->sched_map
);
3442 node
->sched_map
= NULL
;
3444 node
->sched
= isl_mat_drop_rows(node
->sched
,
3445 graph
->band_start
, drop
);
3454 /* Split the current graph into two parts and compute a schedule for each
3455 * part individually. In particular, one part consists of all SCCs up
3456 * to and including graph->src_scc, while the other part contains the other
3457 * SCCs. The split is enforced by a sequence node inserted at position "node"
3458 * in the schedule tree. Return the updated schedule node.
3459 * If either of these two parts consists of a sequence, then it is spliced
3460 * into the sequence containing the two parts.
3462 * The current band is reset. It would be possible to reuse
3463 * the previously computed rows as the first rows in the next
3464 * band, but recomputing them may result in better rows as we are looking
3465 * at a smaller part of the dependence graph.
3467 static __isl_give isl_schedule_node
*compute_split_schedule(
3468 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3472 isl_union_set_list
*filters
;
3477 if (reset_band(graph
) < 0)
3478 return isl_schedule_node_free(node
);
3482 ctx
= isl_schedule_node_get_ctx(node
);
3483 filters
= extract_split(ctx
, graph
);
3484 node
= isl_schedule_node_insert_sequence(node
, filters
);
3485 node
= isl_schedule_node_child(node
, 1);
3486 node
= isl_schedule_node_child(node
, 0);
3488 node
= compute_sub_schedule(node
, ctx
, graph
,
3489 &node_scc_at_least
, &edge_src_scc_at_least
,
3490 graph
->src_scc
+ 1, 0);
3491 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3492 node
= isl_schedule_node_parent(node
);
3493 node
= isl_schedule_node_parent(node
);
3495 node
= isl_schedule_node_sequence_splice_child(node
, 1);
3496 node
= isl_schedule_node_child(node
, 0);
3497 node
= isl_schedule_node_child(node
, 0);
3498 node
= compute_sub_schedule(node
, ctx
, graph
,
3499 &node_scc_at_most
, &edge_dst_scc_at_most
,
3501 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3502 node
= isl_schedule_node_parent(node
);
3503 node
= isl_schedule_node_parent(node
);
3505 node
= isl_schedule_node_sequence_splice_child(node
, 0);
3510 /* Insert a band node at position "node" in the schedule tree corresponding
3511 * to the current band in "graph". Mark the band node permutable
3512 * if "permutable" is set.
3513 * The partial schedules and the coincidence property are extracted
3514 * from the graph nodes.
3515 * Return the updated schedule node.
3517 static __isl_give isl_schedule_node
*insert_current_band(
3518 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3524 isl_multi_pw_aff
*mpa
;
3525 isl_multi_union_pw_aff
*mupa
;
3531 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3532 "graph should have at least one node",
3533 return isl_schedule_node_free(node
));
3535 start
= graph
->band_start
;
3536 end
= graph
->n_total_row
;
3539 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3540 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3541 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3543 for (i
= 1; i
< graph
->n
; ++i
) {
3544 isl_multi_union_pw_aff
*mupa_i
;
3546 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3548 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3549 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3550 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3552 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3554 for (i
= 0; i
< n
; ++i
)
3555 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3556 graph
->node
[0].coincident
[start
+ i
]);
3557 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3562 /* Update the dependence relations based on the current schedule,
3563 * add the current band to "node" and then continue with the computation
3565 * Return the updated schedule node.
3567 static __isl_give isl_schedule_node
*compute_next_band(
3568 __isl_take isl_schedule_node
*node
,
3569 struct isl_sched_graph
*graph
, int permutable
)
3576 ctx
= isl_schedule_node_get_ctx(node
);
3577 if (update_edges(ctx
, graph
) < 0)
3578 return isl_schedule_node_free(node
);
3579 node
= insert_current_band(node
, graph
, permutable
);
3582 node
= isl_schedule_node_child(node
, 0);
3583 node
= compute_schedule(node
, graph
);
3584 node
= isl_schedule_node_parent(node
);
3589 /* Add constraints to graph->lp that force the dependence "map" (which
3590 * is part of the dependence relation of "edge")
3591 * to be respected and attempt to carry it, where the edge is one from
3592 * a node j to itself. "pos" is the sequence number of the given map.
3593 * That is, add constraints that enforce
3595 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3596 * = c_j_x (y - x) >= e_i
3598 * for each (x,y) in R.
3599 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3600 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3601 * with each coefficient in c_j_x represented as a pair of non-negative
3604 static int add_intra_constraints(struct isl_sched_graph
*graph
,
3605 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3608 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3610 isl_dim_map
*dim_map
;
3611 isl_basic_set
*coef
;
3612 struct isl_sched_node
*node
= edge
->src
;
3614 coef
= intra_coefficients(graph
, node
, map
);
3618 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3620 total
= isl_basic_set_total_dim(graph
->lp
);
3621 dim_map
= isl_dim_map_alloc(ctx
, total
);
3622 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3623 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
3624 isl_space_dim(dim
, isl_dim_set
), 1,
3626 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
3627 isl_space_dim(dim
, isl_dim_set
), 1,
3629 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3630 coef
->n_eq
, coef
->n_ineq
);
3631 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3633 isl_space_free(dim
);
3638 /* Add constraints to graph->lp that force the dependence "map" (which
3639 * is part of the dependence relation of "edge")
3640 * to be respected and attempt to carry it, where the edge is one from
3641 * node j to node k. "pos" is the sequence number of the given map.
3642 * That is, add constraints that enforce
3644 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3646 * for each (x,y) in R.
3647 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3648 * of valid constraints for R and then plug in
3649 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3650 * with each coefficient (except e_i, c_k_0 and c_j_0)
3651 * represented as a pair of non-negative coefficients.
3653 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3654 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3657 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3659 isl_dim_map
*dim_map
;
3660 isl_basic_set
*coef
;
3661 struct isl_sched_node
*src
= edge
->src
;
3662 struct isl_sched_node
*dst
= edge
->dst
;
3664 coef
= inter_coefficients(graph
, edge
, map
);
3668 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3670 total
= isl_basic_set_total_dim(graph
->lp
);
3671 dim_map
= isl_dim_map_alloc(ctx
, total
);
3673 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3675 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
3676 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
3677 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
3678 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
3679 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3681 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
3682 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3685 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
3686 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
3687 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
3688 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
3689 isl_space_dim(dim
, isl_dim_set
), 1,
3691 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
3692 isl_space_dim(dim
, isl_dim_set
), 1,
3695 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3696 coef
->n_eq
, coef
->n_ineq
);
3697 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3699 isl_space_free(dim
);
3704 /* Add constraints to graph->lp that force all (conditional) validity
3705 * dependences to be respected and attempt to carry them.
3707 static int add_all_constraints(struct isl_sched_graph
*graph
)
3713 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3714 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3716 if (!is_validity(edge
) && !is_conditional_validity(edge
))
3719 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3720 isl_basic_map
*bmap
;
3723 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3724 map
= isl_map_from_basic_map(bmap
);
3726 if (edge
->src
== edge
->dst
&&
3727 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3729 if (edge
->src
!= edge
->dst
&&
3730 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3739 /* Count the number of equality and inequality constraints
3740 * that will be added to the carry_lp problem.
3741 * We count each edge exactly once.
3743 static int count_all_constraints(struct isl_sched_graph
*graph
,
3744 int *n_eq
, int *n_ineq
)
3748 *n_eq
= *n_ineq
= 0;
3749 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3750 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3751 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3752 isl_basic_map
*bmap
;
3755 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3756 map
= isl_map_from_basic_map(bmap
);
3758 if (count_map_constraints(graph
, edge
, map
,
3759 n_eq
, n_ineq
, 1, 0) < 0)
3767 /* Construct an LP problem for finding schedule coefficients
3768 * such that the schedule carries as many dependences as possible.
3769 * In particular, for each dependence i, we bound the dependence distance
3770 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3771 * of all e_i's. Dependences with e_i = 0 in the solution are simply
3772 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3773 * Note that if the dependence relation is a union of basic maps,
3774 * then we have to consider each basic map individually as it may only
3775 * be possible to carry the dependences expressed by some of those
3776 * basic maps and not all of them.
3777 * Below, we consider each of those basic maps as a separate "edge".
3779 * All variables of the LP are non-negative. The actual coefficients
3780 * may be negative, so each coefficient is represented as the difference
3781 * of two non-negative variables. The negative part always appears
3782 * immediately before the positive part.
3783 * Other than that, the variables have the following order
3785 * - sum of (1 - e_i) over all edges
3786 * - sum of positive and negative parts of all c_n coefficients
3787 * (unconstrained when computing non-parametric schedules)
3788 * - sum of positive and negative parts of all c_x coefficients
3793 * - positive and negative parts of c_i_n (if parametric)
3794 * - positive and negative parts of c_i_x
3796 * The constraints are those from the (validity) edges plus three equalities
3797 * to express the sums and n_edge inequalities to express e_i <= 1.
3799 static isl_stat
setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3809 for (i
= 0; i
< graph
->n_edge
; ++i
)
3810 n_edge
+= graph
->edge
[i
].map
->n
;
3813 for (i
= 0; i
< graph
->n
; ++i
) {
3814 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3815 node
->start
= total
;
3816 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
3819 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3820 return isl_stat_error
;
3822 dim
= isl_space_set_alloc(ctx
, 0, total
);
3823 isl_basic_set_free(graph
->lp
);
3826 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3827 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3829 k
= isl_basic_set_alloc_equality(graph
->lp
);
3831 return isl_stat_error
;
3832 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3833 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3834 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3835 for (i
= 0; i
< n_edge
; ++i
)
3836 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3838 if (add_param_sum_constraint(graph
, 1) < 0)
3839 return isl_stat_error
;
3840 if (add_var_sum_constraint(graph
, 2) < 0)
3841 return isl_stat_error
;
3843 for (i
= 0; i
< n_edge
; ++i
) {
3844 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3846 return isl_stat_error
;
3847 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3848 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3849 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3852 if (add_all_constraints(graph
) < 0)
3853 return isl_stat_error
;
3858 static __isl_give isl_schedule_node
*compute_component_schedule(
3859 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3862 /* Comparison function for sorting the statements based on
3863 * the corresponding value in "r".
3865 static int smaller_value(const void *a
, const void *b
, void *data
)
3871 return isl_int_cmp(r
->el
[*i1
], r
->el
[*i2
]);
3874 /* If the schedule_split_scaled option is set and if the linear
3875 * parts of the scheduling rows for all nodes in the graphs have
3876 * a non-trivial common divisor, then split off the remainder of the
3877 * constant term modulo this common divisor from the linear part.
3878 * Otherwise, insert a band node directly and continue with
3879 * the construction of the schedule.
3881 * If a non-trivial common divisor is found, then
3882 * the linear part is reduced and the remainder is enforced
3883 * by a sequence node with the children placed in the order
3884 * of this remainder.
3885 * In particular, we assign an scc index based on the remainder and
3886 * then rely on compute_component_schedule to insert the sequence and
3887 * to continue the schedule construction on each part.
3889 static __isl_give isl_schedule_node
*split_scaled(
3890 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3903 ctx
= isl_schedule_node_get_ctx(node
);
3904 if (!ctx
->opt
->schedule_split_scaled
)
3905 return compute_next_band(node
, graph
, 0);
3907 return compute_next_band(node
, graph
, 0);
3910 isl_int_init(gcd_i
);
3912 isl_int_set_si(gcd
, 0);
3914 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3916 for (i
= 0; i
< graph
->n
; ++i
) {
3917 struct isl_sched_node
*node
= &graph
->node
[i
];
3918 int cols
= isl_mat_cols(node
->sched
);
3920 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3921 isl_int_gcd(gcd
, gcd
, gcd_i
);
3924 isl_int_clear(gcd_i
);
3926 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3928 return compute_next_band(node
, graph
, 0);
3931 r
= isl_vec_alloc(ctx
, graph
->n
);
3932 order
= isl_calloc_array(ctx
, int, graph
->n
);
3936 for (i
= 0; i
< graph
->n
; ++i
) {
3937 struct isl_sched_node
*node
= &graph
->node
[i
];
3940 isl_int_fdiv_r(r
->el
[i
], node
->sched
->row
[row
][0], gcd
);
3941 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3942 node
->sched
->row
[row
][0], gcd
);
3943 isl_int_mul(node
->sched
->row
[row
][0],
3944 node
->sched
->row
[row
][0], gcd
);
3945 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3950 if (isl_sort(order
, graph
->n
, sizeof(order
[0]), &smaller_value
, r
) < 0)
3954 for (i
= 0; i
< graph
->n
; ++i
) {
3955 if (i
> 0 && isl_int_ne(r
->el
[order
[i
- 1]], r
->el
[order
[i
]]))
3957 graph
->node
[order
[i
]].scc
= scc
;
3966 if (update_edges(ctx
, graph
) < 0)
3967 return isl_schedule_node_free(node
);
3968 node
= insert_current_band(node
, graph
, 0);
3971 node
= isl_schedule_node_child(node
, 0);
3972 node
= compute_component_schedule(node
, graph
, 0);
3973 node
= isl_schedule_node_parent(node
);
3980 return isl_schedule_node_free(node
);
3983 /* Is the schedule row "sol" trivial on node "node"?
3984 * That is, is the solution zero on the dimensions orthogonal to
3985 * the previously found solutions?
3986 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3988 * Each coefficient is represented as the difference between
3989 * two non-negative values in "sol". "sol" has been computed
3990 * in terms of the original iterators (i.e., without use of cmap).
3991 * We construct the schedule row s and write it as a linear
3992 * combination of (linear combinations of) previously computed schedule rows.
3993 * s = Q c or c = U s.
3994 * If the final entries of c are all zero, then the solution is trivial.
3996 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
4006 if (node
->nvar
== node
->rank
)
4009 ctx
= isl_vec_get_ctx(sol
);
4010 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
4014 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
4016 for (i
= 0; i
< node
->nvar
; ++i
)
4017 isl_int_sub(node_sol
->el
[i
],
4018 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
4020 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
4025 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
4026 node
->nvar
- node
->rank
) == -1;
4028 isl_vec_free(node_sol
);
4033 /* Is the schedule row "sol" trivial on any node where it should
4035 * "sol" has been computed in terms of the original iterators
4036 * (i.e., without use of cmap).
4037 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4039 static int is_any_trivial(struct isl_sched_graph
*graph
,
4040 __isl_keep isl_vec
*sol
)
4044 for (i
= 0; i
< graph
->n
; ++i
) {
4045 struct isl_sched_node
*node
= &graph
->node
[i
];
4048 if (!needs_row(graph
, node
))
4050 trivial
= is_trivial(node
, sol
);
4051 if (trivial
< 0 || trivial
)
4058 /* Construct a schedule row for each node such that as many dependences
4059 * as possible are carried and then continue with the next band.
4061 * Note that despite the fact that the problem is solved using a rational
4062 * solver, the solution is guaranteed to be integral.
4063 * Specifically, the dependence distance lower bounds e_i (and therefore
4064 * also their sum) are integers. See Lemma 5 of [1].
4066 * If the computed schedule row turns out to be trivial on one or
4067 * more nodes where it should not be trivial, then we throw it away
4068 * and try again on each component separately.
4070 * If there is only one component, then we accept the schedule row anyway,
4071 * but we do not consider it as a complete row and therefore do not
4072 * increment graph->n_row. Note that the ranks of the nodes that
4073 * do get a non-trivial schedule part will get updated regardless and
4074 * graph->maxvar is computed based on these ranks. The test for
4075 * whether more schedule rows are required in compute_schedule_wcc
4076 * is therefore not affected.
4078 * Insert a band corresponding to the schedule row at position "node"
4079 * of the schedule tree and continue with the construction of the schedule.
4080 * This insertion and the continued construction is performed by split_scaled
4081 * after optionally checking for non-trivial common divisors.
4083 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4084 * Problem, Part II: Multi-Dimensional Time.
4085 * In Intl. Journal of Parallel Programming, 1992.
4087 static __isl_give isl_schedule_node
*carry_dependences(
4088 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4101 for (i
= 0; i
< graph
->n_edge
; ++i
)
4102 n_edge
+= graph
->edge
[i
].map
->n
;
4104 ctx
= isl_schedule_node_get_ctx(node
);
4105 if (setup_carry_lp(ctx
, graph
) < 0)
4106 return isl_schedule_node_free(node
);
4108 lp
= isl_basic_set_copy(graph
->lp
);
4109 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
4111 return isl_schedule_node_free(node
);
4113 if (sol
->size
== 0) {
4115 isl_die(ctx
, isl_error_internal
,
4116 "error in schedule construction",
4117 return isl_schedule_node_free(node
));
4120 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
4121 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
4123 isl_die(ctx
, isl_error_unknown
,
4124 "unable to carry dependences",
4125 return isl_schedule_node_free(node
));
4128 trivial
= is_any_trivial(graph
, sol
);
4130 sol
= isl_vec_free(sol
);
4131 } else if (trivial
&& graph
->scc
> 1) {
4133 return compute_component_schedule(node
, graph
, 1);
4136 if (update_schedule(graph
, sol
, 0, 0) < 0)
4137 return isl_schedule_node_free(node
);
4141 return split_scaled(node
, graph
);
4144 /* Topologically sort statements mapped to the same schedule iteration
4145 * and add insert a sequence node in front of "node"
4146 * corresponding to this order.
4147 * If "initialized" is set, then it may be assumed that compute_maxvar
4148 * has been called on the current band. Otherwise, call
4149 * compute_maxvar if and before carry_dependences gets called.
4151 * If it turns out to be impossible to sort the statements apart,
4152 * because different dependences impose different orderings
4153 * on the statements, then we extend the schedule such that
4154 * it carries at least one more dependence.
4156 static __isl_give isl_schedule_node
*sort_statements(
4157 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4161 isl_union_set_list
*filters
;
4166 ctx
= isl_schedule_node_get_ctx(node
);
4168 isl_die(ctx
, isl_error_internal
,
4169 "graph should have at least one node",
4170 return isl_schedule_node_free(node
));
4175 if (update_edges(ctx
, graph
) < 0)
4176 return isl_schedule_node_free(node
);
4178 if (graph
->n_edge
== 0)
4181 if (detect_sccs(ctx
, graph
) < 0)
4182 return isl_schedule_node_free(node
);
4185 if (graph
->scc
< graph
->n
) {
4186 if (!initialized
&& compute_maxvar(graph
) < 0)
4187 return isl_schedule_node_free(node
);
4188 return carry_dependences(node
, graph
);
4191 filters
= extract_sccs(ctx
, graph
);
4192 node
= isl_schedule_node_insert_sequence(node
, filters
);
4197 /* Are there any (non-empty) (conditional) validity edges in the graph?
4199 static int has_validity_edges(struct isl_sched_graph
*graph
)
4203 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4206 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
4211 if (is_validity(&graph
->edge
[i
]) ||
4212 is_conditional_validity(&graph
->edge
[i
]))
4219 /* Should we apply a Feautrier step?
4220 * That is, did the user request the Feautrier algorithm and are
4221 * there any validity dependences (left)?
4223 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4225 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
4228 return has_validity_edges(graph
);
4231 /* Compute a schedule for a connected dependence graph using Feautrier's
4232 * multi-dimensional scheduling algorithm and return the updated schedule node.
4234 * The original algorithm is described in [1].
4235 * The main idea is to minimize the number of scheduling dimensions, by
4236 * trying to satisfy as many dependences as possible per scheduling dimension.
4238 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4239 * Problem, Part II: Multi-Dimensional Time.
4240 * In Intl. Journal of Parallel Programming, 1992.
4242 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
4243 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4245 return carry_dependences(node
, graph
);
4248 /* Turn off the "local" bit on all (condition) edges.
4250 static void clear_local_edges(struct isl_sched_graph
*graph
)
4254 for (i
= 0; i
< graph
->n_edge
; ++i
)
4255 if (is_condition(&graph
->edge
[i
]))
4256 clear_local(&graph
->edge
[i
]);
4259 /* Does "graph" have both condition and conditional validity edges?
4261 static int need_condition_check(struct isl_sched_graph
*graph
)
4264 int any_condition
= 0;
4265 int any_conditional_validity
= 0;
4267 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4268 if (is_condition(&graph
->edge
[i
]))
4270 if (is_conditional_validity(&graph
->edge
[i
]))
4271 any_conditional_validity
= 1;
4274 return any_condition
&& any_conditional_validity
;
4277 /* Does "graph" contain any coincidence edge?
4279 static int has_any_coincidence(struct isl_sched_graph
*graph
)
4283 for (i
= 0; i
< graph
->n_edge
; ++i
)
4284 if (is_coincidence(&graph
->edge
[i
]))
4290 /* Extract the final schedule row as a map with the iteration domain
4291 * of "node" as domain.
4293 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
4295 isl_local_space
*ls
;
4299 row
= isl_mat_rows(node
->sched
) - 1;
4300 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
4301 aff
= extract_schedule_row(ls
, node
, row
);
4302 return isl_map_from_aff(aff
);
4305 /* Is the conditional validity dependence in the edge with index "edge_index"
4306 * violated by the latest (i.e., final) row of the schedule?
4307 * That is, is i scheduled after j
4308 * for any conditional validity dependence i -> j?
4310 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
4312 isl_map
*src_sched
, *dst_sched
, *map
;
4313 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
4316 src_sched
= final_row(edge
->src
);
4317 dst_sched
= final_row(edge
->dst
);
4318 map
= isl_map_copy(edge
->map
);
4319 map
= isl_map_apply_domain(map
, src_sched
);
4320 map
= isl_map_apply_range(map
, dst_sched
);
4321 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
4322 empty
= isl_map_is_empty(map
);
4331 /* Does "graph" have any satisfied condition edges that
4332 * are adjacent to the conditional validity constraint with
4333 * domain "conditional_source" and range "conditional_sink"?
4335 * A satisfied condition is one that is not local.
4336 * If a condition was forced to be local already (i.e., marked as local)
4337 * then there is no need to check if it is in fact local.
4339 * Additionally, mark all adjacent condition edges found as local.
4341 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
4342 __isl_keep isl_union_set
*conditional_source
,
4343 __isl_keep isl_union_set
*conditional_sink
)
4348 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4349 int adjacent
, local
;
4350 isl_union_map
*condition
;
4352 if (!is_condition(&graph
->edge
[i
]))
4354 if (is_local(&graph
->edge
[i
]))
4357 condition
= graph
->edge
[i
].tagged_condition
;
4358 adjacent
= domain_intersects(condition
, conditional_sink
);
4359 if (adjacent
>= 0 && !adjacent
)
4360 adjacent
= range_intersects(condition
,
4361 conditional_source
);
4367 set_local(&graph
->edge
[i
]);
4369 local
= is_condition_false(&graph
->edge
[i
]);
4379 /* Are there any violated conditional validity dependences with
4380 * adjacent condition dependences that are not local with respect
4381 * to the current schedule?
4382 * That is, is the conditional validity constraint violated?
4384 * Additionally, mark all those adjacent condition dependences as local.
4385 * We also mark those adjacent condition dependences that were not marked
4386 * as local before, but just happened to be local already. This ensures
4387 * that they remain local if the schedule is recomputed.
4389 * We first collect domain and range of all violated conditional validity
4390 * dependences and then check if there are any adjacent non-local
4391 * condition dependences.
4393 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
4394 struct isl_sched_graph
*graph
)
4398 isl_union_set
*source
, *sink
;
4400 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4401 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4402 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4403 isl_union_set
*uset
;
4404 isl_union_map
*umap
;
4407 if (!is_conditional_validity(&graph
->edge
[i
]))
4410 violated
= is_violated(graph
, i
);
4418 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4419 uset
= isl_union_map_domain(umap
);
4420 source
= isl_union_set_union(source
, uset
);
4421 source
= isl_union_set_coalesce(source
);
4423 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4424 uset
= isl_union_map_range(umap
);
4425 sink
= isl_union_set_union(sink
, uset
);
4426 sink
= isl_union_set_coalesce(sink
);
4430 any
= has_adjacent_true_conditions(graph
, source
, sink
);
4432 isl_union_set_free(source
);
4433 isl_union_set_free(sink
);
4436 isl_union_set_free(source
);
4437 isl_union_set_free(sink
);
4441 /* Examine the current band (the rows between graph->band_start and
4442 * graph->n_total_row), deciding whether to drop it or add it to "node"
4443 * and then continue with the computation of the next band, if any.
4444 * If "initialized" is set, then it may be assumed that compute_maxvar
4445 * has been called on the current band. Otherwise, call
4446 * compute_maxvar if and before carry_dependences gets called.
4448 * The caller keeps looking for a new row as long as
4449 * graph->n_row < graph->maxvar. If the latest attempt to find
4450 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
4452 * - split between SCCs and start over (assuming we found an interesting
4453 * pair of SCCs between which to split)
4454 * - continue with the next band (assuming the current band has at least
4456 * - try to carry as many dependences as possible and continue with the next
4458 * In each case, we first insert a band node in the schedule tree
4459 * if any rows have been computed.
4461 * If the caller managed to complete the schedule, we insert a band node
4462 * (if any schedule rows were computed) and we finish off by topologically
4463 * sorting the statements based on the remaining dependences.
4465 static __isl_give isl_schedule_node
*compute_schedule_finish_band(
4466 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4474 if (graph
->n_row
< graph
->maxvar
) {
4476 int empty
= graph
->n_total_row
== graph
->band_start
;
4478 ctx
= isl_schedule_node_get_ctx(node
);
4479 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
4480 return compute_next_band(node
, graph
, 1);
4481 if (graph
->src_scc
>= 0)
4482 return compute_split_schedule(node
, graph
);
4484 return compute_next_band(node
, graph
, 1);
4485 if (!initialized
&& compute_maxvar(graph
) < 0)
4486 return isl_schedule_node_free(node
);
4487 return carry_dependences(node
, graph
);
4490 insert
= graph
->n_total_row
> graph
->band_start
;
4492 node
= insert_current_band(node
, graph
, 1);
4493 node
= isl_schedule_node_child(node
, 0);
4495 node
= sort_statements(node
, graph
, initialized
);
4497 node
= isl_schedule_node_parent(node
);
4502 /* Construct a band of schedule rows for a connected dependence graph.
4503 * The caller is responsible for determining the strongly connected
4504 * components and calling compute_maxvar first.
4506 * We try to find a sequence of as many schedule rows as possible that result
4507 * in non-negative dependence distances (independent of the previous rows
4508 * in the sequence, i.e., such that the sequence is tilable), with as
4509 * many of the initial rows as possible satisfying the coincidence constraints.
4510 * The computation stops if we can't find any more rows or if we have found
4511 * all the rows we wanted to find.
4513 * If ctx->opt->schedule_outer_coincidence is set, then we force the
4514 * outermost dimension to satisfy the coincidence constraints. If this
4515 * turns out to be impossible, we fall back on the general scheme above
4516 * and try to carry as many dependences as possible.
4518 * If "graph" contains both condition and conditional validity dependences,
4519 * then we need to check that that the conditional schedule constraint
4520 * is satisfied, i.e., there are no violated conditional validity dependences
4521 * that are adjacent to any non-local condition dependences.
4522 * If there are, then we mark all those adjacent condition dependences
4523 * as local and recompute the current band. Those dependences that
4524 * are marked local will then be forced to be local.
4525 * The initial computation is performed with no dependences marked as local.
4526 * If we are lucky, then there will be no violated conditional validity
4527 * dependences adjacent to any non-local condition dependences.
4528 * Otherwise, we mark some additional condition dependences as local and
4529 * recompute. We continue this process until there are no violations left or
4530 * until we are no longer able to compute a schedule.
4531 * Since there are only a finite number of dependences,
4532 * there will only be a finite number of iterations.
4534 static isl_stat
compute_schedule_wcc_band(isl_ctx
*ctx
,
4535 struct isl_sched_graph
*graph
)
4537 int has_coincidence
;
4538 int use_coincidence
;
4539 int force_coincidence
= 0;
4540 int check_conditional
;
4542 if (sort_sccs(graph
) < 0)
4543 return isl_stat_error
;
4545 clear_local_edges(graph
);
4546 check_conditional
= need_condition_check(graph
);
4547 has_coincidence
= has_any_coincidence(graph
);
4549 if (ctx
->opt
->schedule_outer_coincidence
)
4550 force_coincidence
= 1;
4552 use_coincidence
= has_coincidence
;
4553 while (graph
->n_row
< graph
->maxvar
) {
4558 graph
->src_scc
= -1;
4559 graph
->dst_scc
= -1;
4561 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
4562 return isl_stat_error
;
4563 sol
= solve_lp(graph
);
4565 return isl_stat_error
;
4566 if (sol
->size
== 0) {
4567 int empty
= graph
->n_total_row
== graph
->band_start
;
4570 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
4571 use_coincidence
= 0;
4576 coincident
= !has_coincidence
|| use_coincidence
;
4577 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
4578 return isl_stat_error
;
4580 if (!check_conditional
)
4582 violated
= has_violated_conditional_constraint(ctx
, graph
);
4584 return isl_stat_error
;
4587 if (reset_band(graph
) < 0)
4588 return isl_stat_error
;
4589 use_coincidence
= has_coincidence
;
4595 /* Compute a schedule for a connected dependence graph by considering
4596 * the graph as a whole and return the updated schedule node.
4598 * The actual schedule rows of the current band are computed by
4599 * compute_schedule_wcc_band. compute_schedule_finish_band takes
4600 * care of integrating the band into "node" and continuing
4603 static __isl_give isl_schedule_node
*compute_schedule_wcc_whole(
4604 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4611 ctx
= isl_schedule_node_get_ctx(node
);
4612 if (compute_schedule_wcc_band(ctx
, graph
) < 0)
4613 return isl_schedule_node_free(node
);
4615 return compute_schedule_finish_band(node
, graph
, 1);
4618 /* Clustering information used by compute_schedule_wcc_clustering.
4620 * "n" is the number of SCCs in the original dependence graph
4621 * "scc" is an array of "n" elements, each representing an SCC
4622 * of the original dependence graph. All entries in the same cluster
4623 * have the same number of schedule rows.
4624 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
4625 * where each cluster is represented by the index of the first SCC
4626 * in the cluster. Initially, each SCC belongs to a cluster containing
4629 * "scc_in_merge" is used by merge_clusters_along_edge to keep
4630 * track of which SCCs need to be merged.
4632 * "cluster" contains the merged clusters of SCCs after the clustering
4635 * "scc_node" is a temporary data structure used inside copy_partial.
4636 * For each SCC, it keeps track of the number of nodes in the SCC
4637 * that have already been copied.
4639 struct isl_clustering
{
4641 struct isl_sched_graph
*scc
;
4642 struct isl_sched_graph
*cluster
;
4648 /* Initialize the clustering data structure "c" from "graph".
4650 * In particular, allocate memory, extract the SCCs from "graph"
4651 * into c->scc, initialize scc_cluster and construct
4652 * a band of schedule rows for each SCC.
4653 * Within each SCC, there is only one SCC by definition.
4654 * Each SCC initially belongs to a cluster containing only that SCC.
4656 static isl_stat
clustering_init(isl_ctx
*ctx
, struct isl_clustering
*c
,
4657 struct isl_sched_graph
*graph
)
4662 c
->scc
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
4663 c
->cluster
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
4664 c
->scc_cluster
= isl_calloc_array(ctx
, int, c
->n
);
4665 c
->scc_node
= isl_calloc_array(ctx
, int, c
->n
);
4666 c
->scc_in_merge
= isl_calloc_array(ctx
, int, c
->n
);
4667 if (!c
->scc
|| !c
->cluster
||
4668 !c
->scc_cluster
|| !c
->scc_node
|| !c
->scc_in_merge
)
4669 return isl_stat_error
;
4671 for (i
= 0; i
< c
->n
; ++i
) {
4672 if (extract_sub_graph(ctx
, graph
, &node_scc_exactly
,
4673 &edge_scc_exactly
, i
, &c
->scc
[i
]) < 0)
4674 return isl_stat_error
;
4676 if (compute_maxvar(&c
->scc
[i
]) < 0)
4677 return isl_stat_error
;
4678 if (compute_schedule_wcc_band(ctx
, &c
->scc
[i
]) < 0)
4679 return isl_stat_error
;
4680 c
->scc_cluster
[i
] = i
;
4686 /* Free all memory allocated for "c".
4688 static void clustering_free(isl_ctx
*ctx
, struct isl_clustering
*c
)
4693 for (i
= 0; i
< c
->n
; ++i
)
4694 graph_free(ctx
, &c
->scc
[i
]);
4697 for (i
= 0; i
< c
->n
; ++i
)
4698 graph_free(ctx
, &c
->cluster
[i
]);
4700 free(c
->scc_cluster
);
4702 free(c
->scc_in_merge
);
4705 /* Should we refrain from merging the cluster in "graph" with
4706 * any other cluster?
4707 * In particular, is its current schedule band empty and incomplete.
4709 static int bad_cluster(struct isl_sched_graph
*graph
)
4711 return graph
->n_row
< graph
->maxvar
&&
4712 graph
->n_total_row
== graph
->band_start
;
4715 /* Return the index of an edge in "graph" that can be used to merge
4716 * two clusters in "c".
4717 * Return graph->n_edge if no such edge can be found.
4718 * Return -1 on error.
4720 * In particular, return a proximity edge between two clusters
4721 * that is not marked "no_merge" and such that neither of the
4722 * two clusters has an incomplete, empty band.
4724 * If there are multiple such edges, then try and find the most
4725 * appropriate edge to use for merging. In particular, pick the edge
4726 * with the greatest weight. If there are multiple of those,
4727 * then pick one with the shortest distance between
4728 * the two cluster representatives.
4730 static int find_proximity(struct isl_sched_graph
*graph
,
4731 struct isl_clustering
*c
)
4733 int i
, best
= graph
->n_edge
, best_dist
, best_weight
;
4735 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4736 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4739 if (!is_proximity(edge
))
4743 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
4744 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
4746 dist
= c
->scc_cluster
[edge
->dst
->scc
] -
4747 c
->scc_cluster
[edge
->src
->scc
];
4750 weight
= edge
->weight
;
4751 if (best
< graph
->n_edge
) {
4752 if (best_weight
> weight
)
4754 if (best_weight
== weight
&& best_dist
<= dist
)
4759 best_weight
= weight
;
4765 /* Internal data structure used in mark_merge_sccs.
4767 * "graph" is the dependence graph in which a strongly connected
4768 * component is constructed.
4769 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
4770 * "src" and "dst" are the indices of the nodes that are being merged.
4772 struct isl_mark_merge_sccs_data
{
4773 struct isl_sched_graph
*graph
;
4779 /* Check whether the cluster containing node "i" depends on the cluster
4780 * containing node "j". If "i" and "j" belong to the same cluster,
4781 * then they are taken to depend on each other to ensure that
4782 * the resulting strongly connected component consists of complete
4783 * clusters. Furthermore, if "i" and "j" are the two nodes that
4784 * are being merged, then they are taken to depend on each other as well.
4785 * Otherwise, check if there is a (conditional) validity dependence
4786 * from node[j] to node[i], forcing node[i] to follow node[j].
4788 static isl_bool
cluster_follows(int i
, int j
, void *user
)
4790 struct isl_mark_merge_sccs_data
*data
= user
;
4791 struct isl_sched_graph
*graph
= data
->graph
;
4792 int *scc_cluster
= data
->scc_cluster
;
4794 if (data
->src
== i
&& data
->dst
== j
)
4795 return isl_bool_true
;
4796 if (data
->src
== j
&& data
->dst
== i
)
4797 return isl_bool_true
;
4798 if (scc_cluster
[graph
->node
[i
].scc
] == scc_cluster
[graph
->node
[j
].scc
])
4799 return isl_bool_true
;
4801 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
4804 /* Mark all SCCs that belong to either of the two clusters in "c"
4805 * connected by the edge in "graph" with index "edge", or to any
4806 * of the intermediate clusters.
4807 * The marking is recorded in c->scc_in_merge.
4809 * The given edge has been selected for merging two clusters,
4810 * meaning that there is at least a proximity edge between the two nodes.
4811 * However, there may also be (indirect) validity dependences
4812 * between the two nodes. When merging the two clusters, all clusters
4813 * containing one or more of the intermediate nodes along the
4814 * indirect validity dependences need to be merged in as well.
4816 * First collect all such nodes by computing the strongly connected
4817 * component (SCC) containing the two nodes connected by the edge, where
4818 * the two nodes are considered to depend on each other to make
4819 * sure they end up in the same SCC. Similarly, each node is considered
4820 * to depend on every other node in the same cluster to ensure
4821 * that the SCC consists of complete clusters.
4823 * Then the original SCCs that contain any of these nodes are marked
4824 * in c->scc_in_merge.
4826 static isl_stat
mark_merge_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
4827 int edge
, struct isl_clustering
*c
)
4829 struct isl_mark_merge_sccs_data data
;
4830 struct isl_tarjan_graph
*g
;
4833 for (i
= 0; i
< c
->n
; ++i
)
4834 c
->scc_in_merge
[i
] = 0;
4837 data
.scc_cluster
= c
->scc_cluster
;
4838 data
.src
= graph
->edge
[edge
].src
- graph
->node
;
4839 data
.dst
= graph
->edge
[edge
].dst
- graph
->node
;
4841 g
= isl_tarjan_graph_component(ctx
, graph
->n
, data
.dst
,
4842 &cluster_follows
, &data
);
4848 isl_die(ctx
, isl_error_internal
,
4849 "expecting at least two nodes in component",
4851 if (g
->order
[--i
] != -1)
4852 isl_die(ctx
, isl_error_internal
,
4853 "expecting end of component marker", goto error
);
4855 for (--i
; i
>= 0 && g
->order
[i
] != -1; --i
) {
4856 int scc
= graph
->node
[g
->order
[i
]].scc
;
4857 c
->scc_in_merge
[scc
] = 1;
4860 isl_tarjan_graph_free(g
);
4863 isl_tarjan_graph_free(g
);
4864 return isl_stat_error
;
4867 /* Construct the identifier "cluster_i".
4869 static __isl_give isl_id
*cluster_id(isl_ctx
*ctx
, int i
)
4873 snprintf(name
, sizeof(name
), "cluster_%d", i
);
4874 return isl_id_alloc(ctx
, name
, NULL
);
4877 /* Construct the space of the cluster with index "i" containing
4878 * the strongly connected component "scc".
4880 * In particular, construct a space called cluster_i with dimension equal
4881 * to the number of schedule rows in the current band of "scc".
4883 static __isl_give isl_space
*cluster_space(struct isl_sched_graph
*scc
, int i
)
4889 nvar
= scc
->n_total_row
- scc
->band_start
;
4890 space
= isl_space_copy(scc
->node
[0].space
);
4891 space
= isl_space_params(space
);
4892 space
= isl_space_set_from_params(space
);
4893 space
= isl_space_add_dims(space
, isl_dim_set
, nvar
);
4894 id
= cluster_id(isl_space_get_ctx(space
), i
);
4895 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
4900 /* Collect the domain of the graph for merging clusters.
4902 * In particular, for each cluster with first SCC "i", construct
4903 * a set in the space called cluster_i with dimension equal
4904 * to the number of schedule rows in the current band of the cluster.
4906 static __isl_give isl_union_set
*collect_domain(isl_ctx
*ctx
,
4907 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
4911 isl_union_set
*domain
;
4913 space
= isl_space_params_alloc(ctx
, 0);
4914 domain
= isl_union_set_empty(space
);
4916 for (i
= 0; i
< graph
->scc
; ++i
) {
4919 if (!c
->scc_in_merge
[i
])
4921 if (c
->scc_cluster
[i
] != i
)
4923 space
= cluster_space(&c
->scc
[i
], i
);
4924 domain
= isl_union_set_add_set(domain
, isl_set_universe(space
));
4930 /* Construct a map from the original instances to the corresponding
4931 * cluster instance in the current bands of the clusters in "c".
4933 static __isl_give isl_union_map
*collect_cluster_map(isl_ctx
*ctx
,
4934 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
4938 isl_union_map
*cluster_map
;
4940 space
= isl_space_params_alloc(ctx
, 0);
4941 cluster_map
= isl_union_map_empty(space
);
4942 for (i
= 0; i
< graph
->scc
; ++i
) {
4946 if (!c
->scc_in_merge
[i
])
4949 id
= cluster_id(ctx
, c
->scc_cluster
[i
]);
4950 start
= c
->scc
[i
].band_start
;
4951 n
= c
->scc
[i
].n_total_row
- start
;
4952 for (j
= 0; j
< c
->scc
[i
].n
; ++j
) {
4955 struct isl_sched_node
*node
= &c
->scc
[i
].node
[j
];
4957 ma
= node_extract_partial_schedule_multi_aff(node
,
4959 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
,
4961 map
= isl_map_from_multi_aff(ma
);
4962 cluster_map
= isl_union_map_add_map(cluster_map
, map
);
4970 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
4971 * that are not isl_edge_condition or isl_edge_conditional_validity.
4973 static __isl_give isl_schedule_constraints
*add_non_conditional_constraints(
4974 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
4975 __isl_take isl_schedule_constraints
*sc
)
4977 enum isl_edge_type t
;
4982 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
4983 if (t
== isl_edge_condition
||
4984 t
== isl_edge_conditional_validity
)
4986 if (!is_type(edge
, t
))
4988 sc
->constraint
[t
] = isl_union_map_union(sc
->constraint
[t
],
4989 isl_union_map_copy(umap
));
4990 if (!sc
->constraint
[t
])
4991 return isl_schedule_constraints_free(sc
);
4997 /* Add schedule constraints of types isl_edge_condition and
4998 * isl_edge_conditional_validity to "sc" by applying "umap" to
4999 * the domains of the wrapped relations in domain and range
5000 * of the corresponding tagged constraints of "edge".
5002 static __isl_give isl_schedule_constraints
*add_conditional_constraints(
5003 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5004 __isl_take isl_schedule_constraints
*sc
)
5006 enum isl_edge_type t
;
5007 isl_union_map
*tagged
;
5009 for (t
= isl_edge_condition
; t
<= isl_edge_conditional_validity
; ++t
) {
5010 if (!is_type(edge
, t
))
5012 if (t
== isl_edge_condition
)
5013 tagged
= isl_union_map_copy(edge
->tagged_condition
);
5015 tagged
= isl_union_map_copy(edge
->tagged_validity
);
5016 tagged
= isl_union_map_zip(tagged
);
5017 tagged
= isl_union_map_apply_domain(tagged
,
5018 isl_union_map_copy(umap
));
5019 tagged
= isl_union_map_zip(tagged
);
5020 sc
->constraint
[t
] = isl_union_map_union(sc
->constraint
[t
],
5022 if (!sc
->constraint
[t
])
5023 return isl_schedule_constraints_free(sc
);
5029 /* Given a mapping "cluster_map" from the original instances to
5030 * the cluster instances, add schedule constraints on the clusters
5031 * to "sc" corresponding to the original constraints represented by "edge".
5033 * For non-tagged dependence constraints, the cluster constraints
5034 * are obtained by applying "cluster_map" to the edge->map.
5036 * For tagged dependence constraints, "cluster_map" needs to be applied
5037 * to the domains of the wrapped relations in domain and range
5038 * of the tagged dependence constraints. Pick out the mappings
5039 * from these domains from "cluster_map" and construct their product.
5040 * This mapping can then be applied to the pair of domains.
5042 static __isl_give isl_schedule_constraints
*collect_edge_constraints(
5043 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*cluster_map
,
5044 __isl_take isl_schedule_constraints
*sc
)
5046 isl_union_map
*umap
;
5048 isl_union_set
*uset
;
5049 isl_union_map
*umap1
, *umap2
;
5054 umap
= isl_union_map_from_map(isl_map_copy(edge
->map
));
5055 umap
= isl_union_map_apply_domain(umap
,
5056 isl_union_map_copy(cluster_map
));
5057 umap
= isl_union_map_apply_range(umap
,
5058 isl_union_map_copy(cluster_map
));
5059 sc
= add_non_conditional_constraints(edge
, umap
, sc
);
5060 isl_union_map_free(umap
);
5062 if (!sc
|| (!is_condition(edge
) && !is_conditional_validity(edge
)))
5065 space
= isl_space_domain(isl_map_get_space(edge
->map
));
5066 uset
= isl_union_set_from_set(isl_set_universe(space
));
5067 umap1
= isl_union_map_copy(cluster_map
);
5068 umap1
= isl_union_map_intersect_domain(umap1
, uset
);
5069 space
= isl_space_range(isl_map_get_space(edge
->map
));
5070 uset
= isl_union_set_from_set(isl_set_universe(space
));
5071 umap2
= isl_union_map_copy(cluster_map
);
5072 umap2
= isl_union_map_intersect_domain(umap2
, uset
);
5073 umap
= isl_union_map_product(umap1
, umap2
);
5075 sc
= add_conditional_constraints(edge
, umap
, sc
);
5077 isl_union_map_free(umap
);
5081 /* Given a mapping "cluster_map" from the original instances to
5082 * the cluster instances, add schedule constraints on the clusters
5083 * to "sc" corresponding to all edges in "graph" between nodes that
5084 * belong to SCCs that are marked for merging in "scc_in_merge".
5086 static __isl_give isl_schedule_constraints
*collect_constraints(
5087 struct isl_sched_graph
*graph
, int *scc_in_merge
,
5088 __isl_keep isl_union_map
*cluster_map
,
5089 __isl_take isl_schedule_constraints
*sc
)
5093 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5094 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5096 if (!scc_in_merge
[edge
->src
->scc
])
5098 if (!scc_in_merge
[edge
->dst
->scc
])
5100 sc
= collect_edge_constraints(edge
, cluster_map
, sc
);
5106 /* Construct a dependence graph for scheduling clusters with respect
5107 * to each other and store the result in "merge_graph".
5108 * In particular, the nodes of the graph correspond to the schedule
5109 * dimensions of the current bands of those clusters that have been
5110 * marked for merging in "c".
5112 * First construct an isl_schedule_constraints object for this domain
5113 * by transforming the edges in "graph" to the domain.
5114 * Then initialize a dependence graph for scheduling from these
5117 static isl_stat
init_merge_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5118 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
5120 isl_union_set
*domain
;
5121 isl_union_map
*cluster_map
;
5122 isl_schedule_constraints
*sc
;
5125 domain
= collect_domain(ctx
, graph
, c
);
5126 sc
= isl_schedule_constraints_on_domain(domain
);
5128 return isl_stat_error
;
5129 cluster_map
= collect_cluster_map(ctx
, graph
, c
);
5130 sc
= collect_constraints(graph
, c
->scc_in_merge
, cluster_map
, sc
);
5131 isl_union_map_free(cluster_map
);
5133 r
= graph_init(merge_graph
, sc
);
5135 isl_schedule_constraints_free(sc
);
5140 /* Compute the maximal number of remaining schedule rows that still need
5141 * to be computed for the nodes that belong to clusters with the maximal
5142 * dimension for the current band (i.e., the band that is to be merged).
5143 * Only clusters that are about to be merged are considered.
5144 * "maxvar" is the maximal dimension for the current band.
5145 * "c" contains information about the clusters.
5147 * Return the maximal number of remaining schedule rows or -1 on error.
5149 static int compute_maxvar_max_slack(int maxvar
, struct isl_clustering
*c
)
5155 for (i
= 0; i
< c
->n
; ++i
) {
5157 struct isl_sched_graph
*scc
;
5159 if (!c
->scc_in_merge
[i
])
5162 nvar
= scc
->n_total_row
- scc
->band_start
;
5165 for (j
= 0; j
< scc
->n
; ++j
) {
5166 struct isl_sched_node
*node
= &scc
->node
[j
];
5169 if (node_update_cmap(node
) < 0)
5171 slack
= node
->nvar
- node
->rank
;
5172 if (slack
> max_slack
)
5180 /* If there are any clusters where the dimension of the current band
5181 * (i.e., the band that is to be merged) is smaller than "maxvar" and
5182 * if there are any nodes in such a cluster where the number
5183 * of remaining schedule rows that still need to be computed
5184 * is greater than "max_slack", then return the smallest current band
5185 * dimension of all these clusters. Otherwise return the original value
5186 * of "maxvar". Return -1 in case of any error.
5187 * Only clusters that are about to be merged are considered.
5188 * "c" contains information about the clusters.
5190 static int limit_maxvar_to_slack(int maxvar
, int max_slack
,
5191 struct isl_clustering
*c
)
5195 for (i
= 0; i
< c
->n
; ++i
) {
5197 struct isl_sched_graph
*scc
;
5199 if (!c
->scc_in_merge
[i
])
5202 nvar
= scc
->n_total_row
- scc
->band_start
;
5205 for (j
= 0; j
< scc
->n
; ++j
) {
5206 struct isl_sched_node
*node
= &scc
->node
[j
];
5209 if (node_update_cmap(node
) < 0)
5211 slack
= node
->nvar
- node
->rank
;
5212 if (slack
> max_slack
) {
5222 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
5223 * that still need to be computed. In particular, if there is a node
5224 * in a cluster where the dimension of the current band is smaller
5225 * than merge_graph->maxvar, but the number of remaining schedule rows
5226 * is greater than that of any node in a cluster with the maximal
5227 * dimension for the current band (i.e., merge_graph->maxvar),
5228 * then adjust merge_graph->maxvar to the (smallest) current band dimension
5229 * of those clusters. Without this adjustment, the total number of
5230 * schedule dimensions would be increased, resulting in a skewed view
5231 * of the number of coincident dimensions.
5232 * "c" contains information about the clusters.
5234 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
5235 * then there is no point in attempting any merge since it will be rejected
5236 * anyway. Set merge_graph->maxvar to zero in such cases.
5238 static isl_stat
adjust_maxvar_to_slack(isl_ctx
*ctx
,
5239 struct isl_sched_graph
*merge_graph
, struct isl_clustering
*c
)
5241 int max_slack
, maxvar
;
5243 max_slack
= compute_maxvar_max_slack(merge_graph
->maxvar
, c
);
5245 return isl_stat_error
;
5246 maxvar
= limit_maxvar_to_slack(merge_graph
->maxvar
, max_slack
, c
);
5248 return isl_stat_error
;
5250 if (maxvar
< merge_graph
->maxvar
) {
5251 if (isl_options_get_schedule_maximize_band_depth(ctx
))
5252 merge_graph
->maxvar
= 0;
5254 merge_graph
->maxvar
= maxvar
;
5260 /* Return the number of coincident dimensions in the current band of "graph",
5261 * where the nodes of "graph" are assumed to be scheduled by a single band.
5263 static int get_n_coincident(struct isl_sched_graph
*graph
)
5267 for (i
= graph
->band_start
; i
< graph
->n_total_row
; ++i
)
5268 if (!graph
->node
[0].coincident
[i
])
5271 return i
- graph
->band_start
;
5274 /* Should the clusters be merged based on the cluster schedule
5275 * in the current (and only) band of "merge_graph", given that
5276 * coincidence should be maximized?
5278 * If the number of coincident schedule dimensions in the merged band
5279 * would be less than the maximal number of coincident schedule dimensions
5280 * in any of the merged clusters, then the clusters should not be merged.
5282 static isl_bool
ok_to_merge_coincident(struct isl_clustering
*c
,
5283 struct isl_sched_graph
*merge_graph
)
5290 for (i
= 0; i
< c
->n
; ++i
) {
5291 if (!c
->scc_in_merge
[i
])
5293 n_coincident
= get_n_coincident(&c
->scc
[i
]);
5294 if (n_coincident
> max_coincident
)
5295 max_coincident
= n_coincident
;
5298 n_coincident
= get_n_coincident(merge_graph
);
5300 return n_coincident
>= max_coincident
;
5303 /* Return the transformation on "node" expressed by the current (and only)
5304 * band of "merge_graph" applied to the clusters in "c".
5306 * First find the representation of "node" in its SCC in "c" and
5307 * extract the transformation expressed by the current band.
5308 * Then extract the transformation applied by "merge_graph"
5309 * to the cluster to which this SCC belongs.
5310 * Combine the two to obtain the complete transformation on the node.
5312 * Note that the range of the first transformation is an anonymous space,
5313 * while the domain of the second is named "cluster_X". The range
5314 * of the former therefore needs to be adjusted before the two
5317 static __isl_give isl_map
*extract_node_transformation(isl_ctx
*ctx
,
5318 struct isl_sched_node
*node
, struct isl_clustering
*c
,
5319 struct isl_sched_graph
*merge_graph
)
5321 struct isl_sched_node
*scc_node
, *cluster_node
;
5325 isl_multi_aff
*ma
, *ma2
;
5327 scc_node
= graph_find_node(ctx
, &c
->scc
[node
->scc
], node
->space
);
5328 start
= c
->scc
[node
->scc
].band_start
;
5329 n
= c
->scc
[node
->scc
].n_total_row
- start
;
5330 ma
= node_extract_partial_schedule_multi_aff(scc_node
, start
, n
);
5331 space
= cluster_space(&c
->scc
[node
->scc
], c
->scc_cluster
[node
->scc
]);
5332 cluster_node
= graph_find_node(ctx
, merge_graph
, space
);
5333 if (space
&& !cluster_node
)
5334 isl_die(ctx
, isl_error_internal
, "unable to find cluster",
5335 space
= isl_space_free(space
));
5336 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
5337 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
, id
);
5338 isl_space_free(space
);
5339 n
= merge_graph
->n_total_row
;
5340 ma2
= node_extract_partial_schedule_multi_aff(cluster_node
, 0, n
);
5341 ma
= isl_multi_aff_pullback_multi_aff(ma2
, ma
);
5343 return isl_map_from_multi_aff(ma
);
5346 /* Give a set of distances "set", are they bounded by a small constant
5347 * in direction "pos"?
5348 * In practice, check if they are bounded by 2 by checking that there
5349 * are no elements with a value greater than or equal to 3 or
5350 * smaller than or equal to -3.
5352 static isl_bool
distance_is_bounded(__isl_keep isl_set
*set
, int pos
)
5358 return isl_bool_error
;
5360 test
= isl_set_copy(set
);
5361 test
= isl_set_lower_bound_si(test
, isl_dim_set
, pos
, 3);
5362 bounded
= isl_set_is_empty(test
);
5365 if (bounded
< 0 || !bounded
)
5368 test
= isl_set_copy(set
);
5369 test
= isl_set_upper_bound_si(test
, isl_dim_set
, pos
, -3);
5370 bounded
= isl_set_is_empty(test
);
5376 /* Does the set "set" have a fixed (but possible parametric) value
5377 * at dimension "pos"?
5379 static isl_bool
has_single_value(__isl_keep isl_set
*set
, int pos
)
5385 return isl_bool_error
;
5386 set
= isl_set_copy(set
);
5387 n
= isl_set_dim(set
, isl_dim_set
);
5388 set
= isl_set_project_out(set
, isl_dim_set
, pos
+ 1, n
- (pos
+ 1));
5389 set
= isl_set_project_out(set
, isl_dim_set
, 0, pos
);
5390 single
= isl_set_is_singleton(set
);
5396 /* Does "map" have a fixed (but possible parametric) value
5397 * at dimension "pos" of either its domain or its range?
5399 static isl_bool
has_singular_src_or_dst(__isl_keep isl_map
*map
, int pos
)
5404 set
= isl_map_domain(isl_map_copy(map
));
5405 single
= has_single_value(set
, pos
);
5408 if (single
< 0 || single
)
5411 set
= isl_map_range(isl_map_copy(map
));
5412 single
= has_single_value(set
, pos
);
5418 /* Does the edge "edge" from "graph" have bounded dependence distances
5419 * in the merged graph "merge_graph" of a selection of clusters in "c"?
5421 * Extract the complete transformations of the source and destination
5422 * nodes of the edge, apply them to the edge constraints and
5423 * compute the differences. Finally, check if these differences are bounded
5424 * in each direction.
5426 * If the dimension of the band is greater than the number of
5427 * dimensions that can be expected to be optimized by the edge
5428 * (based on its weight), then also allow the differences to be unbounded
5429 * in the remaining dimensions, but only if either the source or
5430 * the destination has a fixed value in that direction.
5431 * This allows a statement that produces values that are used by
5432 * several instance of another statement to be merged with that
5434 * However, merging such clusters will introduce an inherently
5435 * large proximity distance inside the merged cluster, meaning
5436 * that proximity distances will no longer be optimized in
5437 * subsequent merges. These merges are therefore only allowed
5438 * after all other possible merges have been tried.
5439 * The first time such a merge is encountered, the weight of the edge
5440 * is replaced by a negative weight. The second time (i.e., after
5441 * all merges over edges with a non-negative weight have been tried),
5442 * the merge is allowed.
5444 static isl_bool
has_bounded_distances(isl_ctx
*ctx
, struct isl_sched_edge
*edge
,
5445 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
5446 struct isl_sched_graph
*merge_graph
)
5453 map
= isl_map_copy(edge
->map
);
5454 t
= extract_node_transformation(ctx
, edge
->src
, c
, merge_graph
);
5455 map
= isl_map_apply_domain(map
, t
);
5456 t
= extract_node_transformation(ctx
, edge
->dst
, c
, merge_graph
);
5457 map
= isl_map_apply_range(map
, t
);
5458 dist
= isl_map_deltas(isl_map_copy(map
));
5460 bounded
= isl_bool_true
;
5461 n
= isl_set_dim(dist
, isl_dim_set
);
5462 n_slack
= n
- edge
->weight
;
5463 if (edge
->weight
< 0)
5464 n_slack
-= graph
->max_weight
+ 1;
5465 for (i
= 0; i
< n
; ++i
) {
5466 isl_bool bounded_i
, singular_i
;
5468 bounded_i
= distance_is_bounded(dist
, i
);
5473 if (edge
->weight
>= 0)
5474 bounded
= isl_bool_false
;
5478 singular_i
= has_singular_src_or_dst(map
, i
);
5483 bounded
= isl_bool_false
;
5486 if (!bounded
&& i
>= n
&& edge
->weight
>= 0)
5487 edge
->weight
-= graph
->max_weight
+ 1;
5495 return isl_bool_error
;
5498 /* Should the clusters be merged based on the cluster schedule
5499 * in the current (and only) band of "merge_graph"?
5500 * "graph" is the original dependence graph, while "c" records
5501 * which SCCs are involved in the latest merge.
5503 * In particular, is there at least one proximity constraint
5504 * that is optimized by the merge?
5506 * A proximity constraint is considered to be optimized
5507 * if the dependence distances are small.
5509 static isl_bool
ok_to_merge_proximity(isl_ctx
*ctx
,
5510 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
5511 struct isl_sched_graph
*merge_graph
)
5515 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5516 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5519 if (!is_proximity(edge
))
5521 if (!c
->scc_in_merge
[edge
->src
->scc
])
5523 if (!c
->scc_in_merge
[edge
->dst
->scc
])
5525 if (c
->scc_cluster
[edge
->dst
->scc
] ==
5526 c
->scc_cluster
[edge
->src
->scc
])
5528 bounded
= has_bounded_distances(ctx
, edge
, graph
, c
,
5530 if (bounded
< 0 || bounded
)
5534 return isl_bool_false
;
5537 /* Should the clusters be merged based on the cluster schedule
5538 * in the current (and only) band of "merge_graph"?
5539 * "graph" is the original dependence graph, while "c" records
5540 * which SCCs are involved in the latest merge.
5542 * If the current band is empty, then the clusters should not be merged.
5544 * If the band depth should be maximized and the merge schedule
5545 * is incomplete (meaning that the dimension of some of the schedule
5546 * bands in the original schedule will be reduced), then the clusters
5547 * should not be merged.
5549 * If the schedule_maximize_coincidence option is set, then check that
5550 * the number of coincident schedule dimensions is not reduced.
5552 * Finally, only allow the merge if at least one proximity
5553 * constraint is optimized.
5555 static isl_bool
ok_to_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5556 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
5558 if (merge_graph
->n_total_row
== merge_graph
->band_start
)
5559 return isl_bool_false
;
5561 if (isl_options_get_schedule_maximize_band_depth(ctx
) &&
5562 merge_graph
->n_total_row
< merge_graph
->maxvar
)
5563 return isl_bool_false
;
5565 if (isl_options_get_schedule_maximize_coincidence(ctx
)) {
5568 ok
= ok_to_merge_coincident(c
, merge_graph
);
5573 return ok_to_merge_proximity(ctx
, graph
, c
, merge_graph
);
5576 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
5577 * of the schedule in "node" and return the result.
5579 * That is, essentially compute
5581 * T * N(first:first+n-1)
5583 * taking into account the constant term and the parameter coefficients
5586 static __isl_give isl_mat
*node_transformation(isl_ctx
*ctx
,
5587 struct isl_sched_node
*t_node
, struct isl_sched_node
*node
,
5592 int n_row
, n_col
, n_param
, n_var
;
5594 n_param
= node
->nparam
;
5596 n_row
= isl_mat_rows(t_node
->sched
);
5597 n_col
= isl_mat_cols(node
->sched
);
5598 t
= isl_mat_alloc(ctx
, n_row
, n_col
);
5601 for (i
= 0; i
< n_row
; ++i
) {
5602 isl_seq_cpy(t
->row
[i
], t_node
->sched
->row
[i
], 1 + n_param
);
5603 isl_seq_clr(t
->row
[i
] + 1 + n_param
, n_var
);
5604 for (j
= 0; j
< n
; ++j
)
5605 isl_seq_addmul(t
->row
[i
],
5606 t_node
->sched
->row
[i
][1 + n_param
+ j
],
5607 node
->sched
->row
[first
+ j
],
5608 1 + n_param
+ n_var
);
5613 /* Apply the cluster schedule in "t_node" to the current band
5614 * schedule of the nodes in "graph".
5616 * In particular, replace the rows starting at band_start
5617 * by the result of applying the cluster schedule in "t_node"
5618 * to the original rows.
5620 * The coincidence of the schedule is determined by the coincidence
5621 * of the cluster schedule.
5623 static isl_stat
transform(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5624 struct isl_sched_node
*t_node
)
5630 start
= graph
->band_start
;
5631 n
= graph
->n_total_row
- start
;
5633 n_new
= isl_mat_rows(t_node
->sched
);
5634 for (i
= 0; i
< graph
->n
; ++i
) {
5635 struct isl_sched_node
*node
= &graph
->node
[i
];
5638 t
= node_transformation(ctx
, t_node
, node
, start
, n
);
5639 node
->sched
= isl_mat_drop_rows(node
->sched
, start
, n
);
5640 node
->sched
= isl_mat_concat(node
->sched
, t
);
5641 node
->sched_map
= isl_map_free(node
->sched_map
);
5643 return isl_stat_error
;
5644 for (j
= 0; j
< n_new
; ++j
)
5645 node
->coincident
[start
+ j
] = t_node
->coincident
[j
];
5647 graph
->n_total_row
-= n
;
5649 graph
->n_total_row
+= n_new
;
5650 graph
->n_row
+= n_new
;
5655 /* Merge the clusters marked for merging in "c" into a single
5656 * cluster using the cluster schedule in the current band of "merge_graph".
5657 * The representative SCC for the new cluster is the SCC with
5658 * the smallest index.
5660 * The current band schedule of each SCC in the new cluster is obtained
5661 * by applying the schedule of the corresponding original cluster
5662 * to the original band schedule.
5663 * All SCCs in the new cluster have the same number of schedule rows.
5665 static isl_stat
merge(isl_ctx
*ctx
, struct isl_clustering
*c
,
5666 struct isl_sched_graph
*merge_graph
)
5672 for (i
= 0; i
< c
->n
; ++i
) {
5673 struct isl_sched_node
*node
;
5675 if (!c
->scc_in_merge
[i
])
5679 space
= cluster_space(&c
->scc
[i
], c
->scc_cluster
[i
]);
5681 return isl_stat_error
;
5682 node
= graph_find_node(ctx
, merge_graph
, space
);
5683 isl_space_free(space
);
5685 isl_die(ctx
, isl_error_internal
,
5686 "unable to find cluster",
5687 return isl_stat_error
);
5688 if (transform(ctx
, &c
->scc
[i
], node
) < 0)
5689 return isl_stat_error
;
5690 c
->scc_cluster
[i
] = cluster
;
5696 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
5697 * by scheduling the current cluster bands with respect to each other.
5699 * Construct a dependence graph with a space for each cluster and
5700 * with the coordinates of each space corresponding to the schedule
5701 * dimensions of the current band of that cluster.
5702 * Construct a cluster schedule in this cluster dependence graph and
5703 * apply it to the current cluster bands if it is applicable
5704 * according to ok_to_merge.
5706 * If the number of remaining schedule dimensions in a cluster
5707 * with a non-maximal current schedule dimension is greater than
5708 * the number of remaining schedule dimensions in clusters
5709 * with a maximal current schedule dimension, then restrict
5710 * the number of rows to be computed in the cluster schedule
5711 * to the minimal such non-maximal current schedule dimension.
5712 * Do this by adjusting merge_graph.maxvar.
5714 * Return isl_bool_true if the clusters have effectively been merged
5715 * into a single cluster.
5717 * Note that since the standard scheduling algorithm minimizes the maximal
5718 * distance over proximity constraints, the proximity constraints between
5719 * the merged clusters may not be optimized any further than what is
5720 * sufficient to bring the distances within the limits of the internal
5721 * proximity constraints inside the individual clusters.
5722 * It may therefore make sense to perform an additional translation step
5723 * to bring the clusters closer to each other, while maintaining
5724 * the linear part of the merging schedule found using the standard
5725 * scheduling algorithm.
5727 static isl_bool
try_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5728 struct isl_clustering
*c
)
5730 struct isl_sched_graph merge_graph
= { 0 };
5733 if (init_merge_graph(ctx
, graph
, c
, &merge_graph
) < 0)
5736 if (compute_maxvar(&merge_graph
) < 0)
5738 if (adjust_maxvar_to_slack(ctx
, &merge_graph
,c
) < 0)
5740 if (compute_schedule_wcc_band(ctx
, &merge_graph
) < 0)
5742 merged
= ok_to_merge(ctx
, graph
, c
, &merge_graph
);
5743 if (merged
&& merge(ctx
, c
, &merge_graph
) < 0)
5746 graph_free(ctx
, &merge_graph
);
5749 graph_free(ctx
, &merge_graph
);
5750 return isl_bool_error
;
5753 /* Is there any edge marked "no_merge" between two SCCs that are
5754 * about to be merged (i.e., that are set in "scc_in_merge")?
5755 * "merge_edge" is the proximity edge along which the clusters of SCCs
5756 * are going to be merged.
5758 * If there is any edge between two SCCs with a negative weight,
5759 * while the weight of "merge_edge" is non-negative, then this
5760 * means that the edge was postponed. "merge_edge" should then
5761 * also be postponed since merging along the edge with negative weight should
5762 * be postponed until all edges with non-negative weight have been tried.
5763 * Replace the weight of "merge_edge" by a negative weight as well and
5764 * tell the caller not to attempt a merge.
5766 static int any_no_merge(struct isl_sched_graph
*graph
, int *scc_in_merge
,
5767 struct isl_sched_edge
*merge_edge
)
5771 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5772 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5774 if (!scc_in_merge
[edge
->src
->scc
])
5776 if (!scc_in_merge
[edge
->dst
->scc
])
5780 if (merge_edge
->weight
>= 0 && edge
->weight
< 0) {
5781 merge_edge
->weight
-= graph
->max_weight
+ 1;
5789 /* Merge the two clusters in "c" connected by the edge in "graph"
5790 * with index "edge" into a single cluster.
5791 * If it turns out to be impossible to merge these two clusters,
5792 * then mark the edge as "no_merge" such that it will not be
5795 * First mark all SCCs that need to be merged. This includes the SCCs
5796 * in the two clusters, but it may also include the SCCs
5797 * of intermediate clusters.
5798 * If there is already a no_merge edge between any pair of such SCCs,
5799 * then simply mark the current edge as no_merge as well.
5800 * Likewise, if any of those edges was postponed by has_bounded_distances,
5801 * then postpone the current edge as well.
5802 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
5803 * if the clusters did not end up getting merged, unless the non-merge
5804 * is due to the fact that the edge was postponed. This postponement
5805 * can be recognized by a change in weight (from non-negative to negative).
5807 static isl_stat
merge_clusters_along_edge(isl_ctx
*ctx
,
5808 struct isl_sched_graph
*graph
, int edge
, struct isl_clustering
*c
)
5811 int edge_weight
= graph
->edge
[edge
].weight
;
5813 if (mark_merge_sccs(ctx
, graph
, edge
, c
) < 0)
5814 return isl_stat_error
;
5816 if (any_no_merge(graph
, c
->scc_in_merge
, &graph
->edge
[edge
]))
5817 merged
= isl_bool_false
;
5819 merged
= try_merge(ctx
, graph
, c
);
5821 return isl_stat_error
;
5822 if (!merged
&& edge_weight
== graph
->edge
[edge
].weight
)
5823 graph
->edge
[edge
].no_merge
= 1;
5828 /* Does "node" belong to the cluster identified by "cluster"?
5830 static int node_cluster_exactly(struct isl_sched_node
*node
, int cluster
)
5832 return node
->cluster
== cluster
;
5835 /* Does "edge" connect two nodes belonging to the cluster
5836 * identified by "cluster"?
5838 static int edge_cluster_exactly(struct isl_sched_edge
*edge
, int cluster
)
5840 return edge
->src
->cluster
== cluster
&& edge
->dst
->cluster
== cluster
;
5843 /* Swap the schedule of "node1" and "node2".
5844 * Both nodes have been derived from the same node in a common parent graph.
5845 * Since the "coincident" field is shared with that node
5846 * in the parent graph, there is no need to also swap this field.
5848 static void swap_sched(struct isl_sched_node
*node1
,
5849 struct isl_sched_node
*node2
)
5854 sched
= node1
->sched
;
5855 node1
->sched
= node2
->sched
;
5856 node2
->sched
= sched
;
5858 sched_map
= node1
->sched_map
;
5859 node1
->sched_map
= node2
->sched_map
;
5860 node2
->sched_map
= sched_map
;
5863 /* Copy the current band schedule from the SCCs that form the cluster
5864 * with index "pos" to the actual cluster at position "pos".
5865 * By construction, the index of the first SCC that belongs to the cluster
5868 * The order of the nodes inside both the SCCs and the cluster
5869 * is assumed to be same as the order in the original "graph".
5871 * Since the SCC graphs will no longer be used after this function,
5872 * the schedules are actually swapped rather than copied.
5874 static isl_stat
copy_partial(struct isl_sched_graph
*graph
,
5875 struct isl_clustering
*c
, int pos
)
5879 c
->cluster
[pos
].n_total_row
= c
->scc
[pos
].n_total_row
;
5880 c
->cluster
[pos
].n_row
= c
->scc
[pos
].n_row
;
5881 c
->cluster
[pos
].maxvar
= c
->scc
[pos
].maxvar
;
5883 for (i
= 0; i
< graph
->n
; ++i
) {
5887 if (graph
->node
[i
].cluster
!= pos
)
5889 s
= graph
->node
[i
].scc
;
5890 k
= c
->scc_node
[s
]++;
5891 swap_sched(&c
->cluster
[pos
].node
[j
], &c
->scc
[s
].node
[k
]);
5892 if (c
->scc
[s
].maxvar
> c
->cluster
[pos
].maxvar
)
5893 c
->cluster
[pos
].maxvar
= c
->scc
[s
].maxvar
;
5900 /* Is there a (conditional) validity dependence from node[j] to node[i],
5901 * forcing node[i] to follow node[j] or do the nodes belong to the same
5904 static isl_bool
node_follows_strong_or_same_cluster(int i
, int j
, void *user
)
5906 struct isl_sched_graph
*graph
= user
;
5908 if (graph
->node
[i
].cluster
== graph
->node
[j
].cluster
)
5909 return isl_bool_true
;
5910 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
5913 /* Extract the merged clusters of SCCs in "graph", sort them, and
5914 * store them in c->clusters. Update c->scc_cluster accordingly.
5916 * First keep track of the cluster containing the SCC to which a node
5917 * belongs in the node itself.
5918 * Then extract the clusters into c->clusters, copying the current
5919 * band schedule from the SCCs that belong to the cluster.
5920 * Do this only once per cluster.
5922 * Finally, topologically sort the clusters and update c->scc_cluster
5923 * to match the new scc numbering. While the SCCs were originally
5924 * sorted already, some SCCs that depend on some other SCCs may
5925 * have been merged with SCCs that appear before these other SCCs.
5926 * A reordering may therefore be required.
5928 static isl_stat
extract_clusters(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5929 struct isl_clustering
*c
)
5933 for (i
= 0; i
< graph
->n
; ++i
)
5934 graph
->node
[i
].cluster
= c
->scc_cluster
[graph
->node
[i
].scc
];
5936 for (i
= 0; i
< graph
->scc
; ++i
) {
5937 if (c
->scc_cluster
[i
] != i
)
5939 if (extract_sub_graph(ctx
, graph
, &node_cluster_exactly
,
5940 &edge_cluster_exactly
, i
, &c
->cluster
[i
]) < 0)
5941 return isl_stat_error
;
5942 c
->cluster
[i
].src_scc
= -1;
5943 c
->cluster
[i
].dst_scc
= -1;
5944 if (copy_partial(graph
, c
, i
) < 0)
5945 return isl_stat_error
;
5948 if (detect_ccs(ctx
, graph
, &node_follows_strong_or_same_cluster
) < 0)
5949 return isl_stat_error
;
5950 for (i
= 0; i
< graph
->n
; ++i
)
5951 c
->scc_cluster
[graph
->node
[i
].scc
] = graph
->node
[i
].cluster
;
5956 /* Compute weights on the proximity edges of "graph" that can
5957 * be used by find_proximity to find the most appropriate
5958 * proximity edge to use to merge two clusters in "c".
5959 * The weights are also used by has_bounded_distances to determine
5960 * whether the merge should be allowed.
5961 * Store the maximum of the computed weights in graph->max_weight.
5963 * The computed weight is a measure for the number of remaining schedule
5964 * dimensions that can still be completely aligned.
5965 * In particular, compute the number of equalities between
5966 * input dimensions and output dimensions in the proximity constraints.
5967 * The directions that are already handled by outer schedule bands
5968 * are projected out prior to determining this number.
5970 * Edges that will never be considered by find_proximity are ignored.
5972 static isl_stat
compute_weights(struct isl_sched_graph
*graph
,
5973 struct isl_clustering
*c
)
5977 graph
->max_weight
= 0;
5979 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5980 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5981 struct isl_sched_node
*src
= edge
->src
;
5982 struct isl_sched_node
*dst
= edge
->dst
;
5983 isl_basic_map
*hull
;
5986 if (!is_proximity(edge
))
5988 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
5989 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
5991 if (c
->scc_cluster
[edge
->dst
->scc
] ==
5992 c
->scc_cluster
[edge
->src
->scc
])
5995 hull
= isl_map_affine_hull(isl_map_copy(edge
->map
));
5996 hull
= isl_basic_map_transform_dims(hull
, isl_dim_in
, 0,
5997 isl_mat_copy(src
->ctrans
));
5998 hull
= isl_basic_map_transform_dims(hull
, isl_dim_out
, 0,
5999 isl_mat_copy(dst
->ctrans
));
6000 hull
= isl_basic_map_project_out(hull
,
6001 isl_dim_in
, 0, src
->rank
);
6002 hull
= isl_basic_map_project_out(hull
,
6003 isl_dim_out
, 0, dst
->rank
);
6004 hull
= isl_basic_map_remove_divs(hull
);
6005 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
6006 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
6007 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6008 isl_dim_in
, 0, n_in
);
6009 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6010 isl_dim_out
, 0, n_out
);
6012 return isl_stat_error
;
6013 edge
->weight
= hull
->n_eq
;
6014 isl_basic_map_free(hull
);
6016 if (edge
->weight
> graph
->max_weight
)
6017 graph
->max_weight
= edge
->weight
;
6023 /* Call compute_schedule_finish_band on each of the clusters in "c"
6024 * in their topological order. This order is determined by the scc
6025 * fields of the nodes in "graph".
6026 * Combine the results in a sequence expressing the topological order.
6028 * If there is only one cluster left, then there is no need to introduce
6029 * a sequence node. Also, in this case, the cluster necessarily contains
6030 * the SCC at position 0 in the original graph and is therefore also
6031 * stored in the first cluster of "c".
6033 static __isl_give isl_schedule_node
*finish_bands_clustering(
6034 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6035 struct isl_clustering
*c
)
6039 isl_union_set_list
*filters
;
6041 if (graph
->scc
== 1)
6042 return compute_schedule_finish_band(node
, &c
->cluster
[0], 0);
6044 ctx
= isl_schedule_node_get_ctx(node
);
6046 filters
= extract_sccs(ctx
, graph
);
6047 node
= isl_schedule_node_insert_sequence(node
, filters
);
6049 for (i
= 0; i
< graph
->scc
; ++i
) {
6050 int j
= c
->scc_cluster
[i
];
6051 node
= isl_schedule_node_child(node
, i
);
6052 node
= isl_schedule_node_child(node
, 0);
6053 node
= compute_schedule_finish_band(node
, &c
->cluster
[j
], 0);
6054 node
= isl_schedule_node_parent(node
);
6055 node
= isl_schedule_node_parent(node
);
6061 /* Compute a schedule for a connected dependence graph by first considering
6062 * each strongly connected component (SCC) in the graph separately and then
6063 * incrementally combining them into clusters.
6064 * Return the updated schedule node.
6066 * Initially, each cluster consists of a single SCC, each with its
6067 * own band schedule. The algorithm then tries to merge pairs
6068 * of clusters along a proximity edge until no more suitable
6069 * proximity edges can be found. During this merging, the schedule
6070 * is maintained in the individual SCCs.
6071 * After the merging is completed, the full resulting clusters
6072 * are extracted and in finish_bands_clustering,
6073 * compute_schedule_finish_band is called on each of them to integrate
6074 * the band into "node" and to continue the computation.
6076 * compute_weights initializes the weights that are used by find_proximity.
6078 static __isl_give isl_schedule_node
*compute_schedule_wcc_clustering(
6079 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6082 struct isl_clustering c
;
6085 ctx
= isl_schedule_node_get_ctx(node
);
6087 if (clustering_init(ctx
, &c
, graph
) < 0)
6090 if (compute_weights(graph
, &c
) < 0)
6094 i
= find_proximity(graph
, &c
);
6097 if (i
>= graph
->n_edge
)
6099 if (merge_clusters_along_edge(ctx
, graph
, i
, &c
) < 0)
6103 if (extract_clusters(ctx
, graph
, &c
) < 0)
6106 node
= finish_bands_clustering(node
, graph
, &c
);
6108 clustering_free(ctx
, &c
);
6111 clustering_free(ctx
, &c
);
6112 return isl_schedule_node_free(node
);
6115 /* Compute a schedule for a connected dependence graph and return
6116 * the updated schedule node.
6118 * If Feautrier's algorithm is selected, we first recursively try to satisfy
6119 * as many validity dependences as possible. When all validity dependences
6120 * are satisfied we extend the schedule to a full-dimensional schedule.
6122 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
6123 * depending on whether the user has selected the option to try and
6124 * compute a schedule for the entire (weakly connected) component first.
6125 * If there is only a single strongly connected component (SCC), then
6126 * there is no point in trying to combine SCCs
6127 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
6128 * is called instead.
6130 static __isl_give isl_schedule_node
*compute_schedule_wcc(
6131 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6138 ctx
= isl_schedule_node_get_ctx(node
);
6139 if (detect_sccs(ctx
, graph
) < 0)
6140 return isl_schedule_node_free(node
);
6142 if (compute_maxvar(graph
) < 0)
6143 return isl_schedule_node_free(node
);
6145 if (need_feautrier_step(ctx
, graph
))
6146 return compute_schedule_wcc_feautrier(node
, graph
);
6148 if (graph
->scc
<= 1 || isl_options_get_schedule_whole_component(ctx
))
6149 return compute_schedule_wcc_whole(node
, graph
);
6151 return compute_schedule_wcc_clustering(node
, graph
);
6154 /* Compute a schedule for each group of nodes identified by node->scc
6155 * separately and then combine them in a sequence node (or as set node
6156 * if graph->weak is set) inserted at position "node" of the schedule tree.
6157 * Return the updated schedule node.
6159 * If "wcc" is set then each of the groups belongs to a single
6160 * weakly connected component in the dependence graph so that
6161 * there is no need for compute_sub_schedule to look for weakly
6162 * connected components.
6164 static __isl_give isl_schedule_node
*compute_component_schedule(
6165 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6170 isl_union_set_list
*filters
;
6174 ctx
= isl_schedule_node_get_ctx(node
);
6176 filters
= extract_sccs(ctx
, graph
);
6178 node
= isl_schedule_node_insert_set(node
, filters
);
6180 node
= isl_schedule_node_insert_sequence(node
, filters
);
6182 for (component
= 0; component
< graph
->scc
; ++component
) {
6183 node
= isl_schedule_node_child(node
, component
);
6184 node
= isl_schedule_node_child(node
, 0);
6185 node
= compute_sub_schedule(node
, ctx
, graph
,
6187 &edge_scc_exactly
, component
, wcc
);
6188 node
= isl_schedule_node_parent(node
);
6189 node
= isl_schedule_node_parent(node
);
6195 /* Compute a schedule for the given dependence graph and insert it at "node".
6196 * Return the updated schedule node.
6198 * We first check if the graph is connected (through validity and conditional
6199 * validity dependences) and, if not, compute a schedule
6200 * for each component separately.
6201 * If the schedule_serialize_sccs option is set, then we check for strongly
6202 * connected components instead and compute a separate schedule for
6203 * each such strongly connected component.
6205 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
6206 struct isl_sched_graph
*graph
)
6213 ctx
= isl_schedule_node_get_ctx(node
);
6214 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
6215 if (detect_sccs(ctx
, graph
) < 0)
6216 return isl_schedule_node_free(node
);
6218 if (detect_wccs(ctx
, graph
) < 0)
6219 return isl_schedule_node_free(node
);
6223 return compute_component_schedule(node
, graph
, 1);
6225 return compute_schedule_wcc(node
, graph
);
6228 /* Compute a schedule on sc->domain that respects the given schedule
6231 * In particular, the schedule respects all the validity dependences.
6232 * If the default isl scheduling algorithm is used, it tries to minimize
6233 * the dependence distances over the proximity dependences.
6234 * If Feautrier's scheduling algorithm is used, the proximity dependence
6235 * distances are only minimized during the extension to a full-dimensional
6238 * If there are any condition and conditional validity dependences,
6239 * then the conditional validity dependences may be violated inside
6240 * a tilable band, provided they have no adjacent non-local
6241 * condition dependences.
6243 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
6244 __isl_take isl_schedule_constraints
*sc
)
6246 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
6247 struct isl_sched_graph graph
= { 0 };
6248 isl_schedule
*sched
;
6249 isl_schedule_node
*node
;
6250 isl_union_set
*domain
;
6252 sc
= isl_schedule_constraints_align_params(sc
);
6254 domain
= isl_schedule_constraints_get_domain(sc
);
6255 if (isl_union_set_n_set(domain
) == 0) {
6256 isl_schedule_constraints_free(sc
);
6257 return isl_schedule_from_domain(domain
);
6260 if (graph_init(&graph
, sc
) < 0)
6261 domain
= isl_union_set_free(domain
);
6263 node
= isl_schedule_node_from_domain(domain
);
6264 node
= isl_schedule_node_child(node
, 0);
6266 node
= compute_schedule(node
, &graph
);
6267 sched
= isl_schedule_node_get_schedule(node
);
6268 isl_schedule_node_free(node
);
6270 graph_free(ctx
, &graph
);
6271 isl_schedule_constraints_free(sc
);
6276 /* Compute a schedule for the given union of domains that respects
6277 * all the validity dependences and minimizes
6278 * the dependence distances over the proximity dependences.
6280 * This function is kept for backward compatibility.
6282 __isl_give isl_schedule
*isl_union_set_compute_schedule(
6283 __isl_take isl_union_set
*domain
,
6284 __isl_take isl_union_map
*validity
,
6285 __isl_take isl_union_map
*proximity
)
6287 isl_schedule_constraints
*sc
;
6289 sc
= isl_schedule_constraints_on_domain(domain
);
6290 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
6291 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
6293 return isl_schedule_constraints_compute_schedule(sc
);