2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_space_private.h>
16 #include <isl_aff_private.h>
18 #include <isl/constraint.h>
19 #include <isl/schedule.h>
20 #include <isl/schedule_node.h>
21 #include <isl_mat_private.h>
22 #include <isl_vec_private.h>
26 #include <isl_dim_map.h>
27 #include <isl/map_to_basic_set.h>
29 #include <isl_options_private.h>
30 #include <isl_tarjan.h>
31 #include <isl_morph.h>
34 * The scheduling algorithm implemented in this file was inspired by
35 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
36 * Parallelization and Locality Optimization in the Polyhedral Model".
40 isl_edge_validity
= 0,
41 isl_edge_first
= isl_edge_validity
,
44 isl_edge_conditional_validity
,
46 isl_edge_last
= isl_edge_proximity
49 /* The constraints that need to be satisfied by a schedule on "domain".
51 * "validity" constraints map domain elements i to domain elements
52 * that should be scheduled after i. (Hard constraint)
53 * "proximity" constraints map domain elements i to domains elements
54 * that should be scheduled as early as possible after i (or before i).
57 * "condition" and "conditional_validity" constraints map possibly "tagged"
58 * domain elements i -> s to "tagged" domain elements j -> t.
59 * The elements of the "conditional_validity" constraints, but without the
60 * tags (i.e., the elements i -> j) are treated as validity constraints,
61 * except that during the construction of a tilable band,
62 * the elements of the "conditional_validity" constraints may be violated
63 * provided that all adjacent elements of the "condition" constraints
64 * are local within the band.
65 * A dependence is local within a band if domain and range are mapped
66 * to the same schedule point by the band.
68 struct isl_schedule_constraints
{
69 isl_union_set
*domain
;
71 isl_union_map
*constraint
[isl_edge_last
+ 1];
74 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
75 __isl_keep isl_schedule_constraints
*sc
)
78 isl_schedule_constraints
*sc_copy
;
81 ctx
= isl_union_set_get_ctx(sc
->domain
);
82 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
86 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
88 return isl_schedule_constraints_free(sc_copy
);
90 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
91 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
92 if (!sc_copy
->constraint
[i
])
93 return isl_schedule_constraints_free(sc_copy
);
100 /* Construct an isl_schedule_constraints object for computing a schedule
101 * on "domain". The initial object does not impose any constraints.
103 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
104 __isl_take isl_union_set
*domain
)
108 isl_schedule_constraints
*sc
;
109 isl_union_map
*empty
;
110 enum isl_edge_type i
;
115 ctx
= isl_union_set_get_ctx(domain
);
116 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
120 space
= isl_union_set_get_space(domain
);
122 empty
= isl_union_map_empty(space
);
123 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
124 sc
->constraint
[i
] = isl_union_map_copy(empty
);
125 if (!sc
->constraint
[i
])
126 sc
->domain
= isl_union_set_free(sc
->domain
);
128 isl_union_map_free(empty
);
131 return isl_schedule_constraints_free(sc
);
135 isl_union_set_free(domain
);
139 /* Replace the validity constraints of "sc" by "validity".
141 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
142 __isl_take isl_schedule_constraints
*sc
,
143 __isl_take isl_union_map
*validity
)
145 if (!sc
|| !validity
)
148 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
149 sc
->constraint
[isl_edge_validity
] = validity
;
153 isl_schedule_constraints_free(sc
);
154 isl_union_map_free(validity
);
158 /* Replace the coincidence constraints of "sc" by "coincidence".
160 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
161 __isl_take isl_schedule_constraints
*sc
,
162 __isl_take isl_union_map
*coincidence
)
164 if (!sc
|| !coincidence
)
167 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
168 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
172 isl_schedule_constraints_free(sc
);
173 isl_union_map_free(coincidence
);
177 /* Replace the proximity constraints of "sc" by "proximity".
179 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
180 __isl_take isl_schedule_constraints
*sc
,
181 __isl_take isl_union_map
*proximity
)
183 if (!sc
|| !proximity
)
186 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
187 sc
->constraint
[isl_edge_proximity
] = proximity
;
191 isl_schedule_constraints_free(sc
);
192 isl_union_map_free(proximity
);
196 /* Replace the conditional validity constraints of "sc" by "condition"
199 __isl_give isl_schedule_constraints
*
200 isl_schedule_constraints_set_conditional_validity(
201 __isl_take isl_schedule_constraints
*sc
,
202 __isl_take isl_union_map
*condition
,
203 __isl_take isl_union_map
*validity
)
205 if (!sc
|| !condition
|| !validity
)
208 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
209 sc
->constraint
[isl_edge_condition
] = condition
;
210 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
211 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
215 isl_schedule_constraints_free(sc
);
216 isl_union_map_free(condition
);
217 isl_union_map_free(validity
);
221 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
222 __isl_take isl_schedule_constraints
*sc
)
224 enum isl_edge_type i
;
229 isl_union_set_free(sc
->domain
);
230 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
231 isl_union_map_free(sc
->constraint
[i
]);
238 isl_ctx
*isl_schedule_constraints_get_ctx(
239 __isl_keep isl_schedule_constraints
*sc
)
241 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
244 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
249 fprintf(stderr
, "domain: ");
250 isl_union_set_dump(sc
->domain
);
251 fprintf(stderr
, "validity: ");
252 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
253 fprintf(stderr
, "proximity: ");
254 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
255 fprintf(stderr
, "coincidence: ");
256 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
257 fprintf(stderr
, "condition: ");
258 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
259 fprintf(stderr
, "conditional_validity: ");
260 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
263 /* Align the parameters of the fields of "sc".
265 static __isl_give isl_schedule_constraints
*
266 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
269 enum isl_edge_type i
;
274 space
= isl_union_set_get_space(sc
->domain
);
275 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
276 space
= isl_space_align_params(space
,
277 isl_union_map_get_space(sc
->constraint
[i
]));
279 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
280 sc
->constraint
[i
] = isl_union_map_align_params(
281 sc
->constraint
[i
], isl_space_copy(space
));
282 if (!sc
->constraint
[i
])
283 space
= isl_space_free(space
);
285 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
287 return isl_schedule_constraints_free(sc
);
292 /* Return the total number of isl_maps in the constraints of "sc".
294 static __isl_give
int isl_schedule_constraints_n_map(
295 __isl_keep isl_schedule_constraints
*sc
)
297 enum isl_edge_type i
;
300 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
301 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
306 /* Internal information about a node that is used during the construction
308 * space represents the space in which the domain lives
309 * sched is a matrix representation of the schedule being constructed
310 * for this node; if compressed is set, then this schedule is
311 * defined over the compressed domain space
312 * sched_map is an isl_map representation of the same (partial) schedule
313 * sched_map may be NULL; if compressed is set, then this map
314 * is defined over the uncompressed domain space
315 * rank is the number of linearly independent rows in the linear part
317 * the columns of cmap represent a change of basis for the schedule
318 * coefficients; the first rank columns span the linear part of
320 * cinv is the inverse of cmap.
321 * start is the first variable in the LP problem in the sequences that
322 * represents the schedule coefficients of this node
323 * nvar is the dimension of the domain
324 * nparam is the number of parameters or 0 if we are not constructing
325 * a parametric schedule
327 * If compressed is set, then hull represents the constraints
328 * that were used to derive the compression, while compress and
329 * decompress map the original space to the compressed space and
332 * scc is the index of SCC (or WCC) this node belongs to
334 * coincident contains a boolean for each of the rows of the schedule,
335 * indicating whether the corresponding scheduling dimension satisfies
336 * the coincidence constraints in the sense that the corresponding
337 * dependence distances are zero.
339 struct isl_sched_node
{
343 isl_multi_aff
*compress
;
344 isl_multi_aff
*decompress
;
359 static int node_has_space(const void *entry
, const void *val
)
361 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
362 isl_space
*dim
= (isl_space
*)val
;
364 return isl_space_is_equal(node
->space
, dim
);
367 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
369 return node
->scc
== scc
;
372 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
374 return node
->scc
<= scc
;
377 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
379 return node
->scc
>= scc
;
382 /* An edge in the dependence graph. An edge may be used to
383 * ensure validity of the generated schedule, to minimize the dependence
386 * map is the dependence relation, with i -> j in the map if j depends on i
387 * tagged_condition and tagged_validity contain the union of all tagged
388 * condition or conditional validity dependence relations that
389 * specialize the dependence relation "map"; that is,
390 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
391 * or "tagged_validity", then i -> j is an element of "map".
392 * If these fields are NULL, then they represent the empty relation.
393 * src is the source node
394 * dst is the sink node
395 * validity is set if the edge is used to ensure correctness
396 * coincidence is used to enforce zero dependence distances
397 * proximity is set if the edge is used to minimize dependence distances
398 * condition is set if the edge represents a condition
399 * for a conditional validity schedule constraint
400 * local can only be set for condition edges and indicates that
401 * the dependence distance over the edge should be zero
402 * conditional_validity is set if the edge is used to conditionally
405 * For validity edges, start and end mark the sequence of inequality
406 * constraints in the LP problem that encode the validity constraint
407 * corresponding to this edge.
409 struct isl_sched_edge
{
411 isl_union_map
*tagged_condition
;
412 isl_union_map
*tagged_validity
;
414 struct isl_sched_node
*src
;
415 struct isl_sched_node
*dst
;
417 unsigned validity
: 1;
418 unsigned coincidence
: 1;
419 unsigned proximity
: 1;
421 unsigned condition
: 1;
422 unsigned conditional_validity
: 1;
428 /* Internal information about the dependence graph used during
429 * the construction of the schedule.
431 * intra_hmap is a cache, mapping dependence relations to their dual,
432 * for dependences from a node to itself
433 * inter_hmap is a cache, mapping dependence relations to their dual,
434 * for dependences between distinct nodes
435 * if compression is involved then the key for these maps
436 * it the original, uncompressed dependence relation, while
437 * the value is the dual of the compressed dependence relation.
439 * n is the number of nodes
440 * node is the list of nodes
441 * maxvar is the maximal number of variables over all nodes
442 * max_row is the allocated number of rows in the schedule
443 * n_row is the current (maximal) number of linearly independent
444 * rows in the node schedules
445 * n_total_row is the current number of rows in the node schedules
446 * band_start is the starting row in the node schedules of the current band
447 * root is set if this graph is the original dependence graph,
448 * without any splitting
450 * sorted contains a list of node indices sorted according to the
451 * SCC to which a node belongs
453 * n_edge is the number of edges
454 * edge is the list of edges
455 * max_edge contains the maximal number of edges of each type;
456 * in particular, it contains the number of edges in the inital graph.
457 * edge_table contains pointers into the edge array, hashed on the source
458 * and sink spaces; there is one such table for each type;
459 * a given edge may be referenced from more than one table
460 * if the corresponding relation appears in more than of the
461 * sets of dependences
463 * node_table contains pointers into the node array, hashed on the space
465 * region contains a list of variable sequences that should be non-trivial
467 * lp contains the (I)LP problem used to obtain new schedule rows
469 * src_scc and dst_scc are the source and sink SCCs of an edge with
470 * conflicting constraints
472 * scc represents the number of components
473 * weak is set if the components are weakly connected
475 struct isl_sched_graph
{
476 isl_map_to_basic_set
*intra_hmap
;
477 isl_map_to_basic_set
*inter_hmap
;
479 struct isl_sched_node
*node
;
492 struct isl_sched_edge
*edge
;
494 int max_edge
[isl_edge_last
+ 1];
495 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
497 struct isl_hash_table
*node_table
;
498 struct isl_region
*region
;
509 /* Initialize node_table based on the list of nodes.
511 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
515 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
516 if (!graph
->node_table
)
519 for (i
= 0; i
< graph
->n
; ++i
) {
520 struct isl_hash_table_entry
*entry
;
523 hash
= isl_space_get_hash(graph
->node
[i
].space
);
524 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
526 graph
->node
[i
].space
, 1);
529 entry
->data
= &graph
->node
[i
];
535 /* Return a pointer to the node that lives within the given space,
536 * or NULL if there is no such node.
538 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
539 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
541 struct isl_hash_table_entry
*entry
;
544 hash
= isl_space_get_hash(dim
);
545 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
546 &node_has_space
, dim
, 0);
548 return entry
? entry
->data
: NULL
;
551 static int edge_has_src_and_dst(const void *entry
, const void *val
)
553 const struct isl_sched_edge
*edge
= entry
;
554 const struct isl_sched_edge
*temp
= val
;
556 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
559 /* Add the given edge to graph->edge_table[type].
561 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
562 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
564 struct isl_hash_table_entry
*entry
;
567 hash
= isl_hash_init();
568 hash
= isl_hash_builtin(hash
, edge
->src
);
569 hash
= isl_hash_builtin(hash
, edge
->dst
);
570 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
571 &edge_has_src_and_dst
, edge
, 1);
579 /* Allocate the edge_tables based on the maximal number of edges of
582 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
586 for (i
= 0; i
<= isl_edge_last
; ++i
) {
587 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
589 if (!graph
->edge_table
[i
])
596 /* If graph->edge_table[type] contains an edge from the given source
597 * to the given destination, then return the hash table entry of this edge.
598 * Otherwise, return NULL.
600 static struct isl_hash_table_entry
*graph_find_edge_entry(
601 struct isl_sched_graph
*graph
,
602 enum isl_edge_type type
,
603 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
605 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
607 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
609 hash
= isl_hash_init();
610 hash
= isl_hash_builtin(hash
, temp
.src
);
611 hash
= isl_hash_builtin(hash
, temp
.dst
);
612 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
613 &edge_has_src_and_dst
, &temp
, 0);
617 /* If graph->edge_table[type] contains an edge from the given source
618 * to the given destination, then return this edge.
619 * Otherwise, return NULL.
621 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
622 enum isl_edge_type type
,
623 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
625 struct isl_hash_table_entry
*entry
;
627 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
634 /* Check whether the dependence graph has an edge of the given type
635 * between the given two nodes.
637 static int graph_has_edge(struct isl_sched_graph
*graph
,
638 enum isl_edge_type type
,
639 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
641 struct isl_sched_edge
*edge
;
644 edge
= graph_find_edge(graph
, type
, src
, dst
);
648 empty
= isl_map_plain_is_empty(edge
->map
);
655 /* Look for any edge with the same src, dst and map fields as "model".
657 * Return the matching edge if one can be found.
658 * Return "model" if no matching edge is found.
659 * Return NULL on error.
661 static struct isl_sched_edge
*graph_find_matching_edge(
662 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
664 enum isl_edge_type i
;
665 struct isl_sched_edge
*edge
;
667 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
670 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
673 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
683 /* Remove the given edge from all the edge_tables that refer to it.
685 static void graph_remove_edge(struct isl_sched_graph
*graph
,
686 struct isl_sched_edge
*edge
)
688 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
689 enum isl_edge_type i
;
691 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
692 struct isl_hash_table_entry
*entry
;
694 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
697 if (entry
->data
!= edge
)
699 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
703 /* Check whether the dependence graph has any edge
704 * between the given two nodes.
706 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
707 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
709 enum isl_edge_type i
;
712 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
713 r
= graph_has_edge(graph
, i
, src
, dst
);
721 /* Check whether the dependence graph has a validity edge
722 * between the given two nodes.
724 * Conditional validity edges are essentially validity edges that
725 * can be ignored if the corresponding condition edges are iteration private.
726 * Here, we are only checking for the presence of validity
727 * edges, so we need to consider the conditional validity edges too.
728 * In particular, this function is used during the detection
729 * of strongly connected components and we cannot ignore
730 * conditional validity edges during this detection.
732 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
733 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
737 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
741 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
744 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
745 int n_node
, int n_edge
)
750 graph
->n_edge
= n_edge
;
751 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
752 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
753 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
754 graph
->edge
= isl_calloc_array(ctx
,
755 struct isl_sched_edge
, graph
->n_edge
);
757 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
758 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
760 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
764 for(i
= 0; i
< graph
->n
; ++i
)
765 graph
->sorted
[i
] = i
;
770 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
774 isl_map_to_basic_set_free(graph
->intra_hmap
);
775 isl_map_to_basic_set_free(graph
->inter_hmap
);
778 for (i
= 0; i
< graph
->n
; ++i
) {
779 isl_space_free(graph
->node
[i
].space
);
780 isl_set_free(graph
->node
[i
].hull
);
781 isl_multi_aff_free(graph
->node
[i
].compress
);
782 isl_multi_aff_free(graph
->node
[i
].decompress
);
783 isl_mat_free(graph
->node
[i
].sched
);
784 isl_map_free(graph
->node
[i
].sched_map
);
785 isl_mat_free(graph
->node
[i
].cmap
);
786 isl_mat_free(graph
->node
[i
].cinv
);
788 free(graph
->node
[i
].coincident
);
793 for (i
= 0; i
< graph
->n_edge
; ++i
) {
794 isl_map_free(graph
->edge
[i
].map
);
795 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
796 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
800 for (i
= 0; i
<= isl_edge_last
; ++i
)
801 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
802 isl_hash_table_free(ctx
, graph
->node_table
);
803 isl_basic_set_free(graph
->lp
);
806 /* For each "set" on which this function is called, increment
807 * graph->n by one and update graph->maxvar.
809 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
811 struct isl_sched_graph
*graph
= user
;
812 int nvar
= isl_set_dim(set
, isl_dim_set
);
815 if (nvar
> graph
->maxvar
)
816 graph
->maxvar
= nvar
;
823 /* Add the number of basic maps in "map" to *n.
825 static int add_n_basic_map(__isl_take isl_map
*map
, void *user
)
829 *n
+= isl_map_n_basic_map(map
);
835 /* Compute the number of rows that should be allocated for the schedule.
836 * In particular, we need one row for each variable or one row
837 * for each basic map in the dependences.
838 * Note that it is practically impossible to exhaust both
839 * the number of dependences and the number of variables.
841 static int compute_max_row(struct isl_sched_graph
*graph
,
842 __isl_keep isl_schedule_constraints
*sc
)
844 enum isl_edge_type i
;
849 if (isl_union_set_foreach_set(sc
->domain
, &init_n_maxvar
, graph
) < 0)
852 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
853 if (isl_union_map_foreach_map(sc
->constraint
[i
],
854 &add_n_basic_map
, &n_edge
) < 0)
856 graph
->max_row
= n_edge
+ graph
->maxvar
;
861 /* Does "bset" have any defining equalities for its set variables?
863 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
870 n
= isl_basic_set_dim(bset
, isl_dim_set
);
871 for (i
= 0; i
< n
; ++i
) {
874 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
883 /* Add a new node to the graph representing the given space.
884 * "nvar" is the (possibly compressed) number of variables and
885 * may be smaller than then number of set variables in "space"
886 * if "compressed" is set.
887 * If "compressed" is set, then "hull" represents the constraints
888 * that were used to derive the compression, while "compress" and
889 * "decompress" map the original space to the compressed space and
891 * If "compressed" is not set, then "hull", "compress" and "decompress"
894 static int add_node(struct isl_sched_graph
*graph
, __isl_take isl_space
*space
,
895 int nvar
, int compressed
, __isl_take isl_set
*hull
,
896 __isl_take isl_multi_aff
*compress
,
897 __isl_take isl_multi_aff
*decompress
)
907 ctx
= isl_space_get_ctx(space
);
908 nparam
= isl_space_dim(space
, isl_dim_param
);
909 if (!ctx
->opt
->schedule_parametric
)
911 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
912 graph
->node
[graph
->n
].space
= space
;
913 graph
->node
[graph
->n
].nvar
= nvar
;
914 graph
->node
[graph
->n
].nparam
= nparam
;
915 graph
->node
[graph
->n
].sched
= sched
;
916 graph
->node
[graph
->n
].sched_map
= NULL
;
917 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
918 graph
->node
[graph
->n
].coincident
= coincident
;
919 graph
->node
[graph
->n
].compressed
= compressed
;
920 graph
->node
[graph
->n
].hull
= hull
;
921 graph
->node
[graph
->n
].compress
= compress
;
922 graph
->node
[graph
->n
].decompress
= decompress
;
925 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
927 if (compressed
&& (!hull
|| !compress
|| !decompress
))
933 /* Add a new node to the graph representing the given set.
935 * If any of the set variables is defined by an equality, then
936 * we perform variable compression such that we can perform
937 * the scheduling on the compressed domain.
939 static int extract_node(__isl_take isl_set
*set
, void *user
)
947 isl_multi_aff
*compress
, *decompress
;
948 struct isl_sched_graph
*graph
= user
;
950 space
= isl_set_get_space(set
);
951 hull
= isl_set_affine_hull(set
);
952 hull
= isl_basic_set_remove_divs(hull
);
953 nvar
= isl_space_dim(space
, isl_dim_set
);
954 has_equality
= has_any_defining_equality(hull
);
956 if (has_equality
< 0)
959 isl_basic_set_free(hull
);
960 return add_node(graph
, space
, nvar
, 0, NULL
, NULL
, NULL
);
963 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
964 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
965 compress
= isl_morph_get_var_multi_aff(morph
);
966 morph
= isl_morph_inverse(morph
);
967 decompress
= isl_morph_get_var_multi_aff(morph
);
968 isl_morph_free(morph
);
970 hull_set
= isl_set_from_basic_set(hull
);
971 return add_node(graph
, space
, nvar
, 1, hull_set
, compress
, decompress
);
973 isl_basic_set_free(hull
);
974 isl_space_free(space
);
978 struct isl_extract_edge_data
{
979 enum isl_edge_type type
;
980 struct isl_sched_graph
*graph
;
983 /* Merge edge2 into edge1, freeing the contents of edge2.
984 * "type" is the type of the schedule constraint from which edge2 was
986 * Return 0 on success and -1 on failure.
988 * edge1 and edge2 are assumed to have the same value for the map field.
990 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
991 struct isl_sched_edge
*edge2
)
993 edge1
->validity
|= edge2
->validity
;
994 edge1
->coincidence
|= edge2
->coincidence
;
995 edge1
->proximity
|= edge2
->proximity
;
996 edge1
->condition
|= edge2
->condition
;
997 edge1
->conditional_validity
|= edge2
->conditional_validity
;
998 isl_map_free(edge2
->map
);
1000 if (type
== isl_edge_condition
) {
1001 if (!edge1
->tagged_condition
)
1002 edge1
->tagged_condition
= edge2
->tagged_condition
;
1004 edge1
->tagged_condition
=
1005 isl_union_map_union(edge1
->tagged_condition
,
1006 edge2
->tagged_condition
);
1009 if (type
== isl_edge_conditional_validity
) {
1010 if (!edge1
->tagged_validity
)
1011 edge1
->tagged_validity
= edge2
->tagged_validity
;
1013 edge1
->tagged_validity
=
1014 isl_union_map_union(edge1
->tagged_validity
,
1015 edge2
->tagged_validity
);
1018 if (type
== isl_edge_condition
&& !edge1
->tagged_condition
)
1020 if (type
== isl_edge_conditional_validity
&& !edge1
->tagged_validity
)
1026 /* Insert dummy tags in domain and range of "map".
1028 * In particular, if "map" is of the form
1034 * [A -> dummy_tag] -> [B -> dummy_tag]
1036 * where the dummy_tags are identical and equal to any dummy tags
1037 * introduced by any other call to this function.
1039 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1045 isl_set
*domain
, *range
;
1047 ctx
= isl_map_get_ctx(map
);
1049 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1050 space
= isl_space_params(isl_map_get_space(map
));
1051 space
= isl_space_set_from_params(space
);
1052 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1053 space
= isl_space_map_from_set(space
);
1055 domain
= isl_map_wrap(map
);
1056 range
= isl_map_wrap(isl_map_universe(space
));
1057 map
= isl_map_from_domain_and_range(domain
, range
);
1058 map
= isl_map_zip(map
);
1063 /* Given that at least one of "src" or "dst" is compressed, return
1064 * a map between the spaces of these nodes restricted to the affine
1065 * hull that was used in the compression.
1067 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1068 struct isl_sched_node
*dst
)
1072 if (src
->compressed
)
1073 dom
= isl_set_copy(src
->hull
);
1075 dom
= isl_set_universe(isl_space_copy(src
->space
));
1076 if (dst
->compressed
)
1077 ran
= isl_set_copy(dst
->hull
);
1079 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1081 return isl_map_from_domain_and_range(dom
, ran
);
1084 /* Intersect the domains of the nested relations in domain and range
1085 * of "tagged" with "map".
1087 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1088 __isl_keep isl_map
*map
)
1092 tagged
= isl_map_zip(tagged
);
1093 set
= isl_map_wrap(isl_map_copy(map
));
1094 tagged
= isl_map_intersect_domain(tagged
, set
);
1095 tagged
= isl_map_zip(tagged
);
1099 /* Add a new edge to the graph based on the given map
1100 * and add it to data->graph->edge_table[data->type].
1101 * If a dependence relation of a given type happens to be identical
1102 * to one of the dependence relations of a type that was added before,
1103 * then we don't create a new edge, but instead mark the original edge
1104 * as also representing a dependence of the current type.
1106 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1107 * may be specified as "tagged" dependence relations. That is, "map"
1108 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1109 * the dependence on iterations and a and b are tags.
1110 * edge->map is set to the relation containing the elements i -> j,
1111 * while edge->tagged_condition and edge->tagged_validity contain
1112 * the union of all the "map" relations
1113 * for which extract_edge is called that result in the same edge->map.
1115 * If the source or the destination node is compressed, then
1116 * intersect both "map" and "tagged" with the constraints that
1117 * were used to construct the compression.
1118 * This ensures that there are no schedule constraints defined
1119 * outside of these domains, while the scheduler no longer has
1120 * any control over those outside parts.
1122 static int extract_edge(__isl_take isl_map
*map
, void *user
)
1124 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1125 struct isl_extract_edge_data
*data
= user
;
1126 struct isl_sched_graph
*graph
= data
->graph
;
1127 struct isl_sched_node
*src
, *dst
;
1129 struct isl_sched_edge
*edge
;
1130 isl_map
*tagged
= NULL
;
1132 if (data
->type
== isl_edge_condition
||
1133 data
->type
== isl_edge_conditional_validity
) {
1134 if (isl_map_can_zip(map
)) {
1135 tagged
= isl_map_copy(map
);
1136 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1138 tagged
= insert_dummy_tags(isl_map_copy(map
));
1142 dim
= isl_space_domain(isl_map_get_space(map
));
1143 src
= graph_find_node(ctx
, graph
, dim
);
1144 isl_space_free(dim
);
1145 dim
= isl_space_range(isl_map_get_space(map
));
1146 dst
= graph_find_node(ctx
, graph
, dim
);
1147 isl_space_free(dim
);
1151 isl_map_free(tagged
);
1155 if (src
->compressed
|| dst
->compressed
) {
1157 hull
= extract_hull(src
, dst
);
1159 tagged
= map_intersect_domains(tagged
, hull
);
1160 map
= isl_map_intersect(map
, hull
);
1163 graph
->edge
[graph
->n_edge
].src
= src
;
1164 graph
->edge
[graph
->n_edge
].dst
= dst
;
1165 graph
->edge
[graph
->n_edge
].map
= map
;
1166 graph
->edge
[graph
->n_edge
].validity
= 0;
1167 graph
->edge
[graph
->n_edge
].coincidence
= 0;
1168 graph
->edge
[graph
->n_edge
].proximity
= 0;
1169 graph
->edge
[graph
->n_edge
].condition
= 0;
1170 graph
->edge
[graph
->n_edge
].local
= 0;
1171 graph
->edge
[graph
->n_edge
].conditional_validity
= 0;
1172 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1173 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1174 if (data
->type
== isl_edge_validity
)
1175 graph
->edge
[graph
->n_edge
].validity
= 1;
1176 if (data
->type
== isl_edge_coincidence
)
1177 graph
->edge
[graph
->n_edge
].coincidence
= 1;
1178 if (data
->type
== isl_edge_proximity
)
1179 graph
->edge
[graph
->n_edge
].proximity
= 1;
1180 if (data
->type
== isl_edge_condition
) {
1181 graph
->edge
[graph
->n_edge
].condition
= 1;
1182 graph
->edge
[graph
->n_edge
].tagged_condition
=
1183 isl_union_map_from_map(tagged
);
1185 if (data
->type
== isl_edge_conditional_validity
) {
1186 graph
->edge
[graph
->n_edge
].conditional_validity
= 1;
1187 graph
->edge
[graph
->n_edge
].tagged_validity
=
1188 isl_union_map_from_map(tagged
);
1191 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1196 if (edge
== &graph
->edge
[graph
->n_edge
])
1197 return graph_edge_table_add(ctx
, graph
, data
->type
,
1198 &graph
->edge
[graph
->n_edge
++]);
1200 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1203 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1206 /* Check whether there is any dependence from node[j] to node[i]
1207 * or from node[i] to node[j].
1209 static int node_follows_weak(int i
, int j
, void *user
)
1212 struct isl_sched_graph
*graph
= user
;
1214 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1217 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1220 /* Check whether there is a (conditional) validity dependence from node[j]
1221 * to node[i], forcing node[i] to follow node[j].
1223 static int node_follows_strong(int i
, int j
, void *user
)
1225 struct isl_sched_graph
*graph
= user
;
1227 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1230 /* Use Tarjan's algorithm for computing the strongly connected components
1231 * in the dependence graph (only validity edges).
1232 * If weak is set, we consider the graph to be undirected and
1233 * we effectively compute the (weakly) connected components.
1234 * Additionally, we also consider other edges when weak is set.
1236 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
1239 struct isl_tarjan_graph
*g
= NULL
;
1241 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
1242 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
1251 while (g
->order
[i
] != -1) {
1252 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1260 isl_tarjan_graph_free(g
);
1265 /* Apply Tarjan's algorithm to detect the strongly connected components
1266 * in the dependence graph.
1268 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1270 return detect_ccs(ctx
, graph
, 0);
1273 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1274 * in the dependence graph.
1276 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1278 return detect_ccs(ctx
, graph
, 1);
1281 static int cmp_scc(const void *a
, const void *b
, void *data
)
1283 struct isl_sched_graph
*graph
= data
;
1287 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1290 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1292 static int sort_sccs(struct isl_sched_graph
*graph
)
1294 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1297 /* Given a dependence relation R from "node" to itself,
1298 * construct the set of coefficients of valid constraints for elements
1299 * in that dependence relation.
1300 * In particular, the result contains tuples of coefficients
1301 * c_0, c_n, c_x such that
1303 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1307 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1309 * We choose here to compute the dual of delta R.
1310 * Alternatively, we could have computed the dual of R, resulting
1311 * in a set of tuples c_0, c_n, c_x, c_y, and then
1312 * plugged in (c_0, c_n, c_x, -c_x).
1314 * If "node" has been compressed, then the dependence relation
1315 * is also compressed before the set of coefficients is computed.
1317 static __isl_give isl_basic_set
*intra_coefficients(
1318 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1319 __isl_take isl_map
*map
)
1323 isl_basic_set
*coef
;
1325 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1326 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1328 key
= isl_map_copy(map
);
1329 if (node
->compressed
) {
1330 map
= isl_map_preimage_domain_multi_aff(map
,
1331 isl_multi_aff_copy(node
->decompress
));
1332 map
= isl_map_preimage_range_multi_aff(map
,
1333 isl_multi_aff_copy(node
->decompress
));
1335 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1336 coef
= isl_set_coefficients(delta
);
1337 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1338 isl_basic_set_copy(coef
));
1343 /* Given a dependence relation R, construct the set of coefficients
1344 * of valid constraints for elements in that dependence relation.
1345 * In particular, the result contains tuples of coefficients
1346 * c_0, c_n, c_x, c_y such that
1348 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1350 * If the source or destination nodes of "edge" have been compressed,
1351 * then the dependence relation is also compressed before
1352 * the set of coefficients is computed.
1354 static __isl_give isl_basic_set
*inter_coefficients(
1355 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1356 __isl_take isl_map
*map
)
1360 isl_basic_set
*coef
;
1362 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1363 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1365 key
= isl_map_copy(map
);
1366 if (edge
->src
->compressed
)
1367 map
= isl_map_preimage_domain_multi_aff(map
,
1368 isl_multi_aff_copy(edge
->src
->decompress
));
1369 if (edge
->dst
->compressed
)
1370 map
= isl_map_preimage_range_multi_aff(map
,
1371 isl_multi_aff_copy(edge
->dst
->decompress
));
1372 set
= isl_map_wrap(isl_map_remove_divs(map
));
1373 coef
= isl_set_coefficients(set
);
1374 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1375 isl_basic_set_copy(coef
));
1380 /* Add constraints to graph->lp that force validity for the given
1381 * dependence from a node i to itself.
1382 * That is, add constraints that enforce
1384 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1385 * = c_i_x (y - x) >= 0
1387 * for each (x,y) in R.
1388 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1389 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1390 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1391 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1393 * Actually, we do not construct constraints for the c_i_x themselves,
1394 * but for the coefficients of c_i_x written as a linear combination
1395 * of the columns in node->cmap.
1397 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1398 struct isl_sched_edge
*edge
)
1401 isl_map
*map
= isl_map_copy(edge
->map
);
1402 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1404 isl_dim_map
*dim_map
;
1405 isl_basic_set
*coef
;
1406 struct isl_sched_node
*node
= edge
->src
;
1408 coef
= intra_coefficients(graph
, node
, map
);
1410 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1412 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1413 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1417 total
= isl_basic_set_total_dim(graph
->lp
);
1418 dim_map
= isl_dim_map_alloc(ctx
, total
);
1419 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1420 isl_space_dim(dim
, isl_dim_set
), 1,
1422 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1423 isl_space_dim(dim
, isl_dim_set
), 1,
1425 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1426 coef
->n_eq
, coef
->n_ineq
);
1427 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1429 isl_space_free(dim
);
1433 isl_space_free(dim
);
1437 /* Add constraints to graph->lp that force validity for the given
1438 * dependence from node i to node j.
1439 * That is, add constraints that enforce
1441 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1443 * for each (x,y) in R.
1444 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1445 * of valid constraints for R and then plug in
1446 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1447 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1448 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1449 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1451 * Actually, we do not construct constraints for the c_*_x themselves,
1452 * but for the coefficients of c_*_x written as a linear combination
1453 * of the columns in node->cmap.
1455 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1456 struct isl_sched_edge
*edge
)
1459 isl_map
*map
= isl_map_copy(edge
->map
);
1460 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1462 isl_dim_map
*dim_map
;
1463 isl_basic_set
*coef
;
1464 struct isl_sched_node
*src
= edge
->src
;
1465 struct isl_sched_node
*dst
= edge
->dst
;
1467 coef
= inter_coefficients(graph
, edge
, map
);
1469 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1471 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1472 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1473 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1474 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1475 isl_mat_copy(dst
->cmap
));
1479 total
= isl_basic_set_total_dim(graph
->lp
);
1480 dim_map
= isl_dim_map_alloc(ctx
, total
);
1482 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1483 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1484 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1485 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1486 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1488 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1489 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1492 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1493 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1494 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1495 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1496 isl_space_dim(dim
, isl_dim_set
), 1,
1498 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1499 isl_space_dim(dim
, isl_dim_set
), 1,
1502 edge
->start
= graph
->lp
->n_ineq
;
1503 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1504 coef
->n_eq
, coef
->n_ineq
);
1505 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1509 isl_space_free(dim
);
1510 edge
->end
= graph
->lp
->n_ineq
;
1514 isl_space_free(dim
);
1518 /* Add constraints to graph->lp that bound the dependence distance for the given
1519 * dependence from a node i to itself.
1520 * If s = 1, we add the constraint
1522 * c_i_x (y - x) <= m_0 + m_n n
1526 * -c_i_x (y - x) + m_0 + m_n n >= 0
1528 * for each (x,y) in R.
1529 * If s = -1, we add the constraint
1531 * -c_i_x (y - x) <= m_0 + m_n n
1535 * c_i_x (y - x) + m_0 + m_n n >= 0
1537 * for each (x,y) in R.
1538 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1539 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1540 * with each coefficient (except m_0) represented as a pair of non-negative
1543 * Actually, we do not construct constraints for the c_i_x themselves,
1544 * but for the coefficients of c_i_x written as a linear combination
1545 * of the columns in node->cmap.
1548 * If "local" is set, then we add constraints
1550 * c_i_x (y - x) <= 0
1554 * -c_i_x (y - x) <= 0
1556 * instead, forcing the dependence distance to be (less than or) equal to 0.
1557 * That is, we plug in (0, 0, -s * c_i_x),
1558 * Note that dependences marked local are treated as validity constraints
1559 * by add_all_validity_constraints and therefore also have
1560 * their distances bounded by 0 from below.
1562 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1563 struct isl_sched_edge
*edge
, int s
, int local
)
1567 isl_map
*map
= isl_map_copy(edge
->map
);
1568 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1570 isl_dim_map
*dim_map
;
1571 isl_basic_set
*coef
;
1572 struct isl_sched_node
*node
= edge
->src
;
1574 coef
= intra_coefficients(graph
, node
, map
);
1576 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1578 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1579 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1583 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1584 total
= isl_basic_set_total_dim(graph
->lp
);
1585 dim_map
= isl_dim_map_alloc(ctx
, total
);
1588 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1589 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1590 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1592 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1593 isl_space_dim(dim
, isl_dim_set
), 1,
1595 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1596 isl_space_dim(dim
, isl_dim_set
), 1,
1598 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1599 coef
->n_eq
, coef
->n_ineq
);
1600 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1602 isl_space_free(dim
);
1606 isl_space_free(dim
);
1610 /* Add constraints to graph->lp that bound the dependence distance for the given
1611 * dependence from node i to node j.
1612 * If s = 1, we add the constraint
1614 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1619 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1622 * for each (x,y) in R.
1623 * If s = -1, we add the constraint
1625 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1630 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1633 * for each (x,y) in R.
1634 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1635 * of valid constraints for R and then plug in
1636 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1638 * with each coefficient (except m_0, c_j_0 and c_i_0)
1639 * represented as a pair of non-negative coefficients.
1641 * Actually, we do not construct constraints for the c_*_x themselves,
1642 * but for the coefficients of c_*_x written as a linear combination
1643 * of the columns in node->cmap.
1646 * If "local" is set, then we add constraints
1648 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1652 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1654 * instead, forcing the dependence distance to be (less than or) equal to 0.
1655 * That is, we plug in
1656 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1657 * Note that dependences marked local are treated as validity constraints
1658 * by add_all_validity_constraints and therefore also have
1659 * their distances bounded by 0 from below.
1661 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1662 struct isl_sched_edge
*edge
, int s
, int local
)
1666 isl_map
*map
= isl_map_copy(edge
->map
);
1667 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1669 isl_dim_map
*dim_map
;
1670 isl_basic_set
*coef
;
1671 struct isl_sched_node
*src
= edge
->src
;
1672 struct isl_sched_node
*dst
= edge
->dst
;
1674 coef
= inter_coefficients(graph
, edge
, map
);
1676 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1678 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1679 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1680 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1681 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1682 isl_mat_copy(dst
->cmap
));
1686 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1687 total
= isl_basic_set_total_dim(graph
->lp
);
1688 dim_map
= isl_dim_map_alloc(ctx
, total
);
1691 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1692 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1693 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1696 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1697 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1698 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1699 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1700 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1702 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1703 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1706 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1707 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1708 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1709 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1710 isl_space_dim(dim
, isl_dim_set
), 1,
1712 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1713 isl_space_dim(dim
, isl_dim_set
), 1,
1716 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1717 coef
->n_eq
, coef
->n_ineq
);
1718 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1720 isl_space_free(dim
);
1724 isl_space_free(dim
);
1728 /* Add all validity constraints to graph->lp.
1730 * An edge that is forced to be local needs to have its dependence
1731 * distances equal to zero. We take care of bounding them by 0 from below
1732 * here. add_all_proximity_constraints takes care of bounding them by 0
1735 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1736 * Otherwise, we ignore them.
1738 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1739 int use_coincidence
)
1743 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1744 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1747 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1748 if (!edge
->validity
&& !local
)
1750 if (edge
->src
!= edge
->dst
)
1752 if (add_intra_validity_constraints(graph
, edge
) < 0)
1756 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1757 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1760 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1761 if (!edge
->validity
&& !local
)
1763 if (edge
->src
== edge
->dst
)
1765 if (add_inter_validity_constraints(graph
, edge
) < 0)
1772 /* Add constraints to graph->lp that bound the dependence distance
1773 * for all dependence relations.
1774 * If a given proximity dependence is identical to a validity
1775 * dependence, then the dependence distance is already bounded
1776 * from below (by zero), so we only need to bound the distance
1777 * from above. (This includes the case of "local" dependences
1778 * which are treated as validity dependence by add_all_validity_constraints.)
1779 * Otherwise, we need to bound the distance both from above and from below.
1781 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1782 * Otherwise, we ignore them.
1784 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
1785 int use_coincidence
)
1789 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1790 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1793 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1794 if (!edge
->proximity
&& !local
)
1796 if (edge
->src
== edge
->dst
&&
1797 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
1799 if (edge
->src
!= edge
->dst
&&
1800 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
1802 if (edge
->validity
|| local
)
1804 if (edge
->src
== edge
->dst
&&
1805 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
1807 if (edge
->src
!= edge
->dst
&&
1808 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
1815 /* Compute a basis for the rows in the linear part of the schedule
1816 * and extend this basis to a full basis. The remaining rows
1817 * can then be used to force linear independence from the rows
1820 * In particular, given the schedule rows S, we compute
1825 * with H the Hermite normal form of S. That is, all but the
1826 * first rank columns of H are zero and so each row in S is
1827 * a linear combination of the first rank rows of Q.
1828 * The matrix Q is then transposed because we will write the
1829 * coefficients of the next schedule row as a column vector s
1830 * and express this s as a linear combination s = Q c of the
1832 * Similarly, the matrix U is transposed such that we can
1833 * compute the coefficients c = U s from a schedule row s.
1835 static int node_update_cmap(struct isl_sched_node
*node
)
1838 int n_row
= isl_mat_rows(node
->sched
);
1840 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1841 1 + node
->nparam
, node
->nvar
);
1843 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1844 isl_mat_free(node
->cmap
);
1845 isl_mat_free(node
->cinv
);
1846 node
->cmap
= isl_mat_transpose(Q
);
1847 node
->cinv
= isl_mat_transpose(U
);
1848 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1851 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1856 /* How many times should we count the constraints in "edge"?
1858 * If carry is set, then we are counting the number of
1859 * (validity or conditional validity) constraints that will be added
1860 * in setup_carry_lp and we count each edge exactly once.
1862 * Otherwise, we count as follows
1863 * validity -> 1 (>= 0)
1864 * validity+proximity -> 2 (>= 0 and upper bound)
1865 * proximity -> 2 (lower and upper bound)
1866 * local(+any) -> 2 (>= 0 and <= 0)
1868 * If an edge is only marked conditional_validity then it counts
1869 * as zero since it is only checked afterwards.
1871 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1872 * Otherwise, we ignore them.
1874 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
1875 int use_coincidence
)
1877 if (carry
&& !edge
->validity
&& !edge
->conditional_validity
)
1881 if (edge
->proximity
|| edge
->local
)
1883 if (use_coincidence
&& edge
->coincidence
)
1890 /* Count the number of equality and inequality constraints
1891 * that will be added for the given map.
1893 * "use_coincidence" is set if we should take into account coincidence edges.
1895 static int count_map_constraints(struct isl_sched_graph
*graph
,
1896 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1897 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
1899 isl_basic_set
*coef
;
1900 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
1907 if (edge
->src
== edge
->dst
)
1908 coef
= intra_coefficients(graph
, edge
->src
, map
);
1910 coef
= inter_coefficients(graph
, edge
, map
);
1913 *n_eq
+= f
* coef
->n_eq
;
1914 *n_ineq
+= f
* coef
->n_ineq
;
1915 isl_basic_set_free(coef
);
1920 /* Count the number of equality and inequality constraints
1921 * that will be added to the main lp problem.
1922 * We count as follows
1923 * validity -> 1 (>= 0)
1924 * validity+proximity -> 2 (>= 0 and upper bound)
1925 * proximity -> 2 (lower and upper bound)
1926 * local(+any) -> 2 (>= 0 and <= 0)
1928 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1929 * Otherwise, we ignore them.
1931 static int count_constraints(struct isl_sched_graph
*graph
,
1932 int *n_eq
, int *n_ineq
, int use_coincidence
)
1936 *n_eq
= *n_ineq
= 0;
1937 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1938 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1939 isl_map
*map
= isl_map_copy(edge
->map
);
1941 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
1942 0, use_coincidence
) < 0)
1949 /* Count the number of constraints that will be added by
1950 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1953 * In practice, add_bound_coefficient_constraints only adds inequalities.
1955 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1956 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1960 if (ctx
->opt
->schedule_max_coefficient
== -1)
1963 for (i
= 0; i
< graph
->n
; ++i
)
1964 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1969 /* Add constraints that bound the values of the variable and parameter
1970 * coefficients of the schedule.
1972 * The maximal value of the coefficients is defined by the option
1973 * 'schedule_max_coefficient'.
1975 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1976 struct isl_sched_graph
*graph
)
1979 int max_coefficient
;
1982 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1984 if (max_coefficient
== -1)
1987 total
= isl_basic_set_total_dim(graph
->lp
);
1989 for (i
= 0; i
< graph
->n
; ++i
) {
1990 struct isl_sched_node
*node
= &graph
->node
[i
];
1991 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1993 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1996 dim
= 1 + node
->start
+ 1 + j
;
1997 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1998 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1999 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
2006 /* Construct an ILP problem for finding schedule coefficients
2007 * that result in non-negative, but small dependence distances
2008 * over all dependences.
2009 * In particular, the dependence distances over proximity edges
2010 * are bounded by m_0 + m_n n and we compute schedule coefficients
2011 * with small values (preferably zero) of m_n and m_0.
2013 * All variables of the ILP are non-negative. The actual coefficients
2014 * may be negative, so each coefficient is represented as the difference
2015 * of two non-negative variables. The negative part always appears
2016 * immediately before the positive part.
2017 * Other than that, the variables have the following order
2019 * - sum of positive and negative parts of m_n coefficients
2021 * - sum of positive and negative parts of all c_n coefficients
2022 * (unconstrained when computing non-parametric schedules)
2023 * - sum of positive and negative parts of all c_x coefficients
2024 * - positive and negative parts of m_n coefficients
2027 * - positive and negative parts of c_i_n (if parametric)
2028 * - positive and negative parts of c_i_x
2030 * The c_i_x are not represented directly, but through the columns of
2031 * node->cmap. That is, the computed values are for variable t_i_x
2032 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2034 * The constraints are those from the edges plus two or three equalities
2035 * to express the sums.
2037 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2038 * Otherwise, we ignore them.
2040 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2041 int use_coincidence
)
2051 int max_constant_term
;
2053 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
2055 parametric
= ctx
->opt
->schedule_parametric
;
2056 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2058 total
= param_pos
+ 2 * nparam
;
2059 for (i
= 0; i
< graph
->n
; ++i
) {
2060 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2061 if (node_update_cmap(node
) < 0)
2063 node
->start
= total
;
2064 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2067 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2069 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2072 dim
= isl_space_set_alloc(ctx
, 0, total
);
2073 isl_basic_set_free(graph
->lp
);
2074 n_eq
+= 2 + parametric
;
2075 if (max_constant_term
!= -1)
2078 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2080 k
= isl_basic_set_alloc_equality(graph
->lp
);
2083 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2084 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
2085 for (i
= 0; i
< 2 * nparam
; ++i
)
2086 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
2089 k
= isl_basic_set_alloc_equality(graph
->lp
);
2092 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2093 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2094 for (i
= 0; i
< graph
->n
; ++i
) {
2095 int pos
= 1 + graph
->node
[i
].start
+ 1;
2097 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2098 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2102 k
= isl_basic_set_alloc_equality(graph
->lp
);
2105 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2106 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
2107 for (i
= 0; i
< graph
->n
; ++i
) {
2108 struct isl_sched_node
*node
= &graph
->node
[i
];
2109 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2111 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2112 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2115 if (max_constant_term
!= -1)
2116 for (i
= 0; i
< graph
->n
; ++i
) {
2117 struct isl_sched_node
*node
= &graph
->node
[i
];
2118 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2121 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2122 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2123 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
2126 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2128 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2130 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2136 /* Analyze the conflicting constraint found by
2137 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2138 * constraint of one of the edges between distinct nodes, living, moreover
2139 * in distinct SCCs, then record the source and sink SCC as this may
2140 * be a good place to cut between SCCs.
2142 static int check_conflict(int con
, void *user
)
2145 struct isl_sched_graph
*graph
= user
;
2147 if (graph
->src_scc
>= 0)
2150 con
-= graph
->lp
->n_eq
;
2152 if (con
>= graph
->lp
->n_ineq
)
2155 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2156 if (!graph
->edge
[i
].validity
)
2158 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2160 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2162 if (graph
->edge
[i
].start
> con
)
2164 if (graph
->edge
[i
].end
<= con
)
2166 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2167 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2173 /* Check whether the next schedule row of the given node needs to be
2174 * non-trivial. Lower-dimensional domains may have some trivial rows,
2175 * but as soon as the number of remaining required non-trivial rows
2176 * is as large as the number or remaining rows to be computed,
2177 * all remaining rows need to be non-trivial.
2179 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2181 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2184 /* Solve the ILP problem constructed in setup_lp.
2185 * For each node such that all the remaining rows of its schedule
2186 * need to be non-trivial, we construct a non-triviality region.
2187 * This region imposes that the next row is independent of previous rows.
2188 * In particular the coefficients c_i_x are represented by t_i_x
2189 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2190 * its first columns span the rows of the previously computed part
2191 * of the schedule. The non-triviality region enforces that at least
2192 * one of the remaining components of t_i_x is non-zero, i.e.,
2193 * that the new schedule row depends on at least one of the remaining
2196 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2202 for (i
= 0; i
< graph
->n
; ++i
) {
2203 struct isl_sched_node
*node
= &graph
->node
[i
];
2204 int skip
= node
->rank
;
2205 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
2206 if (needs_row(graph
, node
))
2207 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2209 graph
->region
[i
].len
= 0;
2211 lp
= isl_basic_set_copy(graph
->lp
);
2212 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2213 graph
->region
, &check_conflict
, graph
);
2217 /* Update the schedules of all nodes based on the given solution
2218 * of the LP problem.
2219 * The new row is added to the current band.
2220 * All possibly negative coefficients are encoded as a difference
2221 * of two non-negative variables, so we need to perform the subtraction
2222 * here. Moreover, if use_cmap is set, then the solution does
2223 * not refer to the actual coefficients c_i_x, but instead to variables
2224 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2225 * In this case, we then also need to perform this multiplication
2226 * to obtain the values of c_i_x.
2228 * If coincident is set, then the caller guarantees that the new
2229 * row satisfies the coincidence constraints.
2231 static int update_schedule(struct isl_sched_graph
*graph
,
2232 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2235 isl_vec
*csol
= NULL
;
2240 isl_die(sol
->ctx
, isl_error_internal
,
2241 "no solution found", goto error
);
2242 if (graph
->n_total_row
>= graph
->max_row
)
2243 isl_die(sol
->ctx
, isl_error_internal
,
2244 "too many schedule rows", goto error
);
2246 for (i
= 0; i
< graph
->n
; ++i
) {
2247 struct isl_sched_node
*node
= &graph
->node
[i
];
2248 int pos
= node
->start
;
2249 int row
= isl_mat_rows(node
->sched
);
2252 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2256 isl_map_free(node
->sched_map
);
2257 node
->sched_map
= NULL
;
2258 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2261 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2263 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2264 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2265 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2266 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2267 for (j
= 0; j
< node
->nparam
; ++j
)
2268 node
->sched
= isl_mat_set_element(node
->sched
,
2269 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2270 for (j
= 0; j
< node
->nvar
; ++j
)
2271 isl_int_set(csol
->el
[j
],
2272 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2274 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2278 for (j
= 0; j
< node
->nvar
; ++j
)
2279 node
->sched
= isl_mat_set_element(node
->sched
,
2280 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2281 node
->coincident
[graph
->n_total_row
] = coincident
;
2287 graph
->n_total_row
++;
2296 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2297 * and return this isl_aff.
2299 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2300 struct isl_sched_node
*node
, int row
)
2308 aff
= isl_aff_zero_on_domain(ls
);
2309 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2310 aff
= isl_aff_set_constant(aff
, v
);
2311 for (j
= 0; j
< node
->nparam
; ++j
) {
2312 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2313 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2315 for (j
= 0; j
< node
->nvar
; ++j
) {
2316 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2317 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2325 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2326 * and return this multi_aff.
2328 * The result is defined over the uncompressed node domain.
2330 static __isl_give isl_multi_aff
*node_extract_partial_schedule_multi_aff(
2331 struct isl_sched_node
*node
, int first
, int n
)
2335 isl_local_space
*ls
;
2340 nrow
= isl_mat_rows(node
->sched
);
2341 ncol
= isl_mat_cols(node
->sched
) - 1;
2342 if (node
->compressed
)
2343 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2345 space
= isl_space_copy(node
->space
);
2346 ls
= isl_local_space_from_space(isl_space_copy(space
));
2347 space
= isl_space_from_domain(space
);
2348 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
2349 ma
= isl_multi_aff_zero(space
);
2351 for (i
= first
; i
< first
+ n
; ++i
) {
2352 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2353 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
2356 isl_local_space_free(ls
);
2358 if (node
->compressed
)
2359 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2360 isl_multi_aff_copy(node
->compress
));
2365 /* Convert node->sched into a multi_aff and return this multi_aff.
2367 * The result is defined over the uncompressed node domain.
2369 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2370 struct isl_sched_node
*node
)
2374 nrow
= isl_mat_rows(node
->sched
);
2375 return node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
2378 /* Convert node->sched into a map and return this map.
2380 * The result is cached in node->sched_map, which needs to be released
2381 * whenever node->sched is updated.
2382 * It is defined over the uncompressed node domain.
2384 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2386 if (!node
->sched_map
) {
2389 ma
= node_extract_schedule_multi_aff(node
);
2390 node
->sched_map
= isl_map_from_multi_aff(ma
);
2393 return isl_map_copy(node
->sched_map
);
2396 /* Construct a map that can be used to update a dependence relation
2397 * based on the current schedule.
2398 * That is, construct a map expressing that source and sink
2399 * are executed within the same iteration of the current schedule.
2400 * This map can then be intersected with the dependence relation.
2401 * This is not the most efficient way, but this shouldn't be a critical
2404 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2405 struct isl_sched_node
*dst
)
2407 isl_map
*src_sched
, *dst_sched
;
2409 src_sched
= node_extract_schedule(src
);
2410 dst_sched
= node_extract_schedule(dst
);
2411 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2414 /* Intersect the domains of the nested relations in domain and range
2415 * of "umap" with "map".
2417 static __isl_give isl_union_map
*intersect_domains(
2418 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2420 isl_union_set
*uset
;
2422 umap
= isl_union_map_zip(umap
);
2423 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2424 umap
= isl_union_map_intersect_domain(umap
, uset
);
2425 umap
= isl_union_map_zip(umap
);
2429 /* Update the dependence relation of the given edge based
2430 * on the current schedule.
2431 * If the dependence is carried completely by the current schedule, then
2432 * it is removed from the edge_tables. It is kept in the list of edges
2433 * as otherwise all edge_tables would have to be recomputed.
2435 static int update_edge(struct isl_sched_graph
*graph
,
2436 struct isl_sched_edge
*edge
)
2440 id
= specializer(edge
->src
, edge
->dst
);
2441 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2445 if (edge
->tagged_condition
) {
2446 edge
->tagged_condition
=
2447 intersect_domains(edge
->tagged_condition
, id
);
2448 if (!edge
->tagged_condition
)
2451 if (edge
->tagged_validity
) {
2452 edge
->tagged_validity
=
2453 intersect_domains(edge
->tagged_validity
, id
);
2454 if (!edge
->tagged_validity
)
2459 if (isl_map_plain_is_empty(edge
->map
))
2460 graph_remove_edge(graph
, edge
);
2468 /* Update the dependence relations of all edges based on the current schedule.
2470 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2474 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2475 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2482 static void next_band(struct isl_sched_graph
*graph
)
2484 graph
->band_start
= graph
->n_total_row
;
2487 /* Return the union of the universe domains of the nodes in "graph"
2488 * that satisfy "pred".
2490 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
2491 struct isl_sched_graph
*graph
,
2492 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
2498 for (i
= 0; i
< graph
->n
; ++i
)
2499 if (pred(&graph
->node
[i
], data
))
2503 isl_die(ctx
, isl_error_internal
,
2504 "empty component", return NULL
);
2506 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
2507 dom
= isl_union_set_from_set(set
);
2509 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
2510 if (!pred(&graph
->node
[i
], data
))
2512 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
2513 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
2519 /* Return a list of unions of universe domains, where each element
2520 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
2522 static __isl_give isl_union_set_list
*extract_sccs(isl_ctx
*ctx
,
2523 struct isl_sched_graph
*graph
)
2526 isl_union_set_list
*filters
;
2528 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
2529 for (i
= 0; i
< graph
->scc
; ++i
) {
2532 dom
= isl_sched_graph_domain(ctx
, graph
, &node_scc_exactly
, i
);
2533 filters
= isl_union_set_list_add(filters
, dom
);
2539 /* Return a list of two unions of universe domains, one for the SCCs up
2540 * to and including graph->src_scc and another for the other SCCS.
2542 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
2543 struct isl_sched_graph
*graph
)
2546 isl_union_set_list
*filters
;
2548 filters
= isl_union_set_list_alloc(ctx
, 2);
2549 dom
= isl_sched_graph_domain(ctx
, graph
,
2550 &node_scc_at_most
, graph
->src_scc
);
2551 filters
= isl_union_set_list_add(filters
, dom
);
2552 dom
= isl_sched_graph_domain(ctx
, graph
,
2553 &node_scc_at_least
, graph
->src_scc
+ 1);
2554 filters
= isl_union_set_list_add(filters
, dom
);
2559 /* Topologically sort statements mapped to the same schedule iteration
2560 * and add insert a sequence node in front of "node"
2561 * corresponding to this order.
2563 static __isl_give isl_schedule_node
*sort_statements(
2564 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
2567 isl_union_set_list
*filters
;
2572 ctx
= isl_schedule_node_get_ctx(node
);
2574 isl_die(ctx
, isl_error_internal
,
2575 "graph should have at least one node",
2576 return isl_schedule_node_free(node
));
2581 if (update_edges(ctx
, graph
) < 0)
2582 return isl_schedule_node_free(node
);
2584 if (graph
->n_edge
== 0)
2587 if (detect_sccs(ctx
, graph
) < 0)
2588 return isl_schedule_node_free(node
);
2590 filters
= extract_sccs(ctx
, graph
);
2591 node
= isl_schedule_node_insert_sequence(node
, filters
);
2596 /* Copy nodes that satisfy node_pred from the src dependence graph
2597 * to the dst dependence graph.
2599 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2600 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2605 for (i
= 0; i
< src
->n
; ++i
) {
2608 if (!node_pred(&src
->node
[i
], data
))
2612 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
2613 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
2614 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
2615 dst
->node
[j
].compress
=
2616 isl_multi_aff_copy(src
->node
[i
].compress
);
2617 dst
->node
[j
].decompress
=
2618 isl_multi_aff_copy(src
->node
[i
].decompress
);
2619 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
2620 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
2621 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2622 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
2623 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
2626 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
2628 if (dst
->node
[j
].compressed
&&
2629 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
2630 !dst
->node
[j
].decompress
))
2637 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2638 * to the dst dependence graph.
2639 * If the source or destination node of the edge is not in the destination
2640 * graph, then it must be a backward proximity edge and it should simply
2643 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2644 struct isl_sched_graph
*src
,
2645 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2648 enum isl_edge_type t
;
2651 for (i
= 0; i
< src
->n_edge
; ++i
) {
2652 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2654 isl_union_map
*tagged_condition
;
2655 isl_union_map
*tagged_validity
;
2656 struct isl_sched_node
*dst_src
, *dst_dst
;
2658 if (!edge_pred(edge
, data
))
2661 if (isl_map_plain_is_empty(edge
->map
))
2664 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
2665 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
2666 if (!dst_src
|| !dst_dst
) {
2667 if (edge
->validity
|| edge
->conditional_validity
)
2668 isl_die(ctx
, isl_error_internal
,
2669 "backward (conditional) validity edge",
2674 map
= isl_map_copy(edge
->map
);
2675 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
2676 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
2678 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2679 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2680 dst
->edge
[dst
->n_edge
].map
= map
;
2681 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
2682 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
2683 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2684 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2685 dst
->edge
[dst
->n_edge
].coincidence
= edge
->coincidence
;
2686 dst
->edge
[dst
->n_edge
].condition
= edge
->condition
;
2687 dst
->edge
[dst
->n_edge
].conditional_validity
=
2688 edge
->conditional_validity
;
2691 if (edge
->tagged_condition
&& !tagged_condition
)
2693 if (edge
->tagged_validity
&& !tagged_validity
)
2696 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2698 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2700 if (graph_edge_table_add(ctx
, dst
, t
,
2701 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2709 /* Compute the maximal number of variables over all nodes.
2710 * This is the maximal number of linearly independent schedule
2711 * rows that we need to compute.
2712 * Just in case we end up in a part of the dependence graph
2713 * with only lower-dimensional domains, we make sure we will
2714 * compute the required amount of extra linearly independent rows.
2716 static int compute_maxvar(struct isl_sched_graph
*graph
)
2721 for (i
= 0; i
< graph
->n
; ++i
) {
2722 struct isl_sched_node
*node
= &graph
->node
[i
];
2725 if (node_update_cmap(node
) < 0)
2727 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2728 if (nvar
> graph
->maxvar
)
2729 graph
->maxvar
= nvar
;
2735 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
2736 struct isl_sched_graph
*graph
);
2737 static __isl_give isl_schedule_node
*compute_schedule_wcc(
2738 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
2740 /* Compute a schedule for a subgraph of "graph". In particular, for
2741 * the graph composed of nodes that satisfy node_pred and edges that
2742 * that satisfy edge_pred. The caller should precompute the number
2743 * of nodes and edges that satisfy these predicates and pass them along
2744 * as "n" and "n_edge".
2745 * If the subgraph is known to consist of a single component, then wcc should
2746 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2747 * Otherwise, we call compute_schedule, which will check whether the subgraph
2750 * The schedule is inserted at "node" and the updated schedule node
2753 static __isl_give isl_schedule_node
*compute_sub_schedule(
2754 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
2755 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2756 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2757 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2760 struct isl_sched_graph split
= { 0 };
2763 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2765 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2767 if (graph_init_table(ctx
, &split
) < 0)
2769 for (t
= 0; t
<= isl_edge_last
; ++t
)
2770 split
.max_edge
[t
] = graph
->max_edge
[t
];
2771 if (graph_init_edge_tables(ctx
, &split
) < 0)
2773 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2775 split
.n_row
= graph
->n_row
;
2776 split
.max_row
= graph
->max_row
;
2777 split
.n_total_row
= graph
->n_total_row
;
2778 split
.band_start
= graph
->band_start
;
2781 node
= compute_schedule_wcc(node
, &split
);
2783 node
= compute_schedule(node
, &split
);
2785 graph_free(ctx
, &split
);
2788 graph_free(ctx
, &split
);
2789 return isl_schedule_node_free(node
);
2792 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2794 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2797 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2799 return edge
->dst
->scc
<= scc
;
2802 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2804 return edge
->src
->scc
>= scc
;
2807 /* Reset the current band by dropping all its schedule rows.
2809 static int reset_band(struct isl_sched_graph
*graph
)
2814 drop
= graph
->n_total_row
- graph
->band_start
;
2815 graph
->n_total_row
-= drop
;
2816 graph
->n_row
-= drop
;
2818 for (i
= 0; i
< graph
->n
; ++i
) {
2819 struct isl_sched_node
*node
= &graph
->node
[i
];
2821 isl_map_free(node
->sched_map
);
2822 node
->sched_map
= NULL
;
2824 node
->sched
= isl_mat_drop_rows(node
->sched
,
2825 graph
->band_start
, drop
);
2834 /* Split the current graph into two parts and compute a schedule for each
2835 * part individually. In particular, one part consists of all SCCs up
2836 * to and including graph->src_scc, while the other part contains the other
2837 * SCCS. The split is enforced by a sequence node inserted at position "node"
2838 * in the schedule tree. Return the updated schedule node.
2840 * The current band is reset. It would be possible to reuse
2841 * the previously computed rows as the first rows in the next
2842 * band, but recomputing them may result in better rows as we are looking
2843 * at a smaller part of the dependence graph.
2845 static __isl_give isl_schedule_node
*compute_split_schedule(
2846 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
2851 isl_union_set_list
*filters
;
2856 if (reset_band(graph
) < 0)
2857 return isl_schedule_node_free(node
);
2860 for (i
= 0; i
< graph
->n
; ++i
) {
2861 struct isl_sched_node
*node
= &graph
->node
[i
];
2862 int before
= node
->scc
<= graph
->src_scc
;
2869 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2870 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2872 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2878 ctx
= isl_schedule_node_get_ctx(node
);
2879 filters
= extract_split(ctx
, graph
);
2880 node
= isl_schedule_node_insert_sequence(node
, filters
);
2881 node
= isl_schedule_node_child(node
, 0);
2882 node
= isl_schedule_node_child(node
, 0);
2884 orig_total_row
= graph
->n_total_row
;
2885 node
= compute_sub_schedule(node
, ctx
, graph
, n
, e1
,
2886 &node_scc_at_most
, &edge_dst_scc_at_most
,
2888 node
= isl_schedule_node_parent(node
);
2889 node
= isl_schedule_node_next_sibling(node
);
2890 node
= isl_schedule_node_child(node
, 0);
2891 graph
->n_total_row
= orig_total_row
;
2892 node
= compute_sub_schedule(node
, ctx
, graph
, graph
->n
- n
, e2
,
2893 &node_scc_at_least
, &edge_src_scc_at_least
,
2894 graph
->src_scc
+ 1, 0);
2895 node
= isl_schedule_node_parent(node
);
2896 node
= isl_schedule_node_parent(node
);
2901 /* Insert a band node at position "node" in the schedule tree corresponding
2902 * to the current band in "graph". Mark the band node permutable
2903 * if "permutable" is set.
2904 * The partial schedules and the coincidence property are extracted
2905 * from the graph nodes.
2906 * Return the updated schedule node.
2908 static __isl_give isl_schedule_node
*insert_current_band(
2909 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
2915 isl_multi_pw_aff
*mpa
;
2916 isl_multi_union_pw_aff
*mupa
;
2922 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
2923 "graph should have at least one node",
2924 return isl_schedule_node_free(node
));
2926 start
= graph
->band_start
;
2927 end
= graph
->n_total_row
;
2930 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[0], start
, n
);
2931 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
2932 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
2934 for (i
= 1; i
< graph
->n
; ++i
) {
2935 isl_multi_union_pw_aff
*mupa_i
;
2937 ma
= node_extract_partial_schedule_multi_aff(&graph
->node
[i
],
2939 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
2940 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
2941 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
2943 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
2945 for (i
= 0; i
< n
; ++i
)
2946 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
2947 graph
->node
[0].coincident
[start
+ i
]);
2948 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
2953 /* Update the dependence relations based on the current schedule,
2954 * add the current band to "node" and the continue with the computation
2956 * Return the updated schedule node.
2958 static __isl_give isl_schedule_node
*compute_next_band(
2959 __isl_take isl_schedule_node
*node
,
2960 struct isl_sched_graph
*graph
, int permutable
)
2967 ctx
= isl_schedule_node_get_ctx(node
);
2968 if (update_edges(ctx
, graph
) < 0)
2969 return isl_schedule_node_free(node
);
2970 node
= insert_current_band(node
, graph
, permutable
);
2973 node
= isl_schedule_node_child(node
, 0);
2974 node
= compute_schedule(node
, graph
);
2975 node
= isl_schedule_node_parent(node
);
2980 /* Add constraints to graph->lp that force the dependence "map" (which
2981 * is part of the dependence relation of "edge")
2982 * to be respected and attempt to carry it, where the edge is one from
2983 * a node j to itself. "pos" is the sequence number of the given map.
2984 * That is, add constraints that enforce
2986 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2987 * = c_j_x (y - x) >= e_i
2989 * for each (x,y) in R.
2990 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2991 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2992 * with each coefficient in c_j_x represented as a pair of non-negative
2995 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2996 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2999 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3001 isl_dim_map
*dim_map
;
3002 isl_basic_set
*coef
;
3003 struct isl_sched_node
*node
= edge
->src
;
3005 coef
= intra_coefficients(graph
, node
, map
);
3009 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3011 total
= isl_basic_set_total_dim(graph
->lp
);
3012 dim_map
= isl_dim_map_alloc(ctx
, total
);
3013 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3014 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
3015 isl_space_dim(dim
, isl_dim_set
), 1,
3017 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
3018 isl_space_dim(dim
, isl_dim_set
), 1,
3020 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3021 coef
->n_eq
, coef
->n_ineq
);
3022 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3024 isl_space_free(dim
);
3029 /* Add constraints to graph->lp that force the dependence "map" (which
3030 * is part of the dependence relation of "edge")
3031 * to be respected and attempt to carry it, where the edge is one from
3032 * node j to node k. "pos" is the sequence number of the given map.
3033 * That is, add constraints that enforce
3035 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3037 * for each (x,y) in R.
3038 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3039 * of valid constraints for R and then plug in
3040 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3041 * with each coefficient (except e_i, c_k_0 and c_j_0)
3042 * represented as a pair of non-negative coefficients.
3044 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3045 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3048 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3050 isl_dim_map
*dim_map
;
3051 isl_basic_set
*coef
;
3052 struct isl_sched_node
*src
= edge
->src
;
3053 struct isl_sched_node
*dst
= edge
->dst
;
3055 coef
= inter_coefficients(graph
, edge
, map
);
3059 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3061 total
= isl_basic_set_total_dim(graph
->lp
);
3062 dim_map
= isl_dim_map_alloc(ctx
, total
);
3064 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3066 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
3067 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
3068 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
3069 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
3070 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3072 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
3073 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3076 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
3077 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
3078 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
3079 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
3080 isl_space_dim(dim
, isl_dim_set
), 1,
3082 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
3083 isl_space_dim(dim
, isl_dim_set
), 1,
3086 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3087 coef
->n_eq
, coef
->n_ineq
);
3088 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3090 isl_space_free(dim
);
3095 /* Add constraints to graph->lp that force all (conditional) validity
3096 * dependences to be respected and attempt to carry them.
3098 static int add_all_constraints(struct isl_sched_graph
*graph
)
3104 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3105 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3107 if (!edge
->validity
&& !edge
->conditional_validity
)
3110 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3111 isl_basic_map
*bmap
;
3114 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3115 map
= isl_map_from_basic_map(bmap
);
3117 if (edge
->src
== edge
->dst
&&
3118 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3120 if (edge
->src
!= edge
->dst
&&
3121 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3130 /* Count the number of equality and inequality constraints
3131 * that will be added to the carry_lp problem.
3132 * We count each edge exactly once.
3134 static int count_all_constraints(struct isl_sched_graph
*graph
,
3135 int *n_eq
, int *n_ineq
)
3139 *n_eq
= *n_ineq
= 0;
3140 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3141 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3142 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3143 isl_basic_map
*bmap
;
3146 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3147 map
= isl_map_from_basic_map(bmap
);
3149 if (count_map_constraints(graph
, edge
, map
,
3150 n_eq
, n_ineq
, 1, 0) < 0)
3158 /* Construct an LP problem for finding schedule coefficients
3159 * such that the schedule carries as many dependences as possible.
3160 * In particular, for each dependence i, we bound the dependence distance
3161 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3162 * of all e_i's. Dependence with e_i = 0 in the solution are simply
3163 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3164 * Note that if the dependence relation is a union of basic maps,
3165 * then we have to consider each basic map individually as it may only
3166 * be possible to carry the dependences expressed by some of those
3167 * basic maps and not all off them.
3168 * Below, we consider each of those basic maps as a separate "edge".
3170 * All variables of the LP are non-negative. The actual coefficients
3171 * may be negative, so each coefficient is represented as the difference
3172 * of two non-negative variables. The negative part always appears
3173 * immediately before the positive part.
3174 * Other than that, the variables have the following order
3176 * - sum of (1 - e_i) over all edges
3177 * - sum of positive and negative parts of all c_n coefficients
3178 * (unconstrained when computing non-parametric schedules)
3179 * - sum of positive and negative parts of all c_x coefficients
3184 * - positive and negative parts of c_i_n (if parametric)
3185 * - positive and negative parts of c_i_x
3187 * The constraints are those from the (validity) edges plus three equalities
3188 * to express the sums and n_edge inequalities to express e_i <= 1.
3190 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3200 for (i
= 0; i
< graph
->n_edge
; ++i
)
3201 n_edge
+= graph
->edge
[i
].map
->n
;
3204 for (i
= 0; i
< graph
->n
; ++i
) {
3205 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3206 node
->start
= total
;
3207 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
3210 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3212 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
3215 dim
= isl_space_set_alloc(ctx
, 0, total
);
3216 isl_basic_set_free(graph
->lp
);
3219 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3220 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3222 k
= isl_basic_set_alloc_equality(graph
->lp
);
3225 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3226 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3227 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3228 for (i
= 0; i
< n_edge
; ++i
)
3229 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3231 k
= isl_basic_set_alloc_equality(graph
->lp
);
3234 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3235 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
3236 for (i
= 0; i
< graph
->n
; ++i
) {
3237 int pos
= 1 + graph
->node
[i
].start
+ 1;
3239 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
3240 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3243 k
= isl_basic_set_alloc_equality(graph
->lp
);
3246 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3247 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
3248 for (i
= 0; i
< graph
->n
; ++i
) {
3249 struct isl_sched_node
*node
= &graph
->node
[i
];
3250 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3252 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
3253 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3256 for (i
= 0; i
< n_edge
; ++i
) {
3257 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3260 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3261 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3262 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3265 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
3267 if (add_all_constraints(graph
) < 0)
3273 static __isl_give isl_schedule_node
*compute_component_schedule(
3274 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3277 /* Comparison function for sorting the statements based on
3278 * the corresponding value in "r".
3280 static int smaller_value(const void *a
, const void *b
, void *data
)
3286 return isl_int_cmp(r
->el
[*i1
], r
->el
[*i2
]);
3289 /* If the schedule_split_scaled option is set and if the linear
3290 * parts of the scheduling rows for all nodes in the graphs have
3291 * a non-trivial common divisor, then split off the remainder of the
3292 * constant term modulo this common divisor from the linear part.
3293 * Otherwise, insert a band node directly and continue with
3294 * the construction of the schedule.
3296 * If a non-trivial common divisor is found, then
3297 * the linear part is reduced and the remainder is enforced
3298 * by a sequence node with the children placed in the order
3299 * of this remainder.
3300 * In particular, we assign an scc index based on the remainder and
3301 * then rely on compute_component_schedule to insert the sequence and
3302 * to continue the schedule construction on each part.
3304 static __isl_give isl_schedule_node
*split_scaled(
3305 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3318 ctx
= isl_schedule_node_get_ctx(node
);
3319 if (!ctx
->opt
->schedule_split_scaled
)
3320 return compute_next_band(node
, graph
, 0);
3322 return compute_next_band(node
, graph
, 0);
3325 isl_int_init(gcd_i
);
3327 isl_int_set_si(gcd
, 0);
3329 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3331 for (i
= 0; i
< graph
->n
; ++i
) {
3332 struct isl_sched_node
*node
= &graph
->node
[i
];
3333 int cols
= isl_mat_cols(node
->sched
);
3335 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3336 isl_int_gcd(gcd
, gcd
, gcd_i
);
3339 isl_int_clear(gcd_i
);
3341 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3343 return compute_next_band(node
, graph
, 0);
3346 r
= isl_vec_alloc(ctx
, graph
->n
);
3347 order
= isl_calloc_array(ctx
, int, graph
->n
);
3351 for (i
= 0; i
< graph
->n
; ++i
) {
3352 struct isl_sched_node
*node
= &graph
->node
[i
];
3355 isl_int_fdiv_r(r
->el
[i
], node
->sched
->row
[row
][0], gcd
);
3356 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3357 node
->sched
->row
[row
][0], gcd
);
3358 isl_int_mul(node
->sched
->row
[row
][0],
3359 node
->sched
->row
[row
][0], gcd
);
3360 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3365 if (isl_sort(order
, graph
->n
, sizeof(order
[0]), &smaller_value
, r
) < 0)
3369 for (i
= 0; i
< graph
->n
; ++i
) {
3370 if (i
> 0 && isl_int_ne(r
->el
[order
[i
- 1]], r
->el
[order
[i
]]))
3372 graph
->node
[order
[i
]].scc
= scc
;
3381 if (update_edges(ctx
, graph
) < 0)
3382 return isl_schedule_node_free(node
);
3383 node
= insert_current_band(node
, graph
, 0);
3386 node
= isl_schedule_node_child(node
, 0);
3387 node
= compute_component_schedule(node
, graph
, 0);
3388 node
= isl_schedule_node_parent(node
);
3395 return isl_schedule_node_free(node
);
3398 /* Is the schedule row "sol" trivial on node "node"?
3399 * That is, is the solution zero on the dimensions orthogonal to
3400 * the previously found solutions?
3401 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3403 * Each coefficient is represented as the difference between
3404 * two non-negative values in "sol". "sol" has been computed
3405 * in terms of the original iterators (i.e., without use of cmap).
3406 * We construct the schedule row s and write it as a linear
3407 * combination of (linear combinations of) previously computed schedule rows.
3408 * s = Q c or c = U s.
3409 * If the final entries of c are all zero, then the solution is trivial.
3411 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3421 if (node
->nvar
== node
->rank
)
3424 ctx
= isl_vec_get_ctx(sol
);
3425 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3429 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3431 for (i
= 0; i
< node
->nvar
; ++i
)
3432 isl_int_sub(node_sol
->el
[i
],
3433 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3435 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3440 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3441 node
->nvar
- node
->rank
) == -1;
3443 isl_vec_free(node_sol
);
3448 /* Is the schedule row "sol" trivial on any node where it should
3450 * "sol" has been computed in terms of the original iterators
3451 * (i.e., without use of cmap).
3452 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3454 static int is_any_trivial(struct isl_sched_graph
*graph
,
3455 __isl_keep isl_vec
*sol
)
3459 for (i
= 0; i
< graph
->n
; ++i
) {
3460 struct isl_sched_node
*node
= &graph
->node
[i
];
3463 if (!needs_row(graph
, node
))
3465 trivial
= is_trivial(node
, sol
);
3466 if (trivial
< 0 || trivial
)
3473 /* Construct a schedule row for each node such that as many dependences
3474 * as possible are carried and then continue with the next band.
3476 * If the computed schedule row turns out to be trivial on one or
3477 * more nodes where it should not be trivial, then we throw it away
3478 * and try again on each component separately.
3480 * If there is only one component, then we accept the schedule row anyway,
3481 * but we do not consider it as a complete row and therefore do not
3482 * increment graph->n_row. Note that the ranks of the nodes that
3483 * do get a non-trivial schedule part will get updated regardless and
3484 * graph->maxvar is computed based on these ranks. The test for
3485 * whether more schedule rows are required in compute_schedule_wcc
3486 * is therefore not affected.
3488 * Insert a band corresponding to the schedule row at position "node"
3489 * of the schedule tree and continue with the construction of the schedule.
3490 * This insertion and the continued construction is performed by split_scaled
3491 * after optionally checking for non-trivial common divisors.
3493 static __isl_give isl_schedule_node
*carry_dependences(
3494 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3507 for (i
= 0; i
< graph
->n_edge
; ++i
)
3508 n_edge
+= graph
->edge
[i
].map
->n
;
3510 ctx
= isl_schedule_node_get_ctx(node
);
3511 if (setup_carry_lp(ctx
, graph
) < 0)
3512 return isl_schedule_node_free(node
);
3514 lp
= isl_basic_set_copy(graph
->lp
);
3515 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3517 return isl_schedule_node_free(node
);
3519 if (sol
->size
== 0) {
3521 isl_die(ctx
, isl_error_internal
,
3522 "error in schedule construction",
3523 return isl_schedule_node_free(node
));
3526 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3527 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3529 isl_die(ctx
, isl_error_unknown
,
3530 "unable to carry dependences",
3531 return isl_schedule_node_free(node
));
3534 trivial
= is_any_trivial(graph
, sol
);
3536 sol
= isl_vec_free(sol
);
3537 } else if (trivial
&& graph
->scc
> 1) {
3539 return compute_component_schedule(node
, graph
, 1);
3542 if (update_schedule(graph
, sol
, 0, 0) < 0)
3543 return isl_schedule_node_free(node
);
3547 return split_scaled(node
, graph
);
3550 /* Are there any (non-empty) (conditional) validity edges in the graph?
3552 static int has_validity_edges(struct isl_sched_graph
*graph
)
3556 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3559 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3564 if (graph
->edge
[i
].validity
||
3565 graph
->edge
[i
].conditional_validity
)
3572 /* Should we apply a Feautrier step?
3573 * That is, did the user request the Feautrier algorithm and are
3574 * there any validity dependences (left)?
3576 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3578 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3581 return has_validity_edges(graph
);
3584 /* Compute a schedule for a connected dependence graph using Feautrier's
3585 * multi-dimensional scheduling algorithm and return the updated schedule node.
3587 * The original algorithm is described in [1].
3588 * The main idea is to minimize the number of scheduling dimensions, by
3589 * trying to satisfy as many dependences as possible per scheduling dimension.
3591 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3592 * Problem, Part II: Multi-Dimensional Time.
3593 * In Intl. Journal of Parallel Programming, 1992.
3595 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
3596 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3598 return carry_dependences(node
, graph
);
3601 /* Turn off the "local" bit on all (condition) edges.
3603 static void clear_local_edges(struct isl_sched_graph
*graph
)
3607 for (i
= 0; i
< graph
->n_edge
; ++i
)
3608 if (graph
->edge
[i
].condition
)
3609 graph
->edge
[i
].local
= 0;
3612 /* Does "graph" have both condition and conditional validity edges?
3614 static int need_condition_check(struct isl_sched_graph
*graph
)
3617 int any_condition
= 0;
3618 int any_conditional_validity
= 0;
3620 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3621 if (graph
->edge
[i
].condition
)
3623 if (graph
->edge
[i
].conditional_validity
)
3624 any_conditional_validity
= 1;
3627 return any_condition
&& any_conditional_validity
;
3630 /* Does "graph" contain any coincidence edge?
3632 static int has_any_coincidence(struct isl_sched_graph
*graph
)
3636 for (i
= 0; i
< graph
->n_edge
; ++i
)
3637 if (graph
->edge
[i
].coincidence
)
3643 /* Extract the final schedule row as a map with the iteration domain
3644 * of "node" as domain.
3646 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
3648 isl_local_space
*ls
;
3652 row
= isl_mat_rows(node
->sched
) - 1;
3653 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
3654 aff
= extract_schedule_row(ls
, node
, row
);
3655 return isl_map_from_aff(aff
);
3658 /* Is the conditional validity dependence in the edge with index "edge_index"
3659 * violated by the latest (i.e., final) row of the schedule?
3660 * That is, is i scheduled after j
3661 * for any conditional validity dependence i -> j?
3663 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
3665 isl_map
*src_sched
, *dst_sched
, *map
;
3666 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
3669 src_sched
= final_row(edge
->src
);
3670 dst_sched
= final_row(edge
->dst
);
3671 map
= isl_map_copy(edge
->map
);
3672 map
= isl_map_apply_domain(map
, src_sched
);
3673 map
= isl_map_apply_range(map
, dst_sched
);
3674 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
3675 empty
= isl_map_is_empty(map
);
3684 /* Does the domain of "umap" intersect "uset"?
3686 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3687 __isl_keep isl_union_set
*uset
)
3691 umap
= isl_union_map_copy(umap
);
3692 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3693 empty
= isl_union_map_is_empty(umap
);
3694 isl_union_map_free(umap
);
3696 return empty
< 0 ? -1 : !empty
;
3699 /* Does the range of "umap" intersect "uset"?
3701 static int range_intersects(__isl_keep isl_union_map
*umap
,
3702 __isl_keep isl_union_set
*uset
)
3706 umap
= isl_union_map_copy(umap
);
3707 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3708 empty
= isl_union_map_is_empty(umap
);
3709 isl_union_map_free(umap
);
3711 return empty
< 0 ? -1 : !empty
;
3714 /* Are the condition dependences of "edge" local with respect to
3715 * the current schedule?
3717 * That is, are domain and range of the condition dependences mapped
3718 * to the same point?
3720 * In other words, is the condition false?
3722 static int is_condition_false(struct isl_sched_edge
*edge
)
3724 isl_union_map
*umap
;
3725 isl_map
*map
, *sched
, *test
;
3728 umap
= isl_union_map_copy(edge
->tagged_condition
);
3729 umap
= isl_union_map_zip(umap
);
3730 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3731 map
= isl_map_from_union_map(umap
);
3733 sched
= node_extract_schedule(edge
->src
);
3734 map
= isl_map_apply_domain(map
, sched
);
3735 sched
= node_extract_schedule(edge
->dst
);
3736 map
= isl_map_apply_range(map
, sched
);
3738 test
= isl_map_identity(isl_map_get_space(map
));
3739 local
= isl_map_is_subset(map
, test
);
3746 /* Does "graph" have any satisfied condition edges that
3747 * are adjacent to the conditional validity constraint with
3748 * domain "conditional_source" and range "conditional_sink"?
3750 * A satisfied condition is one that is not local.
3751 * If a condition was forced to be local already (i.e., marked as local)
3752 * then there is no need to check if it is in fact local.
3754 * Additionally, mark all adjacent condition edges found as local.
3756 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
3757 __isl_keep isl_union_set
*conditional_source
,
3758 __isl_keep isl_union_set
*conditional_sink
)
3763 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3764 int adjacent
, local
;
3765 isl_union_map
*condition
;
3767 if (!graph
->edge
[i
].condition
)
3769 if (graph
->edge
[i
].local
)
3772 condition
= graph
->edge
[i
].tagged_condition
;
3773 adjacent
= domain_intersects(condition
, conditional_sink
);
3774 if (adjacent
>= 0 && !adjacent
)
3775 adjacent
= range_intersects(condition
,
3776 conditional_source
);
3782 graph
->edge
[i
].local
= 1;
3784 local
= is_condition_false(&graph
->edge
[i
]);
3794 /* Are there any violated conditional validity dependences with
3795 * adjacent condition dependences that are not local with respect
3796 * to the current schedule?
3797 * That is, is the conditional validity constraint violated?
3799 * Additionally, mark all those adjacent condition dependences as local.
3800 * We also mark those adjacent condition dependences that were not marked
3801 * as local before, but just happened to be local already. This ensures
3802 * that they remain local if the schedule is recomputed.
3804 * We first collect domain and range of all violated conditional validity
3805 * dependences and then check if there are any adjacent non-local
3806 * condition dependences.
3808 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
3809 struct isl_sched_graph
*graph
)
3813 isl_union_set
*source
, *sink
;
3815 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3816 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3817 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3818 isl_union_set
*uset
;
3819 isl_union_map
*umap
;
3822 if (!graph
->edge
[i
].conditional_validity
)
3825 violated
= is_violated(graph
, i
);
3833 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3834 uset
= isl_union_map_domain(umap
);
3835 source
= isl_union_set_union(source
, uset
);
3836 source
= isl_union_set_coalesce(source
);
3838 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3839 uset
= isl_union_map_range(umap
);
3840 sink
= isl_union_set_union(sink
, uset
);
3841 sink
= isl_union_set_coalesce(sink
);
3845 any
= has_adjacent_true_conditions(graph
, source
, sink
);
3847 isl_union_set_free(source
);
3848 isl_union_set_free(sink
);
3851 isl_union_set_free(source
);
3852 isl_union_set_free(sink
);
3856 /* Compute a schedule for a connected dependence graph and return
3857 * the updated schedule node.
3859 * We try to find a sequence of as many schedule rows as possible that result
3860 * in non-negative dependence distances (independent of the previous rows
3861 * in the sequence, i.e., such that the sequence is tilable), with as
3862 * many of the initial rows as possible satisfying the coincidence constraints.
3863 * If we can't find any more rows we either
3864 * - split between SCCs and start over (assuming we found an interesting
3865 * pair of SCCs between which to split)
3866 * - continue with the next band (assuming the current band has at least
3868 * - try to carry as many dependences as possible and continue with the next
3870 * In each case, we first insert a band node in the schedule tree
3871 * if any rows have been computed.
3873 * If Feautrier's algorithm is selected, we first recursively try to satisfy
3874 * as many validity dependences as possible. When all validity dependences
3875 * are satisfied we extend the schedule to a full-dimensional schedule.
3877 * If we manage to complete the schedule, we insert a band node
3878 * (if any schedule rows were computed) and we finish off by topologically
3879 * sorting the statements based on the remaining dependences.
3881 * If ctx->opt->schedule_outer_coincidence is set, then we force the
3882 * outermost dimension to satisfy the coincidence constraints. If this
3883 * turns out to be impossible, we fall back on the general scheme above
3884 * and try to carry as many dependences as possible.
3886 * If "graph" contains both condition and conditional validity dependences,
3887 * then we need to check that that the conditional schedule constraint
3888 * is satisfied, i.e., there are no violated conditional validity dependences
3889 * that are adjacent to any non-local condition dependences.
3890 * If there are, then we mark all those adjacent condition dependences
3891 * as local and recompute the current band. Those dependences that
3892 * are marked local will then be forced to be local.
3893 * The initial computation is performed with no dependences marked as local.
3894 * If we are lucky, then there will be no violated conditional validity
3895 * dependences adjacent to any non-local condition dependences.
3896 * Otherwise, we mark some additional condition dependences as local and
3897 * recompute. We continue this process until there are no violations left or
3898 * until we are no longer able to compute a schedule.
3899 * Since there are only a finite number of dependences,
3900 * there will only be a finite number of iterations.
3902 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3903 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3905 int has_coincidence
;
3906 int use_coincidence
;
3907 int force_coincidence
= 0;
3908 int check_conditional
;
3914 ctx
= isl_schedule_node_get_ctx(node
);
3915 if (detect_sccs(ctx
, graph
) < 0)
3916 return isl_schedule_node_free(node
);
3917 if (sort_sccs(graph
) < 0)
3918 return isl_schedule_node_free(node
);
3920 if (compute_maxvar(graph
) < 0)
3921 return isl_schedule_node_free(node
);
3923 if (need_feautrier_step(ctx
, graph
))
3924 return compute_schedule_wcc_feautrier(node
, graph
);
3926 clear_local_edges(graph
);
3927 check_conditional
= need_condition_check(graph
);
3928 has_coincidence
= has_any_coincidence(graph
);
3930 if (ctx
->opt
->schedule_outer_coincidence
)
3931 force_coincidence
= 1;
3933 use_coincidence
= has_coincidence
;
3934 while (graph
->n_row
< graph
->maxvar
) {
3939 graph
->src_scc
= -1;
3940 graph
->dst_scc
= -1;
3942 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
3943 return isl_schedule_node_free(node
);
3944 sol
= solve_lp(graph
);
3946 return isl_schedule_node_free(node
);
3947 if (sol
->size
== 0) {
3948 int empty
= graph
->n_total_row
== graph
->band_start
;
3951 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
3952 use_coincidence
= 0;
3955 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
3956 return compute_next_band(node
, graph
, 1);
3957 if (graph
->src_scc
>= 0)
3958 return compute_split_schedule(node
, graph
);
3960 return compute_next_band(node
, graph
, 1);
3961 return carry_dependences(node
, graph
);
3963 coincident
= !has_coincidence
|| use_coincidence
;
3964 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
3965 return isl_schedule_node_free(node
);
3967 if (!check_conditional
)
3969 violated
= has_violated_conditional_constraint(ctx
, graph
);
3971 return isl_schedule_node_free(node
);
3974 if (reset_band(graph
) < 0)
3975 return isl_schedule_node_free(node
);
3976 use_coincidence
= has_coincidence
;
3979 if (graph
->n_total_row
> graph
->band_start
) {
3980 node
= insert_current_band(node
, graph
, 1);
3981 node
= isl_schedule_node_child(node
, 0);
3983 node
= sort_statements(node
, graph
);
3984 if (graph
->n_total_row
> graph
->band_start
)
3985 node
= isl_schedule_node_parent(node
);
3990 /* Compute a schedule for each group of nodes identified by node->scc
3991 * separately and then combine them in a sequence node (or as set node
3992 * if graph->weak is set) inserted at position "node" of the schedule tree.
3993 * Return the updated schedule node.
3995 * If "wcc" is set then each of the groups belongs to a single
3996 * weakly connected component in the dependence graph so that
3997 * there is no need for compute_sub_schedule to look for weakly
3998 * connected components.
4000 static __isl_give isl_schedule_node
*compute_component_schedule(
4001 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4008 isl_union_set_list
*filters
;
4012 ctx
= isl_schedule_node_get_ctx(node
);
4014 filters
= extract_sccs(ctx
, graph
);
4016 node
= isl_schedule_node_insert_set(node
, filters
);
4018 node
= isl_schedule_node_insert_sequence(node
, filters
);
4020 orig_total_row
= graph
->n_total_row
;
4021 for (component
= 0; component
< graph
->scc
; ++component
) {
4023 for (i
= 0; i
< graph
->n
; ++i
)
4024 if (graph
->node
[i
].scc
== component
)
4027 for (i
= 0; i
< graph
->n_edge
; ++i
)
4028 if (graph
->edge
[i
].src
->scc
== component
&&
4029 graph
->edge
[i
].dst
->scc
== component
)
4032 node
= isl_schedule_node_child(node
, component
);
4033 node
= isl_schedule_node_child(node
, 0);
4034 node
= compute_sub_schedule(node
, ctx
, graph
, n
, n_edge
,
4036 &edge_scc_exactly
, component
, wcc
);
4037 node
= isl_schedule_node_parent(node
);
4038 node
= isl_schedule_node_parent(node
);
4039 graph
->n_total_row
= orig_total_row
;
4045 /* Compute a schedule for the given dependence graph and insert it at "node".
4046 * Return the updated schedule node.
4048 * We first check if the graph is connected (through validity and conditional
4049 * validity dependences) and, if not, compute a schedule
4050 * for each component separately.
4051 * If schedule_fuse is set to minimal fusion, then we check for strongly
4052 * connected components instead and compute a separate schedule for
4053 * each such strongly connected component.
4055 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
4056 struct isl_sched_graph
*graph
)
4063 ctx
= isl_schedule_node_get_ctx(node
);
4064 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
4065 if (detect_sccs(ctx
, graph
) < 0)
4066 return isl_schedule_node_free(node
);
4068 if (detect_wccs(ctx
, graph
) < 0)
4069 return isl_schedule_node_free(node
);
4073 return compute_component_schedule(node
, graph
, 1);
4075 return compute_schedule_wcc(node
, graph
);
4078 /* Compute a schedule on sc->domain that respects the given schedule
4081 * In particular, the schedule respects all the validity dependences.
4082 * If the default isl scheduling algorithm is used, it tries to minimize
4083 * the dependence distances over the proximity dependences.
4084 * If Feautrier's scheduling algorithm is used, the proximity dependence
4085 * distances are only minimized during the extension to a full-dimensional
4088 * If there are any condition and conditional validity dependences,
4089 * then the conditional validity dependences may be violated inside
4090 * a tilable band, provided they have no adjacent non-local
4091 * condition dependences.
4093 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
4094 __isl_take isl_schedule_constraints
*sc
)
4096 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
4097 struct isl_sched_graph graph
= { 0 };
4098 isl_schedule
*sched
;
4099 isl_schedule_node
*node
;
4100 struct isl_extract_edge_data data
;
4101 enum isl_edge_type i
;
4103 sc
= isl_schedule_constraints_align_params(sc
);
4107 graph
.n
= isl_union_set_n_set(sc
->domain
);
4109 isl_union_set
*domain
= isl_union_set_copy(sc
->domain
);
4110 sched
= isl_schedule_from_domain(domain
);
4113 if (graph_alloc(ctx
, &graph
, graph
.n
,
4114 isl_schedule_constraints_n_map(sc
)) < 0)
4116 if (compute_max_row(&graph
, sc
) < 0)
4120 if (isl_union_set_foreach_set(sc
->domain
, &extract_node
, &graph
) < 0)
4122 if (graph_init_table(ctx
, &graph
) < 0)
4124 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
4125 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
4126 if (graph_init_edge_tables(ctx
, &graph
) < 0)
4129 data
.graph
= &graph
;
4130 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
4132 if (isl_union_map_foreach_map(sc
->constraint
[i
],
4133 &extract_edge
, &data
) < 0)
4137 node
= isl_schedule_node_from_domain(isl_union_set_copy(sc
->domain
));
4138 node
= isl_schedule_node_child(node
, 0);
4139 node
= compute_schedule(node
, &graph
);
4140 sched
= isl_schedule_node_get_schedule(node
);
4141 isl_schedule_node_free(node
);
4144 graph_free(ctx
, &graph
);
4145 isl_schedule_constraints_free(sc
);
4149 graph_free(ctx
, &graph
);
4150 isl_schedule_constraints_free(sc
);
4154 /* Compute a schedule for the given union of domains that respects
4155 * all the validity dependences and minimizes
4156 * the dependence distances over the proximity dependences.
4158 * This function is kept for backward compatibility.
4160 __isl_give isl_schedule
*isl_union_set_compute_schedule(
4161 __isl_take isl_union_set
*domain
,
4162 __isl_take isl_union_map
*validity
,
4163 __isl_take isl_union_map
*proximity
)
4165 isl_schedule_constraints
*sc
;
4167 sc
= isl_schedule_constraints_on_domain(domain
);
4168 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
4169 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
4171 return isl_schedule_constraints_compute_schedule(sc
);