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>
27 #include <isl_dim_map.h>
28 #include <isl/map_to_basic_set.h>
30 #include <isl_options_private.h>
31 #include <isl_tarjan.h>
32 #include <isl_morph.h>
35 * The scheduling algorithm implemented in this file was inspired by
36 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
37 * Parallelization and Locality Optimization in the Polyhedral Model".
41 isl_edge_validity
= 0,
42 isl_edge_first
= isl_edge_validity
,
45 isl_edge_conditional_validity
,
47 isl_edge_last
= isl_edge_proximity
50 /* The constraints that need to be satisfied by a schedule on "domain".
52 * "context" specifies extra constraints on the parameters.
54 * "validity" constraints map domain elements i to domain elements
55 * that should be scheduled after i. (Hard constraint)
56 * "proximity" constraints map domain elements i to domains elements
57 * that should be scheduled as early as possible after i (or before i).
60 * "condition" and "conditional_validity" constraints map possibly "tagged"
61 * domain elements i -> s to "tagged" domain elements j -> t.
62 * The elements of the "conditional_validity" constraints, but without the
63 * tags (i.e., the elements i -> j) are treated as validity constraints,
64 * except that during the construction of a tilable band,
65 * the elements of the "conditional_validity" constraints may be violated
66 * provided that all adjacent elements of the "condition" constraints
67 * are local within the band.
68 * A dependence is local within a band if domain and range are mapped
69 * to the same schedule point by the band.
71 struct isl_schedule_constraints
{
72 isl_union_set
*domain
;
75 isl_union_map
*constraint
[isl_edge_last
+ 1];
78 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
79 __isl_keep isl_schedule_constraints
*sc
)
82 isl_schedule_constraints
*sc_copy
;
85 ctx
= isl_union_set_get_ctx(sc
->domain
);
86 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
90 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
91 sc_copy
->context
= isl_set_copy(sc
->context
);
92 if (!sc_copy
->domain
|| !sc_copy
->context
)
93 return isl_schedule_constraints_free(sc_copy
);
95 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
96 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
97 if (!sc_copy
->constraint
[i
])
98 return isl_schedule_constraints_free(sc_copy
);
105 /* Construct an isl_schedule_constraints object for computing a schedule
106 * on "domain". The initial object does not impose any constraints.
108 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
109 __isl_take isl_union_set
*domain
)
113 isl_schedule_constraints
*sc
;
114 isl_union_map
*empty
;
115 enum isl_edge_type i
;
120 ctx
= isl_union_set_get_ctx(domain
);
121 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
125 space
= isl_union_set_get_space(domain
);
127 sc
->context
= isl_set_universe(isl_space_copy(space
));
128 empty
= isl_union_map_empty(space
);
129 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
130 sc
->constraint
[i
] = isl_union_map_copy(empty
);
131 if (!sc
->constraint
[i
])
132 sc
->domain
= isl_union_set_free(sc
->domain
);
134 isl_union_map_free(empty
);
136 if (!sc
->domain
|| !sc
->context
)
137 return isl_schedule_constraints_free(sc
);
141 isl_union_set_free(domain
);
145 /* Replace the context of "sc" by "context".
147 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_context(
148 __isl_take isl_schedule_constraints
*sc
, __isl_take isl_set
*context
)
153 isl_set_free(sc
->context
);
154 sc
->context
= context
;
158 isl_schedule_constraints_free(sc
);
159 isl_set_free(context
);
163 /* Replace the validity constraints of "sc" by "validity".
165 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
166 __isl_take isl_schedule_constraints
*sc
,
167 __isl_take isl_union_map
*validity
)
169 if (!sc
|| !validity
)
172 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
173 sc
->constraint
[isl_edge_validity
] = validity
;
177 isl_schedule_constraints_free(sc
);
178 isl_union_map_free(validity
);
182 /* Replace the coincidence constraints of "sc" by "coincidence".
184 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
185 __isl_take isl_schedule_constraints
*sc
,
186 __isl_take isl_union_map
*coincidence
)
188 if (!sc
|| !coincidence
)
191 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
192 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
196 isl_schedule_constraints_free(sc
);
197 isl_union_map_free(coincidence
);
201 /* Replace the proximity constraints of "sc" by "proximity".
203 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
204 __isl_take isl_schedule_constraints
*sc
,
205 __isl_take isl_union_map
*proximity
)
207 if (!sc
|| !proximity
)
210 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
211 sc
->constraint
[isl_edge_proximity
] = proximity
;
215 isl_schedule_constraints_free(sc
);
216 isl_union_map_free(proximity
);
220 /* Replace the conditional validity constraints of "sc" by "condition"
223 __isl_give isl_schedule_constraints
*
224 isl_schedule_constraints_set_conditional_validity(
225 __isl_take isl_schedule_constraints
*sc
,
226 __isl_take isl_union_map
*condition
,
227 __isl_take isl_union_map
*validity
)
229 if (!sc
|| !condition
|| !validity
)
232 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
233 sc
->constraint
[isl_edge_condition
] = condition
;
234 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
235 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
239 isl_schedule_constraints_free(sc
);
240 isl_union_map_free(condition
);
241 isl_union_map_free(validity
);
245 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
246 __isl_take isl_schedule_constraints
*sc
)
248 enum isl_edge_type i
;
253 isl_union_set_free(sc
->domain
);
254 isl_set_free(sc
->context
);
255 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
256 isl_union_map_free(sc
->constraint
[i
]);
263 isl_ctx
*isl_schedule_constraints_get_ctx(
264 __isl_keep isl_schedule_constraints
*sc
)
266 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
269 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
274 fprintf(stderr
, "domain: ");
275 isl_union_set_dump(sc
->domain
);
276 fprintf(stderr
, "context: ");
277 isl_set_dump(sc
->context
);
278 fprintf(stderr
, "validity: ");
279 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
280 fprintf(stderr
, "proximity: ");
281 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
282 fprintf(stderr
, "coincidence: ");
283 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
284 fprintf(stderr
, "condition: ");
285 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
286 fprintf(stderr
, "conditional_validity: ");
287 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
290 /* Align the parameters of the fields of "sc".
292 static __isl_give isl_schedule_constraints
*
293 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
296 enum isl_edge_type i
;
301 space
= isl_union_set_get_space(sc
->domain
);
302 space
= isl_space_align_params(space
, isl_set_get_space(sc
->context
));
303 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
304 space
= isl_space_align_params(space
,
305 isl_union_map_get_space(sc
->constraint
[i
]));
307 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
308 sc
->constraint
[i
] = isl_union_map_align_params(
309 sc
->constraint
[i
], isl_space_copy(space
));
310 if (!sc
->constraint
[i
])
311 space
= isl_space_free(space
);
313 sc
->context
= isl_set_align_params(sc
->context
, isl_space_copy(space
));
314 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
315 if (!sc
->context
|| !sc
->domain
)
316 return isl_schedule_constraints_free(sc
);
321 /* Return the total number of isl_maps in the constraints of "sc".
323 static __isl_give
int isl_schedule_constraints_n_map(
324 __isl_keep isl_schedule_constraints
*sc
)
326 enum isl_edge_type i
;
329 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
330 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
335 /* Internal information about a node that is used during the construction
337 * space represents the space in which the domain lives
338 * sched is a matrix representation of the schedule being constructed
339 * for this node; if compressed is set, then this schedule is
340 * defined over the compressed domain space
341 * sched_map is an isl_map representation of the same (partial) schedule
342 * sched_map may be NULL; if compressed is set, then this map
343 * is defined over the uncompressed domain space
344 * rank is the number of linearly independent rows in the linear part
346 * the columns of cmap represent a change of basis for the schedule
347 * coefficients; the first rank columns span the linear part of
349 * cinv is the inverse of cmap.
350 * start is the first variable in the LP problem in the sequences that
351 * represents the schedule coefficients of this node
352 * nvar is the dimension of the domain
353 * nparam is the number of parameters or 0 if we are not constructing
354 * a parametric schedule
356 * If compressed is set, then hull represents the constraints
357 * that were used to derive the compression, while compress and
358 * decompress map the original space to the compressed space and
361 * scc is the index of SCC (or WCC) this node belongs to
363 * coincident contains a boolean for each of the rows of the schedule,
364 * indicating whether the corresponding scheduling dimension satisfies
365 * the coincidence constraints in the sense that the corresponding
366 * dependence distances are zero.
368 struct isl_sched_node
{
372 isl_multi_aff
*compress
;
373 isl_multi_aff
*decompress
;
388 static int node_has_space(const void *entry
, const void *val
)
390 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
391 isl_space
*dim
= (isl_space
*)val
;
393 return isl_space_is_equal(node
->space
, dim
);
396 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
398 return node
->scc
== scc
;
401 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
403 return node
->scc
<= scc
;
406 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
408 return node
->scc
>= scc
;
411 /* An edge in the dependence graph. An edge may be used to
412 * ensure validity of the generated schedule, to minimize the dependence
415 * map is the dependence relation, with i -> j in the map if j depends on i
416 * tagged_condition and tagged_validity contain the union of all tagged
417 * condition or conditional validity dependence relations that
418 * specialize the dependence relation "map"; that is,
419 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
420 * or "tagged_validity", then i -> j is an element of "map".
421 * If these fields are NULL, then they represent the empty relation.
422 * src is the source node
423 * dst is the sink node
424 * validity is set if the edge is used to ensure correctness
425 * coincidence is used to enforce zero dependence distances
426 * proximity is set if the edge is used to minimize dependence distances
427 * condition is set if the edge represents a condition
428 * for a conditional validity schedule constraint
429 * local can only be set for condition edges and indicates that
430 * the dependence distance over the edge should be zero
431 * conditional_validity is set if the edge is used to conditionally
434 * For validity edges, start and end mark the sequence of inequality
435 * constraints in the LP problem that encode the validity constraint
436 * corresponding to this edge.
438 struct isl_sched_edge
{
440 isl_union_map
*tagged_condition
;
441 isl_union_map
*tagged_validity
;
443 struct isl_sched_node
*src
;
444 struct isl_sched_node
*dst
;
446 unsigned validity
: 1;
447 unsigned coincidence
: 1;
448 unsigned proximity
: 1;
450 unsigned condition
: 1;
451 unsigned conditional_validity
: 1;
457 /* Internal information about the dependence graph used during
458 * the construction of the schedule.
460 * intra_hmap is a cache, mapping dependence relations to their dual,
461 * for dependences from a node to itself
462 * inter_hmap is a cache, mapping dependence relations to their dual,
463 * for dependences between distinct nodes
464 * if compression is involved then the key for these maps
465 * it the original, uncompressed dependence relation, while
466 * the value is the dual of the compressed dependence relation.
468 * n is the number of nodes
469 * node is the list of nodes
470 * maxvar is the maximal number of variables over all nodes
471 * max_row is the allocated number of rows in the schedule
472 * n_row is the current (maximal) number of linearly independent
473 * rows in the node schedules
474 * n_total_row is the current number of rows in the node schedules
475 * band_start is the starting row in the node schedules of the current band
476 * root is set if this graph is the original dependence graph,
477 * without any splitting
479 * sorted contains a list of node indices sorted according to the
480 * SCC to which a node belongs
482 * n_edge is the number of edges
483 * edge is the list of edges
484 * max_edge contains the maximal number of edges of each type;
485 * in particular, it contains the number of edges in the inital graph.
486 * edge_table contains pointers into the edge array, hashed on the source
487 * and sink spaces; there is one such table for each type;
488 * a given edge may be referenced from more than one table
489 * if the corresponding relation appears in more than of the
490 * sets of dependences
492 * node_table contains pointers into the node array, hashed on the space
494 * region contains a list of variable sequences that should be non-trivial
496 * lp contains the (I)LP problem used to obtain new schedule rows
498 * src_scc and dst_scc are the source and sink SCCs of an edge with
499 * conflicting constraints
501 * scc represents the number of components
502 * weak is set if the components are weakly connected
504 struct isl_sched_graph
{
505 isl_map_to_basic_set
*intra_hmap
;
506 isl_map_to_basic_set
*inter_hmap
;
508 struct isl_sched_node
*node
;
521 struct isl_sched_edge
*edge
;
523 int max_edge
[isl_edge_last
+ 1];
524 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
526 struct isl_hash_table
*node_table
;
527 struct isl_region
*region
;
538 /* Initialize node_table based on the list of nodes.
540 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
544 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
545 if (!graph
->node_table
)
548 for (i
= 0; i
< graph
->n
; ++i
) {
549 struct isl_hash_table_entry
*entry
;
552 hash
= isl_space_get_hash(graph
->node
[i
].space
);
553 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
555 graph
->node
[i
].space
, 1);
558 entry
->data
= &graph
->node
[i
];
564 /* Return a pointer to the node that lives within the given space,
565 * or NULL if there is no such node.
567 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
568 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
570 struct isl_hash_table_entry
*entry
;
573 hash
= isl_space_get_hash(dim
);
574 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
575 &node_has_space
, dim
, 0);
577 return entry
? entry
->data
: NULL
;
580 static int edge_has_src_and_dst(const void *entry
, const void *val
)
582 const struct isl_sched_edge
*edge
= entry
;
583 const struct isl_sched_edge
*temp
= val
;
585 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
588 /* Add the given edge to graph->edge_table[type].
590 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
591 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
593 struct isl_hash_table_entry
*entry
;
596 hash
= isl_hash_init();
597 hash
= isl_hash_builtin(hash
, edge
->src
);
598 hash
= isl_hash_builtin(hash
, edge
->dst
);
599 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
600 &edge_has_src_and_dst
, edge
, 1);
608 /* Allocate the edge_tables based on the maximal number of edges of
611 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
615 for (i
= 0; i
<= isl_edge_last
; ++i
) {
616 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
618 if (!graph
->edge_table
[i
])
625 /* If graph->edge_table[type] contains an edge from the given source
626 * to the given destination, then return the hash table entry of this edge.
627 * Otherwise, return NULL.
629 static struct isl_hash_table_entry
*graph_find_edge_entry(
630 struct isl_sched_graph
*graph
,
631 enum isl_edge_type type
,
632 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
634 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
636 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
638 hash
= isl_hash_init();
639 hash
= isl_hash_builtin(hash
, temp
.src
);
640 hash
= isl_hash_builtin(hash
, temp
.dst
);
641 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
642 &edge_has_src_and_dst
, &temp
, 0);
646 /* If graph->edge_table[type] contains an edge from the given source
647 * to the given destination, then return this edge.
648 * Otherwise, return NULL.
650 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
651 enum isl_edge_type type
,
652 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
654 struct isl_hash_table_entry
*entry
;
656 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
663 /* Check whether the dependence graph has an edge of the given type
664 * between the given two nodes.
666 static int graph_has_edge(struct isl_sched_graph
*graph
,
667 enum isl_edge_type type
,
668 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
670 struct isl_sched_edge
*edge
;
673 edge
= graph_find_edge(graph
, type
, src
, dst
);
677 empty
= isl_map_plain_is_empty(edge
->map
);
684 /* Look for any edge with the same src, dst and map fields as "model".
686 * Return the matching edge if one can be found.
687 * Return "model" if no matching edge is found.
688 * Return NULL on error.
690 static struct isl_sched_edge
*graph_find_matching_edge(
691 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
693 enum isl_edge_type i
;
694 struct isl_sched_edge
*edge
;
696 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
699 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
702 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
712 /* Remove the given edge from all the edge_tables that refer to it.
714 static void graph_remove_edge(struct isl_sched_graph
*graph
,
715 struct isl_sched_edge
*edge
)
717 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
718 enum isl_edge_type i
;
720 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
721 struct isl_hash_table_entry
*entry
;
723 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
726 if (entry
->data
!= edge
)
728 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
732 /* Check whether the dependence graph has any edge
733 * between the given two nodes.
735 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
736 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
738 enum isl_edge_type i
;
741 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
742 r
= graph_has_edge(graph
, i
, src
, dst
);
750 /* Check whether the dependence graph has a validity edge
751 * between the given two nodes.
753 * Conditional validity edges are essentially validity edges that
754 * can be ignored if the corresponding condition edges are iteration private.
755 * Here, we are only checking for the presence of validity
756 * edges, so we need to consider the conditional validity edges too.
757 * In particular, this function is used during the detection
758 * of strongly connected components and we cannot ignore
759 * conditional validity edges during this detection.
761 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
762 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
766 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
770 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
773 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
774 int n_node
, int n_edge
)
779 graph
->n_edge
= n_edge
;
780 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
781 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
782 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
783 graph
->edge
= isl_calloc_array(ctx
,
784 struct isl_sched_edge
, graph
->n_edge
);
786 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
787 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
789 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
793 for(i
= 0; i
< graph
->n
; ++i
)
794 graph
->sorted
[i
] = i
;
799 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
803 isl_map_to_basic_set_free(graph
->intra_hmap
);
804 isl_map_to_basic_set_free(graph
->inter_hmap
);
807 for (i
= 0; i
< graph
->n
; ++i
) {
808 isl_space_free(graph
->node
[i
].space
);
809 isl_set_free(graph
->node
[i
].hull
);
810 isl_multi_aff_free(graph
->node
[i
].compress
);
811 isl_multi_aff_free(graph
->node
[i
].decompress
);
812 isl_mat_free(graph
->node
[i
].sched
);
813 isl_map_free(graph
->node
[i
].sched_map
);
814 isl_mat_free(graph
->node
[i
].cmap
);
815 isl_mat_free(graph
->node
[i
].cinv
);
817 free(graph
->node
[i
].coincident
);
822 for (i
= 0; i
< graph
->n_edge
; ++i
) {
823 isl_map_free(graph
->edge
[i
].map
);
824 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
825 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
829 for (i
= 0; i
<= isl_edge_last
; ++i
)
830 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
831 isl_hash_table_free(ctx
, graph
->node_table
);
832 isl_basic_set_free(graph
->lp
);
835 /* For each "set" on which this function is called, increment
836 * graph->n by one and update graph->maxvar.
838 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
840 struct isl_sched_graph
*graph
= user
;
841 int nvar
= isl_set_dim(set
, isl_dim_set
);
844 if (nvar
> graph
->maxvar
)
845 graph
->maxvar
= nvar
;
852 /* Add the number of basic maps in "map" to *n.
854 static int add_n_basic_map(__isl_take isl_map
*map
, void *user
)
858 *n
+= isl_map_n_basic_map(map
);
864 /* Compute the number of rows that should be allocated for the schedule.
865 * In particular, we need one row for each variable or one row
866 * for each basic map in the dependences.
867 * Note that it is practically impossible to exhaust both
868 * the number of dependences and the number of variables.
870 static int compute_max_row(struct isl_sched_graph
*graph
,
871 __isl_keep isl_schedule_constraints
*sc
)
873 enum isl_edge_type i
;
878 if (isl_union_set_foreach_set(sc
->domain
, &init_n_maxvar
, graph
) < 0)
881 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
882 if (isl_union_map_foreach_map(sc
->constraint
[i
],
883 &add_n_basic_map
, &n_edge
) < 0)
885 graph
->max_row
= n_edge
+ graph
->maxvar
;
890 /* Does "bset" have any defining equalities for its set variables?
892 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
899 n
= isl_basic_set_dim(bset
, isl_dim_set
);
900 for (i
= 0; i
< n
; ++i
) {
903 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
912 /* Add a new node to the graph representing the given space.
913 * "nvar" is the (possibly compressed) number of variables and
914 * may be smaller than then number of set variables in "space"
915 * if "compressed" is set.
916 * If "compressed" is set, then "hull" represents the constraints
917 * that were used to derive the compression, while "compress" and
918 * "decompress" map the original space to the compressed space and
920 * If "compressed" is not set, then "hull", "compress" and "decompress"
923 static int add_node(struct isl_sched_graph
*graph
, __isl_take isl_space
*space
,
924 int nvar
, int compressed
, __isl_take isl_set
*hull
,
925 __isl_take isl_multi_aff
*compress
,
926 __isl_take isl_multi_aff
*decompress
)
936 ctx
= isl_space_get_ctx(space
);
937 nparam
= isl_space_dim(space
, isl_dim_param
);
938 if (!ctx
->opt
->schedule_parametric
)
940 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
941 graph
->node
[graph
->n
].space
= space
;
942 graph
->node
[graph
->n
].nvar
= nvar
;
943 graph
->node
[graph
->n
].nparam
= nparam
;
944 graph
->node
[graph
->n
].sched
= sched
;
945 graph
->node
[graph
->n
].sched_map
= NULL
;
946 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
947 graph
->node
[graph
->n
].coincident
= coincident
;
948 graph
->node
[graph
->n
].compressed
= compressed
;
949 graph
->node
[graph
->n
].hull
= hull
;
950 graph
->node
[graph
->n
].compress
= compress
;
951 graph
->node
[graph
->n
].decompress
= decompress
;
954 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
956 if (compressed
&& (!hull
|| !compress
|| !decompress
))
962 /* Add a new node to the graph representing the given set.
964 * If any of the set variables is defined by an equality, then
965 * we perform variable compression such that we can perform
966 * the scheduling on the compressed domain.
968 static int extract_node(__isl_take isl_set
*set
, void *user
)
976 isl_multi_aff
*compress
, *decompress
;
977 struct isl_sched_graph
*graph
= user
;
979 space
= isl_set_get_space(set
);
980 hull
= isl_set_affine_hull(set
);
981 hull
= isl_basic_set_remove_divs(hull
);
982 nvar
= isl_space_dim(space
, isl_dim_set
);
983 has_equality
= has_any_defining_equality(hull
);
985 if (has_equality
< 0)
988 isl_basic_set_free(hull
);
989 return add_node(graph
, space
, nvar
, 0, NULL
, NULL
, NULL
);
992 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
993 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
994 compress
= isl_morph_get_var_multi_aff(morph
);
995 morph
= isl_morph_inverse(morph
);
996 decompress
= isl_morph_get_var_multi_aff(morph
);
997 isl_morph_free(morph
);
999 hull_set
= isl_set_from_basic_set(hull
);
1000 return add_node(graph
, space
, nvar
, 1, hull_set
, compress
, decompress
);
1002 isl_basic_set_free(hull
);
1003 isl_space_free(space
);
1007 struct isl_extract_edge_data
{
1008 enum isl_edge_type type
;
1009 struct isl_sched_graph
*graph
;
1012 /* Merge edge2 into edge1, freeing the contents of edge2.
1013 * "type" is the type of the schedule constraint from which edge2 was
1015 * Return 0 on success and -1 on failure.
1017 * edge1 and edge2 are assumed to have the same value for the map field.
1019 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
1020 struct isl_sched_edge
*edge2
)
1022 edge1
->validity
|= edge2
->validity
;
1023 edge1
->coincidence
|= edge2
->coincidence
;
1024 edge1
->proximity
|= edge2
->proximity
;
1025 edge1
->condition
|= edge2
->condition
;
1026 edge1
->conditional_validity
|= edge2
->conditional_validity
;
1027 isl_map_free(edge2
->map
);
1029 if (type
== isl_edge_condition
) {
1030 if (!edge1
->tagged_condition
)
1031 edge1
->tagged_condition
= edge2
->tagged_condition
;
1033 edge1
->tagged_condition
=
1034 isl_union_map_union(edge1
->tagged_condition
,
1035 edge2
->tagged_condition
);
1038 if (type
== isl_edge_conditional_validity
) {
1039 if (!edge1
->tagged_validity
)
1040 edge1
->tagged_validity
= edge2
->tagged_validity
;
1042 edge1
->tagged_validity
=
1043 isl_union_map_union(edge1
->tagged_validity
,
1044 edge2
->tagged_validity
);
1047 if (type
== isl_edge_condition
&& !edge1
->tagged_condition
)
1049 if (type
== isl_edge_conditional_validity
&& !edge1
->tagged_validity
)
1055 /* Insert dummy tags in domain and range of "map".
1057 * In particular, if "map" is of the form
1063 * [A -> dummy_tag] -> [B -> dummy_tag]
1065 * where the dummy_tags are identical and equal to any dummy tags
1066 * introduced by any other call to this function.
1068 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1074 isl_set
*domain
, *range
;
1076 ctx
= isl_map_get_ctx(map
);
1078 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1079 space
= isl_space_params(isl_map_get_space(map
));
1080 space
= isl_space_set_from_params(space
);
1081 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1082 space
= isl_space_map_from_set(space
);
1084 domain
= isl_map_wrap(map
);
1085 range
= isl_map_wrap(isl_map_universe(space
));
1086 map
= isl_map_from_domain_and_range(domain
, range
);
1087 map
= isl_map_zip(map
);
1092 /* Given that at least one of "src" or "dst" is compressed, return
1093 * a map between the spaces of these nodes restricted to the affine
1094 * hull that was used in the compression.
1096 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1097 struct isl_sched_node
*dst
)
1101 if (src
->compressed
)
1102 dom
= isl_set_copy(src
->hull
);
1104 dom
= isl_set_universe(isl_space_copy(src
->space
));
1105 if (dst
->compressed
)
1106 ran
= isl_set_copy(dst
->hull
);
1108 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1110 return isl_map_from_domain_and_range(dom
, ran
);
1113 /* Intersect the domains of the nested relations in domain and range
1114 * of "tagged" with "map".
1116 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1117 __isl_keep isl_map
*map
)
1121 tagged
= isl_map_zip(tagged
);
1122 set
= isl_map_wrap(isl_map_copy(map
));
1123 tagged
= isl_map_intersect_domain(tagged
, set
);
1124 tagged
= isl_map_zip(tagged
);
1128 /* Add a new edge to the graph based on the given map
1129 * and add it to data->graph->edge_table[data->type].
1130 * If a dependence relation of a given type happens to be identical
1131 * to one of the dependence relations of a type that was added before,
1132 * then we don't create a new edge, but instead mark the original edge
1133 * as also representing a dependence of the current type.
1135 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1136 * may be specified as "tagged" dependence relations. That is, "map"
1137 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1138 * the dependence on iterations and a and b are tags.
1139 * edge->map is set to the relation containing the elements i -> j,
1140 * while edge->tagged_condition and edge->tagged_validity contain
1141 * the union of all the "map" relations
1142 * for which extract_edge is called that result in the same edge->map.
1144 * If the source or the destination node is compressed, then
1145 * intersect both "map" and "tagged" with the constraints that
1146 * were used to construct the compression.
1147 * This ensures that there are no schedule constraints defined
1148 * outside of these domains, while the scheduler no longer has
1149 * any control over those outside parts.
1151 static int extract_edge(__isl_take isl_map
*map
, void *user
)
1153 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1154 struct isl_extract_edge_data
*data
= user
;
1155 struct isl_sched_graph
*graph
= data
->graph
;
1156 struct isl_sched_node
*src
, *dst
;
1158 struct isl_sched_edge
*edge
;
1159 isl_map
*tagged
= NULL
;
1161 if (data
->type
== isl_edge_condition
||
1162 data
->type
== isl_edge_conditional_validity
) {
1163 if (isl_map_can_zip(map
)) {
1164 tagged
= isl_map_copy(map
);
1165 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1167 tagged
= insert_dummy_tags(isl_map_copy(map
));
1171 dim
= isl_space_domain(isl_map_get_space(map
));
1172 src
= graph_find_node(ctx
, graph
, dim
);
1173 isl_space_free(dim
);
1174 dim
= isl_space_range(isl_map_get_space(map
));
1175 dst
= graph_find_node(ctx
, graph
, dim
);
1176 isl_space_free(dim
);
1180 isl_map_free(tagged
);
1184 if (src
->compressed
|| dst
->compressed
) {
1186 hull
= extract_hull(src
, dst
);
1188 tagged
= map_intersect_domains(tagged
, hull
);
1189 map
= isl_map_intersect(map
, hull
);
1192 graph
->edge
[graph
->n_edge
].src
= src
;
1193 graph
->edge
[graph
->n_edge
].dst
= dst
;
1194 graph
->edge
[graph
->n_edge
].map
= map
;
1195 graph
->edge
[graph
->n_edge
].validity
= 0;
1196 graph
->edge
[graph
->n_edge
].coincidence
= 0;
1197 graph
->edge
[graph
->n_edge
].proximity
= 0;
1198 graph
->edge
[graph
->n_edge
].condition
= 0;
1199 graph
->edge
[graph
->n_edge
].local
= 0;
1200 graph
->edge
[graph
->n_edge
].conditional_validity
= 0;
1201 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1202 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1203 if (data
->type
== isl_edge_validity
)
1204 graph
->edge
[graph
->n_edge
].validity
= 1;
1205 if (data
->type
== isl_edge_coincidence
)
1206 graph
->edge
[graph
->n_edge
].coincidence
= 1;
1207 if (data
->type
== isl_edge_proximity
)
1208 graph
->edge
[graph
->n_edge
].proximity
= 1;
1209 if (data
->type
== isl_edge_condition
) {
1210 graph
->edge
[graph
->n_edge
].condition
= 1;
1211 graph
->edge
[graph
->n_edge
].tagged_condition
=
1212 isl_union_map_from_map(tagged
);
1214 if (data
->type
== isl_edge_conditional_validity
) {
1215 graph
->edge
[graph
->n_edge
].conditional_validity
= 1;
1216 graph
->edge
[graph
->n_edge
].tagged_validity
=
1217 isl_union_map_from_map(tagged
);
1220 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1225 if (edge
== &graph
->edge
[graph
->n_edge
])
1226 return graph_edge_table_add(ctx
, graph
, data
->type
,
1227 &graph
->edge
[graph
->n_edge
++]);
1229 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1232 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1235 /* Check whether there is any dependence from node[j] to node[i]
1236 * or from node[i] to node[j].
1238 static int node_follows_weak(int i
, int j
, void *user
)
1241 struct isl_sched_graph
*graph
= user
;
1243 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1246 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1249 /* Check whether there is a (conditional) validity dependence from node[j]
1250 * to node[i], forcing node[i] to follow node[j].
1252 static int node_follows_strong(int i
, int j
, void *user
)
1254 struct isl_sched_graph
*graph
= user
;
1256 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1259 /* Use Tarjan's algorithm for computing the strongly connected components
1260 * in the dependence graph (only validity edges).
1261 * If weak is set, we consider the graph to be undirected and
1262 * we effectively compute the (weakly) connected components.
1263 * Additionally, we also consider other edges when weak is set.
1265 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
1268 struct isl_tarjan_graph
*g
= NULL
;
1270 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
1271 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
1280 while (g
->order
[i
] != -1) {
1281 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1289 isl_tarjan_graph_free(g
);
1294 /* Apply Tarjan's algorithm to detect the strongly connected components
1295 * in the dependence graph.
1297 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1299 return detect_ccs(ctx
, graph
, 0);
1302 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1303 * in the dependence graph.
1305 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1307 return detect_ccs(ctx
, graph
, 1);
1310 static int cmp_scc(const void *a
, const void *b
, void *data
)
1312 struct isl_sched_graph
*graph
= data
;
1316 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1319 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1321 static int sort_sccs(struct isl_sched_graph
*graph
)
1323 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1326 /* Given a dependence relation R from "node" to itself,
1327 * construct the set of coefficients of valid constraints for elements
1328 * in that dependence relation.
1329 * In particular, the result contains tuples of coefficients
1330 * c_0, c_n, c_x such that
1332 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1336 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1338 * We choose here to compute the dual of delta R.
1339 * Alternatively, we could have computed the dual of R, resulting
1340 * in a set of tuples c_0, c_n, c_x, c_y, and then
1341 * plugged in (c_0, c_n, c_x, -c_x).
1343 * If "node" has been compressed, then the dependence relation
1344 * is also compressed before the set of coefficients is computed.
1346 static __isl_give isl_basic_set
*intra_coefficients(
1347 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1348 __isl_take isl_map
*map
)
1352 isl_basic_set
*coef
;
1354 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1355 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1357 key
= isl_map_copy(map
);
1358 if (node
->compressed
) {
1359 map
= isl_map_preimage_domain_multi_aff(map
,
1360 isl_multi_aff_copy(node
->decompress
));
1361 map
= isl_map_preimage_range_multi_aff(map
,
1362 isl_multi_aff_copy(node
->decompress
));
1364 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1365 coef
= isl_set_coefficients(delta
);
1366 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1367 isl_basic_set_copy(coef
));
1372 /* Given a dependence relation R, construct the set of coefficients
1373 * of valid constraints for elements in that dependence relation.
1374 * In particular, the result contains tuples of coefficients
1375 * c_0, c_n, c_x, c_y such that
1377 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1379 * If the source or destination nodes of "edge" have been compressed,
1380 * then the dependence relation is also compressed before
1381 * the set of coefficients is computed.
1383 static __isl_give isl_basic_set
*inter_coefficients(
1384 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1385 __isl_take isl_map
*map
)
1389 isl_basic_set
*coef
;
1391 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1392 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1394 key
= isl_map_copy(map
);
1395 if (edge
->src
->compressed
)
1396 map
= isl_map_preimage_domain_multi_aff(map
,
1397 isl_multi_aff_copy(edge
->src
->decompress
));
1398 if (edge
->dst
->compressed
)
1399 map
= isl_map_preimage_range_multi_aff(map
,
1400 isl_multi_aff_copy(edge
->dst
->decompress
));
1401 set
= isl_map_wrap(isl_map_remove_divs(map
));
1402 coef
= isl_set_coefficients(set
);
1403 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1404 isl_basic_set_copy(coef
));
1409 /* Add constraints to graph->lp that force validity for the given
1410 * dependence from a node i to itself.
1411 * That is, add constraints that enforce
1413 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1414 * = c_i_x (y - x) >= 0
1416 * for each (x,y) in R.
1417 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1418 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1419 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1420 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1422 * Actually, we do not construct constraints for the c_i_x themselves,
1423 * but for the coefficients of c_i_x written as a linear combination
1424 * of the columns in node->cmap.
1426 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1427 struct isl_sched_edge
*edge
)
1430 isl_map
*map
= isl_map_copy(edge
->map
);
1431 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1433 isl_dim_map
*dim_map
;
1434 isl_basic_set
*coef
;
1435 struct isl_sched_node
*node
= edge
->src
;
1437 coef
= intra_coefficients(graph
, node
, map
);
1439 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1441 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1442 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1446 total
= isl_basic_set_total_dim(graph
->lp
);
1447 dim_map
= isl_dim_map_alloc(ctx
, total
);
1448 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1449 isl_space_dim(dim
, isl_dim_set
), 1,
1451 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1452 isl_space_dim(dim
, isl_dim_set
), 1,
1454 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1455 coef
->n_eq
, coef
->n_ineq
);
1456 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1458 isl_space_free(dim
);
1462 isl_space_free(dim
);
1466 /* Add constraints to graph->lp that force validity for the given
1467 * dependence from node i to node j.
1468 * That is, add constraints that enforce
1470 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1472 * for each (x,y) in R.
1473 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1474 * of valid constraints for R and then plug in
1475 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1476 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1477 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1478 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1480 * Actually, we do not construct constraints for the c_*_x themselves,
1481 * but for the coefficients of c_*_x written as a linear combination
1482 * of the columns in node->cmap.
1484 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1485 struct isl_sched_edge
*edge
)
1488 isl_map
*map
= isl_map_copy(edge
->map
);
1489 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1491 isl_dim_map
*dim_map
;
1492 isl_basic_set
*coef
;
1493 struct isl_sched_node
*src
= edge
->src
;
1494 struct isl_sched_node
*dst
= edge
->dst
;
1496 coef
= inter_coefficients(graph
, edge
, map
);
1498 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1500 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1501 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1502 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1503 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1504 isl_mat_copy(dst
->cmap
));
1508 total
= isl_basic_set_total_dim(graph
->lp
);
1509 dim_map
= isl_dim_map_alloc(ctx
, total
);
1511 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1512 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1513 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1514 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1515 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1517 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1518 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1521 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1522 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1523 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1524 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1525 isl_space_dim(dim
, isl_dim_set
), 1,
1527 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1528 isl_space_dim(dim
, isl_dim_set
), 1,
1531 edge
->start
= graph
->lp
->n_ineq
;
1532 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1533 coef
->n_eq
, coef
->n_ineq
);
1534 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1538 isl_space_free(dim
);
1539 edge
->end
= graph
->lp
->n_ineq
;
1543 isl_space_free(dim
);
1547 /* Add constraints to graph->lp that bound the dependence distance for the given
1548 * dependence from a node i to itself.
1549 * If s = 1, we add the constraint
1551 * c_i_x (y - x) <= m_0 + m_n n
1555 * -c_i_x (y - x) + m_0 + m_n n >= 0
1557 * for each (x,y) in R.
1558 * If s = -1, we add the constraint
1560 * -c_i_x (y - x) <= m_0 + m_n n
1564 * c_i_x (y - x) + m_0 + m_n n >= 0
1566 * for each (x,y) in R.
1567 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1568 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1569 * with each coefficient (except m_0) represented as a pair of non-negative
1572 * Actually, we do not construct constraints for the c_i_x themselves,
1573 * but for the coefficients of c_i_x written as a linear combination
1574 * of the columns in node->cmap.
1577 * If "local" is set, then we add constraints
1579 * c_i_x (y - x) <= 0
1583 * -c_i_x (y - x) <= 0
1585 * instead, forcing the dependence distance to be (less than or) equal to 0.
1586 * That is, we plug in (0, 0, -s * c_i_x),
1587 * Note that dependences marked local are treated as validity constraints
1588 * by add_all_validity_constraints and therefore also have
1589 * their distances bounded by 0 from below.
1591 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1592 struct isl_sched_edge
*edge
, int s
, int local
)
1596 isl_map
*map
= isl_map_copy(edge
->map
);
1597 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1599 isl_dim_map
*dim_map
;
1600 isl_basic_set
*coef
;
1601 struct isl_sched_node
*node
= edge
->src
;
1603 coef
= intra_coefficients(graph
, node
, map
);
1605 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1607 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1608 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1612 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1613 total
= isl_basic_set_total_dim(graph
->lp
);
1614 dim_map
= isl_dim_map_alloc(ctx
, total
);
1617 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1618 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1619 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1621 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1622 isl_space_dim(dim
, isl_dim_set
), 1,
1624 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1625 isl_space_dim(dim
, isl_dim_set
), 1,
1627 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1628 coef
->n_eq
, coef
->n_ineq
);
1629 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1631 isl_space_free(dim
);
1635 isl_space_free(dim
);
1639 /* Add constraints to graph->lp that bound the dependence distance for the given
1640 * dependence from node i to node j.
1641 * If s = 1, we add the constraint
1643 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1648 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1651 * for each (x,y) in R.
1652 * If s = -1, we add the constraint
1654 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1659 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1662 * for each (x,y) in R.
1663 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1664 * of valid constraints for R and then plug in
1665 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1667 * with each coefficient (except m_0, c_j_0 and c_i_0)
1668 * represented as a pair of non-negative coefficients.
1670 * Actually, we do not construct constraints for the c_*_x themselves,
1671 * but for the coefficients of c_*_x written as a linear combination
1672 * of the columns in node->cmap.
1675 * If "local" is set, then we add constraints
1677 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1681 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1683 * instead, forcing the dependence distance to be (less than or) equal to 0.
1684 * That is, we plug in
1685 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1686 * Note that dependences marked local are treated as validity constraints
1687 * by add_all_validity_constraints and therefore also have
1688 * their distances bounded by 0 from below.
1690 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1691 struct isl_sched_edge
*edge
, int s
, int local
)
1695 isl_map
*map
= isl_map_copy(edge
->map
);
1696 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1698 isl_dim_map
*dim_map
;
1699 isl_basic_set
*coef
;
1700 struct isl_sched_node
*src
= edge
->src
;
1701 struct isl_sched_node
*dst
= edge
->dst
;
1703 coef
= inter_coefficients(graph
, edge
, map
);
1705 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1707 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1708 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1709 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1710 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1711 isl_mat_copy(dst
->cmap
));
1715 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1716 total
= isl_basic_set_total_dim(graph
->lp
);
1717 dim_map
= isl_dim_map_alloc(ctx
, total
);
1720 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1721 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1722 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1725 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1726 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1727 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1728 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1729 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1731 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1732 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1735 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1736 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1737 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1738 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1739 isl_space_dim(dim
, isl_dim_set
), 1,
1741 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1742 isl_space_dim(dim
, isl_dim_set
), 1,
1745 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1746 coef
->n_eq
, coef
->n_ineq
);
1747 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1749 isl_space_free(dim
);
1753 isl_space_free(dim
);
1757 /* Add all validity constraints to graph->lp.
1759 * An edge that is forced to be local needs to have its dependence
1760 * distances equal to zero. We take care of bounding them by 0 from below
1761 * here. add_all_proximity_constraints takes care of bounding them by 0
1764 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1765 * Otherwise, we ignore them.
1767 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1768 int use_coincidence
)
1772 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1773 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1776 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1777 if (!edge
->validity
&& !local
)
1779 if (edge
->src
!= edge
->dst
)
1781 if (add_intra_validity_constraints(graph
, edge
) < 0)
1785 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1786 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1789 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1790 if (!edge
->validity
&& !local
)
1792 if (edge
->src
== edge
->dst
)
1794 if (add_inter_validity_constraints(graph
, edge
) < 0)
1801 /* Add constraints to graph->lp that bound the dependence distance
1802 * for all dependence relations.
1803 * If a given proximity dependence is identical to a validity
1804 * dependence, then the dependence distance is already bounded
1805 * from below (by zero), so we only need to bound the distance
1806 * from above. (This includes the case of "local" dependences
1807 * which are treated as validity dependence by add_all_validity_constraints.)
1808 * Otherwise, we need to bound the distance both from above and from below.
1810 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1811 * Otherwise, we ignore them.
1813 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
1814 int use_coincidence
)
1818 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1819 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1822 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1823 if (!edge
->proximity
&& !local
)
1825 if (edge
->src
== edge
->dst
&&
1826 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
1828 if (edge
->src
!= edge
->dst
&&
1829 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
1831 if (edge
->validity
|| local
)
1833 if (edge
->src
== edge
->dst
&&
1834 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
1836 if (edge
->src
!= edge
->dst
&&
1837 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
1844 /* Compute a basis for the rows in the linear part of the schedule
1845 * and extend this basis to a full basis. The remaining rows
1846 * can then be used to force linear independence from the rows
1849 * In particular, given the schedule rows S, we compute
1854 * with H the Hermite normal form of S. That is, all but the
1855 * first rank columns of H are zero and so each row in S is
1856 * a linear combination of the first rank rows of Q.
1857 * The matrix Q is then transposed because we will write the
1858 * coefficients of the next schedule row as a column vector s
1859 * and express this s as a linear combination s = Q c of the
1861 * Similarly, the matrix U is transposed such that we can
1862 * compute the coefficients c = U s from a schedule row s.
1864 static int node_update_cmap(struct isl_sched_node
*node
)
1867 int n_row
= isl_mat_rows(node
->sched
);
1869 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1870 1 + node
->nparam
, node
->nvar
);
1872 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1873 isl_mat_free(node
->cmap
);
1874 isl_mat_free(node
->cinv
);
1875 node
->cmap
= isl_mat_transpose(Q
);
1876 node
->cinv
= isl_mat_transpose(U
);
1877 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1880 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1885 /* How many times should we count the constraints in "edge"?
1887 * If carry is set, then we are counting the number of
1888 * (validity or conditional validity) constraints that will be added
1889 * in setup_carry_lp and we count each edge exactly once.
1891 * Otherwise, we count as follows
1892 * validity -> 1 (>= 0)
1893 * validity+proximity -> 2 (>= 0 and upper bound)
1894 * proximity -> 2 (lower and upper bound)
1895 * local(+any) -> 2 (>= 0 and <= 0)
1897 * If an edge is only marked conditional_validity then it counts
1898 * as zero since it is only checked afterwards.
1900 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1901 * Otherwise, we ignore them.
1903 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
1904 int use_coincidence
)
1906 if (carry
&& !edge
->validity
&& !edge
->conditional_validity
)
1910 if (edge
->proximity
|| edge
->local
)
1912 if (use_coincidence
&& edge
->coincidence
)
1919 /* Count the number of equality and inequality constraints
1920 * that will be added for the given map.
1922 * "use_coincidence" is set if we should take into account coincidence edges.
1924 static int count_map_constraints(struct isl_sched_graph
*graph
,
1925 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1926 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
1928 isl_basic_set
*coef
;
1929 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
1936 if (edge
->src
== edge
->dst
)
1937 coef
= intra_coefficients(graph
, edge
->src
, map
);
1939 coef
= inter_coefficients(graph
, edge
, map
);
1942 *n_eq
+= f
* coef
->n_eq
;
1943 *n_ineq
+= f
* coef
->n_ineq
;
1944 isl_basic_set_free(coef
);
1949 /* Count the number of equality and inequality constraints
1950 * that will be added to the main lp problem.
1951 * We count as follows
1952 * validity -> 1 (>= 0)
1953 * validity+proximity -> 2 (>= 0 and upper bound)
1954 * proximity -> 2 (lower and upper bound)
1955 * local(+any) -> 2 (>= 0 and <= 0)
1957 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1958 * Otherwise, we ignore them.
1960 static int count_constraints(struct isl_sched_graph
*graph
,
1961 int *n_eq
, int *n_ineq
, int use_coincidence
)
1965 *n_eq
= *n_ineq
= 0;
1966 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1967 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1968 isl_map
*map
= isl_map_copy(edge
->map
);
1970 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
1971 0, use_coincidence
) < 0)
1978 /* Count the number of constraints that will be added by
1979 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1982 * In practice, add_bound_coefficient_constraints only adds inequalities.
1984 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1985 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1989 if (ctx
->opt
->schedule_max_coefficient
== -1)
1992 for (i
= 0; i
< graph
->n
; ++i
)
1993 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1998 /* Add constraints that bound the values of the variable and parameter
1999 * coefficients of the schedule.
2001 * The maximal value of the coefficients is defined by the option
2002 * 'schedule_max_coefficient'.
2004 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
2005 struct isl_sched_graph
*graph
)
2008 int max_coefficient
;
2011 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
2013 if (max_coefficient
== -1)
2016 total
= isl_basic_set_total_dim(graph
->lp
);
2018 for (i
= 0; i
< graph
->n
; ++i
) {
2019 struct isl_sched_node
*node
= &graph
->node
[i
];
2020 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
2022 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2025 dim
= 1 + node
->start
+ 1 + j
;
2026 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2027 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2028 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
2035 /* Construct an ILP problem for finding schedule coefficients
2036 * that result in non-negative, but small dependence distances
2037 * over all dependences.
2038 * In particular, the dependence distances over proximity edges
2039 * are bounded by m_0 + m_n n and we compute schedule coefficients
2040 * with small values (preferably zero) of m_n and m_0.
2042 * All variables of the ILP are non-negative. The actual coefficients
2043 * may be negative, so each coefficient is represented as the difference
2044 * of two non-negative variables. The negative part always appears
2045 * immediately before the positive part.
2046 * Other than that, the variables have the following order
2048 * - sum of positive and negative parts of m_n coefficients
2050 * - sum of positive and negative parts of all c_n coefficients
2051 * (unconstrained when computing non-parametric schedules)
2052 * - sum of positive and negative parts of all c_x coefficients
2053 * - positive and negative parts of m_n coefficients
2056 * - positive and negative parts of c_i_n (if parametric)
2057 * - positive and negative parts of c_i_x
2059 * The c_i_x are not represented directly, but through the columns of
2060 * node->cmap. That is, the computed values are for variable t_i_x
2061 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2063 * The constraints are those from the edges plus two or three equalities
2064 * to express the sums.
2066 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2067 * Otherwise, we ignore them.
2069 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2070 int use_coincidence
)
2080 int max_constant_term
;
2082 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
2084 parametric
= ctx
->opt
->schedule_parametric
;
2085 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2087 total
= param_pos
+ 2 * nparam
;
2088 for (i
= 0; i
< graph
->n
; ++i
) {
2089 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2090 if (node_update_cmap(node
) < 0)
2092 node
->start
= total
;
2093 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2096 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2098 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2101 dim
= isl_space_set_alloc(ctx
, 0, total
);
2102 isl_basic_set_free(graph
->lp
);
2103 n_eq
+= 2 + parametric
;
2104 if (max_constant_term
!= -1)
2107 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2109 k
= isl_basic_set_alloc_equality(graph
->lp
);
2112 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2113 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
2114 for (i
= 0; i
< 2 * nparam
; ++i
)
2115 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
2118 k
= isl_basic_set_alloc_equality(graph
->lp
);
2121 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2122 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2123 for (i
= 0; i
< graph
->n
; ++i
) {
2124 int pos
= 1 + graph
->node
[i
].start
+ 1;
2126 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2127 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2131 k
= isl_basic_set_alloc_equality(graph
->lp
);
2134 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2135 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
2136 for (i
= 0; i
< graph
->n
; ++i
) {
2137 struct isl_sched_node
*node
= &graph
->node
[i
];
2138 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2140 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2141 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2144 if (max_constant_term
!= -1)
2145 for (i
= 0; i
< graph
->n
; ++i
) {
2146 struct isl_sched_node
*node
= &graph
->node
[i
];
2147 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2150 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2151 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2152 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
2155 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2157 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2159 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2165 /* Analyze the conflicting constraint found by
2166 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2167 * constraint of one of the edges between distinct nodes, living, moreover
2168 * in distinct SCCs, then record the source and sink SCC as this may
2169 * be a good place to cut between SCCs.
2171 static int check_conflict(int con
, void *user
)
2174 struct isl_sched_graph
*graph
= user
;
2176 if (graph
->src_scc
>= 0)
2179 con
-= graph
->lp
->n_eq
;
2181 if (con
>= graph
->lp
->n_ineq
)
2184 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2185 if (!graph
->edge
[i
].validity
)
2187 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2189 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2191 if (graph
->edge
[i
].start
> con
)
2193 if (graph
->edge
[i
].end
<= con
)
2195 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2196 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2202 /* Check whether the next schedule row of the given node needs to be
2203 * non-trivial. Lower-dimensional domains may have some trivial rows,
2204 * but as soon as the number of remaining required non-trivial rows
2205 * is as large as the number or remaining rows to be computed,
2206 * all remaining rows need to be non-trivial.
2208 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2210 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2213 /* Solve the ILP problem constructed in setup_lp.
2214 * For each node such that all the remaining rows of its schedule
2215 * need to be non-trivial, we construct a non-triviality region.
2216 * This region imposes that the next row is independent of previous rows.
2217 * In particular the coefficients c_i_x are represented by t_i_x
2218 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2219 * its first columns span the rows of the previously computed part
2220 * of the schedule. The non-triviality region enforces that at least
2221 * one of the remaining components of t_i_x is non-zero, i.e.,
2222 * that the new schedule row depends on at least one of the remaining
2225 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2231 for (i
= 0; i
< graph
->n
; ++i
) {
2232 struct isl_sched_node
*node
= &graph
->node
[i
];
2233 int skip
= node
->rank
;
2234 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
2235 if (needs_row(graph
, node
))
2236 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2238 graph
->region
[i
].len
= 0;
2240 lp
= isl_basic_set_copy(graph
->lp
);
2241 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2242 graph
->region
, &check_conflict
, graph
);
2246 /* Update the schedules of all nodes based on the given solution
2247 * of the LP problem.
2248 * The new row is added to the current band.
2249 * All possibly negative coefficients are encoded as a difference
2250 * of two non-negative variables, so we need to perform the subtraction
2251 * here. Moreover, if use_cmap is set, then the solution does
2252 * not refer to the actual coefficients c_i_x, but instead to variables
2253 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2254 * In this case, we then also need to perform this multiplication
2255 * to obtain the values of c_i_x.
2257 * If coincident is set, then the caller guarantees that the new
2258 * row satisfies the coincidence constraints.
2260 static int update_schedule(struct isl_sched_graph
*graph
,
2261 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2264 isl_vec
*csol
= NULL
;
2269 isl_die(sol
->ctx
, isl_error_internal
,
2270 "no solution found", goto error
);
2271 if (graph
->n_total_row
>= graph
->max_row
)
2272 isl_die(sol
->ctx
, isl_error_internal
,
2273 "too many schedule rows", goto error
);
2275 for (i
= 0; i
< graph
->n
; ++i
) {
2276 struct isl_sched_node
*node
= &graph
->node
[i
];
2277 int pos
= node
->start
;
2278 int row
= isl_mat_rows(node
->sched
);
2281 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2285 isl_map_free(node
->sched_map
);
2286 node
->sched_map
= NULL
;
2287 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2290 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2292 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2293 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2294 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2295 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2296 for (j
= 0; j
< node
->nparam
; ++j
)
2297 node
->sched
= isl_mat_set_element(node
->sched
,
2298 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2299 for (j
= 0; j
< node
->nvar
; ++j
)
2300 isl_int_set(csol
->el
[j
],
2301 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2303 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2307 for (j
= 0; j
< node
->nvar
; ++j
)
2308 node
->sched
= isl_mat_set_element(node
->sched
,
2309 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2310 node
->coincident
[graph
->n_total_row
] = coincident
;
2316 graph
->n_total_row
++;
2325 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2326 * and return this isl_aff.
2328 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2329 struct isl_sched_node
*node
, int row
)
2337 aff
= isl_aff_zero_on_domain(ls
);
2338 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2339 aff
= isl_aff_set_constant(aff
, v
);
2340 for (j
= 0; j
< node
->nparam
; ++j
) {
2341 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2342 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2344 for (j
= 0; j
< node
->nvar
; ++j
) {
2345 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2346 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2354 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2355 * and return this multi_aff.
2357 * The result is defined over the uncompressed node domain.
2359 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2360 struct isl_sched_node
*node
, int first
, int n
)
2364 isl_local_space
*ls
;
2369 nrow
= isl_mat_rows(node
->sched
);
2370 if (node
->compressed
)
2371 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2373 space
= isl_space_copy(node
->space
);
2374 ls
= isl_local_space_from_space(isl_space_copy(space
));
2375 space
= isl_space_from_domain(space
);
2376 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2377 ma
= isl_multi_aff_zero(space
);
2379 for (i
= first
; i
< first
+ n
; ++i
) {
2380 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2381 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2384 isl_local_space_free(ls
);
2386 if (node
->compressed
)
2387 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2388 isl_multi_aff_copy(node
->compress
));
2393 /* Convert node->sched into a multi_aff and return this multi_aff.
2395 * The result is defined over the uncompressed node domain.
2397 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2398 struct isl_sched_node
*node
)
2402 nrow
= isl_mat_rows(node
->sched
);
2403 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
2406 /* Convert node->sched into a map and return this map.
2408 * The result is cached in node->sched_map, which needs to be released
2409 * whenever node->sched is updated.
2410 * It is defined over the uncompressed node domain.
2412 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2414 if (!node
->sched_map
) {
2417 ma
= node_extract_schedule_multi_aff(node
);
2418 node
->sched_map
= isl_map_from_multi_aff(ma
);
2421 return isl_map_copy(node
->sched_map
);
2424 /* Construct a map that can be used to update a dependence relation
2425 * based on the current schedule.
2426 * That is, construct a map expressing that source and sink
2427 * are executed within the same iteration of the current schedule.
2428 * This map can then be intersected with the dependence relation.
2429 * This is not the most efficient way, but this shouldn't be a critical
2432 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2433 struct isl_sched_node
*dst
)
2435 isl_map
*src_sched
, *dst_sched
;
2437 src_sched
= node_extract_schedule(src
);
2438 dst_sched
= node_extract_schedule(dst
);
2439 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2442 /* Intersect the domains of the nested relations in domain and range
2443 * of "umap" with "map".
2445 static __isl_give isl_union_map
*intersect_domains(
2446 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2448 isl_union_set
*uset
;
2450 umap
= isl_union_map_zip(umap
);
2451 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2452 umap
= isl_union_map_intersect_domain(umap
, uset
);
2453 umap
= isl_union_map_zip(umap
);
2457 /* Update the dependence relation of the given edge based
2458 * on the current schedule.
2459 * If the dependence is carried completely by the current schedule, then
2460 * it is removed from the edge_tables. It is kept in the list of edges
2461 * as otherwise all edge_tables would have to be recomputed.
2463 static int update_edge(struct isl_sched_graph
*graph
,
2464 struct isl_sched_edge
*edge
)
2469 id
= specializer(edge
->src
, edge
->dst
);
2470 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2474 if (edge
->tagged_condition
) {
2475 edge
->tagged_condition
=
2476 intersect_domains(edge
->tagged_condition
, id
);
2477 if (!edge
->tagged_condition
)
2480 if (edge
->tagged_validity
) {
2481 edge
->tagged_validity
=
2482 intersect_domains(edge
->tagged_validity
, id
);
2483 if (!edge
->tagged_validity
)
2487 empty
= isl_map_plain_is_empty(edge
->map
);
2491 graph_remove_edge(graph
, edge
);
2500 /* Does the domain of "umap" intersect "uset"?
2502 static int domain_intersects(__isl_keep isl_union_map
*umap
,
2503 __isl_keep isl_union_set
*uset
)
2507 umap
= isl_union_map_copy(umap
);
2508 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
2509 empty
= isl_union_map_is_empty(umap
);
2510 isl_union_map_free(umap
);
2512 return empty
< 0 ? -1 : !empty
;
2515 /* Does the range of "umap" intersect "uset"?
2517 static int range_intersects(__isl_keep isl_union_map
*umap
,
2518 __isl_keep isl_union_set
*uset
)
2522 umap
= isl_union_map_copy(umap
);
2523 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
2524 empty
= isl_union_map_is_empty(umap
);
2525 isl_union_map_free(umap
);
2527 return empty
< 0 ? -1 : !empty
;
2530 /* Are the condition dependences of "edge" local with respect to
2531 * the current schedule?
2533 * That is, are domain and range of the condition dependences mapped
2534 * to the same point?
2536 * In other words, is the condition false?
2538 static int is_condition_false(struct isl_sched_edge
*edge
)
2540 isl_union_map
*umap
;
2541 isl_map
*map
, *sched
, *test
;
2544 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
2545 if (empty
< 0 || empty
)
2548 umap
= isl_union_map_copy(edge
->tagged_condition
);
2549 umap
= isl_union_map_zip(umap
);
2550 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
2551 map
= isl_map_from_union_map(umap
);
2553 sched
= node_extract_schedule(edge
->src
);
2554 map
= isl_map_apply_domain(map
, sched
);
2555 sched
= node_extract_schedule(edge
->dst
);
2556 map
= isl_map_apply_range(map
, sched
);
2558 test
= isl_map_identity(isl_map_get_space(map
));
2559 local
= isl_map_is_subset(map
, test
);
2566 /* For each conditional validity constraint that is adjacent
2567 * to a condition with domain in condition_source or range in condition_sink,
2568 * turn it into an unconditional validity constraint.
2570 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
2571 __isl_take isl_union_set
*condition_source
,
2572 __isl_take isl_union_set
*condition_sink
)
2576 condition_source
= isl_union_set_coalesce(condition_source
);
2577 condition_sink
= isl_union_set_coalesce(condition_sink
);
2579 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2581 isl_union_map
*validity
;
2583 if (!graph
->edge
[i
].conditional_validity
)
2585 if (graph
->edge
[i
].validity
)
2588 validity
= graph
->edge
[i
].tagged_validity
;
2589 adjacent
= domain_intersects(validity
, condition_sink
);
2590 if (adjacent
>= 0 && !adjacent
)
2591 adjacent
= range_intersects(validity
, condition_source
);
2597 graph
->edge
[i
].validity
= 1;
2600 isl_union_set_free(condition_source
);
2601 isl_union_set_free(condition_sink
);
2604 isl_union_set_free(condition_source
);
2605 isl_union_set_free(condition_sink
);
2609 /* Update the dependence relations of all edges based on the current schedule
2610 * and enforce conditional validity constraints that are adjacent
2611 * to satisfied condition constraints.
2613 * First check if any of the condition constraints are satisfied
2614 * (i.e., not local to the outer schedule) and keep track of
2615 * their domain and range.
2616 * Then update all dependence relations (which removes the non-local
2618 * Finally, if any condition constraints turned out to be satisfied,
2619 * then turn all adjacent conditional validity constraints into
2620 * unconditional validity constraints.
2622 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2626 isl_union_set
*source
, *sink
;
2628 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
2629 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
2630 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2632 isl_union_set
*uset
;
2633 isl_union_map
*umap
;
2635 if (!graph
->edge
[i
].condition
)
2637 if (graph
->edge
[i
].local
)
2639 local
= is_condition_false(&graph
->edge
[i
]);
2647 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
2648 uset
= isl_union_map_domain(umap
);
2649 source
= isl_union_set_union(source
, uset
);
2651 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
2652 uset
= isl_union_map_range(umap
);
2653 sink
= isl_union_set_union(sink
, uset
);
2656 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2657 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2662 return unconditionalize_adjacent_validity(graph
, source
, sink
);
2664 isl_union_set_free(source
);
2665 isl_union_set_free(sink
);
2668 isl_union_set_free(source
);
2669 isl_union_set_free(sink
);
2673 static void next_band(struct isl_sched_graph
*graph
)
2675 graph
->band_start
= graph
->n_total_row
;
2678 /* Return the union of the universe domains of the nodes in "graph"
2679 * that satisfy "pred".
2681 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
2682 struct isl_sched_graph
*graph
,
2683 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
2689 for (i
= 0; i
< graph
->n
; ++i
)
2690 if (pred(&graph
->node
[i
], data
))
2694 isl_die(ctx
, isl_error_internal
,
2695 "empty component", return NULL
);
2697 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
2698 dom
= isl_union_set_from_set(set
);
2700 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
2701 if (!pred(&graph
->node
[i
], data
))
2703 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
2704 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
2710 /* Return a list of unions of universe domains, where each element
2711 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
2713 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
2714 struct isl_sched_graph
*graph
)
2717 isl_union_set_list
*filters
;
2719 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
2720 for (i
= 0; i
< graph
->scc
; ++i
) {
2723 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
2724 filters
= isl_union_set_list_add(filters
, dom
);
2730 /* Return a list of two unions of universe domains, one for the SCCs up
2731 * to and including graph->src_scc and another for the other SCCS.
2733 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
2734 struct isl_sched_graph
*graph
)
2737 isl_union_set_list
*filters
;
2739 filters
= isl_union_set_list_alloc(ctx
, 2);
2740 dom
= isl_sched_graph_domain(ctx
, graph
,
2741 &node_scc_at_most
, graph
->src_scc
);
2742 filters
= isl_union_set_list_add(filters
, dom
);
2743 dom
= isl_sched_graph_domain(ctx
, graph
,
2744 &node_scc_at_least
, graph
->src_scc
+ 1);
2745 filters
= isl_union_set_list_add(filters
, dom
);
2750 /* Topologically sort statements mapped to the same schedule iteration
2751 * and add insert a sequence node in front of "node"
2752 * corresponding to this order.
2754 static __isl_give isl_schedule_node
*sort_statements(
2755 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
2758 isl_union_set_list
*filters
;
2763 ctx
= isl_schedule_node_get_ctx(node
);
2765 isl_die(ctx
, isl_error_internal
,
2766 "graph should have at least one node",
2767 return isl_schedule_node_free(node
));
2772 if (update_edges(ctx
, graph
) < 0)
2773 return isl_schedule_node_free(node
);
2775 if (graph
->n_edge
== 0)
2778 if (detect_sccs(ctx
, graph
) < 0)
2779 return isl_schedule_node_free(node
);
2781 filters
= extract_sccs(ctx
, graph
);
2782 node
= isl_schedule_node_insert_sequence(node
, filters
);
2787 /* Copy nodes that satisfy node_pred from the src dependence graph
2788 * to the dst dependence graph.
2790 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2791 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2796 for (i
= 0; i
< src
->n
; ++i
) {
2799 if (!node_pred(&src
->node
[i
], data
))
2803 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
2804 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
2805 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
2806 dst
->node
[j
].compress
=
2807 isl_multi_aff_copy(src
->node
[i
].compress
);
2808 dst
->node
[j
].decompress
=
2809 isl_multi_aff_copy(src
->node
[i
].decompress
);
2810 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
2811 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
2812 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2813 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
2814 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
2817 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
2819 if (dst
->node
[j
].compressed
&&
2820 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
2821 !dst
->node
[j
].decompress
))
2828 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2829 * to the dst dependence graph.
2830 * If the source or destination node of the edge is not in the destination
2831 * graph, then it must be a backward proximity edge and it should simply
2834 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2835 struct isl_sched_graph
*src
,
2836 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2839 enum isl_edge_type t
;
2842 for (i
= 0; i
< src
->n_edge
; ++i
) {
2843 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2845 isl_union_map
*tagged_condition
;
2846 isl_union_map
*tagged_validity
;
2847 struct isl_sched_node
*dst_src
, *dst_dst
;
2849 if (!edge_pred(edge
, data
))
2852 if (isl_map_plain_is_empty(edge
->map
))
2855 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
2856 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
2857 if (!dst_src
|| !dst_dst
) {
2858 if (edge
->validity
|| edge
->conditional_validity
)
2859 isl_die(ctx
, isl_error_internal
,
2860 "backward (conditional) validity edge",
2865 map
= isl_map_copy(edge
->map
);
2866 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
2867 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
2869 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2870 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2871 dst
->edge
[dst
->n_edge
].map
= map
;
2872 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
2873 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
2874 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2875 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2876 dst
->edge
[dst
->n_edge
].coincidence
= edge
->coincidence
;
2877 dst
->edge
[dst
->n_edge
].condition
= edge
->condition
;
2878 dst
->edge
[dst
->n_edge
].conditional_validity
=
2879 edge
->conditional_validity
;
2882 if (edge
->tagged_condition
&& !tagged_condition
)
2884 if (edge
->tagged_validity
&& !tagged_validity
)
2887 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2889 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2891 if (graph_edge_table_add(ctx
, dst
, t
,
2892 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2900 /* Compute the maximal number of variables over all nodes.
2901 * This is the maximal number of linearly independent schedule
2902 * rows that we need to compute.
2903 * Just in case we end up in a part of the dependence graph
2904 * with only lower-dimensional domains, we make sure we will
2905 * compute the required amount of extra linearly independent rows.
2907 static int compute_maxvar(struct isl_sched_graph
*graph
)
2912 for (i
= 0; i
< graph
->n
; ++i
) {
2913 struct isl_sched_node
*node
= &graph
->node
[i
];
2916 if (node_update_cmap(node
) < 0)
2918 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2919 if (nvar
> graph
->maxvar
)
2920 graph
->maxvar
= nvar
;
2926 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
2927 struct isl_sched_graph
*graph
);
2928 static __isl_give isl_schedule_node
*compute_schedule_wcc(
2929 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
2931 /* Compute a schedule for a subgraph of "graph". In particular, for
2932 * the graph composed of nodes that satisfy node_pred and edges that
2933 * that satisfy edge_pred. The caller should precompute the number
2934 * of nodes and edges that satisfy these predicates and pass them along
2935 * as "n" and "n_edge".
2936 * If the subgraph is known to consist of a single component, then wcc should
2937 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2938 * Otherwise, we call compute_schedule, which will check whether the subgraph
2941 * The schedule is inserted at "node" and the updated schedule node
2944 static __isl_give isl_schedule_node
*compute_sub_schedule(
2945 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
2946 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2947 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2948 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2951 struct isl_sched_graph split
= { 0 };
2954 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2956 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2958 if (graph_init_table(ctx
, &split
) < 0)
2960 for (t
= 0; t
<= isl_edge_last
; ++t
)
2961 split
.max_edge
[t
] = graph
->max_edge
[t
];
2962 if (graph_init_edge_tables(ctx
, &split
) < 0)
2964 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2966 split
.n_row
= graph
->n_row
;
2967 split
.max_row
= graph
->max_row
;
2968 split
.n_total_row
= graph
->n_total_row
;
2969 split
.band_start
= graph
->band_start
;
2972 node
= compute_schedule_wcc(node
, &split
);
2974 node
= compute_schedule(node
, &split
);
2976 graph_free(ctx
, &split
);
2979 graph_free(ctx
, &split
);
2980 return isl_schedule_node_free(node
);
2983 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2985 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2988 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2990 return edge
->dst
->scc
<= scc
;
2993 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2995 return edge
->src
->scc
>= scc
;
2998 /* Reset the current band by dropping all its schedule rows.
3000 static int reset_band(struct isl_sched_graph
*graph
)
3005 drop
= graph
->n_total_row
- graph
->band_start
;
3006 graph
->n_total_row
-= drop
;
3007 graph
->n_row
-= drop
;
3009 for (i
= 0; i
< graph
->n
; ++i
) {
3010 struct isl_sched_node
*node
= &graph
->node
[i
];
3012 isl_map_free(node
->sched_map
);
3013 node
->sched_map
= NULL
;
3015 node
->sched
= isl_mat_drop_rows(node
->sched
,
3016 graph
->band_start
, drop
);
3025 /* Split the current graph into two parts and compute a schedule for each
3026 * part individually. In particular, one part consists of all SCCs up
3027 * to and including graph->src_scc, while the other part contains the other
3028 * SCCS. The split is enforced by a sequence node inserted at position "node"
3029 * in the schedule tree. Return the updated schedule node.
3031 * The current band is reset. It would be possible to reuse
3032 * the previously computed rows as the first rows in the next
3033 * band, but recomputing them may result in better rows as we are looking
3034 * at a smaller part of the dependence graph.
3036 static __isl_give isl_schedule_node
*compute_split_schedule(
3037 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3042 isl_union_set_list
*filters
;
3047 if (reset_band(graph
) < 0)
3048 return isl_schedule_node_free(node
);
3051 for (i
= 0; i
< graph
->n
; ++i
) {
3052 struct isl_sched_node
*node
= &graph
->node
[i
];
3053 int before
= node
->scc
<= graph
->src_scc
;
3060 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3061 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
3063 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
3069 ctx
= isl_schedule_node_get_ctx(node
);
3070 filters
= extract_split(ctx
, graph
);
3071 node
= isl_schedule_node_insert_sequence(node
, filters
);
3072 node
= isl_schedule_node_child(node
, 0);
3073 node
= isl_schedule_node_child(node
, 0);
3075 orig_total_row
= graph
->n_total_row
;
3076 node
= compute_sub_schedule(node
, ctx
, graph
, n
, e1
,
3077 &node_scc_at_most
, &edge_dst_scc_at_most
,
3079 node
= isl_schedule_node_parent(node
);
3080 node
= isl_schedule_node_next_sibling(node
);
3081 node
= isl_schedule_node_child(node
, 0);
3082 graph
->n_total_row
= orig_total_row
;
3083 node
= compute_sub_schedule(node
, ctx
, graph
, graph
->n
- n
, e2
,
3084 &node_scc_at_least
, &edge_src_scc_at_least
,
3085 graph
->src_scc
+ 1, 0);
3086 node
= isl_schedule_node_parent(node
);
3087 node
= isl_schedule_node_parent(node
);
3092 /* Insert a band node at position "node" in the schedule tree corresponding
3093 * to the current band in "graph". Mark the band node permutable
3094 * if "permutable" is set.
3095 * The partial schedules and the coincidence property are extracted
3096 * from the graph nodes.
3097 * Return the updated schedule node.
3099 static __isl_give isl_schedule_node
*insert_current_band(
3100 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3106 isl_multi_pw_aff
*mpa
;
3107 isl_multi_union_pw_aff
*mupa
;
3113 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3114 "graph should have at least one node",
3115 return isl_schedule_node_free(node
));
3117 start
= graph
->band_start
;
3118 end
= graph
->n_total_row
;
3121 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
3122 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3123 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3125 for (i
= 1; i
< graph
->n
; ++i
) {
3126 isl_multi_union_pw_aff
*mupa_i
;
3128 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
3130 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3131 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3132 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3134 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3136 for (i
= 0; i
< n
; ++i
)
3137 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3138 graph
->node
[0].coincident
[start
+ i
]);
3139 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3144 /* Update the dependence relations based on the current schedule,
3145 * add the current band to "node" and the continue with the computation
3147 * Return the updated schedule node.
3149 static __isl_give isl_schedule_node
*compute_next_band(
3150 __isl_take isl_schedule_node
*node
,
3151 struct isl_sched_graph
*graph
, int permutable
)
3158 ctx
= isl_schedule_node_get_ctx(node
);
3159 if (update_edges(ctx
, graph
) < 0)
3160 return isl_schedule_node_free(node
);
3161 node
= insert_current_band(node
, graph
, permutable
);
3164 node
= isl_schedule_node_child(node
, 0);
3165 node
= compute_schedule(node
, graph
);
3166 node
= isl_schedule_node_parent(node
);
3171 /* Add constraints to graph->lp that force the dependence "map" (which
3172 * is part of the dependence relation of "edge")
3173 * to be respected and attempt to carry it, where the edge is one from
3174 * a node j to itself. "pos" is the sequence number of the given map.
3175 * That is, add constraints that enforce
3177 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3178 * = c_j_x (y - x) >= e_i
3180 * for each (x,y) in R.
3181 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3182 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3183 * with each coefficient in c_j_x represented as a pair of non-negative
3186 static int add_intra_constraints(struct isl_sched_graph
*graph
,
3187 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3190 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3192 isl_dim_map
*dim_map
;
3193 isl_basic_set
*coef
;
3194 struct isl_sched_node
*node
= edge
->src
;
3196 coef
= intra_coefficients(graph
, node
, map
);
3200 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3202 total
= isl_basic_set_total_dim(graph
->lp
);
3203 dim_map
= isl_dim_map_alloc(ctx
, total
);
3204 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3205 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
3206 isl_space_dim(dim
, isl_dim_set
), 1,
3208 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
3209 isl_space_dim(dim
, isl_dim_set
), 1,
3211 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3212 coef
->n_eq
, coef
->n_ineq
);
3213 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3215 isl_space_free(dim
);
3220 /* Add constraints to graph->lp that force the dependence "map" (which
3221 * is part of the dependence relation of "edge")
3222 * to be respected and attempt to carry it, where the edge is one from
3223 * node j to node k. "pos" is the sequence number of the given map.
3224 * That is, add constraints that enforce
3226 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3228 * for each (x,y) in R.
3229 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3230 * of valid constraints for R and then plug in
3231 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3232 * with each coefficient (except e_i, c_k_0 and c_j_0)
3233 * represented as a pair of non-negative coefficients.
3235 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3236 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3239 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3241 isl_dim_map
*dim_map
;
3242 isl_basic_set
*coef
;
3243 struct isl_sched_node
*src
= edge
->src
;
3244 struct isl_sched_node
*dst
= edge
->dst
;
3246 coef
= inter_coefficients(graph
, edge
, map
);
3250 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3252 total
= isl_basic_set_total_dim(graph
->lp
);
3253 dim_map
= isl_dim_map_alloc(ctx
, total
);
3255 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3257 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
3258 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
3259 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
3260 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
3261 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3263 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
3264 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3267 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
3268 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
3269 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
3270 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
3271 isl_space_dim(dim
, isl_dim_set
), 1,
3273 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
3274 isl_space_dim(dim
, isl_dim_set
), 1,
3277 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3278 coef
->n_eq
, coef
->n_ineq
);
3279 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3281 isl_space_free(dim
);
3286 /* Add constraints to graph->lp that force all (conditional) validity
3287 * dependences to be respected and attempt to carry them.
3289 static int add_all_constraints(struct isl_sched_graph
*graph
)
3295 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3296 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3298 if (!edge
->validity
&& !edge
->conditional_validity
)
3301 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3302 isl_basic_map
*bmap
;
3305 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3306 map
= isl_map_from_basic_map(bmap
);
3308 if (edge
->src
== edge
->dst
&&
3309 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3311 if (edge
->src
!= edge
->dst
&&
3312 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3321 /* Count the number of equality and inequality constraints
3322 * that will be added to the carry_lp problem.
3323 * We count each edge exactly once.
3325 static int count_all_constraints(struct isl_sched_graph
*graph
,
3326 int *n_eq
, int *n_ineq
)
3330 *n_eq
= *n_ineq
= 0;
3331 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3332 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3333 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3334 isl_basic_map
*bmap
;
3337 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3338 map
= isl_map_from_basic_map(bmap
);
3340 if (count_map_constraints(graph
, edge
, map
,
3341 n_eq
, n_ineq
, 1, 0) < 0)
3349 /* Construct an LP problem for finding schedule coefficients
3350 * such that the schedule carries as many dependences as possible.
3351 * In particular, for each dependence i, we bound the dependence distance
3352 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3353 * of all e_i's. Dependence with e_i = 0 in the solution are simply
3354 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3355 * Note that if the dependence relation is a union of basic maps,
3356 * then we have to consider each basic map individually as it may only
3357 * be possible to carry the dependences expressed by some of those
3358 * basic maps and not all off them.
3359 * Below, we consider each of those basic maps as a separate "edge".
3361 * All variables of the LP are non-negative. The actual coefficients
3362 * may be negative, so each coefficient is represented as the difference
3363 * of two non-negative variables. The negative part always appears
3364 * immediately before the positive part.
3365 * Other than that, the variables have the following order
3367 * - sum of (1 - e_i) over all edges
3368 * - sum of positive and negative parts of all c_n coefficients
3369 * (unconstrained when computing non-parametric schedules)
3370 * - sum of positive and negative parts of all c_x coefficients
3375 * - positive and negative parts of c_i_n (if parametric)
3376 * - positive and negative parts of c_i_x
3378 * The constraints are those from the (validity) edges plus three equalities
3379 * to express the sums and n_edge inequalities to express e_i <= 1.
3381 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3391 for (i
= 0; i
< graph
->n_edge
; ++i
)
3392 n_edge
+= graph
->edge
[i
].map
->n
;
3395 for (i
= 0; i
< graph
->n
; ++i
) {
3396 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3397 node
->start
= total
;
3398 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
3401 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3403 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
3406 dim
= isl_space_set_alloc(ctx
, 0, total
);
3407 isl_basic_set_free(graph
->lp
);
3410 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3411 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3413 k
= isl_basic_set_alloc_equality(graph
->lp
);
3416 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3417 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3418 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3419 for (i
= 0; i
< n_edge
; ++i
)
3420 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3422 k
= isl_basic_set_alloc_equality(graph
->lp
);
3425 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3426 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
3427 for (i
= 0; i
< graph
->n
; ++i
) {
3428 int pos
= 1 + graph
->node
[i
].start
+ 1;
3430 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
3431 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3434 k
= isl_basic_set_alloc_equality(graph
->lp
);
3437 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3438 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
3439 for (i
= 0; i
< graph
->n
; ++i
) {
3440 struct isl_sched_node
*node
= &graph
->node
[i
];
3441 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3443 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
3444 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3447 for (i
= 0; i
< n_edge
; ++i
) {
3448 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3451 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3452 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3453 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3456 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
3458 if (add_all_constraints(graph
) < 0)
3464 static __isl_give isl_schedule_node
*compute_component_schedule(
3465 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3468 /* Comparison function for sorting the statements based on
3469 * the corresponding value in "r".
3471 static int smaller_value(const void *a
, const void *b
, void *data
)
3477 return isl_int_cmp(r
->el
[*i1
], r
->el
[*i2
]);
3480 /* If the schedule_split_scaled option is set and if the linear
3481 * parts of the scheduling rows for all nodes in the graphs have
3482 * a non-trivial common divisor, then split off the remainder of the
3483 * constant term modulo this common divisor from the linear part.
3484 * Otherwise, insert a band node directly and continue with
3485 * the construction of the schedule.
3487 * If a non-trivial common divisor is found, then
3488 * the linear part is reduced and the remainder is enforced
3489 * by a sequence node with the children placed in the order
3490 * of this remainder.
3491 * In particular, we assign an scc index based on the remainder and
3492 * then rely on compute_component_schedule to insert the sequence and
3493 * to continue the schedule construction on each part.
3495 static __isl_give isl_schedule_node
*split_scaled(
3496 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3509 ctx
= isl_schedule_node_get_ctx(node
);
3510 if (!ctx
->opt
->schedule_split_scaled
)
3511 return compute_next_band(node
, graph
, 0);
3513 return compute_next_band(node
, graph
, 0);
3516 isl_int_init(gcd_i
);
3518 isl_int_set_si(gcd
, 0);
3520 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3522 for (i
= 0; i
< graph
->n
; ++i
) {
3523 struct isl_sched_node
*node
= &graph
->node
[i
];
3524 int cols
= isl_mat_cols(node
->sched
);
3526 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3527 isl_int_gcd(gcd
, gcd
, gcd_i
);
3530 isl_int_clear(gcd_i
);
3532 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3534 return compute_next_band(node
, graph
, 0);
3537 r
= isl_vec_alloc(ctx
, graph
->n
);
3538 order
= isl_calloc_array(ctx
, int, graph
->n
);
3542 for (i
= 0; i
< graph
->n
; ++i
) {
3543 struct isl_sched_node
*node
= &graph
->node
[i
];
3546 isl_int_fdiv_r(r
->el
[i
], node
->sched
->row
[row
][0], gcd
);
3547 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3548 node
->sched
->row
[row
][0], gcd
);
3549 isl_int_mul(node
->sched
->row
[row
][0],
3550 node
->sched
->row
[row
][0], gcd
);
3551 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3556 if (isl_sort(order
, graph
->n
, sizeof(order
[0]), &smaller_value
, r
) < 0)
3560 for (i
= 0; i
< graph
->n
; ++i
) {
3561 if (i
> 0 && isl_int_ne(r
->el
[order
[i
- 1]], r
->el
[order
[i
]]))
3563 graph
->node
[order
[i
]].scc
= scc
;
3572 if (update_edges(ctx
, graph
) < 0)
3573 return isl_schedule_node_free(node
);
3574 node
= insert_current_band(node
, graph
, 0);
3577 node
= isl_schedule_node_child(node
, 0);
3578 node
= compute_component_schedule(node
, graph
, 0);
3579 node
= isl_schedule_node_parent(node
);
3586 return isl_schedule_node_free(node
);
3589 /* Is the schedule row "sol" trivial on node "node"?
3590 * That is, is the solution zero on the dimensions orthogonal to
3591 * the previously found solutions?
3592 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3594 * Each coefficient is represented as the difference between
3595 * two non-negative values in "sol". "sol" has been computed
3596 * in terms of the original iterators (i.e., without use of cmap).
3597 * We construct the schedule row s and write it as a linear
3598 * combination of (linear combinations of) previously computed schedule rows.
3599 * s = Q c or c = U s.
3600 * If the final entries of c are all zero, then the solution is trivial.
3602 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3612 if (node
->nvar
== node
->rank
)
3615 ctx
= isl_vec_get_ctx(sol
);
3616 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3620 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3622 for (i
= 0; i
< node
->nvar
; ++i
)
3623 isl_int_sub(node_sol
->el
[i
],
3624 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3626 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3631 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3632 node
->nvar
- node
->rank
) == -1;
3634 isl_vec_free(node_sol
);
3639 /* Is the schedule row "sol" trivial on any node where it should
3641 * "sol" has been computed in terms of the original iterators
3642 * (i.e., without use of cmap).
3643 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3645 static int is_any_trivial(struct isl_sched_graph
*graph
,
3646 __isl_keep isl_vec
*sol
)
3650 for (i
= 0; i
< graph
->n
; ++i
) {
3651 struct isl_sched_node
*node
= &graph
->node
[i
];
3654 if (!needs_row(graph
, node
))
3656 trivial
= is_trivial(node
, sol
);
3657 if (trivial
< 0 || trivial
)
3664 /* Construct a schedule row for each node such that as many dependences
3665 * as possible are carried and then continue with the next band.
3667 * If the computed schedule row turns out to be trivial on one or
3668 * more nodes where it should not be trivial, then we throw it away
3669 * and try again on each component separately.
3671 * If there is only one component, then we accept the schedule row anyway,
3672 * but we do not consider it as a complete row and therefore do not
3673 * increment graph->n_row. Note that the ranks of the nodes that
3674 * do get a non-trivial schedule part will get updated regardless and
3675 * graph->maxvar is computed based on these ranks. The test for
3676 * whether more schedule rows are required in compute_schedule_wcc
3677 * is therefore not affected.
3679 * Insert a band corresponding to the schedule row at position "node"
3680 * of the schedule tree and continue with the construction of the schedule.
3681 * This insertion and the continued construction is performed by split_scaled
3682 * after optionally checking for non-trivial common divisors.
3684 static __isl_give isl_schedule_node
*carry_dependences(
3685 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3698 for (i
= 0; i
< graph
->n_edge
; ++i
)
3699 n_edge
+= graph
->edge
[i
].map
->n
;
3701 ctx
= isl_schedule_node_get_ctx(node
);
3702 if (setup_carry_lp(ctx
, graph
) < 0)
3703 return isl_schedule_node_free(node
);
3705 lp
= isl_basic_set_copy(graph
->lp
);
3706 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3708 return isl_schedule_node_free(node
);
3710 if (sol
->size
== 0) {
3712 isl_die(ctx
, isl_error_internal
,
3713 "error in schedule construction",
3714 return isl_schedule_node_free(node
));
3717 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3718 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3720 isl_die(ctx
, isl_error_unknown
,
3721 "unable to carry dependences",
3722 return isl_schedule_node_free(node
));
3725 trivial
= is_any_trivial(graph
, sol
);
3727 sol
= isl_vec_free(sol
);
3728 } else if (trivial
&& graph
->scc
> 1) {
3730 return compute_component_schedule(node
, graph
, 1);
3733 if (update_schedule(graph
, sol
, 0, 0) < 0)
3734 return isl_schedule_node_free(node
);
3738 return split_scaled(node
, graph
);
3741 /* Are there any (non-empty) (conditional) validity edges in the graph?
3743 static int has_validity_edges(struct isl_sched_graph
*graph
)
3747 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3750 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3755 if (graph
->edge
[i
].validity
||
3756 graph
->edge
[i
].conditional_validity
)
3763 /* Should we apply a Feautrier step?
3764 * That is, did the user request the Feautrier algorithm and are
3765 * there any validity dependences (left)?
3767 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3769 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3772 return has_validity_edges(graph
);
3775 /* Compute a schedule for a connected dependence graph using Feautrier's
3776 * multi-dimensional scheduling algorithm and return the updated schedule node.
3778 * The original algorithm is described in [1].
3779 * The main idea is to minimize the number of scheduling dimensions, by
3780 * trying to satisfy as many dependences as possible per scheduling dimension.
3782 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3783 * Problem, Part II: Multi-Dimensional Time.
3784 * In Intl. Journal of Parallel Programming, 1992.
3786 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
3787 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3789 return carry_dependences(node
, graph
);
3792 /* Turn off the "local" bit on all (condition) edges.
3794 static void clear_local_edges(struct isl_sched_graph
*graph
)
3798 for (i
= 0; i
< graph
->n_edge
; ++i
)
3799 if (graph
->edge
[i
].condition
)
3800 graph
->edge
[i
].local
= 0;
3803 /* Does "graph" have both condition and conditional validity edges?
3805 static int need_condition_check(struct isl_sched_graph
*graph
)
3808 int any_condition
= 0;
3809 int any_conditional_validity
= 0;
3811 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3812 if (graph
->edge
[i
].condition
)
3814 if (graph
->edge
[i
].conditional_validity
)
3815 any_conditional_validity
= 1;
3818 return any_condition
&& any_conditional_validity
;
3821 /* Does "graph" contain any coincidence edge?
3823 static int has_any_coincidence(struct isl_sched_graph
*graph
)
3827 for (i
= 0; i
< graph
->n_edge
; ++i
)
3828 if (graph
->edge
[i
].coincidence
)
3834 /* Extract the final schedule row as a map with the iteration domain
3835 * of "node" as domain.
3837 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
3839 isl_local_space
*ls
;
3843 row
= isl_mat_rows(node
->sched
) - 1;
3844 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
3845 aff
= extract_schedule_row(ls
, node
, row
);
3846 return isl_map_from_aff(aff
);
3849 /* Is the conditional validity dependence in the edge with index "edge_index"
3850 * violated by the latest (i.e., final) row of the schedule?
3851 * That is, is i scheduled after j
3852 * for any conditional validity dependence i -> j?
3854 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
3856 isl_map
*src_sched
, *dst_sched
, *map
;
3857 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
3860 src_sched
= final_row(edge
->src
);
3861 dst_sched
= final_row(edge
->dst
);
3862 map
= isl_map_copy(edge
->map
);
3863 map
= isl_map_apply_domain(map
, src_sched
);
3864 map
= isl_map_apply_range(map
, dst_sched
);
3865 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
3866 empty
= isl_map_is_empty(map
);
3875 /* Does "graph" have any satisfied condition edges that
3876 * are adjacent to the conditional validity constraint with
3877 * domain "conditional_source" and range "conditional_sink"?
3879 * A satisfied condition is one that is not local.
3880 * If a condition was forced to be local already (i.e., marked as local)
3881 * then there is no need to check if it is in fact local.
3883 * Additionally, mark all adjacent condition edges found as local.
3885 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
3886 __isl_keep isl_union_set
*conditional_source
,
3887 __isl_keep isl_union_set
*conditional_sink
)
3892 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3893 int adjacent
, local
;
3894 isl_union_map
*condition
;
3896 if (!graph
->edge
[i
].condition
)
3898 if (graph
->edge
[i
].local
)
3901 condition
= graph
->edge
[i
].tagged_condition
;
3902 adjacent
= domain_intersects(condition
, conditional_sink
);
3903 if (adjacent
>= 0 && !adjacent
)
3904 adjacent
= range_intersects(condition
,
3905 conditional_source
);
3911 graph
->edge
[i
].local
= 1;
3913 local
= is_condition_false(&graph
->edge
[i
]);
3923 /* Are there any violated conditional validity dependences with
3924 * adjacent condition dependences that are not local with respect
3925 * to the current schedule?
3926 * That is, is the conditional validity constraint violated?
3928 * Additionally, mark all those adjacent condition dependences as local.
3929 * We also mark those adjacent condition dependences that were not marked
3930 * as local before, but just happened to be local already. This ensures
3931 * that they remain local if the schedule is recomputed.
3933 * We first collect domain and range of all violated conditional validity
3934 * dependences and then check if there are any adjacent non-local
3935 * condition dependences.
3937 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
3938 struct isl_sched_graph
*graph
)
3942 isl_union_set
*source
, *sink
;
3944 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3945 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3946 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3947 isl_union_set
*uset
;
3948 isl_union_map
*umap
;
3951 if (!graph
->edge
[i
].conditional_validity
)
3954 violated
= is_violated(graph
, i
);
3962 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3963 uset
= isl_union_map_domain(umap
);
3964 source
= isl_union_set_union(source
, uset
);
3965 source
= isl_union_set_coalesce(source
);
3967 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3968 uset
= isl_union_map_range(umap
);
3969 sink
= isl_union_set_union(sink
, uset
);
3970 sink
= isl_union_set_coalesce(sink
);
3974 any
= has_adjacent_true_conditions(graph
, source
, sink
);
3976 isl_union_set_free(source
);
3977 isl_union_set_free(sink
);
3980 isl_union_set_free(source
);
3981 isl_union_set_free(sink
);
3985 /* Compute a schedule for a connected dependence graph and return
3986 * the updated schedule node.
3988 * We try to find a sequence of as many schedule rows as possible that result
3989 * in non-negative dependence distances (independent of the previous rows
3990 * in the sequence, i.e., such that the sequence is tilable), with as
3991 * many of the initial rows as possible satisfying the coincidence constraints.
3992 * If we can't find any more rows we either
3993 * - split between SCCs and start over (assuming we found an interesting
3994 * pair of SCCs between which to split)
3995 * - continue with the next band (assuming the current band has at least
3997 * - try to carry as many dependences as possible and continue with the next
3999 * In each case, we first insert a band node in the schedule tree
4000 * if any rows have been computed.
4002 * If Feautrier's algorithm is selected, we first recursively try to satisfy
4003 * as many validity dependences as possible. When all validity dependences
4004 * are satisfied we extend the schedule to a full-dimensional schedule.
4006 * If we manage to complete the schedule, we insert a band node
4007 * (if any schedule rows were computed) and we finish off by topologically
4008 * sorting the statements based on the remaining dependences.
4010 * If ctx->opt->schedule_outer_coincidence is set, then we force the
4011 * outermost dimension to satisfy the coincidence constraints. If this
4012 * turns out to be impossible, we fall back on the general scheme above
4013 * and try to carry as many dependences as possible.
4015 * If "graph" contains both condition and conditional validity dependences,
4016 * then we need to check that that the conditional schedule constraint
4017 * is satisfied, i.e., there are no violated conditional validity dependences
4018 * that are adjacent to any non-local condition dependences.
4019 * If there are, then we mark all those adjacent condition dependences
4020 * as local and recompute the current band. Those dependences that
4021 * are marked local will then be forced to be local.
4022 * The initial computation is performed with no dependences marked as local.
4023 * If we are lucky, then there will be no violated conditional validity
4024 * dependences adjacent to any non-local condition dependences.
4025 * Otherwise, we mark some additional condition dependences as local and
4026 * recompute. We continue this process until there are no violations left or
4027 * until we are no longer able to compute a schedule.
4028 * Since there are only a finite number of dependences,
4029 * there will only be a finite number of iterations.
4031 static __isl_give isl_schedule_node
*compute_schedule_wcc(
4032 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4034 int has_coincidence
;
4035 int use_coincidence
;
4036 int force_coincidence
= 0;
4037 int check_conditional
;
4043 ctx
= isl_schedule_node_get_ctx(node
);
4044 if (detect_sccs(ctx
, graph
) < 0)
4045 return isl_schedule_node_free(node
);
4046 if (sort_sccs(graph
) < 0)
4047 return isl_schedule_node_free(node
);
4049 if (compute_maxvar(graph
) < 0)
4050 return isl_schedule_node_free(node
);
4052 if (need_feautrier_step(ctx
, graph
))
4053 return compute_schedule_wcc_feautrier(node
, graph
);
4055 clear_local_edges(graph
);
4056 check_conditional
= need_condition_check(graph
);
4057 has_coincidence
= has_any_coincidence(graph
);
4059 if (ctx
->opt
->schedule_outer_coincidence
)
4060 force_coincidence
= 1;
4062 use_coincidence
= has_coincidence
;
4063 while (graph
->n_row
< graph
->maxvar
) {
4068 graph
->src_scc
= -1;
4069 graph
->dst_scc
= -1;
4071 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
4072 return isl_schedule_node_free(node
);
4073 sol
= solve_lp(graph
);
4075 return isl_schedule_node_free(node
);
4076 if (sol
->size
== 0) {
4077 int empty
= graph
->n_total_row
== graph
->band_start
;
4080 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
4081 use_coincidence
= 0;
4084 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
4085 return compute_next_band(node
, graph
, 1);
4086 if (graph
->src_scc
>= 0)
4087 return compute_split_schedule(node
, graph
);
4089 return compute_next_band(node
, graph
, 1);
4090 return carry_dependences(node
, graph
);
4092 coincident
= !has_coincidence
|| use_coincidence
;
4093 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
4094 return isl_schedule_node_free(node
);
4096 if (!check_conditional
)
4098 violated
= has_violated_conditional_constraint(ctx
, graph
);
4100 return isl_schedule_node_free(node
);
4103 if (reset_band(graph
) < 0)
4104 return isl_schedule_node_free(node
);
4105 use_coincidence
= has_coincidence
;
4108 if (graph
->n_total_row
> graph
->band_start
) {
4109 node
= insert_current_band(node
, graph
, 1);
4110 node
= isl_schedule_node_child(node
, 0);
4112 node
= sort_statements(node
, graph
);
4113 if (graph
->n_total_row
> graph
->band_start
)
4114 node
= isl_schedule_node_parent(node
);
4119 /* Compute a schedule for each group of nodes identified by node->scc
4120 * separately and then combine them in a sequence node (or as set node
4121 * if graph->weak is set) inserted at position "node" of the schedule tree.
4122 * Return the updated schedule node.
4124 * If "wcc" is set then each of the groups belongs to a single
4125 * weakly connected component in the dependence graph so that
4126 * there is no need for compute_sub_schedule to look for weakly
4127 * connected components.
4129 static __isl_give isl_schedule_node
*compute_component_schedule(
4130 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4137 isl_union_set_list
*filters
;
4141 ctx
= isl_schedule_node_get_ctx(node
);
4143 filters
= extract_sccs(ctx
, graph
);
4145 node
= isl_schedule_node_insert_set(node
, filters
);
4147 node
= isl_schedule_node_insert_sequence(node
, filters
);
4149 orig_total_row
= graph
->n_total_row
;
4150 for (component
= 0; component
< graph
->scc
; ++component
) {
4152 for (i
= 0; i
< graph
->n
; ++i
)
4153 if (graph
->node
[i
].scc
== component
)
4156 for (i
= 0; i
< graph
->n_edge
; ++i
)
4157 if (graph
->edge
[i
].src
->scc
== component
&&
4158 graph
->edge
[i
].dst
->scc
== component
)
4161 node
= isl_schedule_node_child(node
, component
);
4162 node
= isl_schedule_node_child(node
, 0);
4163 node
= compute_sub_schedule(node
, ctx
, graph
, n
, n_edge
,
4165 &edge_scc_exactly
, component
, wcc
);
4166 node
= isl_schedule_node_parent(node
);
4167 node
= isl_schedule_node_parent(node
);
4168 graph
->n_total_row
= orig_total_row
;
4174 /* Compute a schedule for the given dependence graph and insert it at "node".
4175 * Return the updated schedule node.
4177 * We first check if the graph is connected (through validity and conditional
4178 * validity dependences) and, if not, compute a schedule
4179 * for each component separately.
4180 * If schedule_fuse is set to minimal fusion, then we check for strongly
4181 * connected components instead and compute a separate schedule for
4182 * each such strongly connected component.
4184 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
4185 struct isl_sched_graph
*graph
)
4192 ctx
= isl_schedule_node_get_ctx(node
);
4193 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
4194 if (detect_sccs(ctx
, graph
) < 0)
4195 return isl_schedule_node_free(node
);
4197 if (detect_wccs(ctx
, graph
) < 0)
4198 return isl_schedule_node_free(node
);
4202 return compute_component_schedule(node
, graph
, 1);
4204 return compute_schedule_wcc(node
, graph
);
4207 /* Compute a schedule on sc->domain that respects the given schedule
4210 * In particular, the schedule respects all the validity dependences.
4211 * If the default isl scheduling algorithm is used, it tries to minimize
4212 * the dependence distances over the proximity dependences.
4213 * If Feautrier's scheduling algorithm is used, the proximity dependence
4214 * distances are only minimized during the extension to a full-dimensional
4217 * If there are any condition and conditional validity dependences,
4218 * then the conditional validity dependences may be violated inside
4219 * a tilable band, provided they have no adjacent non-local
4220 * condition dependences.
4222 * The context is included in the domain before the nodes of
4223 * the graphs are extracted in order to be able to exploit
4224 * any possible additional equalities.
4225 * However, the returned schedule contains the original domain
4226 * (before this intersection).
4228 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
4229 __isl_take isl_schedule_constraints
*sc
)
4231 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
4232 struct isl_sched_graph graph
= { 0 };
4233 isl_schedule
*sched
;
4234 isl_schedule_node
*node
;
4235 isl_union_set
*domain
;
4236 struct isl_extract_edge_data data
;
4237 enum isl_edge_type i
;
4240 sc
= isl_schedule_constraints_align_params(sc
);
4244 graph
.n
= isl_union_set_n_set(sc
->domain
);
4246 isl_union_set
*domain
= isl_union_set_copy(sc
->domain
);
4247 sched
= isl_schedule_from_domain(domain
);
4250 if (graph_alloc(ctx
, &graph
, graph
.n
,
4251 isl_schedule_constraints_n_map(sc
)) < 0)
4253 if (compute_max_row(&graph
, sc
) < 0)
4257 domain
= isl_union_set_copy(sc
->domain
);
4258 domain
= isl_union_set_intersect_params(domain
,
4259 isl_set_copy(sc
->context
));
4260 r
= isl_union_set_foreach_set(domain
, &extract_node
, &graph
);
4261 isl_union_set_free(domain
);
4264 if (graph_init_table(ctx
, &graph
) < 0)
4266 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
4267 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
4268 if (graph_init_edge_tables(ctx
, &graph
) < 0)
4271 data
.graph
= &graph
;
4272 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
4274 if (isl_union_map_foreach_map(sc
->constraint
[i
],
4275 &extract_edge
, &data
) < 0)
4279 node
= isl_schedule_node_from_domain(isl_union_set_copy(sc
->domain
));
4280 node
= isl_schedule_node_child(node
, 0);
4281 node
= compute_schedule(node
, &graph
);
4282 sched
= isl_schedule_node_get_schedule(node
);
4283 isl_schedule_node_free(node
);
4286 graph_free(ctx
, &graph
);
4287 isl_schedule_constraints_free(sc
);
4291 graph_free(ctx
, &graph
);
4292 isl_schedule_constraints_free(sc
);
4296 /* Compute a schedule for the given union of domains that respects
4297 * all the validity dependences and minimizes
4298 * the dependence distances over the proximity dependences.
4300 * This function is kept for backward compatibility.
4302 __isl_give isl_schedule
*isl_union_set_compute_schedule(
4303 __isl_take isl_union_set
*domain
,
4304 __isl_take isl_union_map
*validity
,
4305 __isl_take isl_union_map
*proximity
)
4307 isl_schedule_constraints
*sc
;
4309 sc
= isl_schedule_constraints_on_domain(domain
);
4310 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
4311 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
4313 return isl_schedule_constraints_compute_schedule(sc
);