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_hmap_map_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".
40 /* Internal information about a node that is used during the construction
42 * dim represents the space in which the domain lives
43 * sched is a matrix representation of the schedule being constructed
45 * sched_map is an isl_map representation of the same (partial) schedule
46 * sched_map may be NULL
47 * rank is the number of linearly independent rows in the linear part
49 * the columns of cmap represent a change of basis for the schedule
50 * coefficients; the first rank columns span the linear part of
52 * start is the first variable in the LP problem in the sequences that
53 * represents the schedule coefficients of this node
54 * nvar is the dimension of the domain
55 * nparam is the number of parameters or 0 if we are not constructing
56 * a parametric schedule
58 * scc is the index of SCC (or WCC) this node belongs to
60 * band contains the band index for each of the rows of the schedule.
61 * band_id is used to differentiate between separate bands at the same
62 * level within the same parent band, i.e., bands that are separated
63 * by the parent band or bands that are independent of each other.
64 * zero contains a boolean for each of the rows of the schedule,
65 * indicating whether the corresponding scheduling dimension results
66 * in zero dependence distances within its band and with respect
67 * to the proximity edges.
69 struct isl_sched_node
{
86 static int node_has_dim(const void *entry
, const void *val
)
88 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
89 isl_space
*dim
= (isl_space
*)val
;
91 return isl_space_is_equal(node
->dim
, dim
);
94 /* An edge in the dependence graph. An edge may be used to
95 * ensure validity of the generated schedule, to minimize the dependence
98 * map is the dependence relation
99 * src is the source node
100 * dst is the sink node
101 * validity is set if the edge is used to ensure correctness
102 * proximity is set if the edge is used to minimize dependence distances
104 * For validity edges, start and end mark the sequence of inequality
105 * constraints in the LP problem that encode the validity constraint
106 * corresponding to this edge.
108 struct isl_sched_edge
{
111 struct isl_sched_node
*src
;
112 struct isl_sched_node
*dst
;
122 isl_edge_validity
= 0,
123 isl_edge_first
= isl_edge_validity
,
125 isl_edge_last
= isl_edge_proximity
128 /* Internal information about the dependence graph used during
129 * the construction of the schedule.
131 * intra_hmap is a cache, mapping dependence relations to their dual,
132 * for dependences from a node to itself
133 * inter_hmap is a cache, mapping dependence relations to their dual,
134 * for dependences between distinct nodes
136 * n is the number of nodes
137 * node is the list of nodes
138 * maxvar is the maximal number of variables over all nodes
139 * max_row is the allocated number of rows in the schedule
140 * n_row is the current (maximal) number of linearly independent
141 * rows in the node schedules
142 * n_total_row is the current number of rows in the node schedules
143 * n_band is the current number of completed bands
144 * band_start is the starting row in the node schedules of the current band
145 * root is set if this graph is the original dependence graph,
146 * without any splitting
148 * sorted contains a list of node indices sorted according to the
149 * SCC to which a node belongs
151 * n_edge is the number of edges
152 * edge is the list of edges
153 * max_edge contains the maximal number of edges of each type;
154 * in particular, it contains the number of edges in the inital graph.
155 * edge_table contains pointers into the edge array, hashed on the source
156 * and sink spaces; there is one such table for each type;
157 * a given edge may be referenced from more than one table
158 * if the corresponding relation appears in more than of the
159 * sets of dependences
161 * node_table contains pointers into the node array, hashed on the space
163 * region contains a list of variable sequences that should be non-trivial
165 * lp contains the (I)LP problem used to obtain new schedule rows
167 * src_scc and dst_scc are the source and sink SCCs of an edge with
168 * conflicting constraints
170 * scc represents the number of components
172 struct isl_sched_graph
{
173 isl_hmap_map_basic_set
*intra_hmap
;
174 isl_hmap_map_basic_set
*inter_hmap
;
176 struct isl_sched_node
*node
;
190 struct isl_sched_edge
*edge
;
192 int max_edge
[isl_edge_last
+ 1];
193 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
195 struct isl_hash_table
*node_table
;
196 struct isl_region
*region
;
206 /* Initialize node_table based on the list of nodes.
208 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
212 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
213 if (!graph
->node_table
)
216 for (i
= 0; i
< graph
->n
; ++i
) {
217 struct isl_hash_table_entry
*entry
;
220 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
221 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
223 graph
->node
[i
].dim
, 1);
226 entry
->data
= &graph
->node
[i
];
232 /* Return a pointer to the node that lives within the given space,
233 * or NULL if there is no such node.
235 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
236 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
238 struct isl_hash_table_entry
*entry
;
241 hash
= isl_space_get_hash(dim
);
242 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
243 &node_has_dim
, dim
, 0);
245 return entry
? entry
->data
: NULL
;
248 static int edge_has_src_and_dst(const void *entry
, const void *val
)
250 const struct isl_sched_edge
*edge
= entry
;
251 const struct isl_sched_edge
*temp
= val
;
253 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
256 /* Add the given edge to graph->edge_table[type].
258 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
259 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
261 struct isl_hash_table_entry
*entry
;
264 hash
= isl_hash_init();
265 hash
= isl_hash_builtin(hash
, edge
->src
);
266 hash
= isl_hash_builtin(hash
, edge
->dst
);
267 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
268 &edge_has_src_and_dst
, edge
, 1);
276 /* Allocate the edge_tables based on the maximal number of edges of
279 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
283 for (i
= 0; i
<= isl_edge_last
; ++i
) {
284 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
286 if (!graph
->edge_table
[i
])
293 /* If graph->edge_table[type] contains an edge from the given source
294 * to the given destination, then return the hash table entry of this edge.
295 * Otherwise, return NULL.
297 static struct isl_hash_table_entry
*graph_find_edge_entry(
298 struct isl_sched_graph
*graph
,
299 enum isl_edge_type type
,
300 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
302 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
304 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
306 hash
= isl_hash_init();
307 hash
= isl_hash_builtin(hash
, temp
.src
);
308 hash
= isl_hash_builtin(hash
, temp
.dst
);
309 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
310 &edge_has_src_and_dst
, &temp
, 0);
314 /* If graph->edge_table[type] contains an edge from the given source
315 * to the given destination, then return this edge.
316 * Otherwise, return NULL.
318 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
319 enum isl_edge_type type
,
320 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
322 struct isl_hash_table_entry
*entry
;
324 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
331 /* Check whether the dependence graph has an edge of the given type
332 * between the given two nodes.
334 static int graph_has_edge(struct isl_sched_graph
*graph
,
335 enum isl_edge_type type
,
336 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
338 struct isl_sched_edge
*edge
;
341 edge
= graph_find_edge(graph
, type
, src
, dst
);
345 empty
= isl_map_plain_is_empty(edge
->map
);
352 /* If there is an edge from the given source to the given destination
353 * of any type then return this edge.
354 * Otherwise, return NULL.
356 static struct isl_sched_edge
*graph_find_any_edge(struct isl_sched_graph
*graph
,
357 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
359 enum isl_edge_type i
;
360 struct isl_sched_edge
*edge
;
362 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
363 edge
= graph_find_edge(graph
, i
, src
, dst
);
371 /* Remove the given edge from all the edge_tables that refer to it.
373 static void graph_remove_edge(struct isl_sched_graph
*graph
,
374 struct isl_sched_edge
*edge
)
376 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
377 enum isl_edge_type i
;
379 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
380 struct isl_hash_table_entry
*entry
;
382 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
385 if (entry
->data
!= edge
)
387 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
391 /* Check whether the dependence graph has any edge
392 * between the given two nodes.
394 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
395 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
397 enum isl_edge_type i
;
400 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
401 r
= graph_has_edge(graph
, i
, src
, dst
);
409 /* Check whether the dependence graph has a validity edge
410 * between the given two nodes.
412 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
413 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
415 return graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
418 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
419 int n_node
, int n_edge
)
424 graph
->n_edge
= n_edge
;
425 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
426 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
427 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
428 graph
->edge
= isl_calloc_array(ctx
,
429 struct isl_sched_edge
, graph
->n_edge
);
431 graph
->intra_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
432 graph
->inter_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
434 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
438 for(i
= 0; i
< graph
->n
; ++i
)
439 graph
->sorted
[i
] = i
;
444 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
448 isl_hmap_map_basic_set_free(ctx
, graph
->intra_hmap
);
449 isl_hmap_map_basic_set_free(ctx
, graph
->inter_hmap
);
451 for (i
= 0; i
< graph
->n
; ++i
) {
452 isl_space_free(graph
->node
[i
].dim
);
453 isl_mat_free(graph
->node
[i
].sched
);
454 isl_map_free(graph
->node
[i
].sched_map
);
455 isl_mat_free(graph
->node
[i
].cmap
);
457 free(graph
->node
[i
].band
);
458 free(graph
->node
[i
].band_id
);
459 free(graph
->node
[i
].zero
);
464 for (i
= 0; i
< graph
->n_edge
; ++i
)
465 isl_map_free(graph
->edge
[i
].map
);
468 for (i
= 0; i
<= isl_edge_last
; ++i
)
469 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
470 isl_hash_table_free(ctx
, graph
->node_table
);
471 isl_basic_set_free(graph
->lp
);
474 /* For each "set" on which this function is called, increment
475 * graph->n by one and update graph->maxvar.
477 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
479 struct isl_sched_graph
*graph
= user
;
480 int nvar
= isl_set_dim(set
, isl_dim_set
);
483 if (nvar
> graph
->maxvar
)
484 graph
->maxvar
= nvar
;
491 /* Compute the number of rows that should be allocated for the schedule.
492 * The graph can be split at most "n - 1" times, there can be at most
493 * two rows for each dimension in the iteration domains (in particular,
494 * we usually have one row, but it may be split by split_scaled),
495 * and there can be one extra row for ordering the statements.
496 * Note that if we have actually split "n - 1" times, then no ordering
497 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
499 static int compute_max_row(struct isl_sched_graph
*graph
,
500 __isl_keep isl_union_set
*domain
)
504 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
506 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
511 /* Add a new node to the graph representing the given set.
513 static int extract_node(__isl_take isl_set
*set
, void *user
)
519 struct isl_sched_graph
*graph
= user
;
520 int *band
, *band_id
, *zero
;
522 ctx
= isl_set_get_ctx(set
);
523 dim
= isl_set_get_space(set
);
525 nvar
= isl_space_dim(dim
, isl_dim_set
);
526 nparam
= isl_space_dim(dim
, isl_dim_param
);
527 if (!ctx
->opt
->schedule_parametric
)
529 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
530 graph
->node
[graph
->n
].dim
= dim
;
531 graph
->node
[graph
->n
].nvar
= nvar
;
532 graph
->node
[graph
->n
].nparam
= nparam
;
533 graph
->node
[graph
->n
].sched
= sched
;
534 graph
->node
[graph
->n
].sched_map
= NULL
;
535 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
536 graph
->node
[graph
->n
].band
= band
;
537 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
538 graph
->node
[graph
->n
].band_id
= band_id
;
539 zero
= isl_calloc_array(ctx
, int, graph
->max_row
);
540 graph
->node
[graph
->n
].zero
= zero
;
543 if (!sched
|| (graph
->max_row
&& (!band
|| !band_id
|| !zero
)))
549 struct isl_extract_edge_data
{
550 enum isl_edge_type type
;
551 struct isl_sched_graph
*graph
;
554 /* Add a new edge to the graph based on the given map
555 * and add it to data->graph->edge_table[data->type].
556 * If a dependence relation of a given type happens to be identical
557 * to one of the dependence relations of a type that was added before,
558 * then we don't create a new edge, but instead mark the original edge
559 * as also representing a dependence of the current type.
561 static int extract_edge(__isl_take isl_map
*map
, void *user
)
563 isl_ctx
*ctx
= isl_map_get_ctx(map
);
564 struct isl_extract_edge_data
*data
= user
;
565 struct isl_sched_graph
*graph
= data
->graph
;
566 struct isl_sched_node
*src
, *dst
;
568 struct isl_sched_edge
*edge
;
571 dim
= isl_space_domain(isl_map_get_space(map
));
572 src
= graph_find_node(ctx
, graph
, dim
);
574 dim
= isl_space_range(isl_map_get_space(map
));
575 dst
= graph_find_node(ctx
, graph
, dim
);
583 graph
->edge
[graph
->n_edge
].src
= src
;
584 graph
->edge
[graph
->n_edge
].dst
= dst
;
585 graph
->edge
[graph
->n_edge
].map
= map
;
586 if (data
->type
== isl_edge_validity
) {
587 graph
->edge
[graph
->n_edge
].validity
= 1;
588 graph
->edge
[graph
->n_edge
].proximity
= 0;
590 if (data
->type
== isl_edge_proximity
) {
591 graph
->edge
[graph
->n_edge
].validity
= 0;
592 graph
->edge
[graph
->n_edge
].proximity
= 1;
596 edge
= graph_find_any_edge(graph
, src
, dst
);
598 return graph_edge_table_add(ctx
, graph
, data
->type
,
599 &graph
->edge
[graph
->n_edge
- 1]);
600 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
604 return graph_edge_table_add(ctx
, graph
, data
->type
,
605 &graph
->edge
[graph
->n_edge
- 1]);
608 edge
->validity
|= graph
->edge
[graph
->n_edge
].validity
;
609 edge
->proximity
|= graph
->edge
[graph
->n_edge
].proximity
;
612 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
615 /* Check whether there is any dependence from node[j] to node[i]
616 * or from node[i] to node[j].
618 static int node_follows_weak(int i
, int j
, void *user
)
621 struct isl_sched_graph
*graph
= user
;
623 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
626 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
629 /* Check whether there is a validity dependence from node[j] to node[i],
630 * forcing node[i] to follow node[j].
632 static int node_follows_strong(int i
, int j
, void *user
)
634 struct isl_sched_graph
*graph
= user
;
636 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
639 /* Use Tarjan's algorithm for computing the strongly connected components
640 * in the dependence graph (only validity edges).
641 * If weak is set, we consider the graph to be undirected and
642 * we effectively compute the (weakly) connected components.
643 * Additionally, we also consider other edges when weak is set.
645 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
648 struct isl_tarjan_graph
*g
= NULL
;
650 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
651 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
659 while (g
->order
[i
] != -1) {
660 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
668 isl_tarjan_graph_free(g
);
673 /* Apply Tarjan's algorithm to detect the strongly connected components
674 * in the dependence graph.
676 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
678 return detect_ccs(ctx
, graph
, 0);
681 /* Apply Tarjan's algorithm to detect the (weakly) connected components
682 * in the dependence graph.
684 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
686 return detect_ccs(ctx
, graph
, 1);
689 static int cmp_scc(const void *a
, const void *b
, void *data
)
691 struct isl_sched_graph
*graph
= data
;
695 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
698 /* Sort the elements of graph->sorted according to the corresponding SCCs.
700 static int sort_sccs(struct isl_sched_graph
*graph
)
702 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
705 /* Given a dependence relation R from a node to itself,
706 * construct the set of coefficients of valid constraints for elements
707 * in that dependence relation.
708 * In particular, the result contains tuples of coefficients
709 * c_0, c_n, c_x such that
711 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
715 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
717 * We choose here to compute the dual of delta R.
718 * Alternatively, we could have computed the dual of R, resulting
719 * in a set of tuples c_0, c_n, c_x, c_y, and then
720 * plugged in (c_0, c_n, c_x, -c_x).
722 static __isl_give isl_basic_set
*intra_coefficients(
723 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
725 isl_ctx
*ctx
= isl_map_get_ctx(map
);
729 if (isl_hmap_map_basic_set_has(ctx
, graph
->intra_hmap
, map
))
730 return isl_hmap_map_basic_set_get(ctx
, graph
->intra_hmap
, map
);
732 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
733 coef
= isl_set_coefficients(delta
);
734 isl_hmap_map_basic_set_set(ctx
, graph
->intra_hmap
, map
,
735 isl_basic_set_copy(coef
));
740 /* Given a dependence relation R, * construct the set of coefficients
741 * of valid constraints for elements in that dependence relation.
742 * In particular, the result contains tuples of coefficients
743 * c_0, c_n, c_x, c_y such that
745 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
748 static __isl_give isl_basic_set
*inter_coefficients(
749 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
751 isl_ctx
*ctx
= isl_map_get_ctx(map
);
755 if (isl_hmap_map_basic_set_has(ctx
, graph
->inter_hmap
, map
))
756 return isl_hmap_map_basic_set_get(ctx
, graph
->inter_hmap
, map
);
758 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
759 coef
= isl_set_coefficients(set
);
760 isl_hmap_map_basic_set_set(ctx
, graph
->inter_hmap
, map
,
761 isl_basic_set_copy(coef
));
766 /* Add constraints to graph->lp that force validity for the given
767 * dependence from a node i to itself.
768 * That is, add constraints that enforce
770 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
771 * = c_i_x (y - x) >= 0
773 * for each (x,y) in R.
774 * We obtain general constraints on coefficients (c_0, c_n, c_x)
775 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
776 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
777 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
779 * Actually, we do not construct constraints for the c_i_x themselves,
780 * but for the coefficients of c_i_x written as a linear combination
781 * of the columns in node->cmap.
783 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
784 struct isl_sched_edge
*edge
)
787 isl_map
*map
= isl_map_copy(edge
->map
);
788 isl_ctx
*ctx
= isl_map_get_ctx(map
);
790 isl_dim_map
*dim_map
;
792 struct isl_sched_node
*node
= edge
->src
;
794 coef
= intra_coefficients(graph
, map
);
796 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
798 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
799 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
803 total
= isl_basic_set_total_dim(graph
->lp
);
804 dim_map
= isl_dim_map_alloc(ctx
, total
);
805 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
806 isl_space_dim(dim
, isl_dim_set
), 1,
808 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
809 isl_space_dim(dim
, isl_dim_set
), 1,
811 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
812 coef
->n_eq
, coef
->n_ineq
);
813 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
823 /* Add constraints to graph->lp that force validity for the given
824 * dependence from node i to node j.
825 * That is, add constraints that enforce
827 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
829 * for each (x,y) in R.
830 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
831 * of valid constraints for R and then plug in
832 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
833 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
834 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
835 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
837 * Actually, we do not construct constraints for the c_*_x themselves,
838 * but for the coefficients of c_*_x written as a linear combination
839 * of the columns in node->cmap.
841 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
842 struct isl_sched_edge
*edge
)
845 isl_map
*map
= isl_map_copy(edge
->map
);
846 isl_ctx
*ctx
= isl_map_get_ctx(map
);
848 isl_dim_map
*dim_map
;
850 struct isl_sched_node
*src
= edge
->src
;
851 struct isl_sched_node
*dst
= edge
->dst
;
853 coef
= inter_coefficients(graph
, map
);
855 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
857 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
858 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
859 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
860 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
861 isl_mat_copy(dst
->cmap
));
865 total
= isl_basic_set_total_dim(graph
->lp
);
866 dim_map
= isl_dim_map_alloc(ctx
, total
);
868 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
869 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
870 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
871 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
872 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
874 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
875 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
878 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
879 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
880 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
881 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
882 isl_space_dim(dim
, isl_dim_set
), 1,
884 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
885 isl_space_dim(dim
, isl_dim_set
), 1,
888 edge
->start
= graph
->lp
->n_ineq
;
889 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
890 coef
->n_eq
, coef
->n_ineq
);
891 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
896 edge
->end
= graph
->lp
->n_ineq
;
904 /* Add constraints to graph->lp that bound the dependence distance for the given
905 * dependence from a node i to itself.
906 * If s = 1, we add the constraint
908 * c_i_x (y - x) <= m_0 + m_n n
912 * -c_i_x (y - x) + m_0 + m_n n >= 0
914 * for each (x,y) in R.
915 * If s = -1, we add the constraint
917 * -c_i_x (y - x) <= m_0 + m_n n
921 * c_i_x (y - x) + m_0 + m_n n >= 0
923 * for each (x,y) in R.
924 * We obtain general constraints on coefficients (c_0, c_n, c_x)
925 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
926 * with each coefficient (except m_0) represented as a pair of non-negative
929 * Actually, we do not construct constraints for the c_i_x themselves,
930 * but for the coefficients of c_i_x written as a linear combination
931 * of the columns in node->cmap.
933 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
934 struct isl_sched_edge
*edge
, int s
)
938 isl_map
*map
= isl_map_copy(edge
->map
);
939 isl_ctx
*ctx
= isl_map_get_ctx(map
);
941 isl_dim_map
*dim_map
;
943 struct isl_sched_node
*node
= edge
->src
;
945 coef
= intra_coefficients(graph
, map
);
947 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
949 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
950 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
954 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
955 total
= isl_basic_set_total_dim(graph
->lp
);
956 dim_map
= isl_dim_map_alloc(ctx
, total
);
957 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
958 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
959 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
960 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
961 isl_space_dim(dim
, isl_dim_set
), 1,
963 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
964 isl_space_dim(dim
, isl_dim_set
), 1,
966 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
967 coef
->n_eq
, coef
->n_ineq
);
968 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
978 /* Add constraints to graph->lp that bound the dependence distance for the given
979 * dependence from node i to node j.
980 * If s = 1, we add the constraint
982 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
987 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
990 * for each (x,y) in R.
991 * If s = -1, we add the constraint
993 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
998 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1001 * for each (x,y) in R.
1002 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1003 * of valid constraints for R and then plug in
1004 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1006 * with each coefficient (except m_0, c_j_0 and c_i_0)
1007 * represented as a pair of non-negative coefficients.
1009 * Actually, we do not construct constraints for the c_*_x themselves,
1010 * but for the coefficients of c_*_x written as a linear combination
1011 * of the columns in node->cmap.
1013 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1014 struct isl_sched_edge
*edge
, int s
)
1018 isl_map
*map
= isl_map_copy(edge
->map
);
1019 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1021 isl_dim_map
*dim_map
;
1022 isl_basic_set
*coef
;
1023 struct isl_sched_node
*src
= edge
->src
;
1024 struct isl_sched_node
*dst
= edge
->dst
;
1026 coef
= inter_coefficients(graph
, map
);
1028 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1030 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1031 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1032 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1033 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1034 isl_mat_copy(dst
->cmap
));
1038 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1039 total
= isl_basic_set_total_dim(graph
->lp
);
1040 dim_map
= isl_dim_map_alloc(ctx
, total
);
1042 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1043 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1044 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1046 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1047 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1048 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1049 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1050 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1052 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1053 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1056 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1057 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1058 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1059 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1060 isl_space_dim(dim
, isl_dim_set
), 1,
1062 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1063 isl_space_dim(dim
, isl_dim_set
), 1,
1066 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1067 coef
->n_eq
, coef
->n_ineq
);
1068 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1070 isl_space_free(dim
);
1074 isl_space_free(dim
);
1078 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1082 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1083 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1084 if (!edge
->validity
)
1086 if (edge
->src
!= edge
->dst
)
1088 if (add_intra_validity_constraints(graph
, edge
) < 0)
1092 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1093 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1094 if (!edge
->validity
)
1096 if (edge
->src
== edge
->dst
)
1098 if (add_inter_validity_constraints(graph
, edge
) < 0)
1105 /* Add constraints to graph->lp that bound the dependence distance
1106 * for all dependence relations.
1107 * If a given proximity dependence is identical to a validity
1108 * dependence, then the dependence distance is already bounded
1109 * from below (by zero), so we only need to bound the distance
1111 * Otherwise, we need to bound the distance both from above and from below.
1113 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1117 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1118 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1119 if (!edge
->proximity
)
1121 if (edge
->src
== edge
->dst
&&
1122 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
1124 if (edge
->src
!= edge
->dst
&&
1125 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
1129 if (edge
->src
== edge
->dst
&&
1130 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
1132 if (edge
->src
!= edge
->dst
&&
1133 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1140 /* Compute a basis for the rows in the linear part of the schedule
1141 * and extend this basis to a full basis. The remaining rows
1142 * can then be used to force linear independence from the rows
1145 * In particular, given the schedule rows S, we compute
1149 * with H the Hermite normal form of S. That is, all but the
1150 * first rank columns of Q are zero and so each row in S is
1151 * a linear combination of the first rank rows of Q.
1152 * The matrix Q is then transposed because we will write the
1153 * coefficients of the next schedule row as a column vector s
1154 * and express this s as a linear combination s = Q c of the
1157 static int node_update_cmap(struct isl_sched_node
*node
)
1160 int n_row
= isl_mat_rows(node
->sched
);
1162 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1163 1 + node
->nparam
, node
->nvar
);
1165 H
= isl_mat_left_hermite(H
, 0, NULL
, &Q
);
1166 isl_mat_free(node
->cmap
);
1167 node
->cmap
= isl_mat_transpose(Q
);
1168 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1171 if (!node
->cmap
|| node
->rank
< 0)
1176 /* Count the number of equality and inequality constraints
1177 * that will be added for the given map.
1178 * If carry is set, then we are counting the number of (validity)
1179 * constraints that will be added in setup_carry_lp and we count
1180 * each edge exactly once. Otherwise, we count as follows
1181 * validity -> 1 (>= 0)
1182 * validity+proximity -> 2 (>= 0 and upper bound)
1183 * proximity -> 2 (lower and upper bound)
1185 static int count_map_constraints(struct isl_sched_graph
*graph
,
1186 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1187 int *n_eq
, int *n_ineq
, int carry
)
1189 isl_basic_set
*coef
;
1190 int f
= carry
? 1 : edge
->proximity
? 2 : 1;
1192 if (carry
&& !edge
->validity
) {
1197 if (edge
->src
== edge
->dst
)
1198 coef
= intra_coefficients(graph
, map
);
1200 coef
= inter_coefficients(graph
, map
);
1203 *n_eq
+= f
* coef
->n_eq
;
1204 *n_ineq
+= f
* coef
->n_ineq
;
1205 isl_basic_set_free(coef
);
1210 /* Count the number of equality and inequality constraints
1211 * that will be added to the main lp problem.
1212 * We count as follows
1213 * validity -> 1 (>= 0)
1214 * validity+proximity -> 2 (>= 0 and upper bound)
1215 * proximity -> 2 (lower and upper bound)
1217 static int count_constraints(struct isl_sched_graph
*graph
,
1218 int *n_eq
, int *n_ineq
)
1222 *n_eq
= *n_ineq
= 0;
1223 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1224 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1225 isl_map
*map
= isl_map_copy(edge
->map
);
1227 if (count_map_constraints(graph
, edge
, map
,
1228 n_eq
, n_ineq
, 0) < 0)
1235 /* Count the number of constraints that will be added by
1236 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1239 * In practice, add_bound_coefficient_constraints only adds inequalities.
1241 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1242 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1246 if (ctx
->opt
->schedule_max_coefficient
== -1)
1249 for (i
= 0; i
< graph
->n
; ++i
)
1250 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1255 /* Add constraints that bound the values of the variable and parameter
1256 * coefficients of the schedule.
1258 * The maximal value of the coefficients is defined by the option
1259 * 'schedule_max_coefficient'.
1261 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1262 struct isl_sched_graph
*graph
)
1265 int max_coefficient
;
1268 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1270 if (max_coefficient
== -1)
1273 total
= isl_basic_set_total_dim(graph
->lp
);
1275 for (i
= 0; i
< graph
->n
; ++i
) {
1276 struct isl_sched_node
*node
= &graph
->node
[i
];
1277 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1279 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1282 dim
= 1 + node
->start
+ 1 + j
;
1283 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1284 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1285 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1292 /* Construct an ILP problem for finding schedule coefficients
1293 * that result in non-negative, but small dependence distances
1294 * over all dependences.
1295 * In particular, the dependence distances over proximity edges
1296 * are bounded by m_0 + m_n n and we compute schedule coefficients
1297 * with small values (preferably zero) of m_n and m_0.
1299 * All variables of the ILP are non-negative. The actual coefficients
1300 * may be negative, so each coefficient is represented as the difference
1301 * of two non-negative variables. The negative part always appears
1302 * immediately before the positive part.
1303 * Other than that, the variables have the following order
1305 * - sum of positive and negative parts of m_n coefficients
1307 * - sum of positive and negative parts of all c_n coefficients
1308 * (unconstrained when computing non-parametric schedules)
1309 * - sum of positive and negative parts of all c_x coefficients
1310 * - positive and negative parts of m_n coefficients
1313 * - positive and negative parts of c_i_n (if parametric)
1314 * - positive and negative parts of c_i_x
1316 * The c_i_x are not represented directly, but through the columns of
1317 * node->cmap. That is, the computed values are for variable t_i_x
1318 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1320 * The constraints are those from the edges plus two or three equalities
1321 * to express the sums.
1323 * If force_zero is set, then we add equalities to ensure that
1324 * the sum of the m_n coefficients and m_0 are both zero.
1326 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1337 int max_constant_term
;
1339 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1341 parametric
= ctx
->opt
->schedule_parametric
;
1342 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1344 total
= param_pos
+ 2 * nparam
;
1345 for (i
= 0; i
< graph
->n
; ++i
) {
1346 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1347 if (node_update_cmap(node
) < 0)
1349 node
->start
= total
;
1350 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1353 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1355 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
1358 dim
= isl_space_set_alloc(ctx
, 0, total
);
1359 isl_basic_set_free(graph
->lp
);
1360 n_eq
+= 2 + parametric
+ force_zero
;
1361 if (max_constant_term
!= -1)
1364 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1366 k
= isl_basic_set_alloc_equality(graph
->lp
);
1369 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1371 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1372 for (i
= 0; i
< 2 * nparam
; ++i
)
1373 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1376 k
= isl_basic_set_alloc_equality(graph
->lp
);
1379 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1380 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1384 k
= isl_basic_set_alloc_equality(graph
->lp
);
1387 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1388 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1389 for (i
= 0; i
< graph
->n
; ++i
) {
1390 int pos
= 1 + graph
->node
[i
].start
+ 1;
1392 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1393 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1397 k
= isl_basic_set_alloc_equality(graph
->lp
);
1400 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1401 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1402 for (i
= 0; i
< graph
->n
; ++i
) {
1403 struct isl_sched_node
*node
= &graph
->node
[i
];
1404 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1406 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1407 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1410 if (max_constant_term
!= -1)
1411 for (i
= 0; i
< graph
->n
; ++i
) {
1412 struct isl_sched_node
*node
= &graph
->node
[i
];
1413 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1416 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1417 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1418 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1421 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1423 if (add_all_validity_constraints(graph
) < 0)
1425 if (add_all_proximity_constraints(graph
) < 0)
1431 /* Analyze the conflicting constraint found by
1432 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1433 * constraint of one of the edges between distinct nodes, living, moreover
1434 * in distinct SCCs, then record the source and sink SCC as this may
1435 * be a good place to cut between SCCs.
1437 static int check_conflict(int con
, void *user
)
1440 struct isl_sched_graph
*graph
= user
;
1442 if (graph
->src_scc
>= 0)
1445 con
-= graph
->lp
->n_eq
;
1447 if (con
>= graph
->lp
->n_ineq
)
1450 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1451 if (!graph
->edge
[i
].validity
)
1453 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1455 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1457 if (graph
->edge
[i
].start
> con
)
1459 if (graph
->edge
[i
].end
<= con
)
1461 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1462 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1468 /* Check whether the next schedule row of the given node needs to be
1469 * non-trivial. Lower-dimensional domains may have some trivial rows,
1470 * but as soon as the number of remaining required non-trivial rows
1471 * is as large as the number or remaining rows to be computed,
1472 * all remaining rows need to be non-trivial.
1474 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1476 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1479 /* Solve the ILP problem constructed in setup_lp.
1480 * For each node such that all the remaining rows of its schedule
1481 * need to be non-trivial, we construct a non-triviality region.
1482 * This region imposes that the next row is independent of previous rows.
1483 * In particular the coefficients c_i_x are represented by t_i_x
1484 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1485 * its first columns span the rows of the previously computed part
1486 * of the schedule. The non-triviality region enforces that at least
1487 * one of the remaining components of t_i_x is non-zero, i.e.,
1488 * that the new schedule row depends on at least one of the remaining
1491 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1497 for (i
= 0; i
< graph
->n
; ++i
) {
1498 struct isl_sched_node
*node
= &graph
->node
[i
];
1499 int skip
= node
->rank
;
1500 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1501 if (needs_row(graph
, node
))
1502 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1504 graph
->region
[i
].len
= 0;
1506 lp
= isl_basic_set_copy(graph
->lp
);
1507 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1508 graph
->region
, &check_conflict
, graph
);
1512 /* Update the schedules of all nodes based on the given solution
1513 * of the LP problem.
1514 * The new row is added to the current band.
1515 * All possibly negative coefficients are encoded as a difference
1516 * of two non-negative variables, so we need to perform the subtraction
1517 * here. Moreover, if use_cmap is set, then the solution does
1518 * not refer to the actual coefficients c_i_x, but instead to variables
1519 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1520 * In this case, we then also need to perform this multiplication
1521 * to obtain the values of c_i_x.
1523 * If check_zero is set, then the first two coordinates of sol are
1524 * assumed to correspond to the dependence distance. If these two
1525 * coordinates are zero, then the corresponding scheduling dimension
1526 * is marked as being zero distance.
1528 static int update_schedule(struct isl_sched_graph
*graph
,
1529 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1533 isl_vec
*csol
= NULL
;
1538 isl_die(sol
->ctx
, isl_error_internal
,
1539 "no solution found", goto error
);
1540 if (graph
->n_total_row
>= graph
->max_row
)
1541 isl_die(sol
->ctx
, isl_error_internal
,
1542 "too many schedule rows", goto error
);
1545 zero
= isl_int_is_zero(sol
->el
[1]) &&
1546 isl_int_is_zero(sol
->el
[2]);
1548 for (i
= 0; i
< graph
->n
; ++i
) {
1549 struct isl_sched_node
*node
= &graph
->node
[i
];
1550 int pos
= node
->start
;
1551 int row
= isl_mat_rows(node
->sched
);
1554 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1558 isl_map_free(node
->sched_map
);
1559 node
->sched_map
= NULL
;
1560 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1563 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1565 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1566 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1567 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1568 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1569 for (j
= 0; j
< node
->nparam
; ++j
)
1570 node
->sched
= isl_mat_set_element(node
->sched
,
1571 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1572 for (j
= 0; j
< node
->nvar
; ++j
)
1573 isl_int_set(csol
->el
[j
],
1574 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1576 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1580 for (j
= 0; j
< node
->nvar
; ++j
)
1581 node
->sched
= isl_mat_set_element(node
->sched
,
1582 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1583 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1584 node
->zero
[graph
->n_total_row
] = zero
;
1590 graph
->n_total_row
++;
1599 /* Convert node->sched into a multi_aff and return this multi_aff.
1601 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
1602 struct isl_sched_node
*node
)
1606 isl_local_space
*ls
;
1612 nrow
= isl_mat_rows(node
->sched
);
1613 ncol
= isl_mat_cols(node
->sched
) - 1;
1614 space
= isl_space_from_domain(isl_space_copy(node
->dim
));
1615 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
1616 ma
= isl_multi_aff_zero(space
);
1617 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
1621 for (i
= 0; i
< nrow
; ++i
) {
1622 aff
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1623 isl_mat_get_element(node
->sched
, i
, 0, &v
);
1624 aff
= isl_aff_set_constant(aff
, v
);
1625 for (j
= 0; j
< node
->nparam
; ++j
) {
1626 isl_mat_get_element(node
->sched
, i
, 1 + j
, &v
);
1627 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
1629 for (j
= 0; j
< node
->nvar
; ++j
) {
1630 isl_mat_get_element(node
->sched
,
1631 i
, 1 + node
->nparam
+ j
, &v
);
1632 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
1634 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
1639 isl_local_space_free(ls
);
1644 /* Convert node->sched into a map and return this map.
1646 * The result is cached in node->sched_map, which needs to be released
1647 * whenever node->sched is updated.
1649 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1651 if (!node
->sched_map
) {
1654 ma
= node_extract_schedule_multi_aff(node
);
1655 node
->sched_map
= isl_map_from_multi_aff(ma
);
1658 return isl_map_copy(node
->sched_map
);
1661 /* Update the given dependence relation based on the current schedule.
1662 * That is, intersect the dependence relation with a map expressing
1663 * that source and sink are executed within the same iteration of
1664 * the current schedule.
1665 * This is not the most efficient way, but this shouldn't be a critical
1668 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1669 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1671 isl_map
*src_sched
, *dst_sched
, *id
;
1673 src_sched
= node_extract_schedule(src
);
1674 dst_sched
= node_extract_schedule(dst
);
1675 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1676 return isl_map_intersect(map
, id
);
1679 /* Update the dependence relations of all edges based on the current schedule.
1680 * If a dependence is carried completely by the current schedule, then
1681 * it is removed from the edge_tables. It is kept in the list of edges
1682 * as otherwise all edge_tables would have to be recomputed.
1684 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1688 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1689 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1690 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1694 if (isl_map_plain_is_empty(edge
->map
))
1695 graph_remove_edge(graph
, edge
);
1701 static void next_band(struct isl_sched_graph
*graph
)
1703 graph
->band_start
= graph
->n_total_row
;
1707 /* Topologically sort statements mapped to the same schedule iteration
1708 * and add a row to the schedule corresponding to this order.
1710 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1717 if (update_edges(ctx
, graph
) < 0)
1720 if (graph
->n_edge
== 0)
1723 if (detect_sccs(ctx
, graph
) < 0)
1726 if (graph
->n_total_row
>= graph
->max_row
)
1727 isl_die(ctx
, isl_error_internal
,
1728 "too many schedule rows", return -1);
1730 for (i
= 0; i
< graph
->n
; ++i
) {
1731 struct isl_sched_node
*node
= &graph
->node
[i
];
1732 int row
= isl_mat_rows(node
->sched
);
1733 int cols
= isl_mat_cols(node
->sched
);
1735 isl_map_free(node
->sched_map
);
1736 node
->sched_map
= NULL
;
1737 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1740 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1742 for (j
= 1; j
< cols
; ++j
)
1743 node
->sched
= isl_mat_set_element_si(node
->sched
,
1745 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1748 graph
->n_total_row
++;
1754 /* Construct an isl_schedule based on the computed schedule stored
1755 * in graph and with parameters specified by dim.
1757 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1758 __isl_take isl_space
*dim
)
1762 isl_schedule
*sched
= NULL
;
1767 ctx
= isl_space_get_ctx(dim
);
1768 sched
= isl_calloc(ctx
, struct isl_schedule
,
1769 sizeof(struct isl_schedule
) +
1770 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1775 sched
->n
= graph
->n
;
1776 sched
->n_band
= graph
->n_band
;
1777 sched
->n_total_row
= graph
->n_total_row
;
1779 for (i
= 0; i
< sched
->n
; ++i
) {
1781 int *band_end
, *band_id
, *zero
;
1783 sched
->node
[i
].sched
=
1784 node_extract_schedule_multi_aff(&graph
->node
[i
]);
1785 if (!sched
->node
[i
].sched
)
1788 sched
->node
[i
].n_band
= graph
->n_band
;
1789 if (graph
->n_band
== 0)
1792 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1793 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1794 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1795 sched
->node
[i
].band_end
= band_end
;
1796 sched
->node
[i
].band_id
= band_id
;
1797 sched
->node
[i
].zero
= zero
;
1798 if (!band_end
|| !band_id
|| !zero
)
1801 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1802 zero
[r
] = graph
->node
[i
].zero
[r
];
1803 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1804 if (graph
->node
[i
].band
[r
] == b
)
1807 if (graph
->node
[i
].band
[r
] == -1)
1810 if (r
== graph
->n_total_row
)
1812 sched
->node
[i
].n_band
= b
;
1813 for (--b
; b
>= 0; --b
)
1814 band_id
[b
] = graph
->node
[i
].band_id
[b
];
1821 isl_space_free(dim
);
1822 isl_schedule_free(sched
);
1826 /* Copy nodes that satisfy node_pred from the src dependence graph
1827 * to the dst dependence graph.
1829 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
1830 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1835 for (i
= 0; i
< src
->n
; ++i
) {
1836 if (!node_pred(&src
->node
[i
], data
))
1838 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
1839 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
1840 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
1841 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
1842 dst
->node
[dst
->n
].sched_map
=
1843 isl_map_copy(src
->node
[i
].sched_map
);
1844 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
1845 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
1846 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
1853 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1854 * to the dst dependence graph.
1855 * If the source or destination node of the edge is not in the destination
1856 * graph, then it must be a backward proximity edge and it should simply
1859 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
1860 struct isl_sched_graph
*src
,
1861 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
1864 enum isl_edge_type t
;
1867 for (i
= 0; i
< src
->n_edge
; ++i
) {
1868 struct isl_sched_edge
*edge
= &src
->edge
[i
];
1870 struct isl_sched_node
*dst_src
, *dst_dst
;
1872 if (!edge_pred(edge
, data
))
1875 if (isl_map_plain_is_empty(edge
->map
))
1878 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
1879 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
1880 if (!dst_src
|| !dst_dst
) {
1882 isl_die(ctx
, isl_error_internal
,
1883 "backward validity edge", return -1);
1887 map
= isl_map_copy(edge
->map
);
1889 dst
->edge
[dst
->n_edge
].src
= dst_src
;
1890 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
1891 dst
->edge
[dst
->n_edge
].map
= map
;
1892 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
1893 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
1896 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
1898 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
1900 if (graph_edge_table_add(ctx
, dst
, t
,
1901 &dst
->edge
[dst
->n_edge
- 1]) < 0)
1909 /* Given a "src" dependence graph that contains the nodes from "dst"
1910 * that satisfy node_pred, copy the schedule computed in "src"
1911 * for those nodes back to "dst".
1913 static int copy_schedule(struct isl_sched_graph
*dst
,
1914 struct isl_sched_graph
*src
,
1915 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1920 for (i
= 0; i
< dst
->n
; ++i
) {
1921 if (!node_pred(&dst
->node
[i
], data
))
1923 isl_mat_free(dst
->node
[i
].sched
);
1924 isl_map_free(dst
->node
[i
].sched_map
);
1925 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
1926 dst
->node
[i
].sched_map
=
1927 isl_map_copy(src
->node
[src
->n
].sched_map
);
1931 dst
->max_row
= src
->max_row
;
1932 dst
->n_total_row
= src
->n_total_row
;
1933 dst
->n_band
= src
->n_band
;
1938 /* Compute the maximal number of variables over all nodes.
1939 * This is the maximal number of linearly independent schedule
1940 * rows that we need to compute.
1941 * Just in case we end up in a part of the dependence graph
1942 * with only lower-dimensional domains, we make sure we will
1943 * compute the required amount of extra linearly independent rows.
1945 static int compute_maxvar(struct isl_sched_graph
*graph
)
1950 for (i
= 0; i
< graph
->n
; ++i
) {
1951 struct isl_sched_node
*node
= &graph
->node
[i
];
1954 if (node_update_cmap(node
) < 0)
1956 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
1957 if (nvar
> graph
->maxvar
)
1958 graph
->maxvar
= nvar
;
1964 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1965 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1967 /* Compute a schedule for a subgraph of "graph". In particular, for
1968 * the graph composed of nodes that satisfy node_pred and edges that
1969 * that satisfy edge_pred. The caller should precompute the number
1970 * of nodes and edges that satisfy these predicates and pass them along
1971 * as "n" and "n_edge".
1972 * If the subgraph is known to consist of a single component, then wcc should
1973 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1974 * Otherwise, we call compute_schedule, which will check whether the subgraph
1977 static int compute_sub_schedule(isl_ctx
*ctx
,
1978 struct isl_sched_graph
*graph
, int n
, int n_edge
,
1979 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
1980 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
1983 struct isl_sched_graph split
= { 0 };
1986 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
1988 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
1990 if (graph_init_table(ctx
, &split
) < 0)
1992 for (t
= 0; t
<= isl_edge_last
; ++t
)
1993 split
.max_edge
[t
] = graph
->max_edge
[t
];
1994 if (graph_init_edge_tables(ctx
, &split
) < 0)
1996 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
1998 split
.n_row
= graph
->n_row
;
1999 split
.max_row
= graph
->max_row
;
2000 split
.n_total_row
= graph
->n_total_row
;
2001 split
.n_band
= graph
->n_band
;
2002 split
.band_start
= graph
->band_start
;
2004 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2006 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2009 copy_schedule(graph
, &split
, node_pred
, data
);
2011 graph_free(ctx
, &split
);
2014 graph_free(ctx
, &split
);
2018 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2020 return node
->scc
== scc
;
2023 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2025 return node
->scc
<= scc
;
2028 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2030 return node
->scc
>= scc
;
2033 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2035 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2038 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2040 return edge
->dst
->scc
<= scc
;
2043 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2045 return edge
->src
->scc
>= scc
;
2048 /* Pad the schedules of all nodes with zero rows such that in the end
2049 * they all have graph->n_total_row rows.
2050 * The extra rows don't belong to any band, so they get assigned band number -1.
2052 static int pad_schedule(struct isl_sched_graph
*graph
)
2056 for (i
= 0; i
< graph
->n
; ++i
) {
2057 struct isl_sched_node
*node
= &graph
->node
[i
];
2058 int row
= isl_mat_rows(node
->sched
);
2059 if (graph
->n_total_row
> row
) {
2060 isl_map_free(node
->sched_map
);
2061 node
->sched_map
= NULL
;
2063 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2064 graph
->n_total_row
- row
);
2067 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2074 /* Split the current graph into two parts and compute a schedule for each
2075 * part individually. In particular, one part consists of all SCCs up
2076 * to and including graph->src_scc, while the other part contains the other
2079 * The split is enforced in the schedule by constant rows with two different
2080 * values (0 and 1). These constant rows replace the previously computed rows
2081 * in the current band.
2082 * It would be possible to reuse them as the first rows in the next
2083 * band, but recomputing them may result in better rows as we are looking
2084 * at a smaller part of the dependence graph.
2085 * compute_split_schedule is only called when no zero-distance schedule row
2086 * could be found on the entire graph, so we wark the splitting row as
2087 * non zero-distance.
2089 * The band_id of the second group is set to n, where n is the number
2090 * of nodes in the first group. This ensures that the band_ids over
2091 * the two groups remain disjoint, even if either or both of the two
2092 * groups contain independent components.
2094 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2096 int i
, j
, n
, e1
, e2
;
2097 int n_total_row
, orig_total_row
;
2098 int n_band
, orig_band
;
2101 if (graph
->n_total_row
>= graph
->max_row
)
2102 isl_die(ctx
, isl_error_internal
,
2103 "too many schedule rows", return -1);
2105 drop
= graph
->n_total_row
- graph
->band_start
;
2106 graph
->n_total_row
-= drop
;
2107 graph
->n_row
-= drop
;
2110 for (i
= 0; i
< graph
->n
; ++i
) {
2111 struct isl_sched_node
*node
= &graph
->node
[i
];
2112 int row
= isl_mat_rows(node
->sched
) - drop
;
2113 int cols
= isl_mat_cols(node
->sched
);
2114 int before
= node
->scc
<= graph
->src_scc
;
2119 isl_map_free(node
->sched_map
);
2120 node
->sched_map
= NULL
;
2121 node
->sched
= isl_mat_drop_rows(node
->sched
,
2122 graph
->band_start
, drop
);
2123 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2126 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2128 for (j
= 1; j
< cols
; ++j
)
2129 node
->sched
= isl_mat_set_element_si(node
->sched
,
2131 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2132 node
->zero
[graph
->n_total_row
] = 0;
2136 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2137 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2139 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2143 graph
->n_total_row
++;
2146 for (i
= 0; i
< graph
->n
; ++i
) {
2147 struct isl_sched_node
*node
= &graph
->node
[i
];
2148 if (node
->scc
> graph
->src_scc
)
2149 node
->band_id
[graph
->n_band
] = n
;
2152 orig_total_row
= graph
->n_total_row
;
2153 orig_band
= graph
->n_band
;
2154 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2155 &node_scc_at_most
, &edge_dst_scc_at_most
,
2156 graph
->src_scc
, 0) < 0)
2158 n_total_row
= graph
->n_total_row
;
2159 graph
->n_total_row
= orig_total_row
;
2160 n_band
= graph
->n_band
;
2161 graph
->n_band
= orig_band
;
2162 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2163 &node_scc_at_least
, &edge_src_scc_at_least
,
2164 graph
->src_scc
+ 1, 0) < 0)
2166 if (n_total_row
> graph
->n_total_row
)
2167 graph
->n_total_row
= n_total_row
;
2168 if (n_band
> graph
->n_band
)
2169 graph
->n_band
= n_band
;
2171 return pad_schedule(graph
);
2174 /* Compute the next band of the schedule after updating the dependence
2175 * relations based on the the current schedule.
2177 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2179 if (update_edges(ctx
, graph
) < 0)
2183 return compute_schedule(ctx
, graph
);
2186 /* Add constraints to graph->lp that force the dependence "map" (which
2187 * is part of the dependence relation of "edge")
2188 * to be respected and attempt to carry it, where the edge is one from
2189 * a node j to itself. "pos" is the sequence number of the given map.
2190 * That is, add constraints that enforce
2192 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2193 * = c_j_x (y - x) >= e_i
2195 * for each (x,y) in R.
2196 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2197 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2198 * with each coefficient in c_j_x represented as a pair of non-negative
2201 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2202 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2205 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2207 isl_dim_map
*dim_map
;
2208 isl_basic_set
*coef
;
2209 struct isl_sched_node
*node
= edge
->src
;
2211 coef
= intra_coefficients(graph
, map
);
2215 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2217 total
= isl_basic_set_total_dim(graph
->lp
);
2218 dim_map
= isl_dim_map_alloc(ctx
, total
);
2219 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2220 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2221 isl_space_dim(dim
, isl_dim_set
), 1,
2223 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2224 isl_space_dim(dim
, isl_dim_set
), 1,
2226 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2227 coef
->n_eq
, coef
->n_ineq
);
2228 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2230 isl_space_free(dim
);
2235 /* Add constraints to graph->lp that force the dependence "map" (which
2236 * is part of the dependence relation of "edge")
2237 * to be respected and attempt to carry it, where the edge is one from
2238 * node j to node k. "pos" is the sequence number of the given map.
2239 * That is, add constraints that enforce
2241 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2243 * for each (x,y) in R.
2244 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2245 * of valid constraints for R and then plug in
2246 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2247 * with each coefficient (except e_i, c_k_0 and c_j_0)
2248 * represented as a pair of non-negative coefficients.
2250 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2251 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2254 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2256 isl_dim_map
*dim_map
;
2257 isl_basic_set
*coef
;
2258 struct isl_sched_node
*src
= edge
->src
;
2259 struct isl_sched_node
*dst
= edge
->dst
;
2261 coef
= inter_coefficients(graph
, map
);
2265 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2267 total
= isl_basic_set_total_dim(graph
->lp
);
2268 dim_map
= isl_dim_map_alloc(ctx
, total
);
2270 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2272 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2273 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2274 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2275 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2276 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2278 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2279 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2282 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2283 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2284 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2285 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2286 isl_space_dim(dim
, isl_dim_set
), 1,
2288 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2289 isl_space_dim(dim
, isl_dim_set
), 1,
2292 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2293 coef
->n_eq
, coef
->n_ineq
);
2294 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2296 isl_space_free(dim
);
2301 /* Add constraints to graph->lp that force all validity dependences
2302 * to be respected and attempt to carry them.
2304 static int add_all_constraints(struct isl_sched_graph
*graph
)
2310 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2311 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2313 if (!edge
->validity
)
2316 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2317 isl_basic_map
*bmap
;
2320 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2321 map
= isl_map_from_basic_map(bmap
);
2323 if (edge
->src
== edge
->dst
&&
2324 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2326 if (edge
->src
!= edge
->dst
&&
2327 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2336 /* Count the number of equality and inequality constraints
2337 * that will be added to the carry_lp problem.
2338 * We count each edge exactly once.
2340 static int count_all_constraints(struct isl_sched_graph
*graph
,
2341 int *n_eq
, int *n_ineq
)
2345 *n_eq
= *n_ineq
= 0;
2346 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2347 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2348 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2349 isl_basic_map
*bmap
;
2352 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2353 map
= isl_map_from_basic_map(bmap
);
2355 if (count_map_constraints(graph
, edge
, map
,
2356 n_eq
, n_ineq
, 1) < 0)
2364 /* Construct an LP problem for finding schedule coefficients
2365 * such that the schedule carries as many dependences as possible.
2366 * In particular, for each dependence i, we bound the dependence distance
2367 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2368 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2369 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2370 * Note that if the dependence relation is a union of basic maps,
2371 * then we have to consider each basic map individually as it may only
2372 * be possible to carry the dependences expressed by some of those
2373 * basic maps and not all off them.
2374 * Below, we consider each of those basic maps as a separate "edge".
2376 * All variables of the LP are non-negative. The actual coefficients
2377 * may be negative, so each coefficient is represented as the difference
2378 * of two non-negative variables. The negative part always appears
2379 * immediately before the positive part.
2380 * Other than that, the variables have the following order
2382 * - sum of (1 - e_i) over all edges
2383 * - sum of positive and negative parts of all c_n coefficients
2384 * (unconstrained when computing non-parametric schedules)
2385 * - sum of positive and negative parts of all c_x coefficients
2390 * - positive and negative parts of c_i_n (if parametric)
2391 * - positive and negative parts of c_i_x
2393 * The constraints are those from the (validity) edges plus three equalities
2394 * to express the sums and n_edge inequalities to express e_i <= 1.
2396 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2406 for (i
= 0; i
< graph
->n_edge
; ++i
)
2407 n_edge
+= graph
->edge
[i
].map
->n
;
2410 for (i
= 0; i
< graph
->n
; ++i
) {
2411 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2412 node
->start
= total
;
2413 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2416 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2418 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2421 dim
= isl_space_set_alloc(ctx
, 0, total
);
2422 isl_basic_set_free(graph
->lp
);
2425 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2426 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2428 k
= isl_basic_set_alloc_equality(graph
->lp
);
2431 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2432 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2433 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2434 for (i
= 0; i
< n_edge
; ++i
)
2435 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2437 k
= isl_basic_set_alloc_equality(graph
->lp
);
2440 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2441 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2442 for (i
= 0; i
< graph
->n
; ++i
) {
2443 int pos
= 1 + graph
->node
[i
].start
+ 1;
2445 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2446 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2449 k
= isl_basic_set_alloc_equality(graph
->lp
);
2452 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2453 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2454 for (i
= 0; i
< graph
->n
; ++i
) {
2455 struct isl_sched_node
*node
= &graph
->node
[i
];
2456 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2458 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2459 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2462 for (i
= 0; i
< n_edge
; ++i
) {
2463 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2466 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2467 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2468 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2471 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2473 if (add_all_constraints(graph
) < 0)
2479 /* If the schedule_split_scaled option is set and if the linear
2480 * parts of the scheduling rows for all nodes in the graphs have
2481 * non-trivial common divisor, then split off the constant term
2482 * from the linear part.
2483 * The constant term is then placed in a separate band and
2484 * the linear part is reduced.
2486 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2492 if (!ctx
->opt
->schedule_split_scaled
)
2497 if (graph
->n_total_row
>= graph
->max_row
)
2498 isl_die(ctx
, isl_error_internal
,
2499 "too many schedule rows", return -1);
2502 isl_int_init(gcd_i
);
2504 isl_int_set_si(gcd
, 0);
2506 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2508 for (i
= 0; i
< graph
->n
; ++i
) {
2509 struct isl_sched_node
*node
= &graph
->node
[i
];
2510 int cols
= isl_mat_cols(node
->sched
);
2512 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2513 isl_int_gcd(gcd
, gcd
, gcd_i
);
2516 isl_int_clear(gcd_i
);
2518 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2525 for (i
= 0; i
< graph
->n
; ++i
) {
2526 struct isl_sched_node
*node
= &graph
->node
[i
];
2528 isl_map_free(node
->sched_map
);
2529 node
->sched_map
= NULL
;
2530 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2533 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2534 node
->sched
->row
[row
][0], gcd
);
2535 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2536 node
->sched
->row
[row
][0], gcd
);
2537 isl_int_mul(node
->sched
->row
[row
][0],
2538 node
->sched
->row
[row
][0], gcd
);
2539 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2542 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2545 graph
->n_total_row
++;
2554 static int compute_component_schedule(isl_ctx
*ctx
,
2555 struct isl_sched_graph
*graph
);
2557 /* Is the schedule row "sol" trivial on node "node"?
2558 * That is, is the solution zero on the dimensions orthogonal to
2559 * the previously found solutions?
2560 * Each coefficient is represented as the difference between
2561 * two non-negative values in "sol". The coefficient is then
2562 * zero if those two values are equal to each other.
2564 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
2570 pos
= 1 + node
->start
+ 1 + 2 * (node
->nparam
+ node
->rank
);
2571 len
= 2 * (node
->nvar
- node
->rank
);
2576 for (i
= 0; i
< len
; i
+= 2)
2577 if (isl_int_ne(sol
->el
[pos
+ i
], sol
->el
[pos
+ i
+ 1]))
2583 /* Is the schedule row "sol" trivial on any node where it should
2586 static int is_any_trivial(struct isl_sched_graph
*graph
,
2587 __isl_keep isl_vec
*sol
)
2591 for (i
= 0; i
< graph
->n
; ++i
) {
2592 struct isl_sched_node
*node
= &graph
->node
[i
];
2594 if (!needs_row(graph
, node
))
2596 if (is_trivial(node
, sol
))
2603 /* Construct a schedule row for each node such that as many dependences
2604 * as possible are carried and then continue with the next band.
2606 * If the computed schedule row turns out to be trivial on one or
2607 * more nodes where it should not be trivial, then we throw it away
2608 * and try again on each component separately.
2610 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2618 for (i
= 0; i
< graph
->n_edge
; ++i
)
2619 n_edge
+= graph
->edge
[i
].map
->n
;
2621 if (setup_carry_lp(ctx
, graph
) < 0)
2624 lp
= isl_basic_set_copy(graph
->lp
);
2625 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2629 if (sol
->size
== 0) {
2631 isl_die(ctx
, isl_error_internal
,
2632 "error in schedule construction", return -1);
2635 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
2636 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2638 isl_die(ctx
, isl_error_unknown
,
2639 "unable to carry dependences", return -1);
2642 if (is_any_trivial(graph
, sol
)) {
2645 return compute_component_schedule(ctx
, graph
);
2646 isl_die(ctx
, isl_error_unknown
,
2647 "unable to construct non-trivial solution", return -1);
2650 if (update_schedule(graph
, sol
, 0, 0) < 0)
2653 if (split_scaled(ctx
, graph
) < 0)
2656 return compute_next_band(ctx
, graph
);
2659 /* Are there any (non-empty) validity edges in the graph?
2661 static int has_validity_edges(struct isl_sched_graph
*graph
)
2665 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2668 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
2673 if (graph
->edge
[i
].validity
)
2680 /* Should we apply a Feautrier step?
2681 * That is, did the user request the Feautrier algorithm and are
2682 * there any validity dependences (left)?
2684 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2686 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2689 return has_validity_edges(graph
);
2692 /* Compute a schedule for a connected dependence graph using Feautrier's
2693 * multi-dimensional scheduling algorithm.
2694 * The original algorithm is described in [1].
2695 * The main idea is to minimize the number of scheduling dimensions, by
2696 * trying to satisfy as many dependences as possible per scheduling dimension.
2698 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2699 * Problem, Part II: Multi-Dimensional Time.
2700 * In Intl. Journal of Parallel Programming, 1992.
2702 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2703 struct isl_sched_graph
*graph
)
2705 return carry_dependences(ctx
, graph
);
2708 /* Compute a schedule for a connected dependence graph.
2709 * We try to find a sequence of as many schedule rows as possible that result
2710 * in non-negative dependence distances (independent of the previous rows
2711 * in the sequence, i.e., such that the sequence is tilable).
2712 * If we can't find any more rows we either
2713 * - split between SCCs and start over (assuming we found an interesting
2714 * pair of SCCs between which to split)
2715 * - continue with the next band (assuming the current band has at least
2717 * - try to carry as many dependences as possible and continue with the next
2720 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2721 * as many validity dependences as possible. When all validity dependences
2722 * are satisfied we extend the schedule to a full-dimensional schedule.
2724 * If we manage to complete the schedule, we finish off by topologically
2725 * sorting the statements based on the remaining dependences.
2727 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2728 * outermost dimension in the current band to be zero distance. If this
2729 * turns out to be impossible, we fall back on the general scheme above
2730 * and try to carry as many dependences as possible.
2732 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2736 if (detect_sccs(ctx
, graph
) < 0)
2738 if (sort_sccs(graph
) < 0)
2741 if (compute_maxvar(graph
) < 0)
2744 if (need_feautrier_step(ctx
, graph
))
2745 return compute_schedule_wcc_feautrier(ctx
, graph
);
2747 if (ctx
->opt
->schedule_outer_zero_distance
)
2750 while (graph
->n_row
< graph
->maxvar
) {
2753 graph
->src_scc
= -1;
2754 graph
->dst_scc
= -1;
2756 if (setup_lp(ctx
, graph
, force_zero
) < 0)
2758 sol
= solve_lp(graph
);
2761 if (sol
->size
== 0) {
2763 if (!ctx
->opt
->schedule_maximize_band_depth
&&
2764 graph
->n_total_row
> graph
->band_start
)
2765 return compute_next_band(ctx
, graph
);
2766 if (graph
->src_scc
>= 0)
2767 return compute_split_schedule(ctx
, graph
);
2768 if (graph
->n_total_row
> graph
->band_start
)
2769 return compute_next_band(ctx
, graph
);
2770 return carry_dependences(ctx
, graph
);
2772 if (update_schedule(graph
, sol
, 1, 1) < 0)
2777 if (graph
->n_total_row
> graph
->band_start
)
2779 return sort_statements(ctx
, graph
);
2782 /* Add a row to the schedules that separates the SCCs and move
2785 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2789 if (graph
->n_total_row
>= graph
->max_row
)
2790 isl_die(ctx
, isl_error_internal
,
2791 "too many schedule rows", return -1);
2793 for (i
= 0; i
< graph
->n
; ++i
) {
2794 struct isl_sched_node
*node
= &graph
->node
[i
];
2795 int row
= isl_mat_rows(node
->sched
);
2797 isl_map_free(node
->sched_map
);
2798 node
->sched_map
= NULL
;
2799 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2800 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2804 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2807 graph
->n_total_row
++;
2813 /* Compute a schedule for each component (identified by node->scc)
2814 * of the dependence graph separately and then combine the results.
2815 * Depending on the setting of schedule_fuse, a component may be
2816 * either weakly or strongly connected.
2818 * The band_id is adjusted such that each component has a separate id.
2819 * Note that the band_id may have already been set to a value different
2820 * from zero by compute_split_schedule.
2822 static int compute_component_schedule(isl_ctx
*ctx
,
2823 struct isl_sched_graph
*graph
)
2827 int n_total_row
, orig_total_row
;
2828 int n_band
, orig_band
;
2830 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
2831 ctx
->opt
->schedule_separate_components
)
2832 if (split_on_scc(ctx
, graph
) < 0)
2836 orig_total_row
= graph
->n_total_row
;
2838 orig_band
= graph
->n_band
;
2839 for (i
= 0; i
< graph
->n
; ++i
)
2840 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
2841 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
2843 for (i
= 0; i
< graph
->n
; ++i
)
2844 if (graph
->node
[i
].scc
== wcc
)
2847 for (i
= 0; i
< graph
->n_edge
; ++i
)
2848 if (graph
->edge
[i
].src
->scc
== wcc
&&
2849 graph
->edge
[i
].dst
->scc
== wcc
)
2852 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
2854 &edge_scc_exactly
, wcc
, 1) < 0)
2856 if (graph
->n_total_row
> n_total_row
)
2857 n_total_row
= graph
->n_total_row
;
2858 graph
->n_total_row
= orig_total_row
;
2859 if (graph
->n_band
> n_band
)
2860 n_band
= graph
->n_band
;
2861 graph
->n_band
= orig_band
;
2864 graph
->n_total_row
= n_total_row
;
2865 graph
->n_band
= n_band
;
2867 return pad_schedule(graph
);
2870 /* Compute a schedule for the given dependence graph.
2871 * We first check if the graph is connected (through validity dependences)
2872 * and, if not, compute a schedule for each component separately.
2873 * If schedule_fuse is set to minimal fusion, then we check for strongly
2874 * connected components instead and compute a separate schedule for
2875 * each such strongly connected component.
2877 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2879 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
2880 if (detect_sccs(ctx
, graph
) < 0)
2883 if (detect_wccs(ctx
, graph
) < 0)
2888 return compute_component_schedule(ctx
, graph
);
2890 return compute_schedule_wcc(ctx
, graph
);
2893 /* Compute a schedule for the given union of domains that respects
2894 * all the validity dependences.
2895 * If the default isl scheduling algorithm is used, it tries to minimize
2896 * the dependence distances over the proximity dependences.
2897 * If Feautrier's scheduling algorithm is used, the proximity dependence
2898 * distances are only minimized during the extension to a full-dimensional
2901 __isl_give isl_schedule
*isl_union_set_compute_schedule(
2902 __isl_take isl_union_set
*domain
,
2903 __isl_take isl_union_map
*validity
,
2904 __isl_take isl_union_map
*proximity
)
2906 isl_ctx
*ctx
= isl_union_set_get_ctx(domain
);
2908 struct isl_sched_graph graph
= { 0 };
2909 isl_schedule
*sched
;
2910 struct isl_extract_edge_data data
;
2912 domain
= isl_union_set_align_params(domain
,
2913 isl_union_map_get_space(validity
));
2914 domain
= isl_union_set_align_params(domain
,
2915 isl_union_map_get_space(proximity
));
2916 dim
= isl_union_set_get_space(domain
);
2917 validity
= isl_union_map_align_params(validity
, isl_space_copy(dim
));
2918 proximity
= isl_union_map_align_params(proximity
, dim
);
2923 graph
.n
= isl_union_set_n_set(domain
);
2926 if (graph_alloc(ctx
, &graph
, graph
.n
,
2927 isl_union_map_n_map(validity
) + isl_union_map_n_map(proximity
)) < 0)
2929 if (compute_max_row(&graph
, domain
) < 0)
2933 if (isl_union_set_foreach_set(domain
, &extract_node
, &graph
) < 0)
2935 if (graph_init_table(ctx
, &graph
) < 0)
2937 graph
.max_edge
[isl_edge_validity
] = isl_union_map_n_map(validity
);
2938 graph
.max_edge
[isl_edge_proximity
] = isl_union_map_n_map(proximity
);
2939 if (graph_init_edge_tables(ctx
, &graph
) < 0)
2942 data
.graph
= &graph
;
2943 data
.type
= isl_edge_validity
;
2944 if (isl_union_map_foreach_map(validity
, &extract_edge
, &data
) < 0)
2946 data
.type
= isl_edge_proximity
;
2947 if (isl_union_map_foreach_map(proximity
, &extract_edge
, &data
) < 0)
2950 if (compute_schedule(ctx
, &graph
) < 0)
2954 sched
= extract_schedule(&graph
, isl_union_set_get_space(domain
));
2956 graph_free(ctx
, &graph
);
2957 isl_union_set_free(domain
);
2958 isl_union_map_free(validity
);
2959 isl_union_map_free(proximity
);
2963 graph_free(ctx
, &graph
);
2964 isl_union_set_free(domain
);
2965 isl_union_map_free(validity
);
2966 isl_union_map_free(proximity
);
2970 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
2976 if (--sched
->ref
> 0)
2979 for (i
= 0; i
< sched
->n
; ++i
) {
2980 isl_multi_aff_free(sched
->node
[i
].sched
);
2981 free(sched
->node
[i
].band_end
);
2982 free(sched
->node
[i
].band_id
);
2983 free(sched
->node
[i
].zero
);
2985 isl_space_free(sched
->dim
);
2986 isl_band_list_free(sched
->band_forest
);
2991 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
2993 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
2996 /* Set max_out to the maximal number of output dimensions over
2999 static int update_max_out(__isl_take isl_map
*map
, void *user
)
3001 int *max_out
= user
;
3002 int n_out
= isl_map_dim(map
, isl_dim_out
);
3004 if (n_out
> *max_out
)
3011 /* Internal data structure for map_pad_range.
3013 * "max_out" is the maximal schedule dimension.
3014 * "res" collects the results.
3016 struct isl_pad_schedule_map_data
{
3021 /* Pad the range of the given map with zeros to data->max_out and
3022 * then add the result to data->res.
3024 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
3026 struct isl_pad_schedule_map_data
*data
= user
;
3028 int n_out
= isl_map_dim(map
, isl_dim_out
);
3030 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
3031 for (i
= n_out
; i
< data
->max_out
; ++i
)
3032 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
3034 data
->res
= isl_union_map_add_map(data
->res
, map
);
3041 /* Pad the ranges of the maps in the union map with zeros such they all have
3042 * the same dimension.
3044 static __isl_give isl_union_map
*pad_schedule_map(
3045 __isl_take isl_union_map
*umap
)
3047 struct isl_pad_schedule_map_data data
;
3051 if (isl_union_map_n_map(umap
) <= 1)
3055 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
3056 return isl_union_map_free(umap
);
3058 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3059 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
3060 data
.res
= isl_union_map_free(data
.res
);
3062 isl_union_map_free(umap
);
3066 /* Return an isl_union_map of the schedule. If we have already constructed
3067 * a band forest, then this band forest may have been modified so we need
3068 * to extract the isl_union_map from the forest rather than from
3069 * the originally computed schedule. This reconstructed schedule map
3070 * then needs to be padded with zeros to unify the schedule space
3071 * since the result of isl_band_list_get_suffix_schedule may not have
3072 * a unified schedule space.
3074 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
3077 isl_union_map
*umap
;
3082 if (sched
->band_forest
) {
3083 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
3084 return pad_schedule_map(umap
);
3087 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
3088 for (i
= 0; i
< sched
->n
; ++i
) {
3091 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
3092 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
3098 static __isl_give isl_band_list
*construct_band_list(
3099 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3100 int band_nr
, int *parent_active
, int n_active
);
3102 /* Construct an isl_band structure for the band in the given schedule
3103 * with sequence number band_nr for the n_active nodes marked by active.
3104 * If the nodes don't have a band with the given sequence number,
3105 * then a band without members is created.
3107 * Because of the way the schedule is constructed, we know that
3108 * the position of the band inside the schedule of a node is the same
3109 * for all active nodes.
3111 * The partial schedule for the band is created before the children
3112 * are created to that construct_band_list can refer to the partial
3113 * schedule of the parent.
3115 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
3116 __isl_keep isl_band
*parent
,
3117 int band_nr
, int *active
, int n_active
)
3120 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3122 unsigned start
, end
;
3124 band
= isl_band_alloc(ctx
);
3128 band
->schedule
= schedule
;
3129 band
->parent
= parent
;
3131 for (i
= 0; i
< schedule
->n
; ++i
)
3135 if (i
>= schedule
->n
)
3136 isl_die(ctx
, isl_error_internal
,
3137 "band without active statements", goto error
);
3139 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
3140 end
= band_nr
< schedule
->node
[i
].n_band
?
3141 schedule
->node
[i
].band_end
[band_nr
] : start
;
3142 band
->n
= end
- start
;
3144 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
3145 if (band
->n
&& !band
->zero
)
3148 for (j
= 0; j
< band
->n
; ++j
)
3149 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
3151 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
3152 for (i
= 0; i
< schedule
->n
; ++i
) {
3154 isl_pw_multi_aff
*pma
;
3160 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
3161 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3162 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
3163 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
3164 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3165 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
3171 for (i
= 0; i
< schedule
->n
; ++i
)
3172 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
3175 if (i
< schedule
->n
) {
3176 band
->children
= construct_band_list(schedule
, band
,
3177 band_nr
+ 1, active
, n_active
);
3178 if (!band
->children
)
3184 isl_band_free(band
);
3188 /* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
3190 * r is set to a negative value if anything goes wrong.
3192 * c1 stores the result of extract_int.
3193 * c2 is a temporary value used inside cmp_band_in_ancestor.
3194 * t is a temporary value used inside extract_int.
3196 * first and equal are used inside extract_int.
3197 * first is set if we are looking at the first isl_multi_aff inside
3198 * the isl_union_pw_multi_aff.
3199 * equal is set if all the isl_multi_affs have been equal so far.
3201 struct isl_cmp_band_data
{
3212 /* Check if "ma" assigns a constant value.
3213 * Note that this function is only called on isl_multi_affs
3214 * with a single output dimension.
3216 * If "ma" assigns a constant value then we compare it to data->c1
3217 * or assign it to data->c1 if this is the first isl_multi_aff we consider.
3218 * If "ma" does not assign a constant value or if it assigns a value
3219 * that is different from data->c1, then we set data->equal to zero
3220 * and terminate the check.
3222 static int multi_aff_extract_int(__isl_take isl_set
*set
,
3223 __isl_take isl_multi_aff
*ma
, void *user
)
3226 struct isl_cmp_band_data
*data
= user
;
3228 aff
= isl_multi_aff_get_aff(ma
, 0);
3229 data
->r
= isl_aff_is_cst(aff
);
3230 if (data
->r
>= 0 && data
->r
) {
3231 isl_aff_get_constant(aff
, &data
->t
);
3233 isl_int_set(data
->c1
, data
->t
);
3235 } else if (!isl_int_eq(data
->c1
, data
->t
))
3237 } else if (data
->r
>= 0 && !data
->r
)
3242 isl_multi_aff_free(ma
);
3251 /* This function is called for each isl_pw_multi_aff in
3252 * the isl_union_pw_multi_aff checked by extract_int.
3253 * Check all the isl_multi_affs inside "pma".
3255 static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff
*pma
,
3260 r
= isl_pw_multi_aff_foreach_piece(pma
, &multi_aff_extract_int
, user
);
3261 isl_pw_multi_aff_free(pma
);
3266 /* Check if "upma" assigns a single constant value to its domain.
3267 * If so, return 1 and store the result in data->c1.
3270 * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
3271 * means that either an error occurred or that we have broken off the check
3272 * because we already know the result is going to be negative.
3273 * In the latter case, data->equal is set to zero.
3275 static int extract_int(__isl_keep isl_union_pw_multi_aff
*upma
,
3276 struct isl_cmp_band_data
*data
)
3281 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
3282 &pw_multi_aff_extract_int
, data
) < 0) {
3288 return !data
->first
&& data
->equal
;
3291 /* Compare "b1" and "b2" based on the parent schedule of their ancestor
3294 * If the parent of "ancestor" also has a single member, then we
3295 * first try to compare the two band based on the partial schedule
3298 * Otherwise, or if the result is inconclusive, we look at the partial schedule
3299 * of "ancestor" itself.
3300 * In particular, we specialize the parent schedule based
3301 * on the domains of the child schedules, check if both assign
3302 * a single constant value and, if so, compare the two constant values.
3303 * If the specialized parent schedules do not assign a constant value,
3304 * then they cannot be used to order the two bands and so in this case
3307 static int cmp_band_in_ancestor(__isl_keep isl_band
*b1
,
3308 __isl_keep isl_band
*b2
, struct isl_cmp_band_data
*data
,
3309 __isl_keep isl_band
*ancestor
)
3311 isl_union_pw_multi_aff
*upma
;
3312 isl_union_set
*domain
;
3318 if (ancestor
->parent
&& ancestor
->parent
->n
== 1) {
3319 r
= cmp_band_in_ancestor(b1
, b2
, data
, ancestor
->parent
);
3326 upma
= isl_union_pw_multi_aff_copy(b1
->pma
);
3327 domain
= isl_union_pw_multi_aff_domain(upma
);
3328 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
3329 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
3330 r
= extract_int(upma
, data
);
3331 isl_union_pw_multi_aff_free(upma
);
3338 isl_int_set(data
->c2
, data
->c1
);
3340 upma
= isl_union_pw_multi_aff_copy(b2
->pma
);
3341 domain
= isl_union_pw_multi_aff_domain(upma
);
3342 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
3343 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
3344 r
= extract_int(upma
, data
);
3345 isl_union_pw_multi_aff_free(upma
);
3352 return isl_int_cmp(data
->c2
, data
->c1
);
3355 /* Compare "a" and "b" based on the parent schedule of their parent.
3357 static int cmp_band(const void *a
, const void *b
, void *user
)
3359 isl_band
*b1
= *(isl_band
* const *) a
;
3360 isl_band
*b2
= *(isl_band
* const *) b
;
3361 struct isl_cmp_band_data
*data
= user
;
3363 return cmp_band_in_ancestor(b1
, b2
, data
, b1
->parent
);
3366 /* Sort the elements in "list" based on the partial schedules of its parent
3367 * (and ancestors). In particular if the parent assigns constant values
3368 * to the domains of the bands in "list", then the elements are sorted
3369 * according to that order.
3370 * This order should be a more "natural" order for the user, but otherwise
3371 * shouldn't have any effect.
3372 * If we would be constructing an isl_band forest directly in
3373 * isl_union_set_compute_schedule then there wouldn't be any need
3374 * for a reordering, since the children would be added to the list
3375 * in their natural order automatically.
3377 * If there is only one element in the list, then there is no need to sort
3379 * If the partial schedule of the parent has more than one member
3380 * (or if there is no parent), then it's
3381 * defnitely not assigning constant values to the different children in
3382 * the list and so we wouldn't be able to use it to sort the list.
3384 static __isl_give isl_band_list
*sort_band_list(__isl_take isl_band_list
*list
,
3385 __isl_keep isl_band
*parent
)
3387 struct isl_cmp_band_data data
;
3393 if (!parent
|| parent
->n
!= 1)
3397 isl_int_init(data
.c1
);
3398 isl_int_init(data
.c2
);
3399 isl_int_init(data
.t
);
3400 isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]), &cmp_band
, &data
);
3402 list
= isl_band_list_free(list
);
3403 isl_int_clear(data
.c1
);
3404 isl_int_clear(data
.c2
);
3405 isl_int_clear(data
.t
);
3410 /* Construct a list of bands that start at the same position (with
3411 * sequence number band_nr) in the schedules of the nodes that
3412 * were active in the parent band.
3414 * A separate isl_band structure is created for each band_id
3415 * and for each node that does not have a band with sequence
3416 * number band_nr. In the latter case, a band without members
3418 * This ensures that if a band has any children, then each node
3419 * that was active in the band is active in exactly one of the children.
3421 static __isl_give isl_band_list
*construct_band_list(
3422 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3423 int band_nr
, int *parent_active
, int n_active
)
3426 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3429 isl_band_list
*list
;
3432 for (i
= 0; i
< n_active
; ++i
) {
3433 for (j
= 0; j
< schedule
->n
; ++j
) {
3434 if (!parent_active
[j
])
3436 if (schedule
->node
[j
].n_band
<= band_nr
)
3438 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
3444 for (j
= 0; j
< schedule
->n
; ++j
)
3445 if (schedule
->node
[j
].n_band
<= band_nr
)
3450 list
= isl_band_list_alloc(ctx
, n_band
);
3451 band
= construct_band(schedule
, parent
, band_nr
,
3452 parent_active
, n_active
);
3453 return isl_band_list_add(list
, band
);
3456 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3457 if (schedule
->n
&& !active
)
3460 list
= isl_band_list_alloc(ctx
, n_band
);
3462 for (i
= 0; i
< n_active
; ++i
) {
3466 for (j
= 0; j
< schedule
->n
; ++j
) {
3467 active
[j
] = parent_active
[j
] &&
3468 schedule
->node
[j
].n_band
> band_nr
&&
3469 schedule
->node
[j
].band_id
[band_nr
] == i
;
3476 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
3478 list
= isl_band_list_add(list
, band
);
3480 for (i
= 0; i
< schedule
->n
; ++i
) {
3482 if (!parent_active
[i
])
3484 if (schedule
->node
[i
].n_band
> band_nr
)
3486 for (j
= 0; j
< schedule
->n
; ++j
)
3488 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
3489 list
= isl_band_list_add(list
, band
);
3494 list
= sort_band_list(list
, parent
);
3499 /* Construct a band forest representation of the schedule and
3500 * return the list of roots.
3502 static __isl_give isl_band_list
*construct_forest(
3503 __isl_keep isl_schedule
*schedule
)
3506 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3507 isl_band_list
*forest
;
3510 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3511 if (schedule
->n
&& !active
)
3514 for (i
= 0; i
< schedule
->n
; ++i
)
3517 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
3524 /* Return the roots of a band forest representation of the schedule.
3526 __isl_give isl_band_list
*isl_schedule_get_band_forest(
3527 __isl_keep isl_schedule
*schedule
)
3531 if (!schedule
->band_forest
)
3532 schedule
->band_forest
= construct_forest(schedule
);
3533 return isl_band_list_dup(schedule
->band_forest
);
3536 /* Call "fn" on each band in the schedule in depth-first post-order.
3538 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
3539 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
3542 isl_band_list
*forest
;
3547 forest
= isl_schedule_get_band_forest(sched
);
3548 r
= isl_band_list_foreach_band(forest
, fn
, user
);
3549 isl_band_list_free(forest
);
3554 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3555 __isl_keep isl_band_list
*list
);
3557 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
3558 __isl_keep isl_band
*band
)
3560 isl_band_list
*children
;
3562 p
= isl_printer_start_line(p
);
3563 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
3564 p
= isl_printer_end_line(p
);
3566 if (!isl_band_has_children(band
))
3569 children
= isl_band_get_children(band
);
3571 p
= isl_printer_indent(p
, 4);
3572 p
= print_band_list(p
, children
);
3573 p
= isl_printer_indent(p
, -4);
3575 isl_band_list_free(children
);
3580 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3581 __isl_keep isl_band_list
*list
)
3585 n
= isl_band_list_n_band(list
);
3586 for (i
= 0; i
< n
; ++i
) {
3588 band
= isl_band_list_get_band(list
, i
);
3589 p
= print_band(p
, band
);
3590 isl_band_free(band
);
3596 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
3597 __isl_keep isl_schedule
*schedule
)
3599 isl_band_list
*forest
;
3601 forest
= isl_schedule_get_band_forest(schedule
);
3603 p
= print_band_list(p
, forest
);
3605 isl_band_list_free(forest
);
3610 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
3612 isl_printer
*printer
;
3617 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
3618 printer
= isl_printer_print_schedule(printer
, schedule
);
3620 isl_printer_free(printer
);