2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <isl_ctx_private.h>
15 #include <isl_map_private.h>
16 #include <isl_space_private.h>
17 #include <isl_aff_private.h>
19 #include <isl/constraint.h>
20 #include <isl/schedule.h>
21 #include <isl/schedule_node.h>
22 #include <isl_mat_private.h>
23 #include <isl_vec_private.h>
25 #include <isl/union_set.h>
28 #include <isl_dim_map.h>
29 #include <isl/map_to_basic_set.h>
31 #include <isl_options_private.h>
32 #include <isl_tarjan.h>
33 #include <isl_morph.h>
36 * The scheduling algorithm implemented in this file was inspired by
37 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
38 * Parallelization and Locality Optimization in the Polyhedral Model".
42 isl_edge_validity
= 0,
43 isl_edge_first
= isl_edge_validity
,
46 isl_edge_conditional_validity
,
48 isl_edge_last
= isl_edge_proximity
,
52 /* The constraints that need to be satisfied by a schedule on "domain".
54 * "context" specifies extra constraints on the parameters.
56 * "validity" constraints map domain elements i to domain elements
57 * that should be scheduled after i. (Hard constraint)
58 * "proximity" constraints map domain elements i to domains elements
59 * that should be scheduled as early as possible after i (or before i).
62 * "condition" and "conditional_validity" constraints map possibly "tagged"
63 * domain elements i -> s to "tagged" domain elements j -> t.
64 * The elements of the "conditional_validity" constraints, but without the
65 * tags (i.e., the elements i -> j) are treated as validity constraints,
66 * except that during the construction of a tilable band,
67 * the elements of the "conditional_validity" constraints may be violated
68 * provided that all adjacent elements of the "condition" constraints
69 * are local within the band.
70 * A dependence is local within a band if domain and range are mapped
71 * to the same schedule point by the band.
73 struct isl_schedule_constraints
{
74 isl_union_set
*domain
;
77 isl_union_map
*constraint
[isl_edge_last
+ 1];
80 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
81 __isl_keep isl_schedule_constraints
*sc
)
84 isl_schedule_constraints
*sc_copy
;
87 ctx
= isl_union_set_get_ctx(sc
->domain
);
88 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
92 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
93 sc_copy
->context
= isl_set_copy(sc
->context
);
94 if (!sc_copy
->domain
|| !sc_copy
->context
)
95 return isl_schedule_constraints_free(sc_copy
);
97 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
98 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
99 if (!sc_copy
->constraint
[i
])
100 return isl_schedule_constraints_free(sc_copy
);
107 /* Construct an isl_schedule_constraints object for computing a schedule
108 * on "domain". The initial object does not impose any constraints.
110 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
111 __isl_take isl_union_set
*domain
)
115 isl_schedule_constraints
*sc
;
116 isl_union_map
*empty
;
117 enum isl_edge_type i
;
122 ctx
= isl_union_set_get_ctx(domain
);
123 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
127 space
= isl_union_set_get_space(domain
);
129 sc
->context
= isl_set_universe(isl_space_copy(space
));
130 empty
= isl_union_map_empty(space
);
131 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
132 sc
->constraint
[i
] = isl_union_map_copy(empty
);
133 if (!sc
->constraint
[i
])
134 sc
->domain
= isl_union_set_free(sc
->domain
);
136 isl_union_map_free(empty
);
138 if (!sc
->domain
|| !sc
->context
)
139 return isl_schedule_constraints_free(sc
);
143 isl_union_set_free(domain
);
147 /* Replace the context of "sc" by "context".
149 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_context(
150 __isl_take isl_schedule_constraints
*sc
, __isl_take isl_set
*context
)
155 isl_set_free(sc
->context
);
156 sc
->context
= context
;
160 isl_schedule_constraints_free(sc
);
161 isl_set_free(context
);
165 /* Replace the validity constraints of "sc" by "validity".
167 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
168 __isl_take isl_schedule_constraints
*sc
,
169 __isl_take isl_union_map
*validity
)
171 if (!sc
|| !validity
)
174 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
175 sc
->constraint
[isl_edge_validity
] = validity
;
179 isl_schedule_constraints_free(sc
);
180 isl_union_map_free(validity
);
184 /* Replace the coincidence constraints of "sc" by "coincidence".
186 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
187 __isl_take isl_schedule_constraints
*sc
,
188 __isl_take isl_union_map
*coincidence
)
190 if (!sc
|| !coincidence
)
193 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
194 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
198 isl_schedule_constraints_free(sc
);
199 isl_union_map_free(coincidence
);
203 /* Replace the proximity constraints of "sc" by "proximity".
205 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
206 __isl_take isl_schedule_constraints
*sc
,
207 __isl_take isl_union_map
*proximity
)
209 if (!sc
|| !proximity
)
212 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
213 sc
->constraint
[isl_edge_proximity
] = proximity
;
217 isl_schedule_constraints_free(sc
);
218 isl_union_map_free(proximity
);
222 /* Replace the conditional validity constraints of "sc" by "condition"
225 __isl_give isl_schedule_constraints
*
226 isl_schedule_constraints_set_conditional_validity(
227 __isl_take isl_schedule_constraints
*sc
,
228 __isl_take isl_union_map
*condition
,
229 __isl_take isl_union_map
*validity
)
231 if (!sc
|| !condition
|| !validity
)
234 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
235 sc
->constraint
[isl_edge_condition
] = condition
;
236 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
237 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
241 isl_schedule_constraints_free(sc
);
242 isl_union_map_free(condition
);
243 isl_union_map_free(validity
);
247 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
248 __isl_take isl_schedule_constraints
*sc
)
250 enum isl_edge_type i
;
255 isl_union_set_free(sc
->domain
);
256 isl_set_free(sc
->context
);
257 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
258 isl_union_map_free(sc
->constraint
[i
]);
265 isl_ctx
*isl_schedule_constraints_get_ctx(
266 __isl_keep isl_schedule_constraints
*sc
)
268 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
271 /* Return the domain of "sc".
273 __isl_give isl_union_set
*isl_schedule_constraints_get_domain(
274 __isl_keep isl_schedule_constraints
*sc
)
279 return isl_union_set_copy(sc
->domain
);
282 /* Return the validity constraints of "sc".
284 __isl_give isl_union_map
*isl_schedule_constraints_get_validity(
285 __isl_keep isl_schedule_constraints
*sc
)
290 return isl_union_map_copy(sc
->constraint
[isl_edge_validity
]);
293 /* Return the coincidence constraints of "sc".
295 __isl_give isl_union_map
*isl_schedule_constraints_get_coincidence(
296 __isl_keep isl_schedule_constraints
*sc
)
301 return isl_union_map_copy(sc
->constraint
[isl_edge_coincidence
]);
304 /* Return the conditional validity constraints of "sc".
306 __isl_give isl_union_map
*isl_schedule_constraints_get_conditional_validity(
307 __isl_keep isl_schedule_constraints
*sc
)
313 isl_union_map_copy(sc
->constraint
[isl_edge_conditional_validity
]);
316 /* Return the conditions for the conditional validity constraints of "sc".
318 __isl_give isl_union_map
*
319 isl_schedule_constraints_get_conditional_validity_condition(
320 __isl_keep isl_schedule_constraints
*sc
)
325 return isl_union_map_copy(sc
->constraint
[isl_edge_condition
]);
328 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
333 fprintf(stderr
, "domain: ");
334 isl_union_set_dump(sc
->domain
);
335 fprintf(stderr
, "context: ");
336 isl_set_dump(sc
->context
);
337 fprintf(stderr
, "validity: ");
338 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
339 fprintf(stderr
, "proximity: ");
340 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
341 fprintf(stderr
, "coincidence: ");
342 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
343 fprintf(stderr
, "condition: ");
344 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
345 fprintf(stderr
, "conditional_validity: ");
346 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
349 /* Align the parameters of the fields of "sc".
351 static __isl_give isl_schedule_constraints
*
352 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
355 enum isl_edge_type i
;
360 space
= isl_union_set_get_space(sc
->domain
);
361 space
= isl_space_align_params(space
, isl_set_get_space(sc
->context
));
362 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
363 space
= isl_space_align_params(space
,
364 isl_union_map_get_space(sc
->constraint
[i
]));
366 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
367 sc
->constraint
[i
] = isl_union_map_align_params(
368 sc
->constraint
[i
], isl_space_copy(space
));
369 if (!sc
->constraint
[i
])
370 space
= isl_space_free(space
);
372 sc
->context
= isl_set_align_params(sc
->context
, isl_space_copy(space
));
373 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
374 if (!sc
->context
|| !sc
->domain
)
375 return isl_schedule_constraints_free(sc
);
380 /* Return the total number of isl_maps in the constraints of "sc".
382 static __isl_give
int isl_schedule_constraints_n_map(
383 __isl_keep isl_schedule_constraints
*sc
)
385 enum isl_edge_type i
;
388 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
389 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
394 /* Internal information about a node that is used during the construction
396 * space represents the space in which the domain lives
397 * sched is a matrix representation of the schedule being constructed
398 * for this node; if compressed is set, then this schedule is
399 * defined over the compressed domain space
400 * sched_map is an isl_map representation of the same (partial) schedule
401 * sched_map may be NULL; if compressed is set, then this map
402 * is defined over the uncompressed domain space
403 * rank is the number of linearly independent rows in the linear part
405 * the columns of cmap represent a change of basis for the schedule
406 * coefficients; the first rank columns span the linear part of
408 * cinv is the inverse of cmap.
409 * start is the first variable in the LP problem in the sequences that
410 * represents the schedule coefficients of this node
411 * nvar is the dimension of the domain
412 * nparam is the number of parameters or 0 if we are not constructing
413 * a parametric schedule
415 * If compressed is set, then hull represents the constraints
416 * that were used to derive the compression, while compress and
417 * decompress map the original space to the compressed space and
420 * scc is the index of SCC (or WCC) this node belongs to
422 * coincident contains a boolean for each of the rows of the schedule,
423 * indicating whether the corresponding scheduling dimension satisfies
424 * the coincidence constraints in the sense that the corresponding
425 * dependence distances are zero.
427 struct isl_sched_node
{
431 isl_multi_aff
*compress
;
432 isl_multi_aff
*decompress
;
447 static int node_has_space(const void *entry
, const void *val
)
449 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
450 isl_space
*dim
= (isl_space
*)val
;
452 return isl_space_is_equal(node
->space
, dim
);
455 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
457 return node
->scc
== scc
;
460 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
462 return node
->scc
<= scc
;
465 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
467 return node
->scc
>= scc
;
470 /* An edge in the dependence graph. An edge may be used to
471 * ensure validity of the generated schedule, to minimize the dependence
474 * map is the dependence relation, with i -> j in the map if j depends on i
475 * tagged_condition and tagged_validity contain the union of all tagged
476 * condition or conditional validity dependence relations that
477 * specialize the dependence relation "map"; that is,
478 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
479 * or "tagged_validity", then i -> j is an element of "map".
480 * If these fields are NULL, then they represent the empty relation.
481 * src is the source node
482 * dst is the sink node
484 * types is a bit vector containing the types of this edge.
485 * validity is set if the edge is used to ensure correctness
486 * coincidence is used to enforce zero dependence distances
487 * proximity is set if the edge is used to minimize dependence distances
488 * condition is set if the edge represents a condition
489 * for a conditional validity schedule constraint
490 * local can only be set for condition edges and indicates that
491 * the dependence distance over the edge should be zero
492 * conditional_validity is set if the edge is used to conditionally
495 * For validity edges, start and end mark the sequence of inequality
496 * constraints in the LP problem that encode the validity constraint
497 * corresponding to this edge.
499 struct isl_sched_edge
{
501 isl_union_map
*tagged_condition
;
502 isl_union_map
*tagged_validity
;
504 struct isl_sched_node
*src
;
505 struct isl_sched_node
*dst
;
513 /* Is "edge" marked as being of type "type"?
515 static int is_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
517 return ISL_FL_ISSET(edge
->types
, 1 << type
);
520 /* Mark "edge" as being of type "type".
522 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
524 ISL_FL_SET(edge
->types
, 1 << type
);
527 /* No longer mark "edge" as being of type "type"?
529 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
531 ISL_FL_CLR(edge
->types
, 1 << type
);
534 /* Is "edge" marked as a validity edge?
536 static int is_validity(struct isl_sched_edge
*edge
)
538 return is_type(edge
, isl_edge_validity
);
541 /* Mark "edge" as a validity edge.
543 static void set_validity(struct isl_sched_edge
*edge
)
545 set_type(edge
, isl_edge_validity
);
548 /* Is "edge" marked as a proximity edge?
550 static int is_proximity(struct isl_sched_edge
*edge
)
552 return is_type(edge
, isl_edge_proximity
);
555 /* Is "edge" marked as a local edge?
557 static int is_local(struct isl_sched_edge
*edge
)
559 return is_type(edge
, isl_edge_local
);
562 /* Mark "edge" as a local edge.
564 static void set_local(struct isl_sched_edge
*edge
)
566 set_type(edge
, isl_edge_local
);
569 /* No longer mark "edge" as a local edge.
571 static void clear_local(struct isl_sched_edge
*edge
)
573 clear_type(edge
, isl_edge_local
);
576 /* Is "edge" marked as a coincidence edge?
578 static int is_coincidence(struct isl_sched_edge
*edge
)
580 return is_type(edge
, isl_edge_coincidence
);
583 /* Is "edge" marked as a condition edge?
585 static int is_condition(struct isl_sched_edge
*edge
)
587 return is_type(edge
, isl_edge_condition
);
590 /* Is "edge" marked as a conditional validity edge?
592 static int is_conditional_validity(struct isl_sched_edge
*edge
)
594 return is_type(edge
, isl_edge_conditional_validity
);
597 /* Internal information about the dependence graph used during
598 * the construction of the schedule.
600 * intra_hmap is a cache, mapping dependence relations to their dual,
601 * for dependences from a node to itself
602 * inter_hmap is a cache, mapping dependence relations to their dual,
603 * for dependences between distinct nodes
604 * if compression is involved then the key for these maps
605 * it the original, uncompressed dependence relation, while
606 * the value is the dual of the compressed dependence relation.
608 * n is the number of nodes
609 * node is the list of nodes
610 * maxvar is the maximal number of variables over all nodes
611 * max_row is the allocated number of rows in the schedule
612 * n_row is the current (maximal) number of linearly independent
613 * rows in the node schedules
614 * n_total_row is the current number of rows in the node schedules
615 * band_start is the starting row in the node schedules of the current band
616 * root is set if this graph is the original dependence graph,
617 * without any splitting
619 * sorted contains a list of node indices sorted according to the
620 * SCC to which a node belongs
622 * n_edge is the number of edges
623 * edge is the list of edges
624 * max_edge contains the maximal number of edges of each type;
625 * in particular, it contains the number of edges in the inital graph.
626 * edge_table contains pointers into the edge array, hashed on the source
627 * and sink spaces; there is one such table for each type;
628 * a given edge may be referenced from more than one table
629 * if the corresponding relation appears in more than one of the
630 * sets of dependences; however, for each type there is only
631 * a single edge between a given pair of source and sink space
632 * in the entire graph
634 * node_table contains pointers into the node array, hashed on the space
636 * region contains a list of variable sequences that should be non-trivial
638 * lp contains the (I)LP problem used to obtain new schedule rows
640 * src_scc and dst_scc are the source and sink SCCs of an edge with
641 * conflicting constraints
643 * scc represents the number of components
644 * weak is set if the components are weakly connected
646 struct isl_sched_graph
{
647 isl_map_to_basic_set
*intra_hmap
;
648 isl_map_to_basic_set
*inter_hmap
;
650 struct isl_sched_node
*node
;
663 struct isl_sched_edge
*edge
;
665 int max_edge
[isl_edge_last
+ 1];
666 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
668 struct isl_hash_table
*node_table
;
669 struct isl_region
*region
;
680 /* Initialize node_table based on the list of nodes.
682 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
686 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
687 if (!graph
->node_table
)
690 for (i
= 0; i
< graph
->n
; ++i
) {
691 struct isl_hash_table_entry
*entry
;
694 hash
= isl_space_get_hash(graph
->node
[i
].space
);
695 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
697 graph
->node
[i
].space
, 1);
700 entry
->data
= &graph
->node
[i
];
706 /* Return a pointer to the node that lives within the given space,
707 * or NULL if there is no such node.
709 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
710 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
712 struct isl_hash_table_entry
*entry
;
715 hash
= isl_space_get_hash(dim
);
716 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
717 &node_has_space
, dim
, 0);
719 return entry
? entry
->data
: NULL
;
722 static int edge_has_src_and_dst(const void *entry
, const void *val
)
724 const struct isl_sched_edge
*edge
= entry
;
725 const struct isl_sched_edge
*temp
= val
;
727 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
730 /* Add the given edge to graph->edge_table[type].
732 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
733 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
734 struct isl_sched_edge
*edge
)
736 struct isl_hash_table_entry
*entry
;
739 hash
= isl_hash_init();
740 hash
= isl_hash_builtin(hash
, edge
->src
);
741 hash
= isl_hash_builtin(hash
, edge
->dst
);
742 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
743 &edge_has_src_and_dst
, edge
, 1);
745 return isl_stat_error
;
751 /* Allocate the edge_tables based on the maximal number of edges of
754 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
758 for (i
= 0; i
<= isl_edge_last
; ++i
) {
759 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
761 if (!graph
->edge_table
[i
])
768 /* If graph->edge_table[type] contains an edge from the given source
769 * to the given destination, then return the hash table entry of this edge.
770 * Otherwise, return NULL.
772 static struct isl_hash_table_entry
*graph_find_edge_entry(
773 struct isl_sched_graph
*graph
,
774 enum isl_edge_type type
,
775 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
777 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
779 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
781 hash
= isl_hash_init();
782 hash
= isl_hash_builtin(hash
, temp
.src
);
783 hash
= isl_hash_builtin(hash
, temp
.dst
);
784 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
785 &edge_has_src_and_dst
, &temp
, 0);
789 /* If graph->edge_table[type] contains an edge from the given source
790 * to the given destination, then return this edge.
791 * Otherwise, return NULL.
793 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
794 enum isl_edge_type type
,
795 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
797 struct isl_hash_table_entry
*entry
;
799 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
806 /* Check whether the dependence graph has an edge of the given type
807 * between the given two nodes.
809 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
810 enum isl_edge_type type
,
811 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
813 struct isl_sched_edge
*edge
;
816 edge
= graph_find_edge(graph
, type
, src
, dst
);
820 empty
= isl_map_plain_is_empty(edge
->map
);
822 return isl_bool_error
;
827 /* Look for any edge with the same src, dst and map fields as "model".
829 * Return the matching edge if one can be found.
830 * Return "model" if no matching edge is found.
831 * Return NULL on error.
833 static struct isl_sched_edge
*graph_find_matching_edge(
834 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
836 enum isl_edge_type i
;
837 struct isl_sched_edge
*edge
;
839 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
842 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
845 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
855 /* Remove the given edge from all the edge_tables that refer to it.
857 static void graph_remove_edge(struct isl_sched_graph
*graph
,
858 struct isl_sched_edge
*edge
)
860 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
861 enum isl_edge_type i
;
863 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
864 struct isl_hash_table_entry
*entry
;
866 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
869 if (entry
->data
!= edge
)
871 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
875 /* Check whether the dependence graph has any edge
876 * between the given two nodes.
878 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
879 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
881 enum isl_edge_type i
;
884 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
885 r
= graph_has_edge(graph
, i
, src
, dst
);
893 /* Check whether the dependence graph has a validity edge
894 * between the given two nodes.
896 * Conditional validity edges are essentially validity edges that
897 * can be ignored if the corresponding condition edges are iteration private.
898 * Here, we are only checking for the presence of validity
899 * edges, so we need to consider the conditional validity edges too.
900 * In particular, this function is used during the detection
901 * of strongly connected components and we cannot ignore
902 * conditional validity edges during this detection.
904 static isl_bool
graph_has_validity_edge(struct isl_sched_graph
*graph
,
905 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
909 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
913 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
916 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
917 int n_node
, int n_edge
)
922 graph
->n_edge
= n_edge
;
923 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
924 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
925 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
926 graph
->edge
= isl_calloc_array(ctx
,
927 struct isl_sched_edge
, graph
->n_edge
);
929 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
930 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
932 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
936 for(i
= 0; i
< graph
->n
; ++i
)
937 graph
->sorted
[i
] = i
;
942 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
946 isl_map_to_basic_set_free(graph
->intra_hmap
);
947 isl_map_to_basic_set_free(graph
->inter_hmap
);
950 for (i
= 0; i
< graph
->n
; ++i
) {
951 isl_space_free(graph
->node
[i
].space
);
952 isl_set_free(graph
->node
[i
].hull
);
953 isl_multi_aff_free(graph
->node
[i
].compress
);
954 isl_multi_aff_free(graph
->node
[i
].decompress
);
955 isl_mat_free(graph
->node
[i
].sched
);
956 isl_map_free(graph
->node
[i
].sched_map
);
957 isl_mat_free(graph
->node
[i
].cmap
);
958 isl_mat_free(graph
->node
[i
].cinv
);
960 free(graph
->node
[i
].coincident
);
965 for (i
= 0; i
< graph
->n_edge
; ++i
) {
966 isl_map_free(graph
->edge
[i
].map
);
967 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
968 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
972 for (i
= 0; i
<= isl_edge_last
; ++i
)
973 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
974 isl_hash_table_free(ctx
, graph
->node_table
);
975 isl_basic_set_free(graph
->lp
);
978 /* For each "set" on which this function is called, increment
979 * graph->n by one and update graph->maxvar.
981 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
983 struct isl_sched_graph
*graph
= user
;
984 int nvar
= isl_set_dim(set
, isl_dim_set
);
987 if (nvar
> graph
->maxvar
)
988 graph
->maxvar
= nvar
;
995 /* Add the number of basic maps in "map" to *n.
997 static isl_stat
add_n_basic_map(__isl_take isl_map
*map
, void *user
)
1001 *n
+= isl_map_n_basic_map(map
);
1007 /* Compute the number of rows that should be allocated for the schedule.
1008 * In particular, we need one row for each variable or one row
1009 * for each basic map in the dependences.
1010 * Note that it is practically impossible to exhaust both
1011 * the number of dependences and the number of variables.
1013 static int compute_max_row(struct isl_sched_graph
*graph
,
1014 __isl_keep isl_schedule_constraints
*sc
)
1016 enum isl_edge_type i
;
1021 if (isl_union_set_foreach_set(sc
->domain
, &init_n_maxvar
, graph
) < 0)
1024 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
1025 if (isl_union_map_foreach_map(sc
->constraint
[i
],
1026 &add_n_basic_map
, &n_edge
) < 0)
1028 graph
->max_row
= n_edge
+ graph
->maxvar
;
1033 /* Does "bset" have any defining equalities for its set variables?
1035 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
1042 n
= isl_basic_set_dim(bset
, isl_dim_set
);
1043 for (i
= 0; i
< n
; ++i
) {
1046 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
1055 /* Add a new node to the graph representing the given space.
1056 * "nvar" is the (possibly compressed) number of variables and
1057 * may be smaller than then number of set variables in "space"
1058 * if "compressed" is set.
1059 * If "compressed" is set, then "hull" represents the constraints
1060 * that were used to derive the compression, while "compress" and
1061 * "decompress" map the original space to the compressed space and
1063 * If "compressed" is not set, then "hull", "compress" and "decompress"
1066 static isl_stat
add_node(struct isl_sched_graph
*graph
,
1067 __isl_take isl_space
*space
, int nvar
, int compressed
,
1068 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
1069 __isl_take isl_multi_aff
*decompress
)
1077 return isl_stat_error
;
1079 ctx
= isl_space_get_ctx(space
);
1080 nparam
= isl_space_dim(space
, isl_dim_param
);
1081 if (!ctx
->opt
->schedule_parametric
)
1083 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
1084 graph
->node
[graph
->n
].space
= space
;
1085 graph
->node
[graph
->n
].nvar
= nvar
;
1086 graph
->node
[graph
->n
].nparam
= nparam
;
1087 graph
->node
[graph
->n
].sched
= sched
;
1088 graph
->node
[graph
->n
].sched_map
= NULL
;
1089 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
1090 graph
->node
[graph
->n
].coincident
= coincident
;
1091 graph
->node
[graph
->n
].compressed
= compressed
;
1092 graph
->node
[graph
->n
].hull
= hull
;
1093 graph
->node
[graph
->n
].compress
= compress
;
1094 graph
->node
[graph
->n
].decompress
= decompress
;
1097 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
1098 return isl_stat_error
;
1099 if (compressed
&& (!hull
|| !compress
|| !decompress
))
1100 return isl_stat_error
;
1105 /* Add a new node to the graph representing the given set.
1107 * If any of the set variables is defined by an equality, then
1108 * we perform variable compression such that we can perform
1109 * the scheduling on the compressed domain.
1111 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1116 isl_basic_set
*hull
;
1119 isl_multi_aff
*compress
, *decompress
;
1120 struct isl_sched_graph
*graph
= user
;
1122 space
= isl_set_get_space(set
);
1123 hull
= isl_set_affine_hull(set
);
1124 hull
= isl_basic_set_remove_divs(hull
);
1125 nvar
= isl_space_dim(space
, isl_dim_set
);
1126 has_equality
= has_any_defining_equality(hull
);
1128 if (has_equality
< 0)
1130 if (!has_equality
) {
1131 isl_basic_set_free(hull
);
1132 return add_node(graph
, space
, nvar
, 0, NULL
, NULL
, NULL
);
1135 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
1136 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1137 compress
= isl_morph_get_var_multi_aff(morph
);
1138 morph
= isl_morph_inverse(morph
);
1139 decompress
= isl_morph_get_var_multi_aff(morph
);
1140 isl_morph_free(morph
);
1142 hull_set
= isl_set_from_basic_set(hull
);
1143 return add_node(graph
, space
, nvar
, 1, hull_set
, compress
, decompress
);
1145 isl_basic_set_free(hull
);
1146 isl_space_free(space
);
1147 return isl_stat_error
;
1150 struct isl_extract_edge_data
{
1151 enum isl_edge_type type
;
1152 struct isl_sched_graph
*graph
;
1155 /* Merge edge2 into edge1, freeing the contents of edge2.
1156 * Return 0 on success and -1 on failure.
1158 * edge1 and edge2 are assumed to have the same value for the map field.
1160 static int merge_edge(struct isl_sched_edge
*edge1
,
1161 struct isl_sched_edge
*edge2
)
1163 edge1
->types
|= edge2
->types
;
1164 isl_map_free(edge2
->map
);
1166 if (is_condition(edge2
)) {
1167 if (!edge1
->tagged_condition
)
1168 edge1
->tagged_condition
= edge2
->tagged_condition
;
1170 edge1
->tagged_condition
=
1171 isl_union_map_union(edge1
->tagged_condition
,
1172 edge2
->tagged_condition
);
1175 if (is_conditional_validity(edge2
)) {
1176 if (!edge1
->tagged_validity
)
1177 edge1
->tagged_validity
= edge2
->tagged_validity
;
1179 edge1
->tagged_validity
=
1180 isl_union_map_union(edge1
->tagged_validity
,
1181 edge2
->tagged_validity
);
1184 if (is_condition(edge2
) && !edge1
->tagged_condition
)
1186 if (is_conditional_validity(edge2
) && !edge1
->tagged_validity
)
1192 /* Insert dummy tags in domain and range of "map".
1194 * In particular, if "map" is of the form
1200 * [A -> dummy_tag] -> [B -> dummy_tag]
1202 * where the dummy_tags are identical and equal to any dummy tags
1203 * introduced by any other call to this function.
1205 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1211 isl_set
*domain
, *range
;
1213 ctx
= isl_map_get_ctx(map
);
1215 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1216 space
= isl_space_params(isl_map_get_space(map
));
1217 space
= isl_space_set_from_params(space
);
1218 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1219 space
= isl_space_map_from_set(space
);
1221 domain
= isl_map_wrap(map
);
1222 range
= isl_map_wrap(isl_map_universe(space
));
1223 map
= isl_map_from_domain_and_range(domain
, range
);
1224 map
= isl_map_zip(map
);
1229 /* Given that at least one of "src" or "dst" is compressed, return
1230 * a map between the spaces of these nodes restricted to the affine
1231 * hull that was used in the compression.
1233 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1234 struct isl_sched_node
*dst
)
1238 if (src
->compressed
)
1239 dom
= isl_set_copy(src
->hull
);
1241 dom
= isl_set_universe(isl_space_copy(src
->space
));
1242 if (dst
->compressed
)
1243 ran
= isl_set_copy(dst
->hull
);
1245 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1247 return isl_map_from_domain_and_range(dom
, ran
);
1250 /* Intersect the domains of the nested relations in domain and range
1251 * of "tagged" with "map".
1253 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1254 __isl_keep isl_map
*map
)
1258 tagged
= isl_map_zip(tagged
);
1259 set
= isl_map_wrap(isl_map_copy(map
));
1260 tagged
= isl_map_intersect_domain(tagged
, set
);
1261 tagged
= isl_map_zip(tagged
);
1265 /* Return a pointer to the node that lives in the domain space of "map"
1266 * or NULL if there is no such node.
1268 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1269 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1271 struct isl_sched_node
*node
;
1274 space
= isl_space_domain(isl_map_get_space(map
));
1275 node
= graph_find_node(ctx
, graph
, space
);
1276 isl_space_free(space
);
1281 /* Return a pointer to the node that lives in the range space of "map"
1282 * or NULL if there is no such node.
1284 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1285 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1287 struct isl_sched_node
*node
;
1290 space
= isl_space_range(isl_map_get_space(map
));
1291 node
= graph_find_node(ctx
, graph
, space
);
1292 isl_space_free(space
);
1297 /* Add a new edge to the graph based on the given map
1298 * and add it to data->graph->edge_table[data->type].
1299 * If a dependence relation of a given type happens to be identical
1300 * to one of the dependence relations of a type that was added before,
1301 * then we don't create a new edge, but instead mark the original edge
1302 * as also representing a dependence of the current type.
1304 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1305 * may be specified as "tagged" dependence relations. That is, "map"
1306 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1307 * the dependence on iterations and a and b are tags.
1308 * edge->map is set to the relation containing the elements i -> j,
1309 * while edge->tagged_condition and edge->tagged_validity contain
1310 * the union of all the "map" relations
1311 * for which extract_edge is called that result in the same edge->map.
1313 * If the source or the destination node is compressed, then
1314 * intersect both "map" and "tagged" with the constraints that
1315 * were used to construct the compression.
1316 * This ensures that there are no schedule constraints defined
1317 * outside of these domains, while the scheduler no longer has
1318 * any control over those outside parts.
1320 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1322 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1323 struct isl_extract_edge_data
*data
= user
;
1324 struct isl_sched_graph
*graph
= data
->graph
;
1325 struct isl_sched_node
*src
, *dst
;
1326 struct isl_sched_edge
*edge
;
1327 isl_map
*tagged
= NULL
;
1329 if (data
->type
== isl_edge_condition
||
1330 data
->type
== isl_edge_conditional_validity
) {
1331 if (isl_map_can_zip(map
)) {
1332 tagged
= isl_map_copy(map
);
1333 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1335 tagged
= insert_dummy_tags(isl_map_copy(map
));
1339 src
= find_domain_node(ctx
, graph
, map
);
1340 dst
= find_range_node(ctx
, graph
, map
);
1344 isl_map_free(tagged
);
1348 if (src
->compressed
|| dst
->compressed
) {
1350 hull
= extract_hull(src
, dst
);
1352 tagged
= map_intersect_domains(tagged
, hull
);
1353 map
= isl_map_intersect(map
, hull
);
1356 graph
->edge
[graph
->n_edge
].src
= src
;
1357 graph
->edge
[graph
->n_edge
].dst
= dst
;
1358 graph
->edge
[graph
->n_edge
].map
= map
;
1359 graph
->edge
[graph
->n_edge
].types
= 0;
1360 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1361 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1362 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1363 if (data
->type
== isl_edge_condition
)
1364 graph
->edge
[graph
->n_edge
].tagged_condition
=
1365 isl_union_map_from_map(tagged
);
1366 if (data
->type
== isl_edge_conditional_validity
)
1367 graph
->edge
[graph
->n_edge
].tagged_validity
=
1368 isl_union_map_from_map(tagged
);
1370 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1373 return isl_stat_error
;
1375 if (edge
== &graph
->edge
[graph
->n_edge
])
1376 return graph_edge_table_add(ctx
, graph
, data
->type
,
1377 &graph
->edge
[graph
->n_edge
++]);
1379 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1382 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1385 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1387 * The context is included in the domain before the nodes of
1388 * the graphs are extracted in order to be able to exploit
1389 * any possible additional equalities.
1390 * Note that this intersection is only performed locally here.
1392 static isl_stat
graph_init(struct isl_sched_graph
*graph
,
1393 __isl_keep isl_schedule_constraints
*sc
)
1396 isl_union_set
*domain
;
1397 struct isl_extract_edge_data data
;
1398 enum isl_edge_type i
;
1402 return isl_stat_error
;
1404 ctx
= isl_schedule_constraints_get_ctx(sc
);
1406 domain
= isl_schedule_constraints_get_domain(sc
);
1407 graph
->n
= isl_union_set_n_set(domain
);
1408 isl_union_set_free(domain
);
1410 if (graph_alloc(ctx
, graph
, graph
->n
,
1411 isl_schedule_constraints_n_map(sc
)) < 0)
1412 return isl_stat_error
;
1414 if (compute_max_row(graph
, sc
) < 0)
1415 return isl_stat_error
;
1418 domain
= isl_schedule_constraints_get_domain(sc
);
1419 domain
= isl_union_set_intersect_params(domain
,
1420 isl_set_copy(sc
->context
));
1421 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1422 isl_union_set_free(domain
);
1424 return isl_stat_error
;
1425 if (graph_init_table(ctx
, graph
) < 0)
1426 return isl_stat_error
;
1427 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
1428 graph
->max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
1429 if (graph_init_edge_tables(ctx
, graph
) < 0)
1430 return isl_stat_error
;
1433 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1435 if (isl_union_map_foreach_map(sc
->constraint
[i
],
1436 &extract_edge
, &data
) < 0)
1437 return isl_stat_error
;
1443 /* Check whether there is any dependence from node[j] to node[i]
1444 * or from node[i] to node[j].
1446 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1449 struct isl_sched_graph
*graph
= user
;
1451 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1454 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1457 /* Check whether there is a (conditional) validity dependence from node[j]
1458 * to node[i], forcing node[i] to follow node[j].
1460 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1462 struct isl_sched_graph
*graph
= user
;
1464 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1467 /* Use Tarjan's algorithm for computing the strongly connected components
1468 * in the dependence graph (only validity edges).
1469 * If weak is set, we consider the graph to be undirected and
1470 * we effectively compute the (weakly) connected components.
1471 * Additionally, we also consider other edges when weak is set.
1473 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
1476 struct isl_tarjan_graph
*g
= NULL
;
1478 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
1479 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
1488 while (g
->order
[i
] != -1) {
1489 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1497 isl_tarjan_graph_free(g
);
1502 /* Apply Tarjan's algorithm to detect the strongly connected components
1503 * in the dependence graph.
1505 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1507 return detect_ccs(ctx
, graph
, 0);
1510 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1511 * in the dependence graph.
1513 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1515 return detect_ccs(ctx
, graph
, 1);
1518 static int cmp_scc(const void *a
, const void *b
, void *data
)
1520 struct isl_sched_graph
*graph
= data
;
1524 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1527 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1529 static int sort_sccs(struct isl_sched_graph
*graph
)
1531 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1534 /* Given a dependence relation R from "node" to itself,
1535 * construct the set of coefficients of valid constraints for elements
1536 * in that dependence relation.
1537 * In particular, the result contains tuples of coefficients
1538 * c_0, c_n, c_x such that
1540 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1544 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1546 * We choose here to compute the dual of delta R.
1547 * Alternatively, we could have computed the dual of R, resulting
1548 * in a set of tuples c_0, c_n, c_x, c_y, and then
1549 * plugged in (c_0, c_n, c_x, -c_x).
1551 * If "node" has been compressed, then the dependence relation
1552 * is also compressed before the set of coefficients is computed.
1554 static __isl_give isl_basic_set
*intra_coefficients(
1555 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1556 __isl_take isl_map
*map
)
1560 isl_basic_set
*coef
;
1562 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1563 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1565 key
= isl_map_copy(map
);
1566 if (node
->compressed
) {
1567 map
= isl_map_preimage_domain_multi_aff(map
,
1568 isl_multi_aff_copy(node
->decompress
));
1569 map
= isl_map_preimage_range_multi_aff(map
,
1570 isl_multi_aff_copy(node
->decompress
));
1572 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1573 coef
= isl_set_coefficients(delta
);
1574 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1575 isl_basic_set_copy(coef
));
1580 /* Given a dependence relation R, construct the set of coefficients
1581 * of valid constraints for elements in that dependence relation.
1582 * In particular, the result contains tuples of coefficients
1583 * c_0, c_n, c_x, c_y such that
1585 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1587 * If the source or destination nodes of "edge" have been compressed,
1588 * then the dependence relation is also compressed before
1589 * the set of coefficients is computed.
1591 static __isl_give isl_basic_set
*inter_coefficients(
1592 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1593 __isl_take isl_map
*map
)
1597 isl_basic_set
*coef
;
1599 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1600 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1602 key
= isl_map_copy(map
);
1603 if (edge
->src
->compressed
)
1604 map
= isl_map_preimage_domain_multi_aff(map
,
1605 isl_multi_aff_copy(edge
->src
->decompress
));
1606 if (edge
->dst
->compressed
)
1607 map
= isl_map_preimage_range_multi_aff(map
,
1608 isl_multi_aff_copy(edge
->dst
->decompress
));
1609 set
= isl_map_wrap(isl_map_remove_divs(map
));
1610 coef
= isl_set_coefficients(set
);
1611 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1612 isl_basic_set_copy(coef
));
1617 /* Add constraints to graph->lp that force validity for the given
1618 * dependence from a node i to itself.
1619 * That is, add constraints that enforce
1621 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1622 * = c_i_x (y - x) >= 0
1624 * for each (x,y) in R.
1625 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1626 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1627 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1628 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1630 * Actually, we do not construct constraints for the c_i_x themselves,
1631 * but for the coefficients of c_i_x written as a linear combination
1632 * of the columns in node->cmap.
1634 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1635 struct isl_sched_edge
*edge
)
1638 isl_map
*map
= isl_map_copy(edge
->map
);
1639 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1641 isl_dim_map
*dim_map
;
1642 isl_basic_set
*coef
;
1643 struct isl_sched_node
*node
= edge
->src
;
1645 coef
= intra_coefficients(graph
, node
, map
);
1647 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1649 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1650 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1654 total
= isl_basic_set_total_dim(graph
->lp
);
1655 dim_map
= isl_dim_map_alloc(ctx
, total
);
1656 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1657 isl_space_dim(dim
, isl_dim_set
), 1,
1659 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1660 isl_space_dim(dim
, isl_dim_set
), 1,
1662 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1663 coef
->n_eq
, coef
->n_ineq
);
1664 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1666 isl_space_free(dim
);
1670 isl_space_free(dim
);
1674 /* Add constraints to graph->lp that force validity for the given
1675 * dependence from node i to node j.
1676 * That is, add constraints that enforce
1678 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1680 * for each (x,y) in R.
1681 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1682 * of valid constraints for R and then plug in
1683 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1684 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1685 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1686 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1688 * Actually, we do not construct constraints for the c_*_x themselves,
1689 * but for the coefficients of c_*_x written as a linear combination
1690 * of the columns in node->cmap.
1692 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1693 struct isl_sched_edge
*edge
)
1696 isl_map
*map
= isl_map_copy(edge
->map
);
1697 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1699 isl_dim_map
*dim_map
;
1700 isl_basic_set
*coef
;
1701 struct isl_sched_node
*src
= edge
->src
;
1702 struct isl_sched_node
*dst
= edge
->dst
;
1704 coef
= inter_coefficients(graph
, edge
, map
);
1706 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1708 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1709 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1710 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1711 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1712 isl_mat_copy(dst
->cmap
));
1716 total
= isl_basic_set_total_dim(graph
->lp
);
1717 dim_map
= isl_dim_map_alloc(ctx
, total
);
1719 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1720 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1721 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1722 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1723 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1725 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1726 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1729 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1730 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1731 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1732 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1733 isl_space_dim(dim
, isl_dim_set
), 1,
1735 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1736 isl_space_dim(dim
, isl_dim_set
), 1,
1739 edge
->start
= graph
->lp
->n_ineq
;
1740 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1741 coef
->n_eq
, coef
->n_ineq
);
1742 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1746 isl_space_free(dim
);
1747 edge
->end
= graph
->lp
->n_ineq
;
1751 isl_space_free(dim
);
1755 /* Add constraints to graph->lp that bound the dependence distance for the given
1756 * dependence from a node i to itself.
1757 * If s = 1, we add the constraint
1759 * c_i_x (y - x) <= m_0 + m_n n
1763 * -c_i_x (y - x) + m_0 + m_n n >= 0
1765 * for each (x,y) in R.
1766 * If s = -1, we add the constraint
1768 * -c_i_x (y - x) <= m_0 + m_n n
1772 * c_i_x (y - x) + m_0 + m_n n >= 0
1774 * for each (x,y) in R.
1775 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1776 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1777 * with each coefficient (except m_0) represented as a pair of non-negative
1780 * Actually, we do not construct constraints for the c_i_x themselves,
1781 * but for the coefficients of c_i_x written as a linear combination
1782 * of the columns in node->cmap.
1785 * If "local" is set, then we add constraints
1787 * c_i_x (y - x) <= 0
1791 * -c_i_x (y - x) <= 0
1793 * instead, forcing the dependence distance to be (less than or) equal to 0.
1794 * That is, we plug in (0, 0, -s * c_i_x),
1795 * Note that dependences marked local are treated as validity constraints
1796 * by add_all_validity_constraints and therefore also have
1797 * their distances bounded by 0 from below.
1799 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1800 struct isl_sched_edge
*edge
, int s
, int local
)
1804 isl_map
*map
= isl_map_copy(edge
->map
);
1805 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1807 isl_dim_map
*dim_map
;
1808 isl_basic_set
*coef
;
1809 struct isl_sched_node
*node
= edge
->src
;
1811 coef
= intra_coefficients(graph
, node
, map
);
1813 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1815 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1816 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1820 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1821 total
= isl_basic_set_total_dim(graph
->lp
);
1822 dim_map
= isl_dim_map_alloc(ctx
, total
);
1825 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1826 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1827 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1829 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1830 isl_space_dim(dim
, isl_dim_set
), 1,
1832 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1833 isl_space_dim(dim
, isl_dim_set
), 1,
1835 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1836 coef
->n_eq
, coef
->n_ineq
);
1837 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1839 isl_space_free(dim
);
1843 isl_space_free(dim
);
1847 /* Add constraints to graph->lp that bound the dependence distance for the given
1848 * dependence from node i to node j.
1849 * If s = 1, we add the constraint
1851 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1856 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1859 * for each (x,y) in R.
1860 * If s = -1, we add the constraint
1862 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1867 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1870 * for each (x,y) in R.
1871 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1872 * of valid constraints for R and then plug in
1873 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1875 * with each coefficient (except m_0, c_j_0 and c_i_0)
1876 * represented as a pair of non-negative coefficients.
1878 * Actually, we do not construct constraints for the c_*_x themselves,
1879 * but for the coefficients of c_*_x written as a linear combination
1880 * of the columns in node->cmap.
1883 * If "local" is set, then we add constraints
1885 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1889 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1891 * instead, forcing the dependence distance to be (less than or) equal to 0.
1892 * That is, we plug in
1893 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1894 * Note that dependences marked local are treated as validity constraints
1895 * by add_all_validity_constraints and therefore also have
1896 * their distances bounded by 0 from below.
1898 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1899 struct isl_sched_edge
*edge
, int s
, int local
)
1903 isl_map
*map
= isl_map_copy(edge
->map
);
1904 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1906 isl_dim_map
*dim_map
;
1907 isl_basic_set
*coef
;
1908 struct isl_sched_node
*src
= edge
->src
;
1909 struct isl_sched_node
*dst
= edge
->dst
;
1911 coef
= inter_coefficients(graph
, edge
, map
);
1913 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1915 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1916 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1917 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1918 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1919 isl_mat_copy(dst
->cmap
));
1923 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1924 total
= isl_basic_set_total_dim(graph
->lp
);
1925 dim_map
= isl_dim_map_alloc(ctx
, total
);
1928 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1929 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1930 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1933 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1934 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1935 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1936 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1937 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1939 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1940 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1943 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1944 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1945 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1946 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1947 isl_space_dim(dim
, isl_dim_set
), 1,
1949 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1950 isl_space_dim(dim
, isl_dim_set
), 1,
1953 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1954 coef
->n_eq
, coef
->n_ineq
);
1955 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1957 isl_space_free(dim
);
1961 isl_space_free(dim
);
1965 /* Add all validity constraints to graph->lp.
1967 * An edge that is forced to be local needs to have its dependence
1968 * distances equal to zero. We take care of bounding them by 0 from below
1969 * here. add_all_proximity_constraints takes care of bounding them by 0
1972 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1973 * Otherwise, we ignore them.
1975 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1976 int use_coincidence
)
1980 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1981 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1984 local
= is_local(edge
) ||
1985 (is_coincidence(edge
) && use_coincidence
);
1986 if (!is_validity(edge
) && !local
)
1988 if (edge
->src
!= edge
->dst
)
1990 if (add_intra_validity_constraints(graph
, edge
) < 0)
1994 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1995 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1998 local
= is_local(edge
) ||
1999 (is_coincidence(edge
) && use_coincidence
);
2000 if (!is_validity(edge
) && !local
)
2002 if (edge
->src
== edge
->dst
)
2004 if (add_inter_validity_constraints(graph
, edge
) < 0)
2011 /* Add constraints to graph->lp that bound the dependence distance
2012 * for all dependence relations.
2013 * If a given proximity dependence is identical to a validity
2014 * dependence, then the dependence distance is already bounded
2015 * from below (by zero), so we only need to bound the distance
2016 * from above. (This includes the case of "local" dependences
2017 * which are treated as validity dependence by add_all_validity_constraints.)
2018 * Otherwise, we need to bound the distance both from above and from below.
2020 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2021 * Otherwise, we ignore them.
2023 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
2024 int use_coincidence
)
2028 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2029 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2032 local
= is_local(edge
) ||
2033 (is_coincidence(edge
) && use_coincidence
);
2034 if (!is_proximity(edge
) && !local
)
2036 if (edge
->src
== edge
->dst
&&
2037 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
2039 if (edge
->src
!= edge
->dst
&&
2040 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
2042 if (is_validity(edge
) || local
)
2044 if (edge
->src
== edge
->dst
&&
2045 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2047 if (edge
->src
!= edge
->dst
&&
2048 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2055 /* Compute a basis for the rows in the linear part of the schedule
2056 * and extend this basis to a full basis. The remaining rows
2057 * can then be used to force linear independence from the rows
2060 * In particular, given the schedule rows S, we compute
2065 * with H the Hermite normal form of S. That is, all but the
2066 * first rank columns of H are zero and so each row in S is
2067 * a linear combination of the first rank rows of Q.
2068 * The matrix Q is then transposed because we will write the
2069 * coefficients of the next schedule row as a column vector s
2070 * and express this s as a linear combination s = Q c of the
2072 * Similarly, the matrix U is transposed such that we can
2073 * compute the coefficients c = U s from a schedule row s.
2075 static int node_update_cmap(struct isl_sched_node
*node
)
2078 int n_row
= isl_mat_rows(node
->sched
);
2080 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2081 1 + node
->nparam
, node
->nvar
);
2083 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2084 isl_mat_free(node
->cmap
);
2085 isl_mat_free(node
->cinv
);
2086 node
->cmap
= isl_mat_transpose(Q
);
2087 node
->cinv
= isl_mat_transpose(U
);
2088 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2091 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
2096 /* How many times should we count the constraints in "edge"?
2098 * If carry is set, then we are counting the number of
2099 * (validity or conditional validity) constraints that will be added
2100 * in setup_carry_lp and we count each edge exactly once.
2102 * Otherwise, we count as follows
2103 * validity -> 1 (>= 0)
2104 * validity+proximity -> 2 (>= 0 and upper bound)
2105 * proximity -> 2 (lower and upper bound)
2106 * local(+any) -> 2 (>= 0 and <= 0)
2108 * If an edge is only marked conditional_validity then it counts
2109 * as zero since it is only checked afterwards.
2111 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2112 * Otherwise, we ignore them.
2114 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
2115 int use_coincidence
)
2117 if (carry
&& !is_validity(edge
) && !is_conditional_validity(edge
))
2121 if (is_proximity(edge
) || is_local(edge
))
2123 if (use_coincidence
&& is_coincidence(edge
))
2125 if (is_validity(edge
))
2130 /* Count the number of equality and inequality constraints
2131 * that will be added for the given map.
2133 * "use_coincidence" is set if we should take into account coincidence edges.
2135 static int count_map_constraints(struct isl_sched_graph
*graph
,
2136 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2137 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
2139 isl_basic_set
*coef
;
2140 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
2147 if (edge
->src
== edge
->dst
)
2148 coef
= intra_coefficients(graph
, edge
->src
, map
);
2150 coef
= inter_coefficients(graph
, edge
, map
);
2153 *n_eq
+= f
* coef
->n_eq
;
2154 *n_ineq
+= f
* coef
->n_ineq
;
2155 isl_basic_set_free(coef
);
2160 /* Count the number of equality and inequality constraints
2161 * that will be added to the main lp problem.
2162 * We count as follows
2163 * validity -> 1 (>= 0)
2164 * validity+proximity -> 2 (>= 0 and upper bound)
2165 * proximity -> 2 (lower and upper bound)
2166 * local(+any) -> 2 (>= 0 and <= 0)
2168 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2169 * Otherwise, we ignore them.
2171 static int count_constraints(struct isl_sched_graph
*graph
,
2172 int *n_eq
, int *n_ineq
, int use_coincidence
)
2176 *n_eq
= *n_ineq
= 0;
2177 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2178 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2179 isl_map
*map
= isl_map_copy(edge
->map
);
2181 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2182 0, use_coincidence
) < 0)
2189 /* Count the number of constraints that will be added by
2190 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2193 * In practice, add_bound_coefficient_constraints only adds inequalities.
2195 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2196 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2200 if (ctx
->opt
->schedule_max_coefficient
== -1)
2203 for (i
= 0; i
< graph
->n
; ++i
)
2204 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2209 /* Add constraints that bound the values of the variable and parameter
2210 * coefficients of the schedule.
2212 * The maximal value of the coefficients is defined by the option
2213 * 'schedule_max_coefficient'.
2215 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
2216 struct isl_sched_graph
*graph
)
2219 int max_coefficient
;
2222 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
2224 if (max_coefficient
== -1)
2227 total
= isl_basic_set_total_dim(graph
->lp
);
2229 for (i
= 0; i
< graph
->n
; ++i
) {
2230 struct isl_sched_node
*node
= &graph
->node
[i
];
2231 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
2233 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2236 dim
= 1 + node
->start
+ 1 + j
;
2237 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2238 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2239 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
2246 /* Construct an ILP problem for finding schedule coefficients
2247 * that result in non-negative, but small dependence distances
2248 * over all dependences.
2249 * In particular, the dependence distances over proximity edges
2250 * are bounded by m_0 + m_n n and we compute schedule coefficients
2251 * with small values (preferably zero) of m_n and m_0.
2253 * All variables of the ILP are non-negative. The actual coefficients
2254 * may be negative, so each coefficient is represented as the difference
2255 * of two non-negative variables. The negative part always appears
2256 * immediately before the positive part.
2257 * Other than that, the variables have the following order
2259 * - sum of positive and negative parts of m_n coefficients
2261 * - sum of positive and negative parts of all c_n coefficients
2262 * (unconstrained when computing non-parametric schedules)
2263 * - sum of positive and negative parts of all c_x coefficients
2264 * - positive and negative parts of m_n coefficients
2267 * - positive and negative parts of c_i_n (if parametric)
2268 * - positive and negative parts of c_i_x
2270 * The c_i_x are not represented directly, but through the columns of
2271 * node->cmap. That is, the computed values are for variable t_i_x
2272 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2274 * The constraints are those from the edges plus two or three equalities
2275 * to express the sums.
2277 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2278 * Otherwise, we ignore them.
2280 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2281 int use_coincidence
)
2291 int max_constant_term
;
2293 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
2295 parametric
= ctx
->opt
->schedule_parametric
;
2296 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2298 total
= param_pos
+ 2 * nparam
;
2299 for (i
= 0; i
< graph
->n
; ++i
) {
2300 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2301 if (node_update_cmap(node
) < 0)
2303 node
->start
= total
;
2304 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2307 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2309 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2312 dim
= isl_space_set_alloc(ctx
, 0, total
);
2313 isl_basic_set_free(graph
->lp
);
2314 n_eq
+= 2 + parametric
;
2315 if (max_constant_term
!= -1)
2318 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2320 k
= isl_basic_set_alloc_equality(graph
->lp
);
2323 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2324 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
2325 for (i
= 0; i
< 2 * nparam
; ++i
)
2326 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
2329 k
= isl_basic_set_alloc_equality(graph
->lp
);
2332 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2333 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2334 for (i
= 0; i
< graph
->n
; ++i
) {
2335 int pos
= 1 + graph
->node
[i
].start
+ 1;
2337 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2338 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2342 k
= isl_basic_set_alloc_equality(graph
->lp
);
2345 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2346 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
2347 for (i
= 0; i
< graph
->n
; ++i
) {
2348 struct isl_sched_node
*node
= &graph
->node
[i
];
2349 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2351 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2352 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2355 if (max_constant_term
!= -1)
2356 for (i
= 0; i
< graph
->n
; ++i
) {
2357 struct isl_sched_node
*node
= &graph
->node
[i
];
2358 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2361 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2362 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2363 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
2366 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2368 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2370 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2376 /* Analyze the conflicting constraint found by
2377 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2378 * constraint of one of the edges between distinct nodes, living, moreover
2379 * in distinct SCCs, then record the source and sink SCC as this may
2380 * be a good place to cut between SCCs.
2382 static int check_conflict(int con
, void *user
)
2385 struct isl_sched_graph
*graph
= user
;
2387 if (graph
->src_scc
>= 0)
2390 con
-= graph
->lp
->n_eq
;
2392 if (con
>= graph
->lp
->n_ineq
)
2395 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2396 if (!is_validity(&graph
->edge
[i
]))
2398 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2400 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2402 if (graph
->edge
[i
].start
> con
)
2404 if (graph
->edge
[i
].end
<= con
)
2406 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2407 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2413 /* Check whether the next schedule row of the given node needs to be
2414 * non-trivial. Lower-dimensional domains may have some trivial rows,
2415 * but as soon as the number of remaining required non-trivial rows
2416 * is as large as the number or remaining rows to be computed,
2417 * all remaining rows need to be non-trivial.
2419 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2421 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2424 /* Solve the ILP problem constructed in setup_lp.
2425 * For each node such that all the remaining rows of its schedule
2426 * need to be non-trivial, we construct a non-triviality region.
2427 * This region imposes that the next row is independent of previous rows.
2428 * In particular the coefficients c_i_x are represented by t_i_x
2429 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2430 * its first columns span the rows of the previously computed part
2431 * of the schedule. The non-triviality region enforces that at least
2432 * one of the remaining components of t_i_x is non-zero, i.e.,
2433 * that the new schedule row depends on at least one of the remaining
2436 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2442 for (i
= 0; i
< graph
->n
; ++i
) {
2443 struct isl_sched_node
*node
= &graph
->node
[i
];
2444 int skip
= node
->rank
;
2445 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
2446 if (needs_row(graph
, node
))
2447 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2449 graph
->region
[i
].len
= 0;
2451 lp
= isl_basic_set_copy(graph
->lp
);
2452 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2453 graph
->region
, &check_conflict
, graph
);
2457 /* Update the schedules of all nodes based on the given solution
2458 * of the LP problem.
2459 * The new row is added to the current band.
2460 * All possibly negative coefficients are encoded as a difference
2461 * of two non-negative variables, so we need to perform the subtraction
2462 * here. Moreover, if use_cmap is set, then the solution does
2463 * not refer to the actual coefficients c_i_x, but instead to variables
2464 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2465 * In this case, we then also need to perform this multiplication
2466 * to obtain the values of c_i_x.
2468 * If coincident is set, then the caller guarantees that the new
2469 * row satisfies the coincidence constraints.
2471 static int update_schedule(struct isl_sched_graph
*graph
,
2472 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2475 isl_vec
*csol
= NULL
;
2480 isl_die(sol
->ctx
, isl_error_internal
,
2481 "no solution found", goto error
);
2482 if (graph
->n_total_row
>= graph
->max_row
)
2483 isl_die(sol
->ctx
, isl_error_internal
,
2484 "too many schedule rows", goto error
);
2486 for (i
= 0; i
< graph
->n
; ++i
) {
2487 struct isl_sched_node
*node
= &graph
->node
[i
];
2488 int pos
= node
->start
;
2489 int row
= isl_mat_rows(node
->sched
);
2492 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2496 isl_map_free(node
->sched_map
);
2497 node
->sched_map
= NULL
;
2498 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2501 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2503 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2504 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2505 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2506 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2507 for (j
= 0; j
< node
->nparam
; ++j
)
2508 node
->sched
= isl_mat_set_element(node
->sched
,
2509 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2510 for (j
= 0; j
< node
->nvar
; ++j
)
2511 isl_int_set(csol
->el
[j
],
2512 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2514 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2518 for (j
= 0; j
< node
->nvar
; ++j
)
2519 node
->sched
= isl_mat_set_element(node
->sched
,
2520 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2521 node
->coincident
[graph
->n_total_row
] = coincident
;
2527 graph
->n_total_row
++;
2536 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2537 * and return this isl_aff.
2539 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2540 struct isl_sched_node
*node
, int row
)
2548 aff
= isl_aff_zero_on_domain(ls
);
2549 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2550 aff
= isl_aff_set_constant(aff
, v
);
2551 for (j
= 0; j
< node
->nparam
; ++j
) {
2552 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2553 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2555 for (j
= 0; j
< node
->nvar
; ++j
) {
2556 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2557 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2565 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2566 * and return this multi_aff.
2568 * The result is defined over the uncompressed node domain.
2570 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2571 struct isl_sched_node
*node
, int first
, int n
)
2575 isl_local_space
*ls
;
2580 nrow
= isl_mat_rows(node
->sched
);
2581 if (node
->compressed
)
2582 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2584 space
= isl_space_copy(node
->space
);
2585 ls
= isl_local_space_from_space(isl_space_copy(space
));
2586 space
= isl_space_from_domain(space
);
2587 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2588 ma
= isl_multi_aff_zero(space
);
2590 for (i
= first
; i
< first
+ n
; ++i
) {
2591 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2592 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2595 isl_local_space_free(ls
);
2597 if (node
->compressed
)
2598 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2599 isl_multi_aff_copy(node
->compress
));
2604 /* Convert node->sched into a multi_aff and return this multi_aff.
2606 * The result is defined over the uncompressed node domain.
2608 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2609 struct isl_sched_node
*node
)
2613 nrow
= isl_mat_rows(node
->sched
);
2614 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
2617 /* Convert node->sched into a map and return this map.
2619 * The result is cached in node->sched_map, which needs to be released
2620 * whenever node->sched is updated.
2621 * It is defined over the uncompressed node domain.
2623 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2625 if (!node
->sched_map
) {
2628 ma
= node_extract_schedule_multi_aff(node
);
2629 node
->sched_map
= isl_map_from_multi_aff(ma
);
2632 return isl_map_copy(node
->sched_map
);
2635 /* Construct a map that can be used to update a dependence relation
2636 * based on the current schedule.
2637 * That is, construct a map expressing that source and sink
2638 * are executed within the same iteration of the current schedule.
2639 * This map can then be intersected with the dependence relation.
2640 * This is not the most efficient way, but this shouldn't be a critical
2643 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2644 struct isl_sched_node
*dst
)
2646 isl_map
*src_sched
, *dst_sched
;
2648 src_sched
= node_extract_schedule(src
);
2649 dst_sched
= node_extract_schedule(dst
);
2650 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2653 /* Intersect the domains of the nested relations in domain and range
2654 * of "umap" with "map".
2656 static __isl_give isl_union_map
*intersect_domains(
2657 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2659 isl_union_set
*uset
;
2661 umap
= isl_union_map_zip(umap
);
2662 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2663 umap
= isl_union_map_intersect_domain(umap
, uset
);
2664 umap
= isl_union_map_zip(umap
);
2668 /* Update the dependence relation of the given edge based
2669 * on the current schedule.
2670 * If the dependence is carried completely by the current schedule, then
2671 * it is removed from the edge_tables. It is kept in the list of edges
2672 * as otherwise all edge_tables would have to be recomputed.
2674 static int update_edge(struct isl_sched_graph
*graph
,
2675 struct isl_sched_edge
*edge
)
2680 id
= specializer(edge
->src
, edge
->dst
);
2681 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2685 if (edge
->tagged_condition
) {
2686 edge
->tagged_condition
=
2687 intersect_domains(edge
->tagged_condition
, id
);
2688 if (!edge
->tagged_condition
)
2691 if (edge
->tagged_validity
) {
2692 edge
->tagged_validity
=
2693 intersect_domains(edge
->tagged_validity
, id
);
2694 if (!edge
->tagged_validity
)
2698 empty
= isl_map_plain_is_empty(edge
->map
);
2702 graph_remove_edge(graph
, edge
);
2711 /* Does the domain of "umap" intersect "uset"?
2713 static int domain_intersects(__isl_keep isl_union_map
*umap
,
2714 __isl_keep isl_union_set
*uset
)
2718 umap
= isl_union_map_copy(umap
);
2719 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
2720 empty
= isl_union_map_is_empty(umap
);
2721 isl_union_map_free(umap
);
2723 return empty
< 0 ? -1 : !empty
;
2726 /* Does the range of "umap" intersect "uset"?
2728 static int range_intersects(__isl_keep isl_union_map
*umap
,
2729 __isl_keep isl_union_set
*uset
)
2733 umap
= isl_union_map_copy(umap
);
2734 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
2735 empty
= isl_union_map_is_empty(umap
);
2736 isl_union_map_free(umap
);
2738 return empty
< 0 ? -1 : !empty
;
2741 /* Are the condition dependences of "edge" local with respect to
2742 * the current schedule?
2744 * That is, are domain and range of the condition dependences mapped
2745 * to the same point?
2747 * In other words, is the condition false?
2749 static int is_condition_false(struct isl_sched_edge
*edge
)
2751 isl_union_map
*umap
;
2752 isl_map
*map
, *sched
, *test
;
2755 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
2756 if (empty
< 0 || empty
)
2759 umap
= isl_union_map_copy(edge
->tagged_condition
);
2760 umap
= isl_union_map_zip(umap
);
2761 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
2762 map
= isl_map_from_union_map(umap
);
2764 sched
= node_extract_schedule(edge
->src
);
2765 map
= isl_map_apply_domain(map
, sched
);
2766 sched
= node_extract_schedule(edge
->dst
);
2767 map
= isl_map_apply_range(map
, sched
);
2769 test
= isl_map_identity(isl_map_get_space(map
));
2770 local
= isl_map_is_subset(map
, test
);
2777 /* For each conditional validity constraint that is adjacent
2778 * to a condition with domain in condition_source or range in condition_sink,
2779 * turn it into an unconditional validity constraint.
2781 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
2782 __isl_take isl_union_set
*condition_source
,
2783 __isl_take isl_union_set
*condition_sink
)
2787 condition_source
= isl_union_set_coalesce(condition_source
);
2788 condition_sink
= isl_union_set_coalesce(condition_sink
);
2790 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2792 isl_union_map
*validity
;
2794 if (!is_conditional_validity(&graph
->edge
[i
]))
2796 if (is_validity(&graph
->edge
[i
]))
2799 validity
= graph
->edge
[i
].tagged_validity
;
2800 adjacent
= domain_intersects(validity
, condition_sink
);
2801 if (adjacent
>= 0 && !adjacent
)
2802 adjacent
= range_intersects(validity
, condition_source
);
2808 set_validity(&graph
->edge
[i
]);
2811 isl_union_set_free(condition_source
);
2812 isl_union_set_free(condition_sink
);
2815 isl_union_set_free(condition_source
);
2816 isl_union_set_free(condition_sink
);
2820 /* Update the dependence relations of all edges based on the current schedule
2821 * and enforce conditional validity constraints that are adjacent
2822 * to satisfied condition constraints.
2824 * First check if any of the condition constraints are satisfied
2825 * (i.e., not local to the outer schedule) and keep track of
2826 * their domain and range.
2827 * Then update all dependence relations (which removes the non-local
2829 * Finally, if any condition constraints turned out to be satisfied,
2830 * then turn all adjacent conditional validity constraints into
2831 * unconditional validity constraints.
2833 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2837 isl_union_set
*source
, *sink
;
2839 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
2840 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
2841 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2843 isl_union_set
*uset
;
2844 isl_union_map
*umap
;
2846 if (!is_condition(&graph
->edge
[i
]))
2848 if (is_local(&graph
->edge
[i
]))
2850 local
= is_condition_false(&graph
->edge
[i
]);
2858 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
2859 uset
= isl_union_map_domain(umap
);
2860 source
= isl_union_set_union(source
, uset
);
2862 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
2863 uset
= isl_union_map_range(umap
);
2864 sink
= isl_union_set_union(sink
, uset
);
2867 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2868 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2873 return unconditionalize_adjacent_validity(graph
, source
, sink
);
2875 isl_union_set_free(source
);
2876 isl_union_set_free(sink
);
2879 isl_union_set_free(source
);
2880 isl_union_set_free(sink
);
2884 static void next_band(struct isl_sched_graph
*graph
)
2886 graph
->band_start
= graph
->n_total_row
;
2889 /* Return the union of the universe domains of the nodes in "graph"
2890 * that satisfy "pred".
2892 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
2893 struct isl_sched_graph
*graph
,
2894 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
2900 for (i
= 0; i
< graph
->n
; ++i
)
2901 if (pred(&graph
->node
[i
], data
))
2905 isl_die(ctx
, isl_error_internal
,
2906 "empty component", return NULL
);
2908 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
2909 dom
= isl_union_set_from_set(set
);
2911 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
2912 if (!pred(&graph
->node
[i
], data
))
2914 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
2915 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
2921 /* Return a list of unions of universe domains, where each element
2922 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
2924 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
2925 struct isl_sched_graph
*graph
)
2928 isl_union_set_list
*filters
;
2930 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
2931 for (i
= 0; i
< graph
->scc
; ++i
) {
2934 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
2935 filters
= isl_union_set_list_add(filters
, dom
);
2941 /* Return a list of two unions of universe domains, one for the SCCs up
2942 * to and including graph->src_scc and another for the other SCCs.
2944 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
2945 struct isl_sched_graph
*graph
)
2948 isl_union_set_list
*filters
;
2950 filters
= isl_union_set_list_alloc(ctx
, 2);
2951 dom
= isl_sched_graph_domain(ctx
, graph
,
2952 &node_scc_at_most
, graph
->src_scc
);
2953 filters
= isl_union_set_list_add(filters
, dom
);
2954 dom
= isl_sched_graph_domain(ctx
, graph
,
2955 &node_scc_at_least
, graph
->src_scc
+ 1);
2956 filters
= isl_union_set_list_add(filters
, dom
);
2961 /* Copy nodes that satisfy node_pred from the src dependence graph
2962 * to the dst dependence graph.
2964 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2965 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2970 for (i
= 0; i
< src
->n
; ++i
) {
2973 if (!node_pred(&src
->node
[i
], data
))
2977 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
2978 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
2979 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
2980 dst
->node
[j
].compress
=
2981 isl_multi_aff_copy(src
->node
[i
].compress
);
2982 dst
->node
[j
].decompress
=
2983 isl_multi_aff_copy(src
->node
[i
].decompress
);
2984 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
2985 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
2986 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2987 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
2988 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
2991 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
2993 if (dst
->node
[j
].compressed
&&
2994 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
2995 !dst
->node
[j
].decompress
))
3002 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3003 * to the dst dependence graph.
3004 * If the source or destination node of the edge is not in the destination
3005 * graph, then it must be a backward proximity edge and it should simply
3008 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3009 struct isl_sched_graph
*src
,
3010 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3013 enum isl_edge_type t
;
3016 for (i
= 0; i
< src
->n_edge
; ++i
) {
3017 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3019 isl_union_map
*tagged_condition
;
3020 isl_union_map
*tagged_validity
;
3021 struct isl_sched_node
*dst_src
, *dst_dst
;
3023 if (!edge_pred(edge
, data
))
3026 if (isl_map_plain_is_empty(edge
->map
))
3029 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
3030 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
3031 if (!dst_src
|| !dst_dst
) {
3032 if (is_validity(edge
) || is_conditional_validity(edge
))
3033 isl_die(ctx
, isl_error_internal
,
3034 "backward (conditional) validity edge",
3039 map
= isl_map_copy(edge
->map
);
3040 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3041 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3043 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3044 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3045 dst
->edge
[dst
->n_edge
].map
= map
;
3046 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3047 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3048 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3051 if (edge
->tagged_condition
&& !tagged_condition
)
3053 if (edge
->tagged_validity
&& !tagged_validity
)
3056 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
3058 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
3060 if (graph_edge_table_add(ctx
, dst
, t
,
3061 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3069 /* Compute the maximal number of variables over all nodes.
3070 * This is the maximal number of linearly independent schedule
3071 * rows that we need to compute.
3072 * Just in case we end up in a part of the dependence graph
3073 * with only lower-dimensional domains, we make sure we will
3074 * compute the required amount of extra linearly independent rows.
3076 static int compute_maxvar(struct isl_sched_graph
*graph
)
3081 for (i
= 0; i
< graph
->n
; ++i
) {
3082 struct isl_sched_node
*node
= &graph
->node
[i
];
3085 if (node_update_cmap(node
) < 0)
3087 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3088 if (nvar
> graph
->maxvar
)
3089 graph
->maxvar
= nvar
;
3095 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3096 struct isl_sched_graph
*graph
);
3097 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3098 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3100 /* Compute a schedule for a subgraph of "graph". In particular, for
3101 * the graph composed of nodes that satisfy node_pred and edges that
3102 * that satisfy edge_pred.
3103 * If the subgraph is known to consist of a single component, then wcc should
3104 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3105 * Otherwise, we call compute_schedule, which will check whether the subgraph
3108 * The schedule is inserted at "node" and the updated schedule node
3111 static __isl_give isl_schedule_node
*compute_sub_schedule(
3112 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3113 struct isl_sched_graph
*graph
,
3114 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3115 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3118 struct isl_sched_graph split
= { 0 };
3119 int i
, n
= 0, n_edge
= 0;
3122 for (i
= 0; i
< graph
->n
; ++i
)
3123 if (node_pred(&graph
->node
[i
], data
))
3125 for (i
= 0; i
< graph
->n_edge
; ++i
)
3126 if (edge_pred(&graph
->edge
[i
], data
))
3128 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
3130 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
3132 if (graph_init_table(ctx
, &split
) < 0)
3134 for (t
= 0; t
<= isl_edge_last
; ++t
)
3135 split
.max_edge
[t
] = graph
->max_edge
[t
];
3136 if (graph_init_edge_tables(ctx
, &split
) < 0)
3138 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
3140 split
.n_row
= graph
->n_row
;
3141 split
.max_row
= graph
->max_row
;
3142 split
.n_total_row
= graph
->n_total_row
;
3143 split
.band_start
= graph
->band_start
;
3146 node
= compute_schedule_wcc(node
, &split
);
3148 node
= compute_schedule(node
, &split
);
3150 graph_free(ctx
, &split
);
3153 graph_free(ctx
, &split
);
3154 return isl_schedule_node_free(node
);
3157 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3159 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3162 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3164 return edge
->dst
->scc
<= scc
;
3167 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3169 return edge
->src
->scc
>= scc
;
3172 /* Reset the current band by dropping all its schedule rows.
3174 static int reset_band(struct isl_sched_graph
*graph
)
3179 drop
= graph
->n_total_row
- graph
->band_start
;
3180 graph
->n_total_row
-= drop
;
3181 graph
->n_row
-= drop
;
3183 for (i
= 0; i
< graph
->n
; ++i
) {
3184 struct isl_sched_node
*node
= &graph
->node
[i
];
3186 isl_map_free(node
->sched_map
);
3187 node
->sched_map
= NULL
;
3189 node
->sched
= isl_mat_drop_rows(node
->sched
,
3190 graph
->band_start
, drop
);
3199 /* Split the current graph into two parts and compute a schedule for each
3200 * part individually. In particular, one part consists of all SCCs up
3201 * to and including graph->src_scc, while the other part contains the other
3202 * SCCs. The split is enforced by a sequence node inserted at position "node"
3203 * in the schedule tree. Return the updated schedule node.
3204 * If either of these two parts consists of a sequence, then it is spliced
3205 * into the sequence containing the two parts.
3207 * The current band is reset. It would be possible to reuse
3208 * the previously computed rows as the first rows in the next
3209 * band, but recomputing them may result in better rows as we are looking
3210 * at a smaller part of the dependence graph.
3212 static __isl_give isl_schedule_node
*compute_split_schedule(
3213 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3217 isl_union_set_list
*filters
;
3222 if (reset_band(graph
) < 0)
3223 return isl_schedule_node_free(node
);
3227 ctx
= isl_schedule_node_get_ctx(node
);
3228 filters
= extract_split(ctx
, graph
);
3229 node
= isl_schedule_node_insert_sequence(node
, filters
);
3230 node
= isl_schedule_node_child(node
, 1);
3231 node
= isl_schedule_node_child(node
, 0);
3233 node
= compute_sub_schedule(node
, ctx
, graph
,
3234 &node_scc_at_least
, &edge_src_scc_at_least
,
3235 graph
->src_scc
+ 1, 0);
3236 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3237 node
= isl_schedule_node_parent(node
);
3238 node
= isl_schedule_node_parent(node
);
3240 node
= isl_schedule_node_sequence_splice_child(node
, 1);
3241 node
= isl_schedule_node_child(node
, 0);
3242 node
= isl_schedule_node_child(node
, 0);
3243 node
= compute_sub_schedule(node
, ctx
, graph
,
3244 &node_scc_at_most
, &edge_dst_scc_at_most
,
3246 is_seq
= isl_schedule_node_get_type(node
) == isl_schedule_node_sequence
;
3247 node
= isl_schedule_node_parent(node
);
3248 node
= isl_schedule_node_parent(node
);
3250 node
= isl_schedule_node_sequence_splice_child(node
, 0);
3255 /* Insert a band node at position "node" in the schedule tree corresponding
3256 * to the current band in "graph". Mark the band node permutable
3257 * if "permutable" is set.
3258 * The partial schedules and the coincidence property are extracted
3259 * from the graph nodes.
3260 * Return the updated schedule node.
3262 static __isl_give isl_schedule_node
*insert_current_band(
3263 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3269 isl_multi_pw_aff
*mpa
;
3270 isl_multi_union_pw_aff
*mupa
;
3276 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3277 "graph should have at least one node",
3278 return isl_schedule_node_free(node
));
3280 start
= graph
->band_start
;
3281 end
= graph
->n_total_row
;
3284 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3285 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3286 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3288 for (i
= 1; i
< graph
->n
; ++i
) {
3289 isl_multi_union_pw_aff
*mupa_i
;
3291 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3293 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3294 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3295 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3297 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3299 for (i
= 0; i
< n
; ++i
)
3300 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3301 graph
->node
[0].coincident
[start
+ i
]);
3302 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3307 /* Update the dependence relations based on the current schedule,
3308 * add the current band to "node" and then continue with the computation
3310 * Return the updated schedule node.
3312 static __isl_give isl_schedule_node
*compute_next_band(
3313 __isl_take isl_schedule_node
*node
,
3314 struct isl_sched_graph
*graph
, int permutable
)
3321 ctx
= isl_schedule_node_get_ctx(node
);
3322 if (update_edges(ctx
, graph
) < 0)
3323 return isl_schedule_node_free(node
);
3324 node
= insert_current_band(node
, graph
, permutable
);
3327 node
= isl_schedule_node_child(node
, 0);
3328 node
= compute_schedule(node
, graph
);
3329 node
= isl_schedule_node_parent(node
);
3334 /* Add constraints to graph->lp that force the dependence "map" (which
3335 * is part of the dependence relation of "edge")
3336 * to be respected and attempt to carry it, where the edge is one from
3337 * a node j to itself. "pos" is the sequence number of the given map.
3338 * That is, add constraints that enforce
3340 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3341 * = c_j_x (y - x) >= e_i
3343 * for each (x,y) in R.
3344 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3345 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3346 * with each coefficient in c_j_x represented as a pair of non-negative
3349 static int add_intra_constraints(struct isl_sched_graph
*graph
,
3350 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3353 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3355 isl_dim_map
*dim_map
;
3356 isl_basic_set
*coef
;
3357 struct isl_sched_node
*node
= edge
->src
;
3359 coef
= intra_coefficients(graph
, node
, map
);
3363 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3365 total
= isl_basic_set_total_dim(graph
->lp
);
3366 dim_map
= isl_dim_map_alloc(ctx
, total
);
3367 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3368 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
3369 isl_space_dim(dim
, isl_dim_set
), 1,
3371 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
3372 isl_space_dim(dim
, isl_dim_set
), 1,
3374 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3375 coef
->n_eq
, coef
->n_ineq
);
3376 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3378 isl_space_free(dim
);
3383 /* Add constraints to graph->lp that force the dependence "map" (which
3384 * is part of the dependence relation of "edge")
3385 * to be respected and attempt to carry it, where the edge is one from
3386 * node j to node k. "pos" is the sequence number of the given map.
3387 * That is, add constraints that enforce
3389 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3391 * for each (x,y) in R.
3392 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3393 * of valid constraints for R and then plug in
3394 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3395 * with each coefficient (except e_i, c_k_0 and c_j_0)
3396 * represented as a pair of non-negative coefficients.
3398 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3399 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3402 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3404 isl_dim_map
*dim_map
;
3405 isl_basic_set
*coef
;
3406 struct isl_sched_node
*src
= edge
->src
;
3407 struct isl_sched_node
*dst
= edge
->dst
;
3409 coef
= inter_coefficients(graph
, edge
, map
);
3413 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3415 total
= isl_basic_set_total_dim(graph
->lp
);
3416 dim_map
= isl_dim_map_alloc(ctx
, total
);
3418 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3420 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
3421 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
3422 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
3423 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
3424 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3426 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
3427 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3430 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
3431 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
3432 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
3433 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
3434 isl_space_dim(dim
, isl_dim_set
), 1,
3436 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
3437 isl_space_dim(dim
, isl_dim_set
), 1,
3440 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3441 coef
->n_eq
, coef
->n_ineq
);
3442 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3444 isl_space_free(dim
);
3449 /* Add constraints to graph->lp that force all (conditional) validity
3450 * dependences to be respected and attempt to carry them.
3452 static int add_all_constraints(struct isl_sched_graph
*graph
)
3458 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3459 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3461 if (!is_validity(edge
) && !is_conditional_validity(edge
))
3464 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3465 isl_basic_map
*bmap
;
3468 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3469 map
= isl_map_from_basic_map(bmap
);
3471 if (edge
->src
== edge
->dst
&&
3472 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3474 if (edge
->src
!= edge
->dst
&&
3475 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3484 /* Count the number of equality and inequality constraints
3485 * that will be added to the carry_lp problem.
3486 * We count each edge exactly once.
3488 static int count_all_constraints(struct isl_sched_graph
*graph
,
3489 int *n_eq
, int *n_ineq
)
3493 *n_eq
= *n_ineq
= 0;
3494 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3495 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3496 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3497 isl_basic_map
*bmap
;
3500 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3501 map
= isl_map_from_basic_map(bmap
);
3503 if (count_map_constraints(graph
, edge
, map
,
3504 n_eq
, n_ineq
, 1, 0) < 0)
3512 /* Construct an LP problem for finding schedule coefficients
3513 * such that the schedule carries as many dependences as possible.
3514 * In particular, for each dependence i, we bound the dependence distance
3515 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3516 * of all e_i's. Dependences with e_i = 0 in the solution are simply
3517 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3518 * Note that if the dependence relation is a union of basic maps,
3519 * then we have to consider each basic map individually as it may only
3520 * be possible to carry the dependences expressed by some of those
3521 * basic maps and not all of them.
3522 * Below, we consider each of those basic maps as a separate "edge".
3524 * All variables of the LP are non-negative. The actual coefficients
3525 * may be negative, so each coefficient is represented as the difference
3526 * of two non-negative variables. The negative part always appears
3527 * immediately before the positive part.
3528 * Other than that, the variables have the following order
3530 * - sum of (1 - e_i) over all edges
3531 * - sum of positive and negative parts of all c_n coefficients
3532 * (unconstrained when computing non-parametric schedules)
3533 * - sum of positive and negative parts of all c_x coefficients
3538 * - positive and negative parts of c_i_n (if parametric)
3539 * - positive and negative parts of c_i_x
3541 * The constraints are those from the (validity) edges plus three equalities
3542 * to express the sums and n_edge inequalities to express e_i <= 1.
3544 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3554 for (i
= 0; i
< graph
->n_edge
; ++i
)
3555 n_edge
+= graph
->edge
[i
].map
->n
;
3558 for (i
= 0; i
< graph
->n
; ++i
) {
3559 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3560 node
->start
= total
;
3561 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
3564 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3567 dim
= isl_space_set_alloc(ctx
, 0, total
);
3568 isl_basic_set_free(graph
->lp
);
3571 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3572 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3574 k
= isl_basic_set_alloc_equality(graph
->lp
);
3577 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3578 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3579 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3580 for (i
= 0; i
< n_edge
; ++i
)
3581 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3583 k
= isl_basic_set_alloc_equality(graph
->lp
);
3586 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3587 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
3588 for (i
= 0; i
< graph
->n
; ++i
) {
3589 int pos
= 1 + graph
->node
[i
].start
+ 1;
3591 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
3592 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3595 k
= isl_basic_set_alloc_equality(graph
->lp
);
3598 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3599 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
3600 for (i
= 0; i
< graph
->n
; ++i
) {
3601 struct isl_sched_node
*node
= &graph
->node
[i
];
3602 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3604 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
3605 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3608 for (i
= 0; i
< n_edge
; ++i
) {
3609 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3612 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3613 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3614 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3617 if (add_all_constraints(graph
) < 0)
3623 static __isl_give isl_schedule_node
*compute_component_schedule(
3624 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3627 /* Comparison function for sorting the statements based on
3628 * the corresponding value in "r".
3630 static int smaller_value(const void *a
, const void *b
, void *data
)
3636 return isl_int_cmp(r
->el
[*i1
], r
->el
[*i2
]);
3639 /* If the schedule_split_scaled option is set and if the linear
3640 * parts of the scheduling rows for all nodes in the graphs have
3641 * a non-trivial common divisor, then split off the remainder of the
3642 * constant term modulo this common divisor from the linear part.
3643 * Otherwise, insert a band node directly and continue with
3644 * the construction of the schedule.
3646 * If a non-trivial common divisor is found, then
3647 * the linear part is reduced and the remainder is enforced
3648 * by a sequence node with the children placed in the order
3649 * of this remainder.
3650 * In particular, we assign an scc index based on the remainder and
3651 * then rely on compute_component_schedule to insert the sequence and
3652 * to continue the schedule construction on each part.
3654 static __isl_give isl_schedule_node
*split_scaled(
3655 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3668 ctx
= isl_schedule_node_get_ctx(node
);
3669 if (!ctx
->opt
->schedule_split_scaled
)
3670 return compute_next_band(node
, graph
, 0);
3672 return compute_next_band(node
, graph
, 0);
3675 isl_int_init(gcd_i
);
3677 isl_int_set_si(gcd
, 0);
3679 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3681 for (i
= 0; i
< graph
->n
; ++i
) {
3682 struct isl_sched_node
*node
= &graph
->node
[i
];
3683 int cols
= isl_mat_cols(node
->sched
);
3685 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3686 isl_int_gcd(gcd
, gcd
, gcd_i
);
3689 isl_int_clear(gcd_i
);
3691 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3693 return compute_next_band(node
, graph
, 0);
3696 r
= isl_vec_alloc(ctx
, graph
->n
);
3697 order
= isl_calloc_array(ctx
, int, graph
->n
);
3701 for (i
= 0; i
< graph
->n
; ++i
) {
3702 struct isl_sched_node
*node
= &graph
->node
[i
];
3705 isl_int_fdiv_r(r
->el
[i
], node
->sched
->row
[row
][0], gcd
);
3706 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3707 node
->sched
->row
[row
][0], gcd
);
3708 isl_int_mul(node
->sched
->row
[row
][0],
3709 node
->sched
->row
[row
][0], gcd
);
3710 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3715 if (isl_sort(order
, graph
->n
, sizeof(order
[0]), &smaller_value
, r
) < 0)
3719 for (i
= 0; i
< graph
->n
; ++i
) {
3720 if (i
> 0 && isl_int_ne(r
->el
[order
[i
- 1]], r
->el
[order
[i
]]))
3722 graph
->node
[order
[i
]].scc
= scc
;
3731 if (update_edges(ctx
, graph
) < 0)
3732 return isl_schedule_node_free(node
);
3733 node
= insert_current_band(node
, graph
, 0);
3736 node
= isl_schedule_node_child(node
, 0);
3737 node
= compute_component_schedule(node
, graph
, 0);
3738 node
= isl_schedule_node_parent(node
);
3745 return isl_schedule_node_free(node
);
3748 /* Is the schedule row "sol" trivial on node "node"?
3749 * That is, is the solution zero on the dimensions orthogonal to
3750 * the previously found solutions?
3751 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3753 * Each coefficient is represented as the difference between
3754 * two non-negative values in "sol". "sol" has been computed
3755 * in terms of the original iterators (i.e., without use of cmap).
3756 * We construct the schedule row s and write it as a linear
3757 * combination of (linear combinations of) previously computed schedule rows.
3758 * s = Q c or c = U s.
3759 * If the final entries of c are all zero, then the solution is trivial.
3761 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3771 if (node
->nvar
== node
->rank
)
3774 ctx
= isl_vec_get_ctx(sol
);
3775 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3779 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3781 for (i
= 0; i
< node
->nvar
; ++i
)
3782 isl_int_sub(node_sol
->el
[i
],
3783 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3785 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3790 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3791 node
->nvar
- node
->rank
) == -1;
3793 isl_vec_free(node_sol
);
3798 /* Is the schedule row "sol" trivial on any node where it should
3800 * "sol" has been computed in terms of the original iterators
3801 * (i.e., without use of cmap).
3802 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3804 static int is_any_trivial(struct isl_sched_graph
*graph
,
3805 __isl_keep isl_vec
*sol
)
3809 for (i
= 0; i
< graph
->n
; ++i
) {
3810 struct isl_sched_node
*node
= &graph
->node
[i
];
3813 if (!needs_row(graph
, node
))
3815 trivial
= is_trivial(node
, sol
);
3816 if (trivial
< 0 || trivial
)
3823 /* Construct a schedule row for each node such that as many dependences
3824 * as possible are carried and then continue with the next band.
3826 * Note that despite the fact that the problem is solved using a rational
3827 * solver, the solution is guaranteed to be integral.
3828 * Specifically, the dependence distance lower bounds e_i (and therefore
3829 * also their sum) are integers. See Lemma 5 of [1].
3831 * If the computed schedule row turns out to be trivial on one or
3832 * more nodes where it should not be trivial, then we throw it away
3833 * and try again on each component separately.
3835 * If there is only one component, then we accept the schedule row anyway,
3836 * but we do not consider it as a complete row and therefore do not
3837 * increment graph->n_row. Note that the ranks of the nodes that
3838 * do get a non-trivial schedule part will get updated regardless and
3839 * graph->maxvar is computed based on these ranks. The test for
3840 * whether more schedule rows are required in compute_schedule_wcc
3841 * is therefore not affected.
3843 * Insert a band corresponding to the schedule row at position "node"
3844 * of the schedule tree and continue with the construction of the schedule.
3845 * This insertion and the continued construction is performed by split_scaled
3846 * after optionally checking for non-trivial common divisors.
3848 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3849 * Problem, Part II: Multi-Dimensional Time.
3850 * In Intl. Journal of Parallel Programming, 1992.
3852 static __isl_give isl_schedule_node
*carry_dependences(
3853 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3866 for (i
= 0; i
< graph
->n_edge
; ++i
)
3867 n_edge
+= graph
->edge
[i
].map
->n
;
3869 ctx
= isl_schedule_node_get_ctx(node
);
3870 if (setup_carry_lp(ctx
, graph
) < 0)
3871 return isl_schedule_node_free(node
);
3873 lp
= isl_basic_set_copy(graph
->lp
);
3874 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3876 return isl_schedule_node_free(node
);
3878 if (sol
->size
== 0) {
3880 isl_die(ctx
, isl_error_internal
,
3881 "error in schedule construction",
3882 return isl_schedule_node_free(node
));
3885 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3886 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3888 isl_die(ctx
, isl_error_unknown
,
3889 "unable to carry dependences",
3890 return isl_schedule_node_free(node
));
3893 trivial
= is_any_trivial(graph
, sol
);
3895 sol
= isl_vec_free(sol
);
3896 } else if (trivial
&& graph
->scc
> 1) {
3898 return compute_component_schedule(node
, graph
, 1);
3901 if (update_schedule(graph
, sol
, 0, 0) < 0)
3902 return isl_schedule_node_free(node
);
3906 return split_scaled(node
, graph
);
3909 /* Topologically sort statements mapped to the same schedule iteration
3910 * and add insert a sequence node in front of "node"
3911 * corresponding to this order.
3913 * If it turns out to be impossible to sort the statements apart,
3914 * because different dependences impose different orderings
3915 * on the statements, then we extend the schedule such that
3916 * it carries at least one more dependence.
3918 static __isl_give isl_schedule_node
*sort_statements(
3919 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3922 isl_union_set_list
*filters
;
3927 ctx
= isl_schedule_node_get_ctx(node
);
3929 isl_die(ctx
, isl_error_internal
,
3930 "graph should have at least one node",
3931 return isl_schedule_node_free(node
));
3936 if (update_edges(ctx
, graph
) < 0)
3937 return isl_schedule_node_free(node
);
3939 if (graph
->n_edge
== 0)
3942 if (detect_sccs(ctx
, graph
) < 0)
3943 return isl_schedule_node_free(node
);
3946 if (graph
->scc
< graph
->n
)
3947 return carry_dependences(node
, graph
);
3949 filters
= extract_sccs(ctx
, graph
);
3950 node
= isl_schedule_node_insert_sequence(node
, filters
);
3955 /* Are there any (non-empty) (conditional) validity edges in the graph?
3957 static int has_validity_edges(struct isl_sched_graph
*graph
)
3961 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3964 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3969 if (is_validity(&graph
->edge
[i
]) ||
3970 is_conditional_validity(&graph
->edge
[i
]))
3977 /* Should we apply a Feautrier step?
3978 * That is, did the user request the Feautrier algorithm and are
3979 * there any validity dependences (left)?
3981 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3983 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3986 return has_validity_edges(graph
);
3989 /* Compute a schedule for a connected dependence graph using Feautrier's
3990 * multi-dimensional scheduling algorithm and return the updated schedule node.
3992 * The original algorithm is described in [1].
3993 * The main idea is to minimize the number of scheduling dimensions, by
3994 * trying to satisfy as many dependences as possible per scheduling dimension.
3996 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3997 * Problem, Part II: Multi-Dimensional Time.
3998 * In Intl. Journal of Parallel Programming, 1992.
4000 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
4001 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4003 return carry_dependences(node
, graph
);
4006 /* Turn off the "local" bit on all (condition) edges.
4008 static void clear_local_edges(struct isl_sched_graph
*graph
)
4012 for (i
= 0; i
< graph
->n_edge
; ++i
)
4013 if (is_condition(&graph
->edge
[i
]))
4014 clear_local(&graph
->edge
[i
]);
4017 /* Does "graph" have both condition and conditional validity edges?
4019 static int need_condition_check(struct isl_sched_graph
*graph
)
4022 int any_condition
= 0;
4023 int any_conditional_validity
= 0;
4025 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4026 if (is_condition(&graph
->edge
[i
]))
4028 if (is_conditional_validity(&graph
->edge
[i
]))
4029 any_conditional_validity
= 1;
4032 return any_condition
&& any_conditional_validity
;
4035 /* Does "graph" contain any coincidence edge?
4037 static int has_any_coincidence(struct isl_sched_graph
*graph
)
4041 for (i
= 0; i
< graph
->n_edge
; ++i
)
4042 if (is_coincidence(&graph
->edge
[i
]))
4048 /* Extract the final schedule row as a map with the iteration domain
4049 * of "node" as domain.
4051 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
4053 isl_local_space
*ls
;
4057 row
= isl_mat_rows(node
->sched
) - 1;
4058 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
4059 aff
= extract_schedule_row(ls
, node
, row
);
4060 return isl_map_from_aff(aff
);
4063 /* Is the conditional validity dependence in the edge with index "edge_index"
4064 * violated by the latest (i.e., final) row of the schedule?
4065 * That is, is i scheduled after j
4066 * for any conditional validity dependence i -> j?
4068 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
4070 isl_map
*src_sched
, *dst_sched
, *map
;
4071 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
4074 src_sched
= final_row(edge
->src
);
4075 dst_sched
= final_row(edge
->dst
);
4076 map
= isl_map_copy(edge
->map
);
4077 map
= isl_map_apply_domain(map
, src_sched
);
4078 map
= isl_map_apply_range(map
, dst_sched
);
4079 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
4080 empty
= isl_map_is_empty(map
);
4089 /* Does "graph" have any satisfied condition edges that
4090 * are adjacent to the conditional validity constraint with
4091 * domain "conditional_source" and range "conditional_sink"?
4093 * A satisfied condition is one that is not local.
4094 * If a condition was forced to be local already (i.e., marked as local)
4095 * then there is no need to check if it is in fact local.
4097 * Additionally, mark all adjacent condition edges found as local.
4099 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
4100 __isl_keep isl_union_set
*conditional_source
,
4101 __isl_keep isl_union_set
*conditional_sink
)
4106 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4107 int adjacent
, local
;
4108 isl_union_map
*condition
;
4110 if (!is_condition(&graph
->edge
[i
]))
4112 if (is_local(&graph
->edge
[i
]))
4115 condition
= graph
->edge
[i
].tagged_condition
;
4116 adjacent
= domain_intersects(condition
, conditional_sink
);
4117 if (adjacent
>= 0 && !adjacent
)
4118 adjacent
= range_intersects(condition
,
4119 conditional_source
);
4125 set_local(&graph
->edge
[i
]);
4127 local
= is_condition_false(&graph
->edge
[i
]);
4137 /* Are there any violated conditional validity dependences with
4138 * adjacent condition dependences that are not local with respect
4139 * to the current schedule?
4140 * That is, is the conditional validity constraint violated?
4142 * Additionally, mark all those adjacent condition dependences as local.
4143 * We also mark those adjacent condition dependences that were not marked
4144 * as local before, but just happened to be local already. This ensures
4145 * that they remain local if the schedule is recomputed.
4147 * We first collect domain and range of all violated conditional validity
4148 * dependences and then check if there are any adjacent non-local
4149 * condition dependences.
4151 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
4152 struct isl_sched_graph
*graph
)
4156 isl_union_set
*source
, *sink
;
4158 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4159 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4160 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4161 isl_union_set
*uset
;
4162 isl_union_map
*umap
;
4165 if (!is_conditional_validity(&graph
->edge
[i
]))
4168 violated
= is_violated(graph
, i
);
4176 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4177 uset
= isl_union_map_domain(umap
);
4178 source
= isl_union_set_union(source
, uset
);
4179 source
= isl_union_set_coalesce(source
);
4181 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
4182 uset
= isl_union_map_range(umap
);
4183 sink
= isl_union_set_union(sink
, uset
);
4184 sink
= isl_union_set_coalesce(sink
);
4188 any
= has_adjacent_true_conditions(graph
, source
, sink
);
4190 isl_union_set_free(source
);
4191 isl_union_set_free(sink
);
4194 isl_union_set_free(source
);
4195 isl_union_set_free(sink
);
4199 /* Compute a schedule for a connected dependence graph and return
4200 * the updated schedule node.
4202 * We try to find a sequence of as many schedule rows as possible that result
4203 * in non-negative dependence distances (independent of the previous rows
4204 * in the sequence, i.e., such that the sequence is tilable), with as
4205 * many of the initial rows as possible satisfying the coincidence constraints.
4206 * If we can't find any more rows we either
4207 * - split between SCCs and start over (assuming we found an interesting
4208 * pair of SCCs between which to split)
4209 * - continue with the next band (assuming the current band has at least
4211 * - try to carry as many dependences as possible and continue with the next
4213 * In each case, we first insert a band node in the schedule tree
4214 * if any rows have been computed.
4216 * If Feautrier's algorithm is selected, we first recursively try to satisfy
4217 * as many validity dependences as possible. When all validity dependences
4218 * are satisfied we extend the schedule to a full-dimensional schedule.
4220 * If we manage to complete the schedule, we insert a band node
4221 * (if any schedule rows were computed) and we finish off by topologically
4222 * sorting the statements based on the remaining dependences.
4224 * If ctx->opt->schedule_outer_coincidence is set, then we force the
4225 * outermost dimension to satisfy the coincidence constraints. If this
4226 * turns out to be impossible, we fall back on the general scheme above
4227 * and try to carry as many dependences as possible.
4229 * If "graph" contains both condition and conditional validity dependences,
4230 * then we need to check that that the conditional schedule constraint
4231 * is satisfied, i.e., there are no violated conditional validity dependences
4232 * that are adjacent to any non-local condition dependences.
4233 * If there are, then we mark all those adjacent condition dependences
4234 * as local and recompute the current band. Those dependences that
4235 * are marked local will then be forced to be local.
4236 * The initial computation is performed with no dependences marked as local.
4237 * If we are lucky, then there will be no violated conditional validity
4238 * dependences adjacent to any non-local condition dependences.
4239 * Otherwise, we mark some additional condition dependences as local and
4240 * recompute. We continue this process until there are no violations left or
4241 * until we are no longer able to compute a schedule.
4242 * Since there are only a finite number of dependences,
4243 * there will only be a finite number of iterations.
4245 static __isl_give isl_schedule_node
*compute_schedule_wcc(
4246 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4248 int has_coincidence
;
4249 int use_coincidence
;
4250 int force_coincidence
= 0;
4251 int check_conditional
;
4258 ctx
= isl_schedule_node_get_ctx(node
);
4259 if (detect_sccs(ctx
, graph
) < 0)
4260 return isl_schedule_node_free(node
);
4261 if (sort_sccs(graph
) < 0)
4262 return isl_schedule_node_free(node
);
4264 if (compute_maxvar(graph
) < 0)
4265 return isl_schedule_node_free(node
);
4267 if (need_feautrier_step(ctx
, graph
))
4268 return compute_schedule_wcc_feautrier(node
, graph
);
4270 clear_local_edges(graph
);
4271 check_conditional
= need_condition_check(graph
);
4272 has_coincidence
= has_any_coincidence(graph
);
4274 if (ctx
->opt
->schedule_outer_coincidence
)
4275 force_coincidence
= 1;
4277 use_coincidence
= has_coincidence
;
4278 while (graph
->n_row
< graph
->maxvar
) {
4283 graph
->src_scc
= -1;
4284 graph
->dst_scc
= -1;
4286 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
4287 return isl_schedule_node_free(node
);
4288 sol
= solve_lp(graph
);
4290 return isl_schedule_node_free(node
);
4291 if (sol
->size
== 0) {
4292 int empty
= graph
->n_total_row
== graph
->band_start
;
4295 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
4296 use_coincidence
= 0;
4299 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
4300 return compute_next_band(node
, graph
, 1);
4301 if (graph
->src_scc
>= 0)
4302 return compute_split_schedule(node
, graph
);
4304 return compute_next_band(node
, graph
, 1);
4305 return carry_dependences(node
, graph
);
4307 coincident
= !has_coincidence
|| use_coincidence
;
4308 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
4309 return isl_schedule_node_free(node
);
4311 if (!check_conditional
)
4313 violated
= has_violated_conditional_constraint(ctx
, graph
);
4315 return isl_schedule_node_free(node
);
4318 if (reset_band(graph
) < 0)
4319 return isl_schedule_node_free(node
);
4320 use_coincidence
= has_coincidence
;
4323 insert
= graph
->n_total_row
> graph
->band_start
;
4325 node
= insert_current_band(node
, graph
, 1);
4326 node
= isl_schedule_node_child(node
, 0);
4328 node
= sort_statements(node
, graph
);
4330 node
= isl_schedule_node_parent(node
);
4335 /* Compute a schedule for each group of nodes identified by node->scc
4336 * separately and then combine them in a sequence node (or as set node
4337 * if graph->weak is set) inserted at position "node" of the schedule tree.
4338 * Return the updated schedule node.
4340 * If "wcc" is set then each of the groups belongs to a single
4341 * weakly connected component in the dependence graph so that
4342 * there is no need for compute_sub_schedule to look for weakly
4343 * connected components.
4345 static __isl_give isl_schedule_node
*compute_component_schedule(
4346 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4351 isl_union_set_list
*filters
;
4355 ctx
= isl_schedule_node_get_ctx(node
);
4357 filters
= extract_sccs(ctx
, graph
);
4359 node
= isl_schedule_node_insert_set(node
, filters
);
4361 node
= isl_schedule_node_insert_sequence(node
, filters
);
4363 for (component
= 0; component
< graph
->scc
; ++component
) {
4364 node
= isl_schedule_node_child(node
, component
);
4365 node
= isl_schedule_node_child(node
, 0);
4366 node
= compute_sub_schedule(node
, ctx
, graph
,
4368 &edge_scc_exactly
, component
, wcc
);
4369 node
= isl_schedule_node_parent(node
);
4370 node
= isl_schedule_node_parent(node
);
4376 /* Compute a schedule for the given dependence graph and insert it at "node".
4377 * Return the updated schedule node.
4379 * We first check if the graph is connected (through validity and conditional
4380 * validity dependences) and, if not, compute a schedule
4381 * for each component separately.
4382 * If the schedule_serialize_sccs option is set, then we check for strongly
4383 * connected components instead and compute a separate schedule for
4384 * each such strongly connected component.
4386 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
4387 struct isl_sched_graph
*graph
)
4394 ctx
= isl_schedule_node_get_ctx(node
);
4395 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
4396 if (detect_sccs(ctx
, graph
) < 0)
4397 return isl_schedule_node_free(node
);
4399 if (detect_wccs(ctx
, graph
) < 0)
4400 return isl_schedule_node_free(node
);
4404 return compute_component_schedule(node
, graph
, 1);
4406 return compute_schedule_wcc(node
, graph
);
4409 /* Compute a schedule on sc->domain that respects the given schedule
4412 * In particular, the schedule respects all the validity dependences.
4413 * If the default isl scheduling algorithm is used, it tries to minimize
4414 * the dependence distances over the proximity dependences.
4415 * If Feautrier's scheduling algorithm is used, the proximity dependence
4416 * distances are only minimized during the extension to a full-dimensional
4419 * If there are any condition and conditional validity dependences,
4420 * then the conditional validity dependences may be violated inside
4421 * a tilable band, provided they have no adjacent non-local
4422 * condition dependences.
4424 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
4425 __isl_take isl_schedule_constraints
*sc
)
4427 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
4428 struct isl_sched_graph graph
= { 0 };
4429 isl_schedule
*sched
;
4430 isl_schedule_node
*node
;
4431 isl_union_set
*domain
;
4433 sc
= isl_schedule_constraints_align_params(sc
);
4435 domain
= isl_schedule_constraints_get_domain(sc
);
4436 if (isl_union_set_n_set(domain
) == 0) {
4437 isl_schedule_constraints_free(sc
);
4438 return isl_schedule_from_domain(domain
);
4441 if (graph_init(&graph
, sc
) < 0)
4442 domain
= isl_union_set_free(domain
);
4444 node
= isl_schedule_node_from_domain(domain
);
4445 node
= isl_schedule_node_child(node
, 0);
4447 node
= compute_schedule(node
, &graph
);
4448 sched
= isl_schedule_node_get_schedule(node
);
4449 isl_schedule_node_free(node
);
4451 graph_free(ctx
, &graph
);
4452 isl_schedule_constraints_free(sc
);
4457 /* Compute a schedule for the given union of domains that respects
4458 * all the validity dependences and minimizes
4459 * the dependence distances over the proximity dependences.
4461 * This function is kept for backward compatibility.
4463 __isl_give isl_schedule
*isl_union_set_compute_schedule(
4464 __isl_take isl_union_set
*domain
,
4465 __isl_take isl_union_map
*validity
,
4466 __isl_take isl_union_map
*proximity
)
4468 isl_schedule_constraints
*sc
;
4470 sc
= isl_schedule_constraints_on_domain(domain
);
4471 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
4472 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
4474 return isl_schedule_constraints_compute_schedule(sc
);