2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_space_private.h>
16 #include <isl_aff_private.h>
18 #include <isl/constraint.h>
19 #include <isl/schedule.h>
20 #include <isl_mat_private.h>
21 #include <isl_vec_private.h>
25 #include <isl_dim_map.h>
26 #include <isl/map_to_basic_set.h>
28 #include <isl_schedule_private.h>
29 #include <isl_band_private.h>
30 #include <isl_options_private.h>
31 #include <isl_tarjan.h>
34 * The scheduling algorithm implemented in this file was inspired by
35 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
36 * Parallelization and Locality Optimization in the Polyhedral Model".
39 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
40 __isl_keep isl_schedule_constraints
*sc
)
43 isl_schedule_constraints
*sc_copy
;
46 ctx
= isl_union_set_get_ctx(sc
->domain
);
47 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
51 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
53 return isl_schedule_constraints_free(sc_copy
);
55 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
56 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
57 if (!sc_copy
->constraint
[i
])
58 return isl_schedule_constraints_free(sc_copy
);
65 /* Construct an isl_schedule_constraints object for computing a schedule
66 * on "domain". The initial object does not impose any constraints.
68 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
69 __isl_take isl_union_set
*domain
)
73 isl_schedule_constraints
*sc
;
80 ctx
= isl_union_set_get_ctx(domain
);
81 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
85 space
= isl_union_set_get_space(domain
);
87 empty
= isl_union_map_empty(space
);
88 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
89 sc
->constraint
[i
] = isl_union_map_copy(empty
);
90 if (!sc
->constraint
[i
])
91 sc
->domain
= isl_union_set_free(sc
->domain
);
93 isl_union_map_free(empty
);
96 return isl_schedule_constraints_free(sc
);
100 isl_union_set_free(domain
);
104 /* Replace the validity constraints of "sc" by "validity".
106 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
107 __isl_take isl_schedule_constraints
*sc
,
108 __isl_take isl_union_map
*validity
)
110 if (!sc
|| !validity
)
113 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
114 sc
->constraint
[isl_edge_validity
] = validity
;
118 isl_schedule_constraints_free(sc
);
119 isl_union_map_free(validity
);
123 /* Replace the coincidence constraints of "sc" by "coincidence".
125 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
126 __isl_take isl_schedule_constraints
*sc
,
127 __isl_take isl_union_map
*coincidence
)
129 if (!sc
|| !coincidence
)
132 isl_union_map_free(sc
->constraint
[isl_edge_coincidence
]);
133 sc
->constraint
[isl_edge_coincidence
] = coincidence
;
137 isl_schedule_constraints_free(sc
);
138 isl_union_map_free(coincidence
);
142 /* Replace the proximity constraints of "sc" by "proximity".
144 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
145 __isl_take isl_schedule_constraints
*sc
,
146 __isl_take isl_union_map
*proximity
)
148 if (!sc
|| !proximity
)
151 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
152 sc
->constraint
[isl_edge_proximity
] = proximity
;
156 isl_schedule_constraints_free(sc
);
157 isl_union_map_free(proximity
);
161 /* Replace the conditional validity constraints of "sc" by "condition"
164 __isl_give isl_schedule_constraints
*
165 isl_schedule_constraints_set_conditional_validity(
166 __isl_take isl_schedule_constraints
*sc
,
167 __isl_take isl_union_map
*condition
,
168 __isl_take isl_union_map
*validity
)
170 if (!sc
|| !condition
|| !validity
)
173 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
174 sc
->constraint
[isl_edge_condition
] = condition
;
175 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
176 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
180 isl_schedule_constraints_free(sc
);
181 isl_union_map_free(condition
);
182 isl_union_map_free(validity
);
186 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
187 __isl_take isl_schedule_constraints
*sc
)
189 enum isl_edge_type i
;
194 isl_union_set_free(sc
->domain
);
195 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
196 isl_union_map_free(sc
->constraint
[i
]);
203 isl_ctx
*isl_schedule_constraints_get_ctx(
204 __isl_keep isl_schedule_constraints
*sc
)
206 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
209 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
214 fprintf(stderr
, "domain: ");
215 isl_union_set_dump(sc
->domain
);
216 fprintf(stderr
, "validity: ");
217 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
218 fprintf(stderr
, "proximity: ");
219 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
220 fprintf(stderr
, "coincidence: ");
221 isl_union_map_dump(sc
->constraint
[isl_edge_coincidence
]);
222 fprintf(stderr
, "condition: ");
223 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
224 fprintf(stderr
, "conditional_validity: ");
225 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
228 /* Align the parameters of the fields of "sc".
230 static __isl_give isl_schedule_constraints
*
231 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
234 enum isl_edge_type i
;
239 space
= isl_union_set_get_space(sc
->domain
);
240 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
241 space
= isl_space_align_params(space
,
242 isl_union_map_get_space(sc
->constraint
[i
]));
244 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
245 sc
->constraint
[i
] = isl_union_map_align_params(
246 sc
->constraint
[i
], isl_space_copy(space
));
247 if (!sc
->constraint
[i
])
248 space
= isl_space_free(space
);
250 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
252 return isl_schedule_constraints_free(sc
);
257 /* Return the total number of isl_maps in the constraints of "sc".
259 static __isl_give
int isl_schedule_constraints_n_map(
260 __isl_keep isl_schedule_constraints
*sc
)
262 enum isl_edge_type i
;
265 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
266 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
271 /* Internal information about a node that is used during the construction
273 * dim represents the space in which the domain lives
274 * sched is a matrix representation of the schedule being constructed
276 * sched_map is an isl_map representation of the same (partial) schedule
277 * sched_map may be NULL
278 * rank is the number of linearly independent rows in the linear part
280 * the columns of cmap represent a change of basis for the schedule
281 * coefficients; the first rank columns span the linear part of
283 * cinv is the inverse of cmap.
284 * start is the first variable in the LP problem in the sequences that
285 * represents the schedule coefficients of this node
286 * nvar is the dimension of the domain
287 * nparam is the number of parameters or 0 if we are not constructing
288 * a parametric schedule
290 * scc is the index of SCC (or WCC) this node belongs to
292 * band contains the band index for each of the rows of the schedule.
293 * band_id is used to differentiate between separate bands at the same
294 * level within the same parent band, i.e., bands that are separated
295 * by the parent band or bands that are independent of each other.
296 * coincident contains a boolean for each of the rows of the schedule,
297 * indicating whether the corresponding scheduling dimension satisfies
298 * the coincidence constraints in the sense that the corresponding
299 * dependence distances are zero.
301 struct isl_sched_node
{
319 static int node_has_dim(const void *entry
, const void *val
)
321 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
322 isl_space
*dim
= (isl_space
*)val
;
324 return isl_space_is_equal(node
->dim
, dim
);
327 /* An edge in the dependence graph. An edge may be used to
328 * ensure validity of the generated schedule, to minimize the dependence
331 * map is the dependence relation, with i -> j in the map if j depends on i
332 * tagged_condition and tagged_validity contain the union of all tagged
333 * condition or conditional validity dependence relations that
334 * specialize the dependence relation "map"; that is,
335 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
336 * or "tagged_validity", then i -> j is an element of "map".
337 * If these fields are NULL, then they represent the empty relation.
338 * src is the source node
339 * dst is the sink node
340 * validity is set if the edge is used to ensure correctness
341 * coincidence is used to enforce zero dependence distances
342 * proximity is set if the edge is used to minimize dependence distances
343 * condition is set if the edge represents a condition
344 * for a conditional validity schedule constraint
345 * local can only be set for condition edges and indicates that
346 * the dependence distance over the edge should be zero
347 * conditional_validity is set if the edge is used to conditionally
350 * For validity edges, start and end mark the sequence of inequality
351 * constraints in the LP problem that encode the validity constraint
352 * corresponding to this edge.
354 struct isl_sched_edge
{
356 isl_union_map
*tagged_condition
;
357 isl_union_map
*tagged_validity
;
359 struct isl_sched_node
*src
;
360 struct isl_sched_node
*dst
;
362 unsigned validity
: 1;
363 unsigned coincidence
: 1;
364 unsigned proximity
: 1;
366 unsigned condition
: 1;
367 unsigned conditional_validity
: 1;
373 /* Internal information about the dependence graph used during
374 * the construction of the schedule.
376 * intra_hmap is a cache, mapping dependence relations to their dual,
377 * for dependences from a node to itself
378 * inter_hmap is a cache, mapping dependence relations to their dual,
379 * for dependences between distinct nodes
381 * n is the number of nodes
382 * node is the list of nodes
383 * maxvar is the maximal number of variables over all nodes
384 * max_row is the allocated number of rows in the schedule
385 * n_row is the current (maximal) number of linearly independent
386 * rows in the node schedules
387 * n_total_row is the current number of rows in the node schedules
388 * n_band is the current number of completed bands
389 * band_start is the starting row in the node schedules of the current band
390 * root is set if this graph is the original dependence graph,
391 * without any splitting
393 * sorted contains a list of node indices sorted according to the
394 * SCC to which a node belongs
396 * n_edge is the number of edges
397 * edge is the list of edges
398 * max_edge contains the maximal number of edges of each type;
399 * in particular, it contains the number of edges in the inital graph.
400 * edge_table contains pointers into the edge array, hashed on the source
401 * and sink spaces; there is one such table for each type;
402 * a given edge may be referenced from more than one table
403 * if the corresponding relation appears in more than of the
404 * sets of dependences
406 * node_table contains pointers into the node array, hashed on the space
408 * region contains a list of variable sequences that should be non-trivial
410 * lp contains the (I)LP problem used to obtain new schedule rows
412 * src_scc and dst_scc are the source and sink SCCs of an edge with
413 * conflicting constraints
415 * scc represents the number of components
417 struct isl_sched_graph
{
418 isl_map_to_basic_set
*intra_hmap
;
419 isl_map_to_basic_set
*inter_hmap
;
421 struct isl_sched_node
*node
;
435 struct isl_sched_edge
*edge
;
437 int max_edge
[isl_edge_last
+ 1];
438 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
440 struct isl_hash_table
*node_table
;
441 struct isl_region
*region
;
451 /* Initialize node_table based on the list of nodes.
453 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
457 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
458 if (!graph
->node_table
)
461 for (i
= 0; i
< graph
->n
; ++i
) {
462 struct isl_hash_table_entry
*entry
;
465 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
466 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
468 graph
->node
[i
].dim
, 1);
471 entry
->data
= &graph
->node
[i
];
477 /* Return a pointer to the node that lives within the given space,
478 * or NULL if there is no such node.
480 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
481 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
483 struct isl_hash_table_entry
*entry
;
486 hash
= isl_space_get_hash(dim
);
487 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
488 &node_has_dim
, dim
, 0);
490 return entry
? entry
->data
: NULL
;
493 static int edge_has_src_and_dst(const void *entry
, const void *val
)
495 const struct isl_sched_edge
*edge
= entry
;
496 const struct isl_sched_edge
*temp
= val
;
498 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
501 /* Add the given edge to graph->edge_table[type].
503 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
504 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
506 struct isl_hash_table_entry
*entry
;
509 hash
= isl_hash_init();
510 hash
= isl_hash_builtin(hash
, edge
->src
);
511 hash
= isl_hash_builtin(hash
, edge
->dst
);
512 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
513 &edge_has_src_and_dst
, edge
, 1);
521 /* Allocate the edge_tables based on the maximal number of edges of
524 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
528 for (i
= 0; i
<= isl_edge_last
; ++i
) {
529 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
531 if (!graph
->edge_table
[i
])
538 /* If graph->edge_table[type] contains an edge from the given source
539 * to the given destination, then return the hash table entry of this edge.
540 * Otherwise, return NULL.
542 static struct isl_hash_table_entry
*graph_find_edge_entry(
543 struct isl_sched_graph
*graph
,
544 enum isl_edge_type type
,
545 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
547 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
549 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
551 hash
= isl_hash_init();
552 hash
= isl_hash_builtin(hash
, temp
.src
);
553 hash
= isl_hash_builtin(hash
, temp
.dst
);
554 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
555 &edge_has_src_and_dst
, &temp
, 0);
559 /* If graph->edge_table[type] contains an edge from the given source
560 * to the given destination, then return this edge.
561 * Otherwise, return NULL.
563 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
564 enum isl_edge_type type
,
565 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
567 struct isl_hash_table_entry
*entry
;
569 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
576 /* Check whether the dependence graph has an edge of the given type
577 * between the given two nodes.
579 static int graph_has_edge(struct isl_sched_graph
*graph
,
580 enum isl_edge_type type
,
581 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
583 struct isl_sched_edge
*edge
;
586 edge
= graph_find_edge(graph
, type
, src
, dst
);
590 empty
= isl_map_plain_is_empty(edge
->map
);
597 /* Look for any edge with the same src, dst and map fields as "model".
599 * Return the matching edge if one can be found.
600 * Return "model" if no matching edge is found.
601 * Return NULL on error.
603 static struct isl_sched_edge
*graph_find_matching_edge(
604 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
606 enum isl_edge_type i
;
607 struct isl_sched_edge
*edge
;
609 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
612 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
615 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
625 /* Remove the given edge from all the edge_tables that refer to it.
627 static void graph_remove_edge(struct isl_sched_graph
*graph
,
628 struct isl_sched_edge
*edge
)
630 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
631 enum isl_edge_type i
;
633 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
634 struct isl_hash_table_entry
*entry
;
636 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
639 if (entry
->data
!= edge
)
641 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
645 /* Check whether the dependence graph has any edge
646 * between the given two nodes.
648 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
649 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
651 enum isl_edge_type i
;
654 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
655 r
= graph_has_edge(graph
, i
, src
, dst
);
663 /* Check whether the dependence graph has a validity edge
664 * between the given two nodes.
666 * Conditional validity edges are essentially validity edges that
667 * can be ignored if the corresponding condition edges are iteration private.
668 * Here, we are only checking for the presence of validity
669 * edges, so we need to consider the conditional validity edges too.
670 * In particular, this function is used during the detection
671 * of strongly connected components and we cannot ignore
672 * conditional validity edges during this detection.
674 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
675 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
679 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
683 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
686 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
687 int n_node
, int n_edge
)
692 graph
->n_edge
= n_edge
;
693 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
694 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
695 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
696 graph
->edge
= isl_calloc_array(ctx
,
697 struct isl_sched_edge
, graph
->n_edge
);
699 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
700 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
702 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
706 for(i
= 0; i
< graph
->n
; ++i
)
707 graph
->sorted
[i
] = i
;
712 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
716 isl_map_to_basic_set_free(graph
->intra_hmap
);
717 isl_map_to_basic_set_free(graph
->inter_hmap
);
720 for (i
= 0; i
< graph
->n
; ++i
) {
721 isl_space_free(graph
->node
[i
].dim
);
722 isl_mat_free(graph
->node
[i
].sched
);
723 isl_map_free(graph
->node
[i
].sched_map
);
724 isl_mat_free(graph
->node
[i
].cmap
);
725 isl_mat_free(graph
->node
[i
].cinv
);
727 free(graph
->node
[i
].band
);
728 free(graph
->node
[i
].band_id
);
729 free(graph
->node
[i
].coincident
);
735 for (i
= 0; i
< graph
->n_edge
; ++i
) {
736 isl_map_free(graph
->edge
[i
].map
);
737 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
738 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
742 for (i
= 0; i
<= isl_edge_last
; ++i
)
743 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
744 isl_hash_table_free(ctx
, graph
->node_table
);
745 isl_basic_set_free(graph
->lp
);
748 /* For each "set" on which this function is called, increment
749 * graph->n by one and update graph->maxvar.
751 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
753 struct isl_sched_graph
*graph
= user
;
754 int nvar
= isl_set_dim(set
, isl_dim_set
);
757 if (nvar
> graph
->maxvar
)
758 graph
->maxvar
= nvar
;
765 /* Compute the number of rows that should be allocated for the schedule.
766 * The graph can be split at most "n - 1" times, there can be at most
767 * two rows for each dimension in the iteration domains (in particular,
768 * we usually have one row, but it may be split by split_scaled),
769 * and there can be one extra row for ordering the statements.
770 * Note that if we have actually split "n - 1" times, then no ordering
771 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
773 static int compute_max_row(struct isl_sched_graph
*graph
,
774 __isl_keep isl_union_set
*domain
)
778 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
780 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
785 /* Add a new node to the graph representing the given set.
787 static int extract_node(__isl_take isl_set
*set
, void *user
)
793 struct isl_sched_graph
*graph
= user
;
794 int *band
, *band_id
, *coincident
;
796 ctx
= isl_set_get_ctx(set
);
797 space
= isl_set_get_space(set
);
799 nvar
= isl_space_dim(space
, isl_dim_set
);
800 nparam
= isl_space_dim(space
, isl_dim_param
);
801 if (!ctx
->opt
->schedule_parametric
)
803 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
804 graph
->node
[graph
->n
].dim
= space
;
805 graph
->node
[graph
->n
].nvar
= nvar
;
806 graph
->node
[graph
->n
].nparam
= nparam
;
807 graph
->node
[graph
->n
].sched
= sched
;
808 graph
->node
[graph
->n
].sched_map
= NULL
;
809 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
810 graph
->node
[graph
->n
].band
= band
;
811 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
812 graph
->node
[graph
->n
].band_id
= band_id
;
813 coincident
= isl_calloc_array(ctx
, int, graph
->max_row
);
814 graph
->node
[graph
->n
].coincident
= coincident
;
817 if (!space
|| !sched
||
818 (graph
->max_row
&& (!band
|| !band_id
|| !coincident
)))
824 struct isl_extract_edge_data
{
825 enum isl_edge_type type
;
826 struct isl_sched_graph
*graph
;
829 /* Merge edge2 into edge1, freeing the contents of edge2.
830 * "type" is the type of the schedule constraint from which edge2 was
832 * Return 0 on success and -1 on failure.
834 * edge1 and edge2 are assumed to have the same value for the map field.
836 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
837 struct isl_sched_edge
*edge2
)
839 edge1
->validity
|= edge2
->validity
;
840 edge1
->coincidence
|= edge2
->coincidence
;
841 edge1
->proximity
|= edge2
->proximity
;
842 edge1
->condition
|= edge2
->condition
;
843 edge1
->conditional_validity
|= edge2
->conditional_validity
;
844 isl_map_free(edge2
->map
);
846 if (type
== isl_edge_condition
) {
847 if (!edge1
->tagged_condition
)
848 edge1
->tagged_condition
= edge2
->tagged_condition
;
850 edge1
->tagged_condition
=
851 isl_union_map_union(edge1
->tagged_condition
,
852 edge2
->tagged_condition
);
855 if (type
== isl_edge_conditional_validity
) {
856 if (!edge1
->tagged_validity
)
857 edge1
->tagged_validity
= edge2
->tagged_validity
;
859 edge1
->tagged_validity
=
860 isl_union_map_union(edge1
->tagged_validity
,
861 edge2
->tagged_validity
);
864 if (type
== isl_edge_condition
&& !edge1
->tagged_condition
)
866 if (type
== isl_edge_conditional_validity
&& !edge1
->tagged_validity
)
872 /* Insert dummy tags in domain and range of "map".
874 * In particular, if "map" is of the form
880 * [A -> dummy_tag] -> [B -> dummy_tag]
882 * where the dummy_tags are identical and equal to any dummy tags
883 * introduced by any other call to this function.
885 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
891 isl_set
*domain
, *range
;
893 ctx
= isl_map_get_ctx(map
);
895 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
896 space
= isl_space_params(isl_map_get_space(map
));
897 space
= isl_space_set_from_params(space
);
898 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
899 space
= isl_space_map_from_set(space
);
901 domain
= isl_map_wrap(map
);
902 range
= isl_map_wrap(isl_map_universe(space
));
903 map
= isl_map_from_domain_and_range(domain
, range
);
904 map
= isl_map_zip(map
);
909 /* Add a new edge to the graph based on the given map
910 * and add it to data->graph->edge_table[data->type].
911 * If a dependence relation of a given type happens to be identical
912 * to one of the dependence relations of a type that was added before,
913 * then we don't create a new edge, but instead mark the original edge
914 * as also representing a dependence of the current type.
916 * Edges of type isl_edge_condition or isl_edge_conditional_validity
917 * may be specified as "tagged" dependence relations. That is, "map"
918 * may contain elements * (i -> a) -> (j -> b), where i -> j denotes
919 * the dependence on iterations and a and b are tags.
920 * edge->map is set to the relation containing the elements i -> j,
921 * while edge->tagged_condition and edge->tagged_validity contain
922 * the union of all the "map" relations
923 * for which extract_edge is called that result in the same edge->map.
925 static int extract_edge(__isl_take isl_map
*map
, void *user
)
927 isl_ctx
*ctx
= isl_map_get_ctx(map
);
928 struct isl_extract_edge_data
*data
= user
;
929 struct isl_sched_graph
*graph
= data
->graph
;
930 struct isl_sched_node
*src
, *dst
;
932 struct isl_sched_edge
*edge
;
933 isl_map
*tagged
= NULL
;
935 if (data
->type
== isl_edge_condition
||
936 data
->type
== isl_edge_conditional_validity
) {
937 if (isl_map_can_zip(map
)) {
938 tagged
= isl_map_copy(map
);
939 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
941 tagged
= insert_dummy_tags(isl_map_copy(map
));
945 dim
= isl_space_domain(isl_map_get_space(map
));
946 src
= graph_find_node(ctx
, graph
, dim
);
948 dim
= isl_space_range(isl_map_get_space(map
));
949 dst
= graph_find_node(ctx
, graph
, dim
);
954 isl_map_free(tagged
);
958 graph
->edge
[graph
->n_edge
].src
= src
;
959 graph
->edge
[graph
->n_edge
].dst
= dst
;
960 graph
->edge
[graph
->n_edge
].map
= map
;
961 graph
->edge
[graph
->n_edge
].validity
= 0;
962 graph
->edge
[graph
->n_edge
].coincidence
= 0;
963 graph
->edge
[graph
->n_edge
].proximity
= 0;
964 graph
->edge
[graph
->n_edge
].condition
= 0;
965 graph
->edge
[graph
->n_edge
].local
= 0;
966 graph
->edge
[graph
->n_edge
].conditional_validity
= 0;
967 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
968 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
969 if (data
->type
== isl_edge_validity
)
970 graph
->edge
[graph
->n_edge
].validity
= 1;
971 if (data
->type
== isl_edge_coincidence
)
972 graph
->edge
[graph
->n_edge
].coincidence
= 1;
973 if (data
->type
== isl_edge_proximity
)
974 graph
->edge
[graph
->n_edge
].proximity
= 1;
975 if (data
->type
== isl_edge_condition
) {
976 graph
->edge
[graph
->n_edge
].condition
= 1;
977 graph
->edge
[graph
->n_edge
].tagged_condition
=
978 isl_union_map_from_map(tagged
);
980 if (data
->type
== isl_edge_conditional_validity
) {
981 graph
->edge
[graph
->n_edge
].conditional_validity
= 1;
982 graph
->edge
[graph
->n_edge
].tagged_validity
=
983 isl_union_map_from_map(tagged
);
986 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
991 if (edge
== &graph
->edge
[graph
->n_edge
])
992 return graph_edge_table_add(ctx
, graph
, data
->type
,
993 &graph
->edge
[graph
->n_edge
++]);
995 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
998 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
1001 /* Check whether there is any dependence from node[j] to node[i]
1002 * or from node[i] to node[j].
1004 static int node_follows_weak(int i
, int j
, void *user
)
1007 struct isl_sched_graph
*graph
= user
;
1009 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1012 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
1015 /* Check whether there is a (conditional) validity dependence from node[j]
1016 * to node[i], forcing node[i] to follow node[j].
1018 static int node_follows_strong(int i
, int j
, void *user
)
1020 struct isl_sched_graph
*graph
= user
;
1022 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
1025 /* Use Tarjan's algorithm for computing the strongly connected components
1026 * in the dependence graph (only validity edges).
1027 * If weak is set, we consider the graph to be undirected and
1028 * we effectively compute the (weakly) connected components.
1029 * Additionally, we also consider other edges when weak is set.
1031 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
1034 struct isl_tarjan_graph
*g
= NULL
;
1036 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
1037 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
1045 while (g
->order
[i
] != -1) {
1046 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
1054 isl_tarjan_graph_free(g
);
1059 /* Apply Tarjan's algorithm to detect the strongly connected components
1060 * in the dependence graph.
1062 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1064 return detect_ccs(ctx
, graph
, 0);
1067 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1068 * in the dependence graph.
1070 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1072 return detect_ccs(ctx
, graph
, 1);
1075 static int cmp_scc(const void *a
, const void *b
, void *data
)
1077 struct isl_sched_graph
*graph
= data
;
1081 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1084 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1086 static int sort_sccs(struct isl_sched_graph
*graph
)
1088 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1091 /* Given a dependence relation R from a node to itself,
1092 * construct the set of coefficients of valid constraints for elements
1093 * in that dependence relation.
1094 * In particular, the result contains tuples of coefficients
1095 * c_0, c_n, c_x such that
1097 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1101 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1103 * We choose here to compute the dual of delta R.
1104 * Alternatively, we could have computed the dual of R, resulting
1105 * in a set of tuples c_0, c_n, c_x, c_y, and then
1106 * plugged in (c_0, c_n, c_x, -c_x).
1108 static __isl_give isl_basic_set
*intra_coefficients(
1109 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
1112 isl_basic_set
*coef
;
1114 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1115 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1117 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
1118 coef
= isl_set_coefficients(delta
);
1119 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, map
,
1120 isl_basic_set_copy(coef
));
1125 /* Given a dependence relation R, * construct the set of coefficients
1126 * of valid constraints for elements in that dependence relation.
1127 * In particular, the result contains tuples of coefficients
1128 * c_0, c_n, c_x, c_y such that
1130 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1133 static __isl_give isl_basic_set
*inter_coefficients(
1134 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
1137 isl_basic_set
*coef
;
1139 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1140 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1142 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
1143 coef
= isl_set_coefficients(set
);
1144 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, map
,
1145 isl_basic_set_copy(coef
));
1150 /* Add constraints to graph->lp that force validity for the given
1151 * dependence from a node i to itself.
1152 * That is, add constraints that enforce
1154 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1155 * = c_i_x (y - x) >= 0
1157 * for each (x,y) in R.
1158 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1159 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1160 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1161 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1163 * Actually, we do not construct constraints for the c_i_x themselves,
1164 * but for the coefficients of c_i_x written as a linear combination
1165 * of the columns in node->cmap.
1167 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1168 struct isl_sched_edge
*edge
)
1171 isl_map
*map
= isl_map_copy(edge
->map
);
1172 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1174 isl_dim_map
*dim_map
;
1175 isl_basic_set
*coef
;
1176 struct isl_sched_node
*node
= edge
->src
;
1178 coef
= intra_coefficients(graph
, map
);
1180 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1182 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1183 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1187 total
= isl_basic_set_total_dim(graph
->lp
);
1188 dim_map
= isl_dim_map_alloc(ctx
, total
);
1189 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1190 isl_space_dim(dim
, isl_dim_set
), 1,
1192 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1193 isl_space_dim(dim
, isl_dim_set
), 1,
1195 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1196 coef
->n_eq
, coef
->n_ineq
);
1197 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1199 isl_space_free(dim
);
1203 isl_space_free(dim
);
1207 /* Add constraints to graph->lp that force validity for the given
1208 * dependence from node i to node j.
1209 * That is, add constraints that enforce
1211 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1213 * for each (x,y) in R.
1214 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1215 * of valid constraints for R and then plug in
1216 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1217 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1218 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1219 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1221 * Actually, we do not construct constraints for the c_*_x themselves,
1222 * but for the coefficients of c_*_x written as a linear combination
1223 * of the columns in node->cmap.
1225 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1226 struct isl_sched_edge
*edge
)
1229 isl_map
*map
= isl_map_copy(edge
->map
);
1230 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1232 isl_dim_map
*dim_map
;
1233 isl_basic_set
*coef
;
1234 struct isl_sched_node
*src
= edge
->src
;
1235 struct isl_sched_node
*dst
= edge
->dst
;
1237 coef
= inter_coefficients(graph
, map
);
1239 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1241 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1242 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1243 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1244 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1245 isl_mat_copy(dst
->cmap
));
1249 total
= isl_basic_set_total_dim(graph
->lp
);
1250 dim_map
= isl_dim_map_alloc(ctx
, total
);
1252 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1253 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1254 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1255 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1256 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1258 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1259 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1262 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1263 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1264 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1265 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1266 isl_space_dim(dim
, isl_dim_set
), 1,
1268 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1269 isl_space_dim(dim
, isl_dim_set
), 1,
1272 edge
->start
= graph
->lp
->n_ineq
;
1273 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1274 coef
->n_eq
, coef
->n_ineq
);
1275 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1279 isl_space_free(dim
);
1280 edge
->end
= graph
->lp
->n_ineq
;
1284 isl_space_free(dim
);
1288 /* Add constraints to graph->lp that bound the dependence distance for the given
1289 * dependence from a node i to itself.
1290 * If s = 1, we add the constraint
1292 * c_i_x (y - x) <= m_0 + m_n n
1296 * -c_i_x (y - x) + m_0 + m_n n >= 0
1298 * for each (x,y) in R.
1299 * If s = -1, we add the constraint
1301 * -c_i_x (y - x) <= m_0 + m_n n
1305 * c_i_x (y - x) + m_0 + m_n n >= 0
1307 * for each (x,y) in R.
1308 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1309 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1310 * with each coefficient (except m_0) represented as a pair of non-negative
1313 * Actually, we do not construct constraints for the c_i_x themselves,
1314 * but for the coefficients of c_i_x written as a linear combination
1315 * of the columns in node->cmap.
1318 * If "local" is set, then we add constraints
1320 * c_i_x (y - x) <= 0
1324 * -c_i_x (y - x) <= 0
1326 * instead, forcing the dependence distance to be (less than or) equal to 0.
1327 * That is, we plug in (0, 0, -s * c_i_x),
1328 * Note that dependences marked local are treated as validity constraints
1329 * by add_all_validity_constraints and therefore also have
1330 * their distances bounded by 0 from below.
1332 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1333 struct isl_sched_edge
*edge
, int s
, int local
)
1337 isl_map
*map
= isl_map_copy(edge
->map
);
1338 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1340 isl_dim_map
*dim_map
;
1341 isl_basic_set
*coef
;
1342 struct isl_sched_node
*node
= edge
->src
;
1344 coef
= intra_coefficients(graph
, map
);
1346 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1348 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1349 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1353 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
1354 total
= isl_basic_set_total_dim(graph
->lp
);
1355 dim_map
= isl_dim_map_alloc(ctx
, total
);
1358 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1359 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1360 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1362 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1363 isl_space_dim(dim
, isl_dim_set
), 1,
1365 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1366 isl_space_dim(dim
, isl_dim_set
), 1,
1368 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1369 coef
->n_eq
, coef
->n_ineq
);
1370 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1372 isl_space_free(dim
);
1376 isl_space_free(dim
);
1380 /* Add constraints to graph->lp that bound the dependence distance for the given
1381 * dependence from node i to node j.
1382 * If s = 1, we add the constraint
1384 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1389 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1392 * for each (x,y) in R.
1393 * If s = -1, we add the constraint
1395 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1400 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1403 * for each (x,y) in R.
1404 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1405 * of valid constraints for R and then plug in
1406 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1408 * with each coefficient (except m_0, c_j_0 and c_i_0)
1409 * represented as a pair of non-negative coefficients.
1411 * Actually, we do not construct constraints for the c_*_x themselves,
1412 * but for the coefficients of c_*_x written as a linear combination
1413 * of the columns in node->cmap.
1416 * If "local" is set, then we add constraints
1418 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1422 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1424 * instead, forcing the dependence distance to be (less than or) equal to 0.
1425 * That is, we plug in
1426 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1427 * Note that dependences marked local are treated as validity constraints
1428 * by add_all_validity_constraints and therefore also have
1429 * their distances bounded by 0 from below.
1431 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1432 struct isl_sched_edge
*edge
, int s
, int local
)
1436 isl_map
*map
= isl_map_copy(edge
->map
);
1437 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1439 isl_dim_map
*dim_map
;
1440 isl_basic_set
*coef
;
1441 struct isl_sched_node
*src
= edge
->src
;
1442 struct isl_sched_node
*dst
= edge
->dst
;
1444 coef
= inter_coefficients(graph
, map
);
1446 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1448 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1449 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1450 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1451 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1452 isl_mat_copy(dst
->cmap
));
1456 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1457 total
= isl_basic_set_total_dim(graph
->lp
);
1458 dim_map
= isl_dim_map_alloc(ctx
, total
);
1461 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1462 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1463 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1466 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1467 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1468 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1469 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1470 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1472 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1473 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1476 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1477 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1478 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1479 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1480 isl_space_dim(dim
, isl_dim_set
), 1,
1482 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1483 isl_space_dim(dim
, isl_dim_set
), 1,
1486 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1487 coef
->n_eq
, coef
->n_ineq
);
1488 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1490 isl_space_free(dim
);
1494 isl_space_free(dim
);
1498 /* Add all validity constraints to graph->lp.
1500 * An edge that is forced to be local needs to have its dependence
1501 * distances equal to zero. We take care of bounding them by 0 from below
1502 * here. add_all_proximity_constraints takes care of bounding them by 0
1505 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1506 * Otherwise, we ignore them.
1508 static int add_all_validity_constraints(struct isl_sched_graph
*graph
,
1509 int use_coincidence
)
1513 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1514 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1517 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1518 if (!edge
->validity
&& !local
)
1520 if (edge
->src
!= edge
->dst
)
1522 if (add_intra_validity_constraints(graph
, edge
) < 0)
1526 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1527 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1530 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1531 if (!edge
->validity
&& !local
)
1533 if (edge
->src
== edge
->dst
)
1535 if (add_inter_validity_constraints(graph
, edge
) < 0)
1542 /* Add constraints to graph->lp that bound the dependence distance
1543 * for all dependence relations.
1544 * If a given proximity dependence is identical to a validity
1545 * dependence, then the dependence distance is already bounded
1546 * from below (by zero), so we only need to bound the distance
1547 * from above. (This includes the case of "local" dependences
1548 * which are treated as validity dependence by add_all_validity_constraints.)
1549 * Otherwise, we need to bound the distance both from above and from below.
1551 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1552 * Otherwise, we ignore them.
1554 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
,
1555 int use_coincidence
)
1559 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1560 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1563 local
= edge
->local
|| (edge
->coincidence
&& use_coincidence
);
1564 if (!edge
->proximity
&& !local
)
1566 if (edge
->src
== edge
->dst
&&
1567 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
1569 if (edge
->src
!= edge
->dst
&&
1570 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
1572 if (edge
->validity
|| local
)
1574 if (edge
->src
== edge
->dst
&&
1575 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
1577 if (edge
->src
!= edge
->dst
&&
1578 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
1585 /* Compute a basis for the rows in the linear part of the schedule
1586 * and extend this basis to a full basis. The remaining rows
1587 * can then be used to force linear independence from the rows
1590 * In particular, given the schedule rows S, we compute
1595 * with H the Hermite normal form of S. That is, all but the
1596 * first rank columns of H are zero and so each row in S is
1597 * a linear combination of the first rank rows of Q.
1598 * The matrix Q is then transposed because we will write the
1599 * coefficients of the next schedule row as a column vector s
1600 * and express this s as a linear combination s = Q c of the
1602 * Similarly, the matrix U is transposed such that we can
1603 * compute the coefficients c = U s from a schedule row s.
1605 static int node_update_cmap(struct isl_sched_node
*node
)
1608 int n_row
= isl_mat_rows(node
->sched
);
1610 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1611 1 + node
->nparam
, node
->nvar
);
1613 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1614 isl_mat_free(node
->cmap
);
1615 isl_mat_free(node
->cinv
);
1616 node
->cmap
= isl_mat_transpose(Q
);
1617 node
->cinv
= isl_mat_transpose(U
);
1618 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1621 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1626 /* How many times should we count the constraints in "edge"?
1628 * If carry is set, then we are counting the number of
1629 * (validity or conditional validity) constraints that will be added
1630 * in setup_carry_lp and we count each edge exactly once.
1632 * Otherwise, we count as follows
1633 * validity -> 1 (>= 0)
1634 * validity+proximity -> 2 (>= 0 and upper bound)
1635 * proximity -> 2 (lower and upper bound)
1636 * local(+any) -> 2 (>= 0 and <= 0)
1638 * If an edge is only marked conditional_validity then it counts
1639 * as zero since it is only checked afterwards.
1641 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1642 * Otherwise, we ignore them.
1644 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
,
1645 int use_coincidence
)
1647 if (carry
&& !edge
->validity
&& !edge
->conditional_validity
)
1651 if (edge
->proximity
|| edge
->local
)
1653 if (use_coincidence
&& edge
->coincidence
)
1660 /* Count the number of equality and inequality constraints
1661 * that will be added for the given map.
1663 * "use_coincidence" is set if we should take into account coincidence edges.
1665 static int count_map_constraints(struct isl_sched_graph
*graph
,
1666 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1667 int *n_eq
, int *n_ineq
, int carry
, int use_coincidence
)
1669 isl_basic_set
*coef
;
1670 int f
= edge_multiplicity(edge
, carry
, use_coincidence
);
1677 if (edge
->src
== edge
->dst
)
1678 coef
= intra_coefficients(graph
, map
);
1680 coef
= inter_coefficients(graph
, map
);
1683 *n_eq
+= f
* coef
->n_eq
;
1684 *n_ineq
+= f
* coef
->n_ineq
;
1685 isl_basic_set_free(coef
);
1690 /* Count the number of equality and inequality constraints
1691 * that will be added to the main lp problem.
1692 * We count as follows
1693 * validity -> 1 (>= 0)
1694 * validity+proximity -> 2 (>= 0 and upper bound)
1695 * proximity -> 2 (lower and upper bound)
1696 * local(+any) -> 2 (>= 0 and <= 0)
1698 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1699 * Otherwise, we ignore them.
1701 static int count_constraints(struct isl_sched_graph
*graph
,
1702 int *n_eq
, int *n_ineq
, int use_coincidence
)
1706 *n_eq
= *n_ineq
= 0;
1707 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1708 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1709 isl_map
*map
= isl_map_copy(edge
->map
);
1711 if (count_map_constraints(graph
, edge
, map
, n_eq
, n_ineq
,
1712 0, use_coincidence
) < 0)
1719 /* Count the number of constraints that will be added by
1720 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1723 * In practice, add_bound_coefficient_constraints only adds inequalities.
1725 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1726 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1730 if (ctx
->opt
->schedule_max_coefficient
== -1)
1733 for (i
= 0; i
< graph
->n
; ++i
)
1734 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1739 /* Add constraints that bound the values of the variable and parameter
1740 * coefficients of the schedule.
1742 * The maximal value of the coefficients is defined by the option
1743 * 'schedule_max_coefficient'.
1745 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1746 struct isl_sched_graph
*graph
)
1749 int max_coefficient
;
1752 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1754 if (max_coefficient
== -1)
1757 total
= isl_basic_set_total_dim(graph
->lp
);
1759 for (i
= 0; i
< graph
->n
; ++i
) {
1760 struct isl_sched_node
*node
= &graph
->node
[i
];
1761 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1763 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1766 dim
= 1 + node
->start
+ 1 + j
;
1767 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1768 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1769 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1776 /* Construct an ILP problem for finding schedule coefficients
1777 * that result in non-negative, but small dependence distances
1778 * over all dependences.
1779 * In particular, the dependence distances over proximity edges
1780 * are bounded by m_0 + m_n n and we compute schedule coefficients
1781 * with small values (preferably zero) of m_n and m_0.
1783 * All variables of the ILP are non-negative. The actual coefficients
1784 * may be negative, so each coefficient is represented as the difference
1785 * of two non-negative variables. The negative part always appears
1786 * immediately before the positive part.
1787 * Other than that, the variables have the following order
1789 * - sum of positive and negative parts of m_n coefficients
1791 * - sum of positive and negative parts of all c_n coefficients
1792 * (unconstrained when computing non-parametric schedules)
1793 * - sum of positive and negative parts of all c_x coefficients
1794 * - positive and negative parts of m_n coefficients
1797 * - positive and negative parts of c_i_n (if parametric)
1798 * - positive and negative parts of c_i_x
1800 * The c_i_x are not represented directly, but through the columns of
1801 * node->cmap. That is, the computed values are for variable t_i_x
1802 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1804 * The constraints are those from the edges plus two or three equalities
1805 * to express the sums.
1807 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1808 * Otherwise, we ignore them.
1810 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1811 int use_coincidence
)
1821 int max_constant_term
;
1823 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1825 parametric
= ctx
->opt
->schedule_parametric
;
1826 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1828 total
= param_pos
+ 2 * nparam
;
1829 for (i
= 0; i
< graph
->n
; ++i
) {
1830 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1831 if (node_update_cmap(node
) < 0)
1833 node
->start
= total
;
1834 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1837 if (count_constraints(graph
, &n_eq
, &n_ineq
, use_coincidence
) < 0)
1839 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
1842 dim
= isl_space_set_alloc(ctx
, 0, total
);
1843 isl_basic_set_free(graph
->lp
);
1844 n_eq
+= 2 + parametric
;
1845 if (max_constant_term
!= -1)
1848 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1850 k
= isl_basic_set_alloc_equality(graph
->lp
);
1853 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1854 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1855 for (i
= 0; i
< 2 * nparam
; ++i
)
1856 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1859 k
= isl_basic_set_alloc_equality(graph
->lp
);
1862 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1863 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1864 for (i
= 0; i
< graph
->n
; ++i
) {
1865 int pos
= 1 + graph
->node
[i
].start
+ 1;
1867 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1868 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1872 k
= isl_basic_set_alloc_equality(graph
->lp
);
1875 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1876 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1877 for (i
= 0; i
< graph
->n
; ++i
) {
1878 struct isl_sched_node
*node
= &graph
->node
[i
];
1879 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1881 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1882 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1885 if (max_constant_term
!= -1)
1886 for (i
= 0; i
< graph
->n
; ++i
) {
1887 struct isl_sched_node
*node
= &graph
->node
[i
];
1888 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1891 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1892 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1893 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1896 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1898 if (add_all_validity_constraints(graph
, use_coincidence
) < 0)
1900 if (add_all_proximity_constraints(graph
, use_coincidence
) < 0)
1906 /* Analyze the conflicting constraint found by
1907 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1908 * constraint of one of the edges between distinct nodes, living, moreover
1909 * in distinct SCCs, then record the source and sink SCC as this may
1910 * be a good place to cut between SCCs.
1912 static int check_conflict(int con
, void *user
)
1915 struct isl_sched_graph
*graph
= user
;
1917 if (graph
->src_scc
>= 0)
1920 con
-= graph
->lp
->n_eq
;
1922 if (con
>= graph
->lp
->n_ineq
)
1925 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1926 if (!graph
->edge
[i
].validity
)
1928 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1930 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1932 if (graph
->edge
[i
].start
> con
)
1934 if (graph
->edge
[i
].end
<= con
)
1936 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1937 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1943 /* Check whether the next schedule row of the given node needs to be
1944 * non-trivial. Lower-dimensional domains may have some trivial rows,
1945 * but as soon as the number of remaining required non-trivial rows
1946 * is as large as the number or remaining rows to be computed,
1947 * all remaining rows need to be non-trivial.
1949 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1951 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1954 /* Solve the ILP problem constructed in setup_lp.
1955 * For each node such that all the remaining rows of its schedule
1956 * need to be non-trivial, we construct a non-triviality region.
1957 * This region imposes that the next row is independent of previous rows.
1958 * In particular the coefficients c_i_x are represented by t_i_x
1959 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1960 * its first columns span the rows of the previously computed part
1961 * of the schedule. The non-triviality region enforces that at least
1962 * one of the remaining components of t_i_x is non-zero, i.e.,
1963 * that the new schedule row depends on at least one of the remaining
1966 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1972 for (i
= 0; i
< graph
->n
; ++i
) {
1973 struct isl_sched_node
*node
= &graph
->node
[i
];
1974 int skip
= node
->rank
;
1975 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1976 if (needs_row(graph
, node
))
1977 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1979 graph
->region
[i
].len
= 0;
1981 lp
= isl_basic_set_copy(graph
->lp
);
1982 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1983 graph
->region
, &check_conflict
, graph
);
1987 /* Update the schedules of all nodes based on the given solution
1988 * of the LP problem.
1989 * The new row is added to the current band.
1990 * All possibly negative coefficients are encoded as a difference
1991 * of two non-negative variables, so we need to perform the subtraction
1992 * here. Moreover, if use_cmap is set, then the solution does
1993 * not refer to the actual coefficients c_i_x, but instead to variables
1994 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1995 * In this case, we then also need to perform this multiplication
1996 * to obtain the values of c_i_x.
1998 * If coincident is set, then the caller guarantees that the new
1999 * row satisfies the coincidence constraints.
2001 static int update_schedule(struct isl_sched_graph
*graph
,
2002 __isl_take isl_vec
*sol
, int use_cmap
, int coincident
)
2005 isl_vec
*csol
= NULL
;
2010 isl_die(sol
->ctx
, isl_error_internal
,
2011 "no solution found", goto error
);
2012 if (graph
->n_total_row
>= graph
->max_row
)
2013 isl_die(sol
->ctx
, isl_error_internal
,
2014 "too many schedule rows", goto error
);
2016 for (i
= 0; i
< graph
->n
; ++i
) {
2017 struct isl_sched_node
*node
= &graph
->node
[i
];
2018 int pos
= node
->start
;
2019 int row
= isl_mat_rows(node
->sched
);
2022 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
2026 isl_map_free(node
->sched_map
);
2027 node
->sched_map
= NULL
;
2028 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2031 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
2033 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
2034 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2035 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
2036 sol
->el
[1 + pos
+ 1 + 2 * j
]);
2037 for (j
= 0; j
< node
->nparam
; ++j
)
2038 node
->sched
= isl_mat_set_element(node
->sched
,
2039 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
2040 for (j
= 0; j
< node
->nvar
; ++j
)
2041 isl_int_set(csol
->el
[j
],
2042 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
2044 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
2048 for (j
= 0; j
< node
->nvar
; ++j
)
2049 node
->sched
= isl_mat_set_element(node
->sched
,
2050 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
2051 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2052 node
->coincident
[graph
->n_total_row
] = coincident
;
2058 graph
->n_total_row
++;
2067 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2068 * and return this isl_aff.
2070 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
2071 struct isl_sched_node
*node
, int row
)
2079 aff
= isl_aff_zero_on_domain(ls
);
2080 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2081 aff
= isl_aff_set_constant(aff
, v
);
2082 for (j
= 0; j
< node
->nparam
; ++j
) {
2083 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2084 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2086 for (j
= 0; j
< node
->nvar
; ++j
) {
2087 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2088 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2096 /* Convert node->sched into a multi_aff and return this multi_aff.
2098 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2099 struct isl_sched_node
*node
)
2103 isl_local_space
*ls
;
2108 nrow
= isl_mat_rows(node
->sched
);
2109 ncol
= isl_mat_cols(node
->sched
) - 1;
2110 space
= isl_space_from_domain(isl_space_copy(node
->dim
));
2111 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
2112 ma
= isl_multi_aff_zero(space
);
2113 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
2115 for (i
= 0; i
< nrow
; ++i
) {
2116 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2117 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
2120 isl_local_space_free(ls
);
2125 /* Convert node->sched into a map and return this map.
2127 * The result is cached in node->sched_map, which needs to be released
2128 * whenever node->sched is updated.
2130 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2132 if (!node
->sched_map
) {
2135 ma
= node_extract_schedule_multi_aff(node
);
2136 node
->sched_map
= isl_map_from_multi_aff(ma
);
2139 return isl_map_copy(node
->sched_map
);
2142 /* Construct a map that can be used to update dependence relation
2143 * based on the current schedule.
2144 * That is, construct a map expressing that source and sink
2145 * are executed within the same iteration of the current schedule.
2146 * This map can then be intersected with the dependence relation.
2147 * This is not the most efficient way, but this shouldn't be a critical
2150 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2151 struct isl_sched_node
*dst
)
2153 isl_map
*src_sched
, *dst_sched
;
2155 src_sched
= node_extract_schedule(src
);
2156 dst_sched
= node_extract_schedule(dst
);
2157 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2160 /* Intersect the domains of the nested relations in domain and range
2161 * of "umap" with "map".
2163 static __isl_give isl_union_map
*intersect_domains(
2164 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2166 isl_union_set
*uset
;
2168 umap
= isl_union_map_zip(umap
);
2169 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2170 umap
= isl_union_map_intersect_domain(umap
, uset
);
2171 umap
= isl_union_map_zip(umap
);
2175 /* Update the dependence relation of the given edge based
2176 * on the current schedule.
2177 * If the dependence is carried completely by the current schedule, then
2178 * it is removed from the edge_tables. It is kept in the list of edges
2179 * as otherwise all edge_tables would have to be recomputed.
2181 static int update_edge(struct isl_sched_graph
*graph
,
2182 struct isl_sched_edge
*edge
)
2186 id
= specializer(edge
->src
, edge
->dst
);
2187 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2191 if (edge
->tagged_condition
) {
2192 edge
->tagged_condition
=
2193 intersect_domains(edge
->tagged_condition
, id
);
2194 if (!edge
->tagged_condition
)
2197 if (edge
->tagged_validity
) {
2198 edge
->tagged_validity
=
2199 intersect_domains(edge
->tagged_validity
, id
);
2200 if (!edge
->tagged_validity
)
2205 if (isl_map_plain_is_empty(edge
->map
))
2206 graph_remove_edge(graph
, edge
);
2214 /* Update the dependence relations of all edges based on the current schedule.
2216 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2220 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2221 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2228 static void next_band(struct isl_sched_graph
*graph
)
2230 graph
->band_start
= graph
->n_total_row
;
2234 /* Topologically sort statements mapped to the same schedule iteration
2235 * and add a row to the schedule corresponding to this order.
2237 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2244 if (update_edges(ctx
, graph
) < 0)
2247 if (graph
->n_edge
== 0)
2250 if (detect_sccs(ctx
, graph
) < 0)
2253 if (graph
->n_total_row
>= graph
->max_row
)
2254 isl_die(ctx
, isl_error_internal
,
2255 "too many schedule rows", return -1);
2257 for (i
= 0; i
< graph
->n
; ++i
) {
2258 struct isl_sched_node
*node
= &graph
->node
[i
];
2259 int row
= isl_mat_rows(node
->sched
);
2260 int cols
= isl_mat_cols(node
->sched
);
2262 isl_map_free(node
->sched_map
);
2263 node
->sched_map
= NULL
;
2264 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2267 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2269 for (j
= 1; j
< cols
; ++j
)
2270 node
->sched
= isl_mat_set_element_si(node
->sched
,
2272 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2275 graph
->n_total_row
++;
2281 /* Construct an isl_schedule based on the computed schedule stored
2282 * in graph and with parameters specified by dim.
2284 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
2285 __isl_take isl_space
*dim
)
2289 isl_schedule
*sched
= NULL
;
2294 ctx
= isl_space_get_ctx(dim
);
2295 sched
= isl_calloc(ctx
, struct isl_schedule
,
2296 sizeof(struct isl_schedule
) +
2297 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
2302 sched
->n
= graph
->n
;
2303 sched
->n_band
= graph
->n_band
;
2304 sched
->n_total_row
= graph
->n_total_row
;
2306 for (i
= 0; i
< sched
->n
; ++i
) {
2308 int *band_end
, *band_id
, *coincident
;
2310 sched
->node
[i
].sched
=
2311 node_extract_schedule_multi_aff(&graph
->node
[i
]);
2312 if (!sched
->node
[i
].sched
)
2315 sched
->node
[i
].n_band
= graph
->n_band
;
2316 if (graph
->n_band
== 0)
2319 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
2320 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
2321 coincident
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
2322 sched
->node
[i
].band_end
= band_end
;
2323 sched
->node
[i
].band_id
= band_id
;
2324 sched
->node
[i
].coincident
= coincident
;
2325 if (!band_end
|| !band_id
|| !coincident
)
2328 for (r
= 0; r
< graph
->n_total_row
; ++r
)
2329 coincident
[r
] = graph
->node
[i
].coincident
[r
];
2330 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
2331 if (graph
->node
[i
].band
[r
] == b
)
2334 if (graph
->node
[i
].band
[r
] == -1)
2337 if (r
== graph
->n_total_row
)
2339 sched
->node
[i
].n_band
= b
;
2340 for (--b
; b
>= 0; --b
)
2341 band_id
[b
] = graph
->node
[i
].band_id
[b
];
2348 isl_space_free(dim
);
2349 isl_schedule_free(sched
);
2353 /* Copy nodes that satisfy node_pred from the src dependence graph
2354 * to the dst dependence graph.
2356 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2357 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2362 for (i
= 0; i
< src
->n
; ++i
) {
2363 if (!node_pred(&src
->node
[i
], data
))
2365 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
2366 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
2367 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
2368 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2369 dst
->node
[dst
->n
].sched_map
=
2370 isl_map_copy(src
->node
[i
].sched_map
);
2371 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
2372 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
2373 dst
->node
[dst
->n
].coincident
= src
->node
[i
].coincident
;
2380 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2381 * to the dst dependence graph.
2382 * If the source or destination node of the edge is not in the destination
2383 * graph, then it must be a backward proximity edge and it should simply
2386 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2387 struct isl_sched_graph
*src
,
2388 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2391 enum isl_edge_type t
;
2394 for (i
= 0; i
< src
->n_edge
; ++i
) {
2395 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2397 isl_union_map
*tagged_condition
;
2398 isl_union_map
*tagged_validity
;
2399 struct isl_sched_node
*dst_src
, *dst_dst
;
2401 if (!edge_pred(edge
, data
))
2404 if (isl_map_plain_is_empty(edge
->map
))
2407 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
2408 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
2409 if (!dst_src
|| !dst_dst
) {
2410 if (edge
->validity
|| edge
->conditional_validity
)
2411 isl_die(ctx
, isl_error_internal
,
2412 "backward (conditional) validity edge",
2417 map
= isl_map_copy(edge
->map
);
2418 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
2419 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
2421 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2422 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2423 dst
->edge
[dst
->n_edge
].map
= map
;
2424 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
2425 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
2426 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2427 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2428 dst
->edge
[dst
->n_edge
].coincidence
= edge
->coincidence
;
2429 dst
->edge
[dst
->n_edge
].condition
= edge
->condition
;
2430 dst
->edge
[dst
->n_edge
].conditional_validity
=
2431 edge
->conditional_validity
;
2434 if (edge
->tagged_condition
&& !tagged_condition
)
2436 if (edge
->tagged_validity
&& !tagged_validity
)
2439 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2441 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2443 if (graph_edge_table_add(ctx
, dst
, t
,
2444 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2452 /* Given a "src" dependence graph that contains the nodes from "dst"
2453 * that satisfy node_pred, copy the schedule computed in "src"
2454 * for those nodes back to "dst".
2456 static int copy_schedule(struct isl_sched_graph
*dst
,
2457 struct isl_sched_graph
*src
,
2458 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2463 for (i
= 0; i
< dst
->n
; ++i
) {
2464 if (!node_pred(&dst
->node
[i
], data
))
2466 isl_mat_free(dst
->node
[i
].sched
);
2467 isl_map_free(dst
->node
[i
].sched_map
);
2468 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
2469 dst
->node
[i
].sched_map
=
2470 isl_map_copy(src
->node
[src
->n
].sched_map
);
2474 dst
->max_row
= src
->max_row
;
2475 dst
->n_total_row
= src
->n_total_row
;
2476 dst
->n_band
= src
->n_band
;
2481 /* Compute the maximal number of variables over all nodes.
2482 * This is the maximal number of linearly independent schedule
2483 * rows that we need to compute.
2484 * Just in case we end up in a part of the dependence graph
2485 * with only lower-dimensional domains, we make sure we will
2486 * compute the required amount of extra linearly independent rows.
2488 static int compute_maxvar(struct isl_sched_graph
*graph
)
2493 for (i
= 0; i
< graph
->n
; ++i
) {
2494 struct isl_sched_node
*node
= &graph
->node
[i
];
2497 if (node_update_cmap(node
) < 0)
2499 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2500 if (nvar
> graph
->maxvar
)
2501 graph
->maxvar
= nvar
;
2507 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2508 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2510 /* Compute a schedule for a subgraph of "graph". In particular, for
2511 * the graph composed of nodes that satisfy node_pred and edges that
2512 * that satisfy edge_pred. The caller should precompute the number
2513 * of nodes and edges that satisfy these predicates and pass them along
2514 * as "n" and "n_edge".
2515 * If the subgraph is known to consist of a single component, then wcc should
2516 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2517 * Otherwise, we call compute_schedule, which will check whether the subgraph
2520 static int compute_sub_schedule(isl_ctx
*ctx
,
2521 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2522 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2523 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2526 struct isl_sched_graph split
= { 0 };
2529 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2531 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2533 if (graph_init_table(ctx
, &split
) < 0)
2535 for (t
= 0; t
<= isl_edge_last
; ++t
)
2536 split
.max_edge
[t
] = graph
->max_edge
[t
];
2537 if (graph_init_edge_tables(ctx
, &split
) < 0)
2539 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2541 split
.n_row
= graph
->n_row
;
2542 split
.max_row
= graph
->max_row
;
2543 split
.n_total_row
= graph
->n_total_row
;
2544 split
.n_band
= graph
->n_band
;
2545 split
.band_start
= graph
->band_start
;
2547 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2549 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2552 copy_schedule(graph
, &split
, node_pred
, data
);
2554 graph_free(ctx
, &split
);
2557 graph_free(ctx
, &split
);
2561 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2563 return node
->scc
== scc
;
2566 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2568 return node
->scc
<= scc
;
2571 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2573 return node
->scc
>= scc
;
2576 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2578 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2581 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2583 return edge
->dst
->scc
<= scc
;
2586 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2588 return edge
->src
->scc
>= scc
;
2591 /* Pad the schedules of all nodes with zero rows such that in the end
2592 * they all have graph->n_total_row rows.
2593 * The extra rows don't belong to any band, so they get assigned band number -1.
2595 static int pad_schedule(struct isl_sched_graph
*graph
)
2599 for (i
= 0; i
< graph
->n
; ++i
) {
2600 struct isl_sched_node
*node
= &graph
->node
[i
];
2601 int row
= isl_mat_rows(node
->sched
);
2602 if (graph
->n_total_row
> row
) {
2603 isl_map_free(node
->sched_map
);
2604 node
->sched_map
= NULL
;
2606 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2607 graph
->n_total_row
- row
);
2610 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2617 /* Reset the current band by dropping all its schedule rows.
2619 static int reset_band(struct isl_sched_graph
*graph
)
2624 drop
= graph
->n_total_row
- graph
->band_start
;
2625 graph
->n_total_row
-= drop
;
2626 graph
->n_row
-= drop
;
2628 for (i
= 0; i
< graph
->n
; ++i
) {
2629 struct isl_sched_node
*node
= &graph
->node
[i
];
2631 isl_map_free(node
->sched_map
);
2632 node
->sched_map
= NULL
;
2634 node
->sched
= isl_mat_drop_rows(node
->sched
,
2635 graph
->band_start
, drop
);
2644 /* Split the current graph into two parts and compute a schedule for each
2645 * part individually. In particular, one part consists of all SCCs up
2646 * to and including graph->src_scc, while the other part contains the other
2649 * The split is enforced in the schedule by constant rows with two different
2650 * values (0 and 1). These constant rows replace the previously computed rows
2651 * in the current band.
2652 * It would be possible to reuse them as the first rows in the next
2653 * band, but recomputing them may result in better rows as we are looking
2654 * at a smaller part of the dependence graph.
2656 * Since we do not enforce coincidence, we conservatively mark the
2657 * splitting row as not coincident.
2659 * The band_id of the second group is set to n, where n is the number
2660 * of nodes in the first group. This ensures that the band_ids over
2661 * the two groups remain disjoint, even if either or both of the two
2662 * groups contain independent components.
2664 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2666 int i
, j
, n
, e1
, e2
;
2667 int n_total_row
, orig_total_row
;
2668 int n_band
, orig_band
;
2670 if (graph
->n_total_row
>= graph
->max_row
)
2671 isl_die(ctx
, isl_error_internal
,
2672 "too many schedule rows", return -1);
2674 if (reset_band(graph
) < 0)
2678 for (i
= 0; i
< graph
->n
; ++i
) {
2679 struct isl_sched_node
*node
= &graph
->node
[i
];
2680 int row
= isl_mat_rows(node
->sched
);
2681 int cols
= isl_mat_cols(node
->sched
);
2682 int before
= node
->scc
<= graph
->src_scc
;
2687 isl_map_free(node
->sched_map
);
2688 node
->sched_map
= NULL
;
2689 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2692 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2694 for (j
= 1; j
< cols
; ++j
)
2695 node
->sched
= isl_mat_set_element_si(node
->sched
,
2697 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2698 node
->coincident
[graph
->n_total_row
] = 0;
2702 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2703 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2705 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2709 graph
->n_total_row
++;
2712 for (i
= 0; i
< graph
->n
; ++i
) {
2713 struct isl_sched_node
*node
= &graph
->node
[i
];
2714 if (node
->scc
> graph
->src_scc
)
2715 node
->band_id
[graph
->n_band
] = n
;
2718 orig_total_row
= graph
->n_total_row
;
2719 orig_band
= graph
->n_band
;
2720 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2721 &node_scc_at_most
, &edge_dst_scc_at_most
,
2722 graph
->src_scc
, 0) < 0)
2724 n_total_row
= graph
->n_total_row
;
2725 graph
->n_total_row
= orig_total_row
;
2726 n_band
= graph
->n_band
;
2727 graph
->n_band
= orig_band
;
2728 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2729 &node_scc_at_least
, &edge_src_scc_at_least
,
2730 graph
->src_scc
+ 1, 0) < 0)
2732 if (n_total_row
> graph
->n_total_row
)
2733 graph
->n_total_row
= n_total_row
;
2734 if (n_band
> graph
->n_band
)
2735 graph
->n_band
= n_band
;
2737 return pad_schedule(graph
);
2740 /* Compute the next band of the schedule after updating the dependence
2741 * relations based on the the current schedule.
2743 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2745 if (update_edges(ctx
, graph
) < 0)
2749 return compute_schedule(ctx
, graph
);
2752 /* Add constraints to graph->lp that force the dependence "map" (which
2753 * is part of the dependence relation of "edge")
2754 * to be respected and attempt to carry it, where the edge is one from
2755 * a node j to itself. "pos" is the sequence number of the given map.
2756 * That is, add constraints that enforce
2758 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2759 * = c_j_x (y - x) >= e_i
2761 * for each (x,y) in R.
2762 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2763 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2764 * with each coefficient in c_j_x represented as a pair of non-negative
2767 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2768 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2771 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2773 isl_dim_map
*dim_map
;
2774 isl_basic_set
*coef
;
2775 struct isl_sched_node
*node
= edge
->src
;
2777 coef
= intra_coefficients(graph
, map
);
2781 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2783 total
= isl_basic_set_total_dim(graph
->lp
);
2784 dim_map
= isl_dim_map_alloc(ctx
, total
);
2785 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2786 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2787 isl_space_dim(dim
, isl_dim_set
), 1,
2789 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2790 isl_space_dim(dim
, isl_dim_set
), 1,
2792 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2793 coef
->n_eq
, coef
->n_ineq
);
2794 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2796 isl_space_free(dim
);
2801 /* Add constraints to graph->lp that force the dependence "map" (which
2802 * is part of the dependence relation of "edge")
2803 * to be respected and attempt to carry it, where the edge is one from
2804 * node j to node k. "pos" is the sequence number of the given map.
2805 * That is, add constraints that enforce
2807 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2809 * for each (x,y) in R.
2810 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2811 * of valid constraints for R and then plug in
2812 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2813 * with each coefficient (except e_i, c_k_0 and c_j_0)
2814 * represented as a pair of non-negative coefficients.
2816 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2817 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2820 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2822 isl_dim_map
*dim_map
;
2823 isl_basic_set
*coef
;
2824 struct isl_sched_node
*src
= edge
->src
;
2825 struct isl_sched_node
*dst
= edge
->dst
;
2827 coef
= inter_coefficients(graph
, map
);
2831 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2833 total
= isl_basic_set_total_dim(graph
->lp
);
2834 dim_map
= isl_dim_map_alloc(ctx
, total
);
2836 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2838 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2839 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2840 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2841 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2842 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2844 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2845 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2848 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2849 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2850 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2851 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2852 isl_space_dim(dim
, isl_dim_set
), 1,
2854 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2855 isl_space_dim(dim
, isl_dim_set
), 1,
2858 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2859 coef
->n_eq
, coef
->n_ineq
);
2860 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2862 isl_space_free(dim
);
2867 /* Add constraints to graph->lp that force all (conditional) validity
2868 * dependences to be respected and attempt to carry them.
2870 static int add_all_constraints(struct isl_sched_graph
*graph
)
2876 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2877 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2879 if (!edge
->validity
&& !edge
->conditional_validity
)
2882 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2883 isl_basic_map
*bmap
;
2886 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2887 map
= isl_map_from_basic_map(bmap
);
2889 if (edge
->src
== edge
->dst
&&
2890 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2892 if (edge
->src
!= edge
->dst
&&
2893 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2902 /* Count the number of equality and inequality constraints
2903 * that will be added to the carry_lp problem.
2904 * We count each edge exactly once.
2906 static int count_all_constraints(struct isl_sched_graph
*graph
,
2907 int *n_eq
, int *n_ineq
)
2911 *n_eq
= *n_ineq
= 0;
2912 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2913 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2914 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2915 isl_basic_map
*bmap
;
2918 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2919 map
= isl_map_from_basic_map(bmap
);
2921 if (count_map_constraints(graph
, edge
, map
,
2922 n_eq
, n_ineq
, 1, 0) < 0)
2930 /* Construct an LP problem for finding schedule coefficients
2931 * such that the schedule carries as many dependences as possible.
2932 * In particular, for each dependence i, we bound the dependence distance
2933 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2934 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2935 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2936 * Note that if the dependence relation is a union of basic maps,
2937 * then we have to consider each basic map individually as it may only
2938 * be possible to carry the dependences expressed by some of those
2939 * basic maps and not all off them.
2940 * Below, we consider each of those basic maps as a separate "edge".
2942 * All variables of the LP are non-negative. The actual coefficients
2943 * may be negative, so each coefficient is represented as the difference
2944 * of two non-negative variables. The negative part always appears
2945 * immediately before the positive part.
2946 * Other than that, the variables have the following order
2948 * - sum of (1 - e_i) over all edges
2949 * - sum of positive and negative parts of all c_n coefficients
2950 * (unconstrained when computing non-parametric schedules)
2951 * - sum of positive and negative parts of all c_x coefficients
2956 * - positive and negative parts of c_i_n (if parametric)
2957 * - positive and negative parts of c_i_x
2959 * The constraints are those from the (validity) edges plus three equalities
2960 * to express the sums and n_edge inequalities to express e_i <= 1.
2962 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2972 for (i
= 0; i
< graph
->n_edge
; ++i
)
2973 n_edge
+= graph
->edge
[i
].map
->n
;
2976 for (i
= 0; i
< graph
->n
; ++i
) {
2977 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2978 node
->start
= total
;
2979 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2982 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2984 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2987 dim
= isl_space_set_alloc(ctx
, 0, total
);
2988 isl_basic_set_free(graph
->lp
);
2991 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2992 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2994 k
= isl_basic_set_alloc_equality(graph
->lp
);
2997 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2998 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2999 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
3000 for (i
= 0; i
< n_edge
; ++i
)
3001 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
3003 k
= isl_basic_set_alloc_equality(graph
->lp
);
3006 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3007 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
3008 for (i
= 0; i
< graph
->n
; ++i
) {
3009 int pos
= 1 + graph
->node
[i
].start
+ 1;
3011 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
3012 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3015 k
= isl_basic_set_alloc_equality(graph
->lp
);
3018 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
3019 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
3020 for (i
= 0; i
< graph
->n
; ++i
) {
3021 struct isl_sched_node
*node
= &graph
->node
[i
];
3022 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3024 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
3025 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
3028 for (i
= 0; i
< n_edge
; ++i
) {
3029 k
= isl_basic_set_alloc_inequality(graph
->lp
);
3032 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
3033 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
3034 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
3037 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
3039 if (add_all_constraints(graph
) < 0)
3045 /* If the schedule_split_scaled option is set and if the linear
3046 * parts of the scheduling rows for all nodes in the graphs have
3047 * non-trivial common divisor, then split off the constant term
3048 * from the linear part.
3049 * The constant term is then placed in a separate band and
3050 * the linear part is reduced.
3052 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3058 if (!ctx
->opt
->schedule_split_scaled
)
3063 if (graph
->n_total_row
>= graph
->max_row
)
3064 isl_die(ctx
, isl_error_internal
,
3065 "too many schedule rows", return -1);
3068 isl_int_init(gcd_i
);
3070 isl_int_set_si(gcd
, 0);
3072 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
3074 for (i
= 0; i
< graph
->n
; ++i
) {
3075 struct isl_sched_node
*node
= &graph
->node
[i
];
3076 int cols
= isl_mat_cols(node
->sched
);
3078 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3079 isl_int_gcd(gcd
, gcd
, gcd_i
);
3082 isl_int_clear(gcd_i
);
3084 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3091 for (i
= 0; i
< graph
->n
; ++i
) {
3092 struct isl_sched_node
*node
= &graph
->node
[i
];
3094 isl_map_free(node
->sched_map
);
3095 node
->sched_map
= NULL
;
3096 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3099 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
3100 node
->sched
->row
[row
][0], gcd
);
3101 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3102 node
->sched
->row
[row
][0], gcd
);
3103 isl_int_mul(node
->sched
->row
[row
][0],
3104 node
->sched
->row
[row
][0], gcd
);
3105 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3108 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3111 graph
->n_total_row
++;
3120 static int compute_component_schedule(isl_ctx
*ctx
,
3121 struct isl_sched_graph
*graph
);
3123 /* Is the schedule row "sol" trivial on node "node"?
3124 * That is, is the solution zero on the dimensions orthogonal to
3125 * the previously found solutions?
3126 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3128 * Each coefficient is represented as the difference between
3129 * two non-negative values in "sol". "sol" has been computed
3130 * in terms of the original iterators (i.e., without use of cmap).
3131 * We construct the schedule row s and write it as a linear
3132 * combination of (linear combinations of) previously computed schedule rows.
3133 * s = Q c or c = U s.
3134 * If the final entries of c are all zero, then the solution is trivial.
3136 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3146 if (node
->nvar
== node
->rank
)
3149 ctx
= isl_vec_get_ctx(sol
);
3150 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3154 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3156 for (i
= 0; i
< node
->nvar
; ++i
)
3157 isl_int_sub(node_sol
->el
[i
],
3158 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3160 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3165 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3166 node
->nvar
- node
->rank
) == -1;
3168 isl_vec_free(node_sol
);
3173 /* Is the schedule row "sol" trivial on any node where it should
3175 * "sol" has been computed in terms of the original iterators
3176 * (i.e., without use of cmap).
3177 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3179 static int is_any_trivial(struct isl_sched_graph
*graph
,
3180 __isl_keep isl_vec
*sol
)
3184 for (i
= 0; i
< graph
->n
; ++i
) {
3185 struct isl_sched_node
*node
= &graph
->node
[i
];
3188 if (!needs_row(graph
, node
))
3190 trivial
= is_trivial(node
, sol
);
3191 if (trivial
< 0 || trivial
)
3198 /* Construct a schedule row for each node such that as many dependences
3199 * as possible are carried and then continue with the next band.
3201 * If the computed schedule row turns out to be trivial on one or
3202 * more nodes where it should not be trivial, then we throw it away
3203 * and try again on each component separately.
3205 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3214 for (i
= 0; i
< graph
->n_edge
; ++i
)
3215 n_edge
+= graph
->edge
[i
].map
->n
;
3217 if (setup_carry_lp(ctx
, graph
) < 0)
3220 lp
= isl_basic_set_copy(graph
->lp
);
3221 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3225 if (sol
->size
== 0) {
3227 isl_die(ctx
, isl_error_internal
,
3228 "error in schedule construction", return -1);
3231 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3232 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3234 isl_die(ctx
, isl_error_unknown
,
3235 "unable to carry dependences", return -1);
3238 trivial
= is_any_trivial(graph
, sol
);
3240 sol
= isl_vec_free(sol
);
3241 } else if (trivial
) {
3244 return compute_component_schedule(ctx
, graph
);
3245 isl_die(ctx
, isl_error_unknown
,
3246 "unable to construct non-trivial solution", return -1);
3249 if (update_schedule(graph
, sol
, 0, 0) < 0)
3252 if (split_scaled(ctx
, graph
) < 0)
3255 return compute_next_band(ctx
, graph
);
3258 /* Are there any (non-empty) (conditional) validity edges in the graph?
3260 static int has_validity_edges(struct isl_sched_graph
*graph
)
3264 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3267 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3272 if (graph
->edge
[i
].validity
||
3273 graph
->edge
[i
].conditional_validity
)
3280 /* Should we apply a Feautrier step?
3281 * That is, did the user request the Feautrier algorithm and are
3282 * there any validity dependences (left)?
3284 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3286 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3289 return has_validity_edges(graph
);
3292 /* Compute a schedule for a connected dependence graph using Feautrier's
3293 * multi-dimensional scheduling algorithm.
3294 * The original algorithm is described in [1].
3295 * The main idea is to minimize the number of scheduling dimensions, by
3296 * trying to satisfy as many dependences as possible per scheduling dimension.
3298 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3299 * Problem, Part II: Multi-Dimensional Time.
3300 * In Intl. Journal of Parallel Programming, 1992.
3302 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
3303 struct isl_sched_graph
*graph
)
3305 return carry_dependences(ctx
, graph
);
3308 /* Turn off the "local" bit on all (condition) edges.
3310 static void clear_local_edges(struct isl_sched_graph
*graph
)
3314 for (i
= 0; i
< graph
->n_edge
; ++i
)
3315 if (graph
->edge
[i
].condition
)
3316 graph
->edge
[i
].local
= 0;
3319 /* Does "graph" have both condition and conditional validity edges?
3321 static int need_condition_check(struct isl_sched_graph
*graph
)
3324 int any_condition
= 0;
3325 int any_conditional_validity
= 0;
3327 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3328 if (graph
->edge
[i
].condition
)
3330 if (graph
->edge
[i
].conditional_validity
)
3331 any_conditional_validity
= 1;
3334 return any_condition
&& any_conditional_validity
;
3337 /* Does "graph" contain any coincidence edge?
3339 static int has_any_coincidence(struct isl_sched_graph
*graph
)
3343 for (i
= 0; i
< graph
->n_edge
; ++i
)
3344 if (graph
->edge
[i
].coincidence
)
3350 /* Extract the final schedule row as a map with the iteration domain
3351 * of "node" as domain.
3353 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
3355 isl_local_space
*ls
;
3359 row
= isl_mat_rows(node
->sched
) - 1;
3360 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
3361 aff
= extract_schedule_row(ls
, node
, row
);
3362 return isl_map_from_aff(aff
);
3365 /* Is the conditional validity dependence in the edge with index "edge_index"
3366 * violated by the latest (i.e., final) row of the schedule?
3367 * That is, is i scheduled after j
3368 * for any conditional validity dependence i -> j?
3370 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
3372 isl_map
*src_sched
, *dst_sched
, *map
;
3373 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
3376 src_sched
= final_row(edge
->src
);
3377 dst_sched
= final_row(edge
->dst
);
3378 map
= isl_map_copy(edge
->map
);
3379 map
= isl_map_apply_domain(map
, src_sched
);
3380 map
= isl_map_apply_range(map
, dst_sched
);
3381 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
3382 empty
= isl_map_is_empty(map
);
3391 /* Does the domain of "umap" intersect "uset"?
3393 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3394 __isl_keep isl_union_set
*uset
)
3398 umap
= isl_union_map_copy(umap
);
3399 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3400 empty
= isl_union_map_is_empty(umap
);
3401 isl_union_map_free(umap
);
3403 return empty
< 0 ? -1 : !empty
;
3406 /* Does the range of "umap" intersect "uset"?
3408 static int range_intersects(__isl_keep isl_union_map
*umap
,
3409 __isl_keep isl_union_set
*uset
)
3413 umap
= isl_union_map_copy(umap
);
3414 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3415 empty
= isl_union_map_is_empty(umap
);
3416 isl_union_map_free(umap
);
3418 return empty
< 0 ? -1 : !empty
;
3421 /* Are the condition dependences of "edge" local with respect to
3422 * the current schedule?
3424 * That is, are domain and range of the condition dependences mapped
3425 * to the same point?
3427 * In other words, is the condition false?
3429 static int is_condition_false(struct isl_sched_edge
*edge
)
3431 isl_union_map
*umap
;
3432 isl_map
*map
, *sched
, *test
;
3435 umap
= isl_union_map_copy(edge
->tagged_condition
);
3436 umap
= isl_union_map_zip(umap
);
3437 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3438 map
= isl_map_from_union_map(umap
);
3440 sched
= node_extract_schedule(edge
->src
);
3441 map
= isl_map_apply_domain(map
, sched
);
3442 sched
= node_extract_schedule(edge
->dst
);
3443 map
= isl_map_apply_range(map
, sched
);
3445 test
= isl_map_identity(isl_map_get_space(map
));
3446 local
= isl_map_is_subset(map
, test
);
3453 /* Does "graph" have any satisfied condition edges that
3454 * are adjacent to the conditional validity constraint with
3455 * domain "conditional_source" and range "conditional_sink"?
3457 * A satisfied condition is one that is not local.
3458 * If a condition was forced to be local already (i.e., marked as local)
3459 * then there is no need to check if it is in fact local.
3461 * Additionally, mark all adjacent condition edges found as local.
3463 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
3464 __isl_keep isl_union_set
*conditional_source
,
3465 __isl_keep isl_union_set
*conditional_sink
)
3470 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3471 int adjacent
, local
;
3472 isl_union_map
*condition
;
3474 if (!graph
->edge
[i
].condition
)
3476 if (graph
->edge
[i
].local
)
3479 condition
= graph
->edge
[i
].tagged_condition
;
3480 adjacent
= domain_intersects(condition
, conditional_sink
);
3481 if (adjacent
>= 0 && !adjacent
)
3482 adjacent
= range_intersects(condition
,
3483 conditional_source
);
3489 graph
->edge
[i
].local
= 1;
3491 local
= is_condition_false(&graph
->edge
[i
]);
3501 /* Are there any violated conditional validity dependences with
3502 * adjacent condition dependences that are not local with respect
3503 * to the current schedule?
3504 * That is, is the conditional validity constraint violated?
3506 * Additionally, mark all those adjacent condition dependences as local.
3507 * We also mark those adjacent condition dependences that were not marked
3508 * as local before, but just happened to be local already. This ensures
3509 * that they remain local if the schedule is recomputed.
3511 * We first collect domain and range of all violated conditional validity
3512 * dependences and then check if there are any adjacent non-local
3513 * condition dependences.
3515 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
3516 struct isl_sched_graph
*graph
)
3520 isl_union_set
*source
, *sink
;
3522 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3523 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3524 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3525 isl_union_set
*uset
;
3526 isl_union_map
*umap
;
3529 if (!graph
->edge
[i
].conditional_validity
)
3532 violated
= is_violated(graph
, i
);
3540 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3541 uset
= isl_union_map_domain(umap
);
3542 source
= isl_union_set_union(source
, uset
);
3543 source
= isl_union_set_coalesce(source
);
3545 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3546 uset
= isl_union_map_range(umap
);
3547 sink
= isl_union_set_union(sink
, uset
);
3548 sink
= isl_union_set_coalesce(sink
);
3552 any
= has_adjacent_true_conditions(graph
, source
, sink
);
3554 isl_union_set_free(source
);
3555 isl_union_set_free(sink
);
3558 isl_union_set_free(source
);
3559 isl_union_set_free(sink
);
3563 /* Compute a schedule for a connected dependence graph.
3564 * We try to find a sequence of as many schedule rows as possible that result
3565 * in non-negative dependence distances (independent of the previous rows
3566 * in the sequence, i.e., such that the sequence is tilable), with as
3567 * many of the initial rows as possible satisfying the coincidence constraints.
3568 * If we can't find any more rows we either
3569 * - split between SCCs and start over (assuming we found an interesting
3570 * pair of SCCs between which to split)
3571 * - continue with the next band (assuming the current band has at least
3573 * - try to carry as many dependences as possible and continue with the next
3576 * If Feautrier's algorithm is selected, we first recursively try to satisfy
3577 * as many validity dependences as possible. When all validity dependences
3578 * are satisfied we extend the schedule to a full-dimensional schedule.
3580 * If we manage to complete the schedule, we finish off by topologically
3581 * sorting the statements based on the remaining dependences.
3583 * If ctx->opt->schedule_outer_coincidence is set, then we force the
3584 * outermost dimension to satisfy the coincidence constraints. If this
3585 * turns out to be impossible, we fall back on the general scheme above
3586 * and try to carry as many dependences as possible.
3588 * If "graph" contains both condition and conditional validity dependences,
3589 * then we need to check that that the conditional schedule constraint
3590 * is satisfied, i.e., there are no violated conditional validity dependences
3591 * that are adjacent to any non-local condition dependences.
3592 * If there are, then we mark all those adjacent condition dependences
3593 * as local and recompute the current band. Those dependences that
3594 * are marked local will then be forced to be local.
3595 * The initial computation is performed with no dependences marked as local.
3596 * If we are lucky, then there will be no violated conditional validity
3597 * dependences adjacent to any non-local condition dependences.
3598 * Otherwise, we mark some additional condition dependences as local and
3599 * recompute. We continue this process until there are no violations left or
3600 * until we are no longer able to compute a schedule.
3601 * Since there are only a finite number of dependences,
3602 * there will only be a finite number of iterations.
3604 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3606 int has_coincidence
;
3607 int use_coincidence
;
3608 int force_coincidence
= 0;
3609 int check_conditional
;
3611 if (detect_sccs(ctx
, graph
) < 0)
3613 if (sort_sccs(graph
) < 0)
3616 if (compute_maxvar(graph
) < 0)
3619 if (need_feautrier_step(ctx
, graph
))
3620 return compute_schedule_wcc_feautrier(ctx
, graph
);
3622 clear_local_edges(graph
);
3623 check_conditional
= need_condition_check(graph
);
3624 has_coincidence
= has_any_coincidence(graph
);
3626 if (ctx
->opt
->schedule_outer_coincidence
)
3627 force_coincidence
= 1;
3629 use_coincidence
= has_coincidence
;
3630 while (graph
->n_row
< graph
->maxvar
) {
3635 graph
->src_scc
= -1;
3636 graph
->dst_scc
= -1;
3638 if (setup_lp(ctx
, graph
, use_coincidence
) < 0)
3640 sol
= solve_lp(graph
);
3643 if (sol
->size
== 0) {
3644 int empty
= graph
->n_total_row
== graph
->band_start
;
3647 if (use_coincidence
&& (!force_coincidence
|| !empty
)) {
3648 use_coincidence
= 0;
3651 if (!ctx
->opt
->schedule_maximize_band_depth
&& !empty
)
3652 return compute_next_band(ctx
, graph
);
3653 if (graph
->src_scc
>= 0)
3654 return compute_split_schedule(ctx
, graph
);
3656 return compute_next_band(ctx
, graph
);
3657 return carry_dependences(ctx
, graph
);
3659 coincident
= !has_coincidence
|| use_coincidence
;
3660 if (update_schedule(graph
, sol
, 1, coincident
) < 0)
3663 if (!check_conditional
)
3665 violated
= has_violated_conditional_constraint(ctx
, graph
);
3670 if (reset_band(graph
) < 0)
3672 use_coincidence
= has_coincidence
;
3675 if (graph
->n_total_row
> graph
->band_start
)
3677 return sort_statements(ctx
, graph
);
3680 /* Add a row to the schedules that separates the SCCs and move
3683 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3687 if (graph
->n_total_row
>= graph
->max_row
)
3688 isl_die(ctx
, isl_error_internal
,
3689 "too many schedule rows", return -1);
3691 for (i
= 0; i
< graph
->n
; ++i
) {
3692 struct isl_sched_node
*node
= &graph
->node
[i
];
3693 int row
= isl_mat_rows(node
->sched
);
3695 isl_map_free(node
->sched_map
);
3696 node
->sched_map
= NULL
;
3697 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3698 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
3702 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3705 graph
->n_total_row
++;
3711 /* Compute a schedule for each component (identified by node->scc)
3712 * of the dependence graph separately and then combine the results.
3713 * Depending on the setting of schedule_fuse, a component may be
3714 * either weakly or strongly connected.
3716 * The band_id is adjusted such that each component has a separate id.
3717 * Note that the band_id may have already been set to a value different
3718 * from zero by compute_split_schedule.
3720 static int compute_component_schedule(isl_ctx
*ctx
,
3721 struct isl_sched_graph
*graph
)
3725 int n_total_row
, orig_total_row
;
3726 int n_band
, orig_band
;
3728 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
3729 ctx
->opt
->schedule_separate_components
)
3730 if (split_on_scc(ctx
, graph
) < 0)
3734 orig_total_row
= graph
->n_total_row
;
3736 orig_band
= graph
->n_band
;
3737 for (i
= 0; i
< graph
->n
; ++i
)
3738 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
3739 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
3741 for (i
= 0; i
< graph
->n
; ++i
)
3742 if (graph
->node
[i
].scc
== wcc
)
3745 for (i
= 0; i
< graph
->n_edge
; ++i
)
3746 if (graph
->edge
[i
].src
->scc
== wcc
&&
3747 graph
->edge
[i
].dst
->scc
== wcc
)
3750 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
3752 &edge_scc_exactly
, wcc
, 1) < 0)
3754 if (graph
->n_total_row
> n_total_row
)
3755 n_total_row
= graph
->n_total_row
;
3756 graph
->n_total_row
= orig_total_row
;
3757 if (graph
->n_band
> n_band
)
3758 n_band
= graph
->n_band
;
3759 graph
->n_band
= orig_band
;
3762 graph
->n_total_row
= n_total_row
;
3763 graph
->n_band
= n_band
;
3765 return pad_schedule(graph
);
3768 /* Compute a schedule for the given dependence graph.
3769 * We first check if the graph is connected (through validity and conditional
3770 * validity dependences) and, if not, compute a schedule
3771 * for each component separately.
3772 * If schedule_fuse is set to minimal fusion, then we check for strongly
3773 * connected components instead and compute a separate schedule for
3774 * each such strongly connected component.
3776 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3778 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
3779 if (detect_sccs(ctx
, graph
) < 0)
3782 if (detect_wccs(ctx
, graph
) < 0)
3787 return compute_component_schedule(ctx
, graph
);
3789 return compute_schedule_wcc(ctx
, graph
);
3792 /* Compute a schedule on sc->domain that respects the given schedule
3795 * In particular, the schedule respects all the validity dependences.
3796 * If the default isl scheduling algorithm is used, it tries to minimize
3797 * the dependence distances over the proximity dependences.
3798 * If Feautrier's scheduling algorithm is used, the proximity dependence
3799 * distances are only minimized during the extension to a full-dimensional
3802 * If there are any condition and conditional validity dependences,
3803 * then the conditional validity dependences may be violated inside
3804 * a tilable band, provided they have no adjacent non-local
3805 * condition dependences.
3807 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
3808 __isl_take isl_schedule_constraints
*sc
)
3810 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
3811 struct isl_sched_graph graph
= { 0 };
3812 isl_schedule
*sched
;
3813 struct isl_extract_edge_data data
;
3814 enum isl_edge_type i
;
3816 sc
= isl_schedule_constraints_align_params(sc
);
3820 graph
.n
= isl_union_set_n_set(sc
->domain
);
3823 if (graph_alloc(ctx
, &graph
, graph
.n
,
3824 isl_schedule_constraints_n_map(sc
)) < 0)
3826 if (compute_max_row(&graph
, sc
->domain
) < 0)
3830 if (isl_union_set_foreach_set(sc
->domain
, &extract_node
, &graph
) < 0)
3832 if (graph_init_table(ctx
, &graph
) < 0)
3834 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
3835 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
3836 if (graph_init_edge_tables(ctx
, &graph
) < 0)
3839 data
.graph
= &graph
;
3840 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
3842 if (isl_union_map_foreach_map(sc
->constraint
[i
],
3843 &extract_edge
, &data
) < 0)
3847 if (compute_schedule(ctx
, &graph
) < 0)
3851 sched
= extract_schedule(&graph
, isl_union_set_get_space(sc
->domain
));
3853 graph_free(ctx
, &graph
);
3854 isl_schedule_constraints_free(sc
);
3858 graph_free(ctx
, &graph
);
3859 isl_schedule_constraints_free(sc
);
3863 /* Compute a schedule for the given union of domains that respects
3864 * all the validity dependences and minimizes
3865 * the dependence distances over the proximity dependences.
3867 * This function is kept for backward compatibility.
3869 __isl_give isl_schedule
*isl_union_set_compute_schedule(
3870 __isl_take isl_union_set
*domain
,
3871 __isl_take isl_union_map
*validity
,
3872 __isl_take isl_union_map
*proximity
)
3874 isl_schedule_constraints
*sc
;
3876 sc
= isl_schedule_constraints_on_domain(domain
);
3877 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
3878 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
3880 return isl_schedule_constraints_compute_schedule(sc
);
3883 __isl_null isl_schedule
*isl_schedule_free(__isl_take isl_schedule
*sched
)
3889 if (--sched
->ref
> 0)
3892 for (i
= 0; i
< sched
->n
; ++i
) {
3893 isl_multi_aff_free(sched
->node
[i
].sched
);
3894 free(sched
->node
[i
].band_end
);
3895 free(sched
->node
[i
].band_id
);
3896 free(sched
->node
[i
].coincident
);
3898 isl_space_free(sched
->dim
);
3899 isl_band_list_free(sched
->band_forest
);
3904 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
3906 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
3909 /* Set max_out to the maximal number of output dimensions over
3912 static int update_max_out(__isl_take isl_map
*map
, void *user
)
3914 int *max_out
= user
;
3915 int n_out
= isl_map_dim(map
, isl_dim_out
);
3917 if (n_out
> *max_out
)
3924 /* Internal data structure for map_pad_range.
3926 * "max_out" is the maximal schedule dimension.
3927 * "res" collects the results.
3929 struct isl_pad_schedule_map_data
{
3934 /* Pad the range of the given map with zeros to data->max_out and
3935 * then add the result to data->res.
3937 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
3939 struct isl_pad_schedule_map_data
*data
= user
;
3941 int n_out
= isl_map_dim(map
, isl_dim_out
);
3943 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
3944 for (i
= n_out
; i
< data
->max_out
; ++i
)
3945 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
3947 data
->res
= isl_union_map_add_map(data
->res
, map
);
3954 /* Pad the ranges of the maps in the union map with zeros such they all have
3955 * the same dimension.
3957 static __isl_give isl_union_map
*pad_schedule_map(
3958 __isl_take isl_union_map
*umap
)
3960 struct isl_pad_schedule_map_data data
;
3964 if (isl_union_map_n_map(umap
) <= 1)
3968 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
3969 return isl_union_map_free(umap
);
3971 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3972 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
3973 data
.res
= isl_union_map_free(data
.res
);
3975 isl_union_map_free(umap
);
3979 /* Return an isl_union_map of the schedule. If we have already constructed
3980 * a band forest, then this band forest may have been modified so we need
3981 * to extract the isl_union_map from the forest rather than from
3982 * the originally computed schedule. This reconstructed schedule map
3983 * then needs to be padded with zeros to unify the schedule space
3984 * since the result of isl_band_list_get_suffix_schedule may not have
3985 * a unified schedule space.
3987 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
3990 isl_union_map
*umap
;
3995 if (sched
->band_forest
) {
3996 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
3997 return pad_schedule_map(umap
);
4000 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
4001 for (i
= 0; i
< sched
->n
; ++i
) {
4004 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
4005 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
4011 static __isl_give isl_band_list
*construct_band_list(
4012 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
4013 int band_nr
, int *parent_active
, int n_active
);
4015 /* Construct an isl_band structure for the band in the given schedule
4016 * with sequence number band_nr for the n_active nodes marked by active.
4017 * If the nodes don't have a band with the given sequence number,
4018 * then a band without members is created.
4020 * Because of the way the schedule is constructed, we know that
4021 * the position of the band inside the schedule of a node is the same
4022 * for all active nodes.
4024 * The partial schedule for the band is created before the children
4025 * are created to that construct_band_list can refer to the partial
4026 * schedule of the parent.
4028 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
4029 __isl_keep isl_band
*parent
,
4030 int band_nr
, int *active
, int n_active
)
4033 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4035 unsigned start
, end
;
4037 band
= isl_band_alloc(ctx
);
4041 band
->schedule
= schedule
;
4042 band
->parent
= parent
;
4044 for (i
= 0; i
< schedule
->n
; ++i
)
4048 if (i
>= schedule
->n
)
4049 isl_die(ctx
, isl_error_internal
,
4050 "band without active statements", goto error
);
4052 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
4053 end
= band_nr
< schedule
->node
[i
].n_band
?
4054 schedule
->node
[i
].band_end
[band_nr
] : start
;
4055 band
->n
= end
- start
;
4057 band
->coincident
= isl_alloc_array(ctx
, int, band
->n
);
4058 if (band
->n
&& !band
->coincident
)
4061 for (j
= 0; j
< band
->n
; ++j
)
4062 band
->coincident
[j
] = schedule
->node
[i
].coincident
[start
+ j
];
4064 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
4065 for (i
= 0; i
< schedule
->n
; ++i
) {
4067 isl_pw_multi_aff
*pma
;
4073 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
4074 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
4075 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
4076 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
4077 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
4078 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
4084 for (i
= 0; i
< schedule
->n
; ++i
)
4085 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
4088 if (i
< schedule
->n
) {
4089 band
->children
= construct_band_list(schedule
, band
,
4090 band_nr
+ 1, active
, n_active
);
4091 if (!band
->children
)
4097 isl_band_free(band
);
4101 /* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
4103 * r is set to a negative value if anything goes wrong.
4105 * c1 stores the result of extract_int.
4106 * c2 is a temporary value used inside cmp_band_in_ancestor.
4107 * t is a temporary value used inside extract_int.
4109 * first and equal are used inside extract_int.
4110 * first is set if we are looking at the first isl_multi_aff inside
4111 * the isl_union_pw_multi_aff.
4112 * equal is set if all the isl_multi_affs have been equal so far.
4114 struct isl_cmp_band_data
{
4125 /* Check if "ma" assigns a constant value.
4126 * Note that this function is only called on isl_multi_affs
4127 * with a single output dimension.
4129 * If "ma" assigns a constant value then we compare it to data->c1
4130 * or assign it to data->c1 if this is the first isl_multi_aff we consider.
4131 * If "ma" does not assign a constant value or if it assigns a value
4132 * that is different from data->c1, then we set data->equal to zero
4133 * and terminate the check.
4135 static int multi_aff_extract_int(__isl_take isl_set
*set
,
4136 __isl_take isl_multi_aff
*ma
, void *user
)
4139 struct isl_cmp_band_data
*data
= user
;
4141 aff
= isl_multi_aff_get_aff(ma
, 0);
4142 data
->r
= isl_aff_is_cst(aff
);
4143 if (data
->r
>= 0 && data
->r
) {
4144 isl_aff_get_constant(aff
, &data
->t
);
4146 isl_int_set(data
->c1
, data
->t
);
4148 } else if (!isl_int_eq(data
->c1
, data
->t
))
4150 } else if (data
->r
>= 0 && !data
->r
)
4155 isl_multi_aff_free(ma
);
4164 /* This function is called for each isl_pw_multi_aff in
4165 * the isl_union_pw_multi_aff checked by extract_int.
4166 * Check all the isl_multi_affs inside "pma".
4168 static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff
*pma
,
4173 r
= isl_pw_multi_aff_foreach_piece(pma
, &multi_aff_extract_int
, user
);
4174 isl_pw_multi_aff_free(pma
);
4179 /* Check if "upma" assigns a single constant value to its domain.
4180 * If so, return 1 and store the result in data->c1.
4183 * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
4184 * means that either an error occurred or that we have broken off the check
4185 * because we already know the result is going to be negative.
4186 * In the latter case, data->equal is set to zero.
4188 static int extract_int(__isl_keep isl_union_pw_multi_aff
*upma
,
4189 struct isl_cmp_band_data
*data
)
4194 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4195 &pw_multi_aff_extract_int
, data
) < 0) {
4201 return !data
->first
&& data
->equal
;
4204 /* Compare "b1" and "b2" based on the parent schedule of their ancestor
4207 * If the parent of "ancestor" also has a single member, then we
4208 * first try to compare the two band based on the partial schedule
4211 * Otherwise, or if the result is inconclusive, we look at the partial schedule
4212 * of "ancestor" itself.
4213 * In particular, we specialize the parent schedule based
4214 * on the domains of the child schedules, check if both assign
4215 * a single constant value and, if so, compare the two constant values.
4216 * If the specialized parent schedules do not assign a constant value,
4217 * then they cannot be used to order the two bands and so in this case
4220 static int cmp_band_in_ancestor(__isl_keep isl_band
*b1
,
4221 __isl_keep isl_band
*b2
, struct isl_cmp_band_data
*data
,
4222 __isl_keep isl_band
*ancestor
)
4224 isl_union_pw_multi_aff
*upma
;
4225 isl_union_set
*domain
;
4231 if (ancestor
->parent
&& ancestor
->parent
->n
== 1) {
4232 r
= cmp_band_in_ancestor(b1
, b2
, data
, ancestor
->parent
);
4239 upma
= isl_union_pw_multi_aff_copy(b1
->pma
);
4240 domain
= isl_union_pw_multi_aff_domain(upma
);
4241 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
4242 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
4243 r
= extract_int(upma
, data
);
4244 isl_union_pw_multi_aff_free(upma
);
4251 isl_int_set(data
->c2
, data
->c1
);
4253 upma
= isl_union_pw_multi_aff_copy(b2
->pma
);
4254 domain
= isl_union_pw_multi_aff_domain(upma
);
4255 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
4256 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
4257 r
= extract_int(upma
, data
);
4258 isl_union_pw_multi_aff_free(upma
);
4265 return isl_int_cmp(data
->c2
, data
->c1
);
4268 /* Compare "a" and "b" based on the parent schedule of their parent.
4270 static int cmp_band(const void *a
, const void *b
, void *user
)
4272 isl_band
*b1
= *(isl_band
* const *) a
;
4273 isl_band
*b2
= *(isl_band
* const *) b
;
4274 struct isl_cmp_band_data
*data
= user
;
4276 return cmp_band_in_ancestor(b1
, b2
, data
, b1
->parent
);
4279 /* Sort the elements in "list" based on the partial schedules of its parent
4280 * (and ancestors). In particular if the parent assigns constant values
4281 * to the domains of the bands in "list", then the elements are sorted
4282 * according to that order.
4283 * This order should be a more "natural" order for the user, but otherwise
4284 * shouldn't have any effect.
4285 * If we would be constructing an isl_band forest directly in
4286 * isl_schedule_constraints_compute_schedule then there wouldn't be any need
4287 * for a reordering, since the children would be added to the list
4288 * in their natural order automatically.
4290 * If there is only one element in the list, then there is no need to sort
4292 * If the partial schedule of the parent has more than one member
4293 * (or if there is no parent), then it's
4294 * defnitely not assigning constant values to the different children in
4295 * the list and so we wouldn't be able to use it to sort the list.
4297 static __isl_give isl_band_list
*sort_band_list(__isl_take isl_band_list
*list
,
4298 __isl_keep isl_band
*parent
)
4300 struct isl_cmp_band_data data
;
4306 if (!parent
|| parent
->n
!= 1)
4310 isl_int_init(data
.c1
);
4311 isl_int_init(data
.c2
);
4312 isl_int_init(data
.t
);
4313 isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]), &cmp_band
, &data
);
4315 list
= isl_band_list_free(list
);
4316 isl_int_clear(data
.c1
);
4317 isl_int_clear(data
.c2
);
4318 isl_int_clear(data
.t
);
4323 /* Construct a list of bands that start at the same position (with
4324 * sequence number band_nr) in the schedules of the nodes that
4325 * were active in the parent band.
4327 * A separate isl_band structure is created for each band_id
4328 * and for each node that does not have a band with sequence
4329 * number band_nr. In the latter case, a band without members
4331 * This ensures that if a band has any children, then each node
4332 * that was active in the band is active in exactly one of the children.
4334 static __isl_give isl_band_list
*construct_band_list(
4335 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
4336 int band_nr
, int *parent_active
, int n_active
)
4339 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4342 isl_band_list
*list
;
4345 for (i
= 0; i
< n_active
; ++i
) {
4346 for (j
= 0; j
< schedule
->n
; ++j
) {
4347 if (!parent_active
[j
])
4349 if (schedule
->node
[j
].n_band
<= band_nr
)
4351 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
4357 for (j
= 0; j
< schedule
->n
; ++j
)
4358 if (schedule
->node
[j
].n_band
<= band_nr
)
4363 list
= isl_band_list_alloc(ctx
, n_band
);
4364 band
= construct_band(schedule
, parent
, band_nr
,
4365 parent_active
, n_active
);
4366 return isl_band_list_add(list
, band
);
4369 active
= isl_alloc_array(ctx
, int, schedule
->n
);
4370 if (schedule
->n
&& !active
)
4373 list
= isl_band_list_alloc(ctx
, n_band
);
4375 for (i
= 0; i
< n_active
; ++i
) {
4379 for (j
= 0; j
< schedule
->n
; ++j
) {
4380 active
[j
] = parent_active
[j
] &&
4381 schedule
->node
[j
].n_band
> band_nr
&&
4382 schedule
->node
[j
].band_id
[band_nr
] == i
;
4389 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
4391 list
= isl_band_list_add(list
, band
);
4393 for (i
= 0; i
< schedule
->n
; ++i
) {
4395 if (!parent_active
[i
])
4397 if (schedule
->node
[i
].n_band
> band_nr
)
4399 for (j
= 0; j
< schedule
->n
; ++j
)
4401 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
4402 list
= isl_band_list_add(list
, band
);
4407 list
= sort_band_list(list
, parent
);
4412 /* Construct a band forest representation of the schedule and
4413 * return the list of roots.
4415 static __isl_give isl_band_list
*construct_forest(
4416 __isl_keep isl_schedule
*schedule
)
4419 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4420 isl_band_list
*forest
;
4423 active
= isl_alloc_array(ctx
, int, schedule
->n
);
4424 if (schedule
->n
&& !active
)
4427 for (i
= 0; i
< schedule
->n
; ++i
)
4430 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
4437 /* Return the roots of a band forest representation of the schedule.
4439 __isl_give isl_band_list
*isl_schedule_get_band_forest(
4440 __isl_keep isl_schedule
*schedule
)
4444 if (!schedule
->band_forest
)
4445 schedule
->band_forest
= construct_forest(schedule
);
4446 return isl_band_list_dup(schedule
->band_forest
);
4449 /* Call "fn" on each band in the schedule in depth-first post-order.
4451 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
4452 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
4455 isl_band_list
*forest
;
4460 forest
= isl_schedule_get_band_forest(sched
);
4461 r
= isl_band_list_foreach_band(forest
, fn
, user
);
4462 isl_band_list_free(forest
);
4467 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
4468 __isl_keep isl_band_list
*list
);
4470 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
4471 __isl_keep isl_band
*band
)
4473 isl_band_list
*children
;
4475 p
= isl_printer_start_line(p
);
4476 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
4477 p
= isl_printer_end_line(p
);
4479 if (!isl_band_has_children(band
))
4482 children
= isl_band_get_children(band
);
4484 p
= isl_printer_indent(p
, 4);
4485 p
= print_band_list(p
, children
);
4486 p
= isl_printer_indent(p
, -4);
4488 isl_band_list_free(children
);
4493 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
4494 __isl_keep isl_band_list
*list
)
4498 n
= isl_band_list_n_band(list
);
4499 for (i
= 0; i
< n
; ++i
) {
4501 band
= isl_band_list_get_band(list
, i
);
4502 p
= print_band(p
, band
);
4503 isl_band_free(band
);
4509 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
4510 __isl_keep isl_schedule
*schedule
)
4512 isl_band_list
*forest
;
4514 forest
= isl_schedule_get_band_forest(schedule
);
4516 p
= print_band_list(p
, forest
);
4518 isl_band_list_free(forest
);
4523 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
4525 isl_printer
*printer
;
4530 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
4531 printer
= isl_printer_print_schedule(printer
, schedule
);
4533 isl_printer_free(printer
);