2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015-2016 Sven Verdoolaege
5 * Copyright 2016 INRIA Paris
6 * Copyright 2017 Sven Verdoolaege
8 * Use of this software is governed by the MIT license
10 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
11 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
13 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
15 * CS 42112, 75589 Paris Cedex 12, France
18 #include <isl_ctx_private.h>
19 #include <isl_map_private.h>
20 #include <isl_space_private.h>
21 #include <isl_aff_private.h>
24 #include <isl/constraint.h>
25 #include <isl/schedule.h>
26 #include <isl_schedule_constraints.h>
27 #include <isl/schedule_node.h>
28 #include <isl_mat_private.h>
29 #include <isl_vec_private.h>
31 #include <isl_union_set_private.h>
34 #include <isl_dim_map.h>
35 #include <isl/map_to_basic_set.h>
37 #include <isl_options_private.h>
38 #include <isl_tarjan.h>
39 #include <isl_morph.h>
41 #include <isl_val_private.h>
43 #include "isl_scheduler.h"
44 #include "isl_scheduler_clustering.h"
47 * The scheduling algorithm implemented in this file was inspired by
48 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
49 * Parallelization and Locality Optimization in the Polyhedral Model".
51 * For a detailed description of the variant implemented in isl,
52 * see Verdoolaege and Janssens, "Scheduling for PPCG" (2017).
56 static isl_bool
node_has_tuples(const void *entry
, const void *val
)
58 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
59 isl_space
*space
= (isl_space
*) val
;
61 return isl_space_has_equal_tuples(node
->space
, space
);
64 int isl_sched_node_scc_exactly(struct isl_sched_node
*node
, int scc
)
66 return node
->scc
== scc
;
69 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
71 return node
->scc
<= scc
;
74 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
76 return node
->scc
>= scc
;
79 /* Is "edge" marked as being of type "type"?
81 int isl_sched_edge_has_type(struct isl_sched_edge
*edge
,
82 enum isl_edge_type type
)
84 return ISL_FL_ISSET(edge
->types
, 1 << type
);
87 /* Mark "edge" as being of type "type".
89 static void set_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
91 ISL_FL_SET(edge
->types
, 1 << type
);
94 /* No longer mark "edge" as being of type "type"?
96 static void clear_type(struct isl_sched_edge
*edge
, enum isl_edge_type type
)
98 ISL_FL_CLR(edge
->types
, 1 << type
);
101 /* Is "edge" marked as a validity edge?
103 static int is_validity(struct isl_sched_edge
*edge
)
105 return isl_sched_edge_has_type(edge
, isl_edge_validity
);
108 /* Mark "edge" as a validity edge.
110 static void set_validity(struct isl_sched_edge
*edge
)
112 set_type(edge
, isl_edge_validity
);
115 /* Is "edge" marked as a proximity edge?
117 int isl_sched_edge_is_proximity(struct isl_sched_edge
*edge
)
119 return isl_sched_edge_has_type(edge
, isl_edge_proximity
);
122 /* Is "edge" marked as a local edge?
124 static int is_local(struct isl_sched_edge
*edge
)
126 return isl_sched_edge_has_type(edge
, isl_edge_local
);
129 /* Mark "edge" as a local edge.
131 static void set_local(struct isl_sched_edge
*edge
)
133 set_type(edge
, isl_edge_local
);
136 /* No longer mark "edge" as a local edge.
138 static void clear_local(struct isl_sched_edge
*edge
)
140 clear_type(edge
, isl_edge_local
);
143 /* Is "edge" marked as a coincidence edge?
145 static int is_coincidence(struct isl_sched_edge
*edge
)
147 return isl_sched_edge_has_type(edge
, isl_edge_coincidence
);
150 /* Is "edge" marked as a condition edge?
152 int isl_sched_edge_is_condition(struct isl_sched_edge
*edge
)
154 return isl_sched_edge_has_type(edge
, isl_edge_condition
);
157 /* Is "edge" marked as a conditional validity edge?
159 int isl_sched_edge_is_conditional_validity(struct isl_sched_edge
*edge
)
161 return isl_sched_edge_has_type(edge
, isl_edge_conditional_validity
);
164 /* Is "edge" of a type that can appear multiple times between
165 * the same pair of nodes?
167 * Condition edges and conditional validity edges may have tagged
168 * dependence relations, in which case an edge is added for each
171 static int is_multi_edge_type(struct isl_sched_edge
*edge
)
173 return isl_sched_edge_is_condition(edge
) ||
174 isl_sched_edge_is_conditional_validity(edge
);
177 /* Initialize node_table based on the list of nodes.
179 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
183 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
184 if (!graph
->node_table
)
187 for (i
= 0; i
< graph
->n
; ++i
) {
188 struct isl_hash_table_entry
*entry
;
191 hash
= isl_space_get_tuple_hash(graph
->node
[i
].space
);
192 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
194 graph
->node
[i
].space
, 1);
197 entry
->data
= &graph
->node
[i
];
203 /* Return a pointer to the node that lives within the given space,
204 * an invalid node if there is no such node, or NULL in case of error.
206 struct isl_sched_node
*isl_sched_graph_find_node(isl_ctx
*ctx
,
207 struct isl_sched_graph
*graph
, __isl_keep isl_space
*space
)
209 struct isl_hash_table_entry
*entry
;
215 hash
= isl_space_get_tuple_hash(space
);
216 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
217 &node_has_tuples
, space
, 0);
220 if (entry
== isl_hash_table_entry_none
)
221 return graph
->node
+ graph
->n
;
226 /* Is "node" a node in "graph"?
228 int isl_sched_graph_is_node(struct isl_sched_graph
*graph
,
229 struct isl_sched_node
*node
)
231 return node
&& node
>= &graph
->node
[0] && node
< &graph
->node
[graph
->n
];
234 static isl_bool
edge_has_src_and_dst(const void *entry
, const void *val
)
236 const struct isl_sched_edge
*edge
= entry
;
237 const struct isl_sched_edge
*temp
= val
;
239 return isl_bool_ok(edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
);
242 /* Add the given edge to graph->edge_table[type].
244 static isl_stat
graph_edge_table_add(isl_ctx
*ctx
,
245 struct isl_sched_graph
*graph
, enum isl_edge_type type
,
246 struct isl_sched_edge
*edge
)
248 struct isl_hash_table_entry
*entry
;
251 hash
= isl_hash_init();
252 hash
= isl_hash_builtin(hash
, edge
->src
);
253 hash
= isl_hash_builtin(hash
, edge
->dst
);
254 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
255 &edge_has_src_and_dst
, edge
, 1);
257 return isl_stat_error
;
263 /* Add "edge" to all relevant edge tables.
264 * That is, for every type of the edge, add it to the corresponding table.
266 static isl_stat
graph_edge_tables_add(isl_ctx
*ctx
,
267 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
)
269 enum isl_edge_type t
;
271 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
272 if (!isl_sched_edge_has_type(edge
, t
))
274 if (graph_edge_table_add(ctx
, graph
, t
, edge
) < 0)
275 return isl_stat_error
;
281 /* Allocate the edge_tables based on the maximal number of edges of
284 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
288 for (i
= 0; i
<= isl_edge_last
; ++i
) {
289 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
291 if (!graph
->edge_table
[i
])
298 /* If graph->edge_table[type] contains an edge from the given source
299 * to the given destination, then return the hash table entry of this edge.
300 * Otherwise, return NULL.
302 static struct isl_hash_table_entry
*graph_find_edge_entry(
303 struct isl_sched_graph
*graph
,
304 enum isl_edge_type type
,
305 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
307 isl_ctx
*ctx
= isl_space_get_ctx(src
->space
);
309 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
311 hash
= isl_hash_init();
312 hash
= isl_hash_builtin(hash
, temp
.src
);
313 hash
= isl_hash_builtin(hash
, temp
.dst
);
314 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
315 &edge_has_src_and_dst
, &temp
, 0);
319 /* If graph->edge_table[type] contains an edge from the given source
320 * to the given destination, then return this edge.
321 * Return "none" if no such edge can be found.
322 * Return NULL on error.
324 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
325 enum isl_edge_type type
,
326 struct isl_sched_node
*src
, struct isl_sched_node
*dst
,
327 struct isl_sched_edge
*none
)
329 struct isl_hash_table_entry
*entry
;
331 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
334 if (entry
== isl_hash_table_entry_none
)
340 /* Check whether the dependence graph has an edge of the given type
341 * between the given two nodes.
343 static isl_bool
graph_has_edge(struct isl_sched_graph
*graph
,
344 enum isl_edge_type type
,
345 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
347 struct isl_sched_edge dummy
;
348 struct isl_sched_edge
*edge
;
351 edge
= graph_find_edge(graph
, type
, src
, dst
, &dummy
);
353 return isl_bool_error
;
355 return isl_bool_false
;
357 empty
= isl_map_plain_is_empty(edge
->map
);
359 return isl_bool_not(empty
);
362 /* Look for any edge with the same src, dst and map fields as "model".
364 * Return the matching edge if one can be found.
365 * Return "model" if no matching edge is found.
366 * Return NULL on error.
368 static struct isl_sched_edge
*graph_find_matching_edge(
369 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
371 enum isl_edge_type i
;
372 struct isl_sched_edge
*edge
;
374 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
377 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
, model
);
382 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
392 /* Remove the given edge from all the edge_tables that refer to it.
394 static isl_stat
graph_remove_edge(struct isl_sched_graph
*graph
,
395 struct isl_sched_edge
*edge
)
397 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
398 enum isl_edge_type i
;
400 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
401 struct isl_hash_table_entry
*entry
;
403 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
405 return isl_stat_error
;
406 if (entry
== isl_hash_table_entry_none
)
408 if (entry
->data
!= edge
)
410 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
416 /* Check whether the dependence graph has any edge
417 * between the given two nodes.
419 static isl_bool
graph_has_any_edge(struct isl_sched_graph
*graph
,
420 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
422 enum isl_edge_type i
;
425 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
426 r
= graph_has_edge(graph
, i
, src
, dst
);
434 /* Check whether the dependence graph has a validity edge
435 * between the given two nodes.
437 * Conditional validity edges are essentially validity edges that
438 * can be ignored if the corresponding condition edges are iteration private.
439 * Here, we are only checking for the presence of validity
440 * edges, so we need to consider the conditional validity edges too.
441 * In particular, this function is used during the detection
442 * of strongly connected components and we cannot ignore
443 * conditional validity edges during this detection.
445 isl_bool
isl_sched_graph_has_validity_edge(struct isl_sched_graph
*graph
,
446 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
450 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
454 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
457 /* Perform all the required memory allocations for a schedule graph "graph"
458 * with "n_node" nodes and "n_edge" edge and initialize the corresponding
461 static isl_stat
graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
462 int n_node
, int n_edge
)
467 graph
->n_edge
= n_edge
;
468 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
469 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
470 graph
->region
= isl_alloc_array(ctx
,
471 struct isl_trivial_region
, graph
->n
);
472 graph
->edge
= isl_calloc_array(ctx
,
473 struct isl_sched_edge
, graph
->n_edge
);
475 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
476 graph
->intra_hmap_param
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
477 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
479 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
481 return isl_stat_error
;
483 for(i
= 0; i
< graph
->n
; ++i
)
484 graph
->sorted
[i
] = i
;
489 /* Free the memory associated to node "node" in "graph".
490 * The "coincident" field is shared by nodes in a graph and its subgraph.
491 * It therefore only needs to be freed for the original dependence graph,
492 * i.e., one that is not the result of splitting.
494 static void clear_node(struct isl_sched_graph
*graph
,
495 struct isl_sched_node
*node
)
497 isl_space_free(node
->space
);
498 isl_set_free(node
->hull
);
499 isl_multi_aff_free(node
->compress
);
500 isl_pw_multi_aff_free(node
->decompress
);
501 isl_mat_free(node
->sched
);
502 isl_map_free(node
->sched_map
);
503 isl_mat_free(node
->indep
);
504 isl_mat_free(node
->vmap
);
505 if (graph
->root
== graph
)
506 free(node
->coincident
);
507 isl_multi_val_free(node
->sizes
);
508 isl_basic_set_free(node
->bounds
);
509 isl_vec_free(node
->max
);
512 void isl_sched_graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
516 isl_map_to_basic_set_free(graph
->intra_hmap
);
517 isl_map_to_basic_set_free(graph
->intra_hmap_param
);
518 isl_map_to_basic_set_free(graph
->inter_hmap
);
521 for (i
= 0; i
< graph
->n
; ++i
)
522 clear_node(graph
, &graph
->node
[i
]);
526 for (i
= 0; i
< graph
->n_edge
; ++i
) {
527 isl_map_free(graph
->edge
[i
].map
);
528 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
529 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
533 for (i
= 0; i
<= isl_edge_last
; ++i
)
534 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
535 isl_hash_table_free(ctx
, graph
->node_table
);
536 isl_basic_set_free(graph
->lp
);
539 /* For each "set" on which this function is called, increment
540 * graph->n by one and update graph->maxvar.
542 static isl_stat
init_n_maxvar(__isl_take isl_set
*set
, void *user
)
544 struct isl_sched_graph
*graph
= user
;
545 isl_size nvar
= isl_set_dim(set
, isl_dim_set
);
548 if (nvar
> graph
->maxvar
)
549 graph
->maxvar
= nvar
;
554 return isl_stat_error
;
558 /* Compute the number of rows that should be allocated for the schedule.
559 * In particular, we need one row for each variable or one row
560 * for each basic map in the dependences.
561 * Note that it is practically impossible to exhaust both
562 * the number of dependences and the number of variables.
564 static isl_stat
compute_max_row(struct isl_sched_graph
*graph
,
565 __isl_keep isl_schedule_constraints
*sc
)
569 isl_union_set
*domain
;
573 domain
= isl_schedule_constraints_get_domain(sc
);
574 r
= isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
);
575 isl_union_set_free(domain
);
577 return isl_stat_error
;
578 n_edge
= isl_schedule_constraints_n_basic_map(sc
);
580 return isl_stat_error
;
581 graph
->max_row
= n_edge
+ graph
->maxvar
;
586 /* Does "bset" have any defining equalities for its set variables?
588 static isl_bool
has_any_defining_equality(__isl_keep isl_basic_set
*bset
)
593 n
= isl_basic_set_dim(bset
, isl_dim_set
);
595 return isl_bool_error
;
597 for (i
= 0; i
< n
; ++i
) {
600 has
= isl_basic_set_has_defining_equality(bset
, isl_dim_set
, i
,
606 return isl_bool_false
;
609 /* Set the entries of node->max to the value of the schedule_max_coefficient
612 static isl_stat
set_max_coefficient(isl_ctx
*ctx
, struct isl_sched_node
*node
)
616 max
= isl_options_get_schedule_max_coefficient(ctx
);
620 node
->max
= isl_vec_alloc(ctx
, node
->nvar
);
621 node
->max
= isl_vec_set_si(node
->max
, max
);
623 return isl_stat_error
;
628 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
629 * option (if set) and half of the minimum of the sizes in the other
630 * dimensions. Round up when computing the half such that
631 * if the minimum of the sizes is one, half of the size is taken to be one
633 * If the global minimum is unbounded (i.e., if both
634 * the schedule_max_coefficient is not set and the sizes in the other
635 * dimensions are unbounded), then store a negative value.
636 * If the schedule coefficient is close to the size of the instance set
637 * in another dimension, then the schedule may represent a loop
638 * coalescing transformation (especially if the coefficient
639 * in that other dimension is one). Forcing the coefficient to be
640 * smaller than or equal to half the minimal size should avoid this
643 static isl_stat
compute_max_coefficient(isl_ctx
*ctx
,
644 struct isl_sched_node
*node
)
650 max
= isl_options_get_schedule_max_coefficient(ctx
);
651 v
= isl_vec_alloc(ctx
, node
->nvar
);
653 return isl_stat_error
;
655 for (i
= 0; i
< node
->nvar
; ++i
) {
656 isl_int_set_si(v
->el
[i
], max
);
657 isl_int_mul_si(v
->el
[i
], v
->el
[i
], 2);
660 for (i
= 0; i
< node
->nvar
; ++i
) {
663 size
= isl_multi_val_get_val(node
->sizes
, i
);
666 if (!isl_val_is_int(size
)) {
670 for (j
= 0; j
< node
->nvar
; ++j
) {
673 if (isl_int_is_neg(v
->el
[j
]) ||
674 isl_int_gt(v
->el
[j
], size
->n
))
675 isl_int_set(v
->el
[j
], size
->n
);
680 for (i
= 0; i
< node
->nvar
; ++i
)
681 isl_int_cdiv_q_ui(v
->el
[i
], v
->el
[i
], 2);
687 return isl_stat_error
;
690 /* Construct an identifier for node "node", which will represent "set".
691 * The name of the identifier is either "compressed" or
692 * "compressed_<name>", with <name> the name of the space of "set".
693 * The user pointer of the identifier points to "node".
695 static __isl_give isl_id
*construct_compressed_id(__isl_keep isl_set
*set
,
696 struct isl_sched_node
*node
)
705 has_name
= isl_set_has_tuple_name(set
);
709 ctx
= isl_set_get_ctx(set
);
711 return isl_id_alloc(ctx
, "compressed", node
);
713 p
= isl_printer_to_str(ctx
);
714 name
= isl_set_get_tuple_name(set
);
715 p
= isl_printer_print_str(p
, "compressed_");
716 p
= isl_printer_print_str(p
, name
);
717 id_name
= isl_printer_get_str(p
);
720 id
= isl_id_alloc(ctx
, id_name
, node
);
726 /* Construct a map that isolates the variable in position "pos" in "set".
730 * [i_0, ..., i_pos-1, i_pos+1, ...] -> [i_pos]
732 static __isl_give isl_map
*isolate(__isl_take isl_set
*set
, int pos
)
736 map
= isl_set_project_onto_map(set
, isl_dim_set
, pos
, 1);
737 map
= isl_map_project_out(map
, isl_dim_in
, pos
, 1);
741 /* Compute and return the size of "set" in dimension "dim".
742 * The size is taken to be the difference in values for that variable
743 * for fixed values of the other variables.
744 * This assumes that "set" is convex.
745 * In particular, the variable is first isolated from the other variables
746 * in the range of a map
748 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
750 * and then duplicated
752 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
754 * The shared variables are then projected out and the maximal value
755 * of i_dim' - i_dim is computed.
757 static __isl_give isl_val
*compute_size(__isl_take isl_set
*set
, int dim
)
764 map
= isolate(set
, dim
);
765 map
= isl_map_range_product(map
, isl_map_copy(map
));
766 map
= isl_set_unwrap(isl_map_range(map
));
767 set
= isl_map_deltas(map
);
768 ls
= isl_local_space_from_space(isl_set_get_space(set
));
769 obj
= isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
770 v
= isl_set_max_val(set
, obj
);
777 /* Perform a compression on "node" where "hull" represents the constraints
778 * that were used to derive the compression, while "compress" and
779 * "decompress" map the original space to the compressed space and
782 * If "node" was not compressed already, then simply store
783 * the compression information.
784 * Otherwise the "original" space is actually the result
785 * of a previous compression, which is then combined
786 * with the present compression.
788 * The dimensionality of the compressed domain is also adjusted.
789 * Other information, such as the sizes and the maximal coefficient values,
790 * has not been computed yet and therefore does not need to be adjusted.
792 static isl_stat
compress_node(struct isl_sched_node
*node
,
793 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
794 __isl_take isl_pw_multi_aff
*decompress
)
796 node
->nvar
= isl_multi_aff_dim(compress
, isl_dim_out
);
797 if (!node
->compressed
) {
798 node
->compressed
= 1;
800 node
->compress
= compress
;
801 node
->decompress
= decompress
;
803 hull
= isl_set_preimage_multi_aff(hull
,
804 isl_multi_aff_copy(node
->compress
));
805 node
->hull
= isl_set_intersect(node
->hull
, hull
);
806 node
->compress
= isl_multi_aff_pullback_multi_aff(
807 compress
, node
->compress
);
808 node
->decompress
= isl_pw_multi_aff_pullback_pw_multi_aff(
809 node
->decompress
, decompress
);
812 if (!node
->hull
|| !node
->compress
|| !node
->decompress
)
813 return isl_stat_error
;
818 /* Given that dimension "pos" in "set" has a fixed value
819 * in terms of the other dimensions, (further) compress "node"
820 * by projecting out this dimension.
821 * "set" may be the result of a previous compression.
822 * "uncompressed" is the original domain (without compression).
824 * The compression function simply projects out the dimension.
825 * The decompression function adds back the dimension
826 * in the right position as an expression of the other dimensions
827 * derived from "set".
828 * As in extract_node, the compressed space has an identifier
829 * that references "node" such that each compressed space is unique and
830 * such that the node can be recovered from the compressed space.
832 * The constraint removed through the compression is added to the "hull"
833 * such that only edges that relate to the original domains
834 * are taken into account.
835 * In particular, it is obtained by composing compression and decompression and
836 * taking the relation among the variables in the range.
838 static isl_stat
project_out_fixed(struct isl_sched_node
*node
,
839 __isl_keep isl_set
*uncompressed
, __isl_take isl_set
*set
, int pos
)
845 isl_multi_aff
*compress
;
846 isl_pw_multi_aff
*decompress
, *pma
;
847 isl_multi_pw_aff
*mpa
;
850 map
= isolate(isl_set_copy(set
), pos
);
851 pma
= isl_pw_multi_aff_from_map(map
);
852 domain
= isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma
));
853 pma
= isl_pw_multi_aff_gist(pma
, domain
);
854 space
= isl_pw_multi_aff_get_domain_space(pma
);
855 mpa
= isl_multi_pw_aff_identity(isl_space_map_from_set(space
));
856 mpa
= isl_multi_pw_aff_range_splice(mpa
, pos
,
857 isl_multi_pw_aff_from_pw_multi_aff(pma
));
858 decompress
= isl_pw_multi_aff_from_multi_pw_aff(mpa
);
859 space
= isl_set_get_space(set
);
860 compress
= isl_multi_aff_project_out_map(space
, isl_dim_set
, pos
, 1);
861 id
= construct_compressed_id(uncompressed
, node
);
862 compress
= isl_multi_aff_set_tuple_id(compress
, isl_dim_out
, id
);
863 space
= isl_space_reverse(isl_multi_aff_get_space(compress
));
864 decompress
= isl_pw_multi_aff_reset_space(decompress
, space
);
865 pma
= isl_pw_multi_aff_pullback_multi_aff(
866 isl_pw_multi_aff_copy(decompress
), isl_multi_aff_copy(compress
));
867 hull
= isl_map_range(isl_map_from_pw_multi_aff(pma
));
871 return compress_node(node
, hull
, compress
, decompress
);
874 /* Compute the size of the compressed domain in each dimension and
875 * store the results in node->sizes.
876 * "uncompressed" is the original domain (without compression).
878 * First compress the domain if needed and then compute the size
880 * If the domain is not convex, then the sizes are computed
881 * on a convex superset in order to avoid picking up sizes
882 * that are valid for the individual disjuncts, but not for
883 * the domain as a whole.
885 * If any of the sizes turns out to be zero, then this means
886 * that this dimension has a fixed value in terms of
887 * the other dimensions. Perform an (extra) compression
888 * to remove this dimension.
890 static isl_stat
compute_sizes(struct isl_sched_node
*node
,
891 __isl_keep isl_set
*uncompressed
)
896 isl_set
*set
= isl_set_copy(uncompressed
);
898 if (node
->compressed
)
899 set
= isl_set_preimage_pw_multi_aff(set
,
900 isl_pw_multi_aff_copy(node
->decompress
));
901 set
= isl_set_from_basic_set(isl_set_simple_hull(set
));
902 mv
= isl_multi_val_zero(isl_set_get_space(set
));
903 n
= isl_set_dim(set
, isl_dim_set
);
905 mv
= isl_multi_val_free(mv
);
906 for (j
= 0; j
< n
; ++j
) {
910 v
= compute_size(isl_set_copy(set
), j
);
911 is_zero
= isl_val_is_zero(v
);
912 mv
= isl_multi_val_set_val(mv
, j
, v
);
913 if (is_zero
>= 0 && is_zero
) {
914 isl_multi_val_free(mv
);
915 if (project_out_fixed(node
, uncompressed
, set
, j
) < 0)
916 return isl_stat_error
;
917 return compute_sizes(node
, uncompressed
);
923 return isl_stat_error
;
927 /* Compute the size of the instance set "set" of "node", after compression,
928 * as well as bounds on the corresponding coefficients, if needed.
930 * The sizes are needed when the schedule_treat_coalescing option is set.
931 * The bounds are needed when the schedule_treat_coalescing option or
932 * the schedule_max_coefficient option is set.
934 * If the schedule_treat_coalescing option is not set, then at most
935 * the bounds need to be set and this is done in set_max_coefficient.
936 * Otherwise, compute the size of the compressed domain
937 * in each direction and store the results in node->size.
938 * Finally, set the bounds on the coefficients based on the sizes
939 * and the schedule_max_coefficient option in compute_max_coefficient.
941 static isl_stat
compute_sizes_and_max(isl_ctx
*ctx
, struct isl_sched_node
*node
,
942 __isl_take isl_set
*set
)
946 if (!isl_options_get_schedule_treat_coalescing(ctx
)) {
948 return set_max_coefficient(ctx
, node
);
951 r
= compute_sizes(node
, set
);
954 return isl_stat_error
;
955 return compute_max_coefficient(ctx
, node
);
958 /* Add a new node to the graph representing the given instance set.
959 * "nvar" is the (possibly compressed) number of variables and
960 * may be smaller than then number of set variables in "set"
961 * if "compressed" is set.
962 * If "compressed" is set, then "hull" represents the constraints
963 * that were used to derive the compression, while "compress" and
964 * "decompress" map the original space to the compressed space and
966 * If "compressed" is not set, then "hull", "compress" and "decompress"
969 * Compute the size of the instance set and bounds on the coefficients,
972 static isl_stat
add_node(struct isl_sched_graph
*graph
,
973 __isl_take isl_set
*set
, int nvar
, int compressed
,
974 __isl_take isl_set
*hull
, __isl_take isl_multi_aff
*compress
,
975 __isl_take isl_pw_multi_aff
*decompress
)
982 struct isl_sched_node
*node
;
984 nparam
= isl_set_dim(set
, isl_dim_param
);
988 ctx
= isl_set_get_ctx(set
);
989 if (!ctx
->opt
->schedule_parametric
)
991 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
992 node
= &graph
->node
[graph
->n
];
994 space
= isl_set_get_space(set
);
997 node
->nparam
= nparam
;
999 node
->sched_map
= NULL
;
1000 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
1001 node
->coincident
= coincident
;
1002 node
->compressed
= compressed
;
1004 node
->compress
= compress
;
1005 node
->decompress
= decompress
;
1006 if (compute_sizes_and_max(ctx
, node
, set
) < 0)
1007 return isl_stat_error
;
1009 if (!space
|| !sched
|| (graph
->max_row
&& !coincident
))
1010 return isl_stat_error
;
1011 if (compressed
&& (!hull
|| !compress
|| !decompress
))
1012 return isl_stat_error
;
1018 isl_multi_aff_free(compress
);
1019 isl_pw_multi_aff_free(decompress
);
1020 return isl_stat_error
;
1023 /* Add a new node to the graph representing the given set.
1025 * If any of the set variables is defined by an equality, then
1026 * we perform variable compression such that we can perform
1027 * the scheduling on the compressed domain.
1028 * In this case, an identifier is used that references the new node
1029 * such that each compressed space is unique and
1030 * such that the node can be recovered from the compressed space.
1032 static isl_stat
extract_node(__isl_take isl_set
*set
, void *user
)
1035 isl_bool has_equality
;
1037 isl_basic_set
*hull
;
1040 isl_multi_aff
*compress
, *decompress_ma
;
1041 isl_pw_multi_aff
*decompress
;
1042 struct isl_sched_graph
*graph
= user
;
1044 hull
= isl_set_affine_hull(isl_set_copy(set
));
1045 hull
= isl_basic_set_remove_divs(hull
);
1046 nvar
= isl_set_dim(set
, isl_dim_set
);
1047 has_equality
= has_any_defining_equality(hull
);
1049 if (nvar
< 0 || has_equality
< 0)
1051 if (!has_equality
) {
1052 isl_basic_set_free(hull
);
1053 return add_node(graph
, set
, nvar
, 0, NULL
, NULL
, NULL
);
1056 id
= construct_compressed_id(set
, &graph
->node
[graph
->n
]);
1057 morph
= isl_basic_set_variable_compression_with_id(hull
, id
);
1059 nvar
= isl_morph_ran_dim(morph
, isl_dim_set
);
1061 set
= isl_set_free(set
);
1062 compress
= isl_morph_get_var_multi_aff(morph
);
1063 morph
= isl_morph_inverse(morph
);
1064 decompress_ma
= isl_morph_get_var_multi_aff(morph
);
1065 decompress
= isl_pw_multi_aff_from_multi_aff(decompress_ma
);
1066 isl_morph_free(morph
);
1068 hull_set
= isl_set_from_basic_set(hull
);
1069 return add_node(graph
, set
, nvar
, 1, hull_set
, compress
, decompress
);
1071 isl_basic_set_free(hull
);
1073 return isl_stat_error
;
1076 struct isl_extract_edge_data
{
1077 enum isl_edge_type type
;
1078 struct isl_sched_graph
*graph
;
1081 /* Merge edge2 into edge1, freeing the contents of edge2.
1082 * Return 0 on success and -1 on failure.
1084 * edge1 and edge2 are assumed to have the same value for the map field.
1086 static int merge_edge(struct isl_sched_edge
*edge1
,
1087 struct isl_sched_edge
*edge2
)
1089 edge1
->types
|= edge2
->types
;
1090 isl_map_free(edge2
->map
);
1092 if (isl_sched_edge_is_condition(edge2
)) {
1093 if (!edge1
->tagged_condition
)
1094 edge1
->tagged_condition
= edge2
->tagged_condition
;
1096 edge1
->tagged_condition
=
1097 isl_union_map_union(edge1
->tagged_condition
,
1098 edge2
->tagged_condition
);
1101 if (isl_sched_edge_is_conditional_validity(edge2
)) {
1102 if (!edge1
->tagged_validity
)
1103 edge1
->tagged_validity
= edge2
->tagged_validity
;
1105 edge1
->tagged_validity
=
1106 isl_union_map_union(edge1
->tagged_validity
,
1107 edge2
->tagged_validity
);
1110 if (isl_sched_edge_is_condition(edge2
) && !edge1
->tagged_condition
)
1112 if (isl_sched_edge_is_conditional_validity(edge2
) &&
1113 !edge1
->tagged_validity
)
1119 /* Insert dummy tags in domain and range of "map".
1121 * In particular, if "map" is of the form
1127 * [A -> dummy_tag] -> [B -> dummy_tag]
1129 * where the dummy_tags are identical and equal to any dummy tags
1130 * introduced by any other call to this function.
1132 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
1138 isl_set
*domain
, *range
;
1140 ctx
= isl_map_get_ctx(map
);
1142 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
1143 space
= isl_space_params(isl_map_get_space(map
));
1144 space
= isl_space_set_from_params(space
);
1145 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
1146 space
= isl_space_map_from_set(space
);
1148 domain
= isl_map_wrap(map
);
1149 range
= isl_map_wrap(isl_map_universe(space
));
1150 map
= isl_map_from_domain_and_range(domain
, range
);
1151 map
= isl_map_zip(map
);
1156 /* Given that at least one of "src" or "dst" is compressed, return
1157 * a map between the spaces of these nodes restricted to the affine
1158 * hull that was used in the compression.
1160 static __isl_give isl_map
*extract_hull(struct isl_sched_node
*src
,
1161 struct isl_sched_node
*dst
)
1165 if (src
->compressed
)
1166 dom
= isl_set_copy(src
->hull
);
1168 dom
= isl_set_universe(isl_space_copy(src
->space
));
1169 if (dst
->compressed
)
1170 ran
= isl_set_copy(dst
->hull
);
1172 ran
= isl_set_universe(isl_space_copy(dst
->space
));
1174 return isl_map_from_domain_and_range(dom
, ran
);
1177 /* Intersect the domains of the nested relations in domain and range
1178 * of "tagged" with "map".
1180 static __isl_give isl_map
*map_intersect_domains(__isl_take isl_map
*tagged
,
1181 __isl_keep isl_map
*map
)
1185 tagged
= isl_map_zip(tagged
);
1186 set
= isl_map_wrap(isl_map_copy(map
));
1187 tagged
= isl_map_intersect_domain(tagged
, set
);
1188 tagged
= isl_map_zip(tagged
);
1192 /* Return a pointer to the node that lives in the domain space of "map",
1193 * an invalid node if there is no such node, or NULL in case of error.
1195 static struct isl_sched_node
*find_domain_node(isl_ctx
*ctx
,
1196 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1198 struct isl_sched_node
*node
;
1201 space
= isl_space_domain(isl_map_get_space(map
));
1202 node
= isl_sched_graph_find_node(ctx
, graph
, space
);
1203 isl_space_free(space
);
1208 /* Return a pointer to the node that lives in the range space of "map",
1209 * an invalid node if there is no such node, or NULL in case of error.
1211 static struct isl_sched_node
*find_range_node(isl_ctx
*ctx
,
1212 struct isl_sched_graph
*graph
, __isl_keep isl_map
*map
)
1214 struct isl_sched_node
*node
;
1217 space
= isl_space_range(isl_map_get_space(map
));
1218 node
= isl_sched_graph_find_node(ctx
, graph
, space
);
1219 isl_space_free(space
);
1224 /* Refrain from adding a new edge based on "map".
1225 * Instead, just free the map.
1226 * "tagged" is either a copy of "map" with additional tags or NULL.
1228 static isl_stat
skip_edge(__isl_take isl_map
*map
, __isl_take isl_map
*tagged
)
1231 isl_map_free(tagged
);
1236 /* Add a new edge to the graph based on the given map
1237 * and add it to data->graph->edge_table[data->type].
1238 * If a dependence relation of a given type happens to be identical
1239 * to one of the dependence relations of a type that was added before,
1240 * then we don't create a new edge, but instead mark the original edge
1241 * as also representing a dependence of the current type.
1243 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1244 * may be specified as "tagged" dependence relations. That is, "map"
1245 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1246 * the dependence on iterations and a and b are tags.
1247 * edge->map is set to the relation containing the elements i -> j,
1248 * while edge->tagged_condition and edge->tagged_validity contain
1249 * the union of all the "map" relations
1250 * for which extract_edge is called that result in the same edge->map.
1252 * If the source or the destination node is compressed, then
1253 * intersect both "map" and "tagged" with the constraints that
1254 * were used to construct the compression.
1255 * This ensures that there are no schedule constraints defined
1256 * outside of these domains, while the scheduler no longer has
1257 * any control over those outside parts.
1259 static isl_stat
extract_edge(__isl_take isl_map
*map
, void *user
)
1262 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1263 struct isl_extract_edge_data
*data
= user
;
1264 struct isl_sched_graph
*graph
= data
->graph
;
1265 struct isl_sched_node
*src
, *dst
;
1266 struct isl_sched_edge
*edge
;
1267 isl_map
*tagged
= NULL
;
1269 if (data
->type
== isl_edge_condition
||
1270 data
->type
== isl_edge_conditional_validity
) {
1271 if (isl_map_can_zip(map
)) {
1272 tagged
= isl_map_copy(map
);
1273 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
1275 tagged
= insert_dummy_tags(isl_map_copy(map
));
1279 src
= find_domain_node(ctx
, graph
, map
);
1280 dst
= find_range_node(ctx
, graph
, map
);
1284 if (!isl_sched_graph_is_node(graph
, src
) ||
1285 !isl_sched_graph_is_node(graph
, dst
))
1286 return skip_edge(map
, tagged
);
1288 if (src
->compressed
|| dst
->compressed
) {
1290 hull
= extract_hull(src
, dst
);
1292 tagged
= map_intersect_domains(tagged
, hull
);
1293 map
= isl_map_intersect(map
, hull
);
1296 empty
= isl_map_plain_is_empty(map
);
1300 return skip_edge(map
, tagged
);
1302 graph
->edge
[graph
->n_edge
].src
= src
;
1303 graph
->edge
[graph
->n_edge
].dst
= dst
;
1304 graph
->edge
[graph
->n_edge
].map
= map
;
1305 graph
->edge
[graph
->n_edge
].types
= 0;
1306 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
1307 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
1308 set_type(&graph
->edge
[graph
->n_edge
], data
->type
);
1309 if (data
->type
== isl_edge_condition
)
1310 graph
->edge
[graph
->n_edge
].tagged_condition
=
1311 isl_union_map_from_map(tagged
);
1312 if (data
->type
== isl_edge_conditional_validity
)
1313 graph
->edge
[graph
->n_edge
].tagged_validity
=
1314 isl_union_map_from_map(tagged
);
1316 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
1319 return isl_stat_error
;
1321 if (edge
== &graph
->edge
[graph
->n_edge
])
1322 return graph_edge_table_add(ctx
, graph
, data
->type
,
1323 &graph
->edge
[graph
->n_edge
++]);
1325 if (merge_edge(edge
, &graph
->edge
[graph
->n_edge
]) < 0)
1326 return isl_stat_error
;
1328 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1331 isl_map_free(tagged
);
1332 return isl_stat_error
;
1335 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1337 * The context is included in the domain before the nodes of
1338 * the graphs are extracted in order to be able to exploit
1339 * any possible additional equalities.
1340 * Note that this intersection is only performed locally here.
1342 isl_stat
isl_sched_graph_init(struct isl_sched_graph
*graph
,
1343 __isl_keep isl_schedule_constraints
*sc
)
1346 isl_union_set
*domain
;
1348 struct isl_extract_edge_data data
;
1349 enum isl_edge_type i
;
1354 return isl_stat_error
;
1356 ctx
= isl_schedule_constraints_get_ctx(sc
);
1358 domain
= isl_schedule_constraints_get_domain(sc
);
1359 n
= isl_union_set_n_set(domain
);
1361 isl_union_set_free(domain
);
1363 return isl_stat_error
;
1365 n
= isl_schedule_constraints_n_map(sc
);
1366 if (n
< 0 || graph_alloc(ctx
, graph
, graph
->n
, n
) < 0)
1367 return isl_stat_error
;
1369 if (compute_max_row(graph
, sc
) < 0)
1370 return isl_stat_error
;
1371 graph
->root
= graph
;
1373 domain
= isl_schedule_constraints_get_domain(sc
);
1374 domain
= isl_union_set_intersect_params(domain
,
1375 isl_schedule_constraints_get_context(sc
));
1376 r
= isl_union_set_foreach_set(domain
, &extract_node
, graph
);
1377 isl_union_set_free(domain
);
1379 return isl_stat_error
;
1380 if (graph_init_table(ctx
, graph
) < 0)
1381 return isl_stat_error
;
1382 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1385 c
= isl_schedule_constraints_get(sc
, i
);
1386 n
= isl_union_map_n_map(c
);
1387 graph
->max_edge
[i
] = n
;
1388 isl_union_map_free(c
);
1390 return isl_stat_error
;
1392 if (graph_init_edge_tables(ctx
, graph
) < 0)
1393 return isl_stat_error
;
1396 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
1400 c
= isl_schedule_constraints_get(sc
, i
);
1401 r
= isl_union_map_foreach_map(c
, &extract_edge
, &data
);
1402 isl_union_map_free(c
);
1404 return isl_stat_error
;
1410 /* Check whether there is any dependence from node[j] to node[i]
1411 * or from node[i] to node[j].
1413 static isl_bool
node_follows_weak(int i
, int j
, void *user
)
1416 struct isl_sched_graph
*graph
= user
;
1418 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1421 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1424 /* Check whether there is a (conditional) validity dependence from node[j]
1425 * to node[i], forcing node[i] to follow node[j].
1427 static isl_bool
node_follows_strong(int i
, int j
, void *user
)
1429 struct isl_sched_graph
*graph
= user
;
1431 return isl_sched_graph_has_validity_edge(graph
, &graph
->node
[j
],
1435 /* Use Tarjan's algorithm for computing the strongly connected components
1436 * in the dependence graph only considering those edges defined by "follows".
1438 isl_stat
isl_sched_graph_detect_ccs(isl_ctx
*ctx
,
1439 struct isl_sched_graph
*graph
,
1440 isl_bool (*follows
)(int i
, int j
, void *user
))
1443 struct isl_tarjan_graph
*g
= NULL
;
1445 g
= isl_tarjan_graph_init(ctx
, graph
->n
, follows
, graph
);
1447 return isl_stat_error
;
1453 while (g
->order
[i
] != -1) {
1454 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1462 isl_tarjan_graph_free(g
);
1467 /* Apply Tarjan's algorithm to detect the strongly connected components
1468 * in the dependence graph.
1469 * Only consider the (conditional) validity dependences and clear "weak".
1471 static isl_stat
detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1474 return isl_sched_graph_detect_ccs(ctx
, graph
, &node_follows_strong
);
1477 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1478 * in the dependence graph.
1479 * Consider all dependences and set "weak".
1481 static isl_stat
detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1484 return isl_sched_graph_detect_ccs(ctx
, graph
, &node_follows_weak
);
1487 static int cmp_scc(const void *a
, const void *b
, void *data
)
1489 struct isl_sched_graph
*graph
= data
;
1493 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1496 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1498 static int sort_sccs(struct isl_sched_graph
*graph
)
1500 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1503 /* Return a non-parametric set in the compressed space of "node" that is
1504 * bounded by the size in each direction
1506 * { [x] : -S_i <= x_i <= S_i }
1508 * If S_i is infinity in direction i, then there are no constraints
1509 * in that direction.
1511 * Cache the result in node->bounds.
1513 static __isl_give isl_basic_set
*get_size_bounds(struct isl_sched_node
*node
)
1516 isl_basic_set
*bounds
;
1520 return isl_basic_set_copy(node
->bounds
);
1522 if (node
->compressed
)
1523 space
= isl_pw_multi_aff_get_domain_space(node
->decompress
);
1525 space
= isl_space_copy(node
->space
);
1526 space
= isl_space_drop_all_params(space
);
1527 bounds
= isl_basic_set_universe(space
);
1529 for (i
= 0; i
< node
->nvar
; ++i
) {
1532 size
= isl_multi_val_get_val(node
->sizes
, i
);
1534 return isl_basic_set_free(bounds
);
1535 if (!isl_val_is_int(size
)) {
1539 bounds
= isl_basic_set_upper_bound_val(bounds
, isl_dim_set
, i
,
1540 isl_val_copy(size
));
1541 bounds
= isl_basic_set_lower_bound_val(bounds
, isl_dim_set
, i
,
1545 node
->bounds
= isl_basic_set_copy(bounds
);
1549 /* Compress the dependence relation "map", if needed, i.e.,
1550 * when the source node "src" and/or the destination node "dst"
1551 * has been compressed.
1553 static __isl_give isl_map
*compress(__isl_take isl_map
*map
,
1554 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1556 if (src
->compressed
)
1557 map
= isl_map_preimage_domain_pw_multi_aff(map
,
1558 isl_pw_multi_aff_copy(src
->decompress
));
1559 if (dst
->compressed
)
1560 map
= isl_map_preimage_range_pw_multi_aff(map
,
1561 isl_pw_multi_aff_copy(dst
->decompress
));
1565 /* Drop some constraints from "delta" that could be exploited
1566 * to construct loop coalescing schedules.
1567 * In particular, drop those constraint that bound the difference
1568 * to the size of the domain.
1569 * First project out the parameters to improve the effectiveness.
1571 static __isl_give isl_set
*drop_coalescing_constraints(
1572 __isl_take isl_set
*delta
, struct isl_sched_node
*node
)
1575 isl_basic_set
*bounds
;
1577 nparam
= isl_set_dim(delta
, isl_dim_param
);
1579 return isl_set_free(delta
);
1581 bounds
= get_size_bounds(node
);
1583 delta
= isl_set_project_out(delta
, isl_dim_param
, 0, nparam
);
1584 delta
= isl_set_remove_divs(delta
);
1585 delta
= isl_set_plain_gist_basic_set(delta
, bounds
);
1589 /* Given a dependence relation R from "node" to itself,
1590 * construct the set of coefficients of valid constraints for elements
1591 * in that dependence relation.
1592 * In particular, the result contains tuples of coefficients
1593 * c_0, c_n, c_x such that
1595 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1599 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1601 * We choose here to compute the dual of delta R.
1602 * Alternatively, we could have computed the dual of R, resulting
1603 * in a set of tuples c_0, c_n, c_x, c_y, and then
1604 * plugged in (c_0, c_n, c_x, -c_x).
1606 * If "need_param" is set, then the resulting coefficients effectively
1607 * include coefficients for the parameters c_n. Otherwise, they may
1608 * have been projected out already.
1609 * Since the constraints may be different for these two cases,
1610 * they are stored in separate caches.
1611 * In particular, if no parameter coefficients are required and
1612 * the schedule_treat_coalescing option is set, then the parameters
1613 * are projected out and some constraints that could be exploited
1614 * to construct coalescing schedules are removed before the dual
1617 * If "node" has been compressed, then the dependence relation
1618 * is also compressed before the set of coefficients is computed.
1620 static __isl_give isl_basic_set
*intra_coefficients(
1621 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1622 __isl_take isl_map
*map
, int need_param
)
1627 isl_basic_set
*coef
;
1628 isl_maybe_isl_basic_set m
;
1629 isl_map_to_basic_set
**hmap
= &graph
->intra_hmap
;
1635 ctx
= isl_map_get_ctx(map
);
1636 treat
= !need_param
&& isl_options_get_schedule_treat_coalescing(ctx
);
1638 hmap
= &graph
->intra_hmap_param
;
1639 m
= isl_map_to_basic_set_try_get(*hmap
, map
);
1640 if (m
.valid
< 0 || m
.valid
) {
1645 key
= isl_map_copy(map
);
1646 map
= compress(map
, node
, node
);
1647 delta
= isl_map_deltas(map
);
1649 delta
= drop_coalescing_constraints(delta
, node
);
1650 delta
= isl_set_remove_divs(delta
);
1651 coef
= isl_set_coefficients(delta
);
1652 *hmap
= isl_map_to_basic_set_set(*hmap
, key
, isl_basic_set_copy(coef
));
1657 /* Given a dependence relation R, construct the set of coefficients
1658 * of valid constraints for elements in that dependence relation.
1659 * In particular, the result contains tuples of coefficients
1660 * c_0, c_n, c_x, c_y such that
1662 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1664 * If the source or destination nodes of "edge" have been compressed,
1665 * then the dependence relation is also compressed before
1666 * the set of coefficients is computed.
1668 static __isl_give isl_basic_set
*inter_coefficients(
1669 struct isl_sched_graph
*graph
, struct isl_sched_edge
*edge
,
1670 __isl_take isl_map
*map
)
1674 isl_basic_set
*coef
;
1675 isl_maybe_isl_basic_set m
;
1677 m
= isl_map_to_basic_set_try_get(graph
->inter_hmap
, map
);
1678 if (m
.valid
< 0 || m
.valid
) {
1683 key
= isl_map_copy(map
);
1684 map
= compress(map
, edge
->src
, edge
->dst
);
1685 set
= isl_map_wrap(isl_map_remove_divs(map
));
1686 coef
= isl_set_coefficients(set
);
1687 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, key
,
1688 isl_basic_set_copy(coef
));
1693 /* Return the position of the coefficients of the variables in
1694 * the coefficients constraints "coef".
1696 * The space of "coef" is of the form
1698 * { coefficients[[cst, params] -> S] }
1700 * Return the position of S.
1702 static isl_size
coef_var_offset(__isl_keep isl_basic_set
*coef
)
1707 space
= isl_space_unwrap(isl_basic_set_get_space(coef
));
1708 offset
= isl_space_dim(space
, isl_dim_in
);
1709 isl_space_free(space
);
1714 /* Return the offset of the coefficient of the constant term of "node"
1717 * Within each node, the coefficients have the following order:
1718 * - positive and negative parts of c_i_x
1719 * - c_i_n (if parametric)
1722 static int node_cst_coef_offset(struct isl_sched_node
*node
)
1724 return node
->start
+ 2 * node
->nvar
+ node
->nparam
;
1727 /* Return the offset of the coefficients of the parameters of "node"
1730 * Within each node, the coefficients have the following order:
1731 * - positive and negative parts of c_i_x
1732 * - c_i_n (if parametric)
1735 static int node_par_coef_offset(struct isl_sched_node
*node
)
1737 return node
->start
+ 2 * node
->nvar
;
1740 /* Return the offset of the coefficients of the variables of "node"
1743 * Within each node, the coefficients have the following order:
1744 * - positive and negative parts of c_i_x
1745 * - c_i_n (if parametric)
1748 static int node_var_coef_offset(struct isl_sched_node
*node
)
1753 /* Return the position of the pair of variables encoding
1754 * coefficient "i" of "node".
1756 * The order of these variable pairs is the opposite of
1757 * that of the coefficients, with 2 variables per coefficient.
1759 static int node_var_coef_pos(struct isl_sched_node
*node
, int i
)
1761 return node_var_coef_offset(node
) + 2 * (node
->nvar
- 1 - i
);
1764 /* Construct an isl_dim_map for mapping constraints on coefficients
1765 * for "node" to the corresponding positions in graph->lp.
1766 * "offset" is the offset of the coefficients for the variables
1767 * in the input constraints.
1768 * "s" is the sign of the mapping.
1770 * The input constraints are given in terms of the coefficients
1771 * (c_0, c_x) or (c_0, c_n, c_x).
1772 * The mapping produced by this function essentially plugs in
1773 * (0, c_i_x^+ - c_i_x^-) if s = 1 and
1774 * (0, -c_i_x^+ + c_i_x^-) if s = -1 or
1775 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1776 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1777 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1778 * Furthermore, the order of these pairs is the opposite of that
1779 * of the corresponding coefficients.
1781 * The caller can extend the mapping to also map the other coefficients
1782 * (and therefore not plug in 0).
1784 static __isl_give isl_dim_map
*intra_dim_map(isl_ctx
*ctx
,
1785 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
,
1790 isl_dim_map
*dim_map
;
1792 total
= isl_basic_set_dim(graph
->lp
, isl_dim_all
);
1793 if (!node
|| total
< 0)
1796 pos
= node_var_coef_pos(node
, 0);
1797 dim_map
= isl_dim_map_alloc(ctx
, total
);
1798 isl_dim_map_range(dim_map
, pos
, -2, offset
, 1, node
->nvar
, -s
);
1799 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
, 1, node
->nvar
, s
);
1804 /* Construct an isl_dim_map for mapping constraints on coefficients
1805 * for "src" (node i) and "dst" (node j) to the corresponding positions
1807 * "offset" is the offset of the coefficients for the variables of "src"
1808 * in the input constraints.
1809 * "s" is the sign of the mapping.
1811 * The input constraints are given in terms of the coefficients
1812 * (c_0, c_n, c_x, c_y).
1813 * The mapping produced by this function essentially plugs in
1814 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1815 * -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-) if s = 1 and
1816 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1817 * c_i_x^+ - c_i_x^-, -(c_j_x^+ - c_j_x^-)) if s = -1.
1818 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1819 * Furthermore, the order of these pairs is the opposite of that
1820 * of the corresponding coefficients.
1822 * The caller can further extend the mapping.
1824 static __isl_give isl_dim_map
*inter_dim_map(isl_ctx
*ctx
,
1825 struct isl_sched_graph
*graph
, struct isl_sched_node
*src
,
1826 struct isl_sched_node
*dst
, int offset
, int s
)
1830 isl_dim_map
*dim_map
;
1832 total
= isl_basic_set_dim(graph
->lp
, isl_dim_all
);
1833 if (!src
|| !dst
|| total
< 0)
1836 dim_map
= isl_dim_map_alloc(ctx
, total
);
1838 pos
= node_cst_coef_offset(dst
);
1839 isl_dim_map_range(dim_map
, pos
, 0, 0, 0, 1, s
);
1840 pos
= node_par_coef_offset(dst
);
1841 isl_dim_map_range(dim_map
, pos
, 1, 1, 1, dst
->nparam
, s
);
1842 pos
= node_var_coef_pos(dst
, 0);
1843 isl_dim_map_range(dim_map
, pos
, -2, offset
+ src
->nvar
, 1,
1845 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
+ src
->nvar
, 1,
1848 pos
= node_cst_coef_offset(src
);
1849 isl_dim_map_range(dim_map
, pos
, 0, 0, 0, 1, -s
);
1850 pos
= node_par_coef_offset(src
);
1851 isl_dim_map_range(dim_map
, pos
, 1, 1, 1, src
->nparam
, -s
);
1852 pos
= node_var_coef_pos(src
, 0);
1853 isl_dim_map_range(dim_map
, pos
, -2, offset
, 1, src
->nvar
, s
);
1854 isl_dim_map_range(dim_map
, pos
+ 1, -2, offset
, 1, src
->nvar
, -s
);
1859 /* Add the constraints from "src" to "dst" using "dim_map",
1860 * after making sure there is enough room in "dst" for the extra constraints.
1862 static __isl_give isl_basic_set
*add_constraints_dim_map(
1863 __isl_take isl_basic_set
*dst
, __isl_take isl_basic_set
*src
,
1864 __isl_take isl_dim_map
*dim_map
)
1866 isl_size n_eq
, n_ineq
;
1868 n_eq
= isl_basic_set_n_equality(src
);
1869 n_ineq
= isl_basic_set_n_inequality(src
);
1870 if (n_eq
< 0 || n_ineq
< 0)
1871 dst
= isl_basic_set_free(dst
);
1872 dst
= isl_basic_set_extend_constraints(dst
, n_eq
, n_ineq
);
1873 dst
= isl_basic_set_add_constraints_dim_map(dst
, src
, dim_map
);
1877 /* Add constraints to graph->lp that force validity for the given
1878 * dependence from a node i to itself.
1879 * That is, add constraints that enforce
1881 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1882 * = c_i_x (y - x) >= 0
1884 * for each (x,y) in R.
1885 * We obtain general constraints on coefficients (c_0, c_x)
1886 * of valid constraints for (y - x) and then plug in (0, c_i_x^+ - c_i_x^-),
1887 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1888 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1889 * Note that the result of intra_coefficients may also contain
1890 * parameter coefficients c_n, in which case 0 is plugged in for them as well.
1892 static isl_stat
add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1893 struct isl_sched_edge
*edge
)
1896 isl_map
*map
= isl_map_copy(edge
->map
);
1897 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1898 isl_dim_map
*dim_map
;
1899 isl_basic_set
*coef
;
1900 struct isl_sched_node
*node
= edge
->src
;
1902 coef
= intra_coefficients(graph
, node
, map
, 0);
1904 offset
= coef_var_offset(coef
);
1906 coef
= isl_basic_set_free(coef
);
1908 return isl_stat_error
;
1910 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
1911 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1916 /* Add constraints to graph->lp that force validity for the given
1917 * dependence from node i to node j.
1918 * That is, add constraints that enforce
1920 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1922 * for each (x,y) in R.
1923 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1924 * of valid constraints for R and then plug in
1925 * (c_j_0 - c_i_0, c_j_n - c_i_n, -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-),
1926 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1927 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1929 static isl_stat
add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1930 struct isl_sched_edge
*edge
)
1935 isl_dim_map
*dim_map
;
1936 isl_basic_set
*coef
;
1937 struct isl_sched_node
*src
= edge
->src
;
1938 struct isl_sched_node
*dst
= edge
->dst
;
1941 return isl_stat_error
;
1943 map
= isl_map_copy(edge
->map
);
1944 ctx
= isl_map_get_ctx(map
);
1945 coef
= inter_coefficients(graph
, edge
, map
);
1947 offset
= coef_var_offset(coef
);
1949 coef
= isl_basic_set_free(coef
);
1951 return isl_stat_error
;
1953 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
1955 edge
->start
= graph
->lp
->n_ineq
;
1956 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
1958 return isl_stat_error
;
1959 edge
->end
= graph
->lp
->n_ineq
;
1964 /* Add constraints to graph->lp that bound the dependence distance for the given
1965 * dependence from a node i to itself.
1966 * If s = 1, we add the constraint
1968 * c_i_x (y - x) <= m_0 + m_n n
1972 * -c_i_x (y - x) + m_0 + m_n n >= 0
1974 * for each (x,y) in R.
1975 * If s = -1, we add the constraint
1977 * -c_i_x (y - x) <= m_0 + m_n n
1981 * c_i_x (y - x) + m_0 + m_n n >= 0
1983 * for each (x,y) in R.
1984 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1985 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1986 * with each coefficient (except m_0) represented as a pair of non-negative
1990 * If "local" is set, then we add constraints
1992 * c_i_x (y - x) <= 0
1996 * -c_i_x (y - x) <= 0
1998 * instead, forcing the dependence distance to be (less than or) equal to 0.
1999 * That is, we plug in (0, 0, -s * c_i_x),
2000 * intra_coefficients is not required to have c_n in its result when
2001 * "local" is set. If they are missing, then (0, -s * c_i_x) is plugged in.
2002 * Note that dependences marked local are treated as validity constraints
2003 * by add_all_validity_constraints and therefore also have
2004 * their distances bounded by 0 from below.
2006 static isl_stat
add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
2007 struct isl_sched_edge
*edge
, int s
, int local
)
2011 isl_map
*map
= isl_map_copy(edge
->map
);
2012 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2013 isl_dim_map
*dim_map
;
2014 isl_basic_set
*coef
;
2015 struct isl_sched_node
*node
= edge
->src
;
2017 coef
= intra_coefficients(graph
, node
, map
, !local
);
2018 nparam
= isl_space_dim(node
->space
, isl_dim_param
);
2020 offset
= coef_var_offset(coef
);
2021 if (nparam
< 0 || offset
< 0)
2022 coef
= isl_basic_set_free(coef
);
2024 return isl_stat_error
;
2026 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, -s
);
2029 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
2030 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
2031 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
2033 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
2038 /* Add constraints to graph->lp that bound the dependence distance for the given
2039 * dependence from node i to node j.
2040 * If s = 1, we add the constraint
2042 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
2047 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
2050 * for each (x,y) in R.
2051 * If s = -1, we add the constraint
2053 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
2058 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
2061 * for each (x,y) in R.
2062 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
2063 * of valid constraints for R and then plug in
2064 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
2065 * s*c_i_x, -s*c_j_x)
2066 * with each coefficient (except m_0, c_*_0 and c_*_n)
2067 * represented as a pair of non-negative coefficients.
2070 * If "local" is set (and s = 1), then we add constraints
2072 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
2076 * -((c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x)) >= 0
2078 * instead, forcing the dependence distance to be (less than or) equal to 0.
2079 * That is, we plug in
2080 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, s*c_i_x, -s*c_j_x).
2081 * Note that dependences marked local are treated as validity constraints
2082 * by add_all_validity_constraints and therefore also have
2083 * their distances bounded by 0 from below.
2085 static isl_stat
add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
2086 struct isl_sched_edge
*edge
, int s
, int local
)
2090 isl_map
*map
= isl_map_copy(edge
->map
);
2091 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2092 isl_dim_map
*dim_map
;
2093 isl_basic_set
*coef
;
2094 struct isl_sched_node
*src
= edge
->src
;
2095 struct isl_sched_node
*dst
= edge
->dst
;
2097 coef
= inter_coefficients(graph
, edge
, map
);
2098 nparam
= isl_space_dim(src
->space
, isl_dim_param
);
2100 offset
= coef_var_offset(coef
);
2101 if (nparam
< 0 || offset
< 0)
2102 coef
= isl_basic_set_free(coef
);
2104 return isl_stat_error
;
2106 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, -s
);
2109 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
2110 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
2111 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
2114 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
2119 /* Should the distance over "edge" be forced to zero?
2120 * That is, is it marked as a local edge?
2121 * If "use_coincidence" is set, then coincidence edges are treated
2124 static int force_zero(struct isl_sched_edge
*edge
, int use_coincidence
)
2126 return is_local(edge
) || (use_coincidence
&& is_coincidence(edge
));
2129 /* Add all validity constraints to graph->lp.
2131 * An edge that is forced to be local needs to have its dependence
2132 * distances equal to zero. We take care of bounding them by 0 from below
2133 * here. add_all_proximity_constraints takes care of bounding them by 0
2136 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2137 * Otherwise, we ignore them.
2139 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
2140 int use_coincidence
)
2144 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2145 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2148 zero
= force_zero(edge
, use_coincidence
);
2149 if (!is_validity(edge
) && !zero
)
2151 if (edge
->src
!= edge
->dst
)
2153 if (add_intra_validity_constraints(graph
, edge
) < 0)
2157 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2158 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2161 zero
= force_zero(edge
, use_coincidence
);
2162 if (!is_validity(edge
) && !zero
)
2164 if (edge
->src
== edge
->dst
)
2166 if (add_inter_validity_constraints(graph
, edge
) < 0)
2173 /* Add constraints to graph->lp that bound the dependence distance
2174 * for all dependence relations.
2175 * If a given proximity dependence is identical to a validity
2176 * dependence, then the dependence distance is already bounded
2177 * from below (by zero), so we only need to bound the distance
2178 * from above. (This includes the case of "local" dependences
2179 * which are treated as validity dependence by add_all_validity_constraints.)
2180 * Otherwise, we need to bound the distance both from above and from below.
2182 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2183 * Otherwise, we ignore them.
2185 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
2186 int use_coincidence
)
2190 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2191 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2194 zero
= force_zero(edge
, use_coincidence
);
2195 if (!isl_sched_edge_is_proximity(edge
) && !zero
)
2197 if (edge
->src
== edge
->dst
&&
2198 add_intra_proximity_constraints(graph
, edge
, 1, zero
) < 0)
2200 if (edge
->src
!= edge
->dst
&&
2201 add_inter_proximity_constraints(graph
, edge
, 1, zero
) < 0)
2203 if (is_validity(edge
) || zero
)
2205 if (edge
->src
== edge
->dst
&&
2206 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
2208 if (edge
->src
!= edge
->dst
&&
2209 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
2216 /* Normalize the rows of "indep" such that all rows are lexicographically
2217 * positive and such that each row contains as many final zeros as possible,
2218 * given the choice for the previous rows.
2219 * Do this by performing elementary row operations.
2221 static __isl_give isl_mat
*normalize_independent(__isl_take isl_mat
*indep
)
2223 indep
= isl_mat_reverse_gauss(indep
);
2224 indep
= isl_mat_lexnonneg_rows(indep
);
2228 /* Extract the linear part of the current schedule for node "node".
2230 static __isl_give isl_mat
*extract_linear_schedule(struct isl_sched_node
*node
)
2232 isl_size n_row
= isl_mat_rows(node
->sched
);
2236 return isl_mat_sub_alloc(node
->sched
, 0, n_row
,
2237 1 + node
->nparam
, node
->nvar
);
2240 /* Compute a basis for the rows in the linear part of the schedule
2241 * and extend this basis to a full basis. The remaining rows
2242 * can then be used to force linear independence from the rows
2245 * In particular, given the schedule rows S, we compute
2250 * with H the Hermite normal form of S. That is, all but the
2251 * first rank columns of H are zero and so each row in S is
2252 * a linear combination of the first rank rows of Q.
2253 * The matrix Q can be used as a variable transformation
2254 * that isolates the directions of S in the first rank rows.
2255 * Transposing S U = H yields
2259 * with all but the first rank rows of H^T zero.
2260 * The last rows of U^T are therefore linear combinations
2261 * of schedule coefficients that are all zero on schedule
2262 * coefficients that are linearly dependent on the rows of S.
2263 * At least one of these combinations is non-zero on
2264 * linearly independent schedule coefficients.
2265 * The rows are normalized to involve as few of the last
2266 * coefficients as possible and to have a positive initial value.
2268 isl_stat
isl_sched_node_update_vmap(struct isl_sched_node
*node
)
2272 H
= extract_linear_schedule(node
);
2274 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
2275 isl_mat_free(node
->indep
);
2276 isl_mat_free(node
->vmap
);
2278 node
->indep
= isl_mat_transpose(U
);
2279 node
->rank
= isl_mat_initial_non_zero_cols(H
);
2280 node
->indep
= isl_mat_drop_rows(node
->indep
, 0, node
->rank
);
2281 node
->indep
= normalize_independent(node
->indep
);
2284 if (!node
->indep
|| !node
->vmap
|| node
->rank
< 0)
2285 return isl_stat_error
;
2289 /* Is "edge" marked as a validity or a conditional validity edge?
2291 static int is_any_validity(struct isl_sched_edge
*edge
)
2293 return is_validity(edge
) ||
2294 isl_sched_edge_is_conditional_validity(edge
);
2297 /* How many times should we count the constraints in "edge"?
2299 * We count as follows
2300 * validity -> 1 (>= 0)
2301 * validity+proximity -> 2 (>= 0 and upper bound)
2302 * proximity -> 2 (lower and upper bound)
2303 * local(+any) -> 2 (>= 0 and <= 0)
2305 * If an edge is only marked conditional_validity then it counts
2306 * as zero since it is only checked afterwards.
2308 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2309 * Otherwise, we ignore them.
2311 static int edge_multiplicity(struct isl_sched_edge
*edge
, int use_coincidence
)
2313 if (isl_sched_edge_is_proximity(edge
) ||
2314 force_zero(edge
, use_coincidence
))
2316 if (is_validity(edge
))
2321 /* How many times should the constraints in "edge" be counted
2322 * as a parametric intra-node constraint?
2324 * Only proximity edges that are not forced zero need
2325 * coefficient constraints that include coefficients for parameters.
2326 * If the edge is also a validity edge, then only
2327 * an upper bound is introduced. Otherwise, both lower and upper bounds
2330 static int parametric_intra_edge_multiplicity(struct isl_sched_edge
*edge
,
2331 int use_coincidence
)
2333 if (edge
->src
!= edge
->dst
)
2335 if (!isl_sched_edge_is_proximity(edge
))
2337 if (force_zero(edge
, use_coincidence
))
2339 if (is_validity(edge
))
2345 /* Add "f" times the number of equality and inequality constraints of "bset"
2346 * to "n_eq" and "n_ineq" and free "bset".
2348 static isl_stat
update_count(__isl_take isl_basic_set
*bset
,
2349 int f
, int *n_eq
, int *n_ineq
)
2353 eq
= isl_basic_set_n_equality(bset
);
2354 ineq
= isl_basic_set_n_inequality(bset
);
2355 isl_basic_set_free(bset
);
2357 if (eq
< 0 || ineq
< 0)
2358 return isl_stat_error
;
2366 /* Count the number of equality and inequality constraints
2367 * that will be added for the given map.
2369 * The edges that require parameter coefficients are counted separately.
2371 * "use_coincidence" is set if we should take into account coincidence edges.
2373 static isl_stat
count_map_constraints(struct isl_sched_graph
*graph
,
2374 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
2375 int *n_eq
, int *n_ineq
, int use_coincidence
)
2378 isl_basic_set
*coef
;
2379 int f
= edge_multiplicity(edge
, use_coincidence
);
2380 int fp
= parametric_intra_edge_multiplicity(edge
, use_coincidence
);
2387 if (edge
->src
!= edge
->dst
) {
2388 coef
= inter_coefficients(graph
, edge
, map
);
2389 return update_count(coef
, f
, n_eq
, n_ineq
);
2393 copy
= isl_map_copy(map
);
2394 coef
= intra_coefficients(graph
, edge
->src
, copy
, 1);
2395 if (update_count(coef
, fp
, n_eq
, n_ineq
) < 0)
2400 copy
= isl_map_copy(map
);
2401 coef
= intra_coefficients(graph
, edge
->src
, copy
, 0);
2402 if (update_count(coef
, f
- fp
, n_eq
, n_ineq
) < 0)
2410 return isl_stat_error
;
2413 /* Count the number of equality and inequality constraints
2414 * that will be added to the main lp problem.
2415 * We count as follows
2416 * validity -> 1 (>= 0)
2417 * validity+proximity -> 2 (>= 0 and upper bound)
2418 * proximity -> 2 (lower and upper bound)
2419 * local(+any) -> 2 (>= 0 and <= 0)
2421 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2422 * Otherwise, we ignore them.
2424 static int count_constraints(struct isl_sched_graph
*graph
,
2425 int *n_eq
, int *n_ineq
, int use_coincidence
)
2429 *n_eq
= *n_ineq
= 0;
2430 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2431 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2432 isl_map
*map
= isl_map_copy(edge
->map
);
2434 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
2435 use_coincidence
) < 0)
2442 /* Count the number of constraints that will be added by
2443 * add_bound_constant_constraints to bound the values of the constant terms
2444 * and increment *n_eq and *n_ineq accordingly.
2446 * In practice, add_bound_constant_constraints only adds inequalities.
2448 static isl_stat
count_bound_constant_constraints(isl_ctx
*ctx
,
2449 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2451 if (isl_options_get_schedule_max_constant_term(ctx
) == -1)
2454 *n_ineq
+= graph
->n
;
2459 /* Add constraints to bound the values of the constant terms in the schedule,
2460 * if requested by the user.
2462 * The maximal value of the constant terms is defined by the option
2463 * "schedule_max_constant_term".
2465 static isl_stat
add_bound_constant_constraints(isl_ctx
*ctx
,
2466 struct isl_sched_graph
*graph
)
2472 max
= isl_options_get_schedule_max_constant_term(ctx
);
2476 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2478 return isl_stat_error
;
2480 for (i
= 0; i
< graph
->n
; ++i
) {
2481 struct isl_sched_node
*node
= &graph
->node
[i
];
2484 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2486 return isl_stat_error
;
2487 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2488 pos
= node_cst_coef_offset(node
);
2489 isl_int_set_si(graph
->lp
->ineq
[k
][1 + pos
], -1);
2490 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2496 /* Count the number of constraints that will be added by
2497 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2500 * In practice, add_bound_coefficient_constraints only adds inequalities.
2502 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
2503 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
2507 if (isl_options_get_schedule_max_coefficient(ctx
) == -1 &&
2508 !isl_options_get_schedule_treat_coalescing(ctx
))
2511 for (i
= 0; i
< graph
->n
; ++i
)
2512 *n_ineq
+= graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
2517 /* Add constraints to graph->lp that bound the values of
2518 * the parameter schedule coefficients of "node" to "max" and
2519 * the variable schedule coefficients to the corresponding entry
2521 * In either case, a negative value means that no bound needs to be imposed.
2523 * For parameter coefficients, this amounts to adding a constraint
2531 * The variables coefficients are, however, not represented directly.
2532 * Instead, the variable coefficients c_x are written as differences
2533 * c_x = c_x^+ - c_x^-.
2536 * -max_i <= c_x_i <= max_i
2540 * -max_i <= c_x_i^+ - c_x_i^- <= max_i
2544 * -(c_x_i^+ - c_x_i^-) + max_i >= 0
2545 * c_x_i^+ - c_x_i^- + max_i >= 0
2547 static isl_stat
node_add_coefficient_constraints(isl_ctx
*ctx
,
2548 struct isl_sched_graph
*graph
, struct isl_sched_node
*node
, int max
)
2554 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2556 return isl_stat_error
;
2558 for (j
= 0; j
< node
->nparam
; ++j
) {
2564 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2566 return isl_stat_error
;
2567 dim
= 1 + node_par_coef_offset(node
) + j
;
2568 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2569 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
2570 isl_int_set_si(graph
->lp
->ineq
[k
][0], max
);
2573 ineq
= isl_vec_alloc(ctx
, 1 + total
);
2574 ineq
= isl_vec_clr(ineq
);
2576 return isl_stat_error
;
2577 for (i
= 0; i
< node
->nvar
; ++i
) {
2578 int pos
= 1 + node_var_coef_pos(node
, i
);
2580 if (isl_int_is_neg(node
->max
->el
[i
]))
2583 isl_int_set_si(ineq
->el
[pos
], 1);
2584 isl_int_set_si(ineq
->el
[pos
+ 1], -1);
2585 isl_int_set(ineq
->el
[0], node
->max
->el
[i
]);
2587 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2590 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2592 isl_seq_neg(ineq
->el
+ pos
, ineq
->el
+ pos
, 2);
2593 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2596 isl_seq_cpy(graph
->lp
->ineq
[k
], ineq
->el
, 1 + total
);
2598 isl_seq_clr(ineq
->el
+ pos
, 2);
2605 return isl_stat_error
;
2608 /* Add constraints that bound the values of the variable and parameter
2609 * coefficients of the schedule.
2611 * The maximal value of the coefficients is defined by the option
2612 * 'schedule_max_coefficient' and the entries in node->max.
2613 * These latter entries are only set if either the schedule_max_coefficient
2614 * option or the schedule_treat_coalescing option is set.
2616 static isl_stat
add_bound_coefficient_constraints(isl_ctx
*ctx
,
2617 struct isl_sched_graph
*graph
)
2622 max
= isl_options_get_schedule_max_coefficient(ctx
);
2624 if (max
== -1 && !isl_options_get_schedule_treat_coalescing(ctx
))
2627 for (i
= 0; i
< graph
->n
; ++i
) {
2628 struct isl_sched_node
*node
= &graph
->node
[i
];
2630 if (node_add_coefficient_constraints(ctx
, graph
, node
, max
) < 0)
2631 return isl_stat_error
;
2637 /* Add a constraint to graph->lp that equates the value at position
2638 * "sum_pos" to the sum of the "n" values starting at "first".
2640 static isl_stat
add_sum_constraint(struct isl_sched_graph
*graph
,
2641 int sum_pos
, int first
, int n
)
2646 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2648 return isl_stat_error
;
2650 k
= isl_basic_set_alloc_equality(graph
->lp
);
2652 return isl_stat_error
;
2653 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2654 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2655 for (i
= 0; i
< n
; ++i
)
2656 isl_int_set_si(graph
->lp
->eq
[k
][1 + first
+ i
], 1);
2661 /* Add a constraint to graph->lp that equates the value at position
2662 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2664 static isl_stat
add_param_sum_constraint(struct isl_sched_graph
*graph
,
2670 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2672 return isl_stat_error
;
2674 k
= isl_basic_set_alloc_equality(graph
->lp
);
2676 return isl_stat_error
;
2677 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2678 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2679 for (i
= 0; i
< graph
->n
; ++i
) {
2680 int pos
= 1 + node_par_coef_offset(&graph
->node
[i
]);
2682 for (j
= 0; j
< graph
->node
[i
].nparam
; ++j
)
2683 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2689 /* Add a constraint to graph->lp that equates the value at position
2690 * "sum_pos" to the sum of the variable coefficients of all nodes.
2692 static isl_stat
add_var_sum_constraint(struct isl_sched_graph
*graph
,
2698 total
= isl_basic_set_dim(graph
->lp
, isl_dim_set
);
2700 return isl_stat_error
;
2702 k
= isl_basic_set_alloc_equality(graph
->lp
);
2704 return isl_stat_error
;
2705 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2706 isl_int_set_si(graph
->lp
->eq
[k
][1 + sum_pos
], -1);
2707 for (i
= 0; i
< graph
->n
; ++i
) {
2708 struct isl_sched_node
*node
= &graph
->node
[i
];
2709 int pos
= 1 + node_var_coef_offset(node
);
2711 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2712 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2718 /* Construct an ILP problem for finding schedule coefficients
2719 * that result in non-negative, but small dependence distances
2720 * over all dependences.
2721 * In particular, the dependence distances over proximity edges
2722 * are bounded by m_0 + m_n n and we compute schedule coefficients
2723 * with small values (preferably zero) of m_n and m_0.
2725 * All variables of the ILP are non-negative. The actual coefficients
2726 * may be negative, so each coefficient is represented as the difference
2727 * of two non-negative variables. The negative part always appears
2728 * immediately before the positive part.
2729 * Other than that, the variables have the following order
2731 * - sum of positive and negative parts of m_n coefficients
2733 * - sum of all c_n coefficients
2734 * (unconstrained when computing non-parametric schedules)
2735 * - sum of positive and negative parts of all c_x coefficients
2736 * - positive and negative parts of m_n coefficients
2738 * - positive and negative parts of c_i_x, in opposite order
2739 * - c_i_n (if parametric)
2742 * The constraints are those from the edges plus two or three equalities
2743 * to express the sums.
2745 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2746 * Otherwise, we ignore them.
2748 static isl_stat
setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
2749 int use_coincidence
)
2759 parametric
= ctx
->opt
->schedule_parametric
;
2760 nparam
= isl_space_dim(graph
->node
[0].space
, isl_dim_param
);
2762 return isl_stat_error
;
2764 total
= param_pos
+ 2 * nparam
;
2765 for (i
= 0; i
< graph
->n
; ++i
) {
2766 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2767 if (isl_sched_node_update_vmap(node
) < 0)
2768 return isl_stat_error
;
2769 node
->start
= total
;
2770 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
2773 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
2774 return isl_stat_error
;
2775 if (count_bound_constant_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2776 return isl_stat_error
;
2777 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2778 return isl_stat_error
;
2780 space
= isl_space_set_alloc(ctx
, 0, total
);
2781 isl_basic_set_free(graph
->lp
);
2782 n_eq
+= 2 + parametric
;
2784 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
2786 if (add_sum_constraint(graph
, 0, param_pos
, 2 * nparam
) < 0)
2787 return isl_stat_error
;
2788 if (parametric
&& add_param_sum_constraint(graph
, 2) < 0)
2789 return isl_stat_error
;
2790 if (add_var_sum_constraint(graph
, 3) < 0)
2791 return isl_stat_error
;
2792 if (add_bound_constant_constraints(ctx
, graph
) < 0)
2793 return isl_stat_error
;
2794 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2795 return isl_stat_error
;
2796 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
2797 return isl_stat_error
;
2798 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
2799 return isl_stat_error
;
2804 /* Analyze the conflicting constraint found by
2805 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2806 * constraint of one of the edges between distinct nodes, living, moreover
2807 * in distinct SCCs, then record the source and sink SCC as this may
2808 * be a good place to cut between SCCs.
2810 static int check_conflict(int con
, void *user
)
2813 struct isl_sched_graph
*graph
= user
;
2815 if (graph
->src_scc
>= 0)
2818 con
-= graph
->lp
->n_eq
;
2820 if (con
>= graph
->lp
->n_ineq
)
2823 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2824 if (!is_validity(&graph
->edge
[i
]))
2826 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
2828 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
2830 if (graph
->edge
[i
].start
> con
)
2832 if (graph
->edge
[i
].end
<= con
)
2834 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
2835 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
2841 /* Check whether the next schedule row of the given node needs to be
2842 * non-trivial. Lower-dimensional domains may have some trivial rows,
2843 * but as soon as the number of remaining required non-trivial rows
2844 * is as large as the number or remaining rows to be computed,
2845 * all remaining rows need to be non-trivial.
2847 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
2849 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
2852 /* Construct a non-triviality region with triviality directions
2853 * corresponding to the rows of "indep".
2854 * The rows of "indep" are expressed in terms of the schedule coefficients c_i,
2855 * while the triviality directions are expressed in terms of
2856 * pairs of non-negative variables c^+_i - c^-_i, with c^-_i appearing
2857 * before c^+_i. Furthermore,
2858 * the pairs of non-negative variables representing the coefficients
2859 * are stored in the opposite order.
2861 static __isl_give isl_mat
*construct_trivial(__isl_keep isl_mat
*indep
)
2868 n
= isl_mat_rows(indep
);
2869 n_var
= isl_mat_cols(indep
);
2870 if (n
< 0 || n_var
< 0)
2873 ctx
= isl_mat_get_ctx(indep
);
2874 mat
= isl_mat_alloc(ctx
, n
, 2 * n_var
);
2877 for (i
= 0; i
< n
; ++i
) {
2878 for (j
= 0; j
< n_var
; ++j
) {
2879 int nj
= n_var
- 1 - j
;
2880 isl_int_neg(mat
->row
[i
][2 * nj
], indep
->row
[i
][j
]);
2881 isl_int_set(mat
->row
[i
][2 * nj
+ 1], indep
->row
[i
][j
]);
2888 /* Solve the ILP problem constructed in setup_lp.
2889 * For each node such that all the remaining rows of its schedule
2890 * need to be non-trivial, we construct a non-triviality region.
2891 * This region imposes that the next row is independent of previous rows.
2892 * In particular, the non-triviality region enforces that at least
2893 * one of the linear combinations in the rows of node->indep is non-zero.
2895 static __isl_give isl_vec
*solve_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2901 for (i
= 0; i
< graph
->n
; ++i
) {
2902 struct isl_sched_node
*node
= &graph
->node
[i
];
2905 graph
->region
[i
].pos
= node_var_coef_offset(node
);
2906 if (needs_row(graph
, node
))
2907 trivial
= construct_trivial(node
->indep
);
2909 trivial
= isl_mat_zero(ctx
, 0, 0);
2910 graph
->region
[i
].trivial
= trivial
;
2912 lp
= isl_basic_set_copy(graph
->lp
);
2913 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
2914 graph
->region
, &check_conflict
, graph
);
2915 for (i
= 0; i
< graph
->n
; ++i
)
2916 isl_mat_free(graph
->region
[i
].trivial
);
2920 /* Extract the coefficients for the variables of "node" from "sol".
2922 * Each schedule coefficient c_i_x is represented as the difference
2923 * between two non-negative variables c_i_x^+ - c_i_x^-.
2924 * The c_i_x^- appear before their c_i_x^+ counterpart.
2925 * Furthermore, the order of these pairs is the opposite of that
2926 * of the corresponding coefficients.
2928 * Return c_i_x = c_i_x^+ - c_i_x^-
2930 static __isl_give isl_vec
*extract_var_coef(struct isl_sched_node
*node
,
2931 __isl_keep isl_vec
*sol
)
2939 csol
= isl_vec_alloc(isl_vec_get_ctx(sol
), node
->nvar
);
2943 pos
= 1 + node_var_coef_offset(node
);
2944 for (i
= 0; i
< node
->nvar
; ++i
)
2945 isl_int_sub(csol
->el
[node
->nvar
- 1 - i
],
2946 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
2951 /* Update the schedules of all nodes based on the given solution
2952 * of the LP problem.
2953 * The new row is added to the current band.
2954 * All possibly negative coefficients are encoded as a difference
2955 * of two non-negative variables, so we need to perform the subtraction
2958 * If coincident is set, then the caller guarantees that the new
2959 * row satisfies the coincidence constraints.
2961 static int update_schedule(struct isl_sched_graph
*graph
,
2962 __isl_take isl_vec
*sol
, int coincident
)
2965 isl_vec
*csol
= NULL
;
2970 isl_die(sol
->ctx
, isl_error_internal
,
2971 "no solution found", goto error
);
2972 if (graph
->n_total_row
>= graph
->max_row
)
2973 isl_die(sol
->ctx
, isl_error_internal
,
2974 "too many schedule rows", goto error
);
2976 for (i
= 0; i
< graph
->n
; ++i
) {
2977 struct isl_sched_node
*node
= &graph
->node
[i
];
2979 isl_size row
= isl_mat_rows(node
->sched
);
2982 csol
= extract_var_coef(node
, sol
);
2983 if (row
< 0 || !csol
)
2986 isl_map_free(node
->sched_map
);
2987 node
->sched_map
= NULL
;
2988 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2991 pos
= node_cst_coef_offset(node
);
2992 node
->sched
= isl_mat_set_element(node
->sched
,
2993 row
, 0, sol
->el
[1 + pos
]);
2994 pos
= node_par_coef_offset(node
);
2995 for (j
= 0; j
< node
->nparam
; ++j
)
2996 node
->sched
= isl_mat_set_element(node
->sched
,
2997 row
, 1 + j
, sol
->el
[1 + pos
+ j
]);
2998 for (j
= 0; j
< node
->nvar
; ++j
)
2999 node
->sched
= isl_mat_set_element(node
->sched
,
3000 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
3001 node
->coincident
[graph
->n_total_row
] = coincident
;
3007 graph
->n_total_row
++;
3016 /* Convert row "row" of node->sched into an isl_aff living in "ls"
3017 * and return this isl_aff.
3019 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
3020 struct isl_sched_node
*node
, int row
)
3028 aff
= isl_aff_zero_on_domain(ls
);
3029 if (isl_mat_get_element(node
->sched
, row
, 0, &v
) < 0)
3031 aff
= isl_aff_set_constant(aff
, v
);
3032 for (j
= 0; j
< node
->nparam
; ++j
) {
3033 if (isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
) < 0)
3035 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
3037 for (j
= 0; j
< node
->nvar
; ++j
) {
3038 if (isl_mat_get_element(node
->sched
, row
,
3039 1 + node
->nparam
+ j
, &v
) < 0)
3041 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
3053 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
3054 * and return this multi_aff.
3056 * The result is defined over the uncompressed node domain.
3058 __isl_give isl_multi_aff
*isl_sched_node_extract_partial_schedule_multi_aff(
3059 struct isl_sched_node
*node
, int first
, int n
)
3063 isl_local_space
*ls
;
3070 nrow
= isl_mat_rows(node
->sched
);
3073 if (node
->compressed
)
3074 space
= isl_pw_multi_aff_get_domain_space(node
->decompress
);
3076 space
= isl_space_copy(node
->space
);
3077 ls
= isl_local_space_from_space(isl_space_copy(space
));
3078 space
= isl_space_from_domain(space
);
3079 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
3080 ma
= isl_multi_aff_zero(space
);
3082 for (i
= first
; i
< first
+ n
; ++i
) {
3083 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
3084 ma
= isl_multi_aff_set_aff(ma
, i
- first
, aff
);
3087 isl_local_space_free(ls
);
3089 if (node
->compressed
)
3090 ma
= isl_multi_aff_pullback_multi_aff(ma
,
3091 isl_multi_aff_copy(node
->compress
));
3096 /* Convert node->sched into a multi_aff and return this multi_aff.
3098 * The result is defined over the uncompressed node domain.
3100 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
3101 struct isl_sched_node
*node
)
3105 nrow
= isl_mat_rows(node
->sched
);
3108 return isl_sched_node_extract_partial_schedule_multi_aff(node
, 0, nrow
);
3111 /* Convert node->sched into a map and return this map.
3113 * The result is cached in node->sched_map, which needs to be released
3114 * whenever node->sched is updated.
3115 * It is defined over the uncompressed node domain.
3117 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
3119 if (!node
->sched_map
) {
3122 ma
= node_extract_schedule_multi_aff(node
);
3123 node
->sched_map
= isl_map_from_multi_aff(ma
);
3126 return isl_map_copy(node
->sched_map
);
3129 /* Construct a map that can be used to update a dependence relation
3130 * based on the current schedule.
3131 * That is, construct a map expressing that source and sink
3132 * are executed within the same iteration of the current schedule.
3133 * This map can then be intersected with the dependence relation.
3134 * This is not the most efficient way, but this shouldn't be a critical
3137 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
3138 struct isl_sched_node
*dst
)
3140 isl_map
*src_sched
, *dst_sched
;
3142 src_sched
= node_extract_schedule(src
);
3143 dst_sched
= node_extract_schedule(dst
);
3144 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
3147 /* Intersect the domains of the nested relations in domain and range
3148 * of "umap" with "map".
3150 static __isl_give isl_union_map
*intersect_domains(
3151 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
3153 isl_union_set
*uset
;
3155 umap
= isl_union_map_zip(umap
);
3156 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
3157 umap
= isl_union_map_intersect_domain(umap
, uset
);
3158 umap
= isl_union_map_zip(umap
);
3162 /* Update the dependence relation of the given edge based
3163 * on the current schedule.
3164 * If the dependence is carried completely by the current schedule, then
3165 * it is removed from the edge_tables. It is kept in the list of edges
3166 * as otherwise all edge_tables would have to be recomputed.
3168 * If the edge is of a type that can appear multiple times
3169 * between the same pair of nodes, then it is added to
3170 * the edge table (again). This prevents the situation
3171 * where none of these edges is referenced from the edge table
3172 * because the one that was referenced turned out to be empty and
3173 * was therefore removed from the table.
3175 static isl_stat
update_edge(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
3176 struct isl_sched_edge
*edge
)
3181 id
= specializer(edge
->src
, edge
->dst
);
3182 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
3186 if (edge
->tagged_condition
) {
3187 edge
->tagged_condition
=
3188 intersect_domains(edge
->tagged_condition
, id
);
3189 if (!edge
->tagged_condition
)
3192 if (edge
->tagged_validity
) {
3193 edge
->tagged_validity
=
3194 intersect_domains(edge
->tagged_validity
, id
);
3195 if (!edge
->tagged_validity
)
3199 empty
= isl_map_plain_is_empty(edge
->map
);
3203 if (graph_remove_edge(graph
, edge
) < 0)
3205 } else if (is_multi_edge_type(edge
)) {
3206 if (graph_edge_tables_add(ctx
, graph
, edge
) < 0)
3214 return isl_stat_error
;
3217 /* Does the domain of "umap" intersect "uset"?
3219 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3220 __isl_keep isl_union_set
*uset
)
3224 umap
= isl_union_map_copy(umap
);
3225 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3226 empty
= isl_union_map_is_empty(umap
);
3227 isl_union_map_free(umap
);
3229 return empty
< 0 ? -1 : !empty
;
3232 /* Does the range of "umap" intersect "uset"?
3234 static int range_intersects(__isl_keep isl_union_map
*umap
,
3235 __isl_keep isl_union_set
*uset
)
3239 umap
= isl_union_map_copy(umap
);
3240 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3241 empty
= isl_union_map_is_empty(umap
);
3242 isl_union_map_free(umap
);
3244 return empty
< 0 ? -1 : !empty
;
3247 /* Are the condition dependences of "edge" local with respect to
3248 * the current schedule?
3250 * That is, are domain and range of the condition dependences mapped
3251 * to the same point?
3253 * In other words, is the condition false?
3255 static int is_condition_false(struct isl_sched_edge
*edge
)
3257 isl_union_map
*umap
;
3258 isl_map
*map
, *sched
, *test
;
3261 empty
= isl_union_map_is_empty(edge
->tagged_condition
);
3262 if (empty
< 0 || empty
)
3265 umap
= isl_union_map_copy(edge
->tagged_condition
);
3266 umap
= isl_union_map_zip(umap
);
3267 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3268 map
= isl_map_from_union_map(umap
);
3270 sched
= node_extract_schedule(edge
->src
);
3271 map
= isl_map_apply_domain(map
, sched
);
3272 sched
= node_extract_schedule(edge
->dst
);
3273 map
= isl_map_apply_range(map
, sched
);
3275 test
= isl_map_identity(isl_map_get_space(map
));
3276 local
= isl_map_is_subset(map
, test
);
3283 /* For each conditional validity constraint that is adjacent
3284 * to a condition with domain in condition_source or range in condition_sink,
3285 * turn it into an unconditional validity constraint.
3287 static int unconditionalize_adjacent_validity(struct isl_sched_graph
*graph
,
3288 __isl_take isl_union_set
*condition_source
,
3289 __isl_take isl_union_set
*condition_sink
)
3293 condition_source
= isl_union_set_coalesce(condition_source
);
3294 condition_sink
= isl_union_set_coalesce(condition_sink
);
3296 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3298 isl_union_map
*validity
;
3300 if (!isl_sched_edge_is_conditional_validity(&graph
->edge
[i
]))
3302 if (is_validity(&graph
->edge
[i
]))
3305 validity
= graph
->edge
[i
].tagged_validity
;
3306 adjacent
= domain_intersects(validity
, condition_sink
);
3307 if (adjacent
>= 0 && !adjacent
)
3308 adjacent
= range_intersects(validity
, condition_source
);
3314 set_validity(&graph
->edge
[i
]);
3317 isl_union_set_free(condition_source
);
3318 isl_union_set_free(condition_sink
);
3321 isl_union_set_free(condition_source
);
3322 isl_union_set_free(condition_sink
);
3326 /* Update the dependence relations of all edges based on the current schedule
3327 * and enforce conditional validity constraints that are adjacent
3328 * to satisfied condition constraints.
3330 * First check if any of the condition constraints are satisfied
3331 * (i.e., not local to the outer schedule) and keep track of
3332 * their domain and range.
3333 * Then update all dependence relations (which removes the non-local
3335 * Finally, if any condition constraints turned out to be satisfied,
3336 * then turn all adjacent conditional validity constraints into
3337 * unconditional validity constraints.
3339 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3343 isl_union_set
*source
, *sink
;
3345 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3346 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3347 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3349 isl_union_set
*uset
;
3350 isl_union_map
*umap
;
3352 if (!isl_sched_edge_is_condition(&graph
->edge
[i
]))
3354 if (is_local(&graph
->edge
[i
]))
3356 local
= is_condition_false(&graph
->edge
[i
]);
3364 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3365 uset
= isl_union_map_domain(umap
);
3366 source
= isl_union_set_union(source
, uset
);
3368 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_condition
);
3369 uset
= isl_union_map_range(umap
);
3370 sink
= isl_union_set_union(sink
, uset
);
3373 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3374 if (update_edge(ctx
, graph
, &graph
->edge
[i
]) < 0)
3379 return unconditionalize_adjacent_validity(graph
, source
, sink
);
3381 isl_union_set_free(source
);
3382 isl_union_set_free(sink
);
3385 isl_union_set_free(source
);
3386 isl_union_set_free(sink
);
3390 static void next_band(struct isl_sched_graph
*graph
)
3392 graph
->band_start
= graph
->n_total_row
;
3395 /* Return the union of the universe domains of the nodes in "graph"
3396 * that satisfy "pred".
3398 static __isl_give isl_union_set
*isl_sched_graph_domain(isl_ctx
*ctx
,
3399 struct isl_sched_graph
*graph
,
3400 int (*pred
)(struct isl_sched_node
*node
, int data
), int data
)
3406 for (i
= 0; i
< graph
->n
; ++i
)
3407 if (pred(&graph
->node
[i
], data
))
3411 isl_die(ctx
, isl_error_internal
,
3412 "empty component", return NULL
);
3414 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3415 dom
= isl_union_set_from_set(set
);
3417 for (i
= i
+ 1; i
< graph
->n
; ++i
) {
3418 if (!pred(&graph
->node
[i
], data
))
3420 set
= isl_set_universe(isl_space_copy(graph
->node
[i
].space
));
3421 dom
= isl_union_set_union(dom
, isl_union_set_from_set(set
));
3427 /* Return a list of unions of universe domains, where each element
3428 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3430 __isl_give isl_union_set_list
*isl_sched_graph_extract_sccs(isl_ctx
*ctx
,
3431 struct isl_sched_graph
*graph
)
3434 isl_union_set_list
*filters
;
3436 filters
= isl_union_set_list_alloc(ctx
, graph
->scc
);
3437 for (i
= 0; i
< graph
->scc
; ++i
) {
3440 dom
= isl_sched_graph_domain(ctx
, graph
,
3441 &isl_sched_node_scc_exactly
, i
);
3442 filters
= isl_union_set_list_add(filters
, dom
);
3448 /* Return a list of two unions of universe domains, one for the SCCs up
3449 * to and including graph->src_scc and another for the other SCCs.
3451 static __isl_give isl_union_set_list
*extract_split(isl_ctx
*ctx
,
3452 struct isl_sched_graph
*graph
)
3455 isl_union_set_list
*filters
;
3457 filters
= isl_union_set_list_alloc(ctx
, 2);
3458 dom
= isl_sched_graph_domain(ctx
, graph
,
3459 &node_scc_at_most
, graph
->src_scc
);
3460 filters
= isl_union_set_list_add(filters
, dom
);
3461 dom
= isl_sched_graph_domain(ctx
, graph
,
3462 &node_scc_at_least
, graph
->src_scc
+ 1);
3463 filters
= isl_union_set_list_add(filters
, dom
);
3468 /* Copy nodes that satisfy node_pred from the src dependence graph
3469 * to the dst dependence graph.
3471 static isl_stat
copy_nodes(struct isl_sched_graph
*dst
,
3472 struct isl_sched_graph
*src
,
3473 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
3478 for (i
= 0; i
< src
->n
; ++i
) {
3481 if (!node_pred(&src
->node
[i
], data
))
3485 dst
->node
[j
].space
= isl_space_copy(src
->node
[i
].space
);
3486 dst
->node
[j
].compressed
= src
->node
[i
].compressed
;
3487 dst
->node
[j
].hull
= isl_set_copy(src
->node
[i
].hull
);
3488 dst
->node
[j
].compress
=
3489 isl_multi_aff_copy(src
->node
[i
].compress
);
3490 dst
->node
[j
].decompress
=
3491 isl_pw_multi_aff_copy(src
->node
[i
].decompress
);
3492 dst
->node
[j
].nvar
= src
->node
[i
].nvar
;
3493 dst
->node
[j
].nparam
= src
->node
[i
].nparam
;
3494 dst
->node
[j
].sched
= isl_mat_copy(src
->node
[i
].sched
);
3495 dst
->node
[j
].sched_map
= isl_map_copy(src
->node
[i
].sched_map
);
3496 dst
->node
[j
].coincident
= src
->node
[i
].coincident
;
3497 dst
->node
[j
].sizes
= isl_multi_val_copy(src
->node
[i
].sizes
);
3498 dst
->node
[j
].bounds
= isl_basic_set_copy(src
->node
[i
].bounds
);
3499 dst
->node
[j
].max
= isl_vec_copy(src
->node
[i
].max
);
3502 if (!dst
->node
[j
].space
|| !dst
->node
[j
].sched
)
3503 return isl_stat_error
;
3504 if (dst
->node
[j
].compressed
&&
3505 (!dst
->node
[j
].hull
|| !dst
->node
[j
].compress
||
3506 !dst
->node
[j
].decompress
))
3507 return isl_stat_error
;
3513 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3514 * to the dst dependence graph.
3515 * If the source or destination node of the edge is not in the destination
3516 * graph, then it must be a backward proximity edge and it should simply
3519 static isl_stat
copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
3520 struct isl_sched_graph
*src
,
3521 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
3526 for (i
= 0; i
< src
->n_edge
; ++i
) {
3527 struct isl_sched_edge
*edge
= &src
->edge
[i
];
3529 isl_union_map
*tagged_condition
;
3530 isl_union_map
*tagged_validity
;
3531 struct isl_sched_node
*dst_src
, *dst_dst
;
3533 if (!edge_pred(edge
, data
))
3536 if (isl_map_plain_is_empty(edge
->map
))
3539 dst_src
= isl_sched_graph_find_node(ctx
, dst
, edge
->src
->space
);
3540 dst_dst
= isl_sched_graph_find_node(ctx
, dst
, edge
->dst
->space
);
3541 if (!dst_src
|| !dst_dst
)
3542 return isl_stat_error
;
3543 if (!isl_sched_graph_is_node(dst
, dst_src
) ||
3544 !isl_sched_graph_is_node(dst
, dst_dst
)) {
3545 if (is_validity(edge
) ||
3546 isl_sched_edge_is_conditional_validity(edge
))
3547 isl_die(ctx
, isl_error_internal
,
3548 "backward (conditional) validity edge",
3549 return isl_stat_error
);
3553 map
= isl_map_copy(edge
->map
);
3554 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
3555 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
3557 dst
->edge
[dst
->n_edge
].src
= dst_src
;
3558 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
3559 dst
->edge
[dst
->n_edge
].map
= map
;
3560 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
3561 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
3562 dst
->edge
[dst
->n_edge
].types
= edge
->types
;
3565 if (edge
->tagged_condition
&& !tagged_condition
)
3566 return isl_stat_error
;
3567 if (edge
->tagged_validity
&& !tagged_validity
)
3568 return isl_stat_error
;
3570 if (graph_edge_tables_add(ctx
, dst
,
3571 &dst
->edge
[dst
->n_edge
- 1]) < 0)
3572 return isl_stat_error
;
3578 /* Compute the maximal number of variables over all nodes.
3579 * This is the maximal number of linearly independent schedule
3580 * rows that we need to compute.
3581 * Just in case we end up in a part of the dependence graph
3582 * with only lower-dimensional domains, we make sure we will
3583 * compute the required amount of extra linearly independent rows.
3585 isl_stat
isl_sched_graph_compute_maxvar(struct isl_sched_graph
*graph
)
3590 for (i
= 0; i
< graph
->n
; ++i
) {
3591 struct isl_sched_node
*node
= &graph
->node
[i
];
3594 if (isl_sched_node_update_vmap(node
) < 0)
3595 return isl_stat_error
;
3596 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
3597 if (nvar
> graph
->maxvar
)
3598 graph
->maxvar
= nvar
;
3604 /* Extract the subgraph of "graph" that consists of the nodes satisfying
3605 * "node_pred" and the edges satisfying "edge_pred" and store
3606 * the result in "sub".
3608 isl_stat
isl_sched_graph_extract_sub_graph(isl_ctx
*ctx
,
3609 struct isl_sched_graph
*graph
,
3610 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3611 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3612 int data
, struct isl_sched_graph
*sub
)
3614 int i
, n
= 0, n_edge
= 0;
3617 for (i
= 0; i
< graph
->n
; ++i
)
3618 if (node_pred(&graph
->node
[i
], data
))
3620 for (i
= 0; i
< graph
->n_edge
; ++i
)
3621 if (edge_pred(&graph
->edge
[i
], data
))
3623 if (graph_alloc(ctx
, sub
, n
, n_edge
) < 0)
3624 return isl_stat_error
;
3625 sub
->root
= graph
->root
;
3626 if (copy_nodes(sub
, graph
, node_pred
, data
) < 0)
3627 return isl_stat_error
;
3628 if (graph_init_table(ctx
, sub
) < 0)
3629 return isl_stat_error
;
3630 for (t
= 0; t
<= isl_edge_last
; ++t
)
3631 sub
->max_edge
[t
] = graph
->max_edge
[t
];
3632 if (graph_init_edge_tables(ctx
, sub
) < 0)
3633 return isl_stat_error
;
3634 if (copy_edges(ctx
, sub
, graph
, edge_pred
, data
) < 0)
3635 return isl_stat_error
;
3636 sub
->n_row
= graph
->n_row
;
3637 sub
->max_row
= graph
->max_row
;
3638 sub
->n_total_row
= graph
->n_total_row
;
3639 sub
->band_start
= graph
->band_start
;
3644 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
3645 struct isl_sched_graph
*graph
);
3646 static __isl_give isl_schedule_node
*compute_schedule_wcc(
3647 isl_schedule_node
*node
, struct isl_sched_graph
*graph
);
3649 /* Compute a schedule for a subgraph of "graph". In particular, for
3650 * the graph composed of nodes that satisfy node_pred and edges that
3651 * that satisfy edge_pred.
3652 * If the subgraph is known to consist of a single component, then wcc should
3653 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3654 * Otherwise, we call compute_schedule, which will check whether the subgraph
3657 * The schedule is inserted at "node" and the updated schedule node
3660 static __isl_give isl_schedule_node
*compute_sub_schedule(
3661 __isl_take isl_schedule_node
*node
, isl_ctx
*ctx
,
3662 struct isl_sched_graph
*graph
,
3663 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
3664 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
3667 struct isl_sched_graph split
= { 0 };
3669 if (isl_sched_graph_extract_sub_graph(ctx
, graph
, node_pred
, edge_pred
,
3674 node
= compute_schedule_wcc(node
, &split
);
3676 node
= compute_schedule(node
, &split
);
3678 isl_sched_graph_free(ctx
, &split
);
3681 isl_sched_graph_free(ctx
, &split
);
3682 return isl_schedule_node_free(node
);
3685 int isl_sched_edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
3687 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
3690 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
3692 return edge
->dst
->scc
<= scc
;
3695 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
3697 return edge
->src
->scc
>= scc
;
3700 /* Reset the current band by dropping all its schedule rows.
3702 static isl_stat
reset_band(struct isl_sched_graph
*graph
)
3707 drop
= graph
->n_total_row
- graph
->band_start
;
3708 graph
->n_total_row
-= drop
;
3709 graph
->n_row
-= drop
;
3711 for (i
= 0; i
< graph
->n
; ++i
) {
3712 struct isl_sched_node
*node
= &graph
->node
[i
];
3714 isl_map_free(node
->sched_map
);
3715 node
->sched_map
= NULL
;
3717 node
->sched
= isl_mat_drop_rows(node
->sched
,
3718 graph
->band_start
, drop
);
3721 return isl_stat_error
;
3727 /* Split the current graph into two parts and compute a schedule for each
3728 * part individually. In particular, one part consists of all SCCs up
3729 * to and including graph->src_scc, while the other part contains the other
3730 * SCCs. The split is enforced by a sequence node inserted at position "node"
3731 * in the schedule tree. Return the updated schedule node.
3732 * If either of these two parts consists of a sequence, then it is spliced
3733 * into the sequence containing the two parts.
3735 * The current band is reset. It would be possible to reuse
3736 * the previously computed rows as the first rows in the next
3737 * band, but recomputing them may result in better rows as we are looking
3738 * at a smaller part of the dependence graph.
3740 static __isl_give isl_schedule_node
*compute_split_schedule(
3741 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
3744 isl_union_set_list
*filters
;
3749 if (reset_band(graph
) < 0)
3750 return isl_schedule_node_free(node
);
3754 ctx
= isl_schedule_node_get_ctx(node
);
3755 filters
= extract_split(ctx
, graph
);
3756 node
= isl_schedule_node_insert_sequence(node
, filters
);
3757 node
= isl_schedule_node_grandchild(node
, 1, 0);
3759 node
= compute_sub_schedule(node
, ctx
, graph
,
3760 &node_scc_at_least
, &edge_src_scc_at_least
,
3761 graph
->src_scc
+ 1, 0);
3762 node
= isl_schedule_node_grandparent(node
);
3763 node
= isl_schedule_node_grandchild(node
, 0, 0);
3764 node
= compute_sub_schedule(node
, ctx
, graph
,
3765 &node_scc_at_most
, &edge_dst_scc_at_most
,
3767 node
= isl_schedule_node_grandparent(node
);
3769 node
= isl_schedule_node_sequence_splice_children(node
);
3774 /* Insert a band node at position "node" in the schedule tree corresponding
3775 * to the current band in "graph". Mark the band node permutable
3776 * if "permutable" is set.
3777 * The partial schedules and the coincidence property are extracted
3778 * from the graph nodes.
3779 * Return the updated schedule node.
3781 static __isl_give isl_schedule_node
*insert_current_band(
3782 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
3788 isl_multi_pw_aff
*mpa
;
3789 isl_multi_union_pw_aff
*mupa
;
3795 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
3796 "graph should have at least one node",
3797 return isl_schedule_node_free(node
));
3799 start
= graph
->band_start
;
3800 end
= graph
->n_total_row
;
3803 ma
= isl_sched_node_extract_partial_schedule_multi_aff(&graph
->node
[0],
3805 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3806 mupa
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3808 for (i
= 1; i
< graph
->n
; ++i
) {
3809 isl_multi_union_pw_aff
*mupa_i
;
3811 ma
= isl_sched_node_extract_partial_schedule_multi_aff(
3812 &graph
->node
[i
], start
, n
);
3813 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
3814 mupa_i
= isl_multi_union_pw_aff_from_multi_pw_aff(mpa
);
3815 mupa
= isl_multi_union_pw_aff_union_add(mupa
, mupa_i
);
3817 node
= isl_schedule_node_insert_partial_schedule(node
, mupa
);
3819 for (i
= 0; i
< n
; ++i
)
3820 node
= isl_schedule_node_band_member_set_coincident(node
, i
,
3821 graph
->node
[0].coincident
[start
+ i
]);
3822 node
= isl_schedule_node_band_set_permutable(node
, permutable
);
3827 /* Update the dependence relations based on the current schedule,
3828 * add the current band to "node" and then continue with the computation
3830 * Return the updated schedule node.
3832 static __isl_give isl_schedule_node
*compute_next_band(
3833 __isl_take isl_schedule_node
*node
,
3834 struct isl_sched_graph
*graph
, int permutable
)
3841 ctx
= isl_schedule_node_get_ctx(node
);
3842 if (update_edges(ctx
, graph
) < 0)
3843 return isl_schedule_node_free(node
);
3844 node
= insert_current_band(node
, graph
, permutable
);
3847 node
= isl_schedule_node_child(node
, 0);
3848 node
= compute_schedule(node
, graph
);
3849 node
= isl_schedule_node_parent(node
);
3854 /* Add the constraints "coef" derived from an edge from "node" to itself
3855 * to graph->lp in order to respect the dependences and to try and carry them.
3856 * "pos" is the sequence number of the edge that needs to be carried.
3857 * "coef" represents general constraints on coefficients (c_0, c_x)
3858 * of valid constraints for (y - x) with x and y instances of the node.
3860 * The constraints added to graph->lp need to enforce
3862 * (c_j_0 + c_j_x y) - (c_j_0 + c_j_x x)
3863 * = c_j_x (y - x) >= e_i
3865 * for each (x,y) in the dependence relation of the edge.
3866 * That is, (-e_i, c_j_x) needs to be plugged in for (c_0, c_x),
3867 * taking into account that each coefficient in c_j_x is represented
3868 * as a pair of non-negative coefficients.
3870 static isl_stat
add_intra_constraints(struct isl_sched_graph
*graph
,
3871 struct isl_sched_node
*node
, __isl_take isl_basic_set
*coef
, int pos
)
3875 isl_dim_map
*dim_map
;
3877 offset
= coef_var_offset(coef
);
3879 coef
= isl_basic_set_free(coef
);
3881 return isl_stat_error
;
3883 ctx
= isl_basic_set_get_ctx(coef
);
3884 dim_map
= intra_dim_map(ctx
, graph
, node
, offset
, 1);
3885 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3886 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
3891 /* Add the constraints "coef" derived from an edge from "src" to "dst"
3892 * to graph->lp in order to respect the dependences and to try and carry them.
3893 * "pos" is the sequence number of the edge that needs to be carried or
3894 * -1 if no attempt should be made to carry the dependences.
3895 * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y)
3896 * of valid constraints for (x, y) with x and y instances of "src" and "dst".
3898 * The constraints added to graph->lp need to enforce
3900 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3902 * for each (x,y) in the dependence relation of the edge or
3904 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= 0
3908 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3910 * (c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3911 * needs to be plugged in for (c_0, c_n, c_x, c_y),
3912 * taking into account that each coefficient in c_j_x and c_k_x is represented
3913 * as a pair of non-negative coefficients.
3915 static isl_stat
add_inter_constraints(struct isl_sched_graph
*graph
,
3916 struct isl_sched_node
*src
, struct isl_sched_node
*dst
,
3917 __isl_take isl_basic_set
*coef
, int pos
)
3921 isl_dim_map
*dim_map
;
3923 offset
= coef_var_offset(coef
);
3925 coef
= isl_basic_set_free(coef
);
3927 return isl_stat_error
;
3929 ctx
= isl_basic_set_get_ctx(coef
);
3930 dim_map
= inter_dim_map(ctx
, graph
, src
, dst
, offset
, 1);
3932 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
3933 graph
->lp
= add_constraints_dim_map(graph
->lp
, coef
, dim_map
);
3938 /* Data structure for keeping track of the data needed
3939 * to exploit non-trivial lineality spaces.
3941 * "any_non_trivial" is true if there are any non-trivial lineality spaces.
3942 * If "any_non_trivial" is not true, then "equivalent" and "mask" may be NULL.
3943 * "equivalent" connects instances to other instances on the same line(s).
3944 * "mask" contains the domain spaces of "equivalent".
3945 * Any instance set not in "mask" does not have a non-trivial lineality space.
3947 struct isl_exploit_lineality_data
{
3948 isl_bool any_non_trivial
;
3949 isl_union_map
*equivalent
;
3950 isl_union_set
*mask
;
3953 /* Data structure collecting information used during the construction
3954 * of an LP for carrying dependences.
3956 * "intra" is a sequence of coefficient constraints for intra-node edges.
3957 * "inter" is a sequence of coefficient constraints for inter-node edges.
3958 * "lineality" contains data used to exploit non-trivial lineality spaces.
3961 isl_basic_set_list
*intra
;
3962 isl_basic_set_list
*inter
;
3963 struct isl_exploit_lineality_data lineality
;
3966 /* Free all the data stored in "carry".
3968 static void isl_carry_clear(struct isl_carry
*carry
)
3970 isl_basic_set_list_free(carry
->intra
);
3971 isl_basic_set_list_free(carry
->inter
);
3972 isl_union_map_free(carry
->lineality
.equivalent
);
3973 isl_union_set_free(carry
->lineality
.mask
);
3976 /* Return a pointer to the node in "graph" that lives in "space".
3977 * If the requested node has been compressed, then "space"
3978 * corresponds to the compressed space.
3979 * The graph is assumed to have such a node.
3980 * Return NULL in case of error.
3982 * First try and see if "space" is the space of an uncompressed node.
3983 * If so, return that node.
3984 * Otherwise, "space" was constructed by construct_compressed_id and
3985 * contains a user pointer pointing to the node in the tuple id.
3986 * However, this node belongs to the original dependence graph.
3987 * If "graph" is a subgraph of this original dependence graph,
3988 * then the node with the same space still needs to be looked up
3989 * in the current graph.
3991 static struct isl_sched_node
*graph_find_compressed_node(isl_ctx
*ctx
,
3992 struct isl_sched_graph
*graph
, __isl_keep isl_space
*space
)
3995 struct isl_sched_node
*node
;
4000 node
= isl_sched_graph_find_node(ctx
, graph
, space
);
4003 if (isl_sched_graph_is_node(graph
, node
))
4006 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
4007 node
= isl_id_get_user(id
);
4013 if (!isl_sched_graph_is_node(graph
->root
, node
))
4014 isl_die(ctx
, isl_error_internal
,
4015 "space points to invalid node", return NULL
);
4016 if (graph
!= graph
->root
)
4017 node
= isl_sched_graph_find_node(ctx
, graph
, node
->space
);
4018 if (!isl_sched_graph_is_node(graph
, node
))
4019 isl_die(ctx
, isl_error_internal
,
4020 "unable to find node", return NULL
);
4025 /* Internal data structure for add_all_constraints.
4027 * "graph" is the schedule constraint graph for which an LP problem
4028 * is being constructed.
4029 * "carry_inter" indicates whether inter-node edges should be carried.
4030 * "pos" is the position of the next edge that needs to be carried.
4032 struct isl_add_all_constraints_data
{
4034 struct isl_sched_graph
*graph
;
4039 /* Add the constraints "coef" derived from an edge from a node to itself
4040 * to data->graph->lp in order to respect the dependences and
4041 * to try and carry them.
4043 * The space of "coef" is of the form
4045 * coefficients[[c_cst] -> S[c_x]]
4047 * with S[c_x] the (compressed) space of the node.
4048 * Extract the node from the space and call add_intra_constraints.
4050 static isl_stat
lp_add_intra(__isl_take isl_basic_set
*coef
, void *user
)
4052 struct isl_add_all_constraints_data
*data
= user
;
4054 struct isl_sched_node
*node
;
4056 space
= isl_basic_set_get_space(coef
);
4057 space
= isl_space_range(isl_space_unwrap(space
));
4058 node
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
4059 isl_space_free(space
);
4060 return add_intra_constraints(data
->graph
, node
, coef
, data
->pos
++);
4063 /* Add the constraints "coef" derived from an edge from a node j
4064 * to a node k to data->graph->lp in order to respect the dependences and
4065 * to try and carry them (provided data->carry_inter is set).
4067 * The space of "coef" is of the form
4069 * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]]
4071 * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes.
4072 * Extract the nodes from the space and call add_inter_constraints.
4074 static isl_stat
lp_add_inter(__isl_take isl_basic_set
*coef
, void *user
)
4076 struct isl_add_all_constraints_data
*data
= user
;
4077 isl_space
*space
, *dom
;
4078 struct isl_sched_node
*src
, *dst
;
4081 space
= isl_basic_set_get_space(coef
);
4082 space
= isl_space_unwrap(isl_space_range(isl_space_unwrap(space
)));
4083 dom
= isl_space_domain(isl_space_copy(space
));
4084 src
= graph_find_compressed_node(data
->ctx
, data
->graph
, dom
);
4085 isl_space_free(dom
);
4086 space
= isl_space_range(space
);
4087 dst
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
4088 isl_space_free(space
);
4090 pos
= data
->carry_inter
? data
->pos
++ : -1;
4091 return add_inter_constraints(data
->graph
, src
, dst
, coef
, pos
);
4094 /* Add constraints to graph->lp that force all (conditional) validity
4095 * dependences to be respected and attempt to carry them.
4096 * "intra" is the sequence of coefficient constraints for intra-node edges.
4097 * "inter" is the sequence of coefficient constraints for inter-node edges.
4098 * "carry_inter" indicates whether inter-node edges should be carried or
4101 static isl_stat
add_all_constraints(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
4102 __isl_keep isl_basic_set_list
*intra
,
4103 __isl_keep isl_basic_set_list
*inter
, int carry_inter
)
4105 struct isl_add_all_constraints_data data
= { ctx
, graph
, carry_inter
};
4108 if (isl_basic_set_list_foreach(intra
, &lp_add_intra
, &data
) < 0)
4109 return isl_stat_error
;
4110 if (isl_basic_set_list_foreach(inter
, &lp_add_inter
, &data
) < 0)
4111 return isl_stat_error
;
4115 /* Internal data structure for count_all_constraints
4116 * for keeping track of the number of equality and inequality constraints.
4118 struct isl_sched_count
{
4123 /* Add the number of equality and inequality constraints of "bset"
4124 * to data->n_eq and data->n_ineq.
4126 static isl_stat
bset_update_count(__isl_take isl_basic_set
*bset
, void *user
)
4128 struct isl_sched_count
*data
= user
;
4130 return update_count(bset
, 1, &data
->n_eq
, &data
->n_ineq
);
4133 /* Count the number of equality and inequality constraints
4134 * that will be added to the carry_lp problem.
4135 * We count each edge exactly once.
4136 * "intra" is the sequence of coefficient constraints for intra-node edges.
4137 * "inter" is the sequence of coefficient constraints for inter-node edges.
4139 static isl_stat
count_all_constraints(__isl_keep isl_basic_set_list
*intra
,
4140 __isl_keep isl_basic_set_list
*inter
, int *n_eq
, int *n_ineq
)
4142 struct isl_sched_count data
;
4144 data
.n_eq
= data
.n_ineq
= 0;
4145 if (isl_basic_set_list_foreach(inter
, &bset_update_count
, &data
) < 0)
4146 return isl_stat_error
;
4147 if (isl_basic_set_list_foreach(intra
, &bset_update_count
, &data
) < 0)
4148 return isl_stat_error
;
4151 *n_ineq
= data
.n_ineq
;
4156 /* Construct an LP problem for finding schedule coefficients
4157 * such that the schedule carries as many validity dependences as possible.
4158 * In particular, for each dependence i, we bound the dependence distance
4159 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
4160 * of all e_i's. Dependences with e_i = 0 in the solution are simply
4161 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
4162 * "intra" is the sequence of coefficient constraints for intra-node edges.
4163 * "inter" is the sequence of coefficient constraints for inter-node edges.
4164 * "n_edge" is the total number of edges.
4165 * "carry_inter" indicates whether inter-node edges should be carried or
4166 * only respected. That is, if "carry_inter" is not set, then
4167 * no e_i variables are introduced for the inter-node edges.
4169 * All variables of the LP are non-negative. The actual coefficients
4170 * may be negative, so each coefficient is represented as the difference
4171 * of two non-negative variables. The negative part always appears
4172 * immediately before the positive part.
4173 * Other than that, the variables have the following order
4175 * - sum of (1 - e_i) over all edges
4176 * - sum of all c_n coefficients
4177 * (unconstrained when computing non-parametric schedules)
4178 * - sum of positive and negative parts of all c_x coefficients
4182 * - positive and negative parts of c_i_x, in opposite order
4183 * - c_i_n (if parametric)
4186 * The constraints are those from the (validity) edges plus three equalities
4187 * to express the sums and n_edge inequalities to express e_i <= 1.
4189 static isl_stat
setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
4190 int n_edge
, __isl_keep isl_basic_set_list
*intra
,
4191 __isl_keep isl_basic_set_list
*inter
, int carry_inter
)
4200 for (i
= 0; i
< graph
->n
; ++i
) {
4201 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
4202 node
->start
= total
;
4203 total
+= 1 + node
->nparam
+ 2 * node
->nvar
;
4206 if (count_all_constraints(intra
, inter
, &n_eq
, &n_ineq
) < 0)
4207 return isl_stat_error
;
4209 space
= isl_space_set_alloc(ctx
, 0, total
);
4210 isl_basic_set_free(graph
->lp
);
4213 graph
->lp
= isl_basic_set_alloc_space(space
, 0, n_eq
, n_ineq
);
4214 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
4216 k
= isl_basic_set_alloc_equality(graph
->lp
);
4218 return isl_stat_error
;
4219 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
4220 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
4221 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
4222 for (i
= 0; i
< n_edge
; ++i
)
4223 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
4225 if (add_param_sum_constraint(graph
, 1) < 0)
4226 return isl_stat_error
;
4227 if (add_var_sum_constraint(graph
, 2) < 0)
4228 return isl_stat_error
;
4230 for (i
= 0; i
< n_edge
; ++i
) {
4231 k
= isl_basic_set_alloc_inequality(graph
->lp
);
4233 return isl_stat_error
;
4234 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
4235 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
4236 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
4239 if (add_all_constraints(ctx
, graph
, intra
, inter
, carry_inter
) < 0)
4240 return isl_stat_error
;
4245 static __isl_give isl_schedule_node
*compute_component_schedule(
4246 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
4249 /* If the schedule_split_scaled option is set and if the linear
4250 * parts of the scheduling rows for all nodes in the graphs have
4251 * a non-trivial common divisor, then remove this
4252 * common divisor from the linear part.
4253 * Otherwise, insert a band node directly and continue with
4254 * the construction of the schedule.
4256 * If a non-trivial common divisor is found, then
4257 * the linear part is reduced and the remainder is ignored.
4258 * The pieces of the graph that are assigned different remainders
4259 * form (groups of) strongly connected components within
4260 * the scaled down band. If needed, they can therefore
4261 * be ordered along this remainder in a sequence node.
4262 * However, this ordering is not enforced here in order to allow
4263 * the scheduler to combine some of the strongly connected components.
4265 static __isl_give isl_schedule_node
*split_scaled(
4266 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
4277 ctx
= isl_schedule_node_get_ctx(node
);
4278 if (!ctx
->opt
->schedule_split_scaled
)
4279 return compute_next_band(node
, graph
, 0);
4281 return compute_next_band(node
, graph
, 0);
4282 n_row
= isl_mat_rows(graph
->node
[0].sched
);
4284 return isl_schedule_node_free(node
);
4287 isl_int_init(gcd_i
);
4289 isl_int_set_si(gcd
, 0);
4293 for (i
= 0; i
< graph
->n
; ++i
) {
4294 struct isl_sched_node
*node
= &graph
->node
[i
];
4295 isl_size cols
= isl_mat_cols(node
->sched
);
4299 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
4300 isl_int_gcd(gcd
, gcd
, gcd_i
);
4303 isl_int_clear(gcd_i
);
4307 if (isl_int_cmp_si(gcd
, 1) <= 0) {
4309 return compute_next_band(node
, graph
, 0);
4312 for (i
= 0; i
< graph
->n
; ++i
) {
4313 struct isl_sched_node
*node
= &graph
->node
[i
];
4315 isl_int_fdiv_q(node
->sched
->row
[row
][0],
4316 node
->sched
->row
[row
][0], gcd
);
4317 isl_int_mul(node
->sched
->row
[row
][0],
4318 node
->sched
->row
[row
][0], gcd
);
4319 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
4326 return compute_next_band(node
, graph
, 0);
4329 return isl_schedule_node_free(node
);
4332 /* Is the schedule row "sol" trivial on node "node"?
4333 * That is, is the solution zero on the dimensions linearly independent of
4334 * the previously found solutions?
4335 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
4337 * Each coefficient is represented as the difference between
4338 * two non-negative values in "sol".
4339 * We construct the schedule row s and check if it is linearly
4340 * independent of previously computed schedule rows
4341 * by computing T s, with T the linear combinations that are zero
4342 * on linearly dependent schedule rows.
4343 * If the result consists of all zeros, then the solution is trivial.
4345 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
4352 if (node
->nvar
== node
->rank
)
4355 node_sol
= extract_var_coef(node
, sol
);
4356 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->indep
), node_sol
);
4360 trivial
= isl_seq_first_non_zero(node_sol
->el
,
4361 node
->nvar
- node
->rank
) == -1;
4363 isl_vec_free(node_sol
);
4368 /* Is the schedule row "sol" trivial on any node where it should
4370 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4372 static int is_any_trivial(struct isl_sched_graph
*graph
,
4373 __isl_keep isl_vec
*sol
)
4377 for (i
= 0; i
< graph
->n
; ++i
) {
4378 struct isl_sched_node
*node
= &graph
->node
[i
];
4381 if (!needs_row(graph
, node
))
4383 trivial
= is_trivial(node
, sol
);
4384 if (trivial
< 0 || trivial
)
4391 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
4392 * If so, return the position of the coalesced dimension.
4393 * Otherwise, return node->nvar or -1 on error.
4395 * In particular, look for pairs of coefficients c_i and c_j such that
4396 * |c_j/c_i| > ceil(size_i/2), i.e., |c_j| > |c_i * ceil(size_i/2)|.
4397 * If any such pair is found, then return i.
4398 * If size_i is infinity, then no check on c_i needs to be performed.
4400 static int find_node_coalescing(struct isl_sched_node
*node
,
4401 __isl_keep isl_vec
*sol
)
4407 if (node
->nvar
<= 1)
4410 csol
= extract_var_coef(node
, sol
);
4414 for (i
= 0; i
< node
->nvar
; ++i
) {
4417 if (isl_int_is_zero(csol
->el
[i
]))
4419 v
= isl_multi_val_get_val(node
->sizes
, i
);
4422 if (!isl_val_is_int(v
)) {
4426 v
= isl_val_div_ui(v
, 2);
4427 v
= isl_val_ceil(v
);
4430 isl_int_mul(max
, v
->n
, csol
->el
[i
]);
4433 for (j
= 0; j
< node
->nvar
; ++j
) {
4436 if (isl_int_abs_gt(csol
->el
[j
], max
))
4452 /* Force the schedule coefficient at position "pos" of "node" to be zero
4454 * The coefficient is encoded as the difference between two non-negative
4455 * variables. Force these two variables to have the same value.
4457 static __isl_give isl_tab_lexmin
*zero_out_node_coef(
4458 __isl_take isl_tab_lexmin
*tl
, struct isl_sched_node
*node
, int pos
)
4464 ctx
= isl_space_get_ctx(node
->space
);
4465 dim
= isl_tab_lexmin_dim(tl
);
4467 return isl_tab_lexmin_free(tl
);
4468 eq
= isl_vec_alloc(ctx
, 1 + dim
);
4469 eq
= isl_vec_clr(eq
);
4471 return isl_tab_lexmin_free(tl
);
4473 pos
= 1 + node_var_coef_pos(node
, pos
);
4474 isl_int_set_si(eq
->el
[pos
], 1);
4475 isl_int_set_si(eq
->el
[pos
+ 1], -1);
4476 tl
= isl_tab_lexmin_add_eq(tl
, eq
->el
);
4482 /* Return the lexicographically smallest rational point in the basic set
4483 * from which "tl" was constructed, double checking that this input set
4486 static __isl_give isl_vec
*non_empty_solution(__isl_keep isl_tab_lexmin
*tl
)
4490 sol
= isl_tab_lexmin_get_solution(tl
);
4494 isl_die(isl_vec_get_ctx(sol
), isl_error_internal
,
4495 "error in schedule construction",
4496 return isl_vec_free(sol
));
4500 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4501 * carry any of the "n_edge" groups of dependences?
4502 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4503 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4504 * by the edge are carried by the solution.
4505 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4506 * one of those is carried.
4508 * Note that despite the fact that the problem is solved using a rational
4509 * solver, the solution is guaranteed to be integral.
4510 * Specifically, the dependence distance lower bounds e_i (and therefore
4511 * also their sum) are integers. See Lemma 5 of [1].
4513 * Any potential denominator of the sum is cleared by this function.
4514 * The denominator is not relevant for any of the other elements
4517 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4518 * Problem, Part II: Multi-Dimensional Time.
4519 * In Intl. Journal of Parallel Programming, 1992.
4521 static int carries_dependences(__isl_keep isl_vec
*sol
, int n_edge
)
4523 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
4524 isl_int_set_si(sol
->el
[0], 1);
4525 return isl_int_cmp_si(sol
->el
[1], n_edge
) < 0;
4528 /* Return the lexicographically smallest rational point in "lp",
4529 * assuming that all variables are non-negative and performing some
4530 * additional sanity checks.
4531 * If "want_integral" is set, then compute the lexicographically smallest
4532 * integer point instead.
4533 * In particular, "lp" should not be empty by construction.
4534 * Double check that this is the case.
4535 * If dependences are not carried for any of the "n_edge" edges,
4536 * then return an empty vector.
4538 * If the schedule_treat_coalescing option is set and
4539 * if the computed schedule performs loop coalescing on a given node,
4540 * i.e., if it is of the form
4542 * c_i i + c_j j + ...
4544 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4545 * to cut out this solution. Repeat this process until no more loop
4546 * coalescing occurs or until no more dependences can be carried.
4547 * In the latter case, revert to the previously computed solution.
4549 * If the caller requests an integral solution and if coalescing should
4550 * be treated, then perform the coalescing treatment first as
4551 * an integral solution computed before coalescing treatment
4552 * would carry the same number of edges and would therefore probably
4553 * also be coalescing.
4555 * To allow the coalescing treatment to be performed first,
4556 * the initial solution is allowed to be rational and it is only
4557 * cut out (if needed) in the next iteration, if no coalescing measures
4560 static __isl_give isl_vec
*non_neg_lexmin(struct isl_sched_graph
*graph
,
4561 __isl_take isl_basic_set
*lp
, int n_edge
, int want_integral
)
4566 isl_vec
*sol
= NULL
, *prev
;
4567 int treat_coalescing
;
4572 ctx
= isl_basic_set_get_ctx(lp
);
4573 treat_coalescing
= isl_options_get_schedule_treat_coalescing(ctx
);
4574 tl
= isl_tab_lexmin_from_basic_set(lp
);
4582 tl
= isl_tab_lexmin_cut_to_integer(tl
);
4584 sol
= non_empty_solution(tl
);
4588 integral
= isl_int_is_one(sol
->el
[0]);
4589 if (!carries_dependences(sol
, n_edge
)) {
4591 prev
= isl_vec_alloc(ctx
, 0);
4596 prev
= isl_vec_free(prev
);
4597 cut
= want_integral
&& !integral
;
4600 if (!treat_coalescing
)
4602 for (i
= 0; i
< graph
->n
; ++i
) {
4603 struct isl_sched_node
*node
= &graph
->node
[i
];
4605 pos
= find_node_coalescing(node
, sol
);
4608 if (pos
< node
->nvar
)
4613 tl
= zero_out_node_coef(tl
, &graph
->node
[i
], pos
);
4616 } while (try_again
);
4618 isl_tab_lexmin_free(tl
);
4622 isl_tab_lexmin_free(tl
);
4628 /* If "edge" is an edge from a node to itself, then add the corresponding
4629 * dependence relation to "umap".
4630 * If "node" has been compressed, then the dependence relation
4631 * is also compressed first.
4633 static __isl_give isl_union_map
*add_intra(__isl_take isl_union_map
*umap
,
4634 struct isl_sched_edge
*edge
)
4637 struct isl_sched_node
*node
= edge
->src
;
4639 if (edge
->src
!= edge
->dst
)
4642 map
= isl_map_copy(edge
->map
);
4643 map
= compress(map
, node
, node
);
4644 umap
= isl_union_map_add_map(umap
, map
);
4648 /* If "edge" is an edge from a node to another node, then add the corresponding
4649 * dependence relation to "umap".
4650 * If the source or destination nodes of "edge" have been compressed,
4651 * then the dependence relation is also compressed first.
4653 static __isl_give isl_union_map
*add_inter(__isl_take isl_union_map
*umap
,
4654 struct isl_sched_edge
*edge
)
4658 if (edge
->src
== edge
->dst
)
4661 map
= isl_map_copy(edge
->map
);
4662 map
= compress(map
, edge
->src
, edge
->dst
);
4663 umap
= isl_union_map_add_map(umap
, map
);
4667 /* Internal data structure used by union_drop_coalescing_constraints
4668 * to collect bounds on all relevant statements.
4670 * "graph" is the schedule constraint graph for which an LP problem
4671 * is being constructed.
4672 * "bounds" collects the bounds.
4674 struct isl_collect_bounds_data
{
4676 struct isl_sched_graph
*graph
;
4677 isl_union_set
*bounds
;
4680 /* Add the size bounds for the node with instance deltas in "set"
4683 static isl_stat
collect_bounds(__isl_take isl_set
*set
, void *user
)
4685 struct isl_collect_bounds_data
*data
= user
;
4686 struct isl_sched_node
*node
;
4690 space
= isl_set_get_space(set
);
4693 node
= graph_find_compressed_node(data
->ctx
, data
->graph
, space
);
4694 isl_space_free(space
);
4696 bounds
= isl_set_from_basic_set(get_size_bounds(node
));
4697 data
->bounds
= isl_union_set_add_set(data
->bounds
, bounds
);
4702 /* Drop some constraints from "delta" that could be exploited
4703 * to construct loop coalescing schedules.
4704 * In particular, drop those constraint that bound the difference
4705 * to the size of the domain.
4706 * Do this for each set/node in "delta" separately.
4707 * The parameters are assumed to have been projected out by the caller.
4709 static __isl_give isl_union_set
*union_drop_coalescing_constraints(isl_ctx
*ctx
,
4710 struct isl_sched_graph
*graph
, __isl_take isl_union_set
*delta
)
4712 struct isl_collect_bounds_data data
= { ctx
, graph
};
4714 data
.bounds
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
4715 if (isl_union_set_foreach_set(delta
, &collect_bounds
, &data
) < 0)
4716 data
.bounds
= isl_union_set_free(data
.bounds
);
4717 delta
= isl_union_set_plain_gist(delta
, data
.bounds
);
4722 /* Given a non-trivial lineality space "lineality", add the corresponding
4723 * universe set to data->mask and add a map from elements to
4724 * other elements along the lines in "lineality" to data->equivalent.
4725 * If this is the first time this function gets called
4726 * (data->any_non_trivial is still false), then set data->any_non_trivial and
4727 * initialize data->mask and data->equivalent.
4729 * In particular, if the lineality space is defined by equality constraints
4733 * then construct an affine mapping
4737 * and compute the equivalence relation of having the same image under f:
4739 * { x -> x' : E x = E x' }
4741 static isl_stat
add_non_trivial_lineality(__isl_take isl_basic_set
*lineality
,
4742 struct isl_exploit_lineality_data
*data
)
4748 isl_multi_pw_aff
*mpa
;
4752 if (isl_basic_set_check_no_locals(lineality
) < 0)
4755 space
= isl_basic_set_get_space(lineality
);
4756 if (!data
->any_non_trivial
) {
4757 data
->equivalent
= isl_union_map_empty(isl_space_copy(space
));
4758 data
->mask
= isl_union_set_empty(isl_space_copy(space
));
4760 data
->any_non_trivial
= isl_bool_true
;
4762 univ
= isl_set_universe(isl_space_copy(space
));
4763 data
->mask
= isl_union_set_add_set(data
->mask
, univ
);
4765 eq
= isl_basic_set_extract_equalities(lineality
);
4766 n
= isl_mat_rows(eq
);
4768 space
= isl_space_free(space
);
4769 eq
= isl_mat_insert_zero_rows(eq
, 0, 1);
4770 eq
= isl_mat_set_element_si(eq
, 0, 0, 1);
4771 space
= isl_space_from_domain(space
);
4772 space
= isl_space_add_dims(space
, isl_dim_out
, n
);
4773 ma
= isl_multi_aff_from_aff_mat(space
, eq
);
4774 mpa
= isl_multi_pw_aff_from_multi_aff(ma
);
4775 map
= isl_multi_pw_aff_eq_map(mpa
, isl_multi_pw_aff_copy(mpa
));
4776 data
->equivalent
= isl_union_map_add_map(data
->equivalent
, map
);
4778 isl_basic_set_free(lineality
);
4781 isl_basic_set_free(lineality
);
4782 return isl_stat_error
;
4785 /* Check if the lineality space "set" is non-trivial (i.e., is not just
4786 * the origin or, in other words, satisfies a number of equality constraints
4787 * that is smaller than the dimension of the set).
4788 * If so, extend data->mask and data->equivalent accordingly.
4790 * The input should not have any local variables already, but
4791 * isl_set_remove_divs is called to make sure it does not.
4793 static isl_stat
add_lineality(__isl_take isl_set
*set
, void *user
)
4795 struct isl_exploit_lineality_data
*data
= user
;
4796 isl_basic_set
*hull
;
4800 set
= isl_set_remove_divs(set
);
4801 hull
= isl_set_unshifted_simple_hull(set
);
4802 dim
= isl_basic_set_dim(hull
, isl_dim_set
);
4803 n_eq
= isl_basic_set_n_equality(hull
);
4804 if (dim
< 0 || n_eq
< 0)
4807 return add_non_trivial_lineality(hull
, data
);
4808 isl_basic_set_free(hull
);
4811 isl_basic_set_free(hull
);
4812 return isl_stat_error
;
4815 /* Check if the difference set on intra-node schedule constraints "intra"
4816 * has any non-trivial lineality space.
4817 * If so, then extend the difference set to a difference set
4818 * on equivalent elements. That is, if "intra" is
4820 * { y - x : (x,y) \in V }
4822 * and elements are equivalent if they have the same image under f,
4825 * { y' - x' : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4827 * or, since f is linear,
4829 * { y' - x' : (x,y) \in V and f(y - x) = f(y' - x') }
4831 * The results of the search for non-trivial lineality spaces is stored
4834 static __isl_give isl_union_set
*exploit_intra_lineality(
4835 __isl_take isl_union_set
*intra
,
4836 struct isl_exploit_lineality_data
*data
)
4838 isl_union_set
*lineality
;
4839 isl_union_set
*uset
;
4841 data
->any_non_trivial
= isl_bool_false
;
4842 lineality
= isl_union_set_copy(intra
);
4843 lineality
= isl_union_set_combined_lineality_space(lineality
);
4844 if (isl_union_set_foreach_set(lineality
, &add_lineality
, data
) < 0)
4845 data
->any_non_trivial
= isl_bool_error
;
4846 isl_union_set_free(lineality
);
4848 if (data
->any_non_trivial
< 0)
4849 return isl_union_set_free(intra
);
4850 if (!data
->any_non_trivial
)
4853 uset
= isl_union_set_copy(intra
);
4854 intra
= isl_union_set_subtract(intra
, isl_union_set_copy(data
->mask
));
4855 uset
= isl_union_set_apply(uset
, isl_union_map_copy(data
->equivalent
));
4856 intra
= isl_union_set_union(intra
, uset
);
4858 intra
= isl_union_set_remove_divs(intra
);
4863 /* If the difference set on intra-node schedule constraints was found to have
4864 * any non-trivial lineality space by exploit_intra_lineality,
4865 * as recorded in "data", then extend the inter-node
4866 * schedule constraints "inter" to schedule constraints on equivalent elements.
4867 * That is, if "inter" is V and
4868 * elements are equivalent if they have the same image under f, then return
4870 * { (x', y') : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4872 static __isl_give isl_union_map
*exploit_inter_lineality(
4873 __isl_take isl_union_map
*inter
,
4874 struct isl_exploit_lineality_data
*data
)
4876 isl_union_map
*umap
;
4878 if (data
->any_non_trivial
< 0)
4879 return isl_union_map_free(inter
);
4880 if (!data
->any_non_trivial
)
4883 umap
= isl_union_map_copy(inter
);
4884 inter
= isl_union_map_subtract_range(inter
,
4885 isl_union_set_copy(data
->mask
));
4886 umap
= isl_union_map_apply_range(umap
,
4887 isl_union_map_copy(data
->equivalent
));
4888 inter
= isl_union_map_union(inter
, umap
);
4889 umap
= isl_union_map_copy(inter
);
4890 inter
= isl_union_map_subtract_domain(inter
,
4891 isl_union_set_copy(data
->mask
));
4892 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->equivalent
),
4894 inter
= isl_union_map_union(inter
, umap
);
4896 inter
= isl_union_map_remove_divs(inter
);
4901 /* For each (conditional) validity edge in "graph",
4902 * add the corresponding dependence relation using "add"
4903 * to a collection of dependence relations and return the result.
4904 * If "coincidence" is set, then coincidence edges are considered as well.
4906 static __isl_give isl_union_map
*collect_validity(struct isl_sched_graph
*graph
,
4907 __isl_give isl_union_map
*(*add
)(__isl_take isl_union_map
*umap
,
4908 struct isl_sched_edge
*edge
), int coincidence
)
4912 isl_union_map
*umap
;
4914 space
= isl_space_copy(graph
->node
[0].space
);
4915 umap
= isl_union_map_empty(space
);
4917 for (i
= 0; i
< graph
->n_edge
; ++i
) {
4918 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
4920 if (!is_any_validity(edge
) &&
4921 (!coincidence
|| !is_coincidence(edge
)))
4924 umap
= add(umap
, edge
);
4930 /* For each dependence relation on a (conditional) validity edge
4931 * from a node to itself,
4932 * construct the set of coefficients of valid constraints for elements
4933 * in that dependence relation and collect the results.
4934 * If "coincidence" is set, then coincidence edges are considered as well.
4936 * In particular, for each dependence relation R, constraints
4937 * on coefficients (c_0, c_x) are constructed such that
4939 * c_0 + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
4941 * If the schedule_treat_coalescing option is set, then some constraints
4942 * that could be exploited to construct coalescing schedules
4943 * are removed before the dual is computed, but after the parameters
4944 * have been projected out.
4945 * The entire computation is essentially the same as that performed
4946 * by intra_coefficients, except that it operates on multiple
4947 * edges together and that the parameters are always projected out.
4949 * Additionally, exploit any non-trivial lineality space
4950 * in the difference set after removing coalescing constraints and
4951 * store the results of the non-trivial lineality space detection in "data".
4952 * The procedure is currently run unconditionally, but it is unlikely
4953 * to find any non-trivial lineality spaces if no coalescing constraints
4954 * have been removed.
4956 * Note that if a dependence relation is a union of basic maps,
4957 * then each basic map needs to be treated individually as it may only
4958 * be possible to carry the dependences expressed by some of those
4959 * basic maps and not all of them.
4960 * The collected validity constraints are therefore not coalesced and
4961 * it is assumed that they are not coalesced automatically.
4962 * Duplicate basic maps can be removed, however.
4963 * In particular, if the same basic map appears as a disjunct
4964 * in multiple edges, then it only needs to be carried once.
4966 static __isl_give isl_basic_set_list
*collect_intra_validity(isl_ctx
*ctx
,
4967 struct isl_sched_graph
*graph
, int coincidence
,
4968 struct isl_exploit_lineality_data
*data
)
4970 isl_union_map
*intra
;
4971 isl_union_set
*delta
;
4972 isl_basic_set_list
*list
;
4974 intra
= collect_validity(graph
, &add_intra
, coincidence
);
4975 delta
= isl_union_map_deltas(intra
);
4976 delta
= isl_union_set_project_out_all_params(delta
);
4977 delta
= isl_union_set_remove_divs(delta
);
4978 if (isl_options_get_schedule_treat_coalescing(ctx
))
4979 delta
= union_drop_coalescing_constraints(ctx
, graph
, delta
);
4980 delta
= exploit_intra_lineality(delta
, data
);
4981 list
= isl_union_set_get_basic_set_list(delta
);
4982 isl_union_set_free(delta
);
4984 return isl_basic_set_list_coefficients(list
);
4987 /* For each dependence relation on a (conditional) validity edge
4988 * from a node to some other node,
4989 * construct the set of coefficients of valid constraints for elements
4990 * in that dependence relation and collect the results.
4991 * If "coincidence" is set, then coincidence edges are considered as well.
4993 * In particular, for each dependence relation R, constraints
4994 * on coefficients (c_0, c_n, c_x, c_y) are constructed such that
4996 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
4998 * This computation is essentially the same as that performed
4999 * by inter_coefficients, except that it operates on multiple
5002 * Additionally, exploit any non-trivial lineality space
5003 * that may have been discovered by collect_intra_validity
5004 * (as stored in "data").
5006 * Note that if a dependence relation is a union of basic maps,
5007 * then each basic map needs to be treated individually as it may only
5008 * be possible to carry the dependences expressed by some of those
5009 * basic maps and not all of them.
5010 * The collected validity constraints are therefore not coalesced and
5011 * it is assumed that they are not coalesced automatically.
5012 * Duplicate basic maps can be removed, however.
5013 * In particular, if the same basic map appears as a disjunct
5014 * in multiple edges, then it only needs to be carried once.
5016 static __isl_give isl_basic_set_list
*collect_inter_validity(
5017 struct isl_sched_graph
*graph
, int coincidence
,
5018 struct isl_exploit_lineality_data
*data
)
5020 isl_union_map
*inter
;
5021 isl_union_set
*wrap
;
5022 isl_basic_set_list
*list
;
5024 inter
= collect_validity(graph
, &add_inter
, coincidence
);
5025 inter
= exploit_inter_lineality(inter
, data
);
5026 inter
= isl_union_map_remove_divs(inter
);
5027 wrap
= isl_union_map_wrap(inter
);
5028 list
= isl_union_set_get_basic_set_list(wrap
);
5029 isl_union_set_free(wrap
);
5030 return isl_basic_set_list_coefficients(list
);
5033 /* Construct an LP problem for finding schedule coefficients
5034 * such that the schedule carries as many of the "n_edge" groups of
5035 * dependences as possible based on the corresponding coefficient
5036 * constraints and return the lexicographically smallest non-trivial solution.
5037 * "intra" is the sequence of coefficient constraints for intra-node edges.
5038 * "inter" is the sequence of coefficient constraints for inter-node edges.
5039 * If "want_integral" is set, then compute an integral solution
5040 * for the coefficients rather than using the numerators
5041 * of a rational solution.
5042 * "carry_inter" indicates whether inter-node edges should be carried or
5045 * If none of the "n_edge" groups can be carried
5046 * then return an empty vector.
5048 static __isl_give isl_vec
*compute_carrying_sol_coef(isl_ctx
*ctx
,
5049 struct isl_sched_graph
*graph
, int n_edge
,
5050 __isl_keep isl_basic_set_list
*intra
,
5051 __isl_keep isl_basic_set_list
*inter
, int want_integral
,
5056 if (setup_carry_lp(ctx
, graph
, n_edge
, intra
, inter
, carry_inter
) < 0)
5059 lp
= isl_basic_set_copy(graph
->lp
);
5060 return non_neg_lexmin(graph
, lp
, n_edge
, want_integral
);
5063 /* Construct an LP problem for finding schedule coefficients
5064 * such that the schedule carries as many of the validity dependences
5066 * return the lexicographically smallest non-trivial solution.
5067 * If "fallback" is set, then the carrying is performed as a fallback
5068 * for the Pluto-like scheduler.
5069 * If "coincidence" is set, then try and carry coincidence edges as well.
5071 * The variable "n_edge" stores the number of groups that should be carried.
5072 * If none of the "n_edge" groups can be carried
5073 * then return an empty vector.
5074 * If, moreover, "n_edge" is zero, then the LP problem does not even
5075 * need to be constructed.
5077 * If a fallback solution is being computed, then compute an integral solution
5078 * for the coefficients rather than using the numerators
5079 * of a rational solution.
5081 * If a fallback solution is being computed, if there are any intra-node
5082 * dependences, and if requested by the user, then first try
5083 * to only carry those intra-node dependences.
5084 * If this fails to carry any dependences, then try again
5085 * with the inter-node dependences included.
5087 static __isl_give isl_vec
*compute_carrying_sol(isl_ctx
*ctx
,
5088 struct isl_sched_graph
*graph
, int fallback
, int coincidence
)
5090 isl_size n_intra
, n_inter
;
5092 struct isl_carry carry
= { 0 };
5095 carry
.intra
= collect_intra_validity(ctx
, graph
, coincidence
,
5097 carry
.inter
= collect_inter_validity(graph
, coincidence
,
5099 n_intra
= isl_basic_set_list_n_basic_set(carry
.intra
);
5100 n_inter
= isl_basic_set_list_n_basic_set(carry
.inter
);
5101 if (n_intra
< 0 || n_inter
< 0)
5104 if (fallback
&& n_intra
> 0 &&
5105 isl_options_get_schedule_carry_self_first(ctx
)) {
5106 sol
= compute_carrying_sol_coef(ctx
, graph
, n_intra
,
5107 carry
.intra
, carry
.inter
, fallback
, 0);
5108 if (!sol
|| sol
->size
!= 0 || n_inter
== 0) {
5109 isl_carry_clear(&carry
);
5115 n_edge
= n_intra
+ n_inter
;
5117 isl_carry_clear(&carry
);
5118 return isl_vec_alloc(ctx
, 0);
5121 sol
= compute_carrying_sol_coef(ctx
, graph
, n_edge
,
5122 carry
.intra
, carry
.inter
, fallback
, 1);
5123 isl_carry_clear(&carry
);
5126 isl_carry_clear(&carry
);
5130 /* Construct a schedule row for each node such that as many validity dependences
5131 * as possible are carried and then continue with the next band.
5132 * If "fallback" is set, then the carrying is performed as a fallback
5133 * for the Pluto-like scheduler.
5134 * If "coincidence" is set, then try and carry coincidence edges as well.
5136 * If there are no validity dependences, then no dependence can be carried and
5137 * the procedure is guaranteed to fail. If there is more than one component,
5138 * then try computing a schedule on each component separately
5139 * to prevent or at least postpone this failure.
5141 * If a schedule row is computed, then check that dependences are carried
5142 * for at least one of the edges.
5144 * If the computed schedule row turns out to be trivial on one or
5145 * more nodes where it should not be trivial, then we throw it away
5146 * and try again on each component separately.
5148 * If there is only one component, then we accept the schedule row anyway,
5149 * but we do not consider it as a complete row and therefore do not
5150 * increment graph->n_row. Note that the ranks of the nodes that
5151 * do get a non-trivial schedule part will get updated regardless and
5152 * graph->maxvar is computed based on these ranks. The test for
5153 * whether more schedule rows are required in compute_schedule_wcc
5154 * is therefore not affected.
5156 * Insert a band corresponding to the schedule row at position "node"
5157 * of the schedule tree and continue with the construction of the schedule.
5158 * This insertion and the continued construction is performed by split_scaled
5159 * after optionally checking for non-trivial common divisors.
5161 static __isl_give isl_schedule_node
*carry(__isl_take isl_schedule_node
*node
,
5162 struct isl_sched_graph
*graph
, int fallback
, int coincidence
)
5171 ctx
= isl_schedule_node_get_ctx(node
);
5172 sol
= compute_carrying_sol(ctx
, graph
, fallback
, coincidence
);
5174 return isl_schedule_node_free(node
);
5175 if (sol
->size
== 0) {
5178 return compute_component_schedule(node
, graph
, 1);
5179 isl_die(ctx
, isl_error_unknown
, "unable to carry dependences",
5180 return isl_schedule_node_free(node
));
5183 trivial
= is_any_trivial(graph
, sol
);
5185 sol
= isl_vec_free(sol
);
5186 } else if (trivial
&& graph
->scc
> 1) {
5188 return compute_component_schedule(node
, graph
, 1);
5191 if (update_schedule(graph
, sol
, 0) < 0)
5192 return isl_schedule_node_free(node
);
5196 return split_scaled(node
, graph
);
5199 /* Construct a schedule row for each node such that as many validity dependences
5200 * as possible are carried and then continue with the next band.
5201 * Do so as a fallback for the Pluto-like scheduler.
5202 * If "coincidence" is set, then try and carry coincidence edges as well.
5204 static __isl_give isl_schedule_node
*carry_fallback(
5205 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5208 return carry(node
, graph
, 1, coincidence
);
5211 /* Construct a schedule row for each node such that as many validity dependences
5212 * as possible are carried and then continue with the next band.
5213 * Do so for the case where the Feautrier scheduler was selected
5216 static __isl_give isl_schedule_node
*carry_feautrier(
5217 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5219 return carry(node
, graph
, 0, 0);
5222 /* Construct a schedule row for each node such that as many validity dependences
5223 * as possible are carried and then continue with the next band.
5224 * Do so as a fallback for the Pluto-like scheduler.
5226 static __isl_give isl_schedule_node
*carry_dependences(
5227 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5229 return carry_fallback(node
, graph
, 0);
5232 /* Construct a schedule row for each node such that as many validity or
5233 * coincidence dependences as possible are carried and
5234 * then continue with the next band.
5235 * Do so as a fallback for the Pluto-like scheduler.
5237 static __isl_give isl_schedule_node
*carry_coincidence(
5238 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5240 return carry_fallback(node
, graph
, 1);
5243 /* Topologically sort statements mapped to the same schedule iteration
5244 * and add insert a sequence node in front of "node"
5245 * corresponding to this order.
5246 * If "initialized" is set, then it may be assumed that
5247 * isl_sched_graph_compute_maxvar
5248 * has been called on the current band. Otherwise, call
5249 * isl_sched_graph_compute_maxvar if and before carry_dependences gets called.
5251 * If it turns out to be impossible to sort the statements apart,
5252 * because different dependences impose different orderings
5253 * on the statements, then we extend the schedule such that
5254 * it carries at least one more dependence.
5256 static __isl_give isl_schedule_node
*sort_statements(
5257 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5261 isl_union_set_list
*filters
;
5266 ctx
= isl_schedule_node_get_ctx(node
);
5268 isl_die(ctx
, isl_error_internal
,
5269 "graph should have at least one node",
5270 return isl_schedule_node_free(node
));
5275 if (update_edges(ctx
, graph
) < 0)
5276 return isl_schedule_node_free(node
);
5278 if (graph
->n_edge
== 0)
5281 if (detect_sccs(ctx
, graph
) < 0)
5282 return isl_schedule_node_free(node
);
5285 if (graph
->scc
< graph
->n
) {
5286 if (!initialized
&& isl_sched_graph_compute_maxvar(graph
) < 0)
5287 return isl_schedule_node_free(node
);
5288 return carry_dependences(node
, graph
);
5291 filters
= isl_sched_graph_extract_sccs(ctx
, graph
);
5292 node
= isl_schedule_node_insert_sequence(node
, filters
);
5297 /* Are there any (non-empty) (conditional) validity edges in the graph?
5299 static int has_validity_edges(struct isl_sched_graph
*graph
)
5303 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5306 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
5311 if (is_any_validity(&graph
->edge
[i
]))
5318 /* Should we apply a Feautrier step?
5319 * That is, did the user request the Feautrier algorithm and are
5320 * there any validity dependences (left)?
5322 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
5324 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
5327 return has_validity_edges(graph
);
5330 /* Compute a schedule for a connected dependence graph using Feautrier's
5331 * multi-dimensional scheduling algorithm and return the updated schedule node.
5333 * The original algorithm is described in [1].
5334 * The main idea is to minimize the number of scheduling dimensions, by
5335 * trying to satisfy as many dependences as possible per scheduling dimension.
5337 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
5338 * Problem, Part II: Multi-Dimensional Time.
5339 * In Intl. Journal of Parallel Programming, 1992.
5341 static __isl_give isl_schedule_node
*compute_schedule_wcc_feautrier(
5342 isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5344 return carry_feautrier(node
, graph
);
5347 /* Turn off the "local" bit on all (condition) edges.
5349 static void clear_local_edges(struct isl_sched_graph
*graph
)
5353 for (i
= 0; i
< graph
->n_edge
; ++i
)
5354 if (isl_sched_edge_is_condition(&graph
->edge
[i
]))
5355 clear_local(&graph
->edge
[i
]);
5358 /* Does "graph" have both condition and conditional validity edges?
5360 static int need_condition_check(struct isl_sched_graph
*graph
)
5363 int any_condition
= 0;
5364 int any_conditional_validity
= 0;
5366 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5367 if (isl_sched_edge_is_condition(&graph
->edge
[i
]))
5369 if (isl_sched_edge_is_conditional_validity(&graph
->edge
[i
]))
5370 any_conditional_validity
= 1;
5373 return any_condition
&& any_conditional_validity
;
5376 /* Does "graph" contain any coincidence edge?
5378 static int has_any_coincidence(struct isl_sched_graph
*graph
)
5382 for (i
= 0; i
< graph
->n_edge
; ++i
)
5383 if (is_coincidence(&graph
->edge
[i
]))
5389 /* Extract the final schedule row as a map with the iteration domain
5390 * of "node" as domain.
5392 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
5397 n_row
= isl_mat_rows(node
->sched
);
5400 ma
= isl_sched_node_extract_partial_schedule_multi_aff(node
,
5402 return isl_map_from_multi_aff(ma
);
5405 /* Is the conditional validity dependence in the edge with index "edge_index"
5406 * violated by the latest (i.e., final) row of the schedule?
5407 * That is, is i scheduled after j
5408 * for any conditional validity dependence i -> j?
5410 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
5412 isl_map
*src_sched
, *dst_sched
, *map
;
5413 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
5416 src_sched
= final_row(edge
->src
);
5417 dst_sched
= final_row(edge
->dst
);
5418 map
= isl_map_copy(edge
->map
);
5419 map
= isl_map_apply_domain(map
, src_sched
);
5420 map
= isl_map_apply_range(map
, dst_sched
);
5421 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
5422 empty
= isl_map_is_empty(map
);
5431 /* Does "graph" have any satisfied condition edges that
5432 * are adjacent to the conditional validity constraint with
5433 * domain "conditional_source" and range "conditional_sink"?
5435 * A satisfied condition is one that is not local.
5436 * If a condition was forced to be local already (i.e., marked as local)
5437 * then there is no need to check if it is in fact local.
5439 * Additionally, mark all adjacent condition edges found as local.
5441 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
5442 __isl_keep isl_union_set
*conditional_source
,
5443 __isl_keep isl_union_set
*conditional_sink
)
5448 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5449 int adjacent
, local
;
5450 isl_union_map
*condition
;
5452 if (!isl_sched_edge_is_condition(&graph
->edge
[i
]))
5454 if (is_local(&graph
->edge
[i
]))
5457 condition
= graph
->edge
[i
].tagged_condition
;
5458 adjacent
= domain_intersects(condition
, conditional_sink
);
5459 if (adjacent
>= 0 && !adjacent
)
5460 adjacent
= range_intersects(condition
,
5461 conditional_source
);
5467 set_local(&graph
->edge
[i
]);
5469 local
= is_condition_false(&graph
->edge
[i
]);
5479 /* Are there any violated conditional validity dependences with
5480 * adjacent condition dependences that are not local with respect
5481 * to the current schedule?
5482 * That is, is the conditional validity constraint violated?
5484 * Additionally, mark all those adjacent condition dependences as local.
5485 * We also mark those adjacent condition dependences that were not marked
5486 * as local before, but just happened to be local already. This ensures
5487 * that they remain local if the schedule is recomputed.
5489 * We first collect domain and range of all violated conditional validity
5490 * dependences and then check if there are any adjacent non-local
5491 * condition dependences.
5493 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
5494 struct isl_sched_graph
*graph
)
5498 isl_union_set
*source
, *sink
;
5500 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
5501 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
5502 for (i
= 0; i
< graph
->n_edge
; ++i
) {
5503 isl_union_set
*uset
;
5504 isl_union_map
*umap
;
5507 if (!isl_sched_edge_is_conditional_validity(&graph
->edge
[i
]))
5510 violated
= is_violated(graph
, i
);
5518 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
5519 uset
= isl_union_map_domain(umap
);
5520 source
= isl_union_set_union(source
, uset
);
5521 source
= isl_union_set_coalesce(source
);
5523 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
5524 uset
= isl_union_map_range(umap
);
5525 sink
= isl_union_set_union(sink
, uset
);
5526 sink
= isl_union_set_coalesce(sink
);
5530 any
= has_adjacent_true_conditions(graph
, source
, sink
);
5532 isl_union_set_free(source
);
5533 isl_union_set_free(sink
);
5536 isl_union_set_free(source
);
5537 isl_union_set_free(sink
);
5541 /* Examine the current band (the rows between graph->band_start and
5542 * graph->n_total_row), deciding whether to drop it or add it to "node"
5543 * and then continue with the computation of the next band, if any.
5544 * If "initialized" is set, then it may be assumed that
5545 * isl_sched_graph_compute_maxvar
5546 * has been called on the current band. Otherwise, call
5547 * isl_sched_graph_compute_maxvar if and before carry_dependences gets called.
5549 * The caller keeps looking for a new row as long as
5550 * graph->n_row < graph->maxvar. If the latest attempt to find
5551 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
5553 * - split between SCCs and start over (assuming we found an interesting
5554 * pair of SCCs between which to split)
5555 * - continue with the next band (assuming the current band has at least
5557 * - if there is more than one SCC left, then split along all SCCs
5558 * - if outer coincidence needs to be enforced, then try to carry as many
5559 * validity or coincidence dependences as possible and
5560 * continue with the next band
5561 * - try to carry as many validity dependences as possible and
5562 * continue with the next band
5563 * In each case, we first insert a band node in the schedule tree
5564 * if any rows have been computed.
5566 * If the caller managed to complete the schedule and the current band
5567 * is empty, then finish off by topologically
5568 * sorting the statements based on the remaining dependences.
5569 * If, on the other hand, the current band has at least one row,
5570 * then continue with the next band. Note that this next band
5571 * will necessarily be empty, but the graph may still be split up
5572 * into weakly connected components before arriving back here.
5574 __isl_give isl_schedule_node
*isl_schedule_node_compute_finish_band(
5575 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5583 empty
= graph
->n_total_row
== graph
->band_start
;
5584 if (graph
->n_row
< graph
->maxvar
) {
5587 ctx
= isl_schedule_node_get_ctx(node
);
5588 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
5589 return compute_next_band(node
, graph
, 1);
5590 if (graph
->src_scc
>= 0)
5591 return compute_split_schedule(node
, graph
);
5593 return compute_next_band(node
, graph
, 1);
5595 return compute_component_schedule(node
, graph
, 1);
5596 if (!initialized
&& isl_sched_graph_compute_maxvar(graph
) < 0)
5597 return isl_schedule_node_free(node
);
5598 if (isl_options_get_schedule_outer_coincidence(ctx
))
5599 return carry_coincidence(node
, graph
);
5600 return carry_dependences(node
, graph
);
5604 return compute_next_band(node
, graph
, 1);
5605 return sort_statements(node
, graph
, initialized
);
5608 /* Construct a band of schedule rows for a connected dependence graph.
5609 * The caller is responsible for determining the strongly connected
5610 * components and calling isl_sched_graph_compute_maxvar first.
5612 * We try to find a sequence of as many schedule rows as possible that result
5613 * in non-negative dependence distances (independent of the previous rows
5614 * in the sequence, i.e., such that the sequence is tilable), with as
5615 * many of the initial rows as possible satisfying the coincidence constraints.
5616 * The computation stops if we can't find any more rows or if we have found
5617 * all the rows we wanted to find.
5619 * If ctx->opt->schedule_outer_coincidence is set, then we force the
5620 * outermost dimension to satisfy the coincidence constraints. If this
5621 * turns out to be impossible, we fall back on the general scheme above
5622 * and try to carry as many dependences as possible.
5624 * If "graph" contains both condition and conditional validity dependences,
5625 * then we need to check that that the conditional schedule constraint
5626 * is satisfied, i.e., there are no violated conditional validity dependences
5627 * that are adjacent to any non-local condition dependences.
5628 * If there are, then we mark all those adjacent condition dependences
5629 * as local and recompute the current band. Those dependences that
5630 * are marked local will then be forced to be local.
5631 * The initial computation is performed with no dependences marked as local.
5632 * If we are lucky, then there will be no violated conditional validity
5633 * dependences adjacent to any non-local condition dependences.
5634 * Otherwise, we mark some additional condition dependences as local and
5635 * recompute. We continue this process until there are no violations left or
5636 * until we are no longer able to compute a schedule.
5637 * Since there are only a finite number of dependences,
5638 * there will only be a finite number of iterations.
5640 isl_stat
isl_schedule_node_compute_wcc_band(isl_ctx
*ctx
,
5641 struct isl_sched_graph
*graph
)
5643 int has_coincidence
;
5644 int use_coincidence
;
5645 int force_coincidence
= 0;
5646 int check_conditional
;
5648 if (sort_sccs(graph
) < 0)
5649 return isl_stat_error
;
5651 clear_local_edges(graph
);
5652 check_conditional
= need_condition_check(graph
);
5653 has_coincidence
= has_any_coincidence(graph
);
5655 if (ctx
->opt
->schedule_outer_coincidence
)
5656 force_coincidence
= 1;
5658 use_coincidence
= has_coincidence
;
5659 while (graph
->n_row
< graph
->maxvar
) {
5664 graph
->src_scc
= -1;
5665 graph
->dst_scc
= -1;
5667 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
5668 return isl_stat_error
;
5669 sol
= solve_lp(ctx
, graph
);
5671 return isl_stat_error
;
5672 if (sol
->size
== 0) {
5673 int empty
= graph
->n_total_row
== graph
->band_start
;
5676 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
5677 use_coincidence
= 0;
5682 coincident
= !has_coincidence
|| use_coincidence
;
5683 if (update_schedule(graph
, sol
, coincident
) < 0)
5684 return isl_stat_error
;
5686 if (!check_conditional
)
5688 violated
= has_violated_conditional_constraint(ctx
, graph
);
5690 return isl_stat_error
;
5693 if (reset_band(graph
) < 0)
5694 return isl_stat_error
;
5695 use_coincidence
= has_coincidence
;
5701 /* Compute a schedule for a connected dependence graph by considering
5702 * the graph as a whole and return the updated schedule node.
5704 * The actual schedule rows of the current band are computed by
5705 * isl_schedule_node_compute_wcc_band. isl_schedule_node_compute_finish_band
5706 * takes care of integrating the band into "node" and continuing
5709 static __isl_give isl_schedule_node
*compute_schedule_wcc_whole(
5710 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5717 ctx
= isl_schedule_node_get_ctx(node
);
5718 if (isl_schedule_node_compute_wcc_band(ctx
, graph
) < 0)
5719 return isl_schedule_node_free(node
);
5721 return isl_schedule_node_compute_finish_band(node
, graph
, 1);
5724 /* Compute a schedule for a connected dependence graph and return
5725 * the updated schedule node.
5727 * If Feautrier's algorithm is selected, we first recursively try to satisfy
5728 * as many validity dependences as possible. When all validity dependences
5729 * are satisfied we extend the schedule to a full-dimensional schedule.
5731 * Call compute_schedule_wcc_whole or isl_schedule_node_compute_wcc_clustering
5732 * depending on whether the user has selected the option to try and
5733 * compute a schedule for the entire (weakly connected) component first.
5734 * If there is only a single strongly connected component (SCC), then
5735 * there is no point in trying to combine SCCs
5736 * in isl_schedule_node_compute_wcc_clustering, so compute_schedule_wcc_whole
5737 * is called instead.
5739 static __isl_give isl_schedule_node
*compute_schedule_wcc(
5740 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
)
5747 ctx
= isl_schedule_node_get_ctx(node
);
5748 if (detect_sccs(ctx
, graph
) < 0)
5749 return isl_schedule_node_free(node
);
5751 if (isl_sched_graph_compute_maxvar(graph
) < 0)
5752 return isl_schedule_node_free(node
);
5754 if (need_feautrier_step(ctx
, graph
))
5755 return compute_schedule_wcc_feautrier(node
, graph
);
5757 if (graph
->scc
<= 1 || isl_options_get_schedule_whole_component(ctx
))
5758 return compute_schedule_wcc_whole(node
, graph
);
5760 return isl_schedule_node_compute_wcc_clustering(node
, graph
);
5763 /* Compute a schedule for each group of nodes identified by node->scc
5764 * separately and then combine them in a sequence node (or as set node
5765 * if graph->weak is set) inserted at position "node" of the schedule tree.
5766 * Return the updated schedule node.
5768 * If "wcc" is set then each of the groups belongs to a single
5769 * weakly connected component in the dependence graph so that
5770 * there is no need for compute_sub_schedule to look for weakly
5771 * connected components.
5773 * If a set node would be introduced and if the number of components
5774 * is equal to the number of nodes, then check if the schedule
5775 * is already complete. If so, a redundant set node would be introduced
5776 * (without any further descendants) stating that the statements
5777 * can be executed in arbitrary order, which is also expressed
5778 * by the absence of any node. Refrain from inserting any nodes
5779 * in this case and simply return.
5781 static __isl_give isl_schedule_node
*compute_component_schedule(
5782 __isl_take isl_schedule_node
*node
, struct isl_sched_graph
*graph
,
5787 isl_union_set_list
*filters
;
5792 if (graph
->weak
&& graph
->scc
== graph
->n
) {
5793 if (isl_sched_graph_compute_maxvar(graph
) < 0)
5794 return isl_schedule_node_free(node
);
5795 if (graph
->n_row
>= graph
->maxvar
)
5799 ctx
= isl_schedule_node_get_ctx(node
);
5800 filters
= isl_sched_graph_extract_sccs(ctx
, graph
);
5802 node
= isl_schedule_node_insert_set(node
, filters
);
5804 node
= isl_schedule_node_insert_sequence(node
, filters
);
5806 for (component
= 0; component
< graph
->scc
; ++component
) {
5807 node
= isl_schedule_node_grandchild(node
, component
, 0);
5808 node
= compute_sub_schedule(node
, ctx
, graph
,
5809 &isl_sched_node_scc_exactly
,
5810 &isl_sched_edge_scc_exactly
,
5812 node
= isl_schedule_node_grandparent(node
);
5818 /* Compute a schedule for the given dependence graph and insert it at "node".
5819 * Return the updated schedule node.
5821 * We first check if the graph is connected (through validity and conditional
5822 * validity dependences) and, if not, compute a schedule
5823 * for each component separately.
5824 * If the schedule_serialize_sccs option is set, then we check for strongly
5825 * connected components instead and compute a separate schedule for
5826 * each such strongly connected component.
5828 static __isl_give isl_schedule_node
*compute_schedule(isl_schedule_node
*node
,
5829 struct isl_sched_graph
*graph
)
5836 ctx
= isl_schedule_node_get_ctx(node
);
5837 if (isl_options_get_schedule_serialize_sccs(ctx
)) {
5838 if (detect_sccs(ctx
, graph
) < 0)
5839 return isl_schedule_node_free(node
);
5841 if (detect_wccs(ctx
, graph
) < 0)
5842 return isl_schedule_node_free(node
);
5846 return compute_component_schedule(node
, graph
, 1);
5848 return compute_schedule_wcc(node
, graph
);
5851 /* Compute a schedule on sc->domain that respects the given schedule
5854 * In particular, the schedule respects all the validity dependences.
5855 * If the default isl scheduling algorithm is used, it tries to minimize
5856 * the dependence distances over the proximity dependences.
5857 * If Feautrier's scheduling algorithm is used, the proximity dependence
5858 * distances are only minimized during the extension to a full-dimensional
5861 * If there are any condition and conditional validity dependences,
5862 * then the conditional validity dependences may be violated inside
5863 * a tilable band, provided they have no adjacent non-local
5864 * condition dependences.
5866 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
5867 __isl_take isl_schedule_constraints
*sc
)
5869 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
5870 struct isl_sched_graph graph
= { 0 };
5871 isl_schedule
*sched
;
5872 isl_schedule_node
*node
;
5873 isl_union_set
*domain
;
5876 sc
= isl_schedule_constraints_align_params(sc
);
5878 domain
= isl_schedule_constraints_get_domain(sc
);
5879 n
= isl_union_set_n_set(domain
);
5881 isl_schedule_constraints_free(sc
);
5882 return isl_schedule_from_domain(domain
);
5885 if (n
< 0 || isl_sched_graph_init(&graph
, sc
) < 0)
5886 domain
= isl_union_set_free(domain
);
5888 node
= isl_schedule_node_from_domain(domain
);
5889 node
= isl_schedule_node_child(node
, 0);
5891 node
= compute_schedule(node
, &graph
);
5892 sched
= isl_schedule_node_get_schedule(node
);
5893 isl_schedule_node_free(node
);
5895 isl_sched_graph_free(ctx
, &graph
);
5896 isl_schedule_constraints_free(sc
);
5901 /* Compute a schedule for the given union of domains that respects
5902 * all the validity dependences and minimizes
5903 * the dependence distances over the proximity dependences.
5905 * This function is kept for backward compatibility.
5907 __isl_give isl_schedule
*isl_union_set_compute_schedule(
5908 __isl_take isl_union_set
*domain
,
5909 __isl_take isl_union_map
*validity
,
5910 __isl_take isl_union_map
*proximity
)
5912 isl_schedule_constraints
*sc
;
5914 sc
= isl_schedule_constraints_on_domain(domain
);
5915 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
5916 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
5918 return isl_schedule_constraints_compute_schedule(sc
);