2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_space_private.h>
16 #include <isl_aff_private.h>
18 #include <isl/constraint.h>
19 #include <isl/schedule.h>
20 #include <isl_mat_private.h>
21 #include <isl_vec_private.h>
25 #include <isl_dim_map.h>
26 #include <isl/map_to_basic_set.h>
28 #include <isl_schedule_private.h>
29 #include <isl_band_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".
40 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
41 __isl_keep isl_schedule_constraints
*sc
)
44 isl_schedule_constraints
*sc_copy
;
47 ctx
= isl_union_set_get_ctx(sc
->domain
);
48 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
52 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
54 return isl_schedule_constraints_free(sc_copy
);
56 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
57 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
58 if (!sc_copy
->constraint
[i
])
59 return isl_schedule_constraints_free(sc_copy
);
66 /* Construct an isl_schedule_constraints object for computing a schedule
67 * on "domain". The initial object does not impose any constraints.
69 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
70 __isl_take isl_union_set
*domain
)
74 isl_schedule_constraints
*sc
;
81 ctx
= isl_union_set_get_ctx(domain
);
82 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
86 space
= isl_union_set_get_space(domain
);
88 empty
= isl_union_map_empty(space
);
89 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
90 sc
->constraint
[i
] = isl_union_map_copy(empty
);
91 if (!sc
->constraint
[i
])
92 sc
->domain
= isl_union_set_free(sc
->domain
);
94 isl_union_map_free(empty
);
97 return isl_schedule_constraints_free(sc
);
101 isl_union_set_free(domain
);
105 /* Replace the validity constraints of "sc" by "validity".
107 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
108 __isl_take isl_schedule_constraints
*sc
,
109 __isl_take isl_union_map
*validity
)
111 if (!sc
|| !validity
)
114 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
115 sc
->constraint
[isl_edge_validity
] = validity
;
119 isl_schedule_constraints_free(sc
);
120 isl_union_map_free(validity
);
124 /* Replace the coincidence constraints of "sc" by "coincidence".
126 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
127 __isl_take isl_schedule_constraints
*sc
,
128 __isl_take isl_union_map
*coincidence
)
130 if (!sc
|| !coincidence
)
133 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
134 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
138 isl_schedule_constraints_free(sc
);
139 isl_union_map_free(coincidence
);
143 /* Replace the proximity constraints of "sc" by "proximity".
145 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
146 __isl_take isl_schedule_constraints
*sc
,
147 __isl_take isl_union_map
*proximity
)
149 if (!sc
|| !proximity
)
152 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
153 sc
->constraint
[isl_edge_proximity
] = proximity
;
157 isl_schedule_constraints_free(sc
);
158 isl_union_map_free(proximity
);
162 /* Replace the conditional validity constraints of "sc" by "condition"
165 __isl_give isl_schedule_constraints
*
166 isl_schedule_constraints_set_conditional_validity(
167 __isl_take isl_schedule_constraints
*sc
,
168 __isl_take isl_union_map
*condition
,
169 __isl_take isl_union_map
*validity
)
171 if (!sc
|| !condition
|| !validity
)
174 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
175 sc
->constraint
[isl_edge_condition
] = condition
;
176 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
177 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
181 isl_schedule_constraints_free(sc
);
182 isl_union_map_free(condition
);
183 isl_union_map_free(validity
);
187 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
188 __isl_take isl_schedule_constraints
*sc
)
190 enum isl_edge_type i
;
195 isl_union_set_free(sc
->domain
);
196 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
197 isl_union_map_free(sc
->constraint
[i
]);
204 isl_ctx
*isl_schedule_constraints_get_ctx(
205 __isl_keep isl_schedule_constraints
*sc
)
207 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
210 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
215 fprintf(stderr
, "domain: ");
216 isl_union_set_dump(sc
->domain
);
217 fprintf(stderr
, "validity: ");
218 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
219 fprintf(stderr
, "proximity: ");
220 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
221 fprintf(stderr
, "coincidence: ");
222 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
223 fprintf(stderr
, "condition: ");
224 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
225 fprintf(stderr
, "conditional_validity: ");
226 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
229 /* Align the parameters of the fields of "sc".
231 static __isl_give isl_schedule_constraints
*
232 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
235 enum isl_edge_type i
;
240 space
= isl_union_set_get_space(sc
->domain
);
241 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
242 space
= isl_space_align_params(space
,
243 isl_union_map_get_space(sc
->constraint
[i
]));
245 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
246 sc
->constraint
[i
] = isl_union_map_align_params(
247 sc
->constraint
[i
], isl_space_copy(space
));
248 if (!sc
->constraint
[i
])
249 space
= isl_space_free(space
);
251 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
253 return isl_schedule_constraints_free(sc
);
258 /* Return the total number of isl_maps in the constraints of "sc".
260 static __isl_give
int isl_schedule_constraints_n_map(
261 __isl_keep isl_schedule_constraints
*sc
)
263 enum isl_edge_type i
;
266 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
267 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
272 /* Internal information about a node that is used during the construction
274 * space represents the space in which the domain lives
275 * sched is a matrix representation of the schedule being constructed
276 * for this node; if compressed is set, then this schedule is
277 * defined over the compressed domain space
278 * sched_map is an isl_map representation of the same (partial) schedule
279 * sched_map may be NULL; if compressed is set, then this map
280 * is defined over the uncompressed domain space
281 * rank is the number of linearly independent rows in the linear part
283 * the columns of cmap represent a change of basis for the schedule
284 * coefficients; the first rank columns span the linear part of
286 * cinv is the inverse of cmap.
287 * start is the first variable in the LP problem in the sequences that
288 * represents the schedule coefficients of this node
289 * nvar is the dimension of the domain
290 * nparam is the number of parameters or 0 if we are not constructing
291 * a parametric schedule
293 * If compressed is set, then hull represents the constraints
294 * that were used to derive the compression, while compress and
295 * decompress map the original space to the compressed space and
298 * scc is the index of SCC (or WCC) this node belongs to
300 * band contains the band index for each of the rows of the schedule.
301 * band_id is used to differentiate between separate bands at the same
302 * level within the same parent band, i.e., bands that are separated
303 * by the parent band or bands that are independent of each other.
304 * coincident contains a boolean for each of the rows of the schedule,
305 * indicating whether the corresponding scheduling dimension satisfies
306 * the coincidence constraints in the sense that the corresponding
307 * dependence distances are zero.
309 struct isl_sched_node
{
313 isl_multi_aff
*compress
;
314 isl_multi_aff
*decompress
;
331 static int node_has_space(const void *entry
, const void *val
)
333 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
334 isl_space
*dim
= (isl_space
*)val
;
336 return isl_space_is_equal(node
->space
, dim
);
339 /* An edge in the dependence graph. An edge may be used to
340 * ensure validity of the generated schedule, to minimize the dependence
343 * map is the dependence relation, with i -> j in the map if j depends on i
344 * tagged_condition and tagged_validity contain the union of all tagged
345 * condition or conditional validity dependence relations that
346 * specialize the dependence relation "map"; that is,
347 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
348 * or "tagged_validity", then i -> j is an element of "map".
349 * If these fields are NULL, then they represent the empty relation.
350 * src is the source node
351 * dst is the sink node
352 * validity is set if the edge is used to ensure correctness
353 * coincidence is used to enforce zero dependence distances
354 * proximity is set if the edge is used to minimize dependence distances
355 * condition is set if the edge represents a condition
356 * for a conditional validity schedule constraint
357 * local can only be set for condition edges and indicates that
358 * the dependence distance over the edge should be zero
359 * conditional_validity is set if the edge is used to conditionally
362 * For validity edges, start and end mark the sequence of inequality
363 * constraints in the LP problem that encode the validity constraint
364 * corresponding to this edge.
366 struct isl_sched_edge
{
368 isl_union_map
*tagged_condition
;
369 isl_union_map
*tagged_validity
;
371 struct isl_sched_node
*src
;
372 struct isl_sched_node
*dst
;
374 unsigned validity
: 1;
375 unsigned coincidence
: 1;
376 unsigned proximity
: 1;
378 unsigned condition
: 1;
379 unsigned conditional_validity
: 1;
385 /* Internal information about the dependence graph used during
386 * the construction of the schedule.
388 * intra_hmap is a cache, mapping dependence relations to their dual,
389 * for dependences from a node to itself
390 * inter_hmap is a cache, mapping dependence relations to their dual,
391 * for dependences between distinct nodes
392 * if compression is involved then the key for these maps
393 * it the original, uncompressed dependence relation, while
394 * the value is the dual of the compressed dependence relation.
396 * n is the number of nodes
397 * node is the list of nodes
398 * maxvar is the maximal number of variables over all nodes
399 * max_row is the allocated number of rows in the schedule
400 * n_row is the current (maximal) number of linearly independent
401 * rows in the node schedules
402 * n_total_row is the current number of rows in the node schedules
403 * n_band is the current number of completed bands
404 * band_start is the starting row in the node schedules of the current band
405 * root is set if this graph is the original dependence graph,
406 * without any splitting
408 * sorted contains a list of node indices sorted according to the
409 * SCC to which a node belongs
411 * n_edge is the number of edges
412 * edge is the list of edges
413 * max_edge contains the maximal number of edges of each type;
414 * in particular, it contains the number of edges in the inital graph.
415 * edge_table contains pointers into the edge array, hashed on the source
416 * and sink spaces; there is one such table for each type;
417 * a given edge may be referenced from more than one table
418 * if the corresponding relation appears in more than of the
419 * sets of dependences
421 * node_table contains pointers into the node array, hashed on the space
423 * region contains a list of variable sequences that should be non-trivial
425 * lp contains the (I)LP problem used to obtain new schedule rows
427 * src_scc and dst_scc are the source and sink SCCs of an edge with
428 * conflicting constraints
430 * scc represents the number of components
432 struct isl_sched_graph
{
433 isl_map_to_basic_set
*intra_hmap
;
434 isl_map_to_basic_set
*inter_hmap
;
436 struct isl_sched_node
*node
;
450 struct isl_sched_edge
*edge
;
452 int max_edge
[isl_edge_last
+ 1];
453 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
455 struct isl_hash_table
*node_table
;
456 struct isl_region
*region
;
466 /* Initialize node_table based on the list of nodes.
468 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
472 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
473 if (!graph
->node_table
)
476 for (i
= 0; i
< graph
->n
; ++i
) {
477 struct isl_hash_table_entry
*entry
;
480 hash
= isl_space_get_hash(graph
->node
[i
].space
);
481 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
483 graph
->node
[i
].space
, 1);
486 entry
->data
= &graph
->node
[i
];
492 /* Return a pointer to the node that lives within the given space,
493 * or NULL if there is no such node.
495 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
496 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
498 struct isl_hash_table_entry
*entry
;
501 hash
= isl_space_get_hash(dim
);
502 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
503 &node_has_space
, dim
, 0);
505 return entry
? entry
->data
: NULL
;
508 static int edge_has_src_and_dst(const void *entry
, const void *val
)
510 const struct isl_sched_edge
*edge
= entry
;
511 const struct isl_sched_edge
*temp
= val
;
513 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
516 /* Add the given edge to graph->edge_table[type].
518 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
519 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
521 struct isl_hash_table_entry
*entry
;
524 hash
= isl_hash_init();
525 hash
= isl_hash_builtin(hash
, edge
->src
);
526 hash
= isl_hash_builtin(hash
, edge
->dst
);
527 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
528 &edge_has_src_and_dst
, edge
, 1);
536 /* Allocate the edge_tables based on the maximal number of edges of
539 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
543 for (i
= 0; i
<= isl_edge_last
; ++i
) {
544 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
546 if (!graph
->edge_table
[i
])
553 /* If graph->edge_table[type] contains an edge from the given source
554 * to the given destination, then return the hash table entry of this edge.
555 * Otherwise, return NULL.
557 static struct isl_hash_table_entry
*graph_find_edge_entry(
558 struct isl_sched_graph
*graph
,
559 enum isl_edge_type type
,
560 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
562 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
564 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
566 hash
= isl_hash_init();
567 hash
= isl_hash_builtin(hash
, temp
.src
);
568 hash
= isl_hash_builtin(hash
, temp
.dst
);
569 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
570 &edge_has_src_and_dst
, &temp
, 0);
574 /* If graph->edge_table[type] contains an edge from the given source
575 * to the given destination, then return this edge.
576 * Otherwise, return NULL.
578 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
579 enum isl_edge_type type
,
580 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
582 struct isl_hash_table_entry
*entry
;
584 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
591 /* Check whether the dependence graph has an edge of the given type
592 * between the given two nodes.
594 static int graph_has_edge(struct isl_sched_graph
*graph
,
595 enum isl_edge_type type
,
596 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
598 struct isl_sched_edge
*edge
;
601 edge
= graph_find_edge(graph
, type
, src
, dst
);
605 empty
= isl_map_plain_is_empty(edge
->map
);
612 /* Look for any edge with the same src, dst and map fields as "model".
614 * Return the matching edge if one can be found.
615 * Return "model" if no matching edge is found.
616 * Return NULL on error.
618 static struct isl_sched_edge
*graph_find_matching_edge(
619 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
621 enum isl_edge_type i
;
622 struct isl_sched_edge
*edge
;
624 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
627 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
630 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
640 /* Remove the given edge from all the edge_tables that refer to it.
642 static void graph_remove_edge(struct isl_sched_graph
*graph
,
643 struct isl_sched_edge
*edge
)
645 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
646 enum isl_edge_type i
;
648 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
649 struct isl_hash_table_entry
*entry
;
651 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
654 if (entry
->data
!= edge
)
656 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
660 /* Check whether the dependence graph has any edge
661 * between the given two nodes.
663 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
664 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
666 enum isl_edge_type i
;
669 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
670 r
= graph_has_edge(graph
, i
, src
, dst
);
678 /* Check whether the dependence graph has a validity edge
679 * between the given two nodes.
681 * Conditional validity edges are essentially validity edges that
682 * can be ignored if the corresponding condition edges are iteration private.
683 * Here, we are only checking for the presence of validity
684 * edges, so we need to consider the conditional validity edges too.
685 * In particular, this function is used during the detection
686 * of strongly connected components and we cannot ignore
687 * conditional validity edges during this detection.
689 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
690 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
694 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
698 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
701 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
702 int n_node
, int n_edge
)
707 graph
->n_edge
= n_edge
;
708 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
709 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
710 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
711 graph
->edge
= isl_calloc_array(ctx
,
712 struct isl_sched_edge
, graph
->n_edge
);
714 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
715 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
717 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
721 for(i
= 0; i
< graph
->n
; ++i
)
722 graph
->sorted
[i
] = i
;
727 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
731 isl_map_to_basic_set_free(graph
->intra_hmap
);
732 isl_map_to_basic_set_free(graph
->inter_hmap
);
735 for (i
= 0; i
< graph
->n
; ++i
) {
736 isl_space_free(graph
->node
[i
].space
);
737 isl_set_free(graph
->node
[i
].hull
);
738 isl_multi_aff_free(graph
->node
[i
].compress
);
739 isl_multi_aff_free(graph
->node
[i
].decompress
);
740 isl_mat_free(graph
->node
[i
].sched
);
741 isl_map_free(graph
->node
[i
].sched_map
);
742 isl_mat_free(graph
->node
[i
].cmap
);
743 isl_mat_free(graph
->node
[i
].cinv
);
745 free(graph
->node
[i
].band
);
746 free(graph
->node
[i
].band_id
);
747 free(graph
->node
[i
].coincident
);
753 for (i
= 0; i
< graph
->n_edge
; ++i
) {
754 isl_map_free(graph
->edge
[i
].map
);
755 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
756 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
760 for (i
= 0; i
<= isl_edge_last
; ++i
)
761 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
762 isl_hash_table_free(ctx
, graph
->node_table
);
763 isl_basic_set_free(graph
->lp
);
766 /* For each "set" on which this function is called, increment
767 * graph->n by one and update graph->maxvar.
769 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
771 struct isl_sched_graph
*graph
= user
;
772 int nvar
= isl_set_dim(set
, isl_dim_set
);
775 if (nvar
> graph
->maxvar
)
776 graph
->maxvar
= nvar
;
783 /* Compute the number of rows that should be allocated for the schedule.
784 * The graph can be split at most "n - 1" times, there can be at most
785 * two rows for each dimension in the iteration domains (in particular,
786 * we usually have one row, but it may be split by split_scaled),
787 * and there can be one extra row for ordering the statements.
788 * Note that if we have actually split "n - 1" times, then no ordering
789 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
791 static int compute_max_row(struct isl_sched_graph
*graph
,
792 __isl_keep isl_union_set
*domain
)
796 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
798 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
803 /* Does "bset" have any defining equalities for its set variables?
805 static int has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
812 n
= isl_basic_set_dim(bset
, isl_dim_set
);
813 for (i
= 0; i
< n
; ++i
) {
816 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
825 /* Add a new node to the graph representing the given space.
826 * "nvar" is the (possibly compressed) number of variables and
827 * may be smaller than then number of set variables in "space"
828 * if "compressed" is set.
829 * If "compressed" is set, then "hull" represents the constraints
830 * that were used to derive the compression, while "compress" and
831 * "decompress" map the original space to the compressed space and
833 * If "compressed" is not set, then "hull", "compress" and "decompress"
836 static int add_node(struct isl_sched_graph
*graph
, __isl_take isl_space
*space
,
837 int nvar
, int compressed
, __isl_take isl_set
*hull
,
838 __isl_take isl_multi_aff
*compress
,
839 __isl_take isl_multi_aff
*decompress
)
844 int *band
, *band_id
, *coincident
;
849 ctx
= isl_space_get_ctx(space
);
850 nparam
= isl_space_dim(space
, isl_dim_param
);
851 if (!ctx
->opt
->schedule_parametric
)
853 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
854 graph
->node
[graph
->n
].space
= space
;
855 graph
->node
[graph
->n
].nvar
= nvar
;
856 graph
->node
[graph
->n
].nparam
= nparam
;
857 graph
->node
[graph
->n
].sched
= sched
;
858 graph
->node
[graph
->n
].sched_map
= NULL
;
859 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
860 graph
->node
[graph
->n
].band
= band
;
861 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
862 graph
->node
[graph
->n
].band_id
= band_id
;
863 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
864 graph
->node
[graph
->n
].coincident
= coincident
;
865 graph
->node
[graph
->n
].compressed
= compressed
;
866 graph
->node
[graph
->n
].hull
= hull
;
867 graph
->node
[graph
->n
].compress
= compress
;
868 graph
->node
[graph
->n
].decompress
= decompress
;
871 if (!space
|| !sched
||
872 (graph
->max_row
&& (!band
|| !band_id
|| !coincident
)))
874 if (compressed
&& (!hull
|| !compress
|| !decompress
))
880 /* Add a new node to the graph representing the given set.
882 * If any of the set variables is defined by an equality, then
883 * we perform variable compression such that we can perform
884 * the scheduling on the compressed domain.
886 static int extract_node(__isl_take isl_set
*set
, void *user
)
894 isl_multi_aff
*compress
, *decompress
;
895 struct isl_sched_graph
*graph
= user
;
897 space
= isl_set_get_space(set
);
898 hull
= isl_set_affine_hull(set
);
899 hull
= isl_basic_set_remove_divs(hull
);
900 nvar
= isl_space_dim(space
, isl_dim_set
);
901 has_equality
= has_any_defining_equality(hull
);
903 if (has_equality
< 0)
906 isl_basic_set_free(hull
);
907 return add_node(graph
, space
, nvar
, 0, NULL
, NULL
, NULL
);
910 morph
= isl_basic_set_variable_compression(hull
, isl_dim_set
);
911 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
912 compress
= isl_morph_get_var_multi_aff(morph
);
913 morph
= isl_morph_inverse(morph
);
914 decompress
= isl_morph_get_var_multi_aff(morph
);
915 isl_morph_free(morph
);
917 hull_set
= isl_set_from_basic_set(hull
);
918 return add_node(graph
, space
, nvar
, 1, hull_set
, compress
, decompress
);
920 isl_basic_set_free(hull
);
921 isl_space_free(space
);
925 struct isl_extract_edge_data
{
926 enum isl_edge_type type
;
927 struct isl_sched_graph
*graph
;
930 /* Merge edge2 into edge1, freeing the contents of edge2.
931 * "type" is the type of the schedule constraint from which edge2 was
933 * Return 0 on success and -1 on failure.
935 * edge1 and edge2 are assumed to have the same value for the map field.
937 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
938 struct isl_sched_edge
*edge2
)
940 edge1
->validity
|= edge2
->validity
;
941 edge1
->coincidence
|= edge2
->coincidence
;
942 edge1
->proximity
|= edge2
->proximity
;
943 edge1
->condition
|= edge2
->condition
;
944 edge1
->conditional_validity
|= edge2
->conditional_validity
;
945 isl_map_free(edge2
->map
);
947 if (type
== isl_edge_condition
) {
948 if (!edge1
->tagged_condition
)
949 edge1
->tagged_condition
= edge2
->tagged_condition
;
951 edge1
->tagged_condition
=
952 isl_union_map_union(edge1
->tagged_condition
,
953 edge2
->tagged_condition
);
956 if (type
== isl_edge_conditional_validity
) {
957 if (!edge1
->tagged_validity
)
958 edge1
->tagged_validity
= edge2
->tagged_validity
;
960 edge1
->tagged_validity
=
961 isl_union_map_union(edge1
->tagged_validity
,
962 edge2
->tagged_validity
);
965 if (type
== isl_edge_condition
&& !edge1
->tagged_condition
)
967 if (type
== isl_edge_conditional_validity
&& !edge1
->tagged_validity
)
973 /* Insert dummy tags in domain and range of "map".
975 * In particular, if "map" is of the form
981 * [A -> dummy_tag] -> [B -> dummy_tag]
983 * where the dummy_tags are identical and equal to any dummy tags
984 * introduced by any other call to this function.
986 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
992 isl_set
*domain
, *range
;
994 ctx
= isl_map_get_ctx(map
);
996 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
997 space
= isl_space_params(isl_map_get_space(map
));
998 space
= isl_space_set_from_params(space
);
999 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1000 space
= isl_space_map_from_set(space
);
1002 domain
= isl_map_wrap(map
);
1003 range
= isl_map_wrap(isl_map_universe(space
));
1004 map
= isl_map_from_domain_and_range(domain
, range
);
1005 map
= isl_map_zip(map
);
1010 /* Given that at least one of "src" or "dst" is compressed, return
1011 * a map between the spaces of these nodes restricted to the affine
1012 * hull that was used in the compression.
1014 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1015 struct isl_sched_node
*dst
)
1019 if (src
->compressed
)
1020 dom
= isl_set_copy(src
->hull
);
1022 dom
= isl_set_universe(isl_space_copy(src
->space
));
1023 if (dst
->compressed
)
1024 ran
= isl_set_copy(dst
->hull
);
1026 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1028 return isl_map_from_domain_and_range(dom
, ran
);
1031 /* Intersect the domains of the nested relations in domain and range
1032 * of "tagged" with "map".
1034 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1035 __isl_keep isl_map
*map
)
1039 tagged
= isl_map_zip(tagged
);
1040 set
= isl_map_wrap(isl_map_copy(map
));
1041 tagged
= isl_map_intersect_domain(tagged
, set
);
1042 tagged
= isl_map_zip(tagged
);
1046 /* Add a new edge to the graph based on the given map
1047 * and add it to data->graph->edge_table[data->type].
1048 * If a dependence relation of a given type happens to be identical
1049 * to one of the dependence relations of a type that was added before,
1050 * then we don't create a new edge, but instead mark the original edge
1051 * as also representing a dependence of the current type.
1053 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1054 * may be specified as "tagged" dependence relations. That is, "map"
1055 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1056 * the dependence on iterations and a and b are tags.
1057 * edge->map is set to the relation containing the elements i -> j,
1058 * while edge->tagged_condition and edge->tagged_validity contain
1059 * the union of all the "map" relations
1060 * for which extract_edge is called that result in the same edge->map.
1062 * If the source or the destination node is compressed, then
1063 * intersect both "map" and "tagged" with the constraints that
1064 * were used to construct the compression.
1065 * This ensures that there are no schedule constraints defined
1066 * outside of these domains, while the scheduler no longer has
1067 * any control over those outside parts.
1069 static int extract_edge(__isl_take isl_map
*map
, void *user
)
1071 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1072 struct isl_extract_edge_data
*data
= user
;
1073 struct isl_sched_graph
*graph
= data
->graph
;
1074 struct isl_sched_node
*src
, *dst
;
1076 struct isl_sched_edge
*edge
;
1077 isl_map
*tagged
= NULL
;
1079 if (data
->type
== isl_edge_condition
||
1080 data
->type
== isl_edge_conditional_validity
) {
1081 if (isl_map_can_zip(map
)) {
1082 tagged
= isl_map_copy(map
);
1083 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1085 tagged
= insert_dummy_tags(isl_map_copy(map
));
1089 dim
= isl_space_domain(isl_map_get_space(map
));
1090 src
= graph_find_node(ctx
, graph
, dim
);
1091 isl_space_free(dim
);
1092 dim
= isl_space_range(isl_map_get_space(map
));
1093 dst
= graph_find_node(ctx
, graph
, dim
);
1094 isl_space_free(dim
);
1098 isl_map_free(tagged
);
1102 if (src
->compressed
|| dst
->compressed
) {
1104 hull
= extract_hull(src
, dst
);
1106 tagged
= map_intersect_domains(tagged
, hull
);
1107 map
= isl_map_intersect(map
, hull
);
1110 graph
->edge
[graph
->n_edge
].src
= src
;
1111 graph
->edge
[graph
->n_edge
].dst
= dst
;
1112 graph
->edge
[graph
->n_edge
].map
= map
;
1113 graph
->edge
[graph
->n_edge
].validity
= 0;
1114 graph
->edge
[graph
->n_edge
].coincidence
= 0;
1115 graph
->edge
[graph
->n_edge
].proximity
= 0;
1116 graph
->edge
[graph
->n_edge
].condition
= 0;
1117 graph
->edge
[graph
->n_edge
].local
= 0;
1118 graph
->edge
[graph
->n_edge
].conditional_validity
= 0;
1119 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1120 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1121 if (data
->type
== isl_edge_validity
)
1122 graph
->edge
[graph
->n_edge
].validity
= 1;
1123 if (data
->type
== isl_edge_coincidence
)
1124 graph
->edge
[graph
->n_edge
].coincidence
= 1;
1125 if (data
->type
== isl_edge_proximity
)
1126 graph
->edge
[graph
->n_edge
].proximity
= 1;
1127 if (data
->type
== isl_edge_condition
) {
1128 graph
->edge
[graph
->n_edge
].condition
= 1;
1129 graph
->edge
[graph
->n_edge
].tagged_condition
=
1130 isl_union_map_from_map(tagged
);
1132 if (data
->type
== isl_edge_conditional_validity
) {
1133 graph
->edge
[graph
->n_edge
].conditional_validity
= 1;
1134 graph
->edge
[graph
->n_edge
].tagged_validity
=
1135 isl_union_map_from_map(tagged
);
1138 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1143 if (edge
== &graph
->edge
[graph
->n_edge
])
1144 return graph_edge_table_add(ctx
, graph
, data
->type
,
1145 &graph
->edge
[graph
->n_edge
++]);
1147 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1150 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1153 /* Check whether there is any dependence from node[j] to node[i]
1154 * or from node[i] to node[j].
1156 static int node_follows_weak(int i
, int j
, void *user
)
1159 struct isl_sched_graph
*graph
= user
;
1161 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1164 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1167 /* Check whether there is a (conditional) validity dependence from node[j]
1168 * to node[i], forcing node[i] to follow node[j].
1170 static int node_follows_strong(int i
, int j
, void *user
)
1172 struct isl_sched_graph
*graph
= user
;
1174 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1177 /* Use Tarjan's algorithm for computing the strongly connected components
1178 * in the dependence graph (only validity edges).
1179 * If weak is set, we consider the graph to be undirected and
1180 * we effectively compute the (weakly) connected components.
1181 * Additionally, we also consider other edges when weak is set.
1183 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
1186 struct isl_tarjan_graph
*g
= NULL
;
1188 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
1189 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
1197 while (g
->order
[i
] != -1) {
1198 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1206 isl_tarjan_graph_free(g
);
1211 /* Apply Tarjan's algorithm to detect the strongly connected components
1212 * in the dependence graph.
1214 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1216 return detect_ccs(ctx
, graph
, 0);
1219 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1220 * in the dependence graph.
1222 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1224 return detect_ccs(ctx
, graph
, 1);
1227 static int cmp_scc(const void *a
, const void *b
, void *data
)
1229 struct isl_sched_graph
*graph
= data
;
1233 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1236 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1238 static int sort_sccs(struct isl_sched_graph
*graph
)
1240 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1243 /* Given a dependence relation R from "node" to itself,
1244 * construct the set of coefficients of valid constraints for elements
1245 * in that dependence relation.
1246 * In particular, the result contains tuples of coefficients
1247 * c_0, c_n, c_x such that
1249 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1253 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1255 * We choose here to compute the dual of delta R.
1256 * Alternatively, we could have computed the dual of R, resulting
1257 * in a set of tuples c_0, c_n, c_x, c_y, and then
1258 * plugged in (c_0, c_n, c_x, -c_x).
1260 * If "node" has been compressed, then the dependence relation
1261 * is also compressed before the set of coefficients is computed.
1263 static __isl_give isl_basic_set
*intra_coefficients(
1264 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1265 __isl_take isl_map
*map
)
1269 isl_basic_set
*coef
;
1271 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1272 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1274 key
= isl_map_copy(map
);
1275 if (node
->compressed
) {
1276 map
= isl_map_preimage_domain_multi_aff(map
,
1277 isl_multi_aff_copy(node
->decompress
));
1278 map
= isl_map_preimage_range_multi_aff(map
,
1279 isl_multi_aff_copy(node
->decompress
));
1281 delta
= isl_set_remove_divs(isl_map_deltas(map
));
1282 coef
= isl_set_coefficients(delta
);
1283 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, key
,
1284 isl_basic_set_copy(coef
));
1289 /* Given a dependence relation R, construct the set of coefficients
1290 * of valid constraints for elements in that dependence relation.
1291 * In particular, the result contains tuples of coefficients
1292 * c_0, c_n, c_x, c_y such that
1294 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1296 * If the source or destination nodes of "edge" have been compressed,
1297 * then the dependence relation is also compressed before
1298 * the set of coefficients is computed.
1300 static __isl_give isl_basic_set
*inter_coefficients(
1301 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1302 __isl_take isl_map
*map
)
1306 isl_basic_set
*coef
;
1308 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1309 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1311 key
= isl_map_copy(map
);
1312 if (edge
->src
->compressed
)
1313 map
= isl_map_preimage_domain_multi_aff(map
,
1314 isl_multi_aff_copy(edge
->src
->decompress
));
1315 if (edge
->dst
->compressed
)
1316 map
= isl_map_preimage_range_multi_aff(map
,
1317 isl_multi_aff_copy(edge
->dst
->decompress
));
1318 set
= isl_map_wrap(isl_map_remove_divs(map
));
1319 coef
= isl_set_coefficients(set
);
1320 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1321 isl_basic_set_copy(coef
));
1326 /* Add constraints to graph->lp that force validity for the given
1327 * dependence from a node i to itself.
1328 * That is, add constraints that enforce
1330 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1331 * = c_i_x (y - x) >= 0
1333 * for each (x,y) in R.
1334 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1335 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1336 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1337 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1339 * Actually, we do not construct constraints for the c_i_x themselves,
1340 * but for the coefficients of c_i_x written as a linear combination
1341 * of the columns in node->cmap.
1343 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1344 struct isl_sched_edge
*edge
)
1347 isl_map
*map
= isl_map_copy(edge
->map
);
1348 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1350 isl_dim_map
*dim_map
;
1351 isl_basic_set
*coef
;
1352 struct isl_sched_node
*node
= edge
->src
;
1354 coef
= intra_coefficients(graph
, node
, map
);
1356 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1358 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1359 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1363 total
= isl_basic_set_total_dim(graph
->lp
);
1364 dim_map
= isl_dim_map_alloc(ctx
, total
);
1365 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1366 isl_space_dim(dim
, isl_dim_set
), 1,
1368 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1369 isl_space_dim(dim
, isl_dim_set
), 1,
1371 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1372 coef
->n_eq
, coef
->n_ineq
);
1373 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1375 isl_space_free(dim
);
1379 isl_space_free(dim
);
1383 /* Add constraints to graph->lp that force validity for the given
1384 * dependence from node i to node j.
1385 * That is, add constraints that enforce
1387 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1389 * for each (x,y) in R.
1390 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1391 * of valid constraints for R and then plug in
1392 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1393 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1394 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1395 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1397 * Actually, we do not construct constraints for the c_*_x themselves,
1398 * but for the coefficients of c_*_x written as a linear combination
1399 * of the columns in node->cmap.
1401 static int add_inter_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
*src
= edge
->src
;
1411 struct isl_sched_node
*dst
= edge
->dst
;
1413 coef
= inter_coefficients(graph
, edge
, map
);
1415 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1417 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1418 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1419 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1420 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1421 isl_mat_copy(dst
->cmap
));
1425 total
= isl_basic_set_total_dim(graph
->lp
);
1426 dim_map
= isl_dim_map_alloc(ctx
, total
);
1428 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1429 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1430 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1431 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1432 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1434 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1435 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1438 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1439 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1440 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1441 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1442 isl_space_dim(dim
, isl_dim_set
), 1,
1444 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1445 isl_space_dim(dim
, isl_dim_set
), 1,
1448 edge
->start
= graph
->lp
->n_ineq
;
1449 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1450 coef
->n_eq
, coef
->n_ineq
);
1451 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1455 isl_space_free(dim
);
1456 edge
->end
= graph
->lp
->n_ineq
;
1460 isl_space_free(dim
);
1464 /* Add constraints to graph->lp that bound the dependence distance for the given
1465 * dependence from a node i to itself.
1466 * If s = 1, we add the constraint
1468 * c_i_x (y - x) <= m_0 + m_n n
1472 * -c_i_x (y - x) + m_0 + m_n n >= 0
1474 * for each (x,y) in R.
1475 * If s = -1, we add the constraint
1477 * -c_i_x (y - x) <= m_0 + m_n n
1481 * c_i_x (y - x) + m_0 + m_n n >= 0
1483 * for each (x,y) in R.
1484 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1485 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1486 * with each coefficient (except m_0) represented as a pair of non-negative
1489 * Actually, we do not construct constraints for the c_i_x themselves,
1490 * but for the coefficients of c_i_x written as a linear combination
1491 * of the columns in node->cmap.
1494 * If "local" is set, then we add constraints
1496 * c_i_x (y - x) <= 0
1500 * -c_i_x (y - x) <= 0
1502 * instead, forcing the dependence distance to be (less than or) equal to 0.
1503 * That is, we plug in (0, 0, -s * c_i_x),
1504 * Note that dependences marked local are treated as validity constraints
1505 * by add_all_validity_constraints and therefore also have
1506 * their distances bounded by 0 from below.
1508 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1509 struct isl_sched_edge
*edge
, int s
, int local
)
1513 isl_map
*map
= isl_map_copy(edge
->map
);
1514 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1516 isl_dim_map
*dim_map
;
1517 isl_basic_set
*coef
;
1518 struct isl_sched_node
*node
= edge
->src
;
1520 coef
= intra_coefficients(graph
, node
, map
);
1522 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1524 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1525 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1529 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
1530 total
= isl_basic_set_total_dim(graph
->lp
);
1531 dim_map
= isl_dim_map_alloc(ctx
, total
);
1534 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1535 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1536 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1538 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1539 isl_space_dim(dim
, isl_dim_set
), 1,
1541 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1542 isl_space_dim(dim
, isl_dim_set
), 1,
1544 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1545 coef
->n_eq
, coef
->n_ineq
);
1546 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1548 isl_space_free(dim
);
1552 isl_space_free(dim
);
1556 /* Add constraints to graph->lp that bound the dependence distance for the given
1557 * dependence from node i to node j.
1558 * If s = 1, we add the constraint
1560 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1565 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1568 * for each (x,y) in R.
1569 * If s = -1, we add the constraint
1571 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1576 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1579 * for each (x,y) in R.
1580 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1581 * of valid constraints for R and then plug in
1582 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1584 * with each coefficient (except m_0, c_j_0 and c_i_0)
1585 * represented as a pair of non-negative coefficients.
1587 * Actually, we do not construct constraints for the c_*_x themselves,
1588 * but for the coefficients of c_*_x written as a linear combination
1589 * of the columns in node->cmap.
1592 * If "local" is set, then we add constraints
1594 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1598 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1600 * instead, forcing the dependence distance to be (less than or) equal to 0.
1601 * That is, we plug in
1602 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1603 * Note that dependences marked local are treated as validity constraints
1604 * by add_all_validity_constraints and therefore also have
1605 * their distances bounded by 0 from below.
1607 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1608 struct isl_sched_edge
*edge
, int s
, int local
)
1612 isl_map
*map
= isl_map_copy(edge
->map
);
1613 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1615 isl_dim_map
*dim_map
;
1616 isl_basic_set
*coef
;
1617 struct isl_sched_node
*src
= edge
->src
;
1618 struct isl_sched_node
*dst
= edge
->dst
;
1620 coef
= inter_coefficients(graph
, edge
, map
);
1622 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1624 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1625 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1626 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1627 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1628 isl_mat_copy(dst
->cmap
));
1632 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
1633 total
= isl_basic_set_total_dim(graph
->lp
);
1634 dim_map
= isl_dim_map_alloc(ctx
, total
);
1637 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1638 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1639 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1642 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1643 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1644 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1645 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1646 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1648 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1649 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1652 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1653 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1654 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1655 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1656 isl_space_dim(dim
, isl_dim_set
), 1,
1658 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1659 isl_space_dim(dim
, isl_dim_set
), 1,
1662 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1663 coef
->n_eq
, coef
->n_ineq
);
1664 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1666 isl_space_free(dim
);
1670 isl_space_free(dim
);
1674 /* Add all validity constraints to graph->lp.
1676 * An edge that is forced to be local needs to have its dependence
1677 * distances equal to zero. We take care of bounding them by 0 from below
1678 * here. add_all_proximity_constraints takes care of bounding them by 0
1681 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1682 * Otherwise, we ignore them.
1684 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1685 int use_coincidence
)
1689 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1690 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1693 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1694 if (!edge
->validity
&& !local
)
1696 if (edge
->src
!= edge
->dst
)
1698 if (add_intra_validity_constraints(graph
, edge
) < 0)
1702 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1703 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1706 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1707 if (!edge
->validity
&& !local
)
1709 if (edge
->src
== edge
->dst
)
1711 if (add_inter_validity_constraints(graph
, edge
) < 0)
1718 /* Add constraints to graph->lp that bound the dependence distance
1719 * for all dependence relations.
1720 * If a given proximity dependence is identical to a validity
1721 * dependence, then the dependence distance is already bounded
1722 * from below (by zero), so we only need to bound the distance
1723 * from above. (This includes the case of "local" dependences
1724 * which are treated as validity dependence by add_all_validity_constraints.)
1725 * Otherwise, we need to bound the distance both from above and from below.
1727 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1728 * Otherwise, we ignore them.
1730 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
1731 int use_coincidence
)
1735 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1736 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1739 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1740 if (!edge
->proximity
&& !local
)
1742 if (edge
->src
== edge
->dst
&&
1743 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
1745 if (edge
->src
!= edge
->dst
&&
1746 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
1748 if (edge
->validity
|| local
)
1750 if (edge
->src
== edge
->dst
&&
1751 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
1753 if (edge
->src
!= edge
->dst
&&
1754 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
1761 /* Compute a basis for the rows in the linear part of the schedule
1762 * and extend this basis to a full basis. The remaining rows
1763 * can then be used to force linear independence from the rows
1766 * In particular, given the schedule rows S, we compute
1771 * with H the Hermite normal form of S. That is, all but the
1772 * first rank columns of H are zero and so each row in S is
1773 * a linear combination of the first rank rows of Q.
1774 * The matrix Q is then transposed because we will write the
1775 * coefficients of the next schedule row as a column vector s
1776 * and express this s as a linear combination s = Q c of the
1778 * Similarly, the matrix U is transposed such that we can
1779 * compute the coefficients c = U s from a schedule row s.
1781 static int node_update_cmap(struct isl_sched_node
*node
)
1784 int n_row
= isl_mat_rows(node
->sched
);
1786 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1787 1 + node
->nparam
, node
->nvar
);
1789 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1790 isl_mat_free(node
->cmap
);
1791 isl_mat_free(node
->cinv
);
1792 node
->cmap
= isl_mat_transpose(Q
);
1793 node
->cinv
= isl_mat_transpose(U
);
1794 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1797 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1802 /* How many times should we count the constraints in "edge"?
1804 * If carry is set, then we are counting the number of
1805 * (validity or conditional validity) constraints that will be added
1806 * in setup_carry_lp and we count each edge exactly once.
1808 * Otherwise, we count as follows
1809 * validity -> 1 (>= 0)
1810 * validity+proximity -> 2 (>= 0 and upper bound)
1811 * proximity -> 2 (lower and upper bound)
1812 * local(+any) -> 2 (>= 0 and <= 0)
1814 * If an edge is only marked conditional_validity then it counts
1815 * as zero since it is only checked afterwards.
1817 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1818 * Otherwise, we ignore them.
1820 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
1821 int use_coincidence
)
1823 if (carry
&& !edge
->validity
&& !edge
->conditional_validity
)
1827 if (edge
->proximity
|| edge
->local
)
1829 if (use_coincidence
&& edge
->coincidence
)
1836 /* Count the number of equality and inequality constraints
1837 * that will be added for the given map.
1839 * "use_coincidence" is set if we should take into account coincidence edges.
1841 static int count_map_constraints(struct isl_sched_graph
*graph
,
1842 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1843 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
1845 isl_basic_set
*coef
;
1846 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
1853 if (edge
->src
== edge
->dst
)
1854 coef
= intra_coefficients(graph
, edge
->src
, map
);
1856 coef
= inter_coefficients(graph
, edge
, map
);
1859 *n_eq
+= f
* coef
->n_eq
;
1860 *n_ineq
+= f
* coef
->n_ineq
;
1861 isl_basic_set_free(coef
);
1866 /* Count the number of equality and inequality constraints
1867 * that will be added to the main lp problem.
1868 * We count as follows
1869 * validity -> 1 (>= 0)
1870 * validity+proximity -> 2 (>= 0 and upper bound)
1871 * proximity -> 2 (lower and upper bound)
1872 * local(+any) -> 2 (>= 0 and <= 0)
1874 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1875 * Otherwise, we ignore them.
1877 static int count_constraints(struct isl_sched_graph
*graph
,
1878 int *n_eq
, int *n_ineq
, int use_coincidence
)
1882 *n_eq
= *n_ineq
= 0;
1883 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1884 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1885 isl_map
*map
= isl_map_copy(edge
->map
);
1887 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
1888 0, use_coincidence
) < 0)
1895 /* Count the number of constraints that will be added by
1896 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1899 * In practice, add_bound_coefficient_constraints only adds inequalities.
1901 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1902 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1906 if (ctx
->opt
->schedule_max_coefficient
== -1)
1909 for (i
= 0; i
< graph
->n
; ++i
)
1910 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1915 /* Add constraints that bound the values of the variable and parameter
1916 * coefficients of the schedule.
1918 * The maximal value of the coefficients is defined by the option
1919 * 'schedule_max_coefficient'.
1921 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1922 struct isl_sched_graph
*graph
)
1925 int max_coefficient
;
1928 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1930 if (max_coefficient
== -1)
1933 total
= isl_basic_set_total_dim(graph
->lp
);
1935 for (i
= 0; i
< graph
->n
; ++i
) {
1936 struct isl_sched_node
*node
= &graph
->node
[i
];
1937 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1939 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1942 dim
= 1 + node
->start
+ 1 + j
;
1943 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1944 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1945 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1952 /* Construct an ILP problem for finding schedule coefficients
1953 * that result in non-negative, but small dependence distances
1954 * over all dependences.
1955 * In particular, the dependence distances over proximity edges
1956 * are bounded by m_0 + m_n n and we compute schedule coefficients
1957 * with small values (preferably zero) of m_n and m_0.
1959 * All variables of the ILP are non-negative. The actual coefficients
1960 * may be negative, so each coefficient is represented as the difference
1961 * of two non-negative variables. The negative part always appears
1962 * immediately before the positive part.
1963 * Other than that, the variables have the following order
1965 * - sum of positive and negative parts of m_n coefficients
1967 * - sum of positive and negative parts of all c_n coefficients
1968 * (unconstrained when computing non-parametric schedules)
1969 * - sum of positive and negative parts of all c_x coefficients
1970 * - positive and negative parts of m_n coefficients
1973 * - positive and negative parts of c_i_n (if parametric)
1974 * - positive and negative parts of c_i_x
1976 * The c_i_x are not represented directly, but through the columns of
1977 * node->cmap. That is, the computed values are for variable t_i_x
1978 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1980 * The constraints are those from the edges plus two or three equalities
1981 * to express the sums.
1983 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1984 * Otherwise, we ignore them.
1986 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1987 int use_coincidence
)
1997 int max_constant_term
;
1999 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
2001 parametric
= ctx
->opt
->schedule_parametric
;
2002 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2004 total
= param_pos
+ 2 * nparam
;
2005 for (i
= 0; i
< graph
->n
; ++i
) {
2006 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2007 if (node_update_cmap(node
) < 0)
2009 node
->start
= total
;
2010 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2013 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2015 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2018 dim
= isl_space_set_alloc(ctx
, 0, total
);
2019 isl_basic_set_free(graph
->lp
);
2020 n_eq
+= 2 + parametric
;
2021 if (max_constant_term
!= -1)
2024 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2026 k
= isl_basic_set_alloc_equality(graph
->lp
);
2029 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2030 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
2031 for (i
= 0; i
< 2 * nparam
; ++i
)
2032 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
2035 k
= isl_basic_set_alloc_equality(graph
->lp
);
2038 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2039 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2040 for (i
= 0; i
< graph
->n
; ++i
) {
2041 int pos
= 1 + graph
->node
[i
].start
+ 1;
2043 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2044 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2048 k
= isl_basic_set_alloc_equality(graph
->lp
);
2051 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2052 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
2053 for (i
= 0; i
< graph
->n
; ++i
) {
2054 struct isl_sched_node
*node
= &graph
->node
[i
];
2055 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2057 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2058 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2061 if (max_constant_term
!= -1)
2062 for (i
= 0; i
< graph
->n
; ++i
) {
2063 struct isl_sched_node
*node
= &graph
->node
[i
];
2064 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2067 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2068 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
2069 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
2072 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2074 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2076 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2082 /* Analyze the conflicting constraint found by
2083 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2084 * constraint of one of the edges between distinct nodes, living, moreover
2085 * in distinct SCCs, then record the source and sink SCC as this may
2086 * be a good place to cut between SCCs.
2088 static int check_conflict(int con
, void *user
)
2091 struct isl_sched_graph
*graph
= user
;
2093 if (graph
->src_scc
>= 0)
2096 con
-= graph
->lp
->n_eq
;
2098 if (con
>= graph
->lp
->n_ineq
)
2101 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2102 if (!graph
->edge
[i
].validity
)
2104 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2106 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2108 if (graph
->edge
[i
].start
> con
)
2110 if (graph
->edge
[i
].end
<= con
)
2112 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2113 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2119 /* Check whether the next schedule row of the given node needs to be
2120 * non-trivial. Lower-dimensional domains may have some trivial rows,
2121 * but as soon as the number of remaining required non-trivial rows
2122 * is as large as the number or remaining rows to be computed,
2123 * all remaining rows need to be non-trivial.
2125 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2127 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2130 /* Solve the ILP problem constructed in setup_lp.
2131 * For each node such that all the remaining rows of its schedule
2132 * need to be non-trivial, we construct a non-triviality region.
2133 * This region imposes that the next row is independent of previous rows.
2134 * In particular the coefficients c_i_x are represented by t_i_x
2135 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2136 * its first columns span the rows of the previously computed part
2137 * of the schedule. The non-triviality region enforces that at least
2138 * one of the remaining components of t_i_x is non-zero, i.e.,
2139 * that the new schedule row depends on at least one of the remaining
2142 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
2148 for (i
= 0; i
< graph
->n
; ++i
) {
2149 struct isl_sched_node
*node
= &graph
->node
[i
];
2150 int skip
= node
->rank
;
2151 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
2152 if (needs_row(graph
, node
))
2153 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
2155 graph
->region
[i
].len
= 0;
2157 lp
= isl_basic_set_copy(graph
->lp
);
2158 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2159 graph
->region
, &check_conflict
, graph
);
2163 /* Update the schedules of all nodes based on the given solution
2164 * of the LP problem.
2165 * The new row is added to the current band.
2166 * All possibly negative coefficients are encoded as a difference
2167 * of two non-negative variables, so we need to perform the subtraction
2168 * here. Moreover, if use_cmap is set, then the solution does
2169 * not refer to the actual coefficients c_i_x, but instead to variables
2170 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2171 * In this case, we then also need to perform this multiplication
2172 * to obtain the values of c_i_x.
2174 * If coincident is set, then the caller guarantees that the new
2175 * row satisfies the coincidence constraints.
2177 static int update_schedule(struct isl_sched_graph
*graph
,
2178 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2181 isl_vec
*csol
= NULL
;
2186 isl_die(sol
->ctx
, isl_error_internal
,
2187 "no solution found", goto error
);
2188 if (graph
->n_total_row
>= graph
->max_row
)
2189 isl_die(sol
->ctx
, isl_error_internal
,
2190 "too many schedule rows", goto error
);
2192 for (i
= 0; i
< graph
->n
; ++i
) {
2193 struct isl_sched_node
*node
= &graph
->node
[i
];
2194 int pos
= node
->start
;
2195 int row
= isl_mat_rows(node
->sched
);
2198 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2202 isl_map_free(node
->sched_map
);
2203 node
->sched_map
= NULL
;
2204 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2207 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2209 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2210 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2211 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2212 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2213 for (j
= 0; j
< node
->nparam
; ++j
)
2214 node
->sched
= isl_mat_set_element(node
->sched
,
2215 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2216 for (j
= 0; j
< node
->nvar
; ++j
)
2217 isl_int_set(csol
->el
[j
],
2218 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2220 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2224 for (j
= 0; j
< node
->nvar
; ++j
)
2225 node
->sched
= isl_mat_set_element(node
->sched
,
2226 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2227 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2228 node
->coincident
[graph
->n_total_row
] = coincident
;
2234 graph
->n_total_row
++;
2243 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2244 * and return this isl_aff.
2246 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2247 struct isl_sched_node
*node
, int row
)
2255 aff
= isl_aff_zero_on_domain(ls
);
2256 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2257 aff
= isl_aff_set_constant(aff
, v
);
2258 for (j
= 0; j
< node
->nparam
; ++j
) {
2259 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2260 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2262 for (j
= 0; j
< node
->nvar
; ++j
) {
2263 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2264 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2272 /* Convert node->sched into a multi_aff and return this multi_aff.
2274 * The result is defined over the uncompressed node domain.
2276 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2277 struct isl_sched_node
*node
)
2281 isl_local_space
*ls
;
2286 nrow
= isl_mat_rows(node
->sched
);
2287 ncol
= isl_mat_cols(node
->sched
) - 1;
2288 if (node
->compressed
)
2289 space
= isl_multi_aff_get_domain_space(node
->decompress
);
2291 space
= isl_space_copy(node
->space
);
2292 ls
= isl_local_space_from_space(isl_space_copy(space
));
2293 space
= isl_space_from_domain(space
);
2294 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
2295 ma
= isl_multi_aff_zero(space
);
2297 for (i
= 0; i
< nrow
; ++i
) {
2298 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2299 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
2302 isl_local_space_free(ls
);
2304 if (node
->compressed
)
2305 ma
= isl_multi_aff_pullback_multi_aff(ma
,
2306 isl_multi_aff_copy(node
->compress
));
2311 /* Convert node->sched into a map and return this map.
2313 * The result is cached in node->sched_map, which needs to be released
2314 * whenever node->sched is updated.
2315 * It is defined over the uncompressed node domain.
2317 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2319 if (!node
->sched_map
) {
2322 ma
= node_extract_schedule_multi_aff(node
);
2323 node
->sched_map
= isl_map_from_multi_aff(ma
);
2326 return isl_map_copy(node
->sched_map
);
2329 /* Construct a map that can be used to update a dependence relation
2330 * based on the current schedule.
2331 * That is, construct a map expressing that source and sink
2332 * are executed within the same iteration of the current schedule.
2333 * This map can then be intersected with the dependence relation.
2334 * This is not the most efficient way, but this shouldn't be a critical
2337 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2338 struct isl_sched_node
*dst
)
2340 isl_map
*src_sched
, *dst_sched
;
2342 src_sched
= node_extract_schedule(src
);
2343 dst_sched
= node_extract_schedule(dst
);
2344 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2347 /* Intersect the domains of the nested relations in domain and range
2348 * of "umap" with "map".
2350 static __isl_give isl_union_map
*intersect_domains(
2351 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2353 isl_union_set
*uset
;
2355 umap
= isl_union_map_zip(umap
);
2356 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2357 umap
= isl_union_map_intersect_domain(umap
, uset
);
2358 umap
= isl_union_map_zip(umap
);
2362 /* Update the dependence relation of the given edge based
2363 * on the current schedule.
2364 * If the dependence is carried completely by the current schedule, then
2365 * it is removed from the edge_tables. It is kept in the list of edges
2366 * as otherwise all edge_tables would have to be recomputed.
2368 static int update_edge(struct isl_sched_graph
*graph
,
2369 struct isl_sched_edge
*edge
)
2373 id
= specializer(edge
->src
, edge
->dst
);
2374 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2378 if (edge
->tagged_condition
) {
2379 edge
->tagged_condition
=
2380 intersect_domains(edge
->tagged_condition
, id
);
2381 if (!edge
->tagged_condition
)
2384 if (edge
->tagged_validity
) {
2385 edge
->tagged_validity
=
2386 intersect_domains(edge
->tagged_validity
, id
);
2387 if (!edge
->tagged_validity
)
2392 if (isl_map_plain_is_empty(edge
->map
))
2393 graph_remove_edge(graph
, edge
);
2401 /* Update the dependence relations of all edges based on the current schedule.
2403 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2407 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2408 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2415 static void next_band(struct isl_sched_graph
*graph
)
2417 graph
->band_start
= graph
->n_total_row
;
2421 /* Topologically sort statements mapped to the same schedule iteration
2422 * and add a row to the schedule corresponding to this order.
2424 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2431 if (update_edges(ctx
, graph
) < 0)
2434 if (graph
->n_edge
== 0)
2437 if (detect_sccs(ctx
, graph
) < 0)
2440 if (graph
->n_total_row
>= graph
->max_row
)
2441 isl_die(ctx
, isl_error_internal
,
2442 "too many schedule rows", return -1);
2444 for (i
= 0; i
< graph
->n
; ++i
) {
2445 struct isl_sched_node
*node
= &graph
->node
[i
];
2446 int row
= isl_mat_rows(node
->sched
);
2447 int cols
= isl_mat_cols(node
->sched
);
2449 isl_map_free(node
->sched_map
);
2450 node
->sched_map
= NULL
;
2451 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2454 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2456 for (j
= 1; j
< cols
; ++j
)
2457 node
->sched
= isl_mat_set_element_si(node
->sched
,
2459 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2462 graph
->n_total_row
++;
2468 /* Construct an isl_schedule based on the computed schedule stored
2469 * in graph and with parameters specified by dim.
2471 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
2472 __isl_take isl_space
*dim
)
2476 isl_schedule
*sched
= NULL
;
2481 ctx
= isl_space_get_ctx(dim
);
2482 sched
= isl_calloc(ctx
, struct isl_schedule
,
2483 sizeof(struct isl_schedule
) +
2484 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
2489 sched
->n
= graph
->n
;
2490 sched
->n_band
= graph
->n_band
;
2491 sched
->n_total_row
= graph
->n_total_row
;
2493 for (i
= 0; i
< sched
->n
; ++i
) {
2495 int *band_end
, *band_id
, *coincident
;
2497 sched
->node
[i
].sched
=
2498 node_extract_schedule_multi_aff(&graph
->node
[i
]);
2499 if (!sched
->node
[i
].sched
)
2502 sched
->node
[i
].n_band
= graph
->n_band
;
2503 if (graph
->n_band
== 0)
2506 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
2507 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
2508 coincident
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
2509 sched
->node
[i
].band_end
= band_end
;
2510 sched
->node
[i
].band_id
= band_id
;
2511 sched
->node
[i
].coincident
= coincident
;
2512 if (!band_end
|| !band_id
|| !coincident
)
2515 for (r
= 0; r
< graph
->n_total_row
; ++r
)
2516 coincident
[r
] = graph
->node
[i
].coincident
[r
];
2517 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
2518 if (graph
->node
[i
].band
[r
] == b
)
2521 if (graph
->node
[i
].band
[r
] == -1)
2524 if (r
== graph
->n_total_row
)
2526 sched
->node
[i
].n_band
= b
;
2527 for (--b
; b
>= 0; --b
)
2528 band_id
[b
] = graph
->node
[i
].band_id
[b
];
2535 isl_space_free(dim
);
2536 isl_schedule_free(sched
);
2540 /* Copy nodes that satisfy node_pred from the src dependence graph
2541 * to the dst dependence graph.
2543 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2544 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2549 for (i
= 0; i
< src
->n
; ++i
) {
2552 if (!node_pred(&src
->node
[i
], data
))
2556 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
2557 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
2558 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
2559 dst
->node
[j
].compress
=
2560 isl_multi_aff_copy(src
->node
[i
].compress
);
2561 dst
->node
[j
].decompress
=
2562 isl_multi_aff_copy(src
->node
[i
].decompress
);
2563 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
2564 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
2565 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2566 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
2567 dst
->node
[j
].band
= src
->node
[i
].band
;
2568 dst
->node
[j
].band_id
= src
->node
[i
].band_id
;
2569 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
2572 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
2574 if (dst
->node
[j
].compressed
&&
2575 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
2576 !dst
->node
[j
].decompress
))
2583 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2584 * to the dst dependence graph.
2585 * If the source or destination node of the edge is not in the destination
2586 * graph, then it must be a backward proximity edge and it should simply
2589 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2590 struct isl_sched_graph
*src
,
2591 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2594 enum isl_edge_type t
;
2597 for (i
= 0; i
< src
->n_edge
; ++i
) {
2598 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2600 isl_union_map
*tagged_condition
;
2601 isl_union_map
*tagged_validity
;
2602 struct isl_sched_node
*dst_src
, *dst_dst
;
2604 if (!edge_pred(edge
, data
))
2607 if (isl_map_plain_is_empty(edge
->map
))
2610 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->space
);
2611 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->space
);
2612 if (!dst_src
|| !dst_dst
) {
2613 if (edge
->validity
|| edge
->conditional_validity
)
2614 isl_die(ctx
, isl_error_internal
,
2615 "backward (conditional) validity edge",
2620 map
= isl_map_copy(edge
->map
);
2621 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
2622 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
2624 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2625 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2626 dst
->edge
[dst
->n_edge
].map
= map
;
2627 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
2628 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
2629 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2630 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2631 dst
->edge
[dst
->n_edge
].coincidence
= edge
->coincidence
;
2632 dst
->edge
[dst
->n_edge
].condition
= edge
->condition
;
2633 dst
->edge
[dst
->n_edge
].conditional_validity
=
2634 edge
->conditional_validity
;
2637 if (edge
->tagged_condition
&& !tagged_condition
)
2639 if (edge
->tagged_validity
&& !tagged_validity
)
2642 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2644 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2646 if (graph_edge_table_add(ctx
, dst
, t
,
2647 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2655 /* Given a "src" dependence graph that contains the nodes from "dst"
2656 * that satisfy node_pred, copy the schedule computed in "src"
2657 * for those nodes back to "dst".
2659 static int copy_schedule(struct isl_sched_graph
*dst
,
2660 struct isl_sched_graph
*src
,
2661 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2666 for (i
= 0; i
< dst
->n
; ++i
) {
2667 if (!node_pred(&dst
->node
[i
], data
))
2669 isl_mat_free(dst
->node
[i
].sched
);
2670 isl_map_free(dst
->node
[i
].sched_map
);
2671 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
2672 dst
->node
[i
].sched_map
=
2673 isl_map_copy(src
->node
[src
->n
].sched_map
);
2677 dst
->max_row
= src
->max_row
;
2678 dst
->n_total_row
= src
->n_total_row
;
2679 dst
->n_band
= src
->n_band
;
2684 /* Compute the maximal number of variables over all nodes.
2685 * This is the maximal number of linearly independent schedule
2686 * rows that we need to compute.
2687 * Just in case we end up in a part of the dependence graph
2688 * with only lower-dimensional domains, we make sure we will
2689 * compute the required amount of extra linearly independent rows.
2691 static int compute_maxvar(struct isl_sched_graph
*graph
)
2696 for (i
= 0; i
< graph
->n
; ++i
) {
2697 struct isl_sched_node
*node
= &graph
->node
[i
];
2700 if (node_update_cmap(node
) < 0)
2702 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2703 if (nvar
> graph
->maxvar
)
2704 graph
->maxvar
= nvar
;
2710 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2711 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2713 /* Compute a schedule for a subgraph of "graph". In particular, for
2714 * the graph composed of nodes that satisfy node_pred and edges that
2715 * that satisfy edge_pred. The caller should precompute the number
2716 * of nodes and edges that satisfy these predicates and pass them along
2717 * as "n" and "n_edge".
2718 * If the subgraph is known to consist of a single component, then wcc should
2719 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2720 * Otherwise, we call compute_schedule, which will check whether the subgraph
2723 static int compute_sub_schedule(isl_ctx
*ctx
,
2724 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2725 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2726 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2729 struct isl_sched_graph split
= { 0 };
2732 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2734 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2736 if (graph_init_table(ctx
, &split
) < 0)
2738 for (t
= 0; t
<= isl_edge_last
; ++t
)
2739 split
.max_edge
[t
] = graph
->max_edge
[t
];
2740 if (graph_init_edge_tables(ctx
, &split
) < 0)
2742 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2744 split
.n_row
= graph
->n_row
;
2745 split
.max_row
= graph
->max_row
;
2746 split
.n_total_row
= graph
->n_total_row
;
2747 split
.n_band
= graph
->n_band
;
2748 split
.band_start
= graph
->band_start
;
2750 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2752 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2755 copy_schedule(graph
, &split
, node_pred
, data
);
2757 graph_free(ctx
, &split
);
2760 graph_free(ctx
, &split
);
2764 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2766 return node
->scc
== scc
;
2769 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2771 return node
->scc
<= scc
;
2774 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2776 return node
->scc
>= scc
;
2779 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2781 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2784 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2786 return edge
->dst
->scc
<= scc
;
2789 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2791 return edge
->src
->scc
>= scc
;
2794 /* Pad the schedules of all nodes with zero rows such that in the end
2795 * they all have graph->n_total_row rows.
2796 * The extra rows don't belong to any band, so they get assigned band number -1.
2798 static int pad_schedule(struct isl_sched_graph
*graph
)
2802 for (i
= 0; i
< graph
->n
; ++i
) {
2803 struct isl_sched_node
*node
= &graph
->node
[i
];
2804 int row
= isl_mat_rows(node
->sched
);
2805 if (graph
->n_total_row
> row
) {
2806 isl_map_free(node
->sched_map
);
2807 node
->sched_map
= NULL
;
2809 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2810 graph
->n_total_row
- row
);
2813 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2820 /* Reset the current band by dropping all its schedule rows.
2822 static int reset_band(struct isl_sched_graph
*graph
)
2827 drop
= graph
->n_total_row
- graph
->band_start
;
2828 graph
->n_total_row
-= drop
;
2829 graph
->n_row
-= drop
;
2831 for (i
= 0; i
< graph
->n
; ++i
) {
2832 struct isl_sched_node
*node
= &graph
->node
[i
];
2834 isl_map_free(node
->sched_map
);
2835 node
->sched_map
= NULL
;
2837 node
->sched
= isl_mat_drop_rows(node
->sched
,
2838 graph
->band_start
, drop
);
2847 /* Split the current graph into two parts and compute a schedule for each
2848 * part individually. In particular, one part consists of all SCCs up
2849 * to and including graph->src_scc, while the other part contains the other
2852 * The split is enforced in the schedule by constant rows with two different
2853 * values (0 and 1). These constant rows replace the previously computed rows
2854 * in the current band.
2855 * It would be possible to reuse them as the first rows in the next
2856 * band, but recomputing them may result in better rows as we are looking
2857 * at a smaller part of the dependence graph.
2859 * Since we do not enforce coincidence, we conservatively mark the
2860 * splitting row as not coincident.
2862 * The band_id of the second group is set to n, where n is the number
2863 * of nodes in the first group. This ensures that the band_ids over
2864 * the two groups remain disjoint, even if either or both of the two
2865 * groups contain independent components.
2867 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2869 int i
, j
, n
, e1
, e2
;
2870 int n_total_row
, orig_total_row
;
2871 int n_band
, orig_band
;
2873 if (graph
->n_total_row
>= graph
->max_row
)
2874 isl_die(ctx
, isl_error_internal
,
2875 "too many schedule rows", return -1);
2877 if (reset_band(graph
) < 0)
2881 for (i
= 0; i
< graph
->n
; ++i
) {
2882 struct isl_sched_node
*node
= &graph
->node
[i
];
2883 int row
= isl_mat_rows(node
->sched
);
2884 int cols
= isl_mat_cols(node
->sched
);
2885 int before
= node
->scc
<= graph
->src_scc
;
2890 isl_map_free(node
->sched_map
);
2891 node
->sched_map
= NULL
;
2892 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2895 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2897 for (j
= 1; j
< cols
; ++j
)
2898 node
->sched
= isl_mat_set_element_si(node
->sched
,
2900 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2901 node
->coincident
[graph
->n_total_row
] = 0;
2905 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2906 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2908 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2912 graph
->n_total_row
++;
2915 for (i
= 0; i
< graph
->n
; ++i
) {
2916 struct isl_sched_node
*node
= &graph
->node
[i
];
2917 if (node
->scc
> graph
->src_scc
)
2918 node
->band_id
[graph
->n_band
] = n
;
2921 orig_total_row
= graph
->n_total_row
;
2922 orig_band
= graph
->n_band
;
2923 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2924 &node_scc_at_most
, &edge_dst_scc_at_most
,
2925 graph
->src_scc
, 0) < 0)
2927 n_total_row
= graph
->n_total_row
;
2928 graph
->n_total_row
= orig_total_row
;
2929 n_band
= graph
->n_band
;
2930 graph
->n_band
= orig_band
;
2931 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2932 &node_scc_at_least
, &edge_src_scc_at_least
,
2933 graph
->src_scc
+ 1, 0) < 0)
2935 if (n_total_row
> graph
->n_total_row
)
2936 graph
->n_total_row
= n_total_row
;
2937 if (n_band
> graph
->n_band
)
2938 graph
->n_band
= n_band
;
2940 return pad_schedule(graph
);
2943 /* Compute the next band of the schedule after updating the dependence
2944 * relations based on the the current schedule.
2946 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2948 if (update_edges(ctx
, graph
) < 0)
2952 return compute_schedule(ctx
, graph
);
2955 /* Add constraints to graph->lp that force the dependence "map" (which
2956 * is part of the dependence relation of "edge")
2957 * to be respected and attempt to carry it, where the edge is one from
2958 * a node j to itself. "pos" is the sequence number of the given map.
2959 * That is, add constraints that enforce
2961 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2962 * = c_j_x (y - x) >= e_i
2964 * for each (x,y) in R.
2965 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2966 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2967 * with each coefficient in c_j_x represented as a pair of non-negative
2970 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2971 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2974 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2976 isl_dim_map
*dim_map
;
2977 isl_basic_set
*coef
;
2978 struct isl_sched_node
*node
= edge
->src
;
2980 coef
= intra_coefficients(graph
, node
, map
);
2984 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2986 total
= isl_basic_set_total_dim(graph
->lp
);
2987 dim_map
= isl_dim_map_alloc(ctx
, total
);
2988 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2989 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2990 isl_space_dim(dim
, isl_dim_set
), 1,
2992 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2993 isl_space_dim(dim
, isl_dim_set
), 1,
2995 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2996 coef
->n_eq
, coef
->n_ineq
);
2997 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2999 isl_space_free(dim
);
3004 /* Add constraints to graph->lp that force the dependence "map" (which
3005 * is part of the dependence relation of "edge")
3006 * to be respected and attempt to carry it, where the edge is one from
3007 * node j to node k. "pos" is the sequence number of the given map.
3008 * That is, add constraints that enforce
3010 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3012 * for each (x,y) in R.
3013 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3014 * of valid constraints for R and then plug in
3015 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3016 * with each coefficient (except e_i, c_k_0 and c_j_0)
3017 * represented as a pair of non-negative coefficients.
3019 static int add_inter_constraints(struct isl_sched_graph
*graph
,
3020 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
3023 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3025 isl_dim_map
*dim_map
;
3026 isl_basic_set
*coef
;
3027 struct isl_sched_node
*src
= edge
->src
;
3028 struct isl_sched_node
*dst
= edge
->dst
;
3030 coef
= inter_coefficients(graph
, edge
, map
);
3034 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
3036 total
= isl_basic_set_total_dim(graph
->lp
);
3037 dim_map
= isl_dim_map_alloc(ctx
, total
);
3039 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3041 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
3042 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
3043 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
3044 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
3045 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3047 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
3048 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
3051 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
3052 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
3053 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
3054 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
3055 isl_space_dim(dim
, isl_dim_set
), 1,
3057 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
3058 isl_space_dim(dim
, isl_dim_set
), 1,
3061 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
3062 coef
->n_eq
, coef
->n_ineq
);
3063 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
3065 isl_space_free(dim
);
3070 /* Add constraints to graph->lp that force all (conditional) validity
3071 * dependences to be respected and attempt to carry them.
3073 static int add_all_constraints(struct isl_sched_graph
*graph
)
3079 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3080 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3082 if (!edge
->validity
&& !edge
->conditional_validity
)
3085 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3086 isl_basic_map
*bmap
;
3089 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3090 map
= isl_map_from_basic_map(bmap
);
3092 if (edge
->src
== edge
->dst
&&
3093 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
3095 if (edge
->src
!= edge
->dst
&&
3096 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
3105 /* Count the number of equality and inequality constraints
3106 * that will be added to the carry_lp problem.
3107 * We count each edge exactly once.
3109 static int count_all_constraints(struct isl_sched_graph
*graph
,
3110 int *n_eq
, int *n_ineq
)
3114 *n_eq
= *n_ineq
= 0;
3115 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3116 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
3117 for (j
= 0; j
< edge
->map
->n
; ++j
) {
3118 isl_basic_map
*bmap
;
3121 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
3122 map
= isl_map_from_basic_map(bmap
);
3124 if (count_map_constraints(graph
, edge
, map
,
3125 n_eq
, n_ineq
, 1, 0) < 0)
3133 /* Construct an LP problem for finding schedule coefficients
3134 * such that the schedule carries as many dependences as possible.
3135 * In particular, for each dependence i, we bound the dependence distance
3136 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3137 * of all e_i's. Dependence with e_i = 0 in the solution are simply
3138 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3139 * Note that if the dependence relation is a union of basic maps,
3140 * then we have to consider each basic map individually as it may only
3141 * be possible to carry the dependences expressed by some of those
3142 * basic maps and not all off them.
3143 * Below, we consider each of those basic maps as a separate "edge".
3145 * All variables of the LP are non-negative. The actual coefficients
3146 * may be negative, so each coefficient is represented as the difference
3147 * of two non-negative variables. The negative part always appears
3148 * immediately before the positive part.
3149 * Other than that, the variables have the following order
3151 * - sum of (1 - e_i) over all edges
3152 * - sum of positive and negative parts of all c_n coefficients
3153 * (unconstrained when computing non-parametric schedules)
3154 * - sum of positive and negative parts of all c_x coefficients
3159 * - positive and negative parts of c_i_n (if parametric)
3160 * - positive and negative parts of c_i_x
3162 * The constraints are those from the (validity) edges plus three equalities
3163 * to express the sums and n_edge inequalities to express e_i <= 1.
3165 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3175 for (i
= 0; i
< graph
->n_edge
; ++i
)
3176 n_edge
+= graph
->edge
[i
].map
->n
;
3179 for (i
= 0; i
< graph
->n
; ++i
) {
3180 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
3181 node
->start
= total
;
3182 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
3185 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
3187 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
3190 dim
= isl_space_set_alloc(ctx
, 0, total
);
3191 isl_basic_set_free(graph
->lp
);
3194 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
3195 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
3197 k
= isl_basic_set_alloc_equality(graph
->lp
);
3200 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3201 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
3202 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3203 for (i
= 0; i
< n_edge
; ++i
)
3204 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3206 k
= isl_basic_set_alloc_equality(graph
->lp
);
3209 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3210 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
3211 for (i
= 0; i
< graph
->n
; ++i
) {
3212 int pos
= 1 + graph
->node
[i
].start
+ 1;
3214 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
3215 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3218 k
= isl_basic_set_alloc_equality(graph
->lp
);
3221 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3222 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
3223 for (i
= 0; i
< graph
->n
; ++i
) {
3224 struct isl_sched_node
*node
= &graph
->node
[i
];
3225 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3227 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
3228 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3231 for (i
= 0; i
< n_edge
; ++i
) {
3232 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3235 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3236 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3237 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3240 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
3242 if (add_all_constraints(graph
) < 0)
3248 /* If the schedule_split_scaled option is set and if the linear
3249 * parts of the scheduling rows for all nodes in the graphs have
3250 * non-trivial common divisor, then split off the constant term
3251 * from the linear part.
3252 * The constant term is then placed in a separate band and
3253 * the linear part is reduced.
3255 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3261 if (!ctx
->opt
->schedule_split_scaled
)
3266 if (graph
->n_total_row
>= graph
->max_row
)
3267 isl_die(ctx
, isl_error_internal
,
3268 "too many schedule rows", return -1);
3271 isl_int_init(gcd_i
);
3273 isl_int_set_si(gcd
, 0);
3275 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3277 for (i
= 0; i
< graph
->n
; ++i
) {
3278 struct isl_sched_node
*node
= &graph
->node
[i
];
3279 int cols
= isl_mat_cols(node
->sched
);
3281 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3282 isl_int_gcd(gcd
, gcd
, gcd_i
);
3285 isl_int_clear(gcd_i
);
3287 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3294 for (i
= 0; i
< graph
->n
; ++i
) {
3295 struct isl_sched_node
*node
= &graph
->node
[i
];
3297 isl_map_free(node
->sched_map
);
3298 node
->sched_map
= NULL
;
3299 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3302 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
3303 node
->sched
->row
[row
][0], gcd
);
3304 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3305 node
->sched
->row
[row
][0], gcd
);
3306 isl_int_mul(node
->sched
->row
[row
][0],
3307 node
->sched
->row
[row
][0], gcd
);
3308 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3311 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3314 graph
->n_total_row
++;
3323 static int compute_component_schedule(isl_ctx
*ctx
,
3324 struct isl_sched_graph
*graph
);
3326 /* Is the schedule row "sol" trivial on node "node"?
3327 * That is, is the solution zero on the dimensions orthogonal to
3328 * the previously found solutions?
3329 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3331 * Each coefficient is represented as the difference between
3332 * two non-negative values in "sol". "sol" has been computed
3333 * in terms of the original iterators (i.e., without use of cmap).
3334 * We construct the schedule row s and write it as a linear
3335 * combination of (linear combinations of) previously computed schedule rows.
3336 * s = Q c or c = U s.
3337 * If the final entries of c are all zero, then the solution is trivial.
3339 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3349 if (node
->nvar
== node
->rank
)
3352 ctx
= isl_vec_get_ctx(sol
);
3353 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3357 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3359 for (i
= 0; i
< node
->nvar
; ++i
)
3360 isl_int_sub(node_sol
->el
[i
],
3361 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3363 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3368 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3369 node
->nvar
- node
->rank
) == -1;
3371 isl_vec_free(node_sol
);
3376 /* Is the schedule row "sol" trivial on any node where it should
3378 * "sol" has been computed in terms of the original iterators
3379 * (i.e., without use of cmap).
3380 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3382 static int is_any_trivial(struct isl_sched_graph
*graph
,
3383 __isl_keep isl_vec
*sol
)
3387 for (i
= 0; i
< graph
->n
; ++i
) {
3388 struct isl_sched_node
*node
= &graph
->node
[i
];
3391 if (!needs_row(graph
, node
))
3393 trivial
= is_trivial(node
, sol
);
3394 if (trivial
< 0 || trivial
)
3401 /* Construct a schedule row for each node such that as many dependences
3402 * as possible are carried and then continue with the next band.
3404 * If the computed schedule row turns out to be trivial on one or
3405 * more nodes where it should not be trivial, then we throw it away
3406 * and try again on each component separately.
3408 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3417 for (i
= 0; i
< graph
->n_edge
; ++i
)
3418 n_edge
+= graph
->edge
[i
].map
->n
;
3420 if (setup_carry_lp(ctx
, graph
) < 0)
3423 lp
= isl_basic_set_copy(graph
->lp
);
3424 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3428 if (sol
->size
== 0) {
3430 isl_die(ctx
, isl_error_internal
,
3431 "error in schedule construction", return -1);
3434 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3435 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3437 isl_die(ctx
, isl_error_unknown
,
3438 "unable to carry dependences", return -1);
3441 trivial
= is_any_trivial(graph
, sol
);
3443 sol
= isl_vec_free(sol
);
3444 } else if (trivial
) {
3447 return compute_component_schedule(ctx
, graph
);
3448 isl_die(ctx
, isl_error_unknown
,
3449 "unable to construct non-trivial solution", return -1);
3452 if (update_schedule(graph
, sol
, 0, 0) < 0)
3455 if (split_scaled(ctx
, graph
) < 0)
3458 return compute_next_band(ctx
, graph
);
3461 /* Are there any (non-empty) (conditional) validity edges in the graph?
3463 static int has_validity_edges(struct isl_sched_graph
*graph
)
3467 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3470 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3475 if (graph
->edge
[i
].validity
||
3476 graph
->edge
[i
].conditional_validity
)
3483 /* Should we apply a Feautrier step?
3484 * That is, did the user request the Feautrier algorithm and are
3485 * there any validity dependences (left)?
3487 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3489 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3492 return has_validity_edges(graph
);
3495 /* Compute a schedule for a connected dependence graph using Feautrier's
3496 * multi-dimensional scheduling algorithm.
3497 * The original algorithm is described in [1].
3498 * The main idea is to minimize the number of scheduling dimensions, by
3499 * trying to satisfy as many dependences as possible per scheduling dimension.
3501 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3502 * Problem, Part II: Multi-Dimensional Time.
3503 * In Intl. Journal of Parallel Programming, 1992.
3505 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
3506 struct isl_sched_graph
*graph
)
3508 return carry_dependences(ctx
, graph
);
3511 /* Turn off the "local" bit on all (condition) edges.
3513 static void clear_local_edges(struct isl_sched_graph
*graph
)
3517 for (i
= 0; i
< graph
->n_edge
; ++i
)
3518 if (graph
->edge
[i
].condition
)
3519 graph
->edge
[i
].local
= 0;
3522 /* Does "graph" have both condition and conditional validity edges?
3524 static int need_condition_check(struct isl_sched_graph
*graph
)
3527 int any_condition
= 0;
3528 int any_conditional_validity
= 0;
3530 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3531 if (graph
->edge
[i
].condition
)
3533 if (graph
->edge
[i
].conditional_validity
)
3534 any_conditional_validity
= 1;
3537 return any_condition
&& any_conditional_validity
;
3540 /* Does "graph" contain any coincidence edge?
3542 static int has_any_coincidence(struct isl_sched_graph
*graph
)
3546 for (i
= 0; i
< graph
->n_edge
; ++i
)
3547 if (graph
->edge
[i
].coincidence
)
3553 /* Extract the final schedule row as a map with the iteration domain
3554 * of "node" as domain.
3556 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
3558 isl_local_space
*ls
;
3562 row
= isl_mat_rows(node
->sched
) - 1;
3563 ls
= isl_local_space_from_space(isl_space_copy(node
->space
));
3564 aff
= extract_schedule_row(ls
, node
, row
);
3565 return isl_map_from_aff(aff
);
3568 /* Is the conditional validity dependence in the edge with index "edge_index"
3569 * violated by the latest (i.e., final) row of the schedule?
3570 * That is, is i scheduled after j
3571 * for any conditional validity dependence i -> j?
3573 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
3575 isl_map
*src_sched
, *dst_sched
, *map
;
3576 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
3579 src_sched
= final_row(edge
->src
);
3580 dst_sched
= final_row(edge
->dst
);
3581 map
= isl_map_copy(edge
->map
);
3582 map
= isl_map_apply_domain(map
, src_sched
);
3583 map
= isl_map_apply_range(map
, dst_sched
);
3584 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
3585 empty
= isl_map_is_empty(map
);
3594 /* Does the domain of "umap" intersect "uset"?
3596 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3597 __isl_keep isl_union_set
*uset
)
3601 umap
= isl_union_map_copy(umap
);
3602 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3603 empty
= isl_union_map_is_empty(umap
);
3604 isl_union_map_free(umap
);
3606 return empty
< 0 ? -1 : !empty
;
3609 /* Does the range of "umap" intersect "uset"?
3611 static int range_intersects(__isl_keep isl_union_map
*umap
,
3612 __isl_keep isl_union_set
*uset
)
3616 umap
= isl_union_map_copy(umap
);
3617 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3618 empty
= isl_union_map_is_empty(umap
);
3619 isl_union_map_free(umap
);
3621 return empty
< 0 ? -1 : !empty
;
3624 /* Are the condition dependences of "edge" local with respect to
3625 * the current schedule?
3627 * That is, are domain and range of the condition dependences mapped
3628 * to the same point?
3630 * In other words, is the condition false?
3632 static int is_condition_false(struct isl_sched_edge
*edge
)
3634 isl_union_map
*umap
;
3635 isl_map
*map
, *sched
, *test
;
3638 umap
= isl_union_map_copy(edge
->tagged_condition
);
3639 umap
= isl_union_map_zip(umap
);
3640 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3641 map
= isl_map_from_union_map(umap
);
3643 sched
= node_extract_schedule(edge
->src
);
3644 map
= isl_map_apply_domain(map
, sched
);
3645 sched
= node_extract_schedule(edge
->dst
);
3646 map
= isl_map_apply_range(map
, sched
);
3648 test
= isl_map_identity(isl_map_get_space(map
));
3649 local
= isl_map_is_subset(map
, test
);
3656 /* Does "graph" have any satisfied condition edges that
3657 * are adjacent to the conditional validity constraint with
3658 * domain "conditional_source" and range "conditional_sink"?
3660 * A satisfied condition is one that is not local.
3661 * If a condition was forced to be local already (i.e., marked as local)
3662 * then there is no need to check if it is in fact local.
3664 * Additionally, mark all adjacent condition edges found as local.
3666 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
3667 __isl_keep isl_union_set
*conditional_source
,
3668 __isl_keep isl_union_set
*conditional_sink
)
3673 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3674 int adjacent
, local
;
3675 isl_union_map
*condition
;
3677 if (!graph
->edge
[i
].condition
)
3679 if (graph
->edge
[i
].local
)
3682 condition
= graph
->edge
[i
].tagged_condition
;
3683 adjacent
= domain_intersects(condition
, conditional_sink
);
3684 if (adjacent
>= 0 && !adjacent
)
3685 adjacent
= range_intersects(condition
,
3686 conditional_source
);
3692 graph
->edge
[i
].local
= 1;
3694 local
= is_condition_false(&graph
->edge
[i
]);
3704 /* Are there any violated conditional validity dependences with
3705 * adjacent condition dependences that are not local with respect
3706 * to the current schedule?
3707 * That is, is the conditional validity constraint violated?
3709 * Additionally, mark all those adjacent condition dependences as local.
3710 * We also mark those adjacent condition dependences that were not marked
3711 * as local before, but just happened to be local already. This ensures
3712 * that they remain local if the schedule is recomputed.
3714 * We first collect domain and range of all violated conditional validity
3715 * dependences and then check if there are any adjacent non-local
3716 * condition dependences.
3718 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
3719 struct isl_sched_graph
*graph
)
3723 isl_union_set
*source
, *sink
;
3725 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3726 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3727 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3728 isl_union_set
*uset
;
3729 isl_union_map
*umap
;
3732 if (!graph
->edge
[i
].conditional_validity
)
3735 violated
= is_violated(graph
, i
);
3743 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3744 uset
= isl_union_map_domain(umap
);
3745 source
= isl_union_set_union(source
, uset
);
3746 source
= isl_union_set_coalesce(source
);
3748 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3749 uset
= isl_union_map_range(umap
);
3750 sink
= isl_union_set_union(sink
, uset
);
3751 sink
= isl_union_set_coalesce(sink
);
3755 any
= has_adjacent_true_conditions(graph
, source
, sink
);
3757 isl_union_set_free(source
);
3758 isl_union_set_free(sink
);
3761 isl_union_set_free(source
);
3762 isl_union_set_free(sink
);
3766 /* Compute a schedule for a connected dependence graph.
3767 * We try to find a sequence of as many schedule rows as possible that result
3768 * in non-negative dependence distances (independent of the previous rows
3769 * in the sequence, i.e., such that the sequence is tilable), with as
3770 * many of the initial rows as possible satisfying the coincidence constraints.
3771 * If we can't find any more rows we either
3772 * - split between SCCs and start over (assuming we found an interesting
3773 * pair of SCCs between which to split)
3774 * - continue with the next band (assuming the current band has at least
3776 * - try to carry as many dependences as possible and continue with the next
3779 * If Feautrier's algorithm is selected, we first recursively try to satisfy
3780 * as many validity dependences as possible. When all validity dependences
3781 * are satisfied we extend the schedule to a full-dimensional schedule.
3783 * If we manage to complete the schedule, we finish off by topologically
3784 * sorting the statements based on the remaining dependences.
3786 * If ctx->opt->schedule_outer_coincidence is set, then we force the
3787 * outermost dimension to satisfy the coincidence constraints. If this
3788 * turns out to be impossible, we fall back on the general scheme above
3789 * and try to carry as many dependences as possible.
3791 * If "graph" contains both condition and conditional validity dependences,
3792 * then we need to check that that the conditional schedule constraint
3793 * is satisfied, i.e., there are no violated conditional validity dependences
3794 * that are adjacent to any non-local condition dependences.
3795 * If there are, then we mark all those adjacent condition dependences
3796 * as local and recompute the current band. Those dependences that
3797 * are marked local will then be forced to be local.
3798 * The initial computation is performed with no dependences marked as local.
3799 * If we are lucky, then there will be no violated conditional validity
3800 * dependences adjacent to any non-local condition dependences.
3801 * Otherwise, we mark some additional condition dependences as local and
3802 * recompute. We continue this process until there are no violations left or
3803 * until we are no longer able to compute a schedule.
3804 * Since there are only a finite number of dependences,
3805 * there will only be a finite number of iterations.
3807 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3809 int has_coincidence
;
3810 int use_coincidence
;
3811 int force_coincidence
= 0;
3812 int check_conditional
;
3814 if (detect_sccs(ctx
, graph
) < 0)
3816 if (sort_sccs(graph
) < 0)
3819 if (compute_maxvar(graph
) < 0)
3822 if (need_feautrier_step(ctx
, graph
))
3823 return compute_schedule_wcc_feautrier(ctx
, graph
);
3825 clear_local_edges(graph
);
3826 check_conditional
= need_condition_check(graph
);
3827 has_coincidence
= has_any_coincidence(graph
);
3829 if (ctx
->opt
->schedule_outer_coincidence
)
3830 force_coincidence
= 1;
3832 use_coincidence
= has_coincidence
;
3833 while (graph
->n_row
< graph
->maxvar
) {
3838 graph
->src_scc
= -1;
3839 graph
->dst_scc
= -1;
3841 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
3843 sol
= solve_lp(graph
);
3846 if (sol
->size
== 0) {
3847 int empty
= graph
->n_total_row
== graph
->band_start
;
3850 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
3851 use_coincidence
= 0;
3854 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
3855 return compute_next_band(ctx
, graph
);
3856 if (graph
->src_scc
>= 0)
3857 return compute_split_schedule(ctx
, graph
);
3859 return compute_next_band(ctx
, graph
);
3860 return carry_dependences(ctx
, graph
);
3862 coincident
= !has_coincidence
|| use_coincidence
;
3863 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
3866 if (!check_conditional
)
3868 violated
= has_violated_conditional_constraint(ctx
, graph
);
3873 if (reset_band(graph
) < 0)
3875 use_coincidence
= has_coincidence
;
3878 if (graph
->n_total_row
> graph
->band_start
)
3880 return sort_statements(ctx
, graph
);
3883 /* Add a row to the schedules that separates the SCCs and move
3886 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3890 if (graph
->n_total_row
>= graph
->max_row
)
3891 isl_die(ctx
, isl_error_internal
,
3892 "too many schedule rows", return -1);
3894 for (i
= 0; i
< graph
->n
; ++i
) {
3895 struct isl_sched_node
*node
= &graph
->node
[i
];
3896 int row
= isl_mat_rows(node
->sched
);
3898 isl_map_free(node
->sched_map
);
3899 node
->sched_map
= NULL
;
3900 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3901 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
3905 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3908 graph
->n_total_row
++;
3914 /* Compute a schedule for each component (identified by node->scc)
3915 * of the dependence graph separately and then combine the results.
3916 * Depending on the setting of schedule_fuse, a component may be
3917 * either weakly or strongly connected.
3919 * The band_id is adjusted such that each component has a separate id.
3920 * Note that the band_id may have already been set to a value different
3921 * from zero by compute_split_schedule.
3923 static int compute_component_schedule(isl_ctx
*ctx
,
3924 struct isl_sched_graph
*graph
)
3928 int n_total_row
, orig_total_row
;
3929 int n_band
, orig_band
;
3931 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
3932 ctx
->opt
->schedule_separate_components
)
3933 if (split_on_scc(ctx
, graph
) < 0)
3937 orig_total_row
= graph
->n_total_row
;
3939 orig_band
= graph
->n_band
;
3940 for (i
= 0; i
< graph
->n
; ++i
)
3941 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
3942 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
3944 for (i
= 0; i
< graph
->n
; ++i
)
3945 if (graph
->node
[i
].scc
== wcc
)
3948 for (i
= 0; i
< graph
->n_edge
; ++i
)
3949 if (graph
->edge
[i
].src
->scc
== wcc
&&
3950 graph
->edge
[i
].dst
->scc
== wcc
)
3953 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
3955 &edge_scc_exactly
, wcc
, 1) < 0)
3957 if (graph
->n_total_row
> n_total_row
)
3958 n_total_row
= graph
->n_total_row
;
3959 graph
->n_total_row
= orig_total_row
;
3960 if (graph
->n_band
> n_band
)
3961 n_band
= graph
->n_band
;
3962 graph
->n_band
= orig_band
;
3965 graph
->n_total_row
= n_total_row
;
3966 graph
->n_band
= n_band
;
3968 return pad_schedule(graph
);
3971 /* Compute a schedule for the given dependence graph.
3972 * We first check if the graph is connected (through validity and conditional
3973 * validity dependences) and, if not, compute a schedule
3974 * for each component separately.
3975 * If schedule_fuse is set to minimal fusion, then we check for strongly
3976 * connected components instead and compute a separate schedule for
3977 * each such strongly connected component.
3979 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3981 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
3982 if (detect_sccs(ctx
, graph
) < 0)
3985 if (detect_wccs(ctx
, graph
) < 0)
3990 return compute_component_schedule(ctx
, graph
);
3992 return compute_schedule_wcc(ctx
, graph
);
3995 /* Compute a schedule on sc->domain that respects the given schedule
3998 * In particular, the schedule respects all the validity dependences.
3999 * If the default isl scheduling algorithm is used, it tries to minimize
4000 * the dependence distances over the proximity dependences.
4001 * If Feautrier's scheduling algorithm is used, the proximity dependence
4002 * distances are only minimized during the extension to a full-dimensional
4005 * If there are any condition and conditional validity dependences,
4006 * then the conditional validity dependences may be violated inside
4007 * a tilable band, provided they have no adjacent non-local
4008 * condition dependences.
4010 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
4011 __isl_take isl_schedule_constraints
*sc
)
4013 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
4014 struct isl_sched_graph graph
= { 0 };
4015 isl_schedule
*sched
;
4016 struct isl_extract_edge_data data
;
4017 enum isl_edge_type i
;
4019 sc
= isl_schedule_constraints_align_params(sc
);
4023 graph
.n
= isl_union_set_n_set(sc
->domain
);
4026 if (graph_alloc(ctx
, &graph
, graph
.n
,
4027 isl_schedule_constraints_n_map(sc
)) < 0)
4029 if (compute_max_row(&graph
, sc
->domain
) < 0)
4033 if (isl_union_set_foreach_set(sc
->domain
, &extract_node
, &graph
) < 0)
4035 if (graph_init_table(ctx
, &graph
) < 0)
4037 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
4038 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
4039 if (graph_init_edge_tables(ctx
, &graph
) < 0)
4042 data
.graph
= &graph
;
4043 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
4045 if (isl_union_map_foreach_map(sc
->constraint
[i
],
4046 &extract_edge
, &data
) < 0)
4050 if (compute_schedule(ctx
, &graph
) < 0)
4054 sched
= extract_schedule(&graph
, isl_union_set_get_space(sc
->domain
));
4056 graph_free(ctx
, &graph
);
4057 isl_schedule_constraints_free(sc
);
4061 graph_free(ctx
, &graph
);
4062 isl_schedule_constraints_free(sc
);
4066 /* Compute a schedule for the given union of domains that respects
4067 * all the validity dependences and minimizes
4068 * the dependence distances over the proximity dependences.
4070 * This function is kept for backward compatibility.
4072 __isl_give isl_schedule
*isl_union_set_compute_schedule(
4073 __isl_take isl_union_set
*domain
,
4074 __isl_take isl_union_map
*validity
,
4075 __isl_take isl_union_map
*proximity
)
4077 isl_schedule_constraints
*sc
;
4079 sc
= isl_schedule_constraints_on_domain(domain
);
4080 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
4081 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
4083 return isl_schedule_constraints_compute_schedule(sc
);
4086 __isl_null isl_schedule
*isl_schedule_free(__isl_take isl_schedule
*sched
)
4092 if (--sched
->ref
> 0)
4095 for (i
= 0; i
< sched
->n
; ++i
) {
4096 isl_multi_aff_free(sched
->node
[i
].sched
);
4097 free(sched
->node
[i
].band_end
);
4098 free(sched
->node
[i
].band_id
);
4099 free(sched
->node
[i
].coincident
);
4101 isl_space_free(sched
->dim
);
4102 isl_band_list_free(sched
->band_forest
);
4107 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
4109 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
4112 /* Set max_out to the maximal number of output dimensions over
4115 static int update_max_out(__isl_take isl_map
*map
, void *user
)
4117 int *max_out
= user
;
4118 int n_out
= isl_map_dim(map
, isl_dim_out
);
4120 if (n_out
> *max_out
)
4127 /* Internal data structure for map_pad_range.
4129 * "max_out" is the maximal schedule dimension.
4130 * "res" collects the results.
4132 struct isl_pad_schedule_map_data
{
4137 /* Pad the range of the given map with zeros to data->max_out and
4138 * then add the result to data->res.
4140 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
4142 struct isl_pad_schedule_map_data
*data
= user
;
4144 int n_out
= isl_map_dim(map
, isl_dim_out
);
4146 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
4147 for (i
= n_out
; i
< data
->max_out
; ++i
)
4148 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
4150 data
->res
= isl_union_map_add_map(data
->res
, map
);
4157 /* Pad the ranges of the maps in the union map with zeros such they all have
4158 * the same dimension.
4160 static __isl_give isl_union_map
*pad_schedule_map(
4161 __isl_take isl_union_map
*umap
)
4163 struct isl_pad_schedule_map_data data
;
4167 if (isl_union_map_n_map(umap
) <= 1)
4171 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
4172 return isl_union_map_free(umap
);
4174 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
4175 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
4176 data
.res
= isl_union_map_free(data
.res
);
4178 isl_union_map_free(umap
);
4182 /* Return an isl_union_map of the schedule. If we have already constructed
4183 * a band forest, then this band forest may have been modified so we need
4184 * to extract the isl_union_map from the forest rather than from
4185 * the originally computed schedule. This reconstructed schedule map
4186 * then needs to be padded with zeros to unify the schedule space
4187 * since the result of isl_band_list_get_suffix_schedule may not have
4188 * a unified schedule space.
4190 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
4193 isl_union_map
*umap
;
4198 if (sched
->band_forest
) {
4199 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
4200 return pad_schedule_map(umap
);
4203 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
4204 for (i
= 0; i
< sched
->n
; ++i
) {
4207 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
4208 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
4214 static __isl_give isl_band_list
*construct_band_list(
4215 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
4216 int band_nr
, int *parent_active
, int n_active
);
4218 /* Construct an isl_band structure for the band in the given schedule
4219 * with sequence number band_nr for the n_active nodes marked by active.
4220 * If the nodes don't have a band with the given sequence number,
4221 * then a band without members is created.
4223 * Because of the way the schedule is constructed, we know that
4224 * the position of the band inside the schedule of a node is the same
4225 * for all active nodes.
4227 * The partial schedule for the band is created before the children
4228 * are created to that construct_band_list can refer to the partial
4229 * schedule of the parent.
4231 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
4232 __isl_keep isl_band
*parent
,
4233 int band_nr
, int *active
, int n_active
)
4236 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4238 unsigned start
, end
;
4240 band
= isl_band_alloc(ctx
);
4244 band
->schedule
= schedule
;
4245 band
->parent
= parent
;
4247 for (i
= 0; i
< schedule
->n
; ++i
)
4251 if (i
>= schedule
->n
)
4252 isl_die(ctx
, isl_error_internal
,
4253 "band without active statements", goto error
);
4255 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
4256 end
= band_nr
< schedule
->node
[i
].n_band
?
4257 schedule
->node
[i
].band_end
[band_nr
] : start
;
4258 band
->n
= end
- start
;
4260 band
->coincident
= isl_alloc_array(ctx
, int, band
->n
);
4261 if (band
->n
&& !band
->coincident
)
4264 for (j
= 0; j
< band
->n
; ++j
)
4265 band
->coincident
[j
] = schedule
->node
[i
].coincident
[start
+ j
];
4267 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
4268 for (i
= 0; i
< schedule
->n
; ++i
) {
4270 isl_pw_multi_aff
*pma
;
4276 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
4277 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
4278 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
4279 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
4280 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
4281 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
4287 for (i
= 0; i
< schedule
->n
; ++i
)
4288 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
4291 if (i
< schedule
->n
) {
4292 band
->children
= construct_band_list(schedule
, band
,
4293 band_nr
+ 1, active
, n_active
);
4294 if (!band
->children
)
4300 isl_band_free(band
);
4304 /* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
4306 * r is set to a negative value if anything goes wrong.
4308 * c1 stores the result of extract_int.
4309 * c2 is a temporary value used inside cmp_band_in_ancestor.
4310 * t is a temporary value used inside extract_int.
4312 * first and equal are used inside extract_int.
4313 * first is set if we are looking at the first isl_multi_aff inside
4314 * the isl_union_pw_multi_aff.
4315 * equal is set if all the isl_multi_affs have been equal so far.
4317 struct isl_cmp_band_data
{
4328 /* Check if "ma" assigns a constant value.
4329 * Note that this function is only called on isl_multi_affs
4330 * with a single output dimension.
4332 * If "ma" assigns a constant value then we compare it to data->c1
4333 * or assign it to data->c1 if this is the first isl_multi_aff we consider.
4334 * If "ma" does not assign a constant value or if it assigns a value
4335 * that is different from data->c1, then we set data->equal to zero
4336 * and terminate the check.
4338 static int multi_aff_extract_int(__isl_take isl_set
*set
,
4339 __isl_take isl_multi_aff
*ma
, void *user
)
4342 struct isl_cmp_band_data
*data
= user
;
4344 aff
= isl_multi_aff_get_aff(ma
, 0);
4345 data
->r
= isl_aff_is_cst(aff
);
4346 if (data
->r
>= 0 && data
->r
) {
4347 isl_aff_get_constant(aff
, &data
->t
);
4349 isl_int_set(data
->c1
, data
->t
);
4351 } else if (!isl_int_eq(data
->c1
, data
->t
))
4353 } else if (data
->r
>= 0 && !data
->r
)
4358 isl_multi_aff_free(ma
);
4367 /* This function is called for each isl_pw_multi_aff in
4368 * the isl_union_pw_multi_aff checked by extract_int.
4369 * Check all the isl_multi_affs inside "pma".
4371 static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff
*pma
,
4376 r
= isl_pw_multi_aff_foreach_piece(pma
, &multi_aff_extract_int
, user
);
4377 isl_pw_multi_aff_free(pma
);
4382 /* Check if "upma" assigns a single constant value to its domain.
4383 * If so, return 1 and store the result in data->c1.
4386 * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
4387 * means that either an error occurred or that we have broken off the check
4388 * because we already know the result is going to be negative.
4389 * In the latter case, data->equal is set to zero.
4391 static int extract_int(__isl_keep isl_union_pw_multi_aff
*upma
,
4392 struct isl_cmp_band_data
*data
)
4397 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4398 &pw_multi_aff_extract_int
, data
) < 0) {
4404 return !data
->first
&& data
->equal
;
4407 /* Compare "b1" and "b2" based on the parent schedule of their ancestor
4410 * If the parent of "ancestor" also has a single member, then we
4411 * first try to compare the two band based on the partial schedule
4414 * Otherwise, or if the result is inconclusive, we look at the partial schedule
4415 * of "ancestor" itself.
4416 * In particular, we specialize the parent schedule based
4417 * on the domains of the child schedules, check if both assign
4418 * a single constant value and, if so, compare the two constant values.
4419 * If the specialized parent schedules do not assign a constant value,
4420 * then they cannot be used to order the two bands and so in this case
4423 static int cmp_band_in_ancestor(__isl_keep isl_band
*b1
,
4424 __isl_keep isl_band
*b2
, struct isl_cmp_band_data
*data
,
4425 __isl_keep isl_band
*ancestor
)
4427 isl_union_pw_multi_aff
*upma
;
4428 isl_union_set
*domain
;
4434 if (ancestor
->parent
&& ancestor
->parent
->n
== 1) {
4435 r
= cmp_band_in_ancestor(b1
, b2
, data
, ancestor
->parent
);
4442 upma
= isl_union_pw_multi_aff_copy(b1
->pma
);
4443 domain
= isl_union_pw_multi_aff_domain(upma
);
4444 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
4445 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
4446 r
= extract_int(upma
, data
);
4447 isl_union_pw_multi_aff_free(upma
);
4454 isl_int_set(data
->c2
, data
->c1
);
4456 upma
= isl_union_pw_multi_aff_copy(b2
->pma
);
4457 domain
= isl_union_pw_multi_aff_domain(upma
);
4458 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
4459 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
4460 r
= extract_int(upma
, data
);
4461 isl_union_pw_multi_aff_free(upma
);
4468 return isl_int_cmp(data
->c2
, data
->c1
);
4471 /* Compare "a" and "b" based on the parent schedule of their parent.
4473 static int cmp_band(const void *a
, const void *b
, void *user
)
4475 isl_band
*b1
= *(isl_band
* const *) a
;
4476 isl_band
*b2
= *(isl_band
* const *) b
;
4477 struct isl_cmp_band_data
*data
= user
;
4479 return cmp_band_in_ancestor(b1
, b2
, data
, b1
->parent
);
4482 /* Sort the elements in "list" based on the partial schedules of its parent
4483 * (and ancestors). In particular if the parent assigns constant values
4484 * to the domains of the bands in "list", then the elements are sorted
4485 * according to that order.
4486 * This order should be a more "natural" order for the user, but otherwise
4487 * shouldn't have any effect.
4488 * If we would be constructing an isl_band forest directly in
4489 * isl_schedule_constraints_compute_schedule then there wouldn't be any need
4490 * for a reordering, since the children would be added to the list
4491 * in their natural order automatically.
4493 * If there is only one element in the list, then there is no need to sort
4495 * If the partial schedule of the parent has more than one member
4496 * (or if there is no parent), then it's
4497 * defnitely not assigning constant values to the different children in
4498 * the list and so we wouldn't be able to use it to sort the list.
4500 static __isl_give isl_band_list
*sort_band_list(__isl_take isl_band_list
*list
,
4501 __isl_keep isl_band
*parent
)
4503 struct isl_cmp_band_data data
;
4509 if (!parent
|| parent
->n
!= 1)
4513 isl_int_init(data
.c1
);
4514 isl_int_init(data
.c2
);
4515 isl_int_init(data
.t
);
4516 isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]), &cmp_band
, &data
);
4518 list
= isl_band_list_free(list
);
4519 isl_int_clear(data
.c1
);
4520 isl_int_clear(data
.c2
);
4521 isl_int_clear(data
.t
);
4526 /* Construct a list of bands that start at the same position (with
4527 * sequence number band_nr) in the schedules of the nodes that
4528 * were active in the parent band.
4530 * A separate isl_band structure is created for each band_id
4531 * and for each node that does not have a band with sequence
4532 * number band_nr. In the latter case, a band without members
4534 * This ensures that if a band has any children, then each node
4535 * that was active in the band is active in exactly one of the children.
4537 static __isl_give isl_band_list
*construct_band_list(
4538 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
4539 int band_nr
, int *parent_active
, int n_active
)
4542 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4545 isl_band_list
*list
;
4548 for (i
= 0; i
< n_active
; ++i
) {
4549 for (j
= 0; j
< schedule
->n
; ++j
) {
4550 if (!parent_active
[j
])
4552 if (schedule
->node
[j
].n_band
<= band_nr
)
4554 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
4560 for (j
= 0; j
< schedule
->n
; ++j
)
4561 if (schedule
->node
[j
].n_band
<= band_nr
)
4566 list
= isl_band_list_alloc(ctx
, n_band
);
4567 band
= construct_band(schedule
, parent
, band_nr
,
4568 parent_active
, n_active
);
4569 return isl_band_list_add(list
, band
);
4572 active
= isl_alloc_array(ctx
, int, schedule
->n
);
4573 if (schedule
->n
&& !active
)
4576 list
= isl_band_list_alloc(ctx
, n_band
);
4578 for (i
= 0; i
< n_active
; ++i
) {
4582 for (j
= 0; j
< schedule
->n
; ++j
) {
4583 active
[j
] = parent_active
[j
] &&
4584 schedule
->node
[j
].n_band
> band_nr
&&
4585 schedule
->node
[j
].band_id
[band_nr
] == i
;
4592 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
4594 list
= isl_band_list_add(list
, band
);
4596 for (i
= 0; i
< schedule
->n
; ++i
) {
4598 if (!parent_active
[i
])
4600 if (schedule
->node
[i
].n_band
> band_nr
)
4602 for (j
= 0; j
< schedule
->n
; ++j
)
4604 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
4605 list
= isl_band_list_add(list
, band
);
4610 list
= sort_band_list(list
, parent
);
4615 /* Construct a band forest representation of the schedule and
4616 * return the list of roots.
4618 static __isl_give isl_band_list
*construct_forest(
4619 __isl_keep isl_schedule
*schedule
)
4622 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4623 isl_band_list
*forest
;
4626 active
= isl_alloc_array(ctx
, int, schedule
->n
);
4627 if (schedule
->n
&& !active
)
4630 for (i
= 0; i
< schedule
->n
; ++i
)
4633 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
4640 /* Return the roots of a band forest representation of the schedule.
4642 __isl_give isl_band_list
*isl_schedule_get_band_forest(
4643 __isl_keep isl_schedule
*schedule
)
4647 if (!schedule
->band_forest
)
4648 schedule
->band_forest
= construct_forest(schedule
);
4649 return isl_band_list_dup(schedule
->band_forest
);
4652 /* Call "fn" on each band in the schedule in depth-first post-order.
4654 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
4655 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
4658 isl_band_list
*forest
;
4663 forest
= isl_schedule_get_band_forest(sched
);
4664 r
= isl_band_list_foreach_band(forest
, fn
, user
);
4665 isl_band_list_free(forest
);
4670 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
4671 __isl_keep isl_band_list
*list
);
4673 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
4674 __isl_keep isl_band
*band
)
4676 isl_band_list
*children
;
4678 p
= isl_printer_start_line(p
);
4679 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
4680 p
= isl_printer_end_line(p
);
4682 if (!isl_band_has_children(band
))
4685 children
= isl_band_get_children(band
);
4687 p
= isl_printer_indent(p
, 4);
4688 p
= print_band_list(p
, children
);
4689 p
= isl_printer_indent(p
, -4);
4691 isl_band_list_free(children
);
4696 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
4697 __isl_keep isl_band_list
*list
)
4701 n
= isl_band_list_n_band(list
);
4702 for (i
= 0; i
< n
; ++i
) {
4704 band
= isl_band_list_get_band(list
, i
);
4705 p
= print_band(p
, band
);
4706 isl_band_free(band
);
4712 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
4713 __isl_keep isl_schedule
*schedule
)
4715 isl_band_list
*forest
;
4717 forest
= isl_schedule_get_band_forest(schedule
);
4719 p
= print_band_list(p
, forest
);
4721 isl_band_list_free(forest
);
4726 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
4728 isl_printer
*printer
;
4733 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
4734 printer
= isl_printer_print_schedule(printer
, schedule
);
4736 isl_printer_free(printer
);