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>
35 #include <isl_val_private.h>
38 * The scheduling algorithm implemented in this file was inspired by
39 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
40 * Parallelization and Locality Optimization in the Polyhedral Model".
44 isl_edge_validity
= 0,
45 isl_edge_first
= isl_edge_validity
,
48 isl_edge_conditional_validity
,
50 isl_edge_last
= isl_edge_proximity
,
54 /* The constraints that need to be satisfied by a schedule on "domain".
56 * "context" specifies extra constraints on the parameters.
58 * "validity" constraints map domain elements i to domain elements
59 * that should be scheduled after i. (Hard constraint)
60 * "proximity" constraints map domain elements i to domains elements
61 * that should be scheduled as early as possible after i (or before i).
64 * "condition" and "conditional_validity" constraints map possibly "tagged"
65 * domain elements i -> s to "tagged" domain elements j -> t.
66 * The elements of the "conditional_validity" constraints, but without the
67 * tags (i.e., the elements i -> j) are treated as validity constraints,
68 * except that during the construction of a tilable band,
69 * the elements of the "conditional_validity" constraints may be violated
70 * provided that all adjacent elements of the "condition" constraints
71 * are local within the band.
72 * A dependence is local within a band if domain and range are mapped
73 * to the same schedule point by the band.
75 struct isl_schedule_constraints
{
76 isl_union_set
*domain
;
79 isl_union_map
*constraint
[isl_edge_last
+ 1];
82 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
83 __isl_keep isl_schedule_constraints
*sc
)
86 isl_schedule_constraints
*sc_copy
;
89 ctx
= isl_union_set_get_ctx(sc
->domain
);
90 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
94 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
95 sc_copy
->context
= isl_set_copy(sc
->context
);
96 if (!sc_copy
->domain
|| !sc_copy
->context
)
97 return isl_schedule_constraints_free(sc_copy
);
99 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
100 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
101 if (!sc_copy
->constraint
[i
])
102 return isl_schedule_constraints_free(sc_copy
);
109 /* Construct an isl_schedule_constraints object for computing a schedule
110 * on "domain". The initial object does not impose any constraints.
112 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
113 __isl_take isl_union_set
*domain
)
117 isl_schedule_constraints
*sc
;
118 isl_union_map
*empty
;
119 enum isl_edge_type i
;
124 ctx
= isl_union_set_get_ctx(domain
);
125 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
129 space
= isl_union_set_get_space(domain
);
131 sc
->context
= isl_set_universe(isl_space_copy(space
));
132 empty
= isl_union_map_empty(space
);
133 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
134 sc
->constraint
[i
] = isl_union_map_copy(empty
);
135 if (!sc
->constraint
[i
])
136 sc
->domain
= isl_union_set_free(sc
->domain
);
138 isl_union_map_free(empty
);
140 if (!sc
->domain
|| !sc
->context
)
141 return isl_schedule_constraints_free(sc
);
145 isl_union_set_free(domain
);
149 /* Replace the context of "sc" by "context".
151 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_context(
152 __isl_take isl_schedule_constraints
*sc
, __isl_take isl_set
*context
)
157 isl_set_free(sc
->context
);
158 sc
->context
= context
;
162 isl_schedule_constraints_free(sc
);
163 isl_set_free(context
);
167 /* Replace the validity constraints of "sc" by "validity".
169 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
170 __isl_take isl_schedule_constraints
*sc
,
171 __isl_take isl_union_map
*validity
)
173 if (!sc
|| !validity
)
176 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
177 sc
->constraint
[isl_edge_validity
] = validity
;
181 isl_schedule_constraints_free(sc
);
182 isl_union_map_free(validity
);
186 /* Replace the coincidence constraints of "sc" by "coincidence".
188 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
189 __isl_take isl_schedule_constraints
*sc
,
190 __isl_take isl_union_map
*coincidence
)
192 if (!sc
|| !coincidence
)
195 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
196 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
200 isl_schedule_constraints_free(sc
);
201 isl_union_map_free(coincidence
);
205 /* Replace the proximity constraints of "sc" by "proximity".
207 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
208 __isl_take isl_schedule_constraints
*sc
,
209 __isl_take isl_union_map
*proximity
)
211 if (!sc
|| !proximity
)
214 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
215 sc
->constraint
[isl_edge_proximity
] = proximity
;
219 isl_schedule_constraints_free(sc
);
220 isl_union_map_free(proximity
);
224 /* Replace the conditional validity constraints of "sc" by "condition"
227 __isl_give isl_schedule_constraints
*
228 isl_schedule_constraints_set_conditional_validity(
229 __isl_take isl_schedule_constraints
*sc
,
230 __isl_take isl_union_map
*condition
,
231 __isl_take isl_union_map
*validity
)
233 if (!sc
|| !condition
|| !validity
)
236 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
237 sc
->constraint
[isl_edge_condition
] = condition
;
238 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
239 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
243 isl_schedule_constraints_free(sc
);
244 isl_union_map_free(condition
);
245 isl_union_map_free(validity
);
249 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
250 __isl_take isl_schedule_constraints
*sc
)
252 enum isl_edge_type i
;
257 isl_union_set_free(sc
->domain
);
258 isl_set_free(sc
->context
);
259 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
260 isl_union_map_free(sc
->constraint
[i
]);
267 isl_ctx
*isl_schedule_constraints_get_ctx(
268 __isl_keep isl_schedule_constraints
*sc
)
270 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
273 /* Return the domain of "sc".
275 __isl_give isl_union_set
*isl_schedule_constraints_get_domain(
276 __isl_keep isl_schedule_constraints
*sc
)
281 return isl_union_set_copy(sc
->domain
);
284 /* Return the context of "sc".
286 __isl_give isl_set
*isl_schedule_constraints_get_context(
287 __isl_keep isl_schedule_constraints
*sc
)
292 return isl_set_copy(sc
->context
);
295 /* Return the validity constraints of "sc".
297 __isl_give isl_union_map
*isl_schedule_constraints_get_validity(
298 __isl_keep isl_schedule_constraints
*sc
)
303 return isl_union_map_copy(sc
->constraint
[isl_edge_validity
]);
306 /* Return the coincidence constraints of "sc".
308 __isl_give isl_union_map
*isl_schedule_constraints_get_coincidence(
309 __isl_keep isl_schedule_constraints
*sc
)
314 return isl_union_map_copy(sc
->constraint
[isl_edge_coincidence
]);
317 /* Return the proximity constraints of "sc".
319 __isl_give isl_union_map
*isl_schedule_constraints_get_proximity(
320 __isl_keep isl_schedule_constraints
*sc
)
325 return isl_union_map_copy(sc
->constraint
[isl_edge_proximity
]);
328 /* Return the conditional validity constraints of "sc".
330 __isl_give isl_union_map
*isl_schedule_constraints_get_conditional_validity(
331 __isl_keep isl_schedule_constraints
*sc
)
337 isl_union_map_copy(sc
->constraint
[isl_edge_conditional_validity
]);
340 /* Return the conditions for the conditional validity constraints of "sc".
342 __isl_give isl_union_map
*
343 isl_schedule_constraints_get_conditional_validity_condition(
344 __isl_keep isl_schedule_constraints
*sc
)
349 return isl_union_map_copy(sc
->constraint
[isl_edge_condition
]);
352 /* Can a schedule constraint of type "type" be tagged?
354 static int may_be_tagged(enum isl_edge_type type
)
356 if (type
== isl_edge_condition
|| type
== isl_edge_conditional_validity
)
361 /* Apply "umap" to the domains of the wrapped relations
362 * inside the domain and range of "c".
364 * That is, for each map of the form
366 * [D -> S] -> [E -> T]
368 * in "c", apply "umap" to D and E.
370 * D is exposed by currying the relation to
372 * D -> [S -> [E -> T]]
374 * E is exposed by doing the same to the inverse of "c".
376 static __isl_give isl_union_map
*apply_factor_domain(
377 __isl_take isl_union_map
*c
, __isl_keep isl_union_map
*umap
)
379 c
= isl_union_map_curry(c
);
380 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
381 c
= isl_union_map_uncurry(c
);
383 c
= isl_union_map_reverse(c
);
384 c
= isl_union_map_curry(c
);
385 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
386 c
= isl_union_map_uncurry(c
);
387 c
= isl_union_map_reverse(c
);
392 /* Apply "umap" to domain and range of "c".
393 * If "tag" is set, then "c" may contain tags and then "umap"
394 * needs to be applied to the domains of the wrapped relations
395 * inside the domain and range of "c".
397 static __isl_give isl_union_map
*apply(__isl_take isl_union_map
*c
,
398 __isl_keep isl_union_map
*umap
, int tag
)
403 t
= isl_union_map_copy(c
);
404 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
405 c
= isl_union_map_apply_range(c
, isl_union_map_copy(umap
));
408 t
= apply_factor_domain(t
, umap
);
409 c
= isl_union_map_union(c
, t
);
413 /* Apply "umap" to the domain of the schedule constraints "sc".
415 * The two sides of the various schedule constraints are adjusted
418 __isl_give isl_schedule_constraints
*isl_schedule_constraints_apply(
419 __isl_take isl_schedule_constraints
*sc
,
420 __isl_take isl_union_map
*umap
)
422 enum isl_edge_type i
;
427 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
428 int tag
= may_be_tagged(i
);
430 sc
->constraint
[i
] = apply(sc
->constraint
[i
], umap
, tag
);
431 if (!sc
->constraint
[i
])
434 sc
->domain
= isl_union_set_apply(sc
->domain
, umap
);
436 return isl_schedule_constraints_free(sc
);
440 isl_schedule_constraints_free(sc
);
441 isl_union_map_free(umap
);
445 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
450 fprintf(stderr
, "domain: ");
451 isl_union_set_dump(sc
->domain
);
452 fprintf(stderr
, "context: ");
453 isl_set_dump(sc
->context
);
454 fprintf(stderr
, "validity: ");
455 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
456 fprintf(stderr
, "proximity: ");
457 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
458 fprintf(stderr
, "coincidence: ");
459 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
460 fprintf(stderr
, "condition: ");
461 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
462 fprintf(stderr
, "conditional_validity: ");
463 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
466 /* Align the parameters of the fields of "sc".
468 static __isl_give isl_schedule_constraints
*
469 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
472 enum isl_edge_type i
;
477 space
= isl_union_set_get_space(sc
->domain
);
478 space
= isl_space_align_params(space
, isl_set_get_space(sc
->context
));
479 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
480 space
= isl_space_align_params(space
,
481 isl_union_map_get_space(sc
->constraint
[i
]));
483 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
484 sc
->constraint
[i
] = isl_union_map_align_params(
485 sc
->constraint
[i
], isl_space_copy(space
));
486 if (!sc
->constraint
[i
])
487 space
= isl_space_free(space
);
489 sc
->context
= isl_set_align_params(sc
->context
, isl_space_copy(space
));
490 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
491 if (!sc
->context
|| !sc
->domain
)
492 return isl_schedule_constraints_free(sc
);
497 /* Add the number of basic maps in "map" to *n.
499 static isl_stat
add_n_basic_map(__isl_take isl_map
*map
, void *user
)
503 *n
+= isl_map_n_basic_map(map
);
509 /* Return the total number of isl_basic_maps in the constraints of "sc".
510 * Return -1 on error.
512 static int isl_schedule_constraints_n_basic_map(
513 __isl_keep isl_schedule_constraints
*sc
)
515 enum isl_edge_type i
;
520 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
521 if (isl_union_map_foreach_map(sc
->constraint
[i
],
522 &add_n_basic_map
, &n
) < 0)
528 /* Return the total number of isl_maps in the constraints of "sc".
530 static int isl_schedule_constraints_n_map(
531 __isl_keep isl_schedule_constraints
*sc
)
533 enum isl_edge_type i
;
536 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
537 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
542 /* Internal information about a node that is used during the construction
544 * space represents the space in which the domain lives
545 * sched is a matrix representation of the schedule being constructed
546 * for this node; if compressed is set, then this schedule is
547 * defined over the compressed domain space
548 * sched_map is an isl_map representation of the same (partial) schedule
549 * sched_map may be NULL; if compressed is set, then this map
550 * is defined over the uncompressed domain space
551 * rank is the number of linearly independent rows in the linear part
553 * the columns of cmap represent a change of basis for the schedule
554 * coefficients; the first rank columns span the linear part of
556 * cinv is the inverse of cmap.
557 * ctrans is the transpose of cmap.
558 * start is the first variable in the LP problem in the sequences that
559 * represents the schedule coefficients of this node
560 * nvar is the dimension of the domain
561 * nparam is the number of parameters or 0 if we are not constructing
562 * a parametric schedule
564 * If compressed is set, then hull represents the constraints
565 * that were used to derive the compression, while compress and
566 * decompress map the original space to the compressed space and
569 * scc is the index of SCC (or WCC) this node belongs to
571 * "cluster" is only used inside extract_clusters and identifies
572 * the cluster of SCCs that the node belongs to.
574 * coincident contains a boolean for each of the rows of the schedule,
575 * indicating whether the corresponding scheduling dimension satisfies
576 * the coincidence constraints in the sense that the corresponding
577 * dependence distances are zero.
579 * If the schedule_treat_coalescing option is set, then
580 * "sizes" contains the sizes of the (compressed) instance set
581 * in each direction. If there is no fixed size in a given direction,
582 * then the corresponding size value is set to infinity.
583 * If the schedule_treat_coalescing option or the schedule_max_coefficient
584 * option is set, then "max" contains the maximal values for
585 * schedule coefficients of the (compressed) variables. If no bound
586 * needs to be imposed on a particular variable, then the corresponding
589 struct isl_sched_node
{
593 isl_multi_aff
*compress
;
594 isl_multi_aff
*decompress
;
610 isl_multi_val
*sizes
;
614 static int node_has_space(const void *entry
, const void *val
)
616 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
617 isl_space
*dim
= (isl_space
*)val
;
619 return isl_space_is_equal(node
->space
, dim
);
622 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
624 return node
->scc
== scc
;
627 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
629 return node
->scc
<= scc
;
632 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
634 return node
->scc
>= scc
;
637 /* An edge in the dependence graph. An edge may be used to
638 * ensure validity of the generated schedule, to minimize the dependence
641 * map is the dependence relation, with i -> j in the map if j depends on i
642 * tagged_condition and tagged_validity contain the union of all tagged
643 * condition or conditional validity dependence relations that
644 * specialize the dependence relation "map"; that is,
645 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
646 * or "tagged_validity", then i -> j is an element of "map".
647 * If these fields are NULL, then they represent the empty relation.
648 * src is the source node
649 * dst is the sink node
651 * types is a bit vector containing the types of this edge.
652 * validity is set if the edge is used to ensure correctness
653 * coincidence is used to enforce zero dependence distances
654 * proximity is set if the edge is used to minimize dependence distances
655 * condition is set if the edge represents a condition
656 * for a conditional validity schedule constraint
657 * local can only be set for condition edges and indicates that
658 * the dependence distance over the edge should be zero
659 * conditional_validity is set if the edge is used to conditionally
662 * For validity edges, start and end mark the sequence of inequality
663 * constraints in the LP problem that encode the validity constraint
664 * corresponding to this edge.
666 * During clustering, an edge may be marked "no_merge" if it should
667 * not be used to merge clusters.
668 * The weight is also only used during clustering and it is
669 * an indication of how many schedule dimensions on either side
670 * of the schedule constraints can be aligned.
671 * If the weight is negative, then this means that this edge was postponed
672 * by has_bounded_distances or any_no_merge. The original weight can
673 * be retrieved by adding 1 + graph->max_weight, with "graph"
674 * the graph containing this edge.
676 struct isl_sched_edge
{
678 isl_union_map
*tagged_condition
;
679 isl_union_map
*tagged_validity
;
681 struct isl_sched_node
*src
;
682 struct isl_sched_node
*dst
;
693 /* Is "edge" marked as being of type "type"?
695 static int is_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
697 return ISL_FL_ISSET(edge
->types
, 1 << type
);
700 /* Mark "edge" as being of type "type".
702 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
704 ISL_FL_SET(edge
->types
, 1 << type
);
707 /* No longer mark "edge" as being of type "type"?
709 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
711 ISL_FL_CLR(edge
->types
, 1 << type
);
714 /* Is "edge" marked as a validity edge?
716 static int is_validity(struct isl_sched_edge
*edge
)
718 return is_type(edge
, isl_edge_validity
);
721 /* Mark "edge" as a validity edge.
723 static void set_validity(struct isl_sched_edge
*edge
)
725 set_type(edge
, isl_edge_validity
);
728 /* Is "edge" marked as a proximity edge?
730 static int is_proximity(struct isl_sched_edge
*edge
)
732 return is_type(edge
, isl_edge_proximity
);
735 /* Is "edge" marked as a local edge?
737 static int is_local(struct isl_sched_edge
*edge
)
739 return is_type(edge
, isl_edge_local
);
742 /* Mark "edge" as a local edge.
744 static void set_local(struct isl_sched_edge
*edge
)
746 set_type(edge
, isl_edge_local
);
749 /* No longer mark "edge" as a local edge.
751 static void clear_local(struct isl_sched_edge
*edge
)
753 clear_type(edge
, isl_edge_local
);
756 /* Is "edge" marked as a coincidence edge?
758 static int is_coincidence(struct isl_sched_edge
*edge
)
760 return is_type(edge
, isl_edge_coincidence
);
763 /* Is "edge" marked as a condition edge?
765 static int is_condition(struct isl_sched_edge
*edge
)
767 return is_type(edge
, isl_edge_condition
);
770 /* Is "edge" marked as a conditional validity edge?
772 static int is_conditional_validity(struct isl_sched_edge
*edge
)
774 return is_type(edge
, isl_edge_conditional_validity
);
777 /* Internal information about the dependence graph used during
778 * the construction of the schedule.
780 * intra_hmap is a cache, mapping dependence relations to their dual,
781 * for dependences from a node to itself
782 * inter_hmap is a cache, mapping dependence relations to their dual,
783 * for dependences between distinct nodes
784 * if compression is involved then the key for these maps
785 * is the original, uncompressed dependence relation, while
786 * the value is the dual of the compressed dependence relation.
788 * n is the number of nodes
789 * node is the list of nodes
790 * maxvar is the maximal number of variables over all nodes
791 * max_row is the allocated number of rows in the schedule
792 * n_row is the current (maximal) number of linearly independent
793 * rows in the node schedules
794 * n_total_row is the current number of rows in the node schedules
795 * band_start is the starting row in the node schedules of the current band
796 * root is set if this graph is the original dependence graph,
797 * without any splitting
799 * sorted contains a list of node indices sorted according to the
800 * SCC to which a node belongs
802 * n_edge is the number of edges
803 * edge is the list of edges
804 * max_edge contains the maximal number of edges of each type;
805 * in particular, it contains the number of edges in the inital graph.
806 * edge_table contains pointers into the edge array, hashed on the source
807 * and sink spaces; there is one such table for each type;
808 * a given edge may be referenced from more than one table
809 * if the corresponding relation appears in more than one of the
810 * sets of dependences; however, for each type there is only
811 * a single edge between a given pair of source and sink space
812 * in the entire graph
814 * node_table contains pointers into the node array, hashed on the space
816 * region contains a list of variable sequences that should be non-trivial
818 * lp contains the (I)LP problem used to obtain new schedule rows
820 * src_scc and dst_scc are the source and sink SCCs of an edge with
821 * conflicting constraints
823 * scc represents the number of components
824 * weak is set if the components are weakly connected
826 * max_weight is used during clustering and represents the maximal
827 * weight of the relevant proximity edges.
829 struct isl_sched_graph
{
830 isl_map_to_basic_set
*intra_hmap
;
831 isl_map_to_basic_set
*inter_hmap
;
833 struct isl_sched_node
*node
;
846 struct isl_sched_edge
*edge
;
848 int max_edge
[isl_edge_last
+ 1];
849 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
851 struct isl_hash_table
*node_table
;
852 struct isl_region
*region
;
865 /* Initialize node_table based on the list of nodes.
867 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
871 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
872 if (!graph
->node_table
)
875 for (i
= 0; i
< graph
->n
; ++i
) {
876 struct isl_hash_table_entry
*entry
;
879 hash
= isl_space_get_hash(graph
->node
[i
].space
);
880 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
882 graph
->node
[i
].space
, 1);
885 entry
->data
= &graph
->node
[i
];
891 /* Return a pointer to the node that lives within the given space,
892 * or NULL if there is no such node.
894 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
895 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
897 struct isl_hash_table_entry
*entry
;
900 hash
= isl_space_get_hash(dim
);
901 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
902 &node_has_space
, dim
, 0);
904 return entry
? entry
->data
: NULL
;
907 static int edge_has_src_and_dst(const void *entry
, const void *val
)
909 const struct isl_sched_edge
*edge
= entry
;
910 const struct isl_sched_edge
*temp
= val
;
912 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
915 /* Add the given edge to graph->edge_table[type].
917 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
918 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
919 struct isl_sched_edge
*edge
)
921 struct isl_hash_table_entry
*entry
;
924 hash
= isl_hash_init();
925 hash
= isl_hash_builtin(hash
, edge
->src
);
926 hash
= isl_hash_builtin(hash
, edge
->dst
);
927 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
928 &edge_has_src_and_dst
, edge
, 1);
930 return isl_stat_error
;
936 /* Allocate the edge_tables based on the maximal number of edges of
939 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
943 for (i
= 0; i
<= isl_edge_last
; ++i
) {
944 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
946 if (!graph
->edge_table
[i
])
953 /* If graph->edge_table[type] contains an edge from the given source
954 * to the given destination, then return the hash table entry of this edge.
955 * Otherwise, return NULL.
957 static struct isl_hash_table_entry
*graph_find_edge_entry(
958 struct isl_sched_graph
*graph
,
959 enum isl_edge_type type
,
960 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
962 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
964 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
966 hash
= isl_hash_init();
967 hash
= isl_hash_builtin(hash
, temp
.src
);
968 hash
= isl_hash_builtin(hash
, temp
.dst
);
969 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
970 &edge_has_src_and_dst
, &temp
, 0);
974 /* If graph->edge_table[type] contains an edge from the given source
975 * to the given destination, then return this edge.
976 * Otherwise, return NULL.
978 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
979 enum isl_edge_type type
,
980 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
982 struct isl_hash_table_entry
*entry
;
984 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
991 /* Check whether the dependence graph has an edge of the given type
992 * between the given two nodes.
994 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
995 enum isl_edge_type type
,
996 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
998 struct isl_sched_edge
*edge
;
1001 edge
= graph_find_edge(graph
, type
, src
, dst
);
1005 empty
= isl_map_plain_is_empty(edge
->map
);
1007 return isl_bool_error
;
1012 /* Look for any edge with the same src, dst and map fields as "model".
1014 * Return the matching edge if one can be found.
1015 * Return "model" if no matching edge is found.
1016 * Return NULL on error.
1018 static struct isl_sched_edge
*graph_find_matching_edge(
1019 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
1021 enum isl_edge_type i
;
1022 struct isl_sched_edge
*edge
;
1024 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1027 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
1030 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
1040 /* Remove the given edge from all the edge_tables that refer to it.
1042 static void graph_remove_edge(struct isl_sched_graph
*graph
,
1043 struct isl_sched_edge
*edge
)
1045 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
1046 enum isl_edge_type i
;
1048 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1049 struct isl_hash_table_entry
*entry
;
1051 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
1054 if (entry
->data
!= edge
)
1056 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
1060 /* Check whether the dependence graph has any edge
1061 * between the given two nodes.
1063 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
1064 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1066 enum isl_edge_type i
;
1069 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1070 r
= graph_has_edge(graph
, i
, src
, dst
);
1078 /* Check whether the dependence graph has a validity edge
1079 * between the given two nodes.
1081 * Conditional validity edges are essentially validity edges that
1082 * can be ignored if the corresponding condition edges are iteration private.
1083 * Here, we are only checking for the presence of validity
1084 * edges, so we need to consider the conditional validity edges too.
1085 * In particular, this function is used during the detection
1086 * of strongly connected components and we cannot ignore
1087 * conditional validity edges during this detection.
1089 static isl_bool
graph_has_validity_edge(struct isl_sched_graph
*graph
,
1090 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1094 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
1098 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
1101 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1102 int n_node
, int n_edge
)
1107 graph
->n_edge
= n_edge
;
1108 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
1109 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
1110 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
1111 graph
->edge
= isl_calloc_array(ctx
,
1112 struct isl_sched_edge
, graph
->n_edge
);
1114 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
1115 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
1117 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
1121 for(i
= 0; i
< graph
->n
; ++i
)
1122 graph
->sorted
[i
] = i
;
1127 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1131 isl_map_to_basic_set_free(graph
->intra_hmap
);
1132 isl_map_to_basic_set_free(graph
->inter_hmap
);
1135 for (i
= 0; i
< graph
->n
; ++i
) {
1136 isl_space_free(graph
->node
[i
].space
);
1137 isl_set_free(graph
->node
[i
].hull
);
1138 isl_multi_aff_free(graph
->node
[i
].compress
);
1139 isl_multi_aff_free(graph
->node
[i
].decompress
);
1140 isl_mat_free(graph
->node
[i
].sched
);
1141 isl_map_free(graph
->node
[i
].sched_map
);
1142 isl_mat_free(graph
->node
[i
].cmap
);
1143 isl_mat_free(graph
->node
[i
].cinv
);
1144 isl_mat_free(graph
->node
[i
].ctrans
);
1146 free(graph
->node
[i
].coincident
);
1147 isl_multi_val_free(graph
->node
[i
].sizes
);
1148 isl_vec_free(graph
->node
[i
].max
);
1151 free(graph
->sorted
);
1153 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1154 isl_map_free(graph
->edge
[i
].map
);
1155 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
1156 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
1159 free(graph
->region
);
1160 for (i
= 0; i
<= isl_edge_last
; ++i
)
1161 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
1162 isl_hash_table_free(ctx
, graph
->node_table
);
1163 isl_basic_set_free(graph
->lp
);
1166 /* For each "set" on which this function is called, increment
1167 * graph->n by one and update graph->maxvar.
1169 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
1171 struct isl_sched_graph
*graph
= user
;
1172 int nvar
= isl_set_dim(set
, isl_dim_set
);
1175 if (nvar
> graph
->maxvar
)
1176 graph
->maxvar
= nvar
;
1183 /* Compute the number of rows that should be allocated for the schedule.
1184 * In particular, we need one row for each variable or one row
1185 * for each basic map in the dependences.
1186 * Note that it is practically impossible to exhaust both
1187 * the number of dependences and the number of variables.
1189 static isl_stat
compute_max_row(struct isl_sched_graph
*graph
,
1190 __isl_keep isl_schedule_constraints
*sc
)
1196 if (isl_union_set_foreach_set(sc
->domain
, &init_n_maxvar
, graph
) < 0)
1197 return isl_stat_error
;
1198 n_edge
= isl_schedule_constraints_n_basic_map(sc
);
1200 return isl_stat_error
;
1201 graph
->max_row
= n_edge
+ graph
->maxvar
;
1206 /* Does "bset" have any defining equalities for its set variables?
1208 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
1215 n
= isl_basic_set_dim(bset
, isl_dim_set
);
1216 for (i
= 0; i
< n
; ++i
) {
1219 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
1228 /* Set the entries of node->max to the value of the schedule_max_coefficient
1231 static isl_stat
set_max_coefficient(isl_ctx
*ctx
, struct isl_sched_node
*node
)
1235 max
= isl_options_get_schedule_max_coefficient(ctx
);
1239 node
->max
= isl_vec_alloc(ctx
, node
->nvar
);
1240 node
->max
= isl_vec_set_si(node
->max
, max
);
1242 return isl_stat_error
;
1247 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
1248 * option (if set) and half of the minimum of the sizes in the other
1249 * dimensions. If the minimum of the sizes is one, half of the size
1250 * is zero and this value is reset to one.
1251 * If the global minimum is unbounded (i.e., if both
1252 * the schedule_max_coefficient is not set and the sizes in the other
1253 * dimensions are unbounded), then store a negative value.
1254 * If the schedule coefficient is close to the size of the instance set
1255 * in another dimension, then the schedule may represent a loop
1256 * coalescing transformation (especially if the coefficient
1257 * in that other dimension is one). Forcing the coefficient to be
1258 * smaller than or equal to half the minimal size should avoid this
1261 static isl_stat
compute_max_coefficient(isl_ctx
*ctx
,
1262 struct isl_sched_node
*node
)
1268 max
= isl_options_get_schedule_max_coefficient(ctx
);
1269 v
= isl_vec_alloc(ctx
, node
->nvar
);
1271 return isl_stat_error
;
1273 for (i
= 0; i
< node
->nvar
; ++i
) {
1274 isl_int_set_si(v
->el
[i
], max
);
1275 isl_int_mul_si(v
->el
[i
], v
->el
[i
], 2);
1278 for (i
= 0; i
< node
->nvar
; ++i
) {
1281 size
= isl_multi_val_get_val(node
->sizes
, i
);
1284 if (!isl_val_is_int(size
)) {
1288 for (j
= 0; j
< node
->nvar
; ++j
) {
1291 if (isl_int_is_neg(v
->el
[j
]) ||
1292 isl_int_gt(v
->el
[j
], size
->n
))
1293 isl_int_set(v
->el
[j
], size
->n
);
1298 for (i
= 0; i
< node
->nvar
; ++i
) {
1299 isl_int_fdiv_q_ui(v
->el
[i
], v
->el
[i
], 2);
1300 if (isl_int_is_zero(v
->el
[i
]))
1301 isl_int_set_si(v
->el
[i
], 1);
1308 return isl_stat_error
;
1311 /* Compute and return the size of "set" in dimension "dim".
1312 * The size is taken to be the difference in values for that variable
1313 * for fixed values of the other variables.
1314 * In particular, the variable is first isolated from the other variables
1315 * in the range of a map
1317 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
1319 * and then duplicated
1321 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
1323 * The shared variables are then projected out and the maximal value
1324 * of i_dim' - i_dim is computed.
1326 static __isl_give isl_val
*compute_size(__isl_take isl_set
*set
, int dim
)
1329 isl_local_space
*ls
;
1333 map
= isl_set_project_onto_map(set
, isl_dim_set
, dim
, 1);
1334 map
= isl_map_project_out(map
, isl_dim_in
, dim
, 1);
1335 map
= isl_map_range_product(map
, isl_map_copy(map
));
1336 map
= isl_set_unwrap(isl_map_range(map
));
1337 set
= isl_map_deltas(map
);
1338 ls
= isl_local_space_from_space(isl_set_get_space(set
));
1339 obj
= isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1340 v
= isl_set_max_val(set
, obj
);
1347 /* Compute the size of the instance set "set" of "node", after compression,
1348 * as well as bounds on the corresponding coefficients, if needed.
1350 * The sizes are needed when the schedule_treat_coalescing option is set.
1351 * The bounds are needed when the schedule_treat_coalescing option or
1352 * the schedule_max_coefficient option is set.
1354 * If the schedule_treat_coalescing option is not set, then at most
1355 * the bounds need to be set and this is done in set_max_coefficient.
1356 * Otherwise, compress the domain if needed, compute the size
1357 * in each direction and store the results in node->size.
1358 * Finally, set the bounds on the coefficients based on the sizes
1359 * and the schedule_max_coefficient option in compute_max_coefficient.
1361 static isl_stat
compute_sizes_and_max(isl_ctx
*ctx
, struct isl_sched_node
*node
,
1362 __isl_take isl_set
*set
)
1367 if (!isl_options_get_schedule_treat_coalescing(ctx
)) {
1369 return set_max_coefficient(ctx
, node
);
1372 if (node
->compressed
)
1373 set
= isl_set_preimage_multi_aff(set
,
1374 isl_multi_aff_copy(node
->decompress
));
1375 mv
= isl_multi_val_zero(isl_set_get_space(set
));
1376 n
= isl_set_dim(set
, isl_dim_set
);
1377 for (j
= 0; j
< n
; ++j
) {
1380 v
= compute_size(isl_set_copy(set
), j
);
1381 mv
= isl_multi_val_set_val(mv
, j
, v
);
1386 return isl_stat_error
;
1387 return compute_max_coefficient(ctx
, node
);
1390 /* Add a new node to the graph representing the given instance set.
1391 * "nvar" is the (possibly compressed) number of variables and
1392 * may be smaller than then number of set variables in "set"
1393 * if "compressed" is set.
1394 * If "compressed" is set, then "hull" represents the constraints
1395 * that were used to derive the compression, while "compress" and
1396 * "decompress" map the original space to the compressed space and
1398 * If "compressed" is not set, then "hull", "compress" and "decompress"
1401 * Compute the size of the instance set and bounds on the coefficients,
1404 static isl_stat
add_node(struct isl_sched_graph
*graph
,
1405 __isl_take isl_set
*set
, int nvar
, int compressed
,
1406 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
1407 __isl_take isl_multi_aff
*decompress
)
1414 struct isl_sched_node
*node
;
1417 return isl_stat_error
;
1419 ctx
= isl_set_get_ctx(set
);
1420 nparam
= isl_set_dim(set
, isl_dim_param
);
1421 if (!ctx
->opt
->schedule_parametric
)
1423 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
1424 node
= &graph
->node
[graph
->n
];
1426 space
= isl_set_get_space(set
);
1427 node
->space
= space
;
1429 node
->nparam
= nparam
;
1430 node
->sched
= sched
;
1431 node
->sched_map
= NULL
;
1432 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
1433 node
->coincident
= coincident
;
1434 node
->compressed
= compressed
;
1436 node
->compress
= compress
;
1437 node
->decompress
= decompress
;
1438 if (compute_sizes_and_max(ctx
, node
, set
) < 0)
1439 return isl_stat_error
;
1441 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
1442 return isl_stat_error
;
1443 if (compressed
&& (!hull
|| !compress
|| !decompress
))
1444 return isl_stat_error
;
1449 /* Add a new node to the graph representing the given set.
1451 * If any of the set variables is defined by an equality, then
1452 * we perform variable compression such that we can perform
1453 * the scheduling on the compressed domain.
1455 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1459 isl_basic_set
*hull
;
1462 isl_multi_aff
*compress
, *decompress
;
1463 struct isl_sched_graph
*graph
= user
;
1465 hull
= isl_set_affine_hull(isl_set_copy(set
));
1466 hull
= isl_basic_set_remove_divs(hull
);
1467 nvar
= isl_set_dim(set
, isl_dim_set
);
1468 has_equality
= has_any_defining_equality(hull
);
1470 if (has_equality
< 0)
1472 if (!has_equality
) {
1473 isl_basic_set_free(hull
);
1474 return add_node(graph
, set
, nvar
, 0, NULL
, NULL
, NULL
);
1477 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
1478 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1479 compress
= isl_morph_get_var_multi_aff(morph
);
1480 morph
= isl_morph_inverse(morph
);
1481 decompress
= isl_morph_get_var_multi_aff(morph
);
1482 isl_morph_free(morph
);
1484 hull_set
= isl_set_from_basic_set(hull
);
1485 return add_node(graph
, set
, nvar
, 1, hull_set
, compress
, decompress
);
1487 isl_basic_set_free(hull
);
1489 return isl_stat_error
;
1492 struct isl_extract_edge_data
{
1493 enum isl_edge_type type
;
1494 struct isl_sched_graph
*graph
;
1497 /* Merge edge2 into edge1, freeing the contents of edge2.
1498 * Return 0 on success and -1 on failure.
1500 * edge1 and edge2 are assumed to have the same value for the map field.
1502 static int merge_edge(struct isl_sched_edge
*edge1
,
1503 struct isl_sched_edge
*edge2
)
1505 edge1
->types
|= edge2
->types
;
1506 isl_map_free(edge2
->map
);
1508 if (is_condition(edge2
)) {
1509 if (!edge1
->tagged_condition
)
1510 edge1
->tagged_condition
= edge2
->tagged_condition
;
1512 edge1
->tagged_condition
=
1513 isl_union_map_union(edge1
->tagged_condition
,
1514 edge2
->tagged_condition
);
1517 if (is_conditional_validity(edge2
)) {
1518 if (!edge1
->tagged_validity
)
1519 edge1
->tagged_validity
= edge2
->tagged_validity
;
1521 edge1
->tagged_validity
=
1522 isl_union_map_union(edge1
->tagged_validity
,
1523 edge2
->tagged_validity
);
1526 if (is_condition(edge2
) && !edge1
->tagged_condition
)
1528 if (is_conditional_validity(edge2
) && !edge1
->tagged_validity
)
1534 /* Insert dummy tags in domain and range of "map".
1536 * In particular, if "map" is of the form
1542 * [A -> dummy_tag] -> [B -> dummy_tag]
1544 * where the dummy_tags are identical and equal to any dummy tags
1545 * introduced by any other call to this function.
1547 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1553 isl_set
*domain
, *range
;
1555 ctx
= isl_map_get_ctx(map
);
1557 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1558 space
= isl_space_params(isl_map_get_space(map
));
1559 space
= isl_space_set_from_params(space
);
1560 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1561 space
= isl_space_map_from_set(space
);
1563 domain
= isl_map_wrap(map
);
1564 range
= isl_map_wrap(isl_map_universe(space
));
1565 map
= isl_map_from_domain_and_range(domain
, range
);
1566 map
= isl_map_zip(map
);
1571 /* Given that at least one of "src" or "dst" is compressed, return
1572 * a map between the spaces of these nodes restricted to the affine
1573 * hull that was used in the compression.
1575 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1576 struct isl_sched_node
*dst
)
1580 if (src
->compressed
)
1581 dom
= isl_set_copy(src
->hull
);
1583 dom
= isl_set_universe(isl_space_copy(src
->space
));
1584 if (dst
->compressed
)
1585 ran
= isl_set_copy(dst
->hull
);
1587 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1589 return isl_map_from_domain_and_range(dom
, ran
);
1592 /* Intersect the domains of the nested relations in domain and range
1593 * of "tagged" with "map".
1595 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1596 __isl_keep isl_map
*map
)
1600 tagged
= isl_map_zip(tagged
);
1601 set
= isl_map_wrap(isl_map_copy(map
));
1602 tagged
= isl_map_intersect_domain(tagged
, set
);
1603 tagged
= isl_map_zip(tagged
);
1607 /* Return a pointer to the node that lives in the domain space of "map"
1608 * or NULL if there is no such node.
1610 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1611 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1613 struct isl_sched_node
*node
;
1616 space
= isl_space_domain(isl_map_get_space(map
));
1617 node
= graph_find_node(ctx
, graph
, space
);
1618 isl_space_free(space
);
1623 /* Return a pointer to the node that lives in the range space of "map"
1624 * or NULL if there is no such node.
1626 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1627 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1629 struct isl_sched_node
*node
;
1632 space
= isl_space_range(isl_map_get_space(map
));
1633 node
= graph_find_node(ctx
, graph
, space
);
1634 isl_space_free(space
);
1639 /* Add a new edge to the graph based on the given map
1640 * and add it to data->graph->edge_table[data->type].
1641 * If a dependence relation of a given type happens to be identical
1642 * to one of the dependence relations of a type that was added before,
1643 * then we don't create a new edge, but instead mark the original edge
1644 * as also representing a dependence of the current type.
1646 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1647 * may be specified as "tagged" dependence relations. That is, "map"
1648 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1649 * the dependence on iterations and a and b are tags.
1650 * edge->map is set to the relation containing the elements i -> j,
1651 * while edge->tagged_condition and edge->tagged_validity contain
1652 * the union of all the "map" relations
1653 * for which extract_edge is called that result in the same edge->map.
1655 * If the source or the destination node is compressed, then
1656 * intersect both "map" and "tagged" with the constraints that
1657 * were used to construct the compression.
1658 * This ensures that there are no schedule constraints defined
1659 * outside of these domains, while the scheduler no longer has
1660 * any control over those outside parts.
1662 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1664 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1665 struct isl_extract_edge_data
*data
= user
;
1666 struct isl_sched_graph
*graph
= data
->graph
;
1667 struct isl_sched_node
*src
, *dst
;
1668 struct isl_sched_edge
*edge
;
1669 isl_map
*tagged
= NULL
;
1671 if (data
->type
== isl_edge_condition
||
1672 data
->type
== isl_edge_conditional_validity
) {
1673 if (isl_map_can_zip(map
)) {
1674 tagged
= isl_map_copy(map
);
1675 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1677 tagged
= insert_dummy_tags(isl_map_copy(map
));
1681 src
= find_domain_node(ctx
, graph
, map
);
1682 dst
= find_range_node(ctx
, graph
, map
);
1686 isl_map_free(tagged
);
1690 if (src
->compressed
|| dst
->compressed
) {
1692 hull
= extract_hull(src
, dst
);
1694 tagged
= map_intersect_domains(tagged
, hull
);
1695 map
= isl_map_intersect(map
, hull
);
1698 graph
->edge
[graph
->n_edge
].src
= src
;
1699 graph
->edge
[graph
->n_edge
].dst
= dst
;
1700 graph
->edge
[graph
->n_edge
].map
= map
;
1701 graph
->edge
[graph
->n_edge
].types
= 0;
1702 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1703 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1704 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1705 if (data
->type
== isl_edge_condition
)
1706 graph
->edge
[graph
->n_edge
].tagged_condition
=
1707 isl_union_map_from_map(tagged
);
1708 if (data
->type
== isl_edge_conditional_validity
)
1709 graph
->edge
[graph
->n_edge
].tagged_validity
=
1710 isl_union_map_from_map(tagged
);
1712 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1715 return isl_stat_error
;
1717 if (edge
== &graph
->edge
[graph
->n_edge
])
1718 return graph_edge_table_add(ctx
, graph
, data
->type
,
1719 &graph
->edge
[graph
->n_edge
++]);
1721 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1724 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1727 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1729 * The context is included in the domain before the nodes of
1730 * the graphs are extracted in order to be able to exploit
1731 * any possible additional equalities.
1732 * Note that this intersection is only performed locally here.
1734 static isl_stat
graph_init(struct isl_sched_graph
*graph
,
1735 __isl_keep isl_schedule_constraints
*sc
)
1738 isl_union_set
*domain
;
1739 struct isl_extract_edge_data data
;
1740 enum isl_edge_type i
;
1744 return isl_stat_error
;
1746 ctx
= isl_schedule_constraints_get_ctx(sc
);
1748 domain
= isl_schedule_constraints_get_domain(sc
);
1749 graph
->n
= isl_union_set_n_set(domain
);
1750 isl_union_set_free(domain
);
1752 if (graph_alloc(ctx
, graph
, graph
->n
,
1753 isl_schedule_constraints_n_map(sc
)) < 0)
1754 return isl_stat_error
;
1756 if (compute_max_row(graph
, sc
) < 0)
1757 return isl_stat_error
;
1760 domain
= isl_schedule_constraints_get_domain(sc
);
1761 domain
= isl_union_set_intersect_params(domain
,
1762 isl_schedule_constraints_get_context(sc
));
1763 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1764 isl_union_set_free(domain
);
1766 return isl_stat_error
;
1767 if (graph_init_table(ctx
, graph
) < 0)
1768 return isl_stat_error
;
1769 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
1770 graph
->max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
1771 if (graph_init_edge_tables(ctx
, graph
) < 0)
1772 return isl_stat_error
;
1775 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1777 if (isl_union_map_foreach_map(sc
->constraint
[i
],
1778 &extract_edge
, &data
) < 0)
1779 return isl_stat_error
;
1785 /* Check whether there is any dependence from node[j] to node[i]
1786 * or from node[i] to node[j].
1788 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1791 struct isl_sched_graph
*graph
= user
;
1793 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1796 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1799 /* Check whether there is a (conditional) validity dependence from node[j]
1800 * to node[i], forcing node[i] to follow node[j].
1802 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1804 struct isl_sched_graph
*graph
= user
;
1806 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1809 /* Use Tarjan's algorithm for computing the strongly connected components
1810 * in the dependence graph only considering those edges defined by "follows".
1812 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1813 isl_bool (*follows
)(int i
, int j
, void *user
))
1816 struct isl_tarjan_graph
*g
= NULL
;
1818 g
= isl_tarjan_graph_init(ctx
, graph
->n
, follows
, graph
);
1826 while (g
->order
[i
] != -1) {
1827 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1835 isl_tarjan_graph_free(g
);
1840 /* Apply Tarjan's algorithm to detect the strongly connected components
1841 * in the dependence graph.
1842 * Only consider the (conditional) validity dependences and clear "weak".
1844 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1847 return detect_ccs(ctx
, graph
, &node_follows_strong
);
1850 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1851 * in the dependence graph.
1852 * Consider all dependences and set "weak".
1854 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1857 return detect_ccs(ctx
, graph
, &node_follows_weak
);
1860 static int cmp_scc(const void *a
, const void *b
, void *data
)
1862 struct isl_sched_graph
*graph
= data
;
1866 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1869 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1871 static int sort_sccs(struct isl_sched_graph
*graph
)
1873 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1876 /* Given a dependence relation R from "node" to itself,
1877 * construct the set of coefficients of valid constraints for elements
1878 * in that dependence relation.
1879 * In particular, the result contains tuples of coefficients
1880 * c_0, c_n, c_x such that
1882 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1886 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1888 * We choose here to compute the dual of delta R.
1889 * Alternatively, we could have computed the dual of R, resulting
1890 * in a set of tuples c_0, c_n, c_x, c_y, and then
1891 * plugged in (c_0, c_n, c_x, -c_x).
1893 * If "node" has been compressed, then the dependence relation
1894 * is also compressed before the set of coefficients is computed.
1896 static __isl_give isl_basic_set
*intra_coefficients(
1897 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1898 __isl_take isl_map
*map
)
1902 isl_basic_set
*coef
;
1903 isl_maybe_isl_basic_set m
;
1905 m
= isl_map_to_basic_set_try_get(graph
->intra_hmap
, map
);
1906 if (m
.valid
< 0 || m
.valid
) {
1911 key
= isl_map_copy(map
);
1912 if (node
->compressed
) {
1913 map
= isl_map_preimage_domain_multi_aff(map
,
1914 isl_multi_aff_copy(node
->decompress
));
1915 map
= isl_map_preimage_range_multi_aff(map
,
1916 isl_multi_aff_copy(node
->decompress
));
1918 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1919 coef
= isl_set_coefficients(delta
);
1920 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1921 isl_basic_set_copy(coef
));
1926 /* Given a dependence relation R, construct the set of coefficients
1927 * of valid constraints for elements in that dependence relation.
1928 * In particular, the result contains tuples of coefficients
1929 * c_0, c_n, c_x, c_y such that
1931 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1933 * If the source or destination nodes of "edge" have been compressed,
1934 * then the dependence relation is also compressed before
1935 * the set of coefficients is computed.
1937 static __isl_give isl_basic_set
*inter_coefficients(
1938 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1939 __isl_take isl_map
*map
)
1943 isl_basic_set
*coef
;
1944 isl_maybe_isl_basic_set m
;
1946 m
= isl_map_to_basic_set_try_get(graph
->inter_hmap
, map
);
1947 if (m
.valid
< 0 || m
.valid
) {
1952 key
= isl_map_copy(map
);
1953 if (edge
->src
->compressed
)
1954 map
= isl_map_preimage_domain_multi_aff(map
,
1955 isl_multi_aff_copy(edge
->src
->decompress
));
1956 if (edge
->dst
->compressed
)
1957 map
= isl_map_preimage_range_multi_aff(map
,
1958 isl_multi_aff_copy(edge
->dst
->decompress
));
1959 set
= isl_map_wrap(isl_map_remove_divs(map
));
1960 coef
= isl_set_coefficients(set
);
1961 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1962 isl_basic_set_copy(coef
));
1967 /* Return the position of the coefficients of the variables in
1968 * the coefficients constraints "coef".
1970 * The space of "coef" is of the form
1972 * { coefficients[[cst, params] -> S] }
1974 * Return the position of S.
1976 static int coef_var_offset(__isl_keep isl_basic_set
*coef
)
1981 space
= isl_space_unwrap(isl_basic_set_get_space(coef
));
1982 offset
= isl_space_dim(space
, isl_dim_in
);
1983 isl_space_free(space
);
1988 /* Return the offset of the coefficients of the variables of "node"
1991 * Within each node, the coefficients have the following order:
1993 * - c_i_n (if parametric)
1994 * - positive and negative parts of c_i_x
1996 static int node_var_coef_offset(struct isl_sched_node
*node
)
1998 return node
->start
+ 1 + node
->nparam
;
2001 /* Construct an isl_dim_map for mapping constraints on coefficients
2002 * for "node" to the corresponding positions in graph->lp.
2003 * "offset" is the offset of the coefficients for the variables
2004 * in the input constraints.
2005 * "s" is the sign of the mapping.
2007 * The input constraints are given in terms of the coefficients (c_0, c_n, c_x).
2008 * The mapping produced by this function essentially plugs in
2009 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
2010 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
2011 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
2013 * The caller can extend the mapping to also map the other coefficients
2014 * (and therefore not plug in 0).
2016 static __isl_give isl_dim_map
*intra_dim_map(isl_ctx
*ctx
,
2017 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
2022 isl_dim_map
*dim_map
;
2024 total
= isl_basic_set_total_dim(graph
->lp
);
2025 pos
= node_var_coef_offset(node
);
2026 dim_map
= isl_dim_map_alloc(ctx
, total
);
2027 isl_dim_map_range(dim_map
, pos
, 2, offset
, 1, node
->nvar
, -s
);
2028 isl_dim_map_range(dim_map
, pos
+ 1, 2, offset
, 1, node
->nvar
, s
);
2033 /* Construct an isl_dim_map for mapping constraints on coefficients
2034 * for "src" (node i) and "dst" (node j) to the corresponding positions
2036 * "offset" is the offset of the coefficients for the variables of "src"
2037 * in the input constraints.
2038 * "s" is the sign of the mapping.
2040 * The input constraints are given in terms of the coefficients
2041 * (c_0, c_n, c_x, c_y).
2042 * The mapping produced by this function essentially plugs in
2043 * (c_j_0 - c_i_0, c_j_n - c_i_n,
2044 * c_j_x^+ - c_j_x^-, -(c_i_x^+ - c_i_x^-)) if s = 1 and
2045 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
2046 * - (c_j_x^+ - c_j_x^-), c_i_x^+ - c_i_x^-) if s = -1.
2047 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
2049 * The caller can further extend the mapping.
2051 static __isl_give isl_dim_map
*inter_dim_map(isl_ctx
*ctx
,
2052 struct isl_sched_graph
*graph
, struct isl_sched_node
*src
,
2053 struct isl_sched_node
*dst
, int offset
, int s
)
2057 isl_dim_map
*dim_map
;
2059 total
= isl_basic_set_total_dim(graph
->lp
);
2060 dim_map
= isl_dim_map_alloc(ctx
, total
);
2062 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, s
);
2063 isl_dim_map_range(dim_map
, dst
->start
+ 1, 1, 1, 1, dst
->nparam
, s
);
2064 pos
= node_var_coef_offset(dst
);
2065 isl_dim_map_range(dim_map
, pos
, 2, offset
+ src
->nvar
, 1,
2067 isl_dim_map_range(dim_map
, pos
+ 1, 2, offset
+ src
->nvar
, 1,
2070 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -s
);
2071 isl_dim_map_range(dim_map
, src
->start
+ 1, 1, 1, 1, src
->nparam
, -s
);
2072 pos
= node_var_coef_offset(src
);
2073 isl_dim_map_range(dim_map
, pos
, 2, offset
, 1, src
->nvar
, s
);
2074 isl_dim_map_range(dim_map
, pos
+ 1, 2, offset
, 1, src
->nvar
, -s
);
2079 /* Add constraints to graph->lp that force validity for the given
2080 * dependence from a node i to itself.
2081 * That is, add constraints that enforce
2083 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
2084 * = c_i_x (y - x) >= 0
2086 * for each (x,y) in R.
2087 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2088 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
2089 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
2090 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
2092 * Actually, we do not construct constraints for the c_i_x themselves,
2093 * but for the coefficients of c_i_x written as a linear combination
2094 * of the columns in node->cmap.
2096 static isl_stat
add_intra_validity_constraints(struct isl_sched_graph
*graph
,
2097 struct isl_sched_edge
*edge
)
2100 isl_map
*map
= isl_map_copy(edge
->map
);
2101 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2102 isl_dim_map
*dim_map
;
2103 isl_basic_set
*coef
;
2104 struct isl_sched_node
*node
= edge
->src
;
2106 coef
= intra_coefficients(graph
, node
, map
);
2108 offset
= coef_var_offset(coef
);
2110 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2111 offset
, isl_mat_copy(node
->cmap
));
2113 return isl_stat_error
;
2115 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
2116 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2117 coef
->n_eq
, coef
->n_ineq
);
2118 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2124 /* Add constraints to graph->lp that force validity for the given
2125 * dependence from node i to node j.
2126 * That is, add constraints that enforce
2128 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
2130 * for each (x,y) in R.
2131 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
2132 * of valid constraints for R and then plug in
2133 * (c_j_0 - c_i_0, c_j_n - c_i_n, c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
2134 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
2135 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
2137 * Actually, we do not construct constraints for the c_*_x themselves,
2138 * but for the coefficients of c_*_x written as a linear combination
2139 * of the columns in node->cmap.
2141 static isl_stat
add_inter_validity_constraints(struct isl_sched_graph
*graph
,
2142 struct isl_sched_edge
*edge
)
2145 isl_map
*map
= isl_map_copy(edge
->map
);
2146 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2147 isl_dim_map
*dim_map
;
2148 isl_basic_set
*coef
;
2149 struct isl_sched_node
*src
= edge
->src
;
2150 struct isl_sched_node
*dst
= edge
->dst
;
2152 coef
= inter_coefficients(graph
, edge
, map
);
2154 offset
= coef_var_offset(coef
);
2156 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2157 offset
, isl_mat_copy(src
->cmap
));
2158 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2159 offset
+ src
->nvar
, isl_mat_copy(dst
->cmap
));
2161 return isl_stat_error
;
2163 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
2165 edge
->start
= graph
->lp
->n_ineq
;
2166 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2167 coef
->n_eq
, coef
->n_ineq
);
2168 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2171 return isl_stat_error
;
2172 edge
->end
= graph
->lp
->n_ineq
;
2177 /* Add constraints to graph->lp that bound the dependence distance for the given
2178 * dependence from a node i to itself.
2179 * If s = 1, we add the constraint
2181 * c_i_x (y - x) <= m_0 + m_n n
2185 * -c_i_x (y - x) + m_0 + m_n n >= 0
2187 * for each (x,y) in R.
2188 * If s = -1, we add the constraint
2190 * -c_i_x (y - x) <= m_0 + m_n n
2194 * c_i_x (y - x) + m_0 + m_n n >= 0
2196 * for each (x,y) in R.
2197 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2198 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
2199 * with each coefficient (except m_0) represented as a pair of non-negative
2202 * Actually, we do not construct constraints for the c_i_x themselves,
2203 * but for the coefficients of c_i_x written as a linear combination
2204 * of the columns in node->cmap.
2207 * If "local" is set, then we add constraints
2209 * c_i_x (y - x) <= 0
2213 * -c_i_x (y - x) <= 0
2215 * instead, forcing the dependence distance to be (less than or) equal to 0.
2216 * That is, we plug in (0, 0, -s * c_i_x),
2217 * Note that dependences marked local are treated as validity constraints
2218 * by add_all_validity_constraints and therefore also have
2219 * their distances bounded by 0 from below.
2221 static isl_stat
add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
2222 struct isl_sched_edge
*edge
, int s
, int local
)
2226 isl_map
*map
= isl_map_copy(edge
->map
);
2227 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2228 isl_dim_map
*dim_map
;
2229 isl_basic_set
*coef
;
2230 struct isl_sched_node
*node
= edge
->src
;
2232 coef
= intra_coefficients(graph
, node
, map
);
2234 offset
= coef_var_offset(coef
);
2236 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2237 offset
, isl_mat_copy(node
->cmap
));
2239 return isl_stat_error
;
2241 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
2242 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, -s
);
2245 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
2246 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
2247 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
2249 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2250 coef
->n_eq
, coef
->n_ineq
);
2251 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2257 /* Add constraints to graph->lp that bound the dependence distance for the given
2258 * dependence from node i to node j.
2259 * If s = 1, we add the constraint
2261 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
2266 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
2269 * for each (x,y) in R.
2270 * If s = -1, we add the constraint
2272 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
2277 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
2280 * for each (x,y) in R.
2281 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
2282 * of valid constraints for R and then plug in
2283 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
2285 * with each coefficient (except m_0, c_*_0 and c_*_n)
2286 * represented as a pair of non-negative coefficients.
2288 * Actually, we do not construct constraints for the c_*_x themselves,
2289 * but for the coefficients of c_*_x written as a linear combination
2290 * of the columns in node->cmap.
2293 * If "local" is set, then we add constraints
2295 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
2299 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
2301 * instead, forcing the dependence distance to be (less than or) equal to 0.
2302 * That is, we plug in
2303 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
2304 * Note that dependences marked local are treated as validity constraints
2305 * by add_all_validity_constraints and therefore also have
2306 * their distances bounded by 0 from below.
2308 static isl_stat
add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
2309 struct isl_sched_edge
*edge
, int s
, int local
)
2313 isl_map
*map
= isl_map_copy(edge
->map
);
2314 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2315 isl_dim_map
*dim_map
;
2316 isl_basic_set
*coef
;
2317 struct isl_sched_node
*src
= edge
->src
;
2318 struct isl_sched_node
*dst
= edge
->dst
;
2320 coef
= inter_coefficients(graph
, edge
, map
);
2322 offset
= coef_var_offset(coef
);
2324 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2325 offset
, isl_mat_copy(src
->cmap
));
2326 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
2327 offset
+ src
->nvar
, isl_mat_copy(dst
->cmap
));
2329 return isl_stat_error
;
2331 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
2332 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, -s
);
2335 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
2336 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
2337 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
2340 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2341 coef
->n_eq
, coef
->n_ineq
);
2342 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2348 /* Add all validity constraints to graph->lp.
2350 * An edge that is forced to be local needs to have its dependence
2351 * distances equal to zero. We take care of bounding them by 0 from below
2352 * here. add_all_proximity_constraints takes care of bounding them by 0
2355 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2356 * Otherwise, we ignore them.
2358 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
2359 int use_coincidence
)
2363 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2364 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2367 local
= is_local(edge
) ||
2368 (is_coincidence(edge
) && use_coincidence
);
2369 if (!is_validity(edge
) && !local
)
2371 if (edge
->src
!= edge
->dst
)
2373 if (add_intra_validity_constraints(graph
, edge
) < 0)
2377 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2378 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2381 local
= is_local(edge
) ||
2382 (is_coincidence(edge
) && use_coincidence
);
2383 if (!is_validity(edge
) && !local
)
2385 if (edge
->src
== edge
->dst
)
2387 if (add_inter_validity_constraints(graph
, edge
) < 0)
2394 /* Add constraints to graph->lp that bound the dependence distance
2395 * for all dependence relations.
2396 * If a given proximity dependence is identical to a validity
2397 * dependence, then the dependence distance is already bounded
2398 * from below (by zero), so we only need to bound the distance
2399 * from above. (This includes the case of "local" dependences
2400 * which are treated as validity dependence by add_all_validity_constraints.)
2401 * Otherwise, we need to bound the distance both from above and from below.
2403 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2404 * Otherwise, we ignore them.
2406 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
2407 int use_coincidence
)
2411 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2412 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2415 local
= is_local(edge
) ||
2416 (is_coincidence(edge
) && use_coincidence
);
2417 if (!is_proximity(edge
) && !local
)
2419 if (edge
->src
== edge
->dst
&&
2420 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
2422 if (edge
->src
!= edge
->dst
&&
2423 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
2425 if (is_validity(edge
) || local
)
2427 if (edge
->src
== edge
->dst
&&
2428 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2430 if (edge
->src
!= edge
->dst
&&
2431 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2438 /* Compute a basis for the rows in the linear part of the schedule
2439 * and extend this basis to a full basis. The remaining rows
2440 * can then be used to force linear independence from the rows
2443 * In particular, given the schedule rows S, we compute
2448 * with H the Hermite normal form of S. That is, all but the
2449 * first rank columns of H are zero and so each row in S is
2450 * a linear combination of the first rank rows of Q.
2451 * The matrix Q is then transposed because we will write the
2452 * coefficients of the next schedule row as a column vector s
2453 * and express this s as a linear combination s = Q c of the
2455 * Similarly, the matrix U is transposed such that we can
2456 * compute the coefficients c = U s from a schedule row s.
2458 static int node_update_cmap(struct isl_sched_node
*node
)
2461 int n_row
= isl_mat_rows(node
->sched
);
2463 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2464 1 + node
->nparam
, node
->nvar
);
2466 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2467 isl_mat_free(node
->cmap
);
2468 isl_mat_free(node
->cinv
);
2469 isl_mat_free(node
->ctrans
);
2470 node
->ctrans
= isl_mat_copy(Q
);
2471 node
->cmap
= isl_mat_transpose(Q
);
2472 node
->cinv
= isl_mat_transpose(U
);
2473 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2476 if (!node
->cmap
|| !node
->cinv
|| !node
->ctrans
|| node
->rank
< 0)
2481 /* Is "edge" marked as a validity or a conditional validity edge?
2483 static int is_any_validity(struct isl_sched_edge
*edge
)
2485 return is_validity(edge
) || is_conditional_validity(edge
);
2488 /* How many times should we count the constraints in "edge"?
2490 * If carry is set, then we are counting the number of
2491 * (validity or conditional validity) constraints that will be added
2492 * in setup_carry_lp and we count each edge exactly once.
2494 * Otherwise, we count as follows
2495 * validity -> 1 (>= 0)
2496 * validity+proximity -> 2 (>= 0 and upper bound)
2497 * proximity -> 2 (lower and upper bound)
2498 * local(+any) -> 2 (>= 0 and <= 0)
2500 * If an edge is only marked conditional_validity then it counts
2501 * as zero since it is only checked afterwards.
2503 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2504 * Otherwise, we ignore them.
2506 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
2507 int use_coincidence
)
2511 if (is_proximity(edge
) || is_local(edge
))
2513 if (use_coincidence
&& is_coincidence(edge
))
2515 if (is_validity(edge
))
2520 /* Count the number of equality and inequality constraints
2521 * that will be added for the given map.
2523 * "use_coincidence" is set if we should take into account coincidence edges.
2525 static int count_map_constraints(struct isl_sched_graph
*graph
,
2526 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2527 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
2529 isl_basic_set
*coef
;
2530 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
2537 if (edge
->src
== edge
->dst
)
2538 coef
= intra_coefficients(graph
, edge
->src
, map
);
2540 coef
= inter_coefficients(graph
, edge
, map
);
2543 *n_eq
+= f
* coef
->n_eq
;
2544 *n_ineq
+= f
* coef
->n_ineq
;
2545 isl_basic_set_free(coef
);
2550 /* Count the number of equality and inequality constraints
2551 * that will be added to the main lp problem.
2552 * We count as follows
2553 * validity -> 1 (>= 0)
2554 * validity+proximity -> 2 (>= 0 and upper bound)
2555 * proximity -> 2 (lower and upper bound)
2556 * local(+any) -> 2 (>= 0 and <= 0)
2558 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2559 * Otherwise, we ignore them.
2561 static int count_constraints(struct isl_sched_graph
*graph
,
2562 int *n_eq
, int *n_ineq
, int use_coincidence
)
2566 *n_eq
= *n_ineq
= 0;
2567 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2568 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2569 isl_map
*map
= isl_map_copy(edge
->map
);
2571 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2572 0, use_coincidence
) < 0)
2579 /* Count the number of constraints that will be added by
2580 * add_bound_constant_constraints to bound the values of the constant terms
2581 * and increment *n_eq and *n_ineq accordingly.
2583 * In practice, add_bound_constant_constraints only adds inequalities.
2585 static isl_stat
count_bound_constant_constraints(isl_ctx
*ctx
,
2586 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2588 if (isl_options_get_schedule_max_constant_term(ctx
) == -1)
2591 *n_ineq
+= graph
->n
;
2596 /* Add constraints to bound the values of the constant terms in the schedule,
2597 * if requested by the user.
2599 * The maximal value of the constant terms is defined by the option
2600 * "schedule_max_constant_term".
2602 * Within each node, the coefficients have the following order:
2604 * - c_i_n (if parametric)
2605 * - positive and negative parts of c_i_x
2607 static isl_stat
add_bound_constant_constraints(isl_ctx
*ctx
,
2608 struct isl_sched_graph
*graph
)
2614 max
= isl_options_get_schedule_max_constant_term(ctx
);
2618 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2620 for (i
= 0; i
< graph
->n
; ++i
) {
2621 struct isl_sched_node
*node
= &graph
->node
[i
];
2622 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2624 return isl_stat_error
;
2625 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2626 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2627 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2633 /* Count the number of constraints that will be added by
2634 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2637 * In practice, add_bound_coefficient_constraints only adds inequalities.
2639 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2640 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2644 if (isl_options_get_schedule_max_coefficient(ctx
) == -1 &&
2645 !isl_options_get_schedule_treat_coalescing(ctx
))
2648 for (i
= 0; i
< graph
->n
; ++i
)
2649 *n_ineq
+= graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2654 /* Add constraints to graph->lp that bound the values of
2655 * the parameter schedule coefficients of "node" to "max" and
2656 * the variable schedule coefficients to the corresponding entry
2658 * In either case, a negative value means that no bound needs to be imposed.
2660 * For parameter coefficients, this amounts to adding a constraint
2668 * The variables coefficients are, however, not represented directly.
2669 * Instead, the variables coefficients c_x are written as a linear
2670 * combination c_x = cmap c_z of some other coefficients c_z,
2671 * which are in turn encoded as c_z = c_z^+ - c_z^-.
2672 * Let a_j be the elements of row i of node->cmap, then
2674 * -max_i <= c_x_i <= max_i
2678 * -max_i <= \sum_j a_j (c_z_j^+ - c_z_j^-) <= max_i
2682 * -\sum_j a_j (c_z_j^+ - c_z_j^-) + max_i >= 0
2683 * \sum_j a_j (c_z_j^+ - c_z_j^-) + max_i >= 0
2685 static isl_stat
node_add_coefficient_constraints(isl_ctx
*ctx
,
2686 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
, int max
)
2692 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2694 for (j
= 0; j
< node
->nparam
; ++j
) {
2700 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2702 return isl_stat_error
;
2703 dim
= 1 + node
->start
+ 1 + j
;
2704 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2705 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2706 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2709 ineq
= isl_vec_alloc(ctx
, 1 + total
);
2710 ineq
= isl_vec_clr(ineq
);
2712 return isl_stat_error
;
2713 for (i
= 0; i
< node
->nvar
; ++i
) {
2714 int pos
= 1 + node_var_coef_offset(node
);
2716 if (isl_int_is_neg(node
->max
->el
[i
]))
2719 for (j
= 0; j
< node
->nvar
; ++j
) {
2720 isl_int_set(ineq
->el
[pos
+ 2 * j
],
2721 node
->cmap
->row
[i
][j
]);
2722 isl_int_neg(ineq
->el
[pos
+ 2 * j
+ 1],
2723 node
->cmap
->row
[i
][j
]);
2725 isl_int_set(ineq
->el
[0], node
->max
->el
[i
]);
2727 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2730 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2732 isl_seq_neg(ineq
->el
+ pos
, ineq
->el
+ pos
, 2 * node
->nvar
);
2733 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2736 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2743 return isl_stat_error
;
2746 /* Add constraints that bound the values of the variable and parameter
2747 * coefficients of the schedule.
2749 * The maximal value of the coefficients is defined by the option
2750 * 'schedule_max_coefficient' and the entries in node->max.
2751 * These latter entries are only set if either the schedule_max_coefficient
2752 * option or the schedule_treat_coalescing option is set.
2754 static isl_stat
add_bound_coefficient_constraints(isl_ctx
*ctx
,
2755 struct isl_sched_graph
*graph
)
2760 max
= isl_options_get_schedule_max_coefficient(ctx
);
2762 if (max
== -1 && !isl_options_get_schedule_treat_coalescing(ctx
))
2765 for (i
= 0; i
< graph
->n
; ++i
) {
2766 struct isl_sched_node
*node
= &graph
->node
[i
];
2768 if (node_add_coefficient_constraints(ctx
, graph
, node
, max
) < 0)
2769 return isl_stat_error
;
2775 /* Add a constraint to graph->lp that equates the value at position
2776 * "sum_pos" to the sum of the "n" values starting at "first".
2778 static isl_stat
add_sum_constraint(struct isl_sched_graph
*graph
,
2779 int sum_pos
, int first
, int n
)
2784 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2786 k
= isl_basic_set_alloc_equality(graph
->lp
);
2788 return isl_stat_error
;
2789 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2790 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2791 for (i
= 0; i
< n
; ++i
)
2792 isl_int_set_si(graph
->lp
->eq
[k
][1 + first
+ i
], 1);
2797 /* Add a constraint to graph->lp that equates the value at position
2798 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2800 * Within each node, the coefficients have the following order:
2802 * - c_i_n (if parametric)
2803 * - positive and negative parts of c_i_x
2805 static isl_stat
add_param_sum_constraint(struct isl_sched_graph
*graph
,
2811 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2813 k
= isl_basic_set_alloc_equality(graph
->lp
);
2815 return isl_stat_error
;
2816 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2817 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2818 for (i
= 0; i
< graph
->n
; ++i
) {
2819 int pos
= 1 + graph
->node
[i
].start
+ 1;
2821 for (j
= 0; j
< graph
->node
[i
].nparam
; ++j
)
2822 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2828 /* Add a constraint to graph->lp that equates the value at position
2829 * "sum_pos" to the sum of the variable coefficients of all nodes.
2831 * Within each node, the coefficients have the following order:
2833 * - c_i_n (if parametric)
2834 * - positive and negative parts of c_i_x
2836 static isl_stat
add_var_sum_constraint(struct isl_sched_graph
*graph
,
2842 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2844 k
= isl_basic_set_alloc_equality(graph
->lp
);
2846 return isl_stat_error
;
2847 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2848 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2849 for (i
= 0; i
< graph
->n
; ++i
) {
2850 struct isl_sched_node
*node
= &graph
->node
[i
];
2851 int pos
= 1 + node_var_coef_offset(node
);
2853 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2854 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2860 /* Construct an ILP problem for finding schedule coefficients
2861 * that result in non-negative, but small dependence distances
2862 * over all dependences.
2863 * In particular, the dependence distances over proximity edges
2864 * are bounded by m_0 + m_n n and we compute schedule coefficients
2865 * with small values (preferably zero) of m_n and m_0.
2867 * All variables of the ILP are non-negative. The actual coefficients
2868 * may be negative, so each coefficient is represented as the difference
2869 * of two non-negative variables. The negative part always appears
2870 * immediately before the positive part.
2871 * Other than that, the variables have the following order
2873 * - sum of positive and negative parts of m_n coefficients
2875 * - sum of all c_n coefficients
2876 * (unconstrained when computing non-parametric schedules)
2877 * - sum of positive and negative parts of all c_x coefficients
2878 * - positive and negative parts of m_n coefficients
2881 * - c_i_n (if parametric)
2882 * - positive and negative parts of c_i_x
2884 * The c_i_x are not represented directly, but through the columns of
2885 * node->cmap. That is, the computed values are for variable t_i_x
2886 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2888 * The constraints are those from the edges plus two or three equalities
2889 * to express the sums.
2891 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2892 * Otherwise, we ignore them.
2894 static isl_stat
setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2895 int use_coincidence
)
2905 parametric
= ctx
->opt
->schedule_parametric
;
2906 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2908 total
= param_pos
+ 2 * nparam
;
2909 for (i
= 0; i
< graph
->n
; ++i
) {
2910 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2911 if (node_update_cmap(node
) < 0)
2912 return isl_stat_error
;
2913 node
->start
= total
;
2914 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
2917 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2918 return isl_stat_error
;
2919 if (count_bound_constant_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2920 return isl_stat_error
;
2921 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2922 return isl_stat_error
;
2924 space
= isl_space_set_alloc(ctx
, 0, total
);
2925 isl_basic_set_free(graph
->lp
);
2926 n_eq
+= 2 + parametric
;
2928 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
2930 if (add_sum_constraint(graph
, 0, param_pos
, 2 * nparam
) < 0)
2931 return isl_stat_error
;
2932 if (parametric
&& add_param_sum_constraint(graph
, 2) < 0)
2933 return isl_stat_error
;
2934 if (add_var_sum_constraint(graph
, 3) < 0)
2935 return isl_stat_error
;
2936 if (add_bound_constant_constraints(ctx
, graph
) < 0)
2937 return isl_stat_error
;
2938 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2939 return isl_stat_error
;
2940 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2941 return isl_stat_error
;
2942 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2943 return isl_stat_error
;
2948 /* Analyze the conflicting constraint found by
2949 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2950 * constraint of one of the edges between distinct nodes, living, moreover
2951 * in distinct SCCs, then record the source and sink SCC as this may
2952 * be a good place to cut between SCCs.
2954 static int check_conflict(int con
, void *user
)
2957 struct isl_sched_graph
*graph
= user
;
2959 if (graph
->src_scc
>= 0)
2962 con
-= graph
->lp
->n_eq
;
2964 if (con
>= graph
->lp
->n_ineq
)
2967 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2968 if (!is_validity(&graph
->edge
[i
]))
2970 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2972 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2974 if (graph
->edge
[i
].start
> con
)
2976 if (graph
->edge
[i
].end
<= con
)
2978 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2979 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2985 /* Check whether the next schedule row of the given node needs to be
2986 * non-trivial. Lower-dimensional domains may have some trivial rows,
2987 * but as soon as the number of remaining required non-trivial rows
2988 * is as large as the number or remaining rows to be computed,
2989 * all remaining rows need to be non-trivial.
2991 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2993 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2996 /* Solve the ILP problem constructed in setup_lp.
2997 * For each node such that all the remaining rows of its schedule
2998 * need to be non-trivial, we construct a non-triviality region.
2999 * This region imposes that the next row is independent of previous rows.
3000 * In particular the coefficients c_i_x are represented by t_i_x
3001 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
3002 * its first columns span the rows of the previously computed part
3003 * of the schedule. The non-triviality region enforces that at least
3004 * one of the remaining components of t_i_x is non-zero, i.e.,
3005 * that the new schedule row depends on at least one of the remaining
3008 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
3014 for (i
= 0; i
< graph
->n
; ++i
) {
3015 struct isl_sched_node
*node
= &graph
->node
[i
];
3016 int skip
= node
->rank
;
3017 graph
->region
[i
].pos
= node_var_coef_offset(node
) + 2 * skip
;
3018 if (needs_row(graph
, node
))
3019 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
3021 graph
->region
[i
].len
= 0;
3023 lp
= isl_basic_set_copy(graph
->lp
);
3024 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
3025 graph
->region
, &check_conflict
, graph
);
3029 /* Extract the coefficients for the variables of "node" from "sol".
3031 * Within each node, the coefficients have the following order:
3033 * - c_i_n (if parametric)
3034 * - positive and negative parts of c_i_x
3036 * The c_i_x^- appear before their c_i_x^+ counterpart.
3038 * Return c_i_x = c_i_x^+ - c_i_x^-
3040 static __isl_give isl_vec
*extract_var_coef(struct isl_sched_node
*node
,
3041 __isl_keep isl_vec
*sol
)
3049 csol
= isl_vec_alloc(isl_vec_get_ctx(sol
), node
->nvar
);
3053 pos
= 1 + node_var_coef_offset(node
);
3054 for (i
= 0; i
< node
->nvar
; ++i
)
3055 isl_int_sub(csol
->el
[i
],
3056 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3061 /* Update the schedules of all nodes based on the given solution
3062 * of the LP problem.
3063 * The new row is added to the current band.
3064 * All possibly negative coefficients are encoded as a difference
3065 * of two non-negative variables, so we need to perform the subtraction
3066 * here. Moreover, if use_cmap is set, then the solution does
3067 * not refer to the actual coefficients c_i_x, but instead to variables
3068 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
3069 * In this case, we then also need to perform this multiplication
3070 * to obtain the values of c_i_x.
3072 * If coincident is set, then the caller guarantees that the new
3073 * row satisfies the coincidence constraints.
3075 static int update_schedule(struct isl_sched_graph
*graph
,
3076 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
3079 isl_vec
*csol
= NULL
;
3084 isl_die(sol
->ctx
, isl_error_internal
,
3085 "no solution found", goto error
);
3086 if (graph
->n_total_row
>= graph
->max_row
)
3087 isl_die(sol
->ctx
, isl_error_internal
,
3088 "too many schedule rows", goto error
);
3090 for (i
= 0; i
< graph
->n
; ++i
) {
3091 struct isl_sched_node
*node
= &graph
->node
[i
];
3092 int pos
= node
->start
;
3093 int row
= isl_mat_rows(node
->sched
);
3096 csol
= extract_var_coef(node
, sol
);
3100 isl_map_free(node
->sched_map
);
3101 node
->sched_map
= NULL
;
3102 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
3105 for (j
= 0; j
< 1 + node
->nparam
; ++j
)
3106 node
->sched
= isl_mat_set_element(node
->sched
,
3107 row
, j
, sol
->el
[1 + pos
+ j
]);
3109 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
3113 for (j
= 0; j
< node
->nvar
; ++j
)
3114 node
->sched
= isl_mat_set_element(node
->sched
,
3115 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
3116 node
->coincident
[graph
->n_total_row
] = coincident
;
3122 graph
->n_total_row
++;
3131 /* Convert row "row" of node->sched into an isl_aff living in "ls"
3132 * and return this isl_aff.
3134 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
3135 struct isl_sched_node
*node
, int row
)
3143 aff
= isl_aff_zero_on_domain(ls
);
3144 isl_mat_get_element(node
->sched
, row
, 0, &v
);
3145 aff
= isl_aff_set_constant(aff
, v
);
3146 for (j
= 0; j
< node
->nparam
; ++j
) {
3147 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
3148 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
3150 for (j
= 0; j
< node
->nvar
; ++j
) {
3151 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
3152 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
3160 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
3161 * and return this multi_aff.
3163 * The result is defined over the uncompressed node domain.
3165 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
3166 struct isl_sched_node
*node
, int first
, int n
)
3170 isl_local_space
*ls
;
3177 nrow
= isl_mat_rows(node
->sched
);
3178 if (node
->compressed
)
3179 space
= isl_multi_aff_get_domain_space(node
->decompress
);
3181 space
= isl_space_copy(node
->space
);
3182 ls
= isl_local_space_from_space(isl_space_copy(space
));
3183 space
= isl_space_from_domain(space
);
3184 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
3185 ma
= isl_multi_aff_zero(space
);
3187 for (i
= first
; i
< first
+ n
; ++i
) {
3188 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
3189 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
3192 isl_local_space_free(ls
);
3194 if (node
->compressed
)
3195 ma
= isl_multi_aff_pullback_multi_aff(ma
,
3196 isl_multi_aff_copy(node
->compress
));
3201 /* Convert node->sched into a multi_aff and return this multi_aff.
3203 * The result is defined over the uncompressed node domain.
3205 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
3206 struct isl_sched_node
*node
)
3210 nrow
= isl_mat_rows(node
->sched
);
3211 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
3214 /* Convert node->sched into a map and return this map.
3216 * The result is cached in node->sched_map, which needs to be released
3217 * whenever node->sched is updated.
3218 * It is defined over the uncompressed node domain.
3220 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
3222 if (!node
->sched_map
) {
3225 ma
= node_extract_schedule_multi_aff(node
);
3226 node
->sched_map
= isl_map_from_multi_aff(ma
);
3229 return isl_map_copy(node
->sched_map
);
3232 /* Construct a map that can be used to update a dependence relation
3233 * based on the current schedule.
3234 * That is, construct a map expressing that source and sink
3235 * are executed within the same iteration of the current schedule.
3236 * This map can then be intersected with the dependence relation.
3237 * This is not the most efficient way, but this shouldn't be a critical
3240 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
3241 struct isl_sched_node
*dst
)
3243 isl_map
*src_sched
, *dst_sched
;
3245 src_sched
= node_extract_schedule(src
);
3246 dst_sched
= node_extract_schedule(dst
);
3247 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
3250 /* Intersect the domains of the nested relations in domain and range
3251 * of "umap" with "map".
3253 static __isl_give isl_union_map
*intersect_domains(
3254 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
3256 isl_union_set
*uset
;
3258 umap
= isl_union_map_zip(umap
);
3259 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
3260 umap
= isl_union_map_intersect_domain(umap
, uset
);
3261 umap
= isl_union_map_zip(umap
);
3265 /* Update the dependence relation of the given edge based
3266 * on the current schedule.
3267 * If the dependence is carried completely by the current schedule, then
3268 * it is removed from the edge_tables. It is kept in the list of edges
3269 * as otherwise all edge_tables would have to be recomputed.
3271 static int update_edge(struct isl_sched_graph
*graph
,
3272 struct isl_sched_edge
*edge
)
3277 id
= specializer(edge
->src
, edge
->dst
);
3278 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
3282 if (edge
->tagged_condition
) {
3283 edge
->tagged_condition
=
3284 intersect_domains(edge
->tagged_condition
, id
);
3285 if (!edge
->tagged_condition
)
3288 if (edge
->tagged_validity
) {
3289 edge
->tagged_validity
=
3290 intersect_domains(edge
->tagged_validity
, id
);
3291 if (!edge
->tagged_validity
)
3295 empty
= isl_map_plain_is_empty(edge
->map
);
3299 graph_remove_edge(graph
, edge
);
3308 /* Does the domain of "umap" intersect "uset"?
3310 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3311 __isl_keep isl_union_set
*uset
)
3315 umap
= isl_union_map_copy(umap
);
3316 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3317 empty
= isl_union_map_is_empty(umap
);
3318 isl_union_map_free(umap
);
3320 return empty
< 0 ? -1 : !empty
;
3323 /* Does the range of "umap" intersect "uset"?
3325 static int range_intersects(__isl_keep isl_union_map
*umap
,
3326 __isl_keep isl_union_set
*uset
)
3330 umap
= isl_union_map_copy(umap
);
3331 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3332 empty
= isl_union_map_is_empty(umap
);
3333 isl_union_map_free(umap
);
3335 return empty
< 0 ? -1 : !empty
;
3338 /* Are the condition dependences of "edge" local with respect to
3339 * the current schedule?
3341 * That is, are domain and range of the condition dependences mapped
3342 * to the same point?
3344 * In other words, is the condition false?
3346 static int is_condition_false(struct isl_sched_edge
*edge
)
3348 isl_union_map
*umap
;
3349 isl_map
*map
, *sched
, *test
;
3352 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
3353 if (empty
< 0 || empty
)
3356 umap
= isl_union_map_copy(edge
->tagged_condition
);
3357 umap
= isl_union_map_zip(umap
);
3358 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3359 map
= isl_map_from_union_map(umap
);
3361 sched
= node_extract_schedule(edge
->src
);
3362 map
= isl_map_apply_domain(map
, sched
);
3363 sched
= node_extract_schedule(edge
->dst
);
3364 map
= isl_map_apply_range(map
, sched
);
3366 test
= isl_map_identity(isl_map_get_space(map
));
3367 local
= isl_map_is_subset(map
, test
);
3374 /* For each conditional validity constraint that is adjacent
3375 * to a condition with domain in condition_source or range in condition_sink,
3376 * turn it into an unconditional validity constraint.
3378 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
3379 __isl_take isl_union_set
*condition_source
,
3380 __isl_take isl_union_set
*condition_sink
)
3384 condition_source
= isl_union_set_coalesce(condition_source
);
3385 condition_sink
= isl_union_set_coalesce(condition_sink
);
3387 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3389 isl_union_map
*validity
;
3391 if (!is_conditional_validity(&graph
->edge
[i
]))
3393 if (is_validity(&graph
->edge
[i
]))
3396 validity
= graph
->edge
[i
].tagged_validity
;
3397 adjacent
= domain_intersects(validity
, condition_sink
);
3398 if (adjacent
>= 0 && !adjacent
)
3399 adjacent
= range_intersects(validity
, condition_source
);
3405 set_validity(&graph
->edge
[i
]);
3408 isl_union_set_free(condition_source
);
3409 isl_union_set_free(condition_sink
);
3412 isl_union_set_free(condition_source
);
3413 isl_union_set_free(condition_sink
);
3417 /* Update the dependence relations of all edges based on the current schedule
3418 * and enforce conditional validity constraints that are adjacent
3419 * to satisfied condition constraints.
3421 * First check if any of the condition constraints are satisfied
3422 * (i.e., not local to the outer schedule) and keep track of
3423 * their domain and range.
3424 * Then update all dependence relations (which removes the non-local
3426 * Finally, if any condition constraints turned out to be satisfied,
3427 * then turn all adjacent conditional validity constraints into
3428 * unconditional validity constraints.
3430 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3434 isl_union_set
*source
, *sink
;
3436 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3437 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3438 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3440 isl_union_set
*uset
;
3441 isl_union_map
*umap
;
3443 if (!is_condition(&graph
->edge
[i
]))
3445 if (is_local(&graph
->edge
[i
]))
3447 local
= is_condition_false(&graph
->edge
[i
]);
3455 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3456 uset
= isl_union_map_domain(umap
);
3457 source
= isl_union_set_union(source
, uset
);
3459 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3460 uset
= isl_union_map_range(umap
);
3461 sink
= isl_union_set_union(sink
, uset
);
3464 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
3465 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
3470 return unconditionalize_adjacent_validity(graph
, source
, sink
);
3472 isl_union_set_free(source
);
3473 isl_union_set_free(sink
);
3476 isl_union_set_free(source
);
3477 isl_union_set_free(sink
);
3481 static void next_band(struct isl_sched_graph
*graph
)
3483 graph
->band_start
= graph
->n_total_row
;
3486 /* Return the union of the universe domains of the nodes in "graph"
3487 * that satisfy "pred".
3489 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
3490 struct isl_sched_graph
*graph
,
3491 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
3497 for (i
= 0; i
< graph
->n
; ++i
)
3498 if (pred(&graph
->node
[i
], data
))
3502 isl_die(ctx
, isl_error_internal
,
3503 "empty component", return NULL
);
3505 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3506 dom
= isl_union_set_from_set(set
);
3508 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
3509 if (!pred(&graph
->node
[i
], data
))
3511 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3512 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
3518 /* Return a list of unions of universe domains, where each element
3519 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3521 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
3522 struct isl_sched_graph
*graph
)
3525 isl_union_set_list
*filters
;
3527 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
3528 for (i
= 0; i
< graph
->scc
; ++i
) {
3531 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
3532 filters
= isl_union_set_list_add(filters
, dom
);
3538 /* Return a list of two unions of universe domains, one for the SCCs up
3539 * to and including graph->src_scc and another for the other SCCs.
3541 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
3542 struct isl_sched_graph
*graph
)
3545 isl_union_set_list
*filters
;
3547 filters
= isl_union_set_list_alloc(ctx
, 2);
3548 dom
= isl_sched_graph_domain(ctx
, graph
,
3549 &node_scc_at_most
, graph
->src_scc
);
3550 filters
= isl_union_set_list_add(filters
, dom
);
3551 dom
= isl_sched_graph_domain(ctx
, graph
,
3552 &node_scc_at_least
, graph
->src_scc
+ 1);
3553 filters
= isl_union_set_list_add(filters
, dom
);
3558 /* Copy nodes that satisfy node_pred from the src dependence graph
3559 * to the dst dependence graph.
3561 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
3562 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
3567 for (i
= 0; i
< src
->n
; ++i
) {
3570 if (!node_pred(&src
->node
[i
], data
))
3574 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
3575 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
3576 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
3577 dst
->node
[j
].compress
=
3578 isl_multi_aff_copy(src
->node
[i
].compress
);
3579 dst
->node
[j
].decompress
=
3580 isl_multi_aff_copy(src
->node
[i
].decompress
);
3581 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
3582 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
3583 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
3584 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
3585 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
3586 dst
->node
[j
].sizes
= isl_multi_val_copy(src
->node
[i
].sizes
);
3587 dst
->node
[j
].max
= isl_vec_copy(src
->node
[i
].max
);
3590 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
3592 if (dst
->node
[j
].compressed
&&
3593 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
3594 !dst
->node
[j
].decompress
))
3601 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3602 * to the dst dependence graph.
3603 * If the source or destination node of the edge is not in the destination
3604 * graph, then it must be a backward proximity edge and it should simply
3607 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3608 struct isl_sched_graph
*src
,
3609 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3612 enum isl_edge_type t
;
3615 for (i
= 0; i
< src
->n_edge
; ++i
) {
3616 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3618 isl_union_map
*tagged_condition
;
3619 isl_union_map
*tagged_validity
;
3620 struct isl_sched_node
*dst_src
, *dst_dst
;
3622 if (!edge_pred(edge
, data
))
3625 if (isl_map_plain_is_empty(edge
->map
))
3628 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
3629 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
3630 if (!dst_src
|| !dst_dst
) {
3631 if (is_validity(edge
) || is_conditional_validity(edge
))
3632 isl_die(ctx
, isl_error_internal
,
3633 "backward (conditional) validity edge",
3638 map
= isl_map_copy(edge
->map
);
3639 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3640 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3642 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3643 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3644 dst
->edge
[dst
->n_edge
].map
= map
;
3645 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3646 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3647 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3650 if (edge
->tagged_condition
&& !tagged_condition
)
3652 if (edge
->tagged_validity
&& !tagged_validity
)
3655 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
3657 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
3659 if (graph_edge_table_add(ctx
, dst
, t
,
3660 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3668 /* Compute the maximal number of variables over all nodes.
3669 * This is the maximal number of linearly independent schedule
3670 * rows that we need to compute.
3671 * Just in case we end up in a part of the dependence graph
3672 * with only lower-dimensional domains, we make sure we will
3673 * compute the required amount of extra linearly independent rows.
3675 static int compute_maxvar(struct isl_sched_graph
*graph
)
3680 for (i
= 0; i
< graph
->n
; ++i
) {
3681 struct isl_sched_node
*node
= &graph
->node
[i
];
3684 if (node_update_cmap(node
) < 0)
3686 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3687 if (nvar
> graph
->maxvar
)
3688 graph
->maxvar
= nvar
;
3694 /* Extract the subgraph of "graph" that consists of the node satisfying
3695 * "node_pred" and the edges satisfying "edge_pred" and store
3696 * the result in "sub".
3698 static int extract_sub_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3699 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3700 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3701 int data
, struct isl_sched_graph
*sub
)
3703 int i
, n
= 0, n_edge
= 0;
3706 for (i
= 0; i
< graph
->n
; ++i
)
3707 if (node_pred(&graph
->node
[i
], data
))
3709 for (i
= 0; i
< graph
->n_edge
; ++i
)
3710 if (edge_pred(&graph
->edge
[i
], data
))
3712 if (graph_alloc(ctx
, sub
, n
, n_edge
) < 0)
3714 if (copy_nodes(sub
, graph
, node_pred
, data
) < 0)
3716 if (graph_init_table(ctx
, sub
) < 0)
3718 for (t
= 0; t
<= isl_edge_last
; ++t
)
3719 sub
->max_edge
[t
] = graph
->max_edge
[t
];
3720 if (graph_init_edge_tables(ctx
, sub
) < 0)
3722 if (copy_edges(ctx
, sub
, graph
, edge_pred
, data
) < 0)
3724 sub
->n_row
= graph
->n_row
;
3725 sub
->max_row
= graph
->max_row
;
3726 sub
->n_total_row
= graph
->n_total_row
;
3727 sub
->band_start
= graph
->band_start
;
3732 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3733 struct isl_sched_graph
*graph
);
3734 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3735 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3737 /* Compute a schedule for a subgraph of "graph". In particular, for
3738 * the graph composed of nodes that satisfy node_pred and edges that
3739 * that satisfy edge_pred.
3740 * If the subgraph is known to consist of a single component, then wcc should
3741 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3742 * Otherwise, we call compute_schedule, which will check whether the subgraph
3745 * The schedule is inserted at "node" and the updated schedule node
3748 static __isl_give isl_schedule_node
*compute_sub_schedule(
3749 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3750 struct isl_sched_graph
*graph
,
3751 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3752 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3755 struct isl_sched_graph split
= { 0 };
3757 if (extract_sub_graph(ctx
, graph
, node_pred
, edge_pred
, data
,
3762 node
= compute_schedule_wcc(node
, &split
);
3764 node
= compute_schedule(node
, &split
);
3766 graph_free(ctx
, &split
);
3769 graph_free(ctx
, &split
);
3770 return isl_schedule_node_free(node
);
3773 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3775 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3778 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3780 return edge
->dst
->scc
<= scc
;
3783 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3785 return edge
->src
->scc
>= scc
;
3788 /* Reset the current band by dropping all its schedule rows.
3790 static int reset_band(struct isl_sched_graph
*graph
)
3795 drop
= graph
->n_total_row
- graph
->band_start
;
3796 graph
->n_total_row
-= drop
;
3797 graph
->n_row
-= drop
;
3799 for (i
= 0; i
< graph
->n
; ++i
) {
3800 struct isl_sched_node
*node
= &graph
->node
[i
];
3802 isl_map_free(node
->sched_map
);
3803 node
->sched_map
= NULL
;
3805 node
->sched
= isl_mat_drop_rows(node
->sched
,
3806 graph
->band_start
, drop
);
3815 /* Split the current graph into two parts and compute a schedule for each
3816 * part individually. In particular, one part consists of all SCCs up
3817 * to and including graph->src_scc, while the other part contains the other
3818 * SCCs. The split is enforced by a sequence node inserted at position "node"
3819 * in the schedule tree. Return the updated schedule node.
3820 * If either of these two parts consists of a sequence, then it is spliced
3821 * into the sequence containing the two parts.
3823 * The current band is reset. It would be possible to reuse
3824 * the previously computed rows as the first rows in the next
3825 * band, but recomputing them may result in better rows as we are looking
3826 * at a smaller part of the dependence graph.
3828 static __isl_give isl_schedule_node
*compute_split_schedule(
3829 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3833 isl_union_set_list
*filters
;
3838 if (reset_band(graph
) < 0)
3839 return isl_schedule_node_free(node
);
3843 ctx
= isl_schedule_node_get_ctx(node
);
3844 filters
= extract_split(ctx
, graph
);
3845 node
= isl_schedule_node_insert_sequence(node
, filters
);
3846 node
= isl_schedule_node_child(node
, 1);
3847 node
= isl_schedule_node_child(node
, 0);
3849 node
= compute_sub_schedule(node
, ctx
, graph
,
3850 &node_scc_at_least
, &edge_src_scc_at_least
,
3851 graph
->src_scc
+ 1, 0);
3852 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3853 node
= isl_schedule_node_parent(node
);
3854 node
= isl_schedule_node_parent(node
);
3856 node
= isl_schedule_node_sequence_splice_child(node
, 1);
3857 node
= isl_schedule_node_child(node
, 0);
3858 node
= isl_schedule_node_child(node
, 0);
3859 node
= compute_sub_schedule(node
, ctx
, graph
,
3860 &node_scc_at_most
, &edge_dst_scc_at_most
,
3862 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3863 node
= isl_schedule_node_parent(node
);
3864 node
= isl_schedule_node_parent(node
);
3866 node
= isl_schedule_node_sequence_splice_child(node
, 0);
3871 /* Insert a band node at position "node" in the schedule tree corresponding
3872 * to the current band in "graph". Mark the band node permutable
3873 * if "permutable" is set.
3874 * The partial schedules and the coincidence property are extracted
3875 * from the graph nodes.
3876 * Return the updated schedule node.
3878 static __isl_give isl_schedule_node
*insert_current_band(
3879 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3885 isl_multi_pw_aff
*mpa
;
3886 isl_multi_union_pw_aff
*mupa
;
3892 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3893 "graph should have at least one node",
3894 return isl_schedule_node_free(node
));
3896 start
= graph
->band_start
;
3897 end
= graph
->n_total_row
;
3900 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3901 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3902 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3904 for (i
= 1; i
< graph
->n
; ++i
) {
3905 isl_multi_union_pw_aff
*mupa_i
;
3907 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3909 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3910 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3911 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3913 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3915 for (i
= 0; i
< n
; ++i
)
3916 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3917 graph
->node
[0].coincident
[start
+ i
]);
3918 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3923 /* Update the dependence relations based on the current schedule,
3924 * add the current band to "node" and then continue with the computation
3926 * Return the updated schedule node.
3928 static __isl_give isl_schedule_node
*compute_next_band(
3929 __isl_take isl_schedule_node
*node
,
3930 struct isl_sched_graph
*graph
, int permutable
)
3937 ctx
= isl_schedule_node_get_ctx(node
);
3938 if (update_edges(ctx
, graph
) < 0)
3939 return isl_schedule_node_free(node
);
3940 node
= insert_current_band(node
, graph
, permutable
);
3943 node
= isl_schedule_node_child(node
, 0);
3944 node
= compute_schedule(node
, graph
);
3945 node
= isl_schedule_node_parent(node
);
3950 /* Add constraints to graph->lp that force the dependence "map" (which
3951 * is part of the dependence relation of "edge")
3952 * to be respected and attempt to carry it, where the edge is one from
3953 * a node j to itself. "pos" is the sequence number of the given map.
3954 * That is, add constraints that enforce
3956 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3957 * = c_j_x (y - x) >= e_i
3959 * for each (x,y) in R.
3960 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3961 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3962 * with each coefficient in c_j_x represented as a pair of non-negative
3965 static int add_intra_constraints(struct isl_sched_graph
*graph
,
3966 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3969 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3970 isl_dim_map
*dim_map
;
3971 isl_basic_set
*coef
;
3972 struct isl_sched_node
*node
= edge
->src
;
3974 coef
= intra_coefficients(graph
, node
, map
);
3978 offset
= coef_var_offset(coef
);
3979 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
3980 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3981 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3982 coef
->n_eq
, coef
->n_ineq
);
3983 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3989 /* Add constraints to graph->lp that force the dependence "map" (which
3990 * is part of the dependence relation of "edge")
3991 * to be respected and attempt to carry it, where the edge is one from
3992 * node j to node k. "pos" is the sequence number of the given map.
3993 * That is, add constraints that enforce
3995 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3997 * for each (x,y) in R.
3998 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3999 * of valid constraints for R and then plug in
4000 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
4001 * with each coefficient (except e_i, c_*_0 and c_*_n)
4002 * represented as a pair of non-negative coefficients.
4004 static int add_inter_constraints(struct isl_sched_graph
*graph
,
4005 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
4008 isl_ctx
*ctx
= isl_map_get_ctx(map
);
4009 isl_dim_map
*dim_map
;
4010 isl_basic_set
*coef
;
4011 struct isl_sched_node
*src
= edge
->src
;
4012 struct isl_sched_node
*dst
= edge
->dst
;
4014 coef
= inter_coefficients(graph
, edge
, map
);
4018 offset
= coef_var_offset(coef
);
4019 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
4020 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
4021 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
4022 coef
->n_eq
, coef
->n_ineq
);
4023 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
4029 /* Add constraints to graph->lp that force all (conditional) validity
4030 * dependences to be respected and attempt to carry them.
4032 static int add_all_constraints(struct isl_sched_graph
*graph
)
4038 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4039 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4041 if (!is_any_validity(edge
))
4044 for (j
= 0; j
< edge
->map
->n
; ++j
) {
4045 isl_basic_map
*bmap
;
4048 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
4049 map
= isl_map_from_basic_map(bmap
);
4051 if (edge
->src
== edge
->dst
&&
4052 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
4054 if (edge
->src
!= edge
->dst
&&
4055 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
4064 /* Count the number of equality and inequality constraints
4065 * that will be added to the carry_lp problem.
4066 * We count each edge exactly once.
4068 static int count_all_constraints(struct isl_sched_graph
*graph
,
4069 int *n_eq
, int *n_ineq
)
4073 *n_eq
= *n_ineq
= 0;
4074 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4075 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4077 if (!is_any_validity(edge
))
4080 for (j
= 0; j
< edge
->map
->n
; ++j
) {
4081 isl_basic_map
*bmap
;
4084 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
4085 map
= isl_map_from_basic_map(bmap
);
4087 if (count_map_constraints(graph
, edge
, map
,
4088 n_eq
, n_ineq
, 1, 0) < 0)
4096 /* Construct an LP problem for finding schedule coefficients
4097 * such that the schedule carries as many dependences as possible.
4098 * In particular, for each dependence i, we bound the dependence distance
4099 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
4100 * of all e_i's. Dependences with e_i = 0 in the solution are simply
4101 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
4102 * Note that if the dependence relation is a union of basic maps,
4103 * then we have to consider each basic map individually as it may only
4104 * be possible to carry the dependences expressed by some of those
4105 * basic maps and not all of them.
4106 * Below, we consider each of those basic maps as a separate "edge".
4108 * All variables of the LP are non-negative. The actual coefficients
4109 * may be negative, so each coefficient is represented as the difference
4110 * of two non-negative variables. The negative part always appears
4111 * immediately before the positive part.
4112 * Other than that, the variables have the following order
4114 * - sum of (1 - e_i) over all edges
4115 * - sum of all c_n coefficients
4116 * (unconstrained when computing non-parametric schedules)
4117 * - sum of positive and negative parts of all c_x coefficients
4122 * - c_i_n (if parametric)
4123 * - positive and negative parts of c_i_x
4125 * The constraints are those from the (validity) edges plus three equalities
4126 * to express the sums and n_edge inequalities to express e_i <= 1.
4128 static isl_stat
setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4138 for (i
= 0; i
< graph
->n_edge
; ++i
)
4139 n_edge
+= graph
->edge
[i
].map
->n
;
4142 for (i
= 0; i
< graph
->n
; ++i
) {
4143 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
4144 node
->start
= total
;
4145 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
4148 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
4149 return isl_stat_error
;
4151 dim
= isl_space_set_alloc(ctx
, 0, total
);
4152 isl_basic_set_free(graph
->lp
);
4155 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
4156 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
4158 k
= isl_basic_set_alloc_equality(graph
->lp
);
4160 return isl_stat_error
;
4161 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
4162 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
4163 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
4164 for (i
= 0; i
< n_edge
; ++i
)
4165 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
4167 if (add_param_sum_constraint(graph
, 1) < 0)
4168 return isl_stat_error
;
4169 if (add_var_sum_constraint(graph
, 2) < 0)
4170 return isl_stat_error
;
4172 for (i
= 0; i
< n_edge
; ++i
) {
4173 k
= isl_basic_set_alloc_inequality(graph
->lp
);
4175 return isl_stat_error
;
4176 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
4177 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
4178 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
4181 if (add_all_constraints(graph
) < 0)
4182 return isl_stat_error
;
4187 static __isl_give isl_schedule_node
*compute_component_schedule(
4188 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4191 /* Comparison function for sorting the statements based on
4192 * the corresponding value in "r".
4194 static int smaller_value(const void *a
, const void *b
, void *data
)
4200 return isl_int_cmp(r
->el
[*i1
], r
->el
[*i2
]);
4203 /* If the schedule_split_scaled option is set and if the linear
4204 * parts of the scheduling rows for all nodes in the graphs have
4205 * a non-trivial common divisor, then split off the remainder of the
4206 * constant term modulo this common divisor from the linear part.
4207 * Otherwise, insert a band node directly and continue with
4208 * the construction of the schedule.
4210 * If a non-trivial common divisor is found, then
4211 * the linear part is reduced and the remainder is enforced
4212 * by a sequence node with the children placed in the order
4213 * of this remainder.
4214 * In particular, we assign an scc index based on the remainder and
4215 * then rely on compute_component_schedule to insert the sequence and
4216 * to continue the schedule construction on each part.
4218 static __isl_give isl_schedule_node
*split_scaled(
4219 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4232 ctx
= isl_schedule_node_get_ctx(node
);
4233 if (!ctx
->opt
->schedule_split_scaled
)
4234 return compute_next_band(node
, graph
, 0);
4236 return compute_next_band(node
, graph
, 0);
4239 isl_int_init(gcd_i
);
4241 isl_int_set_si(gcd
, 0);
4243 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
4245 for (i
= 0; i
< graph
->n
; ++i
) {
4246 struct isl_sched_node
*node
= &graph
->node
[i
];
4247 int cols
= isl_mat_cols(node
->sched
);
4249 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
4250 isl_int_gcd(gcd
, gcd
, gcd_i
);
4253 isl_int_clear(gcd_i
);
4255 if (isl_int_cmp_si(gcd
, 1) <= 0) {
4257 return compute_next_band(node
, graph
, 0);
4260 r
= isl_vec_alloc(ctx
, graph
->n
);
4261 order
= isl_calloc_array(ctx
, int, graph
->n
);
4265 for (i
= 0; i
< graph
->n
; ++i
) {
4266 struct isl_sched_node
*node
= &graph
->node
[i
];
4269 isl_int_fdiv_r(r
->el
[i
], node
->sched
->row
[row
][0], gcd
);
4270 isl_int_fdiv_q(node
->sched
->row
[row
][0],
4271 node
->sched
->row
[row
][0], gcd
);
4272 isl_int_mul(node
->sched
->row
[row
][0],
4273 node
->sched
->row
[row
][0], gcd
);
4274 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
4279 if (isl_sort(order
, graph
->n
, sizeof(order
[0]), &smaller_value
, r
) < 0)
4283 for (i
= 0; i
< graph
->n
; ++i
) {
4284 if (i
> 0 && isl_int_ne(r
->el
[order
[i
- 1]], r
->el
[order
[i
]]))
4286 graph
->node
[order
[i
]].scc
= scc
;
4295 if (update_edges(ctx
, graph
) < 0)
4296 return isl_schedule_node_free(node
);
4297 node
= insert_current_band(node
, graph
, 0);
4300 node
= isl_schedule_node_child(node
, 0);
4301 node
= compute_component_schedule(node
, graph
, 0);
4302 node
= isl_schedule_node_parent(node
);
4309 return isl_schedule_node_free(node
);
4312 /* Is the schedule row "sol" trivial on node "node"?
4313 * That is, is the solution zero on the dimensions orthogonal to
4314 * the previously found solutions?
4315 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
4317 * Each coefficient is represented as the difference between
4318 * two non-negative values in "sol". "sol" has been computed
4319 * in terms of the original iterators (i.e., without use of cmap).
4320 * We construct the schedule row s and write it as a linear
4321 * combination of (linear combinations of) previously computed schedule rows.
4322 * s = Q c or c = U s.
4323 * If the final entries of c are all zero, then the solution is trivial.
4325 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
4332 if (node
->nvar
== node
->rank
)
4335 node_sol
= extract_var_coef(node
, sol
);
4336 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
4340 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
4341 node
->nvar
- node
->rank
) == -1;
4343 isl_vec_free(node_sol
);
4348 /* Is the schedule row "sol" trivial on any node where it should
4350 * "sol" has been computed in terms of the original iterators
4351 * (i.e., without use of cmap).
4352 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4354 static int is_any_trivial(struct isl_sched_graph
*graph
,
4355 __isl_keep isl_vec
*sol
)
4359 for (i
= 0; i
< graph
->n
; ++i
) {
4360 struct isl_sched_node
*node
= &graph
->node
[i
];
4363 if (!needs_row(graph
, node
))
4365 trivial
= is_trivial(node
, sol
);
4366 if (trivial
< 0 || trivial
)
4373 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
4374 * If so, return the position of the coalesced dimension.
4375 * Otherwise, return node->nvar or -1 on error.
4377 * In particular, look for pairs of coefficients c_i and c_j such that
4378 * |c_j/c_i| >= size_i, i.e., |c_j| >= |c_i * size_i|.
4379 * If any such pair is found, then return i.
4380 * If size_i is infinity, then no check on c_i needs to be performed.
4382 static int find_node_coalescing(struct isl_sched_node
*node
,
4383 __isl_keep isl_vec
*sol
)
4389 if (node
->nvar
<= 1)
4392 csol
= extract_var_coef(node
, sol
);
4396 for (i
= 0; i
< node
->nvar
; ++i
) {
4399 if (isl_int_is_zero(csol
->el
[i
]))
4401 v
= isl_multi_val_get_val(node
->sizes
, i
);
4404 if (!isl_val_is_int(v
)) {
4408 isl_int_mul(max
, v
->n
, csol
->el
[i
]);
4411 for (j
= 0; j
< node
->nvar
; ++j
) {
4414 if (isl_int_abs_ge(csol
->el
[j
], max
))
4430 /* Force the schedule coefficient at position "pos" of "node" to be zero
4432 * The coefficient is encoded as the difference between two non-negative
4433 * variables. Force these two variables to have the same value.
4435 static __isl_give isl_tab_lexmin
*zero_out_node_coef(
4436 __isl_take isl_tab_lexmin
*tl
, struct isl_sched_node
*node
, int pos
)
4442 ctx
= isl_space_get_ctx(node
->space
);
4443 dim
= isl_tab_lexmin_dim(tl
);
4445 return isl_tab_lexmin_free(tl
);
4446 eq
= isl_vec_alloc(ctx
, 1 + dim
);
4447 eq
= isl_vec_clr(eq
);
4449 return isl_tab_lexmin_free(tl
);
4451 pos
= 1 + node_var_coef_offset(node
) + 2 * pos
;
4452 isl_int_set_si(eq
->el
[pos
], 1);
4453 isl_int_set_si(eq
->el
[pos
+ 1], -1);
4454 tl
= isl_tab_lexmin_add_eq(tl
, eq
->el
);
4460 /* Return the lexicographically smallest rational point in the basic set
4461 * from which "tl" was constructed, double checking that this input set
4464 static __isl_give isl_vec
*non_empty_solution(__isl_keep isl_tab_lexmin
*tl
)
4468 sol
= isl_tab_lexmin_get_solution(tl
);
4472 isl_die(isl_vec_get_ctx(sol
), isl_error_internal
,
4473 "error in schedule construction",
4474 return isl_vec_free(sol
));
4478 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4479 * carry any of the "n_edge" groups of dependences?
4480 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4481 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4482 * by the edge are carried by the solution.
4483 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4484 * one of those is carried.
4486 * Note that despite the fact that the problem is solved using a rational
4487 * solver, the solution is guaranteed to be integral.
4488 * Specifically, the dependence distance lower bounds e_i (and therefore
4489 * also their sum) are integers. See Lemma 5 of [1].
4491 * Any potential denominator of the sum is cleared by this function.
4492 * The denominator is not relevant for any of the other elements
4495 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4496 * Problem, Part II: Multi-Dimensional Time.
4497 * In Intl. Journal of Parallel Programming, 1992.
4499 static int carries_dependences(__isl_keep isl_vec
*sol
, int n_edge
)
4501 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
4502 isl_int_set_si(sol
->el
[0], 1);
4503 return isl_int_cmp_si(sol
->el
[1], n_edge
) < 0;
4506 /* Return the lexicographically smallest rational point in "lp",
4507 * assuming that all variables are non-negative and performing some
4508 * additional sanity checks.
4509 * In particular, "lp" should not be empty by construction.
4510 * Double check that this is the case.
4511 * Also, check that dependences are carried for at least one of
4512 * the "n_edge" edges.
4514 * If the computed schedule performs loop coalescing on a given node,
4515 * i.e., if it is of the form
4517 * c_i i + c_j j + ...
4519 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4520 * to cut out this solution. Repeat this process until no more loop
4521 * coalescing occurs or until no more dependences can be carried.
4522 * In the latter case, revert to the previously computed solution.
4524 static __isl_give isl_vec
*non_neg_lexmin(struct isl_sched_graph
*graph
,
4525 __isl_take isl_basic_set
*lp
, int n_edge
)
4530 isl_vec
*sol
, *prev
= NULL
;
4531 int treat_coalescing
;
4535 ctx
= isl_basic_set_get_ctx(lp
);
4536 treat_coalescing
= isl_options_get_schedule_treat_coalescing(ctx
);
4537 tl
= isl_tab_lexmin_from_basic_set(lp
);
4540 sol
= non_empty_solution(tl
);
4544 if (!carries_dependences(sol
, n_edge
)) {
4546 isl_die(ctx
, isl_error_unknown
,
4547 "unable to carry dependences",
4553 prev
= isl_vec_free(prev
);
4554 if (!treat_coalescing
)
4556 for (i
= 0; i
< graph
->n
; ++i
) {
4557 struct isl_sched_node
*node
= &graph
->node
[i
];
4559 pos
= find_node_coalescing(node
, sol
);
4562 if (pos
< node
->nvar
)
4567 tl
= zero_out_node_coef(tl
, &graph
->node
[i
], pos
);
4569 } while (i
< graph
->n
);
4571 isl_tab_lexmin_free(tl
);
4575 isl_tab_lexmin_free(tl
);
4581 /* Construct a schedule row for each node such that as many dependences
4582 * as possible are carried and then continue with the next band.
4584 * If the computed schedule row turns out to be trivial on one or
4585 * more nodes where it should not be trivial, then we throw it away
4586 * and try again on each component separately.
4588 * If there is only one component, then we accept the schedule row anyway,
4589 * but we do not consider it as a complete row and therefore do not
4590 * increment graph->n_row. Note that the ranks of the nodes that
4591 * do get a non-trivial schedule part will get updated regardless and
4592 * graph->maxvar is computed based on these ranks. The test for
4593 * whether more schedule rows are required in compute_schedule_wcc
4594 * is therefore not affected.
4596 * Insert a band corresponding to the schedule row at position "node"
4597 * of the schedule tree and continue with the construction of the schedule.
4598 * This insertion and the continued construction is performed by split_scaled
4599 * after optionally checking for non-trivial common divisors.
4601 static __isl_give isl_schedule_node
*carry_dependences(
4602 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4615 for (i
= 0; i
< graph
->n_edge
; ++i
)
4616 n_edge
+= graph
->edge
[i
].map
->n
;
4618 ctx
= isl_schedule_node_get_ctx(node
);
4619 if (setup_carry_lp(ctx
, graph
) < 0)
4620 return isl_schedule_node_free(node
);
4622 lp
= isl_basic_set_copy(graph
->lp
);
4623 sol
= non_neg_lexmin(graph
, lp
, n_edge
);
4625 return isl_schedule_node_free(node
);
4627 trivial
= is_any_trivial(graph
, sol
);
4629 sol
= isl_vec_free(sol
);
4630 } else if (trivial
&& graph
->scc
> 1) {
4632 return compute_component_schedule(node
, graph
, 1);
4635 if (update_schedule(graph
, sol
, 0, 0) < 0)
4636 return isl_schedule_node_free(node
);
4640 return split_scaled(node
, graph
);
4643 /* Topologically sort statements mapped to the same schedule iteration
4644 * and add insert a sequence node in front of "node"
4645 * corresponding to this order.
4646 * If "initialized" is set, then it may be assumed that compute_maxvar
4647 * has been called on the current band. Otherwise, call
4648 * compute_maxvar if and before carry_dependences gets called.
4650 * If it turns out to be impossible to sort the statements apart,
4651 * because different dependences impose different orderings
4652 * on the statements, then we extend the schedule such that
4653 * it carries at least one more dependence.
4655 static __isl_give isl_schedule_node
*sort_statements(
4656 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4660 isl_union_set_list
*filters
;
4665 ctx
= isl_schedule_node_get_ctx(node
);
4667 isl_die(ctx
, isl_error_internal
,
4668 "graph should have at least one node",
4669 return isl_schedule_node_free(node
));
4674 if (update_edges(ctx
, graph
) < 0)
4675 return isl_schedule_node_free(node
);
4677 if (graph
->n_edge
== 0)
4680 if (detect_sccs(ctx
, graph
) < 0)
4681 return isl_schedule_node_free(node
);
4684 if (graph
->scc
< graph
->n
) {
4685 if (!initialized
&& compute_maxvar(graph
) < 0)
4686 return isl_schedule_node_free(node
);
4687 return carry_dependences(node
, graph
);
4690 filters
= extract_sccs(ctx
, graph
);
4691 node
= isl_schedule_node_insert_sequence(node
, filters
);
4696 /* Are there any (non-empty) (conditional) validity edges in the graph?
4698 static int has_validity_edges(struct isl_sched_graph
*graph
)
4702 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4705 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
4710 if (is_any_validity(&graph
->edge
[i
]))
4717 /* Should we apply a Feautrier step?
4718 * That is, did the user request the Feautrier algorithm and are
4719 * there any validity dependences (left)?
4721 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4723 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
4726 return has_validity_edges(graph
);
4729 /* Compute a schedule for a connected dependence graph using Feautrier's
4730 * multi-dimensional scheduling algorithm and return the updated schedule node.
4732 * The original algorithm is described in [1].
4733 * The main idea is to minimize the number of scheduling dimensions, by
4734 * trying to satisfy as many dependences as possible per scheduling dimension.
4736 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4737 * Problem, Part II: Multi-Dimensional Time.
4738 * In Intl. Journal of Parallel Programming, 1992.
4740 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
4741 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4743 return carry_dependences(node
, graph
);
4746 /* Turn off the "local" bit on all (condition) edges.
4748 static void clear_local_edges(struct isl_sched_graph
*graph
)
4752 for (i
= 0; i
< graph
->n_edge
; ++i
)
4753 if (is_condition(&graph
->edge
[i
]))
4754 clear_local(&graph
->edge
[i
]);
4757 /* Does "graph" have both condition and conditional validity edges?
4759 static int need_condition_check(struct isl_sched_graph
*graph
)
4762 int any_condition
= 0;
4763 int any_conditional_validity
= 0;
4765 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4766 if (is_condition(&graph
->edge
[i
]))
4768 if (is_conditional_validity(&graph
->edge
[i
]))
4769 any_conditional_validity
= 1;
4772 return any_condition
&& any_conditional_validity
;
4775 /* Does "graph" contain any coincidence edge?
4777 static int has_any_coincidence(struct isl_sched_graph
*graph
)
4781 for (i
= 0; i
< graph
->n_edge
; ++i
)
4782 if (is_coincidence(&graph
->edge
[i
]))
4788 /* Extract the final schedule row as a map with the iteration domain
4789 * of "node" as domain.
4791 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
4793 isl_local_space
*ls
;
4797 row
= isl_mat_rows(node
->sched
) - 1;
4798 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
4799 aff
= extract_schedule_row(ls
, node
, row
);
4800 return isl_map_from_aff(aff
);
4803 /* Is the conditional validity dependence in the edge with index "edge_index"
4804 * violated by the latest (i.e., final) row of the schedule?
4805 * That is, is i scheduled after j
4806 * for any conditional validity dependence i -> j?
4808 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
4810 isl_map
*src_sched
, *dst_sched
, *map
;
4811 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
4814 src_sched
= final_row(edge
->src
);
4815 dst_sched
= final_row(edge
->dst
);
4816 map
= isl_map_copy(edge
->map
);
4817 map
= isl_map_apply_domain(map
, src_sched
);
4818 map
= isl_map_apply_range(map
, dst_sched
);
4819 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
4820 empty
= isl_map_is_empty(map
);
4829 /* Does "graph" have any satisfied condition edges that
4830 * are adjacent to the conditional validity constraint with
4831 * domain "conditional_source" and range "conditional_sink"?
4833 * A satisfied condition is one that is not local.
4834 * If a condition was forced to be local already (i.e., marked as local)
4835 * then there is no need to check if it is in fact local.
4837 * Additionally, mark all adjacent condition edges found as local.
4839 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
4840 __isl_keep isl_union_set
*conditional_source
,
4841 __isl_keep isl_union_set
*conditional_sink
)
4846 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4847 int adjacent
, local
;
4848 isl_union_map
*condition
;
4850 if (!is_condition(&graph
->edge
[i
]))
4852 if (is_local(&graph
->edge
[i
]))
4855 condition
= graph
->edge
[i
].tagged_condition
;
4856 adjacent
= domain_intersects(condition
, conditional_sink
);
4857 if (adjacent
>= 0 && !adjacent
)
4858 adjacent
= range_intersects(condition
,
4859 conditional_source
);
4865 set_local(&graph
->edge
[i
]);
4867 local
= is_condition_false(&graph
->edge
[i
]);
4877 /* Are there any violated conditional validity dependences with
4878 * adjacent condition dependences that are not local with respect
4879 * to the current schedule?
4880 * That is, is the conditional validity constraint violated?
4882 * Additionally, mark all those adjacent condition dependences as local.
4883 * We also mark those adjacent condition dependences that were not marked
4884 * as local before, but just happened to be local already. This ensures
4885 * that they remain local if the schedule is recomputed.
4887 * We first collect domain and range of all violated conditional validity
4888 * dependences and then check if there are any adjacent non-local
4889 * condition dependences.
4891 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
4892 struct isl_sched_graph
*graph
)
4896 isl_union_set
*source
, *sink
;
4898 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4899 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4900 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4901 isl_union_set
*uset
;
4902 isl_union_map
*umap
;
4905 if (!is_conditional_validity(&graph
->edge
[i
]))
4908 violated
= is_violated(graph
, i
);
4916 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4917 uset
= isl_union_map_domain(umap
);
4918 source
= isl_union_set_union(source
, uset
);
4919 source
= isl_union_set_coalesce(source
);
4921 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4922 uset
= isl_union_map_range(umap
);
4923 sink
= isl_union_set_union(sink
, uset
);
4924 sink
= isl_union_set_coalesce(sink
);
4928 any
= has_adjacent_true_conditions(graph
, source
, sink
);
4930 isl_union_set_free(source
);
4931 isl_union_set_free(sink
);
4934 isl_union_set_free(source
);
4935 isl_union_set_free(sink
);
4939 /* Examine the current band (the rows between graph->band_start and
4940 * graph->n_total_row), deciding whether to drop it or add it to "node"
4941 * and then continue with the computation of the next band, if any.
4942 * If "initialized" is set, then it may be assumed that compute_maxvar
4943 * has been called on the current band. Otherwise, call
4944 * compute_maxvar if and before carry_dependences gets called.
4946 * The caller keeps looking for a new row as long as
4947 * graph->n_row < graph->maxvar. If the latest attempt to find
4948 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
4950 * - split between SCCs and start over (assuming we found an interesting
4951 * pair of SCCs between which to split)
4952 * - continue with the next band (assuming the current band has at least
4954 * - try to carry as many dependences as possible and continue with the next
4956 * In each case, we first insert a band node in the schedule tree
4957 * if any rows have been computed.
4959 * If the caller managed to complete the schedule, we insert a band node
4960 * (if any schedule rows were computed) and we finish off by topologically
4961 * sorting the statements based on the remaining dependences.
4963 static __isl_give isl_schedule_node
*compute_schedule_finish_band(
4964 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4972 if (graph
->n_row
< graph
->maxvar
) {
4974 int empty
= graph
->n_total_row
== graph
->band_start
;
4976 ctx
= isl_schedule_node_get_ctx(node
);
4977 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
4978 return compute_next_band(node
, graph
, 1);
4979 if (graph
->src_scc
>= 0)
4980 return compute_split_schedule(node
, graph
);
4982 return compute_next_band(node
, graph
, 1);
4983 if (!initialized
&& compute_maxvar(graph
) < 0)
4984 return isl_schedule_node_free(node
);
4985 return carry_dependences(node
, graph
);
4988 insert
= graph
->n_total_row
> graph
->band_start
;
4990 node
= insert_current_band(node
, graph
, 1);
4991 node
= isl_schedule_node_child(node
, 0);
4993 node
= sort_statements(node
, graph
, initialized
);
4995 node
= isl_schedule_node_parent(node
);
5000 /* Construct a band of schedule rows for a connected dependence graph.
5001 * The caller is responsible for determining the strongly connected
5002 * components and calling compute_maxvar first.
5004 * We try to find a sequence of as many schedule rows as possible that result
5005 * in non-negative dependence distances (independent of the previous rows
5006 * in the sequence, i.e., such that the sequence is tilable), with as
5007 * many of the initial rows as possible satisfying the coincidence constraints.
5008 * The computation stops if we can't find any more rows or if we have found
5009 * all the rows we wanted to find.
5011 * If ctx->opt->schedule_outer_coincidence is set, then we force the
5012 * outermost dimension to satisfy the coincidence constraints. If this
5013 * turns out to be impossible, we fall back on the general scheme above
5014 * and try to carry as many dependences as possible.
5016 * If "graph" contains both condition and conditional validity dependences,
5017 * then we need to check that that the conditional schedule constraint
5018 * is satisfied, i.e., there are no violated conditional validity dependences
5019 * that are adjacent to any non-local condition dependences.
5020 * If there are, then we mark all those adjacent condition dependences
5021 * as local and recompute the current band. Those dependences that
5022 * are marked local will then be forced to be local.
5023 * The initial computation is performed with no dependences marked as local.
5024 * If we are lucky, then there will be no violated conditional validity
5025 * dependences adjacent to any non-local condition dependences.
5026 * Otherwise, we mark some additional condition dependences as local and
5027 * recompute. We continue this process until there are no violations left or
5028 * until we are no longer able to compute a schedule.
5029 * Since there are only a finite number of dependences,
5030 * there will only be a finite number of iterations.
5032 static isl_stat
compute_schedule_wcc_band(isl_ctx
*ctx
,
5033 struct isl_sched_graph
*graph
)
5035 int has_coincidence
;
5036 int use_coincidence
;
5037 int force_coincidence
= 0;
5038 int check_conditional
;
5040 if (sort_sccs(graph
) < 0)
5041 return isl_stat_error
;
5043 clear_local_edges(graph
);
5044 check_conditional
= need_condition_check(graph
);
5045 has_coincidence
= has_any_coincidence(graph
);
5047 if (ctx
->opt
->schedule_outer_coincidence
)
5048 force_coincidence
= 1;
5050 use_coincidence
= has_coincidence
;
5051 while (graph
->n_row
< graph
->maxvar
) {
5056 graph
->src_scc
= -1;
5057 graph
->dst_scc
= -1;
5059 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
5060 return isl_stat_error
;
5061 sol
= solve_lp(graph
);
5063 return isl_stat_error
;
5064 if (sol
->size
== 0) {
5065 int empty
= graph
->n_total_row
== graph
->band_start
;
5068 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
5069 use_coincidence
= 0;
5074 coincident
= !has_coincidence
|| use_coincidence
;
5075 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
5076 return isl_stat_error
;
5078 if (!check_conditional
)
5080 violated
= has_violated_conditional_constraint(ctx
, graph
);
5082 return isl_stat_error
;
5085 if (reset_band(graph
) < 0)
5086 return isl_stat_error
;
5087 use_coincidence
= has_coincidence
;
5093 /* Compute a schedule for a connected dependence graph by considering
5094 * the graph as a whole and return the updated schedule node.
5096 * The actual schedule rows of the current band are computed by
5097 * compute_schedule_wcc_band. compute_schedule_finish_band takes
5098 * care of integrating the band into "node" and continuing
5101 static __isl_give isl_schedule_node
*compute_schedule_wcc_whole(
5102 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5109 ctx
= isl_schedule_node_get_ctx(node
);
5110 if (compute_schedule_wcc_band(ctx
, graph
) < 0)
5111 return isl_schedule_node_free(node
);
5113 return compute_schedule_finish_band(node
, graph
, 1);
5116 /* Clustering information used by compute_schedule_wcc_clustering.
5118 * "n" is the number of SCCs in the original dependence graph
5119 * "scc" is an array of "n" elements, each representing an SCC
5120 * of the original dependence graph. All entries in the same cluster
5121 * have the same number of schedule rows.
5122 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
5123 * where each cluster is represented by the index of the first SCC
5124 * in the cluster. Initially, each SCC belongs to a cluster containing
5127 * "scc_in_merge" is used by merge_clusters_along_edge to keep
5128 * track of which SCCs need to be merged.
5130 * "cluster" contains the merged clusters of SCCs after the clustering
5133 * "scc_node" is a temporary data structure used inside copy_partial.
5134 * For each SCC, it keeps track of the number of nodes in the SCC
5135 * that have already been copied.
5137 struct isl_clustering
{
5139 struct isl_sched_graph
*scc
;
5140 struct isl_sched_graph
*cluster
;
5146 /* Initialize the clustering data structure "c" from "graph".
5148 * In particular, allocate memory, extract the SCCs from "graph"
5149 * into c->scc, initialize scc_cluster and construct
5150 * a band of schedule rows for each SCC.
5151 * Within each SCC, there is only one SCC by definition.
5152 * Each SCC initially belongs to a cluster containing only that SCC.
5154 static isl_stat
clustering_init(isl_ctx
*ctx
, struct isl_clustering
*c
,
5155 struct isl_sched_graph
*graph
)
5160 c
->scc
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
5161 c
->cluster
= isl_calloc_array(ctx
, struct isl_sched_graph
, c
->n
);
5162 c
->scc_cluster
= isl_calloc_array(ctx
, int, c
->n
);
5163 c
->scc_node
= isl_calloc_array(ctx
, int, c
->n
);
5164 c
->scc_in_merge
= isl_calloc_array(ctx
, int, c
->n
);
5165 if (!c
->scc
|| !c
->cluster
||
5166 !c
->scc_cluster
|| !c
->scc_node
|| !c
->scc_in_merge
)
5167 return isl_stat_error
;
5169 for (i
= 0; i
< c
->n
; ++i
) {
5170 if (extract_sub_graph(ctx
, graph
, &node_scc_exactly
,
5171 &edge_scc_exactly
, i
, &c
->scc
[i
]) < 0)
5172 return isl_stat_error
;
5174 if (compute_maxvar(&c
->scc
[i
]) < 0)
5175 return isl_stat_error
;
5176 if (compute_schedule_wcc_band(ctx
, &c
->scc
[i
]) < 0)
5177 return isl_stat_error
;
5178 c
->scc_cluster
[i
] = i
;
5184 /* Free all memory allocated for "c".
5186 static void clustering_free(isl_ctx
*ctx
, struct isl_clustering
*c
)
5191 for (i
= 0; i
< c
->n
; ++i
)
5192 graph_free(ctx
, &c
->scc
[i
]);
5195 for (i
= 0; i
< c
->n
; ++i
)
5196 graph_free(ctx
, &c
->cluster
[i
]);
5198 free(c
->scc_cluster
);
5200 free(c
->scc_in_merge
);
5203 /* Should we refrain from merging the cluster in "graph" with
5204 * any other cluster?
5205 * In particular, is its current schedule band empty and incomplete.
5207 static int bad_cluster(struct isl_sched_graph
*graph
)
5209 return graph
->n_row
< graph
->maxvar
&&
5210 graph
->n_total_row
== graph
->band_start
;
5213 /* Return the index of an edge in "graph" that can be used to merge
5214 * two clusters in "c".
5215 * Return graph->n_edge if no such edge can be found.
5216 * Return -1 on error.
5218 * In particular, return a proximity edge between two clusters
5219 * that is not marked "no_merge" and such that neither of the
5220 * two clusters has an incomplete, empty band.
5222 * If there are multiple such edges, then try and find the most
5223 * appropriate edge to use for merging. In particular, pick the edge
5224 * with the greatest weight. If there are multiple of those,
5225 * then pick one with the shortest distance between
5226 * the two cluster representatives.
5228 static int find_proximity(struct isl_sched_graph
*graph
,
5229 struct isl_clustering
*c
)
5231 int i
, best
= graph
->n_edge
, best_dist
, best_weight
;
5233 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5234 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5237 if (!is_proximity(edge
))
5241 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
5242 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
5244 dist
= c
->scc_cluster
[edge
->dst
->scc
] -
5245 c
->scc_cluster
[edge
->src
->scc
];
5248 weight
= edge
->weight
;
5249 if (best
< graph
->n_edge
) {
5250 if (best_weight
> weight
)
5252 if (best_weight
== weight
&& best_dist
<= dist
)
5257 best_weight
= weight
;
5263 /* Internal data structure used in mark_merge_sccs.
5265 * "graph" is the dependence graph in which a strongly connected
5266 * component is constructed.
5267 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
5268 * "src" and "dst" are the indices of the nodes that are being merged.
5270 struct isl_mark_merge_sccs_data
{
5271 struct isl_sched_graph
*graph
;
5277 /* Check whether the cluster containing node "i" depends on the cluster
5278 * containing node "j". If "i" and "j" belong to the same cluster,
5279 * then they are taken to depend on each other to ensure that
5280 * the resulting strongly connected component consists of complete
5281 * clusters. Furthermore, if "i" and "j" are the two nodes that
5282 * are being merged, then they are taken to depend on each other as well.
5283 * Otherwise, check if there is a (conditional) validity dependence
5284 * from node[j] to node[i], forcing node[i] to follow node[j].
5286 static isl_bool
cluster_follows(int i
, int j
, void *user
)
5288 struct isl_mark_merge_sccs_data
*data
= user
;
5289 struct isl_sched_graph
*graph
= data
->graph
;
5290 int *scc_cluster
= data
->scc_cluster
;
5292 if (data
->src
== i
&& data
->dst
== j
)
5293 return isl_bool_true
;
5294 if (data
->src
== j
&& data
->dst
== i
)
5295 return isl_bool_true
;
5296 if (scc_cluster
[graph
->node
[i
].scc
] == scc_cluster
[graph
->node
[j
].scc
])
5297 return isl_bool_true
;
5299 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
5302 /* Mark all SCCs that belong to either of the two clusters in "c"
5303 * connected by the edge in "graph" with index "edge", or to any
5304 * of the intermediate clusters.
5305 * The marking is recorded in c->scc_in_merge.
5307 * The given edge has been selected for merging two clusters,
5308 * meaning that there is at least a proximity edge between the two nodes.
5309 * However, there may also be (indirect) validity dependences
5310 * between the two nodes. When merging the two clusters, all clusters
5311 * containing one or more of the intermediate nodes along the
5312 * indirect validity dependences need to be merged in as well.
5314 * First collect all such nodes by computing the strongly connected
5315 * component (SCC) containing the two nodes connected by the edge, where
5316 * the two nodes are considered to depend on each other to make
5317 * sure they end up in the same SCC. Similarly, each node is considered
5318 * to depend on every other node in the same cluster to ensure
5319 * that the SCC consists of complete clusters.
5321 * Then the original SCCs that contain any of these nodes are marked
5322 * in c->scc_in_merge.
5324 static isl_stat
mark_merge_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5325 int edge
, struct isl_clustering
*c
)
5327 struct isl_mark_merge_sccs_data data
;
5328 struct isl_tarjan_graph
*g
;
5331 for (i
= 0; i
< c
->n
; ++i
)
5332 c
->scc_in_merge
[i
] = 0;
5335 data
.scc_cluster
= c
->scc_cluster
;
5336 data
.src
= graph
->edge
[edge
].src
- graph
->node
;
5337 data
.dst
= graph
->edge
[edge
].dst
- graph
->node
;
5339 g
= isl_tarjan_graph_component(ctx
, graph
->n
, data
.dst
,
5340 &cluster_follows
, &data
);
5346 isl_die(ctx
, isl_error_internal
,
5347 "expecting at least two nodes in component",
5349 if (g
->order
[--i
] != -1)
5350 isl_die(ctx
, isl_error_internal
,
5351 "expecting end of component marker", goto error
);
5353 for (--i
; i
>= 0 && g
->order
[i
] != -1; --i
) {
5354 int scc
= graph
->node
[g
->order
[i
]].scc
;
5355 c
->scc_in_merge
[scc
] = 1;
5358 isl_tarjan_graph_free(g
);
5361 isl_tarjan_graph_free(g
);
5362 return isl_stat_error
;
5365 /* Construct the identifier "cluster_i".
5367 static __isl_give isl_id
*cluster_id(isl_ctx
*ctx
, int i
)
5371 snprintf(name
, sizeof(name
), "cluster_%d", i
);
5372 return isl_id_alloc(ctx
, name
, NULL
);
5375 /* Construct the space of the cluster with index "i" containing
5376 * the strongly connected component "scc".
5378 * In particular, construct a space called cluster_i with dimension equal
5379 * to the number of schedule rows in the current band of "scc".
5381 static __isl_give isl_space
*cluster_space(struct isl_sched_graph
*scc
, int i
)
5387 nvar
= scc
->n_total_row
- scc
->band_start
;
5388 space
= isl_space_copy(scc
->node
[0].space
);
5389 space
= isl_space_params(space
);
5390 space
= isl_space_set_from_params(space
);
5391 space
= isl_space_add_dims(space
, isl_dim_set
, nvar
);
5392 id
= cluster_id(isl_space_get_ctx(space
), i
);
5393 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
5398 /* Collect the domain of the graph for merging clusters.
5400 * In particular, for each cluster with first SCC "i", construct
5401 * a set in the space called cluster_i with dimension equal
5402 * to the number of schedule rows in the current band of the cluster.
5404 static __isl_give isl_union_set
*collect_domain(isl_ctx
*ctx
,
5405 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5409 isl_union_set
*domain
;
5411 space
= isl_space_params_alloc(ctx
, 0);
5412 domain
= isl_union_set_empty(space
);
5414 for (i
= 0; i
< graph
->scc
; ++i
) {
5417 if (!c
->scc_in_merge
[i
])
5419 if (c
->scc_cluster
[i
] != i
)
5421 space
= cluster_space(&c
->scc
[i
], i
);
5422 domain
= isl_union_set_add_set(domain
, isl_set_universe(space
));
5428 /* Construct a map from the original instances to the corresponding
5429 * cluster instance in the current bands of the clusters in "c".
5431 static __isl_give isl_union_map
*collect_cluster_map(isl_ctx
*ctx
,
5432 struct isl_sched_graph
*graph
, struct isl_clustering
*c
)
5436 isl_union_map
*cluster_map
;
5438 space
= isl_space_params_alloc(ctx
, 0);
5439 cluster_map
= isl_union_map_empty(space
);
5440 for (i
= 0; i
< graph
->scc
; ++i
) {
5444 if (!c
->scc_in_merge
[i
])
5447 id
= cluster_id(ctx
, c
->scc_cluster
[i
]);
5448 start
= c
->scc
[i
].band_start
;
5449 n
= c
->scc
[i
].n_total_row
- start
;
5450 for (j
= 0; j
< c
->scc
[i
].n
; ++j
) {
5453 struct isl_sched_node
*node
= &c
->scc
[i
].node
[j
];
5455 ma
= node_extract_partial_schedule_multi_aff(node
,
5457 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
,
5459 map
= isl_map_from_multi_aff(ma
);
5460 cluster_map
= isl_union_map_add_map(cluster_map
, map
);
5468 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
5469 * that are not isl_edge_condition or isl_edge_conditional_validity.
5471 static __isl_give isl_schedule_constraints
*add_non_conditional_constraints(
5472 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5473 __isl_take isl_schedule_constraints
*sc
)
5475 enum isl_edge_type t
;
5480 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
5481 if (t
== isl_edge_condition
||
5482 t
== isl_edge_conditional_validity
)
5484 if (!is_type(edge
, t
))
5486 sc
->constraint
[t
] = isl_union_map_union(sc
->constraint
[t
],
5487 isl_union_map_copy(umap
));
5488 if (!sc
->constraint
[t
])
5489 return isl_schedule_constraints_free(sc
);
5495 /* Add schedule constraints of types isl_edge_condition and
5496 * isl_edge_conditional_validity to "sc" by applying "umap" to
5497 * the domains of the wrapped relations in domain and range
5498 * of the corresponding tagged constraints of "edge".
5500 static __isl_give isl_schedule_constraints
*add_conditional_constraints(
5501 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*umap
,
5502 __isl_take isl_schedule_constraints
*sc
)
5504 enum isl_edge_type t
;
5505 isl_union_map
*tagged
;
5507 for (t
= isl_edge_condition
; t
<= isl_edge_conditional_validity
; ++t
) {
5508 if (!is_type(edge
, t
))
5510 if (t
== isl_edge_condition
)
5511 tagged
= isl_union_map_copy(edge
->tagged_condition
);
5513 tagged
= isl_union_map_copy(edge
->tagged_validity
);
5514 tagged
= isl_union_map_zip(tagged
);
5515 tagged
= isl_union_map_apply_domain(tagged
,
5516 isl_union_map_copy(umap
));
5517 tagged
= isl_union_map_zip(tagged
);
5518 sc
->constraint
[t
] = isl_union_map_union(sc
->constraint
[t
],
5520 if (!sc
->constraint
[t
])
5521 return isl_schedule_constraints_free(sc
);
5527 /* Given a mapping "cluster_map" from the original instances to
5528 * the cluster instances, add schedule constraints on the clusters
5529 * to "sc" corresponding to the original constraints represented by "edge".
5531 * For non-tagged dependence constraints, the cluster constraints
5532 * are obtained by applying "cluster_map" to the edge->map.
5534 * For tagged dependence constraints, "cluster_map" needs to be applied
5535 * to the domains of the wrapped relations in domain and range
5536 * of the tagged dependence constraints. Pick out the mappings
5537 * from these domains from "cluster_map" and construct their product.
5538 * This mapping can then be applied to the pair of domains.
5540 static __isl_give isl_schedule_constraints
*collect_edge_constraints(
5541 struct isl_sched_edge
*edge
, __isl_keep isl_union_map
*cluster_map
,
5542 __isl_take isl_schedule_constraints
*sc
)
5544 isl_union_map
*umap
;
5546 isl_union_set
*uset
;
5547 isl_union_map
*umap1
, *umap2
;
5552 umap
= isl_union_map_from_map(isl_map_copy(edge
->map
));
5553 umap
= isl_union_map_apply_domain(umap
,
5554 isl_union_map_copy(cluster_map
));
5555 umap
= isl_union_map_apply_range(umap
,
5556 isl_union_map_copy(cluster_map
));
5557 sc
= add_non_conditional_constraints(edge
, umap
, sc
);
5558 isl_union_map_free(umap
);
5560 if (!sc
|| (!is_condition(edge
) && !is_conditional_validity(edge
)))
5563 space
= isl_space_domain(isl_map_get_space(edge
->map
));
5564 uset
= isl_union_set_from_set(isl_set_universe(space
));
5565 umap1
= isl_union_map_copy(cluster_map
);
5566 umap1
= isl_union_map_intersect_domain(umap1
, uset
);
5567 space
= isl_space_range(isl_map_get_space(edge
->map
));
5568 uset
= isl_union_set_from_set(isl_set_universe(space
));
5569 umap2
= isl_union_map_copy(cluster_map
);
5570 umap2
= isl_union_map_intersect_domain(umap2
, uset
);
5571 umap
= isl_union_map_product(umap1
, umap2
);
5573 sc
= add_conditional_constraints(edge
, umap
, sc
);
5575 isl_union_map_free(umap
);
5579 /* Given a mapping "cluster_map" from the original instances to
5580 * the cluster instances, add schedule constraints on the clusters
5581 * to "sc" corresponding to all edges in "graph" between nodes that
5582 * belong to SCCs that are marked for merging in "scc_in_merge".
5584 static __isl_give isl_schedule_constraints
*collect_constraints(
5585 struct isl_sched_graph
*graph
, int *scc_in_merge
,
5586 __isl_keep isl_union_map
*cluster_map
,
5587 __isl_take isl_schedule_constraints
*sc
)
5591 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5592 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
5594 if (!scc_in_merge
[edge
->src
->scc
])
5596 if (!scc_in_merge
[edge
->dst
->scc
])
5598 sc
= collect_edge_constraints(edge
, cluster_map
, sc
);
5604 /* Construct a dependence graph for scheduling clusters with respect
5605 * to each other and store the result in "merge_graph".
5606 * In particular, the nodes of the graph correspond to the schedule
5607 * dimensions of the current bands of those clusters that have been
5608 * marked for merging in "c".
5610 * First construct an isl_schedule_constraints object for this domain
5611 * by transforming the edges in "graph" to the domain.
5612 * Then initialize a dependence graph for scheduling from these
5615 static isl_stat
init_merge_graph(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
5616 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
5618 isl_union_set
*domain
;
5619 isl_union_map
*cluster_map
;
5620 isl_schedule_constraints
*sc
;
5623 domain
= collect_domain(ctx
, graph
, c
);
5624 sc
= isl_schedule_constraints_on_domain(domain
);
5626 return isl_stat_error
;
5627 cluster_map
= collect_cluster_map(ctx
, graph
, c
);
5628 sc
= collect_constraints(graph
, c
->scc_in_merge
, cluster_map
, sc
);
5629 isl_union_map_free(cluster_map
);
5631 r
= graph_init(merge_graph
, sc
);
5633 isl_schedule_constraints_free(sc
);
5638 /* Compute the maximal number of remaining schedule rows that still need
5639 * to be computed for the nodes that belong to clusters with the maximal
5640 * dimension for the current band (i.e., the band that is to be merged).
5641 * Only clusters that are about to be merged are considered.
5642 * "maxvar" is the maximal dimension for the current band.
5643 * "c" contains information about the clusters.
5645 * Return the maximal number of remaining schedule rows or -1 on error.
5647 static int compute_maxvar_max_slack(int maxvar
, struct isl_clustering
*c
)
5653 for (i
= 0; i
< c
->n
; ++i
) {
5655 struct isl_sched_graph
*scc
;
5657 if (!c
->scc_in_merge
[i
])
5660 nvar
= scc
->n_total_row
- scc
->band_start
;
5663 for (j
= 0; j
< scc
->n
; ++j
) {
5664 struct isl_sched_node
*node
= &scc
->node
[j
];
5667 if (node_update_cmap(node
) < 0)
5669 slack
= node
->nvar
- node
->rank
;
5670 if (slack
> max_slack
)
5678 /* If there are any clusters where the dimension of the current band
5679 * (i.e., the band that is to be merged) is smaller than "maxvar" and
5680 * if there are any nodes in such a cluster where the number
5681 * of remaining schedule rows that still need to be computed
5682 * is greater than "max_slack", then return the smallest current band
5683 * dimension of all these clusters. Otherwise return the original value
5684 * of "maxvar". Return -1 in case of any error.
5685 * Only clusters that are about to be merged are considered.
5686 * "c" contains information about the clusters.
5688 static int limit_maxvar_to_slack(int maxvar
, int max_slack
,
5689 struct isl_clustering
*c
)
5693 for (i
= 0; i
< c
->n
; ++i
) {
5695 struct isl_sched_graph
*scc
;
5697 if (!c
->scc_in_merge
[i
])
5700 nvar
= scc
->n_total_row
- scc
->band_start
;
5703 for (j
= 0; j
< scc
->n
; ++j
) {
5704 struct isl_sched_node
*node
= &scc
->node
[j
];
5707 if (node_update_cmap(node
) < 0)
5709 slack
= node
->nvar
- node
->rank
;
5710 if (slack
> max_slack
) {
5720 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
5721 * that still need to be computed. In particular, if there is a node
5722 * in a cluster where the dimension of the current band is smaller
5723 * than merge_graph->maxvar, but the number of remaining schedule rows
5724 * is greater than that of any node in a cluster with the maximal
5725 * dimension for the current band (i.e., merge_graph->maxvar),
5726 * then adjust merge_graph->maxvar to the (smallest) current band dimension
5727 * of those clusters. Without this adjustment, the total number of
5728 * schedule dimensions would be increased, resulting in a skewed view
5729 * of the number of coincident dimensions.
5730 * "c" contains information about the clusters.
5732 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
5733 * then there is no point in attempting any merge since it will be rejected
5734 * anyway. Set merge_graph->maxvar to zero in such cases.
5736 static isl_stat
adjust_maxvar_to_slack(isl_ctx
*ctx
,
5737 struct isl_sched_graph
*merge_graph
, struct isl_clustering
*c
)
5739 int max_slack
, maxvar
;
5741 max_slack
= compute_maxvar_max_slack(merge_graph
->maxvar
, c
);
5743 return isl_stat_error
;
5744 maxvar
= limit_maxvar_to_slack(merge_graph
->maxvar
, max_slack
, c
);
5746 return isl_stat_error
;
5748 if (maxvar
< merge_graph
->maxvar
) {
5749 if (isl_options_get_schedule_maximize_band_depth(ctx
))
5750 merge_graph
->maxvar
= 0;
5752 merge_graph
->maxvar
= maxvar
;
5758 /* Return the number of coincident dimensions in the current band of "graph",
5759 * where the nodes of "graph" are assumed to be scheduled by a single band.
5761 static int get_n_coincident(struct isl_sched_graph
*graph
)
5765 for (i
= graph
->band_start
; i
< graph
->n_total_row
; ++i
)
5766 if (!graph
->node
[0].coincident
[i
])
5769 return i
- graph
->band_start
;
5772 /* Should the clusters be merged based on the cluster schedule
5773 * in the current (and only) band of "merge_graph", given that
5774 * coincidence should be maximized?
5776 * If the number of coincident schedule dimensions in the merged band
5777 * would be less than the maximal number of coincident schedule dimensions
5778 * in any of the merged clusters, then the clusters should not be merged.
5780 static isl_bool
ok_to_merge_coincident(struct isl_clustering
*c
,
5781 struct isl_sched_graph
*merge_graph
)
5788 for (i
= 0; i
< c
->n
; ++i
) {
5789 if (!c
->scc_in_merge
[i
])
5791 n_coincident
= get_n_coincident(&c
->scc
[i
]);
5792 if (n_coincident
> max_coincident
)
5793 max_coincident
= n_coincident
;
5796 n_coincident
= get_n_coincident(merge_graph
);
5798 return n_coincident
>= max_coincident
;
5801 /* Return the transformation on "node" expressed by the current (and only)
5802 * band of "merge_graph" applied to the clusters in "c".
5804 * First find the representation of "node" in its SCC in "c" and
5805 * extract the transformation expressed by the current band.
5806 * Then extract the transformation applied by "merge_graph"
5807 * to the cluster to which this SCC belongs.
5808 * Combine the two to obtain the complete transformation on the node.
5810 * Note that the range of the first transformation is an anonymous space,
5811 * while the domain of the second is named "cluster_X". The range
5812 * of the former therefore needs to be adjusted before the two
5815 static __isl_give isl_map
*extract_node_transformation(isl_ctx
*ctx
,
5816 struct isl_sched_node
*node
, struct isl_clustering
*c
,
5817 struct isl_sched_graph
*merge_graph
)
5819 struct isl_sched_node
*scc_node
, *cluster_node
;
5823 isl_multi_aff
*ma
, *ma2
;
5825 scc_node
= graph_find_node(ctx
, &c
->scc
[node
->scc
], node
->space
);
5826 start
= c
->scc
[node
->scc
].band_start
;
5827 n
= c
->scc
[node
->scc
].n_total_row
- start
;
5828 ma
= node_extract_partial_schedule_multi_aff(scc_node
, start
, n
);
5829 space
= cluster_space(&c
->scc
[node
->scc
], c
->scc_cluster
[node
->scc
]);
5830 cluster_node
= graph_find_node(ctx
, merge_graph
, space
);
5831 if (space
&& !cluster_node
)
5832 isl_die(ctx
, isl_error_internal
, "unable to find cluster",
5833 space
= isl_space_free(space
));
5834 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
5835 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
, id
);
5836 isl_space_free(space
);
5837 n
= merge_graph
->n_total_row
;
5838 ma2
= node_extract_partial_schedule_multi_aff(cluster_node
, 0, n
);
5839 ma
= isl_multi_aff_pullback_multi_aff(ma2
, ma
);
5841 return isl_map_from_multi_aff(ma
);
5844 /* Give a set of distances "set", are they bounded by a small constant
5845 * in direction "pos"?
5846 * In practice, check if they are bounded by 2 by checking that there
5847 * are no elements with a value greater than or equal to 3 or
5848 * smaller than or equal to -3.
5850 static isl_bool
distance_is_bounded(__isl_keep isl_set
*set
, int pos
)
5856 return isl_bool_error
;
5858 test
= isl_set_copy(set
);
5859 test
= isl_set_lower_bound_si(test
, isl_dim_set
, pos
, 3);
5860 bounded
= isl_set_is_empty(test
);
5863 if (bounded
< 0 || !bounded
)
5866 test
= isl_set_copy(set
);
5867 test
= isl_set_upper_bound_si(test
, isl_dim_set
, pos
, -3);
5868 bounded
= isl_set_is_empty(test
);
5874 /* Does the set "set" have a fixed (but possible parametric) value
5875 * at dimension "pos"?
5877 static isl_bool
has_single_value(__isl_keep isl_set
*set
, int pos
)
5883 return isl_bool_error
;
5884 set
= isl_set_copy(set
);
5885 n
= isl_set_dim(set
, isl_dim_set
);
5886 set
= isl_set_project_out(set
, isl_dim_set
, pos
+ 1, n
- (pos
+ 1));
5887 set
= isl_set_project_out(set
, isl_dim_set
, 0, pos
);
5888 single
= isl_set_is_singleton(set
);
5894 /* Does "map" have a fixed (but possible parametric) value
5895 * at dimension "pos" of either its domain or its range?
5897 static isl_bool
has_singular_src_or_dst(__isl_keep isl_map
*map
, int pos
)
5902 set
= isl_map_domain(isl_map_copy(map
));
5903 single
= has_single_value(set
, pos
);
5906 if (single
< 0 || single
)
5909 set
= isl_map_range(isl_map_copy(map
));
5910 single
= has_single_value(set
, pos
);
5916 /* Does the edge "edge" from "graph" have bounded dependence distances
5917 * in the merged graph "merge_graph" of a selection of clusters in "c"?
5919 * Extract the complete transformations of the source and destination
5920 * nodes of the edge, apply them to the edge constraints and
5921 * compute the differences. Finally, check if these differences are bounded
5922 * in each direction.
5924 * If the dimension of the band is greater than the number of
5925 * dimensions that can be expected to be optimized by the edge
5926 * (based on its weight), then also allow the differences to be unbounded
5927 * in the remaining dimensions, but only if either the source or
5928 * the destination has a fixed value in that direction.
5929 * This allows a statement that produces values that are used by
5930 * several instances of another statement to be merged with that
5932 * However, merging such clusters will introduce an inherently
5933 * large proximity distance inside the merged cluster, meaning
5934 * that proximity distances will no longer be optimized in
5935 * subsequent merges. These merges are therefore only allowed
5936 * after all other possible merges have been tried.
5937 * The first time such a merge is encountered, the weight of the edge
5938 * is replaced by a negative weight. The second time (i.e., after
5939 * all merges over edges with a non-negative weight have been tried),
5940 * the merge is allowed.
5942 static isl_bool
has_bounded_distances(isl_ctx
*ctx
, struct isl_sched_edge
*edge
,
5943 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
5944 struct isl_sched_graph
*merge_graph
)
5951 map
= isl_map_copy(edge
->map
);
5952 t
= extract_node_transformation(ctx
, edge
->src
, c
, merge_graph
);
5953 map
= isl_map_apply_domain(map
, t
);
5954 t
= extract_node_transformation(ctx
, edge
->dst
, c
, merge_graph
);
5955 map
= isl_map_apply_range(map
, t
);
5956 dist
= isl_map_deltas(isl_map_copy(map
));
5958 bounded
= isl_bool_true
;
5959 n
= isl_set_dim(dist
, isl_dim_set
);
5960 n_slack
= n
- edge
->weight
;
5961 if (edge
->weight
< 0)
5962 n_slack
-= graph
->max_weight
+ 1;
5963 for (i
= 0; i
< n
; ++i
) {
5964 isl_bool bounded_i
, singular_i
;
5966 bounded_i
= distance_is_bounded(dist
, i
);
5971 if (edge
->weight
>= 0)
5972 bounded
= isl_bool_false
;
5976 singular_i
= has_singular_src_or_dst(map
, i
);
5981 bounded
= isl_bool_false
;
5984 if (!bounded
&& i
>= n
&& edge
->weight
>= 0)
5985 edge
->weight
-= graph
->max_weight
+ 1;
5993 return isl_bool_error
;
5996 /* Should the clusters be merged based on the cluster schedule
5997 * in the current (and only) band of "merge_graph"?
5998 * "graph" is the original dependence graph, while "c" records
5999 * which SCCs are involved in the latest merge.
6001 * In particular, is there at least one proximity constraint
6002 * that is optimized by the merge?
6004 * A proximity constraint is considered to be optimized
6005 * if the dependence distances are small.
6007 static isl_bool
ok_to_merge_proximity(isl_ctx
*ctx
,
6008 struct isl_sched_graph
*graph
, struct isl_clustering
*c
,
6009 struct isl_sched_graph
*merge_graph
)
6013 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6014 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6017 if (!is_proximity(edge
))
6019 if (!c
->scc_in_merge
[edge
->src
->scc
])
6021 if (!c
->scc_in_merge
[edge
->dst
->scc
])
6023 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6024 c
->scc_cluster
[edge
->src
->scc
])
6026 bounded
= has_bounded_distances(ctx
, edge
, graph
, c
,
6028 if (bounded
< 0 || bounded
)
6032 return isl_bool_false
;
6035 /* Should the clusters be merged based on the cluster schedule
6036 * in the current (and only) band of "merge_graph"?
6037 * "graph" is the original dependence graph, while "c" records
6038 * which SCCs are involved in the latest merge.
6040 * If the current band is empty, then the clusters should not be merged.
6042 * If the band depth should be maximized and the merge schedule
6043 * is incomplete (meaning that the dimension of some of the schedule
6044 * bands in the original schedule will be reduced), then the clusters
6045 * should not be merged.
6047 * If the schedule_maximize_coincidence option is set, then check that
6048 * the number of coincident schedule dimensions is not reduced.
6050 * Finally, only allow the merge if at least one proximity
6051 * constraint is optimized.
6053 static isl_bool
ok_to_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6054 struct isl_clustering
*c
, struct isl_sched_graph
*merge_graph
)
6056 if (merge_graph
->n_total_row
== merge_graph
->band_start
)
6057 return isl_bool_false
;
6059 if (isl_options_get_schedule_maximize_band_depth(ctx
) &&
6060 merge_graph
->n_total_row
< merge_graph
->maxvar
)
6061 return isl_bool_false
;
6063 if (isl_options_get_schedule_maximize_coincidence(ctx
)) {
6066 ok
= ok_to_merge_coincident(c
, merge_graph
);
6071 return ok_to_merge_proximity(ctx
, graph
, c
, merge_graph
);
6074 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
6075 * of the schedule in "node" and return the result.
6077 * That is, essentially compute
6079 * T * N(first:first+n-1)
6081 * taking into account the constant term and the parameter coefficients
6084 static __isl_give isl_mat
*node_transformation(isl_ctx
*ctx
,
6085 struct isl_sched_node
*t_node
, struct isl_sched_node
*node
,
6090 int n_row
, n_col
, n_param
, n_var
;
6092 n_param
= node
->nparam
;
6094 n_row
= isl_mat_rows(t_node
->sched
);
6095 n_col
= isl_mat_cols(node
->sched
);
6096 t
= isl_mat_alloc(ctx
, n_row
, n_col
);
6099 for (i
= 0; i
< n_row
; ++i
) {
6100 isl_seq_cpy(t
->row
[i
], t_node
->sched
->row
[i
], 1 + n_param
);
6101 isl_seq_clr(t
->row
[i
] + 1 + n_param
, n_var
);
6102 for (j
= 0; j
< n
; ++j
)
6103 isl_seq_addmul(t
->row
[i
],
6104 t_node
->sched
->row
[i
][1 + n_param
+ j
],
6105 node
->sched
->row
[first
+ j
],
6106 1 + n_param
+ n_var
);
6111 /* Apply the cluster schedule in "t_node" to the current band
6112 * schedule of the nodes in "graph".
6114 * In particular, replace the rows starting at band_start
6115 * by the result of applying the cluster schedule in "t_node"
6116 * to the original rows.
6118 * The coincidence of the schedule is determined by the coincidence
6119 * of the cluster schedule.
6121 static isl_stat
transform(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6122 struct isl_sched_node
*t_node
)
6128 start
= graph
->band_start
;
6129 n
= graph
->n_total_row
- start
;
6131 n_new
= isl_mat_rows(t_node
->sched
);
6132 for (i
= 0; i
< graph
->n
; ++i
) {
6133 struct isl_sched_node
*node
= &graph
->node
[i
];
6136 t
= node_transformation(ctx
, t_node
, node
, start
, n
);
6137 node
->sched
= isl_mat_drop_rows(node
->sched
, start
, n
);
6138 node
->sched
= isl_mat_concat(node
->sched
, t
);
6139 node
->sched_map
= isl_map_free(node
->sched_map
);
6141 return isl_stat_error
;
6142 for (j
= 0; j
< n_new
; ++j
)
6143 node
->coincident
[start
+ j
] = t_node
->coincident
[j
];
6145 graph
->n_total_row
-= n
;
6147 graph
->n_total_row
+= n_new
;
6148 graph
->n_row
+= n_new
;
6153 /* Merge the clusters marked for merging in "c" into a single
6154 * cluster using the cluster schedule in the current band of "merge_graph".
6155 * The representative SCC for the new cluster is the SCC with
6156 * the smallest index.
6158 * The current band schedule of each SCC in the new cluster is obtained
6159 * by applying the schedule of the corresponding original cluster
6160 * to the original band schedule.
6161 * All SCCs in the new cluster have the same number of schedule rows.
6163 static isl_stat
merge(isl_ctx
*ctx
, struct isl_clustering
*c
,
6164 struct isl_sched_graph
*merge_graph
)
6170 for (i
= 0; i
< c
->n
; ++i
) {
6171 struct isl_sched_node
*node
;
6173 if (!c
->scc_in_merge
[i
])
6177 space
= cluster_space(&c
->scc
[i
], c
->scc_cluster
[i
]);
6179 return isl_stat_error
;
6180 node
= graph_find_node(ctx
, merge_graph
, space
);
6181 isl_space_free(space
);
6183 isl_die(ctx
, isl_error_internal
,
6184 "unable to find cluster",
6185 return isl_stat_error
);
6186 if (transform(ctx
, &c
->scc
[i
], node
) < 0)
6187 return isl_stat_error
;
6188 c
->scc_cluster
[i
] = cluster
;
6194 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
6195 * by scheduling the current cluster bands with respect to each other.
6197 * Construct a dependence graph with a space for each cluster and
6198 * with the coordinates of each space corresponding to the schedule
6199 * dimensions of the current band of that cluster.
6200 * Construct a cluster schedule in this cluster dependence graph and
6201 * apply it to the current cluster bands if it is applicable
6202 * according to ok_to_merge.
6204 * If the number of remaining schedule dimensions in a cluster
6205 * with a non-maximal current schedule dimension is greater than
6206 * the number of remaining schedule dimensions in clusters
6207 * with a maximal current schedule dimension, then restrict
6208 * the number of rows to be computed in the cluster schedule
6209 * to the minimal such non-maximal current schedule dimension.
6210 * Do this by adjusting merge_graph.maxvar.
6212 * Return isl_bool_true if the clusters have effectively been merged
6213 * into a single cluster.
6215 * Note that since the standard scheduling algorithm minimizes the maximal
6216 * distance over proximity constraints, the proximity constraints between
6217 * the merged clusters may not be optimized any further than what is
6218 * sufficient to bring the distances within the limits of the internal
6219 * proximity constraints inside the individual clusters.
6220 * It may therefore make sense to perform an additional translation step
6221 * to bring the clusters closer to each other, while maintaining
6222 * the linear part of the merging schedule found using the standard
6223 * scheduling algorithm.
6225 static isl_bool
try_merge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6226 struct isl_clustering
*c
)
6228 struct isl_sched_graph merge_graph
= { 0 };
6231 if (init_merge_graph(ctx
, graph
, c
, &merge_graph
) < 0)
6234 if (compute_maxvar(&merge_graph
) < 0)
6236 if (adjust_maxvar_to_slack(ctx
, &merge_graph
,c
) < 0)
6238 if (compute_schedule_wcc_band(ctx
, &merge_graph
) < 0)
6240 merged
= ok_to_merge(ctx
, graph
, c
, &merge_graph
);
6241 if (merged
&& merge(ctx
, c
, &merge_graph
) < 0)
6244 graph_free(ctx
, &merge_graph
);
6247 graph_free(ctx
, &merge_graph
);
6248 return isl_bool_error
;
6251 /* Is there any edge marked "no_merge" between two SCCs that are
6252 * about to be merged (i.e., that are set in "scc_in_merge")?
6253 * "merge_edge" is the proximity edge along which the clusters of SCCs
6254 * are going to be merged.
6256 * If there is any edge between two SCCs with a negative weight,
6257 * while the weight of "merge_edge" is non-negative, then this
6258 * means that the edge was postponed. "merge_edge" should then
6259 * also be postponed since merging along the edge with negative weight should
6260 * be postponed until all edges with non-negative weight have been tried.
6261 * Replace the weight of "merge_edge" by a negative weight as well and
6262 * tell the caller not to attempt a merge.
6264 static int any_no_merge(struct isl_sched_graph
*graph
, int *scc_in_merge
,
6265 struct isl_sched_edge
*merge_edge
)
6269 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6270 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6272 if (!scc_in_merge
[edge
->src
->scc
])
6274 if (!scc_in_merge
[edge
->dst
->scc
])
6278 if (merge_edge
->weight
>= 0 && edge
->weight
< 0) {
6279 merge_edge
->weight
-= graph
->max_weight
+ 1;
6287 /* Merge the two clusters in "c" connected by the edge in "graph"
6288 * with index "edge" into a single cluster.
6289 * If it turns out to be impossible to merge these two clusters,
6290 * then mark the edge as "no_merge" such that it will not be
6293 * First mark all SCCs that need to be merged. This includes the SCCs
6294 * in the two clusters, but it may also include the SCCs
6295 * of intermediate clusters.
6296 * If there is already a no_merge edge between any pair of such SCCs,
6297 * then simply mark the current edge as no_merge as well.
6298 * Likewise, if any of those edges was postponed by has_bounded_distances,
6299 * then postpone the current edge as well.
6300 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
6301 * if the clusters did not end up getting merged, unless the non-merge
6302 * is due to the fact that the edge was postponed. This postponement
6303 * can be recognized by a change in weight (from non-negative to negative).
6305 static isl_stat
merge_clusters_along_edge(isl_ctx
*ctx
,
6306 struct isl_sched_graph
*graph
, int edge
, struct isl_clustering
*c
)
6309 int edge_weight
= graph
->edge
[edge
].weight
;
6311 if (mark_merge_sccs(ctx
, graph
, edge
, c
) < 0)
6312 return isl_stat_error
;
6314 if (any_no_merge(graph
, c
->scc_in_merge
, &graph
->edge
[edge
]))
6315 merged
= isl_bool_false
;
6317 merged
= try_merge(ctx
, graph
, c
);
6319 return isl_stat_error
;
6320 if (!merged
&& edge_weight
== graph
->edge
[edge
].weight
)
6321 graph
->edge
[edge
].no_merge
= 1;
6326 /* Does "node" belong to the cluster identified by "cluster"?
6328 static int node_cluster_exactly(struct isl_sched_node
*node
, int cluster
)
6330 return node
->cluster
== cluster
;
6333 /* Does "edge" connect two nodes belonging to the cluster
6334 * identified by "cluster"?
6336 static int edge_cluster_exactly(struct isl_sched_edge
*edge
, int cluster
)
6338 return edge
->src
->cluster
== cluster
&& edge
->dst
->cluster
== cluster
;
6341 /* Swap the schedule of "node1" and "node2".
6342 * Both nodes have been derived from the same node in a common parent graph.
6343 * Since the "coincident" field is shared with that node
6344 * in the parent graph, there is no need to also swap this field.
6346 static void swap_sched(struct isl_sched_node
*node1
,
6347 struct isl_sched_node
*node2
)
6352 sched
= node1
->sched
;
6353 node1
->sched
= node2
->sched
;
6354 node2
->sched
= sched
;
6356 sched_map
= node1
->sched_map
;
6357 node1
->sched_map
= node2
->sched_map
;
6358 node2
->sched_map
= sched_map
;
6361 /* Copy the current band schedule from the SCCs that form the cluster
6362 * with index "pos" to the actual cluster at position "pos".
6363 * By construction, the index of the first SCC that belongs to the cluster
6366 * The order of the nodes inside both the SCCs and the cluster
6367 * is assumed to be same as the order in the original "graph".
6369 * Since the SCC graphs will no longer be used after this function,
6370 * the schedules are actually swapped rather than copied.
6372 static isl_stat
copy_partial(struct isl_sched_graph
*graph
,
6373 struct isl_clustering
*c
, int pos
)
6377 c
->cluster
[pos
].n_total_row
= c
->scc
[pos
].n_total_row
;
6378 c
->cluster
[pos
].n_row
= c
->scc
[pos
].n_row
;
6379 c
->cluster
[pos
].maxvar
= c
->scc
[pos
].maxvar
;
6381 for (i
= 0; i
< graph
->n
; ++i
) {
6385 if (graph
->node
[i
].cluster
!= pos
)
6387 s
= graph
->node
[i
].scc
;
6388 k
= c
->scc_node
[s
]++;
6389 swap_sched(&c
->cluster
[pos
].node
[j
], &c
->scc
[s
].node
[k
]);
6390 if (c
->scc
[s
].maxvar
> c
->cluster
[pos
].maxvar
)
6391 c
->cluster
[pos
].maxvar
= c
->scc
[s
].maxvar
;
6398 /* Is there a (conditional) validity dependence from node[j] to node[i],
6399 * forcing node[i] to follow node[j] or do the nodes belong to the same
6402 static isl_bool
node_follows_strong_or_same_cluster(int i
, int j
, void *user
)
6404 struct isl_sched_graph
*graph
= user
;
6406 if (graph
->node
[i
].cluster
== graph
->node
[j
].cluster
)
6407 return isl_bool_true
;
6408 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
6411 /* Extract the merged clusters of SCCs in "graph", sort them, and
6412 * store them in c->clusters. Update c->scc_cluster accordingly.
6414 * First keep track of the cluster containing the SCC to which a node
6415 * belongs in the node itself.
6416 * Then extract the clusters into c->clusters, copying the current
6417 * band schedule from the SCCs that belong to the cluster.
6418 * Do this only once per cluster.
6420 * Finally, topologically sort the clusters and update c->scc_cluster
6421 * to match the new scc numbering. While the SCCs were originally
6422 * sorted already, some SCCs that depend on some other SCCs may
6423 * have been merged with SCCs that appear before these other SCCs.
6424 * A reordering may therefore be required.
6426 static isl_stat
extract_clusters(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
6427 struct isl_clustering
*c
)
6431 for (i
= 0; i
< graph
->n
; ++i
)
6432 graph
->node
[i
].cluster
= c
->scc_cluster
[graph
->node
[i
].scc
];
6434 for (i
= 0; i
< graph
->scc
; ++i
) {
6435 if (c
->scc_cluster
[i
] != i
)
6437 if (extract_sub_graph(ctx
, graph
, &node_cluster_exactly
,
6438 &edge_cluster_exactly
, i
, &c
->cluster
[i
]) < 0)
6439 return isl_stat_error
;
6440 c
->cluster
[i
].src_scc
= -1;
6441 c
->cluster
[i
].dst_scc
= -1;
6442 if (copy_partial(graph
, c
, i
) < 0)
6443 return isl_stat_error
;
6446 if (detect_ccs(ctx
, graph
, &node_follows_strong_or_same_cluster
) < 0)
6447 return isl_stat_error
;
6448 for (i
= 0; i
< graph
->n
; ++i
)
6449 c
->scc_cluster
[graph
->node
[i
].scc
] = graph
->node
[i
].cluster
;
6454 /* Compute weights on the proximity edges of "graph" that can
6455 * be used by find_proximity to find the most appropriate
6456 * proximity edge to use to merge two clusters in "c".
6457 * The weights are also used by has_bounded_distances to determine
6458 * whether the merge should be allowed.
6459 * Store the maximum of the computed weights in graph->max_weight.
6461 * The computed weight is a measure for the number of remaining schedule
6462 * dimensions that can still be completely aligned.
6463 * In particular, compute the number of equalities between
6464 * input dimensions and output dimensions in the proximity constraints.
6465 * The directions that are already handled by outer schedule bands
6466 * are projected out prior to determining this number.
6468 * Edges that will never be considered by find_proximity are ignored.
6470 static isl_stat
compute_weights(struct isl_sched_graph
*graph
,
6471 struct isl_clustering
*c
)
6475 graph
->max_weight
= 0;
6477 for (i
= 0; i
< graph
->n_edge
; ++i
) {
6478 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
6479 struct isl_sched_node
*src
= edge
->src
;
6480 struct isl_sched_node
*dst
= edge
->dst
;
6481 isl_basic_map
*hull
;
6484 if (!is_proximity(edge
))
6486 if (bad_cluster(&c
->scc
[edge
->src
->scc
]) ||
6487 bad_cluster(&c
->scc
[edge
->dst
->scc
]))
6489 if (c
->scc_cluster
[edge
->dst
->scc
] ==
6490 c
->scc_cluster
[edge
->src
->scc
])
6493 hull
= isl_map_affine_hull(isl_map_copy(edge
->map
));
6494 hull
= isl_basic_map_transform_dims(hull
, isl_dim_in
, 0,
6495 isl_mat_copy(src
->ctrans
));
6496 hull
= isl_basic_map_transform_dims(hull
, isl_dim_out
, 0,
6497 isl_mat_copy(dst
->ctrans
));
6498 hull
= isl_basic_map_project_out(hull
,
6499 isl_dim_in
, 0, src
->rank
);
6500 hull
= isl_basic_map_project_out(hull
,
6501 isl_dim_out
, 0, dst
->rank
);
6502 hull
= isl_basic_map_remove_divs(hull
);
6503 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
6504 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
6505 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6506 isl_dim_in
, 0, n_in
);
6507 hull
= isl_basic_map_drop_constraints_not_involving_dims(hull
,
6508 isl_dim_out
, 0, n_out
);
6510 return isl_stat_error
;
6511 edge
->weight
= hull
->n_eq
;
6512 isl_basic_map_free(hull
);
6514 if (edge
->weight
> graph
->max_weight
)
6515 graph
->max_weight
= edge
->weight
;
6521 /* Call compute_schedule_finish_band on each of the clusters in "c"
6522 * in their topological order. This order is determined by the scc
6523 * fields of the nodes in "graph".
6524 * Combine the results in a sequence expressing the topological order.
6526 * If there is only one cluster left, then there is no need to introduce
6527 * a sequence node. Also, in this case, the cluster necessarily contains
6528 * the SCC at position 0 in the original graph and is therefore also
6529 * stored in the first cluster of "c".
6531 static __isl_give isl_schedule_node
*finish_bands_clustering(
6532 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6533 struct isl_clustering
*c
)
6537 isl_union_set_list
*filters
;
6539 if (graph
->scc
== 1)
6540 return compute_schedule_finish_band(node
, &c
->cluster
[0], 0);
6542 ctx
= isl_schedule_node_get_ctx(node
);
6544 filters
= extract_sccs(ctx
, graph
);
6545 node
= isl_schedule_node_insert_sequence(node
, filters
);
6547 for (i
= 0; i
< graph
->scc
; ++i
) {
6548 int j
= c
->scc_cluster
[i
];
6549 node
= isl_schedule_node_child(node
, i
);
6550 node
= isl_schedule_node_child(node
, 0);
6551 node
= compute_schedule_finish_band(node
, &c
->cluster
[j
], 0);
6552 node
= isl_schedule_node_parent(node
);
6553 node
= isl_schedule_node_parent(node
);
6559 /* Compute a schedule for a connected dependence graph by first considering
6560 * each strongly connected component (SCC) in the graph separately and then
6561 * incrementally combining them into clusters.
6562 * Return the updated schedule node.
6564 * Initially, each cluster consists of a single SCC, each with its
6565 * own band schedule. The algorithm then tries to merge pairs
6566 * of clusters along a proximity edge until no more suitable
6567 * proximity edges can be found. During this merging, the schedule
6568 * is maintained in the individual SCCs.
6569 * After the merging is completed, the full resulting clusters
6570 * are extracted and in finish_bands_clustering,
6571 * compute_schedule_finish_band is called on each of them to integrate
6572 * the band into "node" and to continue the computation.
6574 * compute_weights initializes the weights that are used by find_proximity.
6576 static __isl_give isl_schedule_node
*compute_schedule_wcc_clustering(
6577 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6580 struct isl_clustering c
;
6583 ctx
= isl_schedule_node_get_ctx(node
);
6585 if (clustering_init(ctx
, &c
, graph
) < 0)
6588 if (compute_weights(graph
, &c
) < 0)
6592 i
= find_proximity(graph
, &c
);
6595 if (i
>= graph
->n_edge
)
6597 if (merge_clusters_along_edge(ctx
, graph
, i
, &c
) < 0)
6601 if (extract_clusters(ctx
, graph
, &c
) < 0)
6604 node
= finish_bands_clustering(node
, graph
, &c
);
6606 clustering_free(ctx
, &c
);
6609 clustering_free(ctx
, &c
);
6610 return isl_schedule_node_free(node
);
6613 /* Compute a schedule for a connected dependence graph and return
6614 * the updated schedule node.
6616 * If Feautrier's algorithm is selected, we first recursively try to satisfy
6617 * as many validity dependences as possible. When all validity dependences
6618 * are satisfied we extend the schedule to a full-dimensional schedule.
6620 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
6621 * depending on whether the user has selected the option to try and
6622 * compute a schedule for the entire (weakly connected) component first.
6623 * If there is only a single strongly connected component (SCC), then
6624 * there is no point in trying to combine SCCs
6625 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
6626 * is called instead.
6628 static __isl_give isl_schedule_node
*compute_schedule_wcc(
6629 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
6636 ctx
= isl_schedule_node_get_ctx(node
);
6637 if (detect_sccs(ctx
, graph
) < 0)
6638 return isl_schedule_node_free(node
);
6640 if (compute_maxvar(graph
) < 0)
6641 return isl_schedule_node_free(node
);
6643 if (need_feautrier_step(ctx
, graph
))
6644 return compute_schedule_wcc_feautrier(node
, graph
);
6646 if (graph
->scc
<= 1 || isl_options_get_schedule_whole_component(ctx
))
6647 return compute_schedule_wcc_whole(node
, graph
);
6649 return compute_schedule_wcc_clustering(node
, graph
);
6652 /* Compute a schedule for each group of nodes identified by node->scc
6653 * separately and then combine them in a sequence node (or as set node
6654 * if graph->weak is set) inserted at position "node" of the schedule tree.
6655 * Return the updated schedule node.
6657 * If "wcc" is set then each of the groups belongs to a single
6658 * weakly connected component in the dependence graph so that
6659 * there is no need for compute_sub_schedule to look for weakly
6660 * connected components.
6662 static __isl_give isl_schedule_node
*compute_component_schedule(
6663 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
6668 isl_union_set_list
*filters
;
6672 ctx
= isl_schedule_node_get_ctx(node
);
6674 filters
= extract_sccs(ctx
, graph
);
6676 node
= isl_schedule_node_insert_set(node
, filters
);
6678 node
= isl_schedule_node_insert_sequence(node
, filters
);
6680 for (component
= 0; component
< graph
->scc
; ++component
) {
6681 node
= isl_schedule_node_child(node
, component
);
6682 node
= isl_schedule_node_child(node
, 0);
6683 node
= compute_sub_schedule(node
, ctx
, graph
,
6685 &edge_scc_exactly
, component
, wcc
);
6686 node
= isl_schedule_node_parent(node
);
6687 node
= isl_schedule_node_parent(node
);
6693 /* Compute a schedule for the given dependence graph and insert it at "node".
6694 * Return the updated schedule node.
6696 * We first check if the graph is connected (through validity and conditional
6697 * validity dependences) and, if not, compute a schedule
6698 * for each component separately.
6699 * If the schedule_serialize_sccs option is set, then we check for strongly
6700 * connected components instead and compute a separate schedule for
6701 * each such strongly connected component.
6703 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
6704 struct isl_sched_graph
*graph
)
6711 ctx
= isl_schedule_node_get_ctx(node
);
6712 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
6713 if (detect_sccs(ctx
, graph
) < 0)
6714 return isl_schedule_node_free(node
);
6716 if (detect_wccs(ctx
, graph
) < 0)
6717 return isl_schedule_node_free(node
);
6721 return compute_component_schedule(node
, graph
, 1);
6723 return compute_schedule_wcc(node
, graph
);
6726 /* Compute a schedule on sc->domain that respects the given schedule
6729 * In particular, the schedule respects all the validity dependences.
6730 * If the default isl scheduling algorithm is used, it tries to minimize
6731 * the dependence distances over the proximity dependences.
6732 * If Feautrier's scheduling algorithm is used, the proximity dependence
6733 * distances are only minimized during the extension to a full-dimensional
6736 * If there are any condition and conditional validity dependences,
6737 * then the conditional validity dependences may be violated inside
6738 * a tilable band, provided they have no adjacent non-local
6739 * condition dependences.
6741 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
6742 __isl_take isl_schedule_constraints
*sc
)
6744 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
6745 struct isl_sched_graph graph
= { 0 };
6746 isl_schedule
*sched
;
6747 isl_schedule_node
*node
;
6748 isl_union_set
*domain
;
6750 sc
= isl_schedule_constraints_align_params(sc
);
6752 domain
= isl_schedule_constraints_get_domain(sc
);
6753 if (isl_union_set_n_set(domain
) == 0) {
6754 isl_schedule_constraints_free(sc
);
6755 return isl_schedule_from_domain(domain
);
6758 if (graph_init(&graph
, sc
) < 0)
6759 domain
= isl_union_set_free(domain
);
6761 node
= isl_schedule_node_from_domain(domain
);
6762 node
= isl_schedule_node_child(node
, 0);
6764 node
= compute_schedule(node
, &graph
);
6765 sched
= isl_schedule_node_get_schedule(node
);
6766 isl_schedule_node_free(node
);
6768 graph_free(ctx
, &graph
);
6769 isl_schedule_constraints_free(sc
);
6774 /* Compute a schedule for the given union of domains that respects
6775 * all the validity dependences and minimizes
6776 * the dependence distances over the proximity dependences.
6778 * This function is kept for backward compatibility.
6780 __isl_give isl_schedule
*isl_union_set_compute_schedule(
6781 __isl_take isl_union_set
*domain
,
6782 __isl_take isl_union_map
*validity
,
6783 __isl_take isl_union_map
*proximity
)
6785 isl_schedule_constraints
*sc
;
6787 sc
= isl_schedule_constraints_on_domain(domain
);
6788 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
6789 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
6791 return isl_schedule_constraints_compute_schedule(sc
);