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 /* Construct an isl_schedule_constraints object for computing a schedule
40 * on "domain". The initial object does not impose any constraints.
42 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
43 __isl_take isl_union_set
*domain
)
47 isl_schedule_constraints
*sc
;
54 ctx
= isl_union_set_get_ctx(domain
);
55 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
57 return isl_union_set_free(domain
);
59 space
= isl_union_set_get_space(domain
);
61 empty
= isl_union_map_empty(space
);
62 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
63 sc
->constraint
[i
] = isl_union_map_copy(empty
);
64 if (!sc
->constraint
[i
])
65 sc
->domain
= isl_union_set_free(sc
->domain
);
67 isl_union_map_free(empty
);
70 return isl_schedule_constraints_free(sc
);
75 /* Replace the validity constraints of "sc" by "validity".
77 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
78 __isl_take isl_schedule_constraints
*sc
,
79 __isl_take isl_union_map
*validity
)
84 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
85 sc
->constraint
[isl_edge_validity
] = validity
;
89 isl_schedule_constraints_free(sc
);
90 isl_union_map_free(validity
);
94 /* Replace the proximity constraints of "sc" by "proximity".
96 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
97 __isl_take isl_schedule_constraints
*sc
,
98 __isl_take isl_union_map
*proximity
)
100 if (!sc
|| !proximity
)
103 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
104 sc
->constraint
[isl_edge_proximity
] = proximity
;
108 isl_schedule_constraints_free(sc
);
109 isl_union_map_free(proximity
);
113 /* Replace the conditional validity constraints of "sc" by "condition"
116 __isl_give isl_schedule_constraints
*
117 isl_schedule_constraints_set_conditional_validity(
118 __isl_take isl_schedule_constraints
*sc
,
119 __isl_take isl_union_map
*condition
,
120 __isl_take isl_union_map
*validity
)
122 if (!sc
|| !condition
|| !validity
)
125 isl_union_map_free(sc
->constraint
[isl_edge_condition
]);
126 sc
->constraint
[isl_edge_condition
] = condition
;
127 isl_union_map_free(sc
->constraint
[isl_edge_conditional_validity
]);
128 sc
->constraint
[isl_edge_conditional_validity
] = validity
;
132 isl_schedule_constraints_free(sc
);
133 isl_union_map_free(condition
);
134 isl_union_map_free(validity
);
138 void *isl_schedule_constraints_free(__isl_take isl_schedule_constraints
*sc
)
140 enum isl_edge_type i
;
145 isl_union_set_free(sc
->domain
);
146 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
147 isl_union_map_free(sc
->constraint
[i
]);
154 isl_ctx
*isl_schedule_constraints_get_ctx(
155 __isl_keep isl_schedule_constraints
*sc
)
157 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
160 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
165 fprintf(stderr
, "domain: ");
166 isl_union_set_dump(sc
->domain
);
167 fprintf(stderr
, "validity: ");
168 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
169 fprintf(stderr
, "proximity: ");
170 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
171 fprintf(stderr
, "condition: ");
172 isl_union_map_dump(sc
->constraint
[isl_edge_condition
]);
173 fprintf(stderr
, "conditional_validity: ");
174 isl_union_map_dump(sc
->constraint
[isl_edge_conditional_validity
]);
177 /* Align the parameters of the fields of "sc".
179 static __isl_give isl_schedule_constraints
*
180 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
183 enum isl_edge_type i
;
188 space
= isl_union_set_get_space(sc
->domain
);
189 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
190 space
= isl_space_align_params(space
,
191 isl_union_map_get_space(sc
->constraint
[i
]));
193 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
194 sc
->constraint
[i
] = isl_union_map_align_params(
195 sc
->constraint
[i
], isl_space_copy(space
));
196 if (!sc
->constraint
[i
])
197 space
= isl_space_free(space
);
199 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
201 return isl_schedule_constraints_free(sc
);
206 /* Return the total number of isl_maps in the constraints of "sc".
208 static __isl_give
int isl_schedule_constraints_n_map(
209 __isl_keep isl_schedule_constraints
*sc
)
211 enum isl_edge_type i
;
214 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
215 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
220 /* Internal information about a node that is used during the construction
222 * dim represents the space in which the domain lives
223 * sched is a matrix representation of the schedule being constructed
225 * sched_map is an isl_map representation of the same (partial) schedule
226 * sched_map may be NULL
227 * rank is the number of linearly independent rows in the linear part
229 * the columns of cmap represent a change of basis for the schedule
230 * coefficients; the first rank columns span the linear part of
232 * cinv is the inverse of cmap.
233 * start is the first variable in the LP problem in the sequences that
234 * represents the schedule coefficients of this node
235 * nvar is the dimension of the domain
236 * nparam is the number of parameters or 0 if we are not constructing
237 * a parametric schedule
239 * scc is the index of SCC (or WCC) this node belongs to
241 * band contains the band index for each of the rows of the schedule.
242 * band_id is used to differentiate between separate bands at the same
243 * level within the same parent band, i.e., bands that are separated
244 * by the parent band or bands that are independent of each other.
245 * zero contains a boolean for each of the rows of the schedule,
246 * indicating whether the corresponding scheduling dimension results
247 * in zero dependence distances within its band and with respect
248 * to the proximity edges.
250 struct isl_sched_node
{
268 static int node_has_dim(const void *entry
, const void *val
)
270 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
271 isl_space
*dim
= (isl_space
*)val
;
273 return isl_space_is_equal(node
->dim
, dim
);
276 /* An edge in the dependence graph. An edge may be used to
277 * ensure validity of the generated schedule, to minimize the dependence
280 * map is the dependence relation, with i -> j in the map if j depends on i
281 * tagged_condition and tagged_validity contain the union of all tagged
282 * condition or conditional validity dependence relations that
283 * specialize the dependence relation "map"; that is,
284 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
285 * or "tagged_validity", then i -> j is an element of "map".
286 * If these fields are NULL, then they represent the empty relation.
287 * src is the source node
288 * dst is the sink node
289 * validity is set if the edge is used to ensure correctness
290 * proximity is set if the edge is used to minimize dependence distances
291 * condition is set if the edge represents a condition
292 * for a conditional validity schedule constraint
293 * local can only be set for condition edges and indicates that
294 * the dependence distance over the edge should be zero
295 * conditional_validity is set if the edge is used to conditionally
298 * For validity edges, start and end mark the sequence of inequality
299 * constraints in the LP problem that encode the validity constraint
300 * corresponding to this edge.
302 struct isl_sched_edge
{
304 isl_union_map
*tagged_condition
;
305 isl_union_map
*tagged_validity
;
307 struct isl_sched_node
*src
;
308 struct isl_sched_node
*dst
;
310 unsigned validity
: 1;
311 unsigned proximity
: 1;
313 unsigned condition
: 1;
314 unsigned conditional_validity
: 1;
320 /* Internal information about the dependence graph used during
321 * the construction of the schedule.
323 * intra_hmap is a cache, mapping dependence relations to their dual,
324 * for dependences from a node to itself
325 * inter_hmap is a cache, mapping dependence relations to their dual,
326 * for dependences between distinct nodes
328 * n is the number of nodes
329 * node is the list of nodes
330 * maxvar is the maximal number of variables over all nodes
331 * max_row is the allocated number of rows in the schedule
332 * n_row is the current (maximal) number of linearly independent
333 * rows in the node schedules
334 * n_total_row is the current number of rows in the node schedules
335 * n_band is the current number of completed bands
336 * band_start is the starting row in the node schedules of the current band
337 * root is set if this graph is the original dependence graph,
338 * without any splitting
340 * sorted contains a list of node indices sorted according to the
341 * SCC to which a node belongs
343 * n_edge is the number of edges
344 * edge is the list of edges
345 * max_edge contains the maximal number of edges of each type;
346 * in particular, it contains the number of edges in the inital graph.
347 * edge_table contains pointers into the edge array, hashed on the source
348 * and sink spaces; there is one such table for each type;
349 * a given edge may be referenced from more than one table
350 * if the corresponding relation appears in more than of the
351 * sets of dependences
353 * node_table contains pointers into the node array, hashed on the space
355 * region contains a list of variable sequences that should be non-trivial
357 * lp contains the (I)LP problem used to obtain new schedule rows
359 * src_scc and dst_scc are the source and sink SCCs of an edge with
360 * conflicting constraints
362 * scc represents the number of components
364 struct isl_sched_graph
{
365 isl_map_to_basic_set
*intra_hmap
;
366 isl_map_to_basic_set
*inter_hmap
;
368 struct isl_sched_node
*node
;
382 struct isl_sched_edge
*edge
;
384 int max_edge
[isl_edge_last
+ 1];
385 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
387 struct isl_hash_table
*node_table
;
388 struct isl_region
*region
;
398 /* Initialize node_table based on the list of nodes.
400 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
404 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
405 if (!graph
->node_table
)
408 for (i
= 0; i
< graph
->n
; ++i
) {
409 struct isl_hash_table_entry
*entry
;
412 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
413 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
415 graph
->node
[i
].dim
, 1);
418 entry
->data
= &graph
->node
[i
];
424 /* Return a pointer to the node that lives within the given space,
425 * or NULL if there is no such node.
427 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
428 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
430 struct isl_hash_table_entry
*entry
;
433 hash
= isl_space_get_hash(dim
);
434 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
435 &node_has_dim
, dim
, 0);
437 return entry
? entry
->data
: NULL
;
440 static int edge_has_src_and_dst(const void *entry
, const void *val
)
442 const struct isl_sched_edge
*edge
= entry
;
443 const struct isl_sched_edge
*temp
= val
;
445 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
448 /* Add the given edge to graph->edge_table[type].
450 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
451 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
453 struct isl_hash_table_entry
*entry
;
456 hash
= isl_hash_init();
457 hash
= isl_hash_builtin(hash
, edge
->src
);
458 hash
= isl_hash_builtin(hash
, edge
->dst
);
459 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
460 &edge_has_src_and_dst
, edge
, 1);
468 /* Allocate the edge_tables based on the maximal number of edges of
471 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
475 for (i
= 0; i
<= isl_edge_last
; ++i
) {
476 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
478 if (!graph
->edge_table
[i
])
485 /* If graph->edge_table[type] contains an edge from the given source
486 * to the given destination, then return the hash table entry of this edge.
487 * Otherwise, return NULL.
489 static struct isl_hash_table_entry
*graph_find_edge_entry(
490 struct isl_sched_graph
*graph
,
491 enum isl_edge_type type
,
492 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
494 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
496 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
498 hash
= isl_hash_init();
499 hash
= isl_hash_builtin(hash
, temp
.src
);
500 hash
= isl_hash_builtin(hash
, temp
.dst
);
501 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
502 &edge_has_src_and_dst
, &temp
, 0);
506 /* If graph->edge_table[type] contains an edge from the given source
507 * to the given destination, then return this edge.
508 * Otherwise, return NULL.
510 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
511 enum isl_edge_type type
,
512 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
514 struct isl_hash_table_entry
*entry
;
516 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
523 /* Check whether the dependence graph has an edge of the given type
524 * between the given two nodes.
526 static int graph_has_edge(struct isl_sched_graph
*graph
,
527 enum isl_edge_type type
,
528 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
530 struct isl_sched_edge
*edge
;
533 edge
= graph_find_edge(graph
, type
, src
, dst
);
537 empty
= isl_map_plain_is_empty(edge
->map
);
544 /* Look for any edge with the same src, dst and map fields as "model".
546 * Return the matching edge if one can be found.
547 * Return "model" if no matching edge is found.
548 * Return NULL on error.
550 static struct isl_sched_edge
*graph_find_matching_edge(
551 struct isl_sched_graph
*graph
, struct isl_sched_edge
*model
)
553 enum isl_edge_type i
;
554 struct isl_sched_edge
*edge
;
556 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
559 edge
= graph_find_edge(graph
, i
, model
->src
, model
->dst
);
562 is_equal
= isl_map_plain_is_equal(model
->map
, edge
->map
);
572 /* Remove the given edge from all the edge_tables that refer to it.
574 static void graph_remove_edge(struct isl_sched_graph
*graph
,
575 struct isl_sched_edge
*edge
)
577 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
578 enum isl_edge_type i
;
580 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
581 struct isl_hash_table_entry
*entry
;
583 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
586 if (entry
->data
!= edge
)
588 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
592 /* Check whether the dependence graph has any edge
593 * between the given two nodes.
595 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
596 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
598 enum isl_edge_type i
;
601 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
602 r
= graph_has_edge(graph
, i
, src
, dst
);
610 /* Check whether the dependence graph has a validity edge
611 * between the given two nodes.
613 * Conditional validity edges are essentially validity edges that
614 * can be ignored if the corresponding condition edges are iteration private.
615 * Here, we are only checking for the presence of validity
616 * edges, so we need to consider the conditional validity edges too.
617 * In particular, this function is used during the detection
618 * of strongly connected components and we cannot ignore
619 * conditional validity edges during this detection.
621 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
622 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
626 r
= graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
630 return graph_has_edge(graph
, isl_edge_conditional_validity
, src
, dst
);
633 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
634 int n_node
, int n_edge
)
639 graph
->n_edge
= n_edge
;
640 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
641 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
642 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
643 graph
->edge
= isl_calloc_array(ctx
,
644 struct isl_sched_edge
, graph
->n_edge
);
646 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
647 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
649 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
653 for(i
= 0; i
< graph
->n
; ++i
)
654 graph
->sorted
[i
] = i
;
659 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
663 isl_map_to_basic_set_free(graph
->intra_hmap
);
664 isl_map_to_basic_set_free(graph
->inter_hmap
);
666 for (i
= 0; i
< graph
->n
; ++i
) {
667 isl_space_free(graph
->node
[i
].dim
);
668 isl_mat_free(graph
->node
[i
].sched
);
669 isl_map_free(graph
->node
[i
].sched_map
);
670 isl_mat_free(graph
->node
[i
].cmap
);
671 isl_mat_free(graph
->node
[i
].cinv
);
673 free(graph
->node
[i
].band
);
674 free(graph
->node
[i
].band_id
);
675 free(graph
->node
[i
].zero
);
680 for (i
= 0; i
< graph
->n_edge
; ++i
) {
681 isl_map_free(graph
->edge
[i
].map
);
682 isl_union_map_free(graph
->edge
[i
].tagged_condition
);
683 isl_union_map_free(graph
->edge
[i
].tagged_validity
);
687 for (i
= 0; i
<= isl_edge_last
; ++i
)
688 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
689 isl_hash_table_free(ctx
, graph
->node_table
);
690 isl_basic_set_free(graph
->lp
);
693 /* For each "set" on which this function is called, increment
694 * graph->n by one and update graph->maxvar.
696 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
698 struct isl_sched_graph
*graph
= user
;
699 int nvar
= isl_set_dim(set
, isl_dim_set
);
702 if (nvar
> graph
->maxvar
)
703 graph
->maxvar
= nvar
;
710 /* Compute the number of rows that should be allocated for the schedule.
711 * The graph can be split at most "n - 1" times, there can be at most
712 * two rows for each dimension in the iteration domains (in particular,
713 * we usually have one row, but it may be split by split_scaled),
714 * and there can be one extra row for ordering the statements.
715 * Note that if we have actually split "n - 1" times, then no ordering
716 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
718 static int compute_max_row(struct isl_sched_graph
*graph
,
719 __isl_keep isl_union_set
*domain
)
723 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
725 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
730 /* Add a new node to the graph representing the given set.
732 static int extract_node(__isl_take isl_set
*set
, void *user
)
738 struct isl_sched_graph
*graph
= user
;
739 int *band
, *band_id
, *zero
;
741 ctx
= isl_set_get_ctx(set
);
742 dim
= isl_set_get_space(set
);
744 nvar
= isl_space_dim(dim
, isl_dim_set
);
745 nparam
= isl_space_dim(dim
, isl_dim_param
);
746 if (!ctx
->opt
->schedule_parametric
)
748 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
749 graph
->node
[graph
->n
].dim
= dim
;
750 graph
->node
[graph
->n
].nvar
= nvar
;
751 graph
->node
[graph
->n
].nparam
= nparam
;
752 graph
->node
[graph
->n
].sched
= sched
;
753 graph
->node
[graph
->n
].sched_map
= NULL
;
754 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
755 graph
->node
[graph
->n
].band
= band
;
756 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
757 graph
->node
[graph
->n
].band_id
= band_id
;
758 zero
= isl_calloc_array(ctx
, int, graph
->max_row
);
759 graph
->node
[graph
->n
].zero
= zero
;
762 if (!sched
|| (graph
->max_row
&& (!band
|| !band_id
|| !zero
)))
768 struct isl_extract_edge_data
{
769 enum isl_edge_type type
;
770 struct isl_sched_graph
*graph
;
773 /* Merge edge2 into edge1, freeing the contents of edge2.
774 * "type" is the type of the schedule constraint from which edge2 was
776 * Return 0 on success and -1 on failure.
778 * edge1 and edge2 are assumed to have the same value for the map field.
780 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
781 struct isl_sched_edge
*edge2
)
783 edge1
->validity
|= edge2
->validity
;
784 edge1
->proximity
|= edge2
->proximity
;
785 edge1
->condition
|= edge2
->condition
;
786 edge1
->conditional_validity
|= edge2
->conditional_validity
;
787 isl_map_free(edge2
->map
);
789 if (type
== isl_edge_condition
) {
790 if (!edge1
->tagged_condition
)
791 edge1
->tagged_condition
= edge2
->tagged_condition
;
793 edge1
->tagged_condition
=
794 isl_union_map_union(edge1
->tagged_condition
,
795 edge2
->tagged_condition
);
798 if (type
== isl_edge_conditional_validity
) {
799 if (!edge1
->tagged_validity
)
800 edge1
->tagged_validity
= edge2
->tagged_validity
;
802 edge1
->tagged_validity
=
803 isl_union_map_union(edge1
->tagged_validity
,
804 edge2
->tagged_validity
);
807 if (type
== isl_edge_condition
&& !edge1
->tagged_condition
)
809 if (type
== isl_edge_conditional_validity
&& !edge1
->tagged_validity
)
815 /* Insert dummy tags in domain and range of "map".
817 * In particular, if "map" is of the form
823 * [A -> dummy_tag] -> [B -> dummy_tag]
825 * where the dummy_tags are identical and equal to any dummy tags
826 * introduced by any other call to this function.
828 static __isl_give isl_map
*insert_dummy_tags(__isl_take isl_map
*map
)
834 isl_set
*domain
, *range
;
836 ctx
= isl_map_get_ctx(map
);
838 id
= isl_id_alloc(ctx
, NULL
, &dummy
);
839 space
= isl_space_params(isl_map_get_space(map
));
840 space
= isl_space_set_from_params(space
);
841 space
= isl_space_set_tuple_id(space
, isl_dim_set
, id
);
842 space
= isl_space_map_from_set(space
);
844 domain
= isl_map_wrap(map
);
845 range
= isl_map_wrap(isl_map_universe(space
));
846 map
= isl_map_from_domain_and_range(domain
, range
);
847 map
= isl_map_zip(map
);
852 /* Add a new edge to the graph based on the given map
853 * and add it to data->graph->edge_table[data->type].
854 * If a dependence relation of a given type happens to be identical
855 * to one of the dependence relations of a type that was added before,
856 * then we don't create a new edge, but instead mark the original edge
857 * as also representing a dependence of the current type.
859 * Edges of type isl_edge_condition or isl_edge_conditional_validity
860 * may be specified as "tagged" dependence relations. That is, "map"
861 * may contain elements * (i -> a) -> (j -> b), where i -> j denotes
862 * the dependence on iterations and a and b are tags.
863 * edge->map is set to the relation containing the elements i -> j,
864 * while edge->tagged_condition and edge->tagged_validity contain
865 * the union of all the "map" relations
866 * for which extract_edge is called that result in the same edge->map.
868 static int extract_edge(__isl_take isl_map
*map
, void *user
)
870 isl_ctx
*ctx
= isl_map_get_ctx(map
);
871 struct isl_extract_edge_data
*data
= user
;
872 struct isl_sched_graph
*graph
= data
->graph
;
873 struct isl_sched_node
*src
, *dst
;
875 struct isl_sched_edge
*edge
;
876 isl_map
*tagged
= NULL
;
878 if (data
->type
== isl_edge_condition
||
879 data
->type
== isl_edge_conditional_validity
) {
880 if (isl_map_can_zip(map
)) {
881 tagged
= isl_map_copy(map
);
882 map
= isl_set_unwrap(isl_map_domain(isl_map_zip(map
)));
884 tagged
= insert_dummy_tags(isl_map_copy(map
));
888 dim
= isl_space_domain(isl_map_get_space(map
));
889 src
= graph_find_node(ctx
, graph
, dim
);
891 dim
= isl_space_range(isl_map_get_space(map
));
892 dst
= graph_find_node(ctx
, graph
, dim
);
897 isl_map_free(tagged
);
901 graph
->edge
[graph
->n_edge
].src
= src
;
902 graph
->edge
[graph
->n_edge
].dst
= dst
;
903 graph
->edge
[graph
->n_edge
].map
= map
;
904 graph
->edge
[graph
->n_edge
].validity
= 0;
905 graph
->edge
[graph
->n_edge
].proximity
= 0;
906 graph
->edge
[graph
->n_edge
].condition
= 0;
907 graph
->edge
[graph
->n_edge
].local
= 0;
908 graph
->edge
[graph
->n_edge
].conditional_validity
= 0;
909 graph
->edge
[graph
->n_edge
].tagged_condition
= NULL
;
910 graph
->edge
[graph
->n_edge
].tagged_validity
= NULL
;
911 if (data
->type
== isl_edge_validity
)
912 graph
->edge
[graph
->n_edge
].validity
= 1;
913 if (data
->type
== isl_edge_proximity
)
914 graph
->edge
[graph
->n_edge
].proximity
= 1;
915 if (data
->type
== isl_edge_condition
) {
916 graph
->edge
[graph
->n_edge
].condition
= 1;
917 graph
->edge
[graph
->n_edge
].tagged_condition
=
918 isl_union_map_from_map(tagged
);
920 if (data
->type
== isl_edge_conditional_validity
) {
921 graph
->edge
[graph
->n_edge
].conditional_validity
= 1;
922 graph
->edge
[graph
->n_edge
].tagged_validity
=
923 isl_union_map_from_map(tagged
);
926 edge
= graph_find_matching_edge(graph
, &graph
->edge
[graph
->n_edge
]);
927 if (edge
== &graph
->edge
[graph
->n_edge
])
928 return graph_edge_table_add(ctx
, graph
, data
->type
,
929 &graph
->edge
[graph
->n_edge
++]);
931 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
934 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
937 /* Check whether there is any dependence from node[j] to node[i]
938 * or from node[i] to node[j].
940 static int node_follows_weak(int i
, int j
, void *user
)
943 struct isl_sched_graph
*graph
= user
;
945 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
948 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
951 /* Check whether there is a (conditional) validity dependence from node[j]
952 * to node[i], forcing node[i] to follow node[j].
954 static int node_follows_strong(int i
, int j
, void *user
)
956 struct isl_sched_graph
*graph
= user
;
958 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
961 /* Use Tarjan's algorithm for computing the strongly connected components
962 * in the dependence graph (only validity edges).
963 * If weak is set, we consider the graph to be undirected and
964 * we effectively compute the (weakly) connected components.
965 * Additionally, we also consider other edges when weak is set.
967 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
970 struct isl_tarjan_graph
*g
= NULL
;
972 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
973 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
981 while (g
->order
[i
] != -1) {
982 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
990 isl_tarjan_graph_free(g
);
995 /* Apply Tarjan's algorithm to detect the strongly connected components
996 * in the dependence graph.
998 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1000 return detect_ccs(ctx
, graph
, 0);
1003 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1004 * in the dependence graph.
1006 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1008 return detect_ccs(ctx
, graph
, 1);
1011 static int cmp_scc(const void *a
, const void *b
, void *data
)
1013 struct isl_sched_graph
*graph
= data
;
1017 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
1020 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1022 static int sort_sccs(struct isl_sched_graph
*graph
)
1024 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
1027 /* Given a dependence relation R from a node to itself,
1028 * construct the set of coefficients of valid constraints for elements
1029 * in that dependence relation.
1030 * In particular, the result contains tuples of coefficients
1031 * c_0, c_n, c_x such that
1033 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1037 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1039 * We choose here to compute the dual of delta R.
1040 * Alternatively, we could have computed the dual of R, resulting
1041 * in a set of tuples c_0, c_n, c_x, c_y, and then
1042 * plugged in (c_0, c_n, c_x, -c_x).
1044 static __isl_give isl_basic_set
*intra_coefficients(
1045 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
1048 isl_basic_set
*coef
;
1050 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
1051 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
1053 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
1054 coef
= isl_set_coefficients(delta
);
1055 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, map
,
1056 isl_basic_set_copy(coef
));
1061 /* Given a dependence relation R, * construct the set of coefficients
1062 * of valid constraints for elements in that dependence relation.
1063 * In particular, the result contains tuples of coefficients
1064 * c_0, c_n, c_x, c_y such that
1066 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1069 static __isl_give isl_basic_set
*inter_coefficients(
1070 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
1073 isl_basic_set
*coef
;
1075 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
1076 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
1078 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
1079 coef
= isl_set_coefficients(set
);
1080 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, map
,
1081 isl_basic_set_copy(coef
));
1086 /* Add constraints to graph->lp that force validity for the given
1087 * dependence from a node i to itself.
1088 * That is, add constraints that enforce
1090 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1091 * = c_i_x (y - x) >= 0
1093 * for each (x,y) in R.
1094 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1095 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1096 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1097 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1099 * Actually, we do not construct constraints for the c_i_x themselves,
1100 * but for the coefficients of c_i_x written as a linear combination
1101 * of the columns in node->cmap.
1103 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
1104 struct isl_sched_edge
*edge
)
1107 isl_map
*map
= isl_map_copy(edge
->map
);
1108 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1110 isl_dim_map
*dim_map
;
1111 isl_basic_set
*coef
;
1112 struct isl_sched_node
*node
= edge
->src
;
1114 coef
= intra_coefficients(graph
, map
);
1116 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1118 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1119 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1123 total
= isl_basic_set_total_dim(graph
->lp
);
1124 dim_map
= isl_dim_map_alloc(ctx
, total
);
1125 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1126 isl_space_dim(dim
, isl_dim_set
), 1,
1128 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1129 isl_space_dim(dim
, isl_dim_set
), 1,
1131 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1132 coef
->n_eq
, coef
->n_ineq
);
1133 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1135 isl_space_free(dim
);
1139 isl_space_free(dim
);
1143 /* Add constraints to graph->lp that force validity for the given
1144 * dependence from node i to node j.
1145 * That is, add constraints that enforce
1147 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1149 * for each (x,y) in R.
1150 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1151 * of valid constraints for R and then plug in
1152 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1153 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1154 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1155 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1157 * Actually, we do not construct constraints for the c_*_x themselves,
1158 * but for the coefficients of c_*_x written as a linear combination
1159 * of the columns in node->cmap.
1161 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1162 struct isl_sched_edge
*edge
)
1165 isl_map
*map
= isl_map_copy(edge
->map
);
1166 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1168 isl_dim_map
*dim_map
;
1169 isl_basic_set
*coef
;
1170 struct isl_sched_node
*src
= edge
->src
;
1171 struct isl_sched_node
*dst
= edge
->dst
;
1173 coef
= inter_coefficients(graph
, map
);
1175 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1177 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1178 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1179 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1180 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1181 isl_mat_copy(dst
->cmap
));
1185 total
= isl_basic_set_total_dim(graph
->lp
);
1186 dim_map
= isl_dim_map_alloc(ctx
, total
);
1188 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1189 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1190 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1191 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1192 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1194 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1195 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1198 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1199 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1200 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1201 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1202 isl_space_dim(dim
, isl_dim_set
), 1,
1204 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1205 isl_space_dim(dim
, isl_dim_set
), 1,
1208 edge
->start
= graph
->lp
->n_ineq
;
1209 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1210 coef
->n_eq
, coef
->n_ineq
);
1211 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1215 isl_space_free(dim
);
1216 edge
->end
= graph
->lp
->n_ineq
;
1220 isl_space_free(dim
);
1224 /* Add constraints to graph->lp that bound the dependence distance for the given
1225 * dependence from a node i to itself.
1226 * If s = 1, we add the constraint
1228 * c_i_x (y - x) <= m_0 + m_n n
1232 * -c_i_x (y - x) + m_0 + m_n n >= 0
1234 * for each (x,y) in R.
1235 * If s = -1, we add the constraint
1237 * -c_i_x (y - x) <= m_0 + m_n n
1241 * c_i_x (y - x) + m_0 + m_n n >= 0
1243 * for each (x,y) in R.
1244 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1245 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1246 * with each coefficient (except m_0) represented as a pair of non-negative
1249 * Actually, we do not construct constraints for the c_i_x themselves,
1250 * but for the coefficients of c_i_x written as a linear combination
1251 * of the columns in node->cmap.
1254 * If "local" is set, then we add constraints
1256 * c_i_x (y - x) <= 0
1260 * -c_i_x (y - x) <= 0
1262 * instead, forcing the dependence distance to be (less than or) equal to 0.
1263 * That is, we plug in (0, 0, -s * c_i_x),
1264 * Note that dependences marked local are treated as validity constraints
1265 * by add_all_validity_constraints and therefore also have
1266 * their distances bounded by 0 from below.
1268 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1269 struct isl_sched_edge
*edge
, int s
, int local
)
1273 isl_map
*map
= isl_map_copy(edge
->map
);
1274 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1276 isl_dim_map
*dim_map
;
1277 isl_basic_set
*coef
;
1278 struct isl_sched_node
*node
= edge
->src
;
1280 coef
= intra_coefficients(graph
, map
);
1282 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1284 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1285 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1289 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
1290 total
= isl_basic_set_total_dim(graph
->lp
);
1291 dim_map
= isl_dim_map_alloc(ctx
, total
);
1294 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1295 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1296 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1298 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1299 isl_space_dim(dim
, isl_dim_set
), 1,
1301 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1302 isl_space_dim(dim
, isl_dim_set
), 1,
1304 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1305 coef
->n_eq
, coef
->n_ineq
);
1306 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1308 isl_space_free(dim
);
1312 isl_space_free(dim
);
1316 /* Add constraints to graph->lp that bound the dependence distance for the given
1317 * dependence from node i to node j.
1318 * If s = 1, we add the constraint
1320 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1325 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1328 * for each (x,y) in R.
1329 * If s = -1, we add the constraint
1331 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1336 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1339 * for each (x,y) in R.
1340 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1341 * of valid constraints for R and then plug in
1342 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1344 * with each coefficient (except m_0, c_j_0 and c_i_0)
1345 * represented as a pair of non-negative coefficients.
1347 * Actually, we do not construct constraints for the c_*_x themselves,
1348 * but for the coefficients of c_*_x written as a linear combination
1349 * of the columns in node->cmap.
1352 * If "local" is set, then we add constraints
1354 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1358 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1360 * instead, forcing the dependence distance to be (less than or) equal to 0.
1361 * That is, we plug in
1362 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1363 * Note that dependences marked local are treated as validity constraints
1364 * by add_all_validity_constraints and therefore also have
1365 * their distances bounded by 0 from below.
1367 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1368 struct isl_sched_edge
*edge
, int s
, int local
)
1372 isl_map
*map
= isl_map_copy(edge
->map
);
1373 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1375 isl_dim_map
*dim_map
;
1376 isl_basic_set
*coef
;
1377 struct isl_sched_node
*src
= edge
->src
;
1378 struct isl_sched_node
*dst
= edge
->dst
;
1380 coef
= inter_coefficients(graph
, map
);
1382 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1384 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1385 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1386 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1387 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1388 isl_mat_copy(dst
->cmap
));
1392 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1393 total
= isl_basic_set_total_dim(graph
->lp
);
1394 dim_map
= isl_dim_map_alloc(ctx
, total
);
1397 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1398 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1399 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1402 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1403 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1404 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1405 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1406 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1408 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1409 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1412 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1413 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1414 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1415 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1416 isl_space_dim(dim
, isl_dim_set
), 1,
1418 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1419 isl_space_dim(dim
, isl_dim_set
), 1,
1422 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1423 coef
->n_eq
, coef
->n_ineq
);
1424 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1426 isl_space_free(dim
);
1430 isl_space_free(dim
);
1434 /* Add all validity constraints to graph->lp.
1436 * An edge that is forced to be local needs to have its dependence
1437 * distances equal to zero. We take care of bounding them by 0 from below
1438 * here. add_all_proximity_constraints takes care of bounding them by 0
1441 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1445 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1446 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1447 if (!edge
->validity
&& !edge
->local
)
1449 if (edge
->src
!= edge
->dst
)
1451 if (add_intra_validity_constraints(graph
, edge
) < 0)
1455 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1456 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1457 if (!edge
->validity
&& !edge
->local
)
1459 if (edge
->src
== edge
->dst
)
1461 if (add_inter_validity_constraints(graph
, edge
) < 0)
1468 /* Add constraints to graph->lp that bound the dependence distance
1469 * for all dependence relations.
1470 * If a given proximity dependence is identical to a validity
1471 * dependence, then the dependence distance is already bounded
1472 * from below (by zero), so we only need to bound the distance
1473 * from above. (This includes the case of "local" dependences
1474 * which are treated as validity dependence by add_all_validity_constraints.)
1475 * Otherwise, we need to bound the distance both from above and from below.
1477 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1481 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1482 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1483 int local
= edge
->local
;
1485 if (!edge
->proximity
&& !local
)
1487 if (edge
->src
== edge
->dst
&&
1488 add_intra_proximity_constraints(graph
, edge
, 1, local
) < 0)
1490 if (edge
->src
!= edge
->dst
&&
1491 add_inter_proximity_constraints(graph
, edge
, 1, local
) < 0)
1493 if (edge
->validity
|| local
)
1495 if (edge
->src
== edge
->dst
&&
1496 add_intra_proximity_constraints(graph
, edge
, -1, 0) < 0)
1498 if (edge
->src
!= edge
->dst
&&
1499 add_inter_proximity_constraints(graph
, edge
, -1, 0) < 0)
1506 /* Compute a basis for the rows in the linear part of the schedule
1507 * and extend this basis to a full basis. The remaining rows
1508 * can then be used to force linear independence from the rows
1511 * In particular, given the schedule rows S, we compute
1516 * with H the Hermite normal form of S. That is, all but the
1517 * first rank columns of H are zero and so each row in S is
1518 * a linear combination of the first rank rows of Q.
1519 * The matrix Q is then transposed because we will write the
1520 * coefficients of the next schedule row as a column vector s
1521 * and express this s as a linear combination s = Q c of the
1523 * Similarly, the matrix U is transposed such that we can
1524 * compute the coefficients c = U s from a schedule row s.
1526 static int node_update_cmap(struct isl_sched_node
*node
)
1529 int n_row
= isl_mat_rows(node
->sched
);
1531 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1532 1 + node
->nparam
, node
->nvar
);
1534 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1535 isl_mat_free(node
->cmap
);
1536 isl_mat_free(node
->cinv
);
1537 node
->cmap
= isl_mat_transpose(Q
);
1538 node
->cinv
= isl_mat_transpose(U
);
1539 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1542 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1547 /* How many times should we count the constraints in "edge"?
1549 * If carry is set, then we are counting the number of
1550 * (validity or conditional validity) constraints that will be added
1551 * in setup_carry_lp and we count each edge exactly once.
1553 * Otherwise, we count as follows
1554 * validity -> 1 (>= 0)
1555 * validity+proximity -> 2 (>= 0 and upper bound)
1556 * proximity -> 2 (lower and upper bound)
1557 * local(+any) -> 2 (>= 0 and <= 0)
1559 * If an edge is only marked conditional_validity then it counts
1560 * as zero since it is only checked afterwards.
1562 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
)
1564 if (carry
&& !edge
->validity
&& !edge
->conditional_validity
)
1568 if (edge
->proximity
|| edge
->local
)
1575 /* Count the number of equality and inequality constraints
1576 * that will be added for the given map.
1578 static int count_map_constraints(struct isl_sched_graph
*graph
,
1579 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1580 int *n_eq
, int *n_ineq
, int carry
)
1582 isl_basic_set
*coef
;
1583 int f
= edge_multiplicity(edge
, carry
);
1590 if (edge
->src
== edge
->dst
)
1591 coef
= intra_coefficients(graph
, map
);
1593 coef
= inter_coefficients(graph
, map
);
1596 *n_eq
+= f
* coef
->n_eq
;
1597 *n_ineq
+= f
* coef
->n_ineq
;
1598 isl_basic_set_free(coef
);
1603 /* Count the number of equality and inequality constraints
1604 * that will be added to the main lp problem.
1605 * We count as follows
1606 * validity -> 1 (>= 0)
1607 * validity+proximity -> 2 (>= 0 and upper bound)
1608 * proximity -> 2 (lower and upper bound)
1609 * local(+any) -> 2 (>= 0 and <= 0)
1611 static int count_constraints(struct isl_sched_graph
*graph
,
1612 int *n_eq
, int *n_ineq
)
1616 *n_eq
= *n_ineq
= 0;
1617 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1618 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1619 isl_map
*map
= isl_map_copy(edge
->map
);
1621 if (count_map_constraints(graph
, edge
, map
,
1622 n_eq
, n_ineq
, 0) < 0)
1629 /* Count the number of constraints that will be added by
1630 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1633 * In practice, add_bound_coefficient_constraints only adds inequalities.
1635 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1636 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1640 if (ctx
->opt
->schedule_max_coefficient
== -1)
1643 for (i
= 0; i
< graph
->n
; ++i
)
1644 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1649 /* Add constraints that bound the values of the variable and parameter
1650 * coefficients of the schedule.
1652 * The maximal value of the coefficients is defined by the option
1653 * 'schedule_max_coefficient'.
1655 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1656 struct isl_sched_graph
*graph
)
1659 int max_coefficient
;
1662 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1664 if (max_coefficient
== -1)
1667 total
= isl_basic_set_total_dim(graph
->lp
);
1669 for (i
= 0; i
< graph
->n
; ++i
) {
1670 struct isl_sched_node
*node
= &graph
->node
[i
];
1671 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1673 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1676 dim
= 1 + node
->start
+ 1 + j
;
1677 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1678 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1679 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1686 /* Construct an ILP problem for finding schedule coefficients
1687 * that result in non-negative, but small dependence distances
1688 * over all dependences.
1689 * In particular, the dependence distances over proximity edges
1690 * are bounded by m_0 + m_n n and we compute schedule coefficients
1691 * with small values (preferably zero) of m_n and m_0.
1693 * All variables of the ILP are non-negative. The actual coefficients
1694 * may be negative, so each coefficient is represented as the difference
1695 * of two non-negative variables. The negative part always appears
1696 * immediately before the positive part.
1697 * Other than that, the variables have the following order
1699 * - sum of positive and negative parts of m_n coefficients
1701 * - sum of positive and negative parts of all c_n coefficients
1702 * (unconstrained when computing non-parametric schedules)
1703 * - sum of positive and negative parts of all c_x coefficients
1704 * - positive and negative parts of m_n coefficients
1707 * - positive and negative parts of c_i_n (if parametric)
1708 * - positive and negative parts of c_i_x
1710 * The c_i_x are not represented directly, but through the columns of
1711 * node->cmap. That is, the computed values are for variable t_i_x
1712 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1714 * The constraints are those from the edges plus two or three equalities
1715 * to express the sums.
1717 * If force_zero is set, then we add equalities to ensure that
1718 * the sum of the m_n coefficients and m_0 are both zero.
1720 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1731 int max_constant_term
;
1733 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1735 parametric
= ctx
->opt
->schedule_parametric
;
1736 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1738 total
= param_pos
+ 2 * nparam
;
1739 for (i
= 0; i
< graph
->n
; ++i
) {
1740 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1741 if (node_update_cmap(node
) < 0)
1743 node
->start
= total
;
1744 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1747 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1749 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
1752 dim
= isl_space_set_alloc(ctx
, 0, total
);
1753 isl_basic_set_free(graph
->lp
);
1754 n_eq
+= 2 + parametric
+ force_zero
;
1755 if (max_constant_term
!= -1)
1758 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1760 k
= isl_basic_set_alloc_equality(graph
->lp
);
1763 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1765 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1766 for (i
= 0; i
< 2 * nparam
; ++i
)
1767 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1770 k
= isl_basic_set_alloc_equality(graph
->lp
);
1773 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1774 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1778 k
= isl_basic_set_alloc_equality(graph
->lp
);
1781 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1782 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1783 for (i
= 0; i
< graph
->n
; ++i
) {
1784 int pos
= 1 + graph
->node
[i
].start
+ 1;
1786 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1787 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1791 k
= isl_basic_set_alloc_equality(graph
->lp
);
1794 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1795 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1796 for (i
= 0; i
< graph
->n
; ++i
) {
1797 struct isl_sched_node
*node
= &graph
->node
[i
];
1798 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1800 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1801 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1804 if (max_constant_term
!= -1)
1805 for (i
= 0; i
< graph
->n
; ++i
) {
1806 struct isl_sched_node
*node
= &graph
->node
[i
];
1807 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1810 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1811 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1812 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1815 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1817 if (add_all_validity_constraints(graph
) < 0)
1819 if (add_all_proximity_constraints(graph
) < 0)
1825 /* Analyze the conflicting constraint found by
1826 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1827 * constraint of one of the edges between distinct nodes, living, moreover
1828 * in distinct SCCs, then record the source and sink SCC as this may
1829 * be a good place to cut between SCCs.
1831 static int check_conflict(int con
, void *user
)
1834 struct isl_sched_graph
*graph
= user
;
1836 if (graph
->src_scc
>= 0)
1839 con
-= graph
->lp
->n_eq
;
1841 if (con
>= graph
->lp
->n_ineq
)
1844 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1845 if (!graph
->edge
[i
].validity
)
1847 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1849 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1851 if (graph
->edge
[i
].start
> con
)
1853 if (graph
->edge
[i
].end
<= con
)
1855 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1856 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1862 /* Check whether the next schedule row of the given node needs to be
1863 * non-trivial. Lower-dimensional domains may have some trivial rows,
1864 * but as soon as the number of remaining required non-trivial rows
1865 * is as large as the number or remaining rows to be computed,
1866 * all remaining rows need to be non-trivial.
1868 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1870 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1873 /* Solve the ILP problem constructed in setup_lp.
1874 * For each node such that all the remaining rows of its schedule
1875 * need to be non-trivial, we construct a non-triviality region.
1876 * This region imposes that the next row is independent of previous rows.
1877 * In particular the coefficients c_i_x are represented by t_i_x
1878 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1879 * its first columns span the rows of the previously computed part
1880 * of the schedule. The non-triviality region enforces that at least
1881 * one of the remaining components of t_i_x is non-zero, i.e.,
1882 * that the new schedule row depends on at least one of the remaining
1885 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1891 for (i
= 0; i
< graph
->n
; ++i
) {
1892 struct isl_sched_node
*node
= &graph
->node
[i
];
1893 int skip
= node
->rank
;
1894 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1895 if (needs_row(graph
, node
))
1896 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1898 graph
->region
[i
].len
= 0;
1900 lp
= isl_basic_set_copy(graph
->lp
);
1901 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1902 graph
->region
, &check_conflict
, graph
);
1906 /* Update the schedules of all nodes based on the given solution
1907 * of the LP problem.
1908 * The new row is added to the current band.
1909 * All possibly negative coefficients are encoded as a difference
1910 * of two non-negative variables, so we need to perform the subtraction
1911 * here. Moreover, if use_cmap is set, then the solution does
1912 * not refer to the actual coefficients c_i_x, but instead to variables
1913 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1914 * In this case, we then also need to perform this multiplication
1915 * to obtain the values of c_i_x.
1917 * If check_zero is set, then the first two coordinates of sol are
1918 * assumed to correspond to the dependence distance. If these two
1919 * coordinates are zero, then the corresponding scheduling dimension
1920 * is marked as being zero distance.
1922 static int update_schedule(struct isl_sched_graph
*graph
,
1923 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1927 isl_vec
*csol
= NULL
;
1932 isl_die(sol
->ctx
, isl_error_internal
,
1933 "no solution found", goto error
);
1934 if (graph
->n_total_row
>= graph
->max_row
)
1935 isl_die(sol
->ctx
, isl_error_internal
,
1936 "too many schedule rows", goto error
);
1939 zero
= isl_int_is_zero(sol
->el
[1]) &&
1940 isl_int_is_zero(sol
->el
[2]);
1942 for (i
= 0; i
< graph
->n
; ++i
) {
1943 struct isl_sched_node
*node
= &graph
->node
[i
];
1944 int pos
= node
->start
;
1945 int row
= isl_mat_rows(node
->sched
);
1948 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1952 isl_map_free(node
->sched_map
);
1953 node
->sched_map
= NULL
;
1954 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1957 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1959 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1960 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1961 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1962 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1963 for (j
= 0; j
< node
->nparam
; ++j
)
1964 node
->sched
= isl_mat_set_element(node
->sched
,
1965 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1966 for (j
= 0; j
< node
->nvar
; ++j
)
1967 isl_int_set(csol
->el
[j
],
1968 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1970 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1974 for (j
= 0; j
< node
->nvar
; ++j
)
1975 node
->sched
= isl_mat_set_element(node
->sched
,
1976 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1977 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1978 node
->zero
[graph
->n_total_row
] = zero
;
1984 graph
->n_total_row
++;
1993 /* Convert row "row" of node->sched into an isl_aff living in "ls"
1994 * and return this isl_aff.
1996 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
1997 struct isl_sched_node
*node
, int row
)
2005 aff
= isl_aff_zero_on_domain(ls
);
2006 isl_mat_get_element(node
->sched
, row
, 0, &v
);
2007 aff
= isl_aff_set_constant(aff
, v
);
2008 for (j
= 0; j
< node
->nparam
; ++j
) {
2009 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
2010 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
2012 for (j
= 0; j
< node
->nvar
; ++j
) {
2013 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
2014 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
2022 /* Convert node->sched into a multi_aff and return this multi_aff.
2024 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
2025 struct isl_sched_node
*node
)
2029 isl_local_space
*ls
;
2034 nrow
= isl_mat_rows(node
->sched
);
2035 ncol
= isl_mat_cols(node
->sched
) - 1;
2036 space
= isl_space_from_domain(isl_space_copy(node
->dim
));
2037 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
2038 ma
= isl_multi_aff_zero(space
);
2039 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
2041 for (i
= 0; i
< nrow
; ++i
) {
2042 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
2043 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
2046 isl_local_space_free(ls
);
2051 /* Convert node->sched into a map and return this map.
2053 * The result is cached in node->sched_map, which needs to be released
2054 * whenever node->sched is updated.
2056 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
2058 if (!node
->sched_map
) {
2061 ma
= node_extract_schedule_multi_aff(node
);
2062 node
->sched_map
= isl_map_from_multi_aff(ma
);
2065 return isl_map_copy(node
->sched_map
);
2068 /* Construct a map that can be used to update dependence relation
2069 * based on the current schedule.
2070 * That is, construct a map expressing that source and sink
2071 * are executed within the same iteration of the current schedule.
2072 * This map can then be intersected with the dependence relation.
2073 * This is not the most efficient way, but this shouldn't be a critical
2076 static __isl_give isl_map
*specializer(struct isl_sched_node
*src
,
2077 struct isl_sched_node
*dst
)
2079 isl_map
*src_sched
, *dst_sched
;
2081 src_sched
= node_extract_schedule(src
);
2082 dst_sched
= node_extract_schedule(dst
);
2083 return isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
2086 /* Intersect the domains of the nested relations in domain and range
2087 * of "umap" with "map".
2089 static __isl_give isl_union_map
*intersect_domains(
2090 __isl_take isl_union_map
*umap
, __isl_keep isl_map
*map
)
2092 isl_union_set
*uset
;
2094 umap
= isl_union_map_zip(umap
);
2095 uset
= isl_union_set_from_set(isl_map_wrap(isl_map_copy(map
)));
2096 umap
= isl_union_map_intersect_domain(umap
, uset
);
2097 umap
= isl_union_map_zip(umap
);
2101 /* Update the dependence relation of the given edge based
2102 * on the current schedule.
2103 * If the dependence is carried completely by the current schedule, then
2104 * it is removed from the edge_tables. It is kept in the list of edges
2105 * as otherwise all edge_tables would have to be recomputed.
2107 static int update_edge(struct isl_sched_graph
*graph
,
2108 struct isl_sched_edge
*edge
)
2112 id
= specializer(edge
->src
, edge
->dst
);
2113 edge
->map
= isl_map_intersect(edge
->map
, isl_map_copy(id
));
2117 if (edge
->tagged_condition
) {
2118 edge
->tagged_condition
=
2119 intersect_domains(edge
->tagged_condition
, id
);
2120 if (!edge
->tagged_condition
)
2123 if (edge
->tagged_validity
) {
2124 edge
->tagged_validity
=
2125 intersect_domains(edge
->tagged_validity
, id
);
2126 if (!edge
->tagged_validity
)
2131 if (isl_map_plain_is_empty(edge
->map
))
2132 graph_remove_edge(graph
, edge
);
2140 /* Update the dependence relations of all edges based on the current schedule.
2142 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2146 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
2147 if (update_edge(graph
, &graph
->edge
[i
]) < 0)
2154 static void next_band(struct isl_sched_graph
*graph
)
2156 graph
->band_start
= graph
->n_total_row
;
2160 /* Topologically sort statements mapped to the same schedule iteration
2161 * and add a row to the schedule corresponding to this order.
2163 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2170 if (update_edges(ctx
, graph
) < 0)
2173 if (graph
->n_edge
== 0)
2176 if (detect_sccs(ctx
, graph
) < 0)
2179 if (graph
->n_total_row
>= graph
->max_row
)
2180 isl_die(ctx
, isl_error_internal
,
2181 "too many schedule rows", return -1);
2183 for (i
= 0; i
< graph
->n
; ++i
) {
2184 struct isl_sched_node
*node
= &graph
->node
[i
];
2185 int row
= isl_mat_rows(node
->sched
);
2186 int cols
= isl_mat_cols(node
->sched
);
2188 isl_map_free(node
->sched_map
);
2189 node
->sched_map
= NULL
;
2190 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2193 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2195 for (j
= 1; j
< cols
; ++j
)
2196 node
->sched
= isl_mat_set_element_si(node
->sched
,
2198 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2201 graph
->n_total_row
++;
2207 /* Construct an isl_schedule based on the computed schedule stored
2208 * in graph and with parameters specified by dim.
2210 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
2211 __isl_take isl_space
*dim
)
2215 isl_schedule
*sched
= NULL
;
2220 ctx
= isl_space_get_ctx(dim
);
2221 sched
= isl_calloc(ctx
, struct isl_schedule
,
2222 sizeof(struct isl_schedule
) +
2223 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
2228 sched
->n
= graph
->n
;
2229 sched
->n_band
= graph
->n_band
;
2230 sched
->n_total_row
= graph
->n_total_row
;
2232 for (i
= 0; i
< sched
->n
; ++i
) {
2234 int *band_end
, *band_id
, *zero
;
2236 sched
->node
[i
].sched
=
2237 node_extract_schedule_multi_aff(&graph
->node
[i
]);
2238 if (!sched
->node
[i
].sched
)
2241 sched
->node
[i
].n_band
= graph
->n_band
;
2242 if (graph
->n_band
== 0)
2245 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
2246 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
2247 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
2248 sched
->node
[i
].band_end
= band_end
;
2249 sched
->node
[i
].band_id
= band_id
;
2250 sched
->node
[i
].zero
= zero
;
2251 if (!band_end
|| !band_id
|| !zero
)
2254 for (r
= 0; r
< graph
->n_total_row
; ++r
)
2255 zero
[r
] = graph
->node
[i
].zero
[r
];
2256 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
2257 if (graph
->node
[i
].band
[r
] == b
)
2260 if (graph
->node
[i
].band
[r
] == -1)
2263 if (r
== graph
->n_total_row
)
2265 sched
->node
[i
].n_band
= b
;
2266 for (--b
; b
>= 0; --b
)
2267 band_id
[b
] = graph
->node
[i
].band_id
[b
];
2274 isl_space_free(dim
);
2275 isl_schedule_free(sched
);
2279 /* Copy nodes that satisfy node_pred from the src dependence graph
2280 * to the dst dependence graph.
2282 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2283 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2288 for (i
= 0; i
< src
->n
; ++i
) {
2289 if (!node_pred(&src
->node
[i
], data
))
2291 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
2292 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
2293 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
2294 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2295 dst
->node
[dst
->n
].sched_map
=
2296 isl_map_copy(src
->node
[i
].sched_map
);
2297 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
2298 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
2299 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
2306 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2307 * to the dst dependence graph.
2308 * If the source or destination node of the edge is not in the destination
2309 * graph, then it must be a backward proximity edge and it should simply
2312 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2313 struct isl_sched_graph
*src
,
2314 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2317 enum isl_edge_type t
;
2320 for (i
= 0; i
< src
->n_edge
; ++i
) {
2321 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2323 isl_union_map
*tagged_condition
;
2324 isl_union_map
*tagged_validity
;
2325 struct isl_sched_node
*dst_src
, *dst_dst
;
2327 if (!edge_pred(edge
, data
))
2330 if (isl_map_plain_is_empty(edge
->map
))
2333 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
2334 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
2335 if (!dst_src
|| !dst_dst
) {
2336 if (edge
->validity
|| edge
->conditional_validity
)
2337 isl_die(ctx
, isl_error_internal
,
2338 "backward (conditional) validity edge",
2343 map
= isl_map_copy(edge
->map
);
2344 tagged_condition
= isl_union_map_copy(edge
->tagged_condition
);
2345 tagged_validity
= isl_union_map_copy(edge
->tagged_validity
);
2347 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2348 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2349 dst
->edge
[dst
->n_edge
].map
= map
;
2350 dst
->edge
[dst
->n_edge
].tagged_condition
= tagged_condition
;
2351 dst
->edge
[dst
->n_edge
].tagged_validity
= tagged_validity
;
2352 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2353 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2354 dst
->edge
[dst
->n_edge
].condition
= edge
->condition
;
2355 dst
->edge
[dst
->n_edge
].conditional_validity
=
2356 edge
->conditional_validity
;
2359 if (edge
->tagged_condition
&& !tagged_condition
)
2361 if (edge
->tagged_validity
&& !tagged_validity
)
2364 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2366 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2368 if (graph_edge_table_add(ctx
, dst
, t
,
2369 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2377 /* Given a "src" dependence graph that contains the nodes from "dst"
2378 * that satisfy node_pred, copy the schedule computed in "src"
2379 * for those nodes back to "dst".
2381 static int copy_schedule(struct isl_sched_graph
*dst
,
2382 struct isl_sched_graph
*src
,
2383 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2388 for (i
= 0; i
< dst
->n
; ++i
) {
2389 if (!node_pred(&dst
->node
[i
], data
))
2391 isl_mat_free(dst
->node
[i
].sched
);
2392 isl_map_free(dst
->node
[i
].sched_map
);
2393 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
2394 dst
->node
[i
].sched_map
=
2395 isl_map_copy(src
->node
[src
->n
].sched_map
);
2399 dst
->max_row
= src
->max_row
;
2400 dst
->n_total_row
= src
->n_total_row
;
2401 dst
->n_band
= src
->n_band
;
2406 /* Compute the maximal number of variables over all nodes.
2407 * This is the maximal number of linearly independent schedule
2408 * rows that we need to compute.
2409 * Just in case we end up in a part of the dependence graph
2410 * with only lower-dimensional domains, we make sure we will
2411 * compute the required amount of extra linearly independent rows.
2413 static int compute_maxvar(struct isl_sched_graph
*graph
)
2418 for (i
= 0; i
< graph
->n
; ++i
) {
2419 struct isl_sched_node
*node
= &graph
->node
[i
];
2422 if (node_update_cmap(node
) < 0)
2424 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2425 if (nvar
> graph
->maxvar
)
2426 graph
->maxvar
= nvar
;
2432 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2433 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2435 /* Compute a schedule for a subgraph of "graph". In particular, for
2436 * the graph composed of nodes that satisfy node_pred and edges that
2437 * that satisfy edge_pred. The caller should precompute the number
2438 * of nodes and edges that satisfy these predicates and pass them along
2439 * as "n" and "n_edge".
2440 * If the subgraph is known to consist of a single component, then wcc should
2441 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2442 * Otherwise, we call compute_schedule, which will check whether the subgraph
2445 static int compute_sub_schedule(isl_ctx
*ctx
,
2446 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2447 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2448 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2451 struct isl_sched_graph split
= { 0 };
2454 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2456 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2458 if (graph_init_table(ctx
, &split
) < 0)
2460 for (t
= 0; t
<= isl_edge_last
; ++t
)
2461 split
.max_edge
[t
] = graph
->max_edge
[t
];
2462 if (graph_init_edge_tables(ctx
, &split
) < 0)
2464 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2466 split
.n_row
= graph
->n_row
;
2467 split
.max_row
= graph
->max_row
;
2468 split
.n_total_row
= graph
->n_total_row
;
2469 split
.n_band
= graph
->n_band
;
2470 split
.band_start
= graph
->band_start
;
2472 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2474 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2477 copy_schedule(graph
, &split
, node_pred
, data
);
2479 graph_free(ctx
, &split
);
2482 graph_free(ctx
, &split
);
2486 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2488 return node
->scc
== scc
;
2491 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2493 return node
->scc
<= scc
;
2496 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2498 return node
->scc
>= scc
;
2501 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2503 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2506 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2508 return edge
->dst
->scc
<= scc
;
2511 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2513 return edge
->src
->scc
>= scc
;
2516 /* Pad the schedules of all nodes with zero rows such that in the end
2517 * they all have graph->n_total_row rows.
2518 * The extra rows don't belong to any band, so they get assigned band number -1.
2520 static int pad_schedule(struct isl_sched_graph
*graph
)
2524 for (i
= 0; i
< graph
->n
; ++i
) {
2525 struct isl_sched_node
*node
= &graph
->node
[i
];
2526 int row
= isl_mat_rows(node
->sched
);
2527 if (graph
->n_total_row
> row
) {
2528 isl_map_free(node
->sched_map
);
2529 node
->sched_map
= NULL
;
2531 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2532 graph
->n_total_row
- row
);
2535 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2542 /* Reset the current band by dropping all its schedule rows.
2544 static int reset_band(struct isl_sched_graph
*graph
)
2549 drop
= graph
->n_total_row
- graph
->band_start
;
2550 graph
->n_total_row
-= drop
;
2551 graph
->n_row
-= drop
;
2553 for (i
= 0; i
< graph
->n
; ++i
) {
2554 struct isl_sched_node
*node
= &graph
->node
[i
];
2556 isl_map_free(node
->sched_map
);
2557 node
->sched_map
= NULL
;
2559 node
->sched
= isl_mat_drop_rows(node
->sched
,
2560 graph
->band_start
, drop
);
2569 /* Split the current graph into two parts and compute a schedule for each
2570 * part individually. In particular, one part consists of all SCCs up
2571 * to and including graph->src_scc, while the other part contains the other
2574 * The split is enforced in the schedule by constant rows with two different
2575 * values (0 and 1). These constant rows replace the previously computed rows
2576 * in the current band.
2577 * It would be possible to reuse them as the first rows in the next
2578 * band, but recomputing them may result in better rows as we are looking
2579 * at a smaller part of the dependence graph.
2580 * compute_split_schedule is only called when no zero-distance schedule row
2581 * could be found on the entire graph, so we wark the splitting row as
2582 * non zero-distance.
2584 * The band_id of the second group is set to n, where n is the number
2585 * of nodes in the first group. This ensures that the band_ids over
2586 * the two groups remain disjoint, even if either or both of the two
2587 * groups contain independent components.
2589 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2591 int i
, j
, n
, e1
, e2
;
2592 int n_total_row
, orig_total_row
;
2593 int n_band
, orig_band
;
2595 if (graph
->n_total_row
>= graph
->max_row
)
2596 isl_die(ctx
, isl_error_internal
,
2597 "too many schedule rows", return -1);
2599 if (reset_band(graph
) < 0)
2603 for (i
= 0; i
< graph
->n
; ++i
) {
2604 struct isl_sched_node
*node
= &graph
->node
[i
];
2605 int row
= isl_mat_rows(node
->sched
);
2606 int cols
= isl_mat_cols(node
->sched
);
2607 int before
= node
->scc
<= graph
->src_scc
;
2612 isl_map_free(node
->sched_map
);
2613 node
->sched_map
= NULL
;
2614 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2617 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2619 for (j
= 1; j
< cols
; ++j
)
2620 node
->sched
= isl_mat_set_element_si(node
->sched
,
2622 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2623 node
->zero
[graph
->n_total_row
] = 0;
2627 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2628 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2630 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2634 graph
->n_total_row
++;
2637 for (i
= 0; i
< graph
->n
; ++i
) {
2638 struct isl_sched_node
*node
= &graph
->node
[i
];
2639 if (node
->scc
> graph
->src_scc
)
2640 node
->band_id
[graph
->n_band
] = n
;
2643 orig_total_row
= graph
->n_total_row
;
2644 orig_band
= graph
->n_band
;
2645 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2646 &node_scc_at_most
, &edge_dst_scc_at_most
,
2647 graph
->src_scc
, 0) < 0)
2649 n_total_row
= graph
->n_total_row
;
2650 graph
->n_total_row
= orig_total_row
;
2651 n_band
= graph
->n_band
;
2652 graph
->n_band
= orig_band
;
2653 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2654 &node_scc_at_least
, &edge_src_scc_at_least
,
2655 graph
->src_scc
+ 1, 0) < 0)
2657 if (n_total_row
> graph
->n_total_row
)
2658 graph
->n_total_row
= n_total_row
;
2659 if (n_band
> graph
->n_band
)
2660 graph
->n_band
= n_band
;
2662 return pad_schedule(graph
);
2665 /* Compute the next band of the schedule after updating the dependence
2666 * relations based on the the current schedule.
2668 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2670 if (update_edges(ctx
, graph
) < 0)
2674 return compute_schedule(ctx
, graph
);
2677 /* Add constraints to graph->lp that force the dependence "map" (which
2678 * is part of the dependence relation of "edge")
2679 * to be respected and attempt to carry it, where the edge is one from
2680 * a node j to itself. "pos" is the sequence number of the given map.
2681 * That is, add constraints that enforce
2683 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2684 * = c_j_x (y - x) >= e_i
2686 * for each (x,y) in R.
2687 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2688 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2689 * with each coefficient in c_j_x represented as a pair of non-negative
2692 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2693 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2696 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2698 isl_dim_map
*dim_map
;
2699 isl_basic_set
*coef
;
2700 struct isl_sched_node
*node
= edge
->src
;
2702 coef
= intra_coefficients(graph
, map
);
2706 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2708 total
= isl_basic_set_total_dim(graph
->lp
);
2709 dim_map
= isl_dim_map_alloc(ctx
, total
);
2710 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2711 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2712 isl_space_dim(dim
, isl_dim_set
), 1,
2714 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2715 isl_space_dim(dim
, isl_dim_set
), 1,
2717 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2718 coef
->n_eq
, coef
->n_ineq
);
2719 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2721 isl_space_free(dim
);
2726 /* Add constraints to graph->lp that force the dependence "map" (which
2727 * is part of the dependence relation of "edge")
2728 * to be respected and attempt to carry it, where the edge is one from
2729 * node j to node k. "pos" is the sequence number of the given map.
2730 * That is, add constraints that enforce
2732 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2734 * for each (x,y) in R.
2735 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2736 * of valid constraints for R and then plug in
2737 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2738 * with each coefficient (except e_i, c_k_0 and c_j_0)
2739 * represented as a pair of non-negative coefficients.
2741 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2742 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2745 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2747 isl_dim_map
*dim_map
;
2748 isl_basic_set
*coef
;
2749 struct isl_sched_node
*src
= edge
->src
;
2750 struct isl_sched_node
*dst
= edge
->dst
;
2752 coef
= inter_coefficients(graph
, map
);
2756 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2758 total
= isl_basic_set_total_dim(graph
->lp
);
2759 dim_map
= isl_dim_map_alloc(ctx
, total
);
2761 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2763 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2764 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2765 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2766 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2767 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2769 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2770 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2773 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2774 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2775 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2776 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2777 isl_space_dim(dim
, isl_dim_set
), 1,
2779 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2780 isl_space_dim(dim
, isl_dim_set
), 1,
2783 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2784 coef
->n_eq
, coef
->n_ineq
);
2785 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2787 isl_space_free(dim
);
2792 /* Add constraints to graph->lp that force all (conditional) validity
2793 * dependences to be respected and attempt to carry them.
2795 static int add_all_constraints(struct isl_sched_graph
*graph
)
2801 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2802 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2804 if (!edge
->validity
&& !edge
->conditional_validity
)
2807 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2808 isl_basic_map
*bmap
;
2811 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2812 map
= isl_map_from_basic_map(bmap
);
2814 if (edge
->src
== edge
->dst
&&
2815 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2817 if (edge
->src
!= edge
->dst
&&
2818 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2827 /* Count the number of equality and inequality constraints
2828 * that will be added to the carry_lp problem.
2829 * We count each edge exactly once.
2831 static int count_all_constraints(struct isl_sched_graph
*graph
,
2832 int *n_eq
, int *n_ineq
)
2836 *n_eq
= *n_ineq
= 0;
2837 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2838 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2839 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2840 isl_basic_map
*bmap
;
2843 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2844 map
= isl_map_from_basic_map(bmap
);
2846 if (count_map_constraints(graph
, edge
, map
,
2847 n_eq
, n_ineq
, 1) < 0)
2855 /* Construct an LP problem for finding schedule coefficients
2856 * such that the schedule carries as many dependences as possible.
2857 * In particular, for each dependence i, we bound the dependence distance
2858 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2859 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2860 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2861 * Note that if the dependence relation is a union of basic maps,
2862 * then we have to consider each basic map individually as it may only
2863 * be possible to carry the dependences expressed by some of those
2864 * basic maps and not all off them.
2865 * Below, we consider each of those basic maps as a separate "edge".
2867 * All variables of the LP are non-negative. The actual coefficients
2868 * may be negative, so each coefficient is represented as the difference
2869 * of two non-negative variables. The negative part always appears
2870 * immediately before the positive part.
2871 * Other than that, the variables have the following order
2873 * - sum of (1 - e_i) over all edges
2874 * - sum of positive and negative parts of all c_n coefficients
2875 * (unconstrained when computing non-parametric schedules)
2876 * - sum of positive and negative parts of all c_x coefficients
2881 * - positive and negative parts of c_i_n (if parametric)
2882 * - positive and negative parts of c_i_x
2884 * The constraints are those from the (validity) edges plus three equalities
2885 * to express the sums and n_edge inequalities to express e_i <= 1.
2887 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2897 for (i
= 0; i
< graph
->n_edge
; ++i
)
2898 n_edge
+= graph
->edge
[i
].map
->n
;
2901 for (i
= 0; i
< graph
->n
; ++i
) {
2902 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2903 node
->start
= total
;
2904 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2907 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2909 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2912 dim
= isl_space_set_alloc(ctx
, 0, total
);
2913 isl_basic_set_free(graph
->lp
);
2916 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2917 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2919 k
= isl_basic_set_alloc_equality(graph
->lp
);
2922 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2923 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2924 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2925 for (i
= 0; i
< n_edge
; ++i
)
2926 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2928 k
= isl_basic_set_alloc_equality(graph
->lp
);
2931 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2932 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2933 for (i
= 0; i
< graph
->n
; ++i
) {
2934 int pos
= 1 + graph
->node
[i
].start
+ 1;
2936 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2937 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2940 k
= isl_basic_set_alloc_equality(graph
->lp
);
2943 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2944 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2945 for (i
= 0; i
< graph
->n
; ++i
) {
2946 struct isl_sched_node
*node
= &graph
->node
[i
];
2947 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2949 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2950 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2953 for (i
= 0; i
< n_edge
; ++i
) {
2954 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2957 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2958 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2959 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2962 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2964 if (add_all_constraints(graph
) < 0)
2970 /* If the schedule_split_scaled option is set and if the linear
2971 * parts of the scheduling rows for all nodes in the graphs have
2972 * non-trivial common divisor, then split off the constant term
2973 * from the linear part.
2974 * The constant term is then placed in a separate band and
2975 * the linear part is reduced.
2977 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2983 if (!ctx
->opt
->schedule_split_scaled
)
2988 if (graph
->n_total_row
>= graph
->max_row
)
2989 isl_die(ctx
, isl_error_internal
,
2990 "too many schedule rows", return -1);
2993 isl_int_init(gcd_i
);
2995 isl_int_set_si(gcd
, 0);
2997 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2999 for (i
= 0; i
< graph
->n
; ++i
) {
3000 struct isl_sched_node
*node
= &graph
->node
[i
];
3001 int cols
= isl_mat_cols(node
->sched
);
3003 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
3004 isl_int_gcd(gcd
, gcd
, gcd_i
);
3007 isl_int_clear(gcd_i
);
3009 if (isl_int_cmp_si(gcd
, 1) <= 0) {
3016 for (i
= 0; i
< graph
->n
; ++i
) {
3017 struct isl_sched_node
*node
= &graph
->node
[i
];
3019 isl_map_free(node
->sched_map
);
3020 node
->sched_map
= NULL
;
3021 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3024 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
3025 node
->sched
->row
[row
][0], gcd
);
3026 isl_int_fdiv_q(node
->sched
->row
[row
][0],
3027 node
->sched
->row
[row
][0], gcd
);
3028 isl_int_mul(node
->sched
->row
[row
][0],
3029 node
->sched
->row
[row
][0], gcd
);
3030 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
3033 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3036 graph
->n_total_row
++;
3045 static int compute_component_schedule(isl_ctx
*ctx
,
3046 struct isl_sched_graph
*graph
);
3048 /* Is the schedule row "sol" trivial on node "node"?
3049 * That is, is the solution zero on the dimensions orthogonal to
3050 * the previously found solutions?
3051 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3053 * Each coefficient is represented as the difference between
3054 * two non-negative values in "sol". "sol" has been computed
3055 * in terms of the original iterators (i.e., without use of cmap).
3056 * We construct the schedule row s and write it as a linear
3057 * combination of (linear combinations of) previously computed schedule rows.
3058 * s = Q c or c = U s.
3059 * If the final entries of c are all zero, then the solution is trivial.
3061 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
3071 if (node
->nvar
== node
->rank
)
3074 ctx
= isl_vec_get_ctx(sol
);
3075 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
3079 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
3081 for (i
= 0; i
< node
->nvar
; ++i
)
3082 isl_int_sub(node_sol
->el
[i
],
3083 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
3085 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
3090 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
3091 node
->nvar
- node
->rank
) == -1;
3093 isl_vec_free(node_sol
);
3098 /* Is the schedule row "sol" trivial on any node where it should
3100 * "sol" has been computed in terms of the original iterators
3101 * (i.e., without use of cmap).
3102 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3104 static int is_any_trivial(struct isl_sched_graph
*graph
,
3105 __isl_keep isl_vec
*sol
)
3109 for (i
= 0; i
< graph
->n
; ++i
) {
3110 struct isl_sched_node
*node
= &graph
->node
[i
];
3113 if (!needs_row(graph
, node
))
3115 trivial
= is_trivial(node
, sol
);
3116 if (trivial
< 0 || trivial
)
3123 /* Construct a schedule row for each node such that as many dependences
3124 * as possible are carried and then continue with the next band.
3126 * If the computed schedule row turns out to be trivial on one or
3127 * more nodes where it should not be trivial, then we throw it away
3128 * and try again on each component separately.
3130 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3139 for (i
= 0; i
< graph
->n_edge
; ++i
)
3140 n_edge
+= graph
->edge
[i
].map
->n
;
3142 if (setup_carry_lp(ctx
, graph
) < 0)
3145 lp
= isl_basic_set_copy(graph
->lp
);
3146 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
3150 if (sol
->size
== 0) {
3152 isl_die(ctx
, isl_error_internal
,
3153 "error in schedule construction", return -1);
3156 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
3157 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
3159 isl_die(ctx
, isl_error_unknown
,
3160 "unable to carry dependences", return -1);
3163 trivial
= is_any_trivial(graph
, sol
);
3165 sol
= isl_vec_free(sol
);
3166 } else if (trivial
) {
3169 return compute_component_schedule(ctx
, graph
);
3170 isl_die(ctx
, isl_error_unknown
,
3171 "unable to construct non-trivial solution", return -1);
3174 if (update_schedule(graph
, sol
, 0, 0) < 0)
3177 if (split_scaled(ctx
, graph
) < 0)
3180 return compute_next_band(ctx
, graph
);
3183 /* Are there any (non-empty) (conditional) validity edges in the graph?
3185 static int has_validity_edges(struct isl_sched_graph
*graph
)
3189 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3192 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
3197 if (graph
->edge
[i
].validity
||
3198 graph
->edge
[i
].conditional_validity
)
3205 /* Should we apply a Feautrier step?
3206 * That is, did the user request the Feautrier algorithm and are
3207 * there any validity dependences (left)?
3209 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3211 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
3214 return has_validity_edges(graph
);
3217 /* Compute a schedule for a connected dependence graph using Feautrier's
3218 * multi-dimensional scheduling algorithm.
3219 * The original algorithm is described in [1].
3220 * The main idea is to minimize the number of scheduling dimensions, by
3221 * trying to satisfy as many dependences as possible per scheduling dimension.
3223 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3224 * Problem, Part II: Multi-Dimensional Time.
3225 * In Intl. Journal of Parallel Programming, 1992.
3227 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
3228 struct isl_sched_graph
*graph
)
3230 return carry_dependences(ctx
, graph
);
3233 /* Turn off the "local" bit on all (condition) edges.
3235 static void clear_local_edges(struct isl_sched_graph
*graph
)
3239 for (i
= 0; i
< graph
->n_edge
; ++i
)
3240 if (graph
->edge
[i
].condition
)
3241 graph
->edge
[i
].local
= 0;
3244 /* Does "graph" have both condition and conditional validity edges?
3246 static int need_condition_check(struct isl_sched_graph
*graph
)
3249 int any_condition
= 0;
3250 int any_conditional_validity
= 0;
3252 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3253 if (graph
->edge
[i
].condition
)
3255 if (graph
->edge
[i
].conditional_validity
)
3256 any_conditional_validity
= 1;
3259 return any_condition
&& any_conditional_validity
;
3262 /* Extract the final schedule row as a map with the iteration domain
3263 * of "node" as domain.
3265 static __isl_give isl_map
*final_row(struct isl_sched_node
*node
)
3267 isl_local_space
*ls
;
3271 row
= isl_mat_rows(node
->sched
) - 1;
3272 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
3273 aff
= extract_schedule_row(ls
, node
, row
);
3274 return isl_map_from_aff(aff
);
3277 /* Is the conditional validity dependence in the edge with index "edge_index"
3278 * violated by the latest (i.e., final) row of the schedule?
3279 * That is, is i scheduled after j
3280 * for any conditional validity dependence i -> j?
3282 static int is_violated(struct isl_sched_graph
*graph
, int edge_index
)
3284 isl_map
*src_sched
, *dst_sched
, *map
;
3285 struct isl_sched_edge
*edge
= &graph
->edge
[edge_index
];
3288 src_sched
= final_row(edge
->src
);
3289 dst_sched
= final_row(edge
->dst
);
3290 map
= isl_map_copy(edge
->map
);
3291 map
= isl_map_apply_domain(map
, src_sched
);
3292 map
= isl_map_apply_range(map
, dst_sched
);
3293 map
= isl_map_order_gt(map
, isl_dim_in
, 0, isl_dim_out
, 0);
3294 empty
= isl_map_is_empty(map
);
3303 /* Does the domain of "umap" intersect "uset"?
3305 static int domain_intersects(__isl_keep isl_union_map
*umap
,
3306 __isl_keep isl_union_set
*uset
)
3310 umap
= isl_union_map_copy(umap
);
3311 umap
= isl_union_map_intersect_domain(umap
, isl_union_set_copy(uset
));
3312 empty
= isl_union_map_is_empty(umap
);
3313 isl_union_map_free(umap
);
3315 return empty
< 0 ? -1 : !empty
;
3318 /* Does the range of "umap" intersect "uset"?
3320 static int range_intersects(__isl_keep isl_union_map
*umap
,
3321 __isl_keep isl_union_set
*uset
)
3325 umap
= isl_union_map_copy(umap
);
3326 umap
= isl_union_map_intersect_range(umap
, isl_union_set_copy(uset
));
3327 empty
= isl_union_map_is_empty(umap
);
3328 isl_union_map_free(umap
);
3330 return empty
< 0 ? -1 : !empty
;
3333 /* Are the condition dependences of "edge" local with respect to
3334 * the current schedule?
3336 * That is, are domain and range of the condition dependences mapped
3337 * to the same point?
3339 * In other words, is the condition false?
3341 static int is_condition_false(struct isl_sched_edge
*edge
)
3343 isl_union_map
*umap
;
3344 isl_map
*map
, *sched
, *test
;
3347 umap
= isl_union_map_copy(edge
->tagged_condition
);
3348 umap
= isl_union_map_zip(umap
);
3349 umap
= isl_union_set_unwrap(isl_union_map_domain(umap
));
3350 map
= isl_map_from_union_map(umap
);
3352 sched
= node_extract_schedule(edge
->src
);
3353 map
= isl_map_apply_domain(map
, sched
);
3354 sched
= node_extract_schedule(edge
->dst
);
3355 map
= isl_map_apply_range(map
, sched
);
3357 test
= isl_map_identity(isl_map_get_space(map
));
3358 local
= isl_map_is_subset(map
, test
);
3365 /* Does "graph" have any satisfied condition edges that
3366 * are adjacent to the conditional validity constraint with
3367 * domain "conditional_source" and range "conditional_sink"?
3369 * A satisfied condition is one that is not local.
3370 * If a condition was forced to be local already (i.e., marked as local)
3371 * then there is no need to check if it is in fact local.
3373 * Additionally, mark all adjacent condition edges found as local.
3375 static int has_adjacent_true_conditions(struct isl_sched_graph
*graph
,
3376 __isl_keep isl_union_set
*conditional_source
,
3377 __isl_keep isl_union_set
*conditional_sink
)
3382 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3383 int adjacent
, local
;
3384 isl_union_map
*condition
;
3386 if (!graph
->edge
[i
].condition
)
3388 if (graph
->edge
[i
].local
)
3391 condition
= graph
->edge
[i
].tagged_condition
;
3392 adjacent
= domain_intersects(condition
, conditional_sink
);
3393 if (adjacent
>= 0 && !adjacent
)
3394 adjacent
= range_intersects(condition
,
3395 conditional_source
);
3401 graph
->edge
[i
].local
= 1;
3403 local
= is_condition_false(&graph
->edge
[i
]);
3413 /* Are there any violated conditional validity dependences with
3414 * adjacent condition dependences that are not local with respect
3415 * to the current schedule?
3416 * That is, is the conditional validity constraint violated?
3418 * Additionally, mark all those adjacent condition dependences as local.
3419 * We also mark those adjacent condition dependences that were not marked
3420 * as local before, but just happened to be local already. This ensures
3421 * that they remain local if the schedule is recomputed.
3423 * We first collect domain and range of all violated conditional validity
3424 * dependences and then check if there are any adjacent non-local
3425 * condition dependences.
3427 static int has_violated_conditional_constraint(isl_ctx
*ctx
,
3428 struct isl_sched_graph
*graph
)
3432 isl_union_set
*source
, *sink
;
3434 source
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3435 sink
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
3436 for (i
= 0; i
< graph
->n_edge
; ++i
) {
3437 isl_union_set
*uset
;
3438 isl_union_map
*umap
;
3441 if (!graph
->edge
[i
].conditional_validity
)
3444 violated
= is_violated(graph
, i
);
3452 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3453 uset
= isl_union_map_domain(umap
);
3454 source
= isl_union_set_union(source
, uset
);
3455 source
= isl_union_set_coalesce(source
);
3457 umap
= isl_union_map_copy(graph
->edge
[i
].tagged_validity
);
3458 uset
= isl_union_map_range(umap
);
3459 sink
= isl_union_set_union(sink
, uset
);
3460 sink
= isl_union_set_coalesce(sink
);
3464 any
= has_adjacent_true_conditions(graph
, source
, sink
);
3466 isl_union_set_free(source
);
3467 isl_union_set_free(sink
);
3470 isl_union_set_free(source
);
3471 isl_union_set_free(sink
);
3475 /* Compute a schedule for a connected dependence graph.
3476 * We try to find a sequence of as many schedule rows as possible that result
3477 * in non-negative dependence distances (independent of the previous rows
3478 * in the sequence, i.e., such that the sequence is tilable).
3479 * If we can't find any more rows we either
3480 * - split between SCCs and start over (assuming we found an interesting
3481 * pair of SCCs between which to split)
3482 * - continue with the next band (assuming the current band has at least
3484 * - try to carry as many dependences as possible and continue with the next
3487 * If Feautrier's algorithm is selected, we first recursively try to satisfy
3488 * as many validity dependences as possible. When all validity dependences
3489 * are satisfied we extend the schedule to a full-dimensional schedule.
3491 * If we manage to complete the schedule, we finish off by topologically
3492 * sorting the statements based on the remaining dependences.
3494 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
3495 * outermost dimension in the current band to be zero distance. If this
3496 * turns out to be impossible, we fall back on the general scheme above
3497 * and try to carry as many dependences as possible.
3499 * If "graph" contains both condition and conditional validity dependences,
3500 * then we need to check that that the conditional schedule constraint
3501 * is satisfied, i.e., there are no violated conditional validity dependences
3502 * that are adjacent to any non-local condition dependences.
3503 * If there are, then we mark all those adjacent condition dependences
3504 * as local and recompute the current band. Those dependences that
3505 * are marked local will then be forced to be local.
3506 * The initial computation is performed with no dependences marked as local.
3507 * If we are lucky, then there will be no violated conditional validity
3508 * dependences adjacent to any non-local condition dependences.
3509 * Otherwise, we mark some additional condition dependences as local and
3510 * recompute. We continue this process until there are no violations left or
3511 * until we are no longer able to compute a schedule.
3512 * Since there are only a finite number of dependences,
3513 * there will only be a finite number of iterations.
3515 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3517 int init_force_zero
= 0;
3519 int check_conditional
;
3521 if (detect_sccs(ctx
, graph
) < 0)
3523 if (sort_sccs(graph
) < 0)
3526 if (compute_maxvar(graph
) < 0)
3529 if (need_feautrier_step(ctx
, graph
))
3530 return compute_schedule_wcc_feautrier(ctx
, graph
);
3532 clear_local_edges(graph
);
3533 check_conditional
= need_condition_check(graph
);
3535 if (ctx
->opt
->schedule_outer_zero_distance
)
3536 init_force_zero
= 1;
3538 force_zero
= init_force_zero
;
3539 while (graph
->n_row
< graph
->maxvar
) {
3543 graph
->src_scc
= -1;
3544 graph
->dst_scc
= -1;
3546 if (setup_lp(ctx
, graph
, force_zero
) < 0)
3548 sol
= solve_lp(graph
);
3551 if (sol
->size
== 0) {
3553 if (!ctx
->opt
->schedule_maximize_band_depth
&&
3554 graph
->n_total_row
> graph
->band_start
)
3555 return compute_next_band(ctx
, graph
);
3556 if (graph
->src_scc
>= 0)
3557 return compute_split_schedule(ctx
, graph
);
3558 if (graph
->n_total_row
> graph
->band_start
)
3559 return compute_next_band(ctx
, graph
);
3560 return carry_dependences(ctx
, graph
);
3562 if (update_schedule(graph
, sol
, 1, 1) < 0)
3566 if (!check_conditional
)
3568 violated
= has_violated_conditional_constraint(ctx
, graph
);
3573 if (reset_band(graph
) < 0)
3575 force_zero
= init_force_zero
;
3578 if (graph
->n_total_row
> graph
->band_start
)
3580 return sort_statements(ctx
, graph
);
3583 /* Add a row to the schedules that separates the SCCs and move
3586 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3590 if (graph
->n_total_row
>= graph
->max_row
)
3591 isl_die(ctx
, isl_error_internal
,
3592 "too many schedule rows", return -1);
3594 for (i
= 0; i
< graph
->n
; ++i
) {
3595 struct isl_sched_node
*node
= &graph
->node
[i
];
3596 int row
= isl_mat_rows(node
->sched
);
3598 isl_map_free(node
->sched_map
);
3599 node
->sched_map
= NULL
;
3600 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3601 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
3605 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3608 graph
->n_total_row
++;
3614 /* Compute a schedule for each component (identified by node->scc)
3615 * of the dependence graph separately and then combine the results.
3616 * Depending on the setting of schedule_fuse, a component may be
3617 * either weakly or strongly connected.
3619 * The band_id is adjusted such that each component has a separate id.
3620 * Note that the band_id may have already been set to a value different
3621 * from zero by compute_split_schedule.
3623 static int compute_component_schedule(isl_ctx
*ctx
,
3624 struct isl_sched_graph
*graph
)
3628 int n_total_row
, orig_total_row
;
3629 int n_band
, orig_band
;
3631 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
3632 ctx
->opt
->schedule_separate_components
)
3633 if (split_on_scc(ctx
, graph
) < 0)
3637 orig_total_row
= graph
->n_total_row
;
3639 orig_band
= graph
->n_band
;
3640 for (i
= 0; i
< graph
->n
; ++i
)
3641 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
3642 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
3644 for (i
= 0; i
< graph
->n
; ++i
)
3645 if (graph
->node
[i
].scc
== wcc
)
3648 for (i
= 0; i
< graph
->n_edge
; ++i
)
3649 if (graph
->edge
[i
].src
->scc
== wcc
&&
3650 graph
->edge
[i
].dst
->scc
== wcc
)
3653 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
3655 &edge_scc_exactly
, wcc
, 1) < 0)
3657 if (graph
->n_total_row
> n_total_row
)
3658 n_total_row
= graph
->n_total_row
;
3659 graph
->n_total_row
= orig_total_row
;
3660 if (graph
->n_band
> n_band
)
3661 n_band
= graph
->n_band
;
3662 graph
->n_band
= orig_band
;
3665 graph
->n_total_row
= n_total_row
;
3666 graph
->n_band
= n_band
;
3668 return pad_schedule(graph
);
3671 /* Compute a schedule for the given dependence graph.
3672 * We first check if the graph is connected (through validity and conditional
3673 * validity dependences) and, if not, compute a schedule
3674 * for each component separately.
3675 * If schedule_fuse is set to minimal fusion, then we check for strongly
3676 * connected components instead and compute a separate schedule for
3677 * each such strongly connected component.
3679 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3681 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
3682 if (detect_sccs(ctx
, graph
) < 0)
3685 if (detect_wccs(ctx
, graph
) < 0)
3690 return compute_component_schedule(ctx
, graph
);
3692 return compute_schedule_wcc(ctx
, graph
);
3695 /* Compute a schedule on sc->domain that respects the given schedule
3698 * In particular, the schedule respects all the validity dependences.
3699 * If the default isl scheduling algorithm is used, it tries to minimize
3700 * the dependence distances over the proximity dependences.
3701 * If Feautrier's scheduling algorithm is used, the proximity dependence
3702 * distances are only minimized during the extension to a full-dimensional
3705 * If there are any condition and conditional validity dependences,
3706 * then the conditional validity dependences may be violated inside
3707 * a tilable band, provided they have no adjacent non-local
3708 * condition dependences.
3710 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
3711 __isl_take isl_schedule_constraints
*sc
)
3713 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
3714 struct isl_sched_graph graph
= { 0 };
3715 isl_schedule
*sched
;
3716 struct isl_extract_edge_data data
;
3717 enum isl_edge_type i
;
3719 sc
= isl_schedule_constraints_align_params(sc
);
3723 graph
.n
= isl_union_set_n_set(sc
->domain
);
3726 if (graph_alloc(ctx
, &graph
, graph
.n
,
3727 isl_schedule_constraints_n_map(sc
)) < 0)
3729 if (compute_max_row(&graph
, sc
->domain
) < 0)
3733 if (isl_union_set_foreach_set(sc
->domain
, &extract_node
, &graph
) < 0)
3735 if (graph_init_table(ctx
, &graph
) < 0)
3737 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
3738 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
3739 if (graph_init_edge_tables(ctx
, &graph
) < 0)
3742 data
.graph
= &graph
;
3743 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
3745 if (isl_union_map_foreach_map(sc
->constraint
[i
],
3746 &extract_edge
, &data
) < 0)
3750 if (compute_schedule(ctx
, &graph
) < 0)
3754 sched
= extract_schedule(&graph
, isl_union_set_get_space(sc
->domain
));
3756 graph_free(ctx
, &graph
);
3757 isl_schedule_constraints_free(sc
);
3761 graph_free(ctx
, &graph
);
3762 isl_schedule_constraints_free(sc
);
3766 /* Compute a schedule for the given union of domains that respects
3767 * all the validity dependences and minimizes
3768 * the dependence distances over the proximity dependences.
3770 * This function is kept for backward compatibility.
3772 __isl_give isl_schedule
*isl_union_set_compute_schedule(
3773 __isl_take isl_union_set
*domain
,
3774 __isl_take isl_union_map
*validity
,
3775 __isl_take isl_union_map
*proximity
)
3777 isl_schedule_constraints
*sc
;
3779 sc
= isl_schedule_constraints_on_domain(domain
);
3780 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
3781 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
3783 return isl_schedule_constraints_compute_schedule(sc
);
3786 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
3792 if (--sched
->ref
> 0)
3795 for (i
= 0; i
< sched
->n
; ++i
) {
3796 isl_multi_aff_free(sched
->node
[i
].sched
);
3797 free(sched
->node
[i
].band_end
);
3798 free(sched
->node
[i
].band_id
);
3799 free(sched
->node
[i
].zero
);
3801 isl_space_free(sched
->dim
);
3802 isl_band_list_free(sched
->band_forest
);
3807 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
3809 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
3812 /* Set max_out to the maximal number of output dimensions over
3815 static int update_max_out(__isl_take isl_map
*map
, void *user
)
3817 int *max_out
= user
;
3818 int n_out
= isl_map_dim(map
, isl_dim_out
);
3820 if (n_out
> *max_out
)
3827 /* Internal data structure for map_pad_range.
3829 * "max_out" is the maximal schedule dimension.
3830 * "res" collects the results.
3832 struct isl_pad_schedule_map_data
{
3837 /* Pad the range of the given map with zeros to data->max_out and
3838 * then add the result to data->res.
3840 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
3842 struct isl_pad_schedule_map_data
*data
= user
;
3844 int n_out
= isl_map_dim(map
, isl_dim_out
);
3846 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
3847 for (i
= n_out
; i
< data
->max_out
; ++i
)
3848 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
3850 data
->res
= isl_union_map_add_map(data
->res
, map
);
3857 /* Pad the ranges of the maps in the union map with zeros such they all have
3858 * the same dimension.
3860 static __isl_give isl_union_map
*pad_schedule_map(
3861 __isl_take isl_union_map
*umap
)
3863 struct isl_pad_schedule_map_data data
;
3867 if (isl_union_map_n_map(umap
) <= 1)
3871 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
3872 return isl_union_map_free(umap
);
3874 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3875 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
3876 data
.res
= isl_union_map_free(data
.res
);
3878 isl_union_map_free(umap
);
3882 /* Return an isl_union_map of the schedule. If we have already constructed
3883 * a band forest, then this band forest may have been modified so we need
3884 * to extract the isl_union_map from the forest rather than from
3885 * the originally computed schedule. This reconstructed schedule map
3886 * then needs to be padded with zeros to unify the schedule space
3887 * since the result of isl_band_list_get_suffix_schedule may not have
3888 * a unified schedule space.
3890 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
3893 isl_union_map
*umap
;
3898 if (sched
->band_forest
) {
3899 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
3900 return pad_schedule_map(umap
);
3903 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
3904 for (i
= 0; i
< sched
->n
; ++i
) {
3907 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
3908 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
3914 static __isl_give isl_band_list
*construct_band_list(
3915 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3916 int band_nr
, int *parent_active
, int n_active
);
3918 /* Construct an isl_band structure for the band in the given schedule
3919 * with sequence number band_nr for the n_active nodes marked by active.
3920 * If the nodes don't have a band with the given sequence number,
3921 * then a band without members is created.
3923 * Because of the way the schedule is constructed, we know that
3924 * the position of the band inside the schedule of a node is the same
3925 * for all active nodes.
3927 * The partial schedule for the band is created before the children
3928 * are created to that construct_band_list can refer to the partial
3929 * schedule of the parent.
3931 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
3932 __isl_keep isl_band
*parent
,
3933 int band_nr
, int *active
, int n_active
)
3936 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3938 unsigned start
, end
;
3940 band
= isl_band_alloc(ctx
);
3944 band
->schedule
= schedule
;
3945 band
->parent
= parent
;
3947 for (i
= 0; i
< schedule
->n
; ++i
)
3951 if (i
>= schedule
->n
)
3952 isl_die(ctx
, isl_error_internal
,
3953 "band without active statements", goto error
);
3955 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
3956 end
= band_nr
< schedule
->node
[i
].n_band
?
3957 schedule
->node
[i
].band_end
[band_nr
] : start
;
3958 band
->n
= end
- start
;
3960 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
3961 if (band
->n
&& !band
->zero
)
3964 for (j
= 0; j
< band
->n
; ++j
)
3965 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
3967 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
3968 for (i
= 0; i
< schedule
->n
; ++i
) {
3970 isl_pw_multi_aff
*pma
;
3976 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
3977 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3978 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
3979 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
3980 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3981 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
3987 for (i
= 0; i
< schedule
->n
; ++i
)
3988 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
3991 if (i
< schedule
->n
) {
3992 band
->children
= construct_band_list(schedule
, band
,
3993 band_nr
+ 1, active
, n_active
);
3994 if (!band
->children
)
4000 isl_band_free(band
);
4004 /* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
4006 * r is set to a negative value if anything goes wrong.
4008 * c1 stores the result of extract_int.
4009 * c2 is a temporary value used inside cmp_band_in_ancestor.
4010 * t is a temporary value used inside extract_int.
4012 * first and equal are used inside extract_int.
4013 * first is set if we are looking at the first isl_multi_aff inside
4014 * the isl_union_pw_multi_aff.
4015 * equal is set if all the isl_multi_affs have been equal so far.
4017 struct isl_cmp_band_data
{
4028 /* Check if "ma" assigns a constant value.
4029 * Note that this function is only called on isl_multi_affs
4030 * with a single output dimension.
4032 * If "ma" assigns a constant value then we compare it to data->c1
4033 * or assign it to data->c1 if this is the first isl_multi_aff we consider.
4034 * If "ma" does not assign a constant value or if it assigns a value
4035 * that is different from data->c1, then we set data->equal to zero
4036 * and terminate the check.
4038 static int multi_aff_extract_int(__isl_take isl_set
*set
,
4039 __isl_take isl_multi_aff
*ma
, void *user
)
4042 struct isl_cmp_band_data
*data
= user
;
4044 aff
= isl_multi_aff_get_aff(ma
, 0);
4045 data
->r
= isl_aff_is_cst(aff
);
4046 if (data
->r
>= 0 && data
->r
) {
4047 isl_aff_get_constant(aff
, &data
->t
);
4049 isl_int_set(data
->c1
, data
->t
);
4051 } else if (!isl_int_eq(data
->c1
, data
->t
))
4053 } else if (data
->r
>= 0 && !data
->r
)
4058 isl_multi_aff_free(ma
);
4067 /* This function is called for each isl_pw_multi_aff in
4068 * the isl_union_pw_multi_aff checked by extract_int.
4069 * Check all the isl_multi_affs inside "pma".
4071 static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff
*pma
,
4076 r
= isl_pw_multi_aff_foreach_piece(pma
, &multi_aff_extract_int
, user
);
4077 isl_pw_multi_aff_free(pma
);
4082 /* Check if "upma" assigns a single constant value to its domain.
4083 * If so, return 1 and store the result in data->c1.
4086 * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
4087 * means that either an error occurred or that we have broken off the check
4088 * because we already know the result is going to be negative.
4089 * In the latter case, data->equal is set to zero.
4091 static int extract_int(__isl_keep isl_union_pw_multi_aff
*upma
,
4092 struct isl_cmp_band_data
*data
)
4097 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4098 &pw_multi_aff_extract_int
, data
) < 0) {
4104 return !data
->first
&& data
->equal
;
4107 /* Compare "b1" and "b2" based on the parent schedule of their ancestor
4110 * If the parent of "ancestor" also has a single member, then we
4111 * first try to compare the two band based on the partial schedule
4114 * Otherwise, or if the result is inconclusive, we look at the partial schedule
4115 * of "ancestor" itself.
4116 * In particular, we specialize the parent schedule based
4117 * on the domains of the child schedules, check if both assign
4118 * a single constant value and, if so, compare the two constant values.
4119 * If the specialized parent schedules do not assign a constant value,
4120 * then they cannot be used to order the two bands and so in this case
4123 static int cmp_band_in_ancestor(__isl_keep isl_band
*b1
,
4124 __isl_keep isl_band
*b2
, struct isl_cmp_band_data
*data
,
4125 __isl_keep isl_band
*ancestor
)
4127 isl_union_pw_multi_aff
*upma
;
4128 isl_union_set
*domain
;
4134 if (ancestor
->parent
&& ancestor
->parent
->n
== 1) {
4135 r
= cmp_band_in_ancestor(b1
, b2
, data
, ancestor
->parent
);
4142 upma
= isl_union_pw_multi_aff_copy(b1
->pma
);
4143 domain
= isl_union_pw_multi_aff_domain(upma
);
4144 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
4145 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
4146 r
= extract_int(upma
, data
);
4147 isl_union_pw_multi_aff_free(upma
);
4154 isl_int_set(data
->c2
, data
->c1
);
4156 upma
= isl_union_pw_multi_aff_copy(b2
->pma
);
4157 domain
= isl_union_pw_multi_aff_domain(upma
);
4158 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
4159 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
4160 r
= extract_int(upma
, data
);
4161 isl_union_pw_multi_aff_free(upma
);
4168 return isl_int_cmp(data
->c2
, data
->c1
);
4171 /* Compare "a" and "b" based on the parent schedule of their parent.
4173 static int cmp_band(const void *a
, const void *b
, void *user
)
4175 isl_band
*b1
= *(isl_band
* const *) a
;
4176 isl_band
*b2
= *(isl_band
* const *) b
;
4177 struct isl_cmp_band_data
*data
= user
;
4179 return cmp_band_in_ancestor(b1
, b2
, data
, b1
->parent
);
4182 /* Sort the elements in "list" based on the partial schedules of its parent
4183 * (and ancestors). In particular if the parent assigns constant values
4184 * to the domains of the bands in "list", then the elements are sorted
4185 * according to that order.
4186 * This order should be a more "natural" order for the user, but otherwise
4187 * shouldn't have any effect.
4188 * If we would be constructing an isl_band forest directly in
4189 * isl_schedule_constraints_compute_schedule then there wouldn't be any need
4190 * for a reordering, since the children would be added to the list
4191 * in their natural order automatically.
4193 * If there is only one element in the list, then there is no need to sort
4195 * If the partial schedule of the parent has more than one member
4196 * (or if there is no parent), then it's
4197 * defnitely not assigning constant values to the different children in
4198 * the list and so we wouldn't be able to use it to sort the list.
4200 static __isl_give isl_band_list
*sort_band_list(__isl_take isl_band_list
*list
,
4201 __isl_keep isl_band
*parent
)
4203 struct isl_cmp_band_data data
;
4209 if (!parent
|| parent
->n
!= 1)
4213 isl_int_init(data
.c1
);
4214 isl_int_init(data
.c2
);
4215 isl_int_init(data
.t
);
4216 isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]), &cmp_band
, &data
);
4218 list
= isl_band_list_free(list
);
4219 isl_int_clear(data
.c1
);
4220 isl_int_clear(data
.c2
);
4221 isl_int_clear(data
.t
);
4226 /* Construct a list of bands that start at the same position (with
4227 * sequence number band_nr) in the schedules of the nodes that
4228 * were active in the parent band.
4230 * A separate isl_band structure is created for each band_id
4231 * and for each node that does not have a band with sequence
4232 * number band_nr. In the latter case, a band without members
4234 * This ensures that if a band has any children, then each node
4235 * that was active in the band is active in exactly one of the children.
4237 static __isl_give isl_band_list
*construct_band_list(
4238 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
4239 int band_nr
, int *parent_active
, int n_active
)
4242 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4245 isl_band_list
*list
;
4248 for (i
= 0; i
< n_active
; ++i
) {
4249 for (j
= 0; j
< schedule
->n
; ++j
) {
4250 if (!parent_active
[j
])
4252 if (schedule
->node
[j
].n_band
<= band_nr
)
4254 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
4260 for (j
= 0; j
< schedule
->n
; ++j
)
4261 if (schedule
->node
[j
].n_band
<= band_nr
)
4266 list
= isl_band_list_alloc(ctx
, n_band
);
4267 band
= construct_band(schedule
, parent
, band_nr
,
4268 parent_active
, n_active
);
4269 return isl_band_list_add(list
, band
);
4272 active
= isl_alloc_array(ctx
, int, schedule
->n
);
4273 if (schedule
->n
&& !active
)
4276 list
= isl_band_list_alloc(ctx
, n_band
);
4278 for (i
= 0; i
< n_active
; ++i
) {
4282 for (j
= 0; j
< schedule
->n
; ++j
) {
4283 active
[j
] = parent_active
[j
] &&
4284 schedule
->node
[j
].n_band
> band_nr
&&
4285 schedule
->node
[j
].band_id
[band_nr
] == i
;
4292 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
4294 list
= isl_band_list_add(list
, band
);
4296 for (i
= 0; i
< schedule
->n
; ++i
) {
4298 if (!parent_active
[i
])
4300 if (schedule
->node
[i
].n_band
> band_nr
)
4302 for (j
= 0; j
< schedule
->n
; ++j
)
4304 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
4305 list
= isl_band_list_add(list
, band
);
4310 list
= sort_band_list(list
, parent
);
4315 /* Construct a band forest representation of the schedule and
4316 * return the list of roots.
4318 static __isl_give isl_band_list
*construct_forest(
4319 __isl_keep isl_schedule
*schedule
)
4322 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
4323 isl_band_list
*forest
;
4326 active
= isl_alloc_array(ctx
, int, schedule
->n
);
4327 if (schedule
->n
&& !active
)
4330 for (i
= 0; i
< schedule
->n
; ++i
)
4333 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
4340 /* Return the roots of a band forest representation of the schedule.
4342 __isl_give isl_band_list
*isl_schedule_get_band_forest(
4343 __isl_keep isl_schedule
*schedule
)
4347 if (!schedule
->band_forest
)
4348 schedule
->band_forest
= construct_forest(schedule
);
4349 return isl_band_list_dup(schedule
->band_forest
);
4352 /* Call "fn" on each band in the schedule in depth-first post-order.
4354 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
4355 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
4358 isl_band_list
*forest
;
4363 forest
= isl_schedule_get_band_forest(sched
);
4364 r
= isl_band_list_foreach_band(forest
, fn
, user
);
4365 isl_band_list_free(forest
);
4370 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
4371 __isl_keep isl_band_list
*list
);
4373 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
4374 __isl_keep isl_band
*band
)
4376 isl_band_list
*children
;
4378 p
= isl_printer_start_line(p
);
4379 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
4380 p
= isl_printer_end_line(p
);
4382 if (!isl_band_has_children(band
))
4385 children
= isl_band_get_children(band
);
4387 p
= isl_printer_indent(p
, 4);
4388 p
= print_band_list(p
, children
);
4389 p
= isl_printer_indent(p
, -4);
4391 isl_band_list_free(children
);
4396 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
4397 __isl_keep isl_band_list
*list
)
4401 n
= isl_band_list_n_band(list
);
4402 for (i
= 0; i
< n
; ++i
) {
4404 band
= isl_band_list_get_band(list
, i
);
4405 p
= print_band(p
, band
);
4406 isl_band_free(band
);
4412 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
4413 __isl_keep isl_schedule
*schedule
)
4415 isl_band_list
*forest
;
4417 forest
= isl_schedule_get_band_forest(schedule
);
4419 p
= print_band_list(p
, forest
);
4421 isl_band_list_free(forest
);
4426 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
4428 isl_printer
*printer
;
4433 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
4434 printer
= isl_printer_print_schedule(printer
, schedule
);
4436 isl_printer_free(printer
);