2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <isl_ctx_private.h>
15 #include <isl_map_private.h>
16 #include <isl_space_private.h>
17 #include <isl_aff_private.h>
19 #include <isl/constraint.h>
20 #include <isl/schedule.h>
21 #include <isl_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_schedule_private.h>
30 #include <isl_options_private.h>
31 #include <isl_tarjan.h>
32 #include <isl_morph.h>
35 * The scheduling algorithm implemented in this file was inspired by
36 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
37 * Parallelization and Locality Optimization in the Polyhedral Model".
41 isl_edge_validity
= 0,
42 isl_edge_first
= isl_edge_validity
,
45 isl_edge_conditional_validity
,
47 isl_edge_last
= isl_edge_proximity
50 /* The constraints that need to be satisfied by a schedule on "domain".
52 * "validity" constraints map domain elements i to domain elements
53 * that should be scheduled after i. (Hard constraint)
54 * "proximity" constraints map domain elements i to domains elements
55 * that should be scheduled as early as possible after i (or before i).
58 * "condition" and "conditional_validity" constraints map possibly "tagged"
59 * domain elements i -> s to "tagged" domain elements j -> t.
60 * The elements of the "conditional_validity" constraints, but without the
61 * tags (i.e., the elements i -> j) are treated as validity constraints,
62 * except that during the construction of a tilable band,
63 * the elements of the "conditional_validity" constraints may be violated
64 * provided that all adjacent elements of the "condition" constraints
65 * are local within the band.
66 * A dependence is local within a band if domain and range are mapped
67 * to the same schedule point by the band.
69 struct isl_schedule_constraints
{
70 isl_union_set
*domain
;
72 isl_union_map
*constraint
[isl_edge_last
+ 1];
75 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
76 __isl_keep isl_schedule_constraints
*sc
)
79 isl_schedule_constraints
*sc_copy
;
82 ctx
= isl_union_set_get_ctx(sc
->domain
);
83 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
87 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
89 return isl_schedule_constraints_free(sc_copy
);
91 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
92 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
93 if (!sc_copy
->constraint
[i
])
94 return isl_schedule_constraints_free(sc_copy
);
101 /* Construct an isl_schedule_constraints object for computing a schedule
102 * on "domain". The initial object does not impose any constraints.
104 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
105 __isl_take isl_union_set
*domain
)
109 isl_schedule_constraints
*sc
;
110 isl_union_map
*empty
;
111 enum isl_edge_type i
;
116 ctx
= isl_union_set_get_ctx(domain
);
117 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
121 space
= isl_union_set_get_space(domain
);
123 empty
= isl_union_map_empty(space
);
124 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
125 sc
->constraint
[i
] = isl_union_map_copy(empty
);
126 if (!sc
->constraint
[i
])
127 sc
->domain
= isl_union_set_free(sc
->domain
);
129 isl_union_map_free(empty
);
132 return isl_schedule_constraints_free(sc
);
136 isl_union_set_free(domain
);
140 /* Replace the validity constraints of "sc" by "validity".
142 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
143 __isl_take isl_schedule_constraints
*sc
,
144 __isl_take isl_union_map
*validity
)
146 if (!sc
|| !validity
)
149 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
150 sc
->constraint
[isl_edge_validity
] = validity
;
154 isl_schedule_constraints_free(sc
);
155 isl_union_map_free(validity
);
159 /* Replace the coincidence constraints of "sc" by "coincidence".
161 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
162 __isl_take isl_schedule_constraints
*sc
,
163 __isl_take isl_union_map
*coincidence
)
165 if (!sc
|| !coincidence
)
168 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
169 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
173 isl_schedule_constraints_free(sc
);
174 isl_union_map_free(coincidence
);
178 /* Replace the proximity constraints of "sc" by "proximity".
180 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
181 __isl_take isl_schedule_constraints
*sc
,
182 __isl_take isl_union_map
*proximity
)
184 if (!sc
|| !proximity
)
187 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
188 sc
->constraint
[isl_edge_proximity
] = proximity
;
192 isl_schedule_constraints_free(sc
);
193 isl_union_map_free(proximity
);
197 /* Replace the conditional validity constraints of "sc" by "condition"
200 __isl_give isl_schedule_constraints
*
201 isl_schedule_constraints_set_conditional_validity(
202 __isl_take isl_schedule_constraints
*sc
,
203 __isl_take isl_union_map
*condition
,
204 __isl_take isl_union_map
*validity
)
206 if (!sc
|| !condition
|| !validity
)
209 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
210 sc
->constraint
[isl_edge_condition
] = condition
;
211 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
212 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
216 isl_schedule_constraints_free(sc
);
217 isl_union_map_free(condition
);
218 isl_union_map_free(validity
);
222 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
223 __isl_take isl_schedule_constraints
*sc
)
225 enum isl_edge_type i
;
230 isl_union_set_free(sc
->domain
);
231 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
232 isl_union_map_free(sc
->constraint
[i
]);
239 isl_ctx
*isl_schedule_constraints_get_ctx(
240 __isl_keep isl_schedule_constraints
*sc
)
242 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
245 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
250 fprintf(stderr
, "domain: ");
251 isl_union_set_dump(sc
->domain
);
252 fprintf(stderr
, "validity: ");
253 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
254 fprintf(stderr
, "proximity: ");
255 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
256 fprintf(stderr
, "coincidence: ");
257 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
258 fprintf(stderr
, "condition: ");
259 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
260 fprintf(stderr
, "conditional_validity: ");
261 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
264 /* Align the parameters of the fields of "sc".
266 static __isl_give isl_schedule_constraints
*
267 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
270 enum isl_edge_type i
;
275 space
= isl_union_set_get_space(sc
->domain
);
276 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
277 space
= isl_space_align_params(space
,
278 isl_union_map_get_space(sc
->constraint
[i
]));
280 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
281 sc
->constraint
[i
] = isl_union_map_align_params(
282 sc
->constraint
[i
], isl_space_copy(space
));
283 if (!sc
->constraint
[i
])
284 space
= isl_space_free(space
);
286 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
288 return isl_schedule_constraints_free(sc
);
293 /* Return the total number of isl_maps in the constraints of "sc".
295 static __isl_give
int isl_schedule_constraints_n_map(
296 __isl_keep isl_schedule_constraints
*sc
)
298 enum isl_edge_type i
;
301 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
302 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
307 /* Internal information about a node that is used during the construction
309 * space represents the space in which the domain lives
310 * sched is a matrix representation of the schedule being constructed
311 * for this node; if compressed is set, then this schedule is
312 * defined over the compressed domain space
313 * sched_map is an isl_map representation of the same (partial) schedule
314 * sched_map may be NULL; if compressed is set, then this map
315 * is defined over the uncompressed domain space
316 * rank is the number of linearly independent rows in the linear part
318 * the columns of cmap represent a change of basis for the schedule
319 * coefficients; the first rank columns span the linear part of
321 * cinv is the inverse of cmap.
322 * start is the first variable in the LP problem in the sequences that
323 * represents the schedule coefficients of this node
324 * nvar is the dimension of the domain
325 * nparam is the number of parameters or 0 if we are not constructing
326 * a parametric schedule
328 * If compressed is set, then hull represents the constraints
329 * that were used to derive the compression, while compress and
330 * decompress map the original space to the compressed space and
333 * scc is the index of SCC (or WCC) this node belongs to
335 * band contains the band index for each of the rows of the schedule.
336 * band_id is used to differentiate between separate bands at the same
337 * level within the same parent band, i.e., bands that are separated
338 * by the parent band or bands that are independent of each other.
339 * coincident contains a boolean for each of the rows of the schedule,
340 * indicating whether the corresponding scheduling dimension satisfies
341 * the coincidence constraints in the sense that the corresponding
342 * dependence distances are zero.
344 struct isl_sched_node
{
348 isl_multi_aff
*compress
;
349 isl_multi_aff
*decompress
;
366 static int node_has_space(const void *entry
, const void *val
)
368 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
369 isl_space
*dim
= (isl_space
*)val
;
371 return isl_space_is_equal(node
->space
, dim
);
374 /* An edge in the dependence graph. An edge may be used to
375 * ensure validity of the generated schedule, to minimize the dependence
378 * map is the dependence relation, with i -> j in the map if j depends on i
379 * tagged_condition and tagged_validity contain the union of all tagged
380 * condition or conditional validity dependence relations that
381 * specialize the dependence relation "map"; that is,
382 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
383 * or "tagged_validity", then i -> j is an element of "map".
384 * If these fields are NULL, then they represent the empty relation.
385 * src is the source node
386 * dst is the sink node
387 * validity is set if the edge is used to ensure correctness
388 * coincidence is used to enforce zero dependence distances
389 * proximity is set if the edge is used to minimize dependence distances
390 * condition is set if the edge represents a condition
391 * for a conditional validity schedule constraint
392 * local can only be set for condition edges and indicates that
393 * the dependence distance over the edge should be zero
394 * conditional_validity is set if the edge is used to conditionally
397 * For validity edges, start and end mark the sequence of inequality
398 * constraints in the LP problem that encode the validity constraint
399 * corresponding to this edge.
401 struct isl_sched_edge
{
403 isl_union_map
*tagged_condition
;
404 isl_union_map
*tagged_validity
;
406 struct isl_sched_node
*src
;
407 struct isl_sched_node
*dst
;
409 unsigned validity
: 1;
410 unsigned coincidence
: 1;
411 unsigned proximity
: 1;
413 unsigned condition
: 1;
414 unsigned conditional_validity
: 1;
420 /* Internal information about the dependence graph used during
421 * the construction of the schedule.
423 * intra_hmap is a cache, mapping dependence relations to their dual,
424 * for dependences from a node to itself
425 * inter_hmap is a cache, mapping dependence relations to their dual,
426 * for dependences between distinct nodes
427 * if compression is involved then the key for these maps
428 * it the original, uncompressed dependence relation, while
429 * the value is the dual of the compressed dependence relation.
431 * n is the number of nodes
432 * node is the list of nodes
433 * maxvar is the maximal number of variables over all nodes
434 * max_row is the allocated number of rows in the schedule
435 * n_row is the current (maximal) number of linearly independent
436 * rows in the node schedules
437 * n_total_row is the current number of rows in the node schedules
438 * n_band is the current number of completed bands
439 * band_start is the starting row in the node schedules of the current band
440 * root is set if this graph is the original dependence graph,
441 * without any splitting
443 * sorted contains a list of node indices sorted according to the
444 * SCC to which a node belongs
446 * n_edge is the number of edges
447 * edge is the list of edges
448 * max_edge contains the maximal number of edges of each type;
449 * in particular, it contains the number of edges in the inital graph.
450 * edge_table contains pointers into the edge array, hashed on the source
451 * and sink spaces; there is one such table for each type;
452 * a given edge may be referenced from more than one table
453 * if the corresponding relation appears in more than of the
454 * sets of dependences
456 * node_table contains pointers into the node array, hashed on the space
458 * region contains a list of variable sequences that should be non-trivial
460 * lp contains the (I)LP problem used to obtain new schedule rows
462 * src_scc and dst_scc are the source and sink SCCs of an edge with
463 * conflicting constraints
465 * scc represents the number of components
467 struct isl_sched_graph
{
468 isl_map_to_basic_set
*intra_hmap
;
469 isl_map_to_basic_set
*inter_hmap
;
471 struct isl_sched_node
*node
;
485 struct isl_sched_edge
*edge
;
487 int max_edge
[isl_edge_last
+ 1];
488 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
490 struct isl_hash_table
*node_table
;
491 struct isl_region
*region
;
501 /* Initialize node_table based on the list of nodes.
503 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
507 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
508 if (!graph
->node_table
)
511 for (i
= 0; i
< graph
->n
; ++i
) {
512 struct isl_hash_table_entry
*entry
;
515 hash
= isl_space_get_hash(graph
->node
[i
].space
);
516 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
518 graph
->node
[i
].space
, 1);
521 entry
->data
= &graph
->node
[i
];
527 /* Return a pointer to the node that lives within the given space,
528 * or NULL if there is no such node.
530 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
531 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
533 struct isl_hash_table_entry
*entry
;
536 hash
= isl_space_get_hash(dim
);
537 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
538 &node_has_space
, dim
, 0);
540 return entry
? entry
->data
: NULL
;
543 static int edge_has_src_and_dst(const void *entry
, const void *val
)
545 const struct isl_sched_edge
*edge
= entry
;
546 const struct isl_sched_edge
*temp
= val
;
548 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
551 /* Add the given edge to graph->edge_table[type].
553 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
554 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
556 struct isl_hash_table_entry
*entry
;
559 hash
= isl_hash_init();
560 hash
= isl_hash_builtin(hash
, edge
->src
);
561 hash
= isl_hash_builtin(hash
, edge
->dst
);
562 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
563 &edge_has_src_and_dst
, edge
, 1);
571 /* Allocate the edge_tables based on the maximal number of edges of
574 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
578 for (i
= 0; i
<= isl_edge_last
; ++i
) {
579 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
581 if (!graph
->edge_table
[i
])
588 /* If graph->edge_table[type] contains an edge from the given source
589 * to the given destination, then return the hash table entry of this edge.
590 * Otherwise, return NULL.
592 static struct isl_hash_table_entry
*graph_find_edge_entry(
593 struct isl_sched_graph
*graph
,
594 enum isl_edge_type type
,
595 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
597 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
599 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
601 hash
= isl_hash_init();
602 hash
= isl_hash_builtin(hash
, temp
.src
);
603 hash
= isl_hash_builtin(hash
, temp
.dst
);
604 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
605 &edge_has_src_and_dst
, &temp
, 0);
609 /* If graph->edge_table[type] contains an edge from the given source
610 * to the given destination, then return this edge.
611 * Otherwise, return NULL.
613 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
614 enum isl_edge_type type
,
615 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
617 struct isl_hash_table_entry
*entry
;
619 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
626 /* Check whether the dependence graph has an edge of the given type
627 * between the given two nodes.
629 static int graph_has_edge(struct isl_sched_graph
*graph
,
630 enum isl_edge_type type
,
631 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
633 struct isl_sched_edge
*edge
;
636 edge
= graph_find_edge(graph
, type
, src
, dst
);
640 empty
= isl_map_plain_is_empty(edge
->map
);
647 /* Look for any edge with the same src, dst and map fields as "model".
649 * Return the matching edge if one can be found.
650 * Return "model" if no matching edge is found.
651 * Return NULL on error.
653 static struct isl_sched_edge
*graph_find_matching_edge(
654 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
656 enum isl_edge_type i
;
657 struct isl_sched_edge
*edge
;
659 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
662 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
665 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
675 /* Remove the given edge from all the edge_tables that refer to it.
677 static void graph_remove_edge(struct isl_sched_graph
*graph
,
678 struct isl_sched_edge
*edge
)
680 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
681 enum isl_edge_type i
;
683 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
684 struct isl_hash_table_entry
*entry
;
686 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
689 if (entry
->data
!= edge
)
691 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
695 /* Check whether the dependence graph has any edge
696 * between the given two nodes.
698 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
699 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
701 enum isl_edge_type i
;
704 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
705 r
= graph_has_edge(graph
, i
, src
, dst
);
713 /* Check whether the dependence graph has a validity edge
714 * between the given two nodes.
716 * Conditional validity edges are essentially validity edges that
717 * can be ignored if the corresponding condition edges are iteration private.
718 * Here, we are only checking for the presence of validity
719 * edges, so we need to consider the conditional validity edges too.
720 * In particular, this function is used during the detection
721 * of strongly connected components and we cannot ignore
722 * conditional validity edges during this detection.
724 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
725 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
729 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
733 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
736 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
737 int n_node
, int n_edge
)
742 graph
->n_edge
= n_edge
;
743 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
744 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
745 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
746 graph
->edge
= isl_calloc_array(ctx
,
747 struct isl_sched_edge
, graph
->n_edge
);
749 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
750 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
752 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
756 for(i
= 0; i
< graph
->n
; ++i
)
757 graph
->sorted
[i
] = i
;
762 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
766 isl_map_to_basic_set_free(graph
->intra_hmap
);
767 isl_map_to_basic_set_free(graph
->inter_hmap
);
770 for (i
= 0; i
< graph
->n
; ++i
) {
771 isl_space_free(graph
->node
[i
].space
);
772 isl_set_free(graph
->node
[i
].hull
);
773 isl_multi_aff_free(graph
->node
[i
].compress
);
774 isl_multi_aff_free(graph
->node
[i
].decompress
);
775 isl_mat_free(graph
->node
[i
].sched
);
776 isl_map_free(graph
->node
[i
].sched_map
);
777 isl_mat_free(graph
->node
[i
].cmap
);
778 isl_mat_free(graph
->node
[i
].cinv
);
780 free(graph
->node
[i
].band
);
781 free(graph
->node
[i
].band_id
);
782 free(graph
->node
[i
].coincident
);
788 for (i
= 0; i
< graph
->n_edge
; ++i
) {
789 isl_map_free(graph
->edge
[i
].map
);
790 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
791 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
795 for (i
= 0; i
<= isl_edge_last
; ++i
)
796 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
797 isl_hash_table_free(ctx
, graph
->node_table
);
798 isl_basic_set_free(graph
->lp
);
801 /* For each "set" on which this function is called, increment
802 * graph->n by one and update graph->maxvar.
804 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
806 struct isl_sched_graph
*graph
= user
;
807 int nvar
= isl_set_dim(set
, isl_dim_set
);
810 if (nvar
> graph
->maxvar
)
811 graph
->maxvar
= nvar
;
818 /* Add the number of basic maps in "map" to *n.
820 static int add_n_basic_map(__isl_take isl_map
*map
, void *user
)
824 *n
+= isl_map_n_basic_map(map
);
830 /* Compute the number of rows that should be allocated for the schedule.
831 * The graph can be split at most "n - 1" times, there can be at most
832 * one row for each dimension in the iteration domains plus two rows
833 * for each basic map in the dependences (in particular,
834 * we usually have one row, but it may be split by split_scaled),
835 * and there can be one extra row for ordering the statements.
836 * Note that if we have actually split "n - 1" times, then no ordering
837 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
838 * It is also practically impossible to exhaust both the number of dependences
839 * 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
= graph
->n
+ 2 * 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
)
902 int *band
, *band_id
, *coincident
;
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 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
918 graph
->node
[graph
->n
].band
= band
;
919 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
920 graph
->node
[graph
->n
].band_id
= band_id
;
921 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
922 graph
->node
[graph
->n
].coincident
= coincident
;
923 graph
->node
[graph
->n
].compressed
= compressed
;
924 graph
->node
[graph
->n
].hull
= hull
;
925 graph
->node
[graph
->n
].compress
= compress
;
926 graph
->node
[graph
->n
].decompress
= decompress
;
929 if (!space
|| !sched
||
930 (graph
->max_row
&& (!band
|| !band_id
|| !coincident
)))
932 if (compressed
&& (!hull
|| !compress
|| !decompress
))
938 /* Add a new node to the graph representing the given set.
940 * If any of the set variables is defined by an equality, then
941 * we perform variable compression such that we can perform
942 * the scheduling on the compressed domain.
944 static int extract_node(__isl_take isl_set
*set
, void *user
)
952 isl_multi_aff
*compress
, *decompress
;
953 struct isl_sched_graph
*graph
= user
;
955 space
= isl_set_get_space(set
);
956 hull
= isl_set_affine_hull(set
);
957 hull
= isl_basic_set_remove_divs(hull
);
958 nvar
= isl_space_dim(space
, isl_dim_set
);
959 has_equality
= has_any_defining_equality(hull
);
961 if (has_equality
< 0)
964 isl_basic_set_free(hull
);
965 return add_node(graph
, space
, nvar
, 0, NULL
, NULL
, NULL
);
968 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
969 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
970 compress
= isl_morph_get_var_multi_aff(morph
);
971 morph
= isl_morph_inverse(morph
);
972 decompress
= isl_morph_get_var_multi_aff(morph
);
973 isl_morph_free(morph
);
975 hull_set
= isl_set_from_basic_set(hull
);
976 return add_node(graph
, space
, nvar
, 1, hull_set
, compress
, decompress
);
978 isl_basic_set_free(hull
);
979 isl_space_free(space
);
983 struct isl_extract_edge_data
{
984 enum isl_edge_type type
;
985 struct isl_sched_graph
*graph
;
988 /* Merge edge2 into edge1, freeing the contents of edge2.
989 * "type" is the type of the schedule constraint from which edge2 was
991 * Return 0 on success and -1 on failure.
993 * edge1 and edge2 are assumed to have the same value for the map field.
995 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
996 struct isl_sched_edge
*edge2
)
998 edge1
->validity
|= edge2
->validity
;
999 edge1
->coincidence
|= edge2
->coincidence
;
1000 edge1
->proximity
|= edge2
->proximity
;
1001 edge1
->condition
|= edge2
->condition
;
1002 edge1
->conditional_validity
|= edge2
->conditional_validity
;
1003 isl_map_free(edge2
->map
);
1005 if (type
== isl_edge_condition
) {
1006 if (!edge1
->tagged_condition
)
1007 edge1
->tagged_condition
= edge2
->tagged_condition
;
1009 edge1
->tagged_condition
=
1010 isl_union_map_union(edge1
->tagged_condition
,
1011 edge2
->tagged_condition
);
1014 if (type
== isl_edge_conditional_validity
) {
1015 if (!edge1
->tagged_validity
)
1016 edge1
->tagged_validity
= edge2
->tagged_validity
;
1018 edge1
->tagged_validity
=
1019 isl_union_map_union(edge1
->tagged_validity
,
1020 edge2
->tagged_validity
);
1023 if (type
== isl_edge_condition
&& !edge1
->tagged_condition
)
1025 if (type
== isl_edge_conditional_validity
&& !edge1
->tagged_validity
)
1031 /* Insert dummy tags in domain and range of "map".
1033 * In particular, if "map" is of the form
1039 * [A -> dummy_tag] -> [B -> dummy_tag]
1041 * where the dummy_tags are identical and equal to any dummy tags
1042 * introduced by any other call to this function.
1044 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1050 isl_set
*domain
, *range
;
1052 ctx
= isl_map_get_ctx(map
);
1054 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1055 space
= isl_space_params(isl_map_get_space(map
));
1056 space
= isl_space_set_from_params(space
);
1057 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1058 space
= isl_space_map_from_set(space
);
1060 domain
= isl_map_wrap(map
);
1061 range
= isl_map_wrap(isl_map_universe(space
));
1062 map
= isl_map_from_domain_and_range(domain
, range
);
1063 map
= isl_map_zip(map
);
1068 /* Given that at least one of "src" or "dst" is compressed, return
1069 * a map between the spaces of these nodes restricted to the affine
1070 * hull that was used in the compression.
1072 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1073 struct isl_sched_node
*dst
)
1077 if (src
->compressed
)
1078 dom
= isl_set_copy(src
->hull
);
1080 dom
= isl_set_universe(isl_space_copy(src
->space
));
1081 if (dst
->compressed
)
1082 ran
= isl_set_copy(dst
->hull
);
1084 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1086 return isl_map_from_domain_and_range(dom
, ran
);
1089 /* Intersect the domains of the nested relations in domain and range
1090 * of "tagged" with "map".
1092 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1093 __isl_keep isl_map
*map
)
1097 tagged
= isl_map_zip(tagged
);
1098 set
= isl_map_wrap(isl_map_copy(map
));
1099 tagged
= isl_map_intersect_domain(tagged
, set
);
1100 tagged
= isl_map_zip(tagged
);
1104 /* Add a new edge to the graph based on the given map
1105 * and add it to data->graph->edge_table[data->type].
1106 * If a dependence relation of a given type happens to be identical
1107 * to one of the dependence relations of a type that was added before,
1108 * then we don't create a new edge, but instead mark the original edge
1109 * as also representing a dependence of the current type.
1111 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1112 * may be specified as "tagged" dependence relations. That is, "map"
1113 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1114 * the dependence on iterations and a and b are tags.
1115 * edge->map is set to the relation containing the elements i -> j,
1116 * while edge->tagged_condition and edge->tagged_validity contain
1117 * the union of all the "map" relations
1118 * for which extract_edge is called that result in the same edge->map.
1120 * If the source or the destination node is compressed, then
1121 * intersect both "map" and "tagged" with the constraints that
1122 * were used to construct the compression.
1123 * This ensures that there are no schedule constraints defined
1124 * outside of these domains, while the scheduler no longer has
1125 * any control over those outside parts.
1127 static int extract_edge(__isl_take isl_map
*map
, void *user
)
1129 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1130 struct isl_extract_edge_data
*data
= user
;
1131 struct isl_sched_graph
*graph
= data
->graph
;
1132 struct isl_sched_node
*src
, *dst
;
1134 struct isl_sched_edge
*edge
;
1135 isl_map
*tagged
= NULL
;
1137 if (data
->type
== isl_edge_condition
||
1138 data
->type
== isl_edge_conditional_validity
) {
1139 if (isl_map_can_zip(map
)) {
1140 tagged
= isl_map_copy(map
);
1141 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1143 tagged
= insert_dummy_tags(isl_map_copy(map
));
1147 dim
= isl_space_domain(isl_map_get_space(map
));
1148 src
= graph_find_node(ctx
, graph
, dim
);
1149 isl_space_free(dim
);
1150 dim
= isl_space_range(isl_map_get_space(map
));
1151 dst
= graph_find_node(ctx
, graph
, dim
);
1152 isl_space_free(dim
);
1156 isl_map_free(tagged
);
1160 if (src
->compressed
|| dst
->compressed
) {
1162 hull
= extract_hull(src
, dst
);
1164 tagged
= map_intersect_domains(tagged
, hull
);
1165 map
= isl_map_intersect(map
, hull
);
1168 graph
->edge
[graph
->n_edge
].src
= src
;
1169 graph
->edge
[graph
->n_edge
].dst
= dst
;
1170 graph
->edge
[graph
->n_edge
].map
= map
;
1171 graph
->edge
[graph
->n_edge
].validity
= 0;
1172 graph
->edge
[graph
->n_edge
].coincidence
= 0;
1173 graph
->edge
[graph
->n_edge
].proximity
= 0;
1174 graph
->edge
[graph
->n_edge
].condition
= 0;
1175 graph
->edge
[graph
->n_edge
].local
= 0;
1176 graph
->edge
[graph
->n_edge
].conditional_validity
= 0;
1177 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1178 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1179 if (data
->type
== isl_edge_validity
)
1180 graph
->edge
[graph
->n_edge
].validity
= 1;
1181 if (data
->type
== isl_edge_coincidence
)
1182 graph
->edge
[graph
->n_edge
].coincidence
= 1;
1183 if (data
->type
== isl_edge_proximity
)
1184 graph
->edge
[graph
->n_edge
].proximity
= 1;
1185 if (data
->type
== isl_edge_condition
) {
1186 graph
->edge
[graph
->n_edge
].condition
= 1;
1187 graph
->edge
[graph
->n_edge
].tagged_condition
=
1188 isl_union_map_from_map(tagged
);
1190 if (data
->type
== isl_edge_conditional_validity
) {
1191 graph
->edge
[graph
->n_edge
].conditional_validity
= 1;
1192 graph
->edge
[graph
->n_edge
].tagged_validity
=
1193 isl_union_map_from_map(tagged
);
1196 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1201 if (edge
== &graph
->edge
[graph
->n_edge
])
1202 return graph_edge_table_add(ctx
, graph
, data
->type
,
1203 &graph
->edge
[graph
->n_edge
++]);
1205 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1208 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1211 /* Check whether there is any dependence from node[j] to node[i]
1212 * or from node[i] to node[j].
1214 static int node_follows_weak(int i
, int j
, void *user
)
1217 struct isl_sched_graph
*graph
= user
;
1219 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1222 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1225 /* Check whether there is a (conditional) validity dependence from node[j]
1226 * to node[i], forcing node[i] to follow node[j].
1228 static int node_follows_strong(int i
, int j
, void *user
)
1230 struct isl_sched_graph
*graph
= user
;
1232 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1235 /* Use Tarjan's algorithm for computing the strongly connected components
1236 * in the dependence graph (only validity edges).
1237 * If weak is set, we consider the graph to be undirected and
1238 * we effectively compute the (weakly) connected components.
1239 * Additionally, we also consider other edges when weak is set.
1241 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
1244 struct isl_tarjan_graph
*g
= NULL
;
1246 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
1247 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
1255 while (g
->order
[i
] != -1) {
1256 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1264 isl_tarjan_graph_free(g
);
1269 /* Apply Tarjan's algorithm to detect the strongly connected components
1270 * in the dependence graph.
1272 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1274 return detect_ccs(ctx
, graph
, 0);
1277 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1278 * in the dependence graph.
1280 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1282 return detect_ccs(ctx
, graph
, 1);
1285 static int cmp_scc(const void *a
, const void *b
, void *data
)
1287 struct isl_sched_graph
*graph
= data
;
1291 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1294 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1296 static int sort_sccs(struct isl_sched_graph
*graph
)
1298 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1301 /* Given a dependence relation R from "node" to itself,
1302 * construct the set of coefficients of valid constraints for elements
1303 * in that dependence relation.
1304 * In particular, the result contains tuples of coefficients
1305 * c_0, c_n, c_x such that
1307 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1311 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1313 * We choose here to compute the dual of delta R.
1314 * Alternatively, we could have computed the dual of R, resulting
1315 * in a set of tuples c_0, c_n, c_x, c_y, and then
1316 * plugged in (c_0, c_n, c_x, -c_x).
1318 * If "node" has been compressed, then the dependence relation
1319 * is also compressed before the set of coefficients is computed.
1321 static __isl_give isl_basic_set
*intra_coefficients(
1322 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1323 __isl_take isl_map
*map
)
1327 isl_basic_set
*coef
;
1329 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1330 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1332 key
= isl_map_copy(map
);
1333 if (node
->compressed
) {
1334 map
= isl_map_preimage_domain_multi_aff(map
,
1335 isl_multi_aff_copy(node
->decompress
));
1336 map
= isl_map_preimage_range_multi_aff(map
,
1337 isl_multi_aff_copy(node
->decompress
));
1339 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1340 coef
= isl_set_coefficients(delta
);
1341 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1342 isl_basic_set_copy(coef
));
1347 /* Given a dependence relation R, construct the set of coefficients
1348 * of valid constraints for elements in that dependence relation.
1349 * In particular, the result contains tuples of coefficients
1350 * c_0, c_n, c_x, c_y such that
1352 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1354 * If the source or destination nodes of "edge" have been compressed,
1355 * then the dependence relation is also compressed before
1356 * the set of coefficients is computed.
1358 static __isl_give isl_basic_set
*inter_coefficients(
1359 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1360 __isl_take isl_map
*map
)
1364 isl_basic_set
*coef
;
1366 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1367 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1369 key
= isl_map_copy(map
);
1370 if (edge
->src
->compressed
)
1371 map
= isl_map_preimage_domain_multi_aff(map
,
1372 isl_multi_aff_copy(edge
->src
->decompress
));
1373 if (edge
->dst
->compressed
)
1374 map
= isl_map_preimage_range_multi_aff(map
,
1375 isl_multi_aff_copy(edge
->dst
->decompress
));
1376 set
= isl_map_wrap(isl_map_remove_divs(map
));
1377 coef
= isl_set_coefficients(set
);
1378 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1379 isl_basic_set_copy(coef
));
1384 /* Add constraints to graph->lp that force validity for the given
1385 * dependence from a node i to itself.
1386 * That is, add constraints that enforce
1388 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1389 * = c_i_x (y - x) >= 0
1391 * for each (x,y) in R.
1392 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1393 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1394 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1395 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1397 * Actually, we do not construct constraints for the c_i_x themselves,
1398 * but for the coefficients of c_i_x written as a linear combination
1399 * of the columns in node->cmap.
1401 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1402 struct isl_sched_edge
*edge
)
1405 isl_map
*map
= isl_map_copy(edge
->map
);
1406 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1408 isl_dim_map
*dim_map
;
1409 isl_basic_set
*coef
;
1410 struct isl_sched_node
*node
= edge
->src
;
1412 coef
= intra_coefficients(graph
, node
, map
);
1414 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1416 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1417 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1421 total
= isl_basic_set_total_dim(graph
->lp
);
1422 dim_map
= isl_dim_map_alloc(ctx
, total
);
1423 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1424 isl_space_dim(dim
, isl_dim_set
), 1,
1426 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1427 isl_space_dim(dim
, isl_dim_set
), 1,
1429 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1430 coef
->n_eq
, coef
->n_ineq
);
1431 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1433 isl_space_free(dim
);
1437 isl_space_free(dim
);
1441 /* Add constraints to graph->lp that force validity for the given
1442 * dependence from node i to node j.
1443 * That is, add constraints that enforce
1445 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1447 * for each (x,y) in R.
1448 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1449 * of valid constraints for R and then plug in
1450 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1451 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1452 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1453 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1455 * Actually, we do not construct constraints for the c_*_x themselves,
1456 * but for the coefficients of c_*_x written as a linear combination
1457 * of the columns in node->cmap.
1459 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1460 struct isl_sched_edge
*edge
)
1463 isl_map
*map
= isl_map_copy(edge
->map
);
1464 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1466 isl_dim_map
*dim_map
;
1467 isl_basic_set
*coef
;
1468 struct isl_sched_node
*src
= edge
->src
;
1469 struct isl_sched_node
*dst
= edge
->dst
;
1471 coef
= inter_coefficients(graph
, edge
, map
);
1473 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1475 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1476 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1477 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1478 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1479 isl_mat_copy(dst
->cmap
));
1483 total
= isl_basic_set_total_dim(graph
->lp
);
1484 dim_map
= isl_dim_map_alloc(ctx
, total
);
1486 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1487 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1488 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1489 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1490 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1492 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1493 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1496 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1497 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1498 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1499 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1500 isl_space_dim(dim
, isl_dim_set
), 1,
1502 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1503 isl_space_dim(dim
, isl_dim_set
), 1,
1506 edge
->start
= graph
->lp
->n_ineq
;
1507 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1508 coef
->n_eq
, coef
->n_ineq
);
1509 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1513 isl_space_free(dim
);
1514 edge
->end
= graph
->lp
->n_ineq
;
1518 isl_space_free(dim
);
1522 /* Add constraints to graph->lp that bound the dependence distance for the given
1523 * dependence from a node i to itself.
1524 * If s = 1, we add the constraint
1526 * c_i_x (y - x) <= m_0 + m_n n
1530 * -c_i_x (y - x) + m_0 + m_n n >= 0
1532 * for each (x,y) in R.
1533 * If s = -1, we add the constraint
1535 * -c_i_x (y - x) <= m_0 + m_n n
1539 * c_i_x (y - x) + m_0 + m_n n >= 0
1541 * for each (x,y) in R.
1542 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1543 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1544 * with each coefficient (except m_0) represented as a pair of non-negative
1547 * Actually, we do not construct constraints for the c_i_x themselves,
1548 * but for the coefficients of c_i_x written as a linear combination
1549 * of the columns in node->cmap.
1552 * If "local" is set, then we add constraints
1554 * c_i_x (y - x) <= 0
1558 * -c_i_x (y - x) <= 0
1560 * instead, forcing the dependence distance to be (less than or) equal to 0.
1561 * That is, we plug in (0, 0, -s * c_i_x),
1562 * Note that dependences marked local are treated as validity constraints
1563 * by add_all_validity_constraints and therefore also have
1564 * their distances bounded by 0 from below.
1566 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1567 struct isl_sched_edge
*edge
, int s
, int local
)
1571 isl_map
*map
= isl_map_copy(edge
->map
);
1572 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1574 isl_dim_map
*dim_map
;
1575 isl_basic_set
*coef
;
1576 struct isl_sched_node
*node
= edge
->src
;
1578 coef
= intra_coefficients(graph
, node
, map
);
1580 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1582 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1583 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1587 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1588 total
= isl_basic_set_total_dim(graph
->lp
);
1589 dim_map
= isl_dim_map_alloc(ctx
, total
);
1592 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1593 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1594 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1596 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1597 isl_space_dim(dim
, isl_dim_set
), 1,
1599 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1600 isl_space_dim(dim
, isl_dim_set
), 1,
1602 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1603 coef
->n_eq
, coef
->n_ineq
);
1604 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1606 isl_space_free(dim
);
1610 isl_space_free(dim
);
1614 /* Add constraints to graph->lp that bound the dependence distance for the given
1615 * dependence from node i to node j.
1616 * If s = 1, we add the constraint
1618 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1623 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1626 * for each (x,y) in R.
1627 * If s = -1, we add the constraint
1629 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1634 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1637 * for each (x,y) in R.
1638 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1639 * of valid constraints for R and then plug in
1640 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1642 * with each coefficient (except m_0, c_j_0 and c_i_0)
1643 * represented as a pair of non-negative coefficients.
1645 * Actually, we do not construct constraints for the c_*_x themselves,
1646 * but for the coefficients of c_*_x written as a linear combination
1647 * of the columns in node->cmap.
1650 * If "local" is set, then we add constraints
1652 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1656 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1658 * instead, forcing the dependence distance to be (less than or) equal to 0.
1659 * That is, we plug in
1660 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1661 * Note that dependences marked local are treated as validity constraints
1662 * by add_all_validity_constraints and therefore also have
1663 * their distances bounded by 0 from below.
1665 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1666 struct isl_sched_edge
*edge
, int s
, int local
)
1670 isl_map
*map
= isl_map_copy(edge
->map
);
1671 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1673 isl_dim_map
*dim_map
;
1674 isl_basic_set
*coef
;
1675 struct isl_sched_node
*src
= edge
->src
;
1676 struct isl_sched_node
*dst
= edge
->dst
;
1678 coef
= inter_coefficients(graph
, edge
, map
);
1680 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1682 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1683 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1684 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1685 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1686 isl_mat_copy(dst
->cmap
));
1690 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1691 total
= isl_basic_set_total_dim(graph
->lp
);
1692 dim_map
= isl_dim_map_alloc(ctx
, total
);
1695 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1696 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1697 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1700 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1701 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1702 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1703 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1704 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1706 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1707 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1710 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1711 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1712 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1713 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1714 isl_space_dim(dim
, isl_dim_set
), 1,
1716 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1717 isl_space_dim(dim
, isl_dim_set
), 1,
1720 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1721 coef
->n_eq
, coef
->n_ineq
);
1722 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1724 isl_space_free(dim
);
1728 isl_space_free(dim
);
1732 /* Add all validity constraints to graph->lp.
1734 * An edge that is forced to be local needs to have its dependence
1735 * distances equal to zero. We take care of bounding them by 0 from below
1736 * here. add_all_proximity_constraints takes care of bounding them by 0
1739 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1740 * Otherwise, we ignore them.
1742 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1743 int use_coincidence
)
1747 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1748 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1751 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1752 if (!edge
->validity
&& !local
)
1754 if (edge
->src
!= edge
->dst
)
1756 if (add_intra_validity_constraints(graph
, edge
) < 0)
1760 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1761 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1764 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1765 if (!edge
->validity
&& !local
)
1767 if (edge
->src
== edge
->dst
)
1769 if (add_inter_validity_constraints(graph
, edge
) < 0)
1776 /* Add constraints to graph->lp that bound the dependence distance
1777 * for all dependence relations.
1778 * If a given proximity dependence is identical to a validity
1779 * dependence, then the dependence distance is already bounded
1780 * from below (by zero), so we only need to bound the distance
1781 * from above. (This includes the case of "local" dependences
1782 * which are treated as validity dependence by add_all_validity_constraints.)
1783 * Otherwise, we need to bound the distance both from above and from below.
1785 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1786 * Otherwise, we ignore them.
1788 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
1789 int use_coincidence
)
1793 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1794 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1797 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1798 if (!edge
->proximity
&& !local
)
1800 if (edge
->src
== edge
->dst
&&
1801 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
1803 if (edge
->src
!= edge
->dst
&&
1804 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
1806 if (edge
->validity
|| local
)
1808 if (edge
->src
== edge
->dst
&&
1809 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
1811 if (edge
->src
!= edge
->dst
&&
1812 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
1819 /* Compute a basis for the rows in the linear part of the schedule
1820 * and extend this basis to a full basis. The remaining rows
1821 * can then be used to force linear independence from the rows
1824 * In particular, given the schedule rows S, we compute
1829 * with H the Hermite normal form of S. That is, all but the
1830 * first rank columns of H are zero and so each row in S is
1831 * a linear combination of the first rank rows of Q.
1832 * The matrix Q is then transposed because we will write the
1833 * coefficients of the next schedule row as a column vector s
1834 * and express this s as a linear combination s = Q c of the
1836 * Similarly, the matrix U is transposed such that we can
1837 * compute the coefficients c = U s from a schedule row s.
1839 static int node_update_cmap(struct isl_sched_node
*node
)
1842 int n_row
= isl_mat_rows(node
->sched
);
1844 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1845 1 + node
->nparam
, node
->nvar
);
1847 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1848 isl_mat_free(node
->cmap
);
1849 isl_mat_free(node
->cinv
);
1850 node
->cmap
= isl_mat_transpose(Q
);
1851 node
->cinv
= isl_mat_transpose(U
);
1852 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1855 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1860 /* How many times should we count the constraints in "edge"?
1862 * If carry is set, then we are counting the number of
1863 * (validity or conditional validity) constraints that will be added
1864 * in setup_carry_lp and we count each edge exactly once.
1866 * Otherwise, we count as follows
1867 * validity -> 1 (>= 0)
1868 * validity+proximity -> 2 (>= 0 and upper bound)
1869 * proximity -> 2 (lower and upper bound)
1870 * local(+any) -> 2 (>= 0 and <= 0)
1872 * If an edge is only marked conditional_validity then it counts
1873 * as zero since it is only checked afterwards.
1875 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1876 * Otherwise, we ignore them.
1878 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
1879 int use_coincidence
)
1881 if (carry
&& !edge
->validity
&& !edge
->conditional_validity
)
1885 if (edge
->proximity
|| edge
->local
)
1887 if (use_coincidence
&& edge
->coincidence
)
1894 /* Count the number of equality and inequality constraints
1895 * that will be added for the given map.
1897 * "use_coincidence" is set if we should take into account coincidence edges.
1899 static int count_map_constraints(struct isl_sched_graph
*graph
,
1900 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1901 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
1903 isl_basic_set
*coef
;
1904 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
1911 if (edge
->src
== edge
->dst
)
1912 coef
= intra_coefficients(graph
, edge
->src
, map
);
1914 coef
= inter_coefficients(graph
, edge
, map
);
1917 *n_eq
+= f
* coef
->n_eq
;
1918 *n_ineq
+= f
* coef
->n_ineq
;
1919 isl_basic_set_free(coef
);
1924 /* Count the number of equality and inequality constraints
1925 * that will be added to the main lp problem.
1926 * We count as follows
1927 * validity -> 1 (>= 0)
1928 * validity+proximity -> 2 (>= 0 and upper bound)
1929 * proximity -> 2 (lower and upper bound)
1930 * local(+any) -> 2 (>= 0 and <= 0)
1932 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1933 * Otherwise, we ignore them.
1935 static int count_constraints(struct isl_sched_graph
*graph
,
1936 int *n_eq
, int *n_ineq
, int use_coincidence
)
1940 *n_eq
= *n_ineq
= 0;
1941 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1942 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1943 isl_map
*map
= isl_map_copy(edge
->map
);
1945 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
1946 0, use_coincidence
) < 0)
1953 /* Count the number of constraints that will be added by
1954 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1957 * In practice, add_bound_coefficient_constraints only adds inequalities.
1959 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1960 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1964 if (ctx
->opt
->schedule_max_coefficient
== -1)
1967 for (i
= 0; i
< graph
->n
; ++i
)
1968 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1973 /* Add constraints that bound the values of the variable and parameter
1974 * coefficients of the schedule.
1976 * The maximal value of the coefficients is defined by the option
1977 * 'schedule_max_coefficient'.
1979 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1980 struct isl_sched_graph
*graph
)
1983 int max_coefficient
;
1986 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1988 if (max_coefficient
== -1)
1991 total
= isl_basic_set_total_dim(graph
->lp
);
1993 for (i
= 0; i
< graph
->n
; ++i
) {
1994 struct isl_sched_node
*node
= &graph
->node
[i
];
1995 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1997 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2000 dim
= 1 + node
->start
+ 1 + j
;
2001 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2002 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2003 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
2010 /* Construct an ILP problem for finding schedule coefficients
2011 * that result in non-negative, but small dependence distances
2012 * over all dependences.
2013 * In particular, the dependence distances over proximity edges
2014 * are bounded by m_0 + m_n n and we compute schedule coefficients
2015 * with small values (preferably zero) of m_n and m_0.
2017 * All variables of the ILP are non-negative. The actual coefficients
2018 * may be negative, so each coefficient is represented as the difference
2019 * of two non-negative variables. The negative part always appears
2020 * immediately before the positive part.
2021 * Other than that, the variables have the following order
2023 * - sum of positive and negative parts of m_n coefficients
2025 * - sum of positive and negative parts of all c_n coefficients
2026 * (unconstrained when computing non-parametric schedules)
2027 * - sum of positive and negative parts of all c_x coefficients
2028 * - positive and negative parts of m_n coefficients
2031 * - positive and negative parts of c_i_n (if parametric)
2032 * - positive and negative parts of c_i_x
2034 * The c_i_x are not represented directly, but through the columns of
2035 * node->cmap. That is, the computed values are for variable t_i_x
2036 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2038 * The constraints are those from the edges plus two or three equalities
2039 * to express the sums.
2041 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2042 * Otherwise, we ignore them.
2044 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2045 int use_coincidence
)
2055 int max_constant_term
;
2057 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
2059 parametric
= ctx
->opt
->schedule_parametric
;
2060 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2062 total
= param_pos
+ 2 * nparam
;
2063 for (i
= 0; i
< graph
->n
; ++i
) {
2064 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2065 if (node_update_cmap(node
) < 0)
2067 node
->start
= total
;
2068 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2071 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2073 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2076 dim
= isl_space_set_alloc(ctx
, 0, total
);
2077 isl_basic_set_free(graph
->lp
);
2078 n_eq
+= 2 + parametric
;
2079 if (max_constant_term
!= -1)
2082 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2084 k
= isl_basic_set_alloc_equality(graph
->lp
);
2087 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2088 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
2089 for (i
= 0; i
< 2 * nparam
; ++i
)
2090 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
2093 k
= isl_basic_set_alloc_equality(graph
->lp
);
2096 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2097 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2098 for (i
= 0; i
< graph
->n
; ++i
) {
2099 int pos
= 1 + graph
->node
[i
].start
+ 1;
2101 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2102 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2106 k
= isl_basic_set_alloc_equality(graph
->lp
);
2109 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2110 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
2111 for (i
= 0; i
< graph
->n
; ++i
) {
2112 struct isl_sched_node
*node
= &graph
->node
[i
];
2113 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2115 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2116 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2119 if (max_constant_term
!= -1)
2120 for (i
= 0; i
< graph
->n
; ++i
) {
2121 struct isl_sched_node
*node
= &graph
->node
[i
];
2122 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2125 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2126 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2127 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
2130 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2132 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2134 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2140 /* Analyze the conflicting constraint found by
2141 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2142 * constraint of one of the edges between distinct nodes, living, moreover
2143 * in distinct SCCs, then record the source and sink SCC as this may
2144 * be a good place to cut between SCCs.
2146 static int check_conflict(int con
, void *user
)
2149 struct isl_sched_graph
*graph
= user
;
2151 if (graph
->src_scc
>= 0)
2154 con
-= graph
->lp
->n_eq
;
2156 if (con
>= graph
->lp
->n_ineq
)
2159 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2160 if (!graph
->edge
[i
].validity
)
2162 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2164 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2166 if (graph
->edge
[i
].start
> con
)
2168 if (graph
->edge
[i
].end
<= con
)
2170 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2171 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2177 /* Check whether the next schedule row of the given node needs to be
2178 * non-trivial. Lower-dimensional domains may have some trivial rows,
2179 * but as soon as the number of remaining required non-trivial rows
2180 * is as large as the number or remaining rows to be computed,
2181 * all remaining rows need to be non-trivial.
2183 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2185 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2188 /* Solve the ILP problem constructed in setup_lp.
2189 * For each node such that all the remaining rows of its schedule
2190 * need to be non-trivial, we construct a non-triviality region.
2191 * This region imposes that the next row is independent of previous rows.
2192 * In particular the coefficients c_i_x are represented by t_i_x
2193 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2194 * its first columns span the rows of the previously computed part
2195 * of the schedule. The non-triviality region enforces that at least
2196 * one of the remaining components of t_i_x is non-zero, i.e.,
2197 * that the new schedule row depends on at least one of the remaining
2200 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2206 for (i
= 0; i
< graph
->n
; ++i
) {
2207 struct isl_sched_node
*node
= &graph
->node
[i
];
2208 int skip
= node
->rank
;
2209 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
2210 if (needs_row(graph
, node
))
2211 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2213 graph
->region
[i
].len
= 0;
2215 lp
= isl_basic_set_copy(graph
->lp
);
2216 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2217 graph
->region
, &check_conflict
, graph
);
2221 /* Update the schedules of all nodes based on the given solution
2222 * of the LP problem.
2223 * The new row is added to the current band.
2224 * All possibly negative coefficients are encoded as a difference
2225 * of two non-negative variables, so we need to perform the subtraction
2226 * here. Moreover, if use_cmap is set, then the solution does
2227 * not refer to the actual coefficients c_i_x, but instead to variables
2228 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2229 * In this case, we then also need to perform this multiplication
2230 * to obtain the values of c_i_x.
2232 * If coincident is set, then the caller guarantees that the new
2233 * row satisfies the coincidence constraints.
2235 static int update_schedule(struct isl_sched_graph
*graph
,
2236 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2239 isl_vec
*csol
= NULL
;
2244 isl_die(sol
->ctx
, isl_error_internal
,
2245 "no solution found", goto error
);
2246 if (graph
->n_total_row
>= graph
->max_row
)
2247 isl_die(sol
->ctx
, isl_error_internal
,
2248 "too many schedule rows", goto error
);
2250 for (i
= 0; i
< graph
->n
; ++i
) {
2251 struct isl_sched_node
*node
= &graph
->node
[i
];
2252 int pos
= node
->start
;
2253 int row
= isl_mat_rows(node
->sched
);
2256 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2260 isl_map_free(node
->sched_map
);
2261 node
->sched_map
= NULL
;
2262 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2265 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2267 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2268 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2269 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2270 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2271 for (j
= 0; j
< node
->nparam
; ++j
)
2272 node
->sched
= isl_mat_set_element(node
->sched
,
2273 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2274 for (j
= 0; j
< node
->nvar
; ++j
)
2275 isl_int_set(csol
->el
[j
],
2276 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2278 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2282 for (j
= 0; j
< node
->nvar
; ++j
)
2283 node
->sched
= isl_mat_set_element(node
->sched
,
2284 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2285 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2286 node
->coincident
[graph
->n_total_row
] = coincident
;
2292 graph
->n_total_row
++;
2301 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2302 * and return this isl_aff.
2304 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2305 struct isl_sched_node
*node
, int row
)
2313 aff
= isl_aff_zero_on_domain(ls
);
2314 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2315 aff
= isl_aff_set_constant(aff
, v
);
2316 for (j
= 0; j
< node
->nparam
; ++j
) {
2317 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2318 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2320 for (j
= 0; j
< node
->nvar
; ++j
) {
2321 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2322 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2330 /* Convert node->sched into a multi_aff and return this multi_aff.
2332 * The result is defined over the uncompressed node domain.
2334 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2335 struct isl_sched_node
*node
)
2339 isl_local_space
*ls
;
2344 nrow
= isl_mat_rows(node
->sched
);
2345 ncol
= isl_mat_cols(node
->sched
) - 1;
2346 if (node
->compressed
)
2347 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2349 space
= isl_space_copy(node
->space
);
2350 ls
= isl_local_space_from_space(isl_space_copy(space
));
2351 space
= isl_space_from_domain(space
);
2352 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
2353 ma
= isl_multi_aff_zero(space
);
2355 for (i
= 0; i
< nrow
; ++i
) {
2356 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2357 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
2360 isl_local_space_free(ls
);
2362 if (node
->compressed
)
2363 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2364 isl_multi_aff_copy(node
->compress
));
2369 /* Convert node->sched into a map and return this map.
2371 * The result is cached in node->sched_map, which needs to be released
2372 * whenever node->sched is updated.
2373 * It is defined over the uncompressed node domain.
2375 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2377 if (!node
->sched_map
) {
2380 ma
= node_extract_schedule_multi_aff(node
);
2381 node
->sched_map
= isl_map_from_multi_aff(ma
);
2384 return isl_map_copy(node
->sched_map
);
2387 /* Construct a map that can be used to update a dependence relation
2388 * based on the current schedule.
2389 * That is, construct a map expressing that source and sink
2390 * are executed within the same iteration of the current schedule.
2391 * This map can then be intersected with the dependence relation.
2392 * This is not the most efficient way, but this shouldn't be a critical
2395 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2396 struct isl_sched_node
*dst
)
2398 isl_map
*src_sched
, *dst_sched
;
2400 src_sched
= node_extract_schedule(src
);
2401 dst_sched
= node_extract_schedule(dst
);
2402 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2405 /* Intersect the domains of the nested relations in domain and range
2406 * of "umap" with "map".
2408 static __isl_give isl_union_map
*intersect_domains(
2409 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2411 isl_union_set
*uset
;
2413 umap
= isl_union_map_zip(umap
);
2414 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2415 umap
= isl_union_map_intersect_domain(umap
, uset
);
2416 umap
= isl_union_map_zip(umap
);
2420 /* Update the dependence relation of the given edge based
2421 * on the current schedule.
2422 * If the dependence is carried completely by the current schedule, then
2423 * it is removed from the edge_tables. It is kept in the list of edges
2424 * as otherwise all edge_tables would have to be recomputed.
2426 static int update_edge(struct isl_sched_graph
*graph
,
2427 struct isl_sched_edge
*edge
)
2432 id
= specializer(edge
->src
, edge
->dst
);
2433 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2437 if (edge
->tagged_condition
) {
2438 edge
->tagged_condition
=
2439 intersect_domains(edge
->tagged_condition
, id
);
2440 if (!edge
->tagged_condition
)
2443 if (edge
->tagged_validity
) {
2444 edge
->tagged_validity
=
2445 intersect_domains(edge
->tagged_validity
, id
);
2446 if (!edge
->tagged_validity
)
2450 empty
= isl_map_plain_is_empty(edge
->map
);
2454 graph_remove_edge(graph
, edge
);
2463 /* Does the domain of "umap" intersect "uset"?
2465 static int domain_intersects(__isl_keep isl_union_map
*umap
,
2466 __isl_keep isl_union_set
*uset
)
2470 umap
= isl_union_map_copy(umap
);
2471 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
2472 empty
= isl_union_map_is_empty(umap
);
2473 isl_union_map_free(umap
);
2475 return empty
< 0 ? -1 : !empty
;
2478 /* Does the range of "umap" intersect "uset"?
2480 static int range_intersects(__isl_keep isl_union_map
*umap
,
2481 __isl_keep isl_union_set
*uset
)
2485 umap
= isl_union_map_copy(umap
);
2486 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
2487 empty
= isl_union_map_is_empty(umap
);
2488 isl_union_map_free(umap
);
2490 return empty
< 0 ? -1 : !empty
;
2493 /* Are the condition dependences of "edge" local with respect to
2494 * the current schedule?
2496 * That is, are domain and range of the condition dependences mapped
2497 * to the same point?
2499 * In other words, is the condition false?
2501 static int is_condition_false(struct isl_sched_edge
*edge
)
2503 isl_union_map
*umap
;
2504 isl_map
*map
, *sched
, *test
;
2507 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
2508 if (empty
< 0 || empty
)
2511 umap
= isl_union_map_copy(edge
->tagged_condition
);
2512 umap
= isl_union_map_zip(umap
);
2513 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
2514 map
= isl_map_from_union_map(umap
);
2516 sched
= node_extract_schedule(edge
->src
);
2517 map
= isl_map_apply_domain(map
, sched
);
2518 sched
= node_extract_schedule(edge
->dst
);
2519 map
= isl_map_apply_range(map
, sched
);
2521 test
= isl_map_identity(isl_map_get_space(map
));
2522 local
= isl_map_is_subset(map
, test
);
2529 /* For each conditional validity constraint that is adjacent
2530 * to a condition with domain in condition_source or range in condition_sink,
2531 * turn it into an unconditional validity constraint.
2533 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
2534 __isl_take isl_union_set
*condition_source
,
2535 __isl_take isl_union_set
*condition_sink
)
2539 condition_source
= isl_union_set_coalesce(condition_source
);
2540 condition_sink
= isl_union_set_coalesce(condition_sink
);
2542 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2544 isl_union_map
*validity
;
2546 if (!graph
->edge
[i
].conditional_validity
)
2548 if (graph
->edge
[i
].validity
)
2551 validity
= graph
->edge
[i
].tagged_validity
;
2552 adjacent
= domain_intersects(validity
, condition_sink
);
2553 if (adjacent
>= 0 && !adjacent
)
2554 adjacent
= range_intersects(validity
, condition_source
);
2560 graph
->edge
[i
].validity
= 1;
2563 isl_union_set_free(condition_source
);
2564 isl_union_set_free(condition_sink
);
2567 isl_union_set_free(condition_source
);
2568 isl_union_set_free(condition_sink
);
2572 /* Update the dependence relations of all edges based on the current schedule
2573 * and enforce conditional validity constraints that are adjacent
2574 * to satisfied condition constraints.
2576 * First check if any of the condition constraints are satisfied
2577 * (i.e., not local to the outer schedule) and keep track of
2578 * their domain and range.
2579 * Then update all dependence relations (which removes the non-local
2581 * Finally, if any condition constraints turned out to be satisfied,
2582 * then turn all adjacent conditional validity constraints into
2583 * unconditional validity constraints.
2585 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2589 isl_union_set
*source
, *sink
;
2591 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
2592 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
2593 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2595 isl_union_set
*uset
;
2596 isl_union_map
*umap
;
2598 if (!graph
->edge
[i
].condition
)
2600 if (graph
->edge
[i
].local
)
2602 local
= is_condition_false(&graph
->edge
[i
]);
2610 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
2611 uset
= isl_union_map_domain(umap
);
2612 source
= isl_union_set_union(source
, uset
);
2614 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
2615 uset
= isl_union_map_range(umap
);
2616 sink
= isl_union_set_union(sink
, uset
);
2619 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2620 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2625 return unconditionalize_adjacent_validity(graph
, source
, sink
);
2627 isl_union_set_free(source
);
2628 isl_union_set_free(sink
);
2631 isl_union_set_free(source
);
2632 isl_union_set_free(sink
);
2636 static void next_band(struct isl_sched_graph
*graph
)
2638 graph
->band_start
= graph
->n_total_row
;
2642 /* Topologically sort statements mapped to the same schedule iteration
2643 * and add a row to the schedule corresponding to this order.
2645 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2652 if (update_edges(ctx
, graph
) < 0)
2655 if (graph
->n_edge
== 0)
2658 if (detect_sccs(ctx
, graph
) < 0)
2661 if (graph
->n_total_row
>= graph
->max_row
)
2662 isl_die(ctx
, isl_error_internal
,
2663 "too many schedule rows", return -1);
2665 for (i
= 0; i
< graph
->n
; ++i
) {
2666 struct isl_sched_node
*node
= &graph
->node
[i
];
2667 int row
= isl_mat_rows(node
->sched
);
2668 int cols
= isl_mat_cols(node
->sched
);
2670 isl_map_free(node
->sched_map
);
2671 node
->sched_map
= NULL
;
2672 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2675 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2677 for (j
= 1; j
< cols
; ++j
)
2678 node
->sched
= isl_mat_set_element_si(node
->sched
,
2680 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2683 graph
->n_total_row
++;
2689 /* Construct an isl_schedule based on the computed schedule stored
2690 * in graph and with parameters specified by dim.
2692 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
2693 __isl_take isl_space
*dim
)
2697 isl_schedule
*sched
= NULL
;
2702 ctx
= isl_space_get_ctx(dim
);
2703 sched
= isl_calloc(ctx
, struct isl_schedule
,
2704 sizeof(struct isl_schedule
) +
2705 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
2710 sched
->n
= graph
->n
;
2711 sched
->n_band
= graph
->n_band
;
2712 sched
->n_total_row
= graph
->n_total_row
;
2714 for (i
= 0; i
< sched
->n
; ++i
) {
2716 int *band_end
, *band_id
, *coincident
;
2718 sched
->node
[i
].sched
=
2719 node_extract_schedule_multi_aff(&graph
->node
[i
]);
2720 if (!sched
->node
[i
].sched
)
2723 sched
->node
[i
].n_band
= graph
->n_band
;
2724 if (graph
->n_band
== 0)
2727 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
2728 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
2729 coincident
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
2730 sched
->node
[i
].band_end
= band_end
;
2731 sched
->node
[i
].band_id
= band_id
;
2732 sched
->node
[i
].coincident
= coincident
;
2733 if (!band_end
|| !band_id
|| !coincident
)
2736 for (r
= 0; r
< graph
->n_total_row
; ++r
)
2737 coincident
[r
] = graph
->node
[i
].coincident
[r
];
2738 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
2739 if (graph
->node
[i
].band
[r
] == b
)
2742 if (graph
->node
[i
].band
[r
] == -1)
2745 if (r
== graph
->n_total_row
)
2747 sched
->node
[i
].n_band
= b
;
2748 for (--b
; b
>= 0; --b
)
2749 band_id
[b
] = graph
->node
[i
].band_id
[b
];
2756 isl_space_free(dim
);
2757 isl_schedule_free(sched
);
2761 /* Copy nodes that satisfy node_pred from the src dependence graph
2762 * to the dst dependence graph.
2764 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2765 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2770 for (i
= 0; i
< src
->n
; ++i
) {
2773 if (!node_pred(&src
->node
[i
], data
))
2777 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
2778 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
2779 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
2780 dst
->node
[j
].compress
=
2781 isl_multi_aff_copy(src
->node
[i
].compress
);
2782 dst
->node
[j
].decompress
=
2783 isl_multi_aff_copy(src
->node
[i
].decompress
);
2784 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
2785 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
2786 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2787 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
2788 dst
->node
[j
].band
= src
->node
[i
].band
;
2789 dst
->node
[j
].band_id
= src
->node
[i
].band_id
;
2790 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
2793 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
2795 if (dst
->node
[j
].compressed
&&
2796 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
2797 !dst
->node
[j
].decompress
))
2804 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2805 * to the dst dependence graph.
2806 * If the source or destination node of the edge is not in the destination
2807 * graph, then it must be a backward proximity edge and it should simply
2810 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2811 struct isl_sched_graph
*src
,
2812 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2815 enum isl_edge_type t
;
2818 for (i
= 0; i
< src
->n_edge
; ++i
) {
2819 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2821 isl_union_map
*tagged_condition
;
2822 isl_union_map
*tagged_validity
;
2823 struct isl_sched_node
*dst_src
, *dst_dst
;
2825 if (!edge_pred(edge
, data
))
2828 if (isl_map_plain_is_empty(edge
->map
))
2831 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
2832 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
2833 if (!dst_src
|| !dst_dst
) {
2834 if (edge
->validity
|| edge
->conditional_validity
)
2835 isl_die(ctx
, isl_error_internal
,
2836 "backward (conditional) validity edge",
2841 map
= isl_map_copy(edge
->map
);
2842 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
2843 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
2845 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2846 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2847 dst
->edge
[dst
->n_edge
].map
= map
;
2848 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
2849 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
2850 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2851 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2852 dst
->edge
[dst
->n_edge
].coincidence
= edge
->coincidence
;
2853 dst
->edge
[dst
->n_edge
].condition
= edge
->condition
;
2854 dst
->edge
[dst
->n_edge
].conditional_validity
=
2855 edge
->conditional_validity
;
2858 if (edge
->tagged_condition
&& !tagged_condition
)
2860 if (edge
->tagged_validity
&& !tagged_validity
)
2863 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2865 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2867 if (graph_edge_table_add(ctx
, dst
, t
,
2868 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2876 /* Given a "src" dependence graph that contains the nodes from "dst"
2877 * that satisfy node_pred, copy the schedule computed in "src"
2878 * for those nodes back to "dst".
2880 static int copy_schedule(struct isl_sched_graph
*dst
,
2881 struct isl_sched_graph
*src
,
2882 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2887 for (i
= 0; i
< dst
->n
; ++i
) {
2888 if (!node_pred(&dst
->node
[i
], data
))
2890 isl_mat_free(dst
->node
[i
].sched
);
2891 isl_map_free(dst
->node
[i
].sched_map
);
2892 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
2893 dst
->node
[i
].sched_map
=
2894 isl_map_copy(src
->node
[src
->n
].sched_map
);
2898 dst
->max_row
= src
->max_row
;
2899 dst
->n_total_row
= src
->n_total_row
;
2900 dst
->n_band
= src
->n_band
;
2905 /* Compute the maximal number of variables over all nodes.
2906 * This is the maximal number of linearly independent schedule
2907 * rows that we need to compute.
2908 * Just in case we end up in a part of the dependence graph
2909 * with only lower-dimensional domains, we make sure we will
2910 * compute the required amount of extra linearly independent rows.
2912 static int compute_maxvar(struct isl_sched_graph
*graph
)
2917 for (i
= 0; i
< graph
->n
; ++i
) {
2918 struct isl_sched_node
*node
= &graph
->node
[i
];
2921 if (node_update_cmap(node
) < 0)
2923 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2924 if (nvar
> graph
->maxvar
)
2925 graph
->maxvar
= nvar
;
2931 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2932 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2934 /* Compute a schedule for a subgraph of "graph". In particular, for
2935 * the graph composed of nodes that satisfy node_pred and edges that
2936 * that satisfy edge_pred. The caller should precompute the number
2937 * of nodes and edges that satisfy these predicates and pass them along
2938 * as "n" and "n_edge".
2939 * If the subgraph is known to consist of a single component, then wcc should
2940 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2941 * Otherwise, we call compute_schedule, which will check whether the subgraph
2944 static int compute_sub_schedule(isl_ctx
*ctx
,
2945 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2946 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2947 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2950 struct isl_sched_graph split
= { 0 };
2953 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2955 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2957 if (graph_init_table(ctx
, &split
) < 0)
2959 for (t
= 0; t
<= isl_edge_last
; ++t
)
2960 split
.max_edge
[t
] = graph
->max_edge
[t
];
2961 if (graph_init_edge_tables(ctx
, &split
) < 0)
2963 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2965 split
.n_row
= graph
->n_row
;
2966 split
.max_row
= graph
->max_row
;
2967 split
.n_total_row
= graph
->n_total_row
;
2968 split
.n_band
= graph
->n_band
;
2969 split
.band_start
= graph
->band_start
;
2971 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2973 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2976 copy_schedule(graph
, &split
, node_pred
, data
);
2978 graph_free(ctx
, &split
);
2981 graph_free(ctx
, &split
);
2985 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2987 return node
->scc
== scc
;
2990 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2992 return node
->scc
<= scc
;
2995 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2997 return node
->scc
>= scc
;
3000 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3002 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3005 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3007 return edge
->dst
->scc
<= scc
;
3010 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3012 return edge
->src
->scc
>= scc
;
3015 /* Pad the schedules of all nodes with zero rows such that in the end
3016 * they all have graph->n_total_row rows.
3017 * The extra rows don't belong to any band, so they get assigned band number -1.
3019 static int pad_schedule(struct isl_sched_graph
*graph
)
3023 for (i
= 0; i
< graph
->n
; ++i
) {
3024 struct isl_sched_node
*node
= &graph
->node
[i
];
3025 int row
= isl_mat_rows(node
->sched
);
3026 if (graph
->n_total_row
> row
) {
3027 isl_map_free(node
->sched_map
);
3028 node
->sched_map
= NULL
;
3030 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
3031 graph
->n_total_row
- row
);
3034 for (j
= row
; j
< graph
->n_total_row
; ++j
)
3041 /* Reset the current band by dropping all its schedule rows.
3043 static int reset_band(struct isl_sched_graph
*graph
)
3048 drop
= graph
->n_total_row
- graph
->band_start
;
3049 graph
->n_total_row
-= drop
;
3050 graph
->n_row
-= drop
;
3052 for (i
= 0; i
< graph
->n
; ++i
) {
3053 struct isl_sched_node
*node
= &graph
->node
[i
];
3055 isl_map_free(node
->sched_map
);
3056 node
->sched_map
= NULL
;
3058 node
->sched
= isl_mat_drop_rows(node
->sched
,
3059 graph
->band_start
, drop
);
3068 /* Split the current graph into two parts and compute a schedule for each
3069 * part individually. In particular, one part consists of all SCCs up
3070 * to and including graph->src_scc, while the other part contains the other
3073 * The split is enforced in the schedule by constant rows with two different
3074 * values (0 and 1). These constant rows replace the previously computed rows
3075 * in the current band.
3076 * It would be possible to reuse them as the first rows in the next
3077 * band, but recomputing them may result in better rows as we are looking
3078 * at a smaller part of the dependence graph.
3080 * Since we do not enforce coincidence, we conservatively mark the
3081 * splitting row as not coincident.
3083 * The band_id of the second group is set to n, where n is the number
3084 * of nodes in the first group. This ensures that the band_ids over
3085 * the two groups remain disjoint, even if either or both of the two
3086 * groups contain independent components.
3088 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3090 int i
, j
, n
, e1
, e2
;
3091 int n_total_row
, orig_total_row
;
3092 int n_band
, orig_band
;
3094 if (graph
->n_total_row
>= graph
->max_row
)
3095 isl_die(ctx
, isl_error_internal
,
3096 "too many schedule rows", return -1);
3098 if (reset_band(graph
) < 0)
3102 for (i
= 0; i
< graph
->n
; ++i
) {
3103 struct isl_sched_node
*node
= &graph
->node
[i
];
3104 int row
= isl_mat_rows(node
->sched
);
3105 int cols
= isl_mat_cols(node
->sched
);
3106 int before
= node
->scc
<= graph
->src_scc
;
3111 isl_map_free(node
->sched_map
);
3112 node
->sched_map
= NULL
;
3113 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
3116 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
3118 for (j
= 1; j
< cols
; ++j
)
3119 node
->sched
= isl_mat_set_element_si(node
->sched
,
3121 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3122 node
->coincident
[graph
->n_total_row
] = 0;
3126 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3127 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
3129 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
3133 graph
->n_total_row
++;
3136 for (i
= 0; i
< graph
->n
; ++i
) {
3137 struct isl_sched_node
*node
= &graph
->node
[i
];
3138 if (node
->scc
> graph
->src_scc
)
3139 node
->band_id
[graph
->n_band
] = n
;
3142 orig_total_row
= graph
->n_total_row
;
3143 orig_band
= graph
->n_band
;
3144 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
3145 &node_scc_at_most
, &edge_dst_scc_at_most
,
3146 graph
->src_scc
, 0) < 0)
3148 n_total_row
= graph
->n_total_row
;
3149 graph
->n_total_row
= orig_total_row
;
3150 n_band
= graph
->n_band
;
3151 graph
->n_band
= orig_band
;
3152 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
3153 &node_scc_at_least
, &edge_src_scc_at_least
,
3154 graph
->src_scc
+ 1, 0) < 0)
3156 if (n_total_row
> graph
->n_total_row
)
3157 graph
->n_total_row
= n_total_row
;
3158 if (n_band
> graph
->n_band
)
3159 graph
->n_band
= n_band
;
3161 return pad_schedule(graph
);
3164 /* Compute the next band of the schedule after updating the dependence
3165 * relations based on the the current schedule.
3167 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3169 if (update_edges(ctx
, graph
) < 0)
3173 return compute_schedule(ctx
, graph
);
3176 /* Add constraints to graph->lp that force the dependence "map" (which
3177 * is part of the dependence relation of "edge")
3178 * to be respected and attempt to carry it, where the edge is one from
3179 * a node j to itself. "pos" is the sequence number of the given map.
3180 * That is, add constraints that enforce
3182 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3183 * = c_j_x (y - x) >= e_i
3185 * for each (x,y) in R.
3186 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3187 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3188 * with each coefficient in c_j_x represented as a pair of non-negative
3191 static int add_intra_constraints(struct isl_sched_graph
*graph
,
3192 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3195 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3197 isl_dim_map
*dim_map
;
3198 isl_basic_set
*coef
;
3199 struct isl_sched_node
*node
= edge
->src
;
3201 coef
= intra_coefficients(graph
, node
, map
);
3205 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3207 total
= isl_basic_set_total_dim(graph
->lp
);
3208 dim_map
= isl_dim_map_alloc(ctx
, total
);
3209 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3210 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
3211 isl_space_dim(dim
, isl_dim_set
), 1,
3213 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
3214 isl_space_dim(dim
, isl_dim_set
), 1,
3216 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3217 coef
->n_eq
, coef
->n_ineq
);
3218 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3220 isl_space_free(dim
);
3225 /* Add constraints to graph->lp that force the dependence "map" (which
3226 * is part of the dependence relation of "edge")
3227 * to be respected and attempt to carry it, where the edge is one from
3228 * node j to node k. "pos" is the sequence number of the given map.
3229 * That is, add constraints that enforce
3231 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3233 * for each (x,y) in R.
3234 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3235 * of valid constraints for R and then plug in
3236 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3237 * with each coefficient (except e_i, c_k_0 and c_j_0)
3238 * represented as a pair of non-negative coefficients.
3240 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3241 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3244 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3246 isl_dim_map
*dim_map
;
3247 isl_basic_set
*coef
;
3248 struct isl_sched_node
*src
= edge
->src
;
3249 struct isl_sched_node
*dst
= edge
->dst
;
3251 coef
= inter_coefficients(graph
, edge
, map
);
3255 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3257 total
= isl_basic_set_total_dim(graph
->lp
);
3258 dim_map
= isl_dim_map_alloc(ctx
, total
);
3260 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3262 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
3263 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
3264 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
3265 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
3266 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3268 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
3269 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3272 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
3273 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
3274 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
3275 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
3276 isl_space_dim(dim
, isl_dim_set
), 1,
3278 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
3279 isl_space_dim(dim
, isl_dim_set
), 1,
3282 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3283 coef
->n_eq
, coef
->n_ineq
);
3284 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3286 isl_space_free(dim
);
3291 /* Add constraints to graph->lp that force all (conditional) validity
3292 * dependences to be respected and attempt to carry them.
3294 static int add_all_constraints(struct isl_sched_graph
*graph
)
3300 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3301 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3303 if (!edge
->validity
&& !edge
->conditional_validity
)
3306 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3307 isl_basic_map
*bmap
;
3310 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3311 map
= isl_map_from_basic_map(bmap
);
3313 if (edge
->src
== edge
->dst
&&
3314 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3316 if (edge
->src
!= edge
->dst
&&
3317 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3326 /* Count the number of equality and inequality constraints
3327 * that will be added to the carry_lp problem.
3328 * We count each edge exactly once.
3330 static int count_all_constraints(struct isl_sched_graph
*graph
,
3331 int *n_eq
, int *n_ineq
)
3335 *n_eq
= *n_ineq
= 0;
3336 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3337 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3338 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3339 isl_basic_map
*bmap
;
3342 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3343 map
= isl_map_from_basic_map(bmap
);
3345 if (count_map_constraints(graph
, edge
, map
,
3346 n_eq
, n_ineq
, 1, 0) < 0)
3354 /* Construct an LP problem for finding schedule coefficients
3355 * such that the schedule carries as many dependences as possible.
3356 * In particular, for each dependence i, we bound the dependence distance
3357 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3358 * of all e_i's. Dependence with e_i = 0 in the solution are simply
3359 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3360 * Note that if the dependence relation is a union of basic maps,
3361 * then we have to consider each basic map individually as it may only
3362 * be possible to carry the dependences expressed by some of those
3363 * basic maps and not all off them.
3364 * Below, we consider each of those basic maps as a separate "edge".
3366 * All variables of the LP are non-negative. The actual coefficients
3367 * may be negative, so each coefficient is represented as the difference
3368 * of two non-negative variables. The negative part always appears
3369 * immediately before the positive part.
3370 * Other than that, the variables have the following order
3372 * - sum of (1 - e_i) over all edges
3373 * - sum of positive and negative parts of all c_n coefficients
3374 * (unconstrained when computing non-parametric schedules)
3375 * - sum of positive and negative parts of all c_x coefficients
3380 * - positive and negative parts of c_i_n (if parametric)
3381 * - positive and negative parts of c_i_x
3383 * The constraints are those from the (validity) edges plus three equalities
3384 * to express the sums and n_edge inequalities to express e_i <= 1.
3386 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3396 for (i
= 0; i
< graph
->n_edge
; ++i
)
3397 n_edge
+= graph
->edge
[i
].map
->n
;
3400 for (i
= 0; i
< graph
->n
; ++i
) {
3401 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3402 node
->start
= total
;
3403 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
3406 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3408 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
3411 dim
= isl_space_set_alloc(ctx
, 0, total
);
3412 isl_basic_set_free(graph
->lp
);
3415 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3416 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3418 k
= isl_basic_set_alloc_equality(graph
->lp
);
3421 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3422 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3423 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3424 for (i
= 0; i
< n_edge
; ++i
)
3425 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3427 k
= isl_basic_set_alloc_equality(graph
->lp
);
3430 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3431 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
3432 for (i
= 0; i
< graph
->n
; ++i
) {
3433 int pos
= 1 + graph
->node
[i
].start
+ 1;
3435 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
3436 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3439 k
= isl_basic_set_alloc_equality(graph
->lp
);
3442 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3443 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
3444 for (i
= 0; i
< graph
->n
; ++i
) {
3445 struct isl_sched_node
*node
= &graph
->node
[i
];
3446 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3448 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
3449 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3452 for (i
= 0; i
< n_edge
; ++i
) {
3453 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3456 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3457 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3458 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3461 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
3463 if (add_all_constraints(graph
) < 0)
3469 /* If the schedule_split_scaled option is set and if the linear
3470 * parts of the scheduling rows for all nodes in the graphs have
3471 * non-trivial common divisor, then split off the constant term
3472 * from the linear part.
3473 * The constant term is then placed in a separate band and
3474 * the linear part is reduced.
3476 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3482 if (!ctx
->opt
->schedule_split_scaled
)
3487 if (graph
->n_total_row
>= graph
->max_row
)
3488 isl_die(ctx
, isl_error_internal
,
3489 "too many schedule rows", return -1);
3492 isl_int_init(gcd_i
);
3494 isl_int_set_si(gcd
, 0);
3496 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3498 for (i
= 0; i
< graph
->n
; ++i
) {
3499 struct isl_sched_node
*node
= &graph
->node
[i
];
3500 int cols
= isl_mat_cols(node
->sched
);
3502 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3503 isl_int_gcd(gcd
, gcd
, gcd_i
);
3506 isl_int_clear(gcd_i
);
3508 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3515 for (i
= 0; i
< graph
->n
; ++i
) {
3516 struct isl_sched_node
*node
= &graph
->node
[i
];
3518 isl_map_free(node
->sched_map
);
3519 node
->sched_map
= NULL
;
3520 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3523 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
3524 node
->sched
->row
[row
][0], gcd
);
3525 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3526 node
->sched
->row
[row
][0], gcd
);
3527 isl_int_mul(node
->sched
->row
[row
][0],
3528 node
->sched
->row
[row
][0], gcd
);
3529 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3532 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3535 graph
->n_total_row
++;
3544 static int compute_component_schedule(isl_ctx
*ctx
,
3545 struct isl_sched_graph
*graph
);
3547 /* Is the schedule row "sol" trivial on node "node"?
3548 * That is, is the solution zero on the dimensions orthogonal to
3549 * the previously found solutions?
3550 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3552 * Each coefficient is represented as the difference between
3553 * two non-negative values in "sol". "sol" has been computed
3554 * in terms of the original iterators (i.e., without use of cmap).
3555 * We construct the schedule row s and write it as a linear
3556 * combination of (linear combinations of) previously computed schedule rows.
3557 * s = Q c or c = U s.
3558 * If the final entries of c are all zero, then the solution is trivial.
3560 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3570 if (node
->nvar
== node
->rank
)
3573 ctx
= isl_vec_get_ctx(sol
);
3574 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3578 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3580 for (i
= 0; i
< node
->nvar
; ++i
)
3581 isl_int_sub(node_sol
->el
[i
],
3582 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3584 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3589 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3590 node
->nvar
- node
->rank
) == -1;
3592 isl_vec_free(node_sol
);
3597 /* Is the schedule row "sol" trivial on any node where it should
3599 * "sol" has been computed in terms of the original iterators
3600 * (i.e., without use of cmap).
3601 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3603 static int is_any_trivial(struct isl_sched_graph
*graph
,
3604 __isl_keep isl_vec
*sol
)
3608 for (i
= 0; i
< graph
->n
; ++i
) {
3609 struct isl_sched_node
*node
= &graph
->node
[i
];
3612 if (!needs_row(graph
, node
))
3614 trivial
= is_trivial(node
, sol
);
3615 if (trivial
< 0 || trivial
)
3622 /* Construct a schedule row for each node such that as many dependences
3623 * as possible are carried and then continue with the next band.
3625 * If the computed schedule row turns out to be trivial on one or
3626 * more nodes where it should not be trivial, then we throw it away
3627 * and try again on each component separately.
3629 * If there is only one component, then we accept the schedule row anyway,
3630 * but we do not consider it as a complete row and therefore do not
3631 * increment graph->n_row. Note that the ranks of the nodes that
3632 * do get a non-trivial schedule part will get updated regardless and
3633 * graph->maxvar is computed based on these ranks. The test for
3634 * whether more schedule rows are required in compute_schedule_wcc
3635 * is therefore not affected.
3637 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3646 for (i
= 0; i
< graph
->n_edge
; ++i
)
3647 n_edge
+= graph
->edge
[i
].map
->n
;
3649 if (setup_carry_lp(ctx
, graph
) < 0)
3652 lp
= isl_basic_set_copy(graph
->lp
);
3653 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3657 if (sol
->size
== 0) {
3659 isl_die(ctx
, isl_error_internal
,
3660 "error in schedule construction", return -1);
3663 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3664 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3666 isl_die(ctx
, isl_error_unknown
,
3667 "unable to carry dependences", return -1);
3670 trivial
= is_any_trivial(graph
, sol
);
3672 sol
= isl_vec_free(sol
);
3673 } else if (trivial
&& graph
->scc
> 1) {
3675 return compute_component_schedule(ctx
, graph
);
3678 if (update_schedule(graph
, sol
, 0, 0) < 0)
3683 if (split_scaled(ctx
, graph
) < 0)
3686 return compute_next_band(ctx
, graph
);
3689 /* Are there any (non-empty) (conditional) validity edges in the graph?
3691 static int has_validity_edges(struct isl_sched_graph
*graph
)
3695 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3698 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3703 if (graph
->edge
[i
].validity
||
3704 graph
->edge
[i
].conditional_validity
)
3711 /* Should we apply a Feautrier step?
3712 * That is, did the user request the Feautrier algorithm and are
3713 * there any validity dependences (left)?
3715 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3717 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3720 return has_validity_edges(graph
);
3723 /* Compute a schedule for a connected dependence graph using Feautrier's
3724 * multi-dimensional scheduling algorithm.
3725 * The original algorithm is described in [1].
3726 * The main idea is to minimize the number of scheduling dimensions, by
3727 * trying to satisfy as many dependences as possible per scheduling dimension.
3729 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3730 * Problem, Part II: Multi-Dimensional Time.
3731 * In Intl. Journal of Parallel Programming, 1992.
3733 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
3734 struct isl_sched_graph
*graph
)
3736 return carry_dependences(ctx
, graph
);
3739 /* Turn off the "local" bit on all (condition) edges.
3741 static void clear_local_edges(struct isl_sched_graph
*graph
)
3745 for (i
= 0; i
< graph
->n_edge
; ++i
)
3746 if (graph
->edge
[i
].condition
)
3747 graph
->edge
[i
].local
= 0;
3750 /* Does "graph" have both condition and conditional validity edges?
3752 static int need_condition_check(struct isl_sched_graph
*graph
)
3755 int any_condition
= 0;
3756 int any_conditional_validity
= 0;
3758 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3759 if (graph
->edge
[i
].condition
)
3761 if (graph
->edge
[i
].conditional_validity
)
3762 any_conditional_validity
= 1;
3765 return any_condition
&& any_conditional_validity
;
3768 /* Does "graph" contain any coincidence edge?
3770 static int has_any_coincidence(struct isl_sched_graph
*graph
)
3774 for (i
= 0; i
< graph
->n_edge
; ++i
)
3775 if (graph
->edge
[i
].coincidence
)
3781 /* Extract the final schedule row as a map with the iteration domain
3782 * of "node" as domain.
3784 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
3786 isl_local_space
*ls
;
3790 row
= isl_mat_rows(node
->sched
) - 1;
3791 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
3792 aff
= extract_schedule_row(ls
, node
, row
);
3793 return isl_map_from_aff(aff
);
3796 /* Is the conditional validity dependence in the edge with index "edge_index"
3797 * violated by the latest (i.e., final) row of the schedule?
3798 * That is, is i scheduled after j
3799 * for any conditional validity dependence i -> j?
3801 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
3803 isl_map
*src_sched
, *dst_sched
, *map
;
3804 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
3807 src_sched
= final_row(edge
->src
);
3808 dst_sched
= final_row(edge
->dst
);
3809 map
= isl_map_copy(edge
->map
);
3810 map
= isl_map_apply_domain(map
, src_sched
);
3811 map
= isl_map_apply_range(map
, dst_sched
);
3812 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
3813 empty
= isl_map_is_empty(map
);
3822 /* Does "graph" have any satisfied condition edges that
3823 * are adjacent to the conditional validity constraint with
3824 * domain "conditional_source" and range "conditional_sink"?
3826 * A satisfied condition is one that is not local.
3827 * If a condition was forced to be local already (i.e., marked as local)
3828 * then there is no need to check if it is in fact local.
3830 * Additionally, mark all adjacent condition edges found as local.
3832 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
3833 __isl_keep isl_union_set
*conditional_source
,
3834 __isl_keep isl_union_set
*conditional_sink
)
3839 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3840 int adjacent
, local
;
3841 isl_union_map
*condition
;
3843 if (!graph
->edge
[i
].condition
)
3845 if (graph
->edge
[i
].local
)
3848 condition
= graph
->edge
[i
].tagged_condition
;
3849 adjacent
= domain_intersects(condition
, conditional_sink
);
3850 if (adjacent
>= 0 && !adjacent
)
3851 adjacent
= range_intersects(condition
,
3852 conditional_source
);
3858 graph
->edge
[i
].local
= 1;
3860 local
= is_condition_false(&graph
->edge
[i
]);
3870 /* Are there any violated conditional validity dependences with
3871 * adjacent condition dependences that are not local with respect
3872 * to the current schedule?
3873 * That is, is the conditional validity constraint violated?
3875 * Additionally, mark all those adjacent condition dependences as local.
3876 * We also mark those adjacent condition dependences that were not marked
3877 * as local before, but just happened to be local already. This ensures
3878 * that they remain local if the schedule is recomputed.
3880 * We first collect domain and range of all violated conditional validity
3881 * dependences and then check if there are any adjacent non-local
3882 * condition dependences.
3884 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
3885 struct isl_sched_graph
*graph
)
3889 isl_union_set
*source
, *sink
;
3891 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3892 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3893 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3894 isl_union_set
*uset
;
3895 isl_union_map
*umap
;
3898 if (!graph
->edge
[i
].conditional_validity
)
3901 violated
= is_violated(graph
, i
);
3909 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3910 uset
= isl_union_map_domain(umap
);
3911 source
= isl_union_set_union(source
, uset
);
3912 source
= isl_union_set_coalesce(source
);
3914 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3915 uset
= isl_union_map_range(umap
);
3916 sink
= isl_union_set_union(sink
, uset
);
3917 sink
= isl_union_set_coalesce(sink
);
3921 any
= has_adjacent_true_conditions(graph
, source
, sink
);
3923 isl_union_set_free(source
);
3924 isl_union_set_free(sink
);
3927 isl_union_set_free(source
);
3928 isl_union_set_free(sink
);
3932 /* Compute a schedule for a connected dependence graph.
3933 * We try to find a sequence of as many schedule rows as possible that result
3934 * in non-negative dependence distances (independent of the previous rows
3935 * in the sequence, i.e., such that the sequence is tilable), with as
3936 * many of the initial rows as possible satisfying the coincidence constraints.
3937 * If we can't find any more rows we either
3938 * - split between SCCs and start over (assuming we found an interesting
3939 * pair of SCCs between which to split)
3940 * - continue with the next band (assuming the current band has at least
3942 * - try to carry as many dependences as possible and continue with the next
3945 * If Feautrier's algorithm is selected, we first recursively try to satisfy
3946 * as many validity dependences as possible. When all validity dependences
3947 * are satisfied we extend the schedule to a full-dimensional schedule.
3949 * If we manage to complete the schedule, we finish off by topologically
3950 * sorting the statements based on the remaining dependences.
3952 * If ctx->opt->schedule_outer_coincidence is set, then we force the
3953 * outermost dimension to satisfy the coincidence constraints. If this
3954 * turns out to be impossible, we fall back on the general scheme above
3955 * and try to carry as many dependences as possible.
3957 * If "graph" contains both condition and conditional validity dependences,
3958 * then we need to check that that the conditional schedule constraint
3959 * is satisfied, i.e., there are no violated conditional validity dependences
3960 * that are adjacent to any non-local condition dependences.
3961 * If there are, then we mark all those adjacent condition dependences
3962 * as local and recompute the current band. Those dependences that
3963 * are marked local will then be forced to be local.
3964 * The initial computation is performed with no dependences marked as local.
3965 * If we are lucky, then there will be no violated conditional validity
3966 * dependences adjacent to any non-local condition dependences.
3967 * Otherwise, we mark some additional condition dependences as local and
3968 * recompute. We continue this process until there are no violations left or
3969 * until we are no longer able to compute a schedule.
3970 * Since there are only a finite number of dependences,
3971 * there will only be a finite number of iterations.
3973 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3975 int has_coincidence
;
3976 int use_coincidence
;
3977 int force_coincidence
= 0;
3978 int check_conditional
;
3980 if (detect_sccs(ctx
, graph
) < 0)
3982 if (sort_sccs(graph
) < 0)
3985 if (compute_maxvar(graph
) < 0)
3988 if (need_feautrier_step(ctx
, graph
))
3989 return compute_schedule_wcc_feautrier(ctx
, graph
);
3991 clear_local_edges(graph
);
3992 check_conditional
= need_condition_check(graph
);
3993 has_coincidence
= has_any_coincidence(graph
);
3995 if (ctx
->opt
->schedule_outer_coincidence
)
3996 force_coincidence
= 1;
3998 use_coincidence
= has_coincidence
;
3999 while (graph
->n_row
< graph
->maxvar
) {
4004 graph
->src_scc
= -1;
4005 graph
->dst_scc
= -1;
4007 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
4009 sol
= solve_lp(graph
);
4012 if (sol
->size
== 0) {
4013 int empty
= graph
->n_total_row
== graph
->band_start
;
4016 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
4017 use_coincidence
= 0;
4020 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
4021 return compute_next_band(ctx
, graph
);
4022 if (graph
->src_scc
>= 0)
4023 return compute_split_schedule(ctx
, graph
);
4025 return compute_next_band(ctx
, graph
);
4026 return carry_dependences(ctx
, graph
);
4028 coincident
= !has_coincidence
|| use_coincidence
;
4029 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
4032 if (!check_conditional
)
4034 violated
= has_violated_conditional_constraint(ctx
, graph
);
4039 if (reset_band(graph
) < 0)
4041 use_coincidence
= has_coincidence
;
4044 if (graph
->n_total_row
> graph
->band_start
)
4046 return sort_statements(ctx
, graph
);
4049 /* Add a row to the schedules that separates the SCCs and move
4052 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4056 if (graph
->n_total_row
>= graph
->max_row
)
4057 isl_die(ctx
, isl_error_internal
,
4058 "too many schedule rows", return -1);
4060 for (i
= 0; i
< graph
->n
; ++i
) {
4061 struct isl_sched_node
*node
= &graph
->node
[i
];
4062 int row
= isl_mat_rows(node
->sched
);
4064 isl_map_free(node
->sched_map
);
4065 node
->sched_map
= NULL
;
4066 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
4067 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
4071 node
->band
[graph
->n_total_row
] = graph
->n_band
;
4074 graph
->n_total_row
++;
4080 /* Compute a schedule for each component (identified by node->scc)
4081 * of the dependence graph separately and then combine the results.
4082 * Depending on the setting of schedule_fuse, a component may be
4083 * either weakly or strongly connected.
4085 * The band_id is adjusted such that each component has a separate id.
4086 * Note that the band_id may have already been set to a value different
4087 * from zero by compute_split_schedule.
4089 static int compute_component_schedule(isl_ctx
*ctx
,
4090 struct isl_sched_graph
*graph
)
4094 int n_total_row
, orig_total_row
;
4095 int n_band
, orig_band
;
4097 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
4098 ctx
->opt
->schedule_separate_components
)
4099 if (split_on_scc(ctx
, graph
) < 0)
4103 orig_total_row
= graph
->n_total_row
;
4105 orig_band
= graph
->n_band
;
4106 for (i
= 0; i
< graph
->n
; ++i
)
4107 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
4108 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
4110 for (i
= 0; i
< graph
->n
; ++i
)
4111 if (graph
->node
[i
].scc
== wcc
)
4114 for (i
= 0; i
< graph
->n_edge
; ++i
)
4115 if (graph
->edge
[i
].src
->scc
== wcc
&&
4116 graph
->edge
[i
].dst
->scc
== wcc
)
4119 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
4121 &edge_scc_exactly
, wcc
, 1) < 0)
4123 if (graph
->n_total_row
> n_total_row
)
4124 n_total_row
= graph
->n_total_row
;
4125 graph
->n_total_row
= orig_total_row
;
4126 if (graph
->n_band
> n_band
)
4127 n_band
= graph
->n_band
;
4128 graph
->n_band
= orig_band
;
4131 graph
->n_total_row
= n_total_row
;
4132 graph
->n_band
= n_band
;
4134 return pad_schedule(graph
);
4137 /* Compute a schedule for the given dependence graph.
4138 * We first check if the graph is connected (through validity and conditional
4139 * validity dependences) and, if not, compute a schedule
4140 * for each component separately.
4141 * If schedule_fuse is set to minimal fusion, then we check for strongly
4142 * connected components instead and compute a separate schedule for
4143 * each such strongly connected component.
4145 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
4147 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
4148 if (detect_sccs(ctx
, graph
) < 0)
4151 if (detect_wccs(ctx
, graph
) < 0)
4156 return compute_component_schedule(ctx
, graph
);
4158 return compute_schedule_wcc(ctx
, graph
);
4161 /* Compute a schedule on sc->domain that respects the given schedule
4164 * In particular, the schedule respects all the validity dependences.
4165 * If the default isl scheduling algorithm is used, it tries to minimize
4166 * the dependence distances over the proximity dependences.
4167 * If Feautrier's scheduling algorithm is used, the proximity dependence
4168 * distances are only minimized during the extension to a full-dimensional
4171 * If there are any condition and conditional validity dependences,
4172 * then the conditional validity dependences may be violated inside
4173 * a tilable band, provided they have no adjacent non-local
4174 * condition dependences.
4176 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
4177 __isl_take isl_schedule_constraints
*sc
)
4179 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
4180 struct isl_sched_graph graph
= { 0 };
4181 isl_schedule
*sched
;
4182 struct isl_extract_edge_data data
;
4183 enum isl_edge_type i
;
4185 sc
= isl_schedule_constraints_align_params(sc
);
4189 graph
.n
= isl_union_set_n_set(sc
->domain
);
4192 if (graph_alloc(ctx
, &graph
, graph
.n
,
4193 isl_schedule_constraints_n_map(sc
)) < 0)
4195 if (compute_max_row(&graph
, sc
) < 0)
4199 if (isl_union_set_foreach_set(sc
->domain
, &extract_node
, &graph
) < 0)
4201 if (graph_init_table(ctx
, &graph
) < 0)
4203 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
4204 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
4205 if (graph_init_edge_tables(ctx
, &graph
) < 0)
4208 data
.graph
= &graph
;
4209 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
4211 if (isl_union_map_foreach_map(sc
->constraint
[i
],
4212 &extract_edge
, &data
) < 0)
4216 if (compute_schedule(ctx
, &graph
) < 0)
4220 sched
= extract_schedule(&graph
, isl_union_set_get_space(sc
->domain
));
4222 graph_free(ctx
, &graph
);
4223 isl_schedule_constraints_free(sc
);
4227 graph_free(ctx
, &graph
);
4228 isl_schedule_constraints_free(sc
);
4232 /* Compute a schedule for the given union of domains that respects
4233 * all the validity dependences and minimizes
4234 * the dependence distances over the proximity dependences.
4236 * This function is kept for backward compatibility.
4238 __isl_give isl_schedule
*isl_union_set_compute_schedule(
4239 __isl_take isl_union_set
*domain
,
4240 __isl_take isl_union_map
*validity
,
4241 __isl_take isl_union_map
*proximity
)
4243 isl_schedule_constraints
*sc
;
4245 sc
= isl_schedule_constraints_on_domain(domain
);
4246 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
4247 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
4249 return isl_schedule_constraints_compute_schedule(sc
);