2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 #include <isl_ctx_private.h>
12 #include <isl_map_private.h>
13 #include <isl_space_private.h>
16 #include <isl/constraint.h>
17 #include <isl/schedule.h>
18 #include <isl_mat_private.h>
22 #include <isl_dim_map.h>
23 #include <isl_hmap_map_basic_set.h>
25 #include <isl_schedule_private.h>
26 #include <isl_band_private.h>
27 #include <isl_list_private.h>
28 #include <isl_options_private.h>
29 #include <isl_tarjan.h>
32 * The scheduling algorithm implemented in this file was inspired by
33 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
34 * Parallelization and Locality Optimization in the Polyhedral Model".
38 /* Internal information about a node that is used during the construction
40 * dim represents the space in which the domain lives
41 * sched is a matrix representation of the schedule being constructed
43 * sched_map is an isl_map representation of the same (partial) schedule
44 * sched_map may be NULL
45 * rank is the number of linearly independent rows in the linear part
47 * the columns of cmap represent a change of basis for the schedule
48 * coefficients; the first rank columns span the linear part of
50 * start is the first variable in the LP problem in the sequences that
51 * represents the schedule coefficients of this node
52 * nvar is the dimension of the domain
53 * nparam is the number of parameters or 0 if we are not constructing
54 * a parametric schedule
56 * scc is the index of SCC (or WCC) this node belongs to
58 * band contains the band index for each of the rows of the schedule.
59 * band_id is used to differentiate between separate bands at the same
60 * level within the same parent band, i.e., bands that are separated
61 * by the parent band or bands that are independent of each other.
62 * zero contains a boolean for each of the rows of the schedule,
63 * indicating whether the corresponding scheduling dimension results
64 * in zero dependence distances within its band and with respect
65 * to the proximity edges.
67 struct isl_sched_node
{
84 static int node_has_dim(const void *entry
, const void *val
)
86 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
87 isl_space
*dim
= (isl_space
*)val
;
89 return isl_space_is_equal(node
->dim
, dim
);
92 /* An edge in the dependence graph. An edge may be used to
93 * ensure validity of the generated schedule, to minimize the dependence
96 * map is the dependence relation
97 * src is the source node
98 * dst is the sink node
99 * validity is set if the edge is used to ensure correctness
100 * proximity is set if the edge is used to minimize dependence distances
102 * For validity edges, start and end mark the sequence of inequality
103 * constraints in the LP problem that encode the validity constraint
104 * corresponding to this edge.
106 struct isl_sched_edge
{
109 struct isl_sched_node
*src
;
110 struct isl_sched_node
*dst
;
120 isl_edge_validity
= 0,
121 isl_edge_first
= isl_edge_validity
,
123 isl_edge_last
= isl_edge_proximity
126 /* Internal information about the dependence graph used during
127 * the construction of the schedule.
129 * intra_hmap is a cache, mapping dependence relations to their dual,
130 * for dependences from a node to itself
131 * inter_hmap is a cache, mapping dependence relations to their dual,
132 * for dependences between distinct nodes
134 * n is the number of nodes
135 * node is the list of nodes
136 * maxvar is the maximal number of variables over all nodes
137 * max_row is the allocated number of rows in the schedule
138 * n_row is the current (maximal) number of linearly independent
139 * rows in the node schedules
140 * n_total_row is the current number of rows in the node schedules
141 * n_band is the current number of completed bands
142 * band_start is the starting row in the node schedules of the current band
143 * root is set if this graph is the original dependence graph,
144 * without any splitting
146 * sorted contains a list of node indices sorted according to the
147 * SCC to which a node belongs
149 * n_edge is the number of edges
150 * edge is the list of edges
151 * max_edge contains the maximal number of edges of each type;
152 * in particular, it contains the number of edges in the inital graph.
153 * edge_table contains pointers into the edge array, hashed on the source
154 * and sink spaces; there is one such table for each type;
155 * a given edge may be referenced from more than one table
156 * if the corresponding relation appears in more than of the
157 * sets of dependences
159 * node_table contains pointers into the node array, hashed on the space
161 * region contains a list of variable sequences that should be non-trivial
163 * lp contains the (I)LP problem used to obtain new schedule rows
165 * src_scc and dst_scc are the source and sink SCCs of an edge with
166 * conflicting constraints
168 * scc represents the number of components
170 struct isl_sched_graph
{
171 isl_hmap_map_basic_set
*intra_hmap
;
172 isl_hmap_map_basic_set
*inter_hmap
;
174 struct isl_sched_node
*node
;
188 struct isl_sched_edge
*edge
;
190 int max_edge
[isl_edge_last
+ 1];
191 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
193 struct isl_hash_table
*node_table
;
194 struct isl_region
*region
;
204 /* Initialize node_table based on the list of nodes.
206 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
210 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
211 if (!graph
->node_table
)
214 for (i
= 0; i
< graph
->n
; ++i
) {
215 struct isl_hash_table_entry
*entry
;
218 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
219 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
221 graph
->node
[i
].dim
, 1);
224 entry
->data
= &graph
->node
[i
];
230 /* Return a pointer to the node that lives within the given space,
231 * or NULL if there is no such node.
233 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
234 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
236 struct isl_hash_table_entry
*entry
;
239 hash
= isl_space_get_hash(dim
);
240 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
241 &node_has_dim
, dim
, 0);
243 return entry
? entry
->data
: NULL
;
246 static int edge_has_src_and_dst(const void *entry
, const void *val
)
248 const struct isl_sched_edge
*edge
= entry
;
249 const struct isl_sched_edge
*temp
= val
;
251 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
254 /* Add the given edge to graph->edge_table[type].
256 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
257 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
259 struct isl_hash_table_entry
*entry
;
262 hash
= isl_hash_init();
263 hash
= isl_hash_builtin(hash
, edge
->src
);
264 hash
= isl_hash_builtin(hash
, edge
->dst
);
265 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
266 &edge_has_src_and_dst
, edge
, 1);
274 /* Allocate the edge_tables based on the maximal number of edges of
277 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
281 for (i
= 0; i
<= isl_edge_last
; ++i
) {
282 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
284 if (!graph
->edge_table
[i
])
291 /* If graph->edge_table[type] contains an edge from the given source
292 * to the given destination, then return the hash table entry of this edge.
293 * Otherwise, return NULL.
295 static struct isl_hash_table_entry
*graph_find_edge_entry(
296 struct isl_sched_graph
*graph
,
297 enum isl_edge_type type
,
298 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
300 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
302 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
304 hash
= isl_hash_init();
305 hash
= isl_hash_builtin(hash
, temp
.src
);
306 hash
= isl_hash_builtin(hash
, temp
.dst
);
307 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
308 &edge_has_src_and_dst
, &temp
, 0);
312 /* If graph->edge_table[type] contains an edge from the given source
313 * to the given destination, then return this edge.
314 * Otherwise, return NULL.
316 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
317 enum isl_edge_type type
,
318 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
320 struct isl_hash_table_entry
*entry
;
322 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
329 /* Check whether the dependence graph has an edge of the give type
330 * between the given two nodes.
332 static int graph_has_edge(struct isl_sched_graph
*graph
,
333 enum isl_edge_type type
,
334 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
336 struct isl_sched_edge
*edge
;
339 edge
= graph_find_edge(graph
, type
, src
, dst
);
343 empty
= isl_map_plain_is_empty(edge
->map
);
350 /* If there is an edge from the given source to the given destination
351 * of any type then return this edge.
352 * Otherwise, return NULL.
354 static struct isl_sched_edge
*graph_find_any_edge(struct isl_sched_graph
*graph
,
355 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
357 enum isl_edge_type i
;
358 struct isl_sched_edge
*edge
;
360 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
361 edge
= graph_find_edge(graph
, i
, src
, dst
);
369 /* Remove the given edge from all the edge_tables that refer to it.
371 static void graph_remove_edge(struct isl_sched_graph
*graph
,
372 struct isl_sched_edge
*edge
)
374 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
375 enum isl_edge_type i
;
377 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
378 struct isl_hash_table_entry
*entry
;
380 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
383 if (entry
->data
!= edge
)
385 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
389 /* Check whether the dependence graph has any edge
390 * between the given two nodes.
392 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
393 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
395 enum isl_edge_type i
;
398 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
399 r
= graph_has_edge(graph
, i
, src
, dst
);
407 /* Check whether the dependence graph has a validity edge
408 * between the given two nodes.
410 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
411 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
413 return graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
416 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
417 int n_node
, int n_edge
)
422 graph
->n_edge
= n_edge
;
423 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
424 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
425 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
426 graph
->edge
= isl_calloc_array(ctx
,
427 struct isl_sched_edge
, graph
->n_edge
);
429 graph
->intra_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
430 graph
->inter_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
432 if (!graph
->node
|| !graph
->region
|| !graph
->edge
|| !graph
->sorted
)
435 for(i
= 0; i
< graph
->n
; ++i
)
436 graph
->sorted
[i
] = i
;
441 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
445 isl_hmap_map_basic_set_free(ctx
, graph
->intra_hmap
);
446 isl_hmap_map_basic_set_free(ctx
, graph
->inter_hmap
);
448 for (i
= 0; i
< graph
->n
; ++i
) {
449 isl_space_free(graph
->node
[i
].dim
);
450 isl_mat_free(graph
->node
[i
].sched
);
451 isl_map_free(graph
->node
[i
].sched_map
);
452 isl_mat_free(graph
->node
[i
].cmap
);
454 free(graph
->node
[i
].band
);
455 free(graph
->node
[i
].band_id
);
456 free(graph
->node
[i
].zero
);
461 for (i
= 0; i
< graph
->n_edge
; ++i
)
462 isl_map_free(graph
->edge
[i
].map
);
465 for (i
= 0; i
<= isl_edge_last
; ++i
)
466 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
467 isl_hash_table_free(ctx
, graph
->node_table
);
468 isl_basic_set_free(graph
->lp
);
471 /* For each "set" on which this function is called, increment
472 * graph->n by one and update graph->maxvar.
474 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
476 struct isl_sched_graph
*graph
= user
;
477 int nvar
= isl_set_dim(set
, isl_dim_set
);
480 if (nvar
> graph
->maxvar
)
481 graph
->maxvar
= nvar
;
488 /* Compute the number of rows that should be allocated for the schedule.
489 * The graph can be split at most "n - 1" times, there can be at most
490 * two rows for each dimension in the iteration domains (in particular,
491 * we usually have one row, but it may be split by split_scaled),
492 * and there can be one extra row for ordering the statements.
493 * Note that if we have actually split "n - 1" times, then no ordering
494 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
496 static int compute_max_row(struct isl_sched_graph
*graph
,
497 __isl_keep isl_union_set
*domain
)
501 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
503 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
508 /* Add a new node to the graph representing the given set.
510 static int extract_node(__isl_take isl_set
*set
, void *user
)
516 struct isl_sched_graph
*graph
= user
;
517 int *band
, *band_id
, *zero
;
519 ctx
= isl_set_get_ctx(set
);
520 dim
= isl_set_get_space(set
);
522 nvar
= isl_space_dim(dim
, isl_dim_set
);
523 nparam
= isl_space_dim(dim
, isl_dim_param
);
524 if (!ctx
->opt
->schedule_parametric
)
526 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
527 graph
->node
[graph
->n
].dim
= dim
;
528 graph
->node
[graph
->n
].nvar
= nvar
;
529 graph
->node
[graph
->n
].nparam
= nparam
;
530 graph
->node
[graph
->n
].sched
= sched
;
531 graph
->node
[graph
->n
].sched_map
= NULL
;
532 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
533 graph
->node
[graph
->n
].band
= band
;
534 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
535 graph
->node
[graph
->n
].band_id
= band_id
;
536 zero
= isl_calloc_array(ctx
, int, graph
->max_row
);
537 graph
->node
[graph
->n
].zero
= zero
;
540 if (!sched
|| !band
|| !band_id
|| !zero
)
546 struct isl_extract_edge_data
{
547 enum isl_edge_type type
;
548 struct isl_sched_graph
*graph
;
551 /* Add a new edge to the graph based on the given map
552 * and add it to data->graph->edge_table[data->type].
553 * If a dependence relation of a given type happens to be identical
554 * to one of the dependence relations of a type that was added before,
555 * then we don't create a new edge, but instead mark the original edge
556 * as also representing a dependence of the current type.
558 static int extract_edge(__isl_take isl_map
*map
, void *user
)
560 isl_ctx
*ctx
= isl_map_get_ctx(map
);
561 struct isl_extract_edge_data
*data
= user
;
562 struct isl_sched_graph
*graph
= data
->graph
;
563 struct isl_sched_node
*src
, *dst
;
565 struct isl_sched_edge
*edge
;
568 dim
= isl_space_domain(isl_map_get_space(map
));
569 src
= graph_find_node(ctx
, graph
, dim
);
571 dim
= isl_space_range(isl_map_get_space(map
));
572 dst
= graph_find_node(ctx
, graph
, dim
);
580 graph
->edge
[graph
->n_edge
].src
= src
;
581 graph
->edge
[graph
->n_edge
].dst
= dst
;
582 graph
->edge
[graph
->n_edge
].map
= map
;
583 if (data
->type
== isl_edge_validity
) {
584 graph
->edge
[graph
->n_edge
].validity
= 1;
585 graph
->edge
[graph
->n_edge
].proximity
= 0;
587 if (data
->type
== isl_edge_proximity
) {
588 graph
->edge
[graph
->n_edge
].validity
= 0;
589 graph
->edge
[graph
->n_edge
].proximity
= 1;
593 edge
= graph_find_any_edge(graph
, src
, dst
);
595 return graph_edge_table_add(ctx
, graph
, data
->type
,
596 &graph
->edge
[graph
->n_edge
- 1]);
597 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
601 return graph_edge_table_add(ctx
, graph
, data
->type
,
602 &graph
->edge
[graph
->n_edge
- 1]);
605 edge
->validity
|= graph
->edge
[graph
->n_edge
].validity
;
606 edge
->proximity
|= graph
->edge
[graph
->n_edge
].proximity
;
609 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
612 /* Check whether there is any dependence from node[j] to node[i]
613 * or from node[i] to node[j].
615 static int node_follows_weak(int i
, int j
, void *user
)
618 struct isl_sched_graph
*graph
= user
;
620 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
623 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
626 /* Check whether there is a validity dependence from node[j] to node[i],
627 * forcing node[i] to follow node[j].
629 static int node_follows_strong(int i
, int j
, void *user
)
631 struct isl_sched_graph
*graph
= user
;
633 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
636 /* Use Tarjan's algorithm for computing the strongly connected components
637 * in the dependence graph (only validity edges).
638 * If weak is set, we consider the graph to be undirected and
639 * we effectively compute the (weakly) connected components.
640 * Additionally, we also consider other edges when weak is set.
642 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
645 struct isl_tarjan_graph
*g
= NULL
;
647 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
648 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
656 while (g
->order
[i
] != -1) {
657 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
665 isl_tarjan_graph_free(g
);
670 /* Apply Tarjan's algorithm to detect the strongly connected components
671 * in the dependence graph.
673 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
675 return detect_ccs(ctx
, graph
, 0);
678 /* Apply Tarjan's algorithm to detect the (weakly) connected components
679 * in the dependence graph.
681 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
683 return detect_ccs(ctx
, graph
, 1);
686 static int cmp_scc(const void *a
, const void *b
, void *data
)
688 struct isl_sched_graph
*graph
= data
;
692 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
695 /* Sort the elements of graph->sorted according to the corresponding SCCs.
697 static int sort_sccs(struct isl_sched_graph
*graph
)
699 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
702 /* Given a dependence relation R from a node to itself,
703 * construct the set of coefficients of valid constraints for elements
704 * in that dependence relation.
705 * In particular, the result contains tuples of coefficients
706 * c_0, c_n, c_x such that
708 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
712 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
714 * We choose here to compute the dual of delta R.
715 * Alternatively, we could have computed the dual of R, resulting
716 * in a set of tuples c_0, c_n, c_x, c_y, and then
717 * plugged in (c_0, c_n, c_x, -c_x).
719 static __isl_give isl_basic_set
*intra_coefficients(
720 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
722 isl_ctx
*ctx
= isl_map_get_ctx(map
);
726 if (isl_hmap_map_basic_set_has(ctx
, graph
->intra_hmap
, map
))
727 return isl_hmap_map_basic_set_get(ctx
, graph
->intra_hmap
, map
);
729 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
730 coef
= isl_set_coefficients(delta
);
731 isl_hmap_map_basic_set_set(ctx
, graph
->intra_hmap
, map
,
732 isl_basic_set_copy(coef
));
737 /* Given a dependence relation R, * construct the set of coefficients
738 * of valid constraints for elements in that dependence relation.
739 * In particular, the result contains tuples of coefficients
740 * c_0, c_n, c_x, c_y such that
742 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
745 static __isl_give isl_basic_set
*inter_coefficients(
746 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
748 isl_ctx
*ctx
= isl_map_get_ctx(map
);
752 if (isl_hmap_map_basic_set_has(ctx
, graph
->inter_hmap
, map
))
753 return isl_hmap_map_basic_set_get(ctx
, graph
->inter_hmap
, map
);
755 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
756 coef
= isl_set_coefficients(set
);
757 isl_hmap_map_basic_set_set(ctx
, graph
->inter_hmap
, map
,
758 isl_basic_set_copy(coef
));
763 /* Add constraints to graph->lp that force validity for the given
764 * dependence from a node i to itself.
765 * That is, add constraints that enforce
767 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
768 * = c_i_x (y - x) >= 0
770 * for each (x,y) in R.
771 * We obtain general constraints on coefficients (c_0, c_n, c_x)
772 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
773 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
774 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
776 * Actually, we do not construct constraints for the c_i_x themselves,
777 * but for the coefficients of c_i_x written as a linear combination
778 * of the columns in node->cmap.
780 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
781 struct isl_sched_edge
*edge
)
784 isl_map
*map
= isl_map_copy(edge
->map
);
785 isl_ctx
*ctx
= isl_map_get_ctx(map
);
787 isl_dim_map
*dim_map
;
789 struct isl_sched_node
*node
= edge
->src
;
791 coef
= intra_coefficients(graph
, map
);
793 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
795 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
796 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
800 total
= isl_basic_set_total_dim(graph
->lp
);
801 dim_map
= isl_dim_map_alloc(ctx
, total
);
802 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
803 isl_space_dim(dim
, isl_dim_set
), 1,
805 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
806 isl_space_dim(dim
, isl_dim_set
), 1,
808 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
809 coef
->n_eq
, coef
->n_ineq
);
810 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
820 /* Add constraints to graph->lp that force validity for the given
821 * dependence from node i to node j.
822 * That is, add constraints that enforce
824 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
826 * for each (x,y) in R.
827 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
828 * of valid constraints for R and then plug in
829 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
830 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
831 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
832 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
834 * Actually, we do not construct constraints for the c_*_x themselves,
835 * but for the coefficients of c_*_x written as a linear combination
836 * of the columns in node->cmap.
838 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
839 struct isl_sched_edge
*edge
)
842 isl_map
*map
= isl_map_copy(edge
->map
);
843 isl_ctx
*ctx
= isl_map_get_ctx(map
);
845 isl_dim_map
*dim_map
;
847 struct isl_sched_node
*src
= edge
->src
;
848 struct isl_sched_node
*dst
= edge
->dst
;
850 coef
= inter_coefficients(graph
, map
);
852 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
854 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
855 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
856 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
857 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
858 isl_mat_copy(dst
->cmap
));
862 total
= isl_basic_set_total_dim(graph
->lp
);
863 dim_map
= isl_dim_map_alloc(ctx
, total
);
865 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
866 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
867 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
868 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
869 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
871 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
872 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
875 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
876 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
877 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
878 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
879 isl_space_dim(dim
, isl_dim_set
), 1,
881 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
882 isl_space_dim(dim
, isl_dim_set
), 1,
885 edge
->start
= graph
->lp
->n_ineq
;
886 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
887 coef
->n_eq
, coef
->n_ineq
);
888 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
893 edge
->end
= graph
->lp
->n_ineq
;
901 /* Add constraints to graph->lp that bound the dependence distance for the given
902 * dependence from a node i to itself.
903 * If s = 1, we add the constraint
905 * c_i_x (y - x) <= m_0 + m_n n
909 * -c_i_x (y - x) + m_0 + m_n n >= 0
911 * for each (x,y) in R.
912 * If s = -1, we add the constraint
914 * -c_i_x (y - x) <= m_0 + m_n n
918 * c_i_x (y - x) + m_0 + m_n n >= 0
920 * for each (x,y) in R.
921 * We obtain general constraints on coefficients (c_0, c_n, c_x)
922 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
923 * with each coefficient (except m_0) represented as a pair of non-negative
926 * Actually, we do not construct constraints for the c_i_x themselves,
927 * but for the coefficients of c_i_x written as a linear combination
928 * of the columns in node->cmap.
930 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
931 struct isl_sched_edge
*edge
, int s
)
935 isl_map
*map
= isl_map_copy(edge
->map
);
936 isl_ctx
*ctx
= isl_map_get_ctx(map
);
938 isl_dim_map
*dim_map
;
940 struct isl_sched_node
*node
= edge
->src
;
942 coef
= intra_coefficients(graph
, map
);
944 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
946 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
947 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
951 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
952 total
= isl_basic_set_total_dim(graph
->lp
);
953 dim_map
= isl_dim_map_alloc(ctx
, total
);
954 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
955 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
956 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
957 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
958 isl_space_dim(dim
, isl_dim_set
), 1,
960 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
961 isl_space_dim(dim
, isl_dim_set
), 1,
963 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
964 coef
->n_eq
, coef
->n_ineq
);
965 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
975 /* Add constraints to graph->lp that bound the dependence distance for the given
976 * dependence from node i to node j.
977 * If s = 1, we add the constraint
979 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
984 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
987 * for each (x,y) in R.
988 * If s = -1, we add the constraint
990 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
995 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
998 * for each (x,y) in R.
999 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1000 * of valid constraints for R and then plug in
1001 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1003 * with each coefficient (except m_0, c_j_0 and c_i_0)
1004 * represented as a pair of non-negative coefficients.
1006 * Actually, we do not construct constraints for the c_*_x themselves,
1007 * but for the coefficients of c_*_x written as a linear combination
1008 * of the columns in node->cmap.
1010 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1011 struct isl_sched_edge
*edge
, int s
)
1015 isl_map
*map
= isl_map_copy(edge
->map
);
1016 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1018 isl_dim_map
*dim_map
;
1019 isl_basic_set
*coef
;
1020 struct isl_sched_node
*src
= edge
->src
;
1021 struct isl_sched_node
*dst
= edge
->dst
;
1023 coef
= inter_coefficients(graph
, map
);
1025 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1027 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1028 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1029 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1030 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1031 isl_mat_copy(dst
->cmap
));
1035 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1036 total
= isl_basic_set_total_dim(graph
->lp
);
1037 dim_map
= isl_dim_map_alloc(ctx
, total
);
1039 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1040 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1041 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1043 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1044 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1045 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1046 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1047 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1049 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1050 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1053 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1054 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1055 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1056 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1057 isl_space_dim(dim
, isl_dim_set
), 1,
1059 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1060 isl_space_dim(dim
, isl_dim_set
), 1,
1063 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1064 coef
->n_eq
, coef
->n_ineq
);
1065 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1067 isl_space_free(dim
);
1071 isl_space_free(dim
);
1075 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1079 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1080 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1081 if (!edge
->validity
)
1083 if (edge
->src
!= edge
->dst
)
1085 if (add_intra_validity_constraints(graph
, edge
) < 0)
1089 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1090 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1091 if (!edge
->validity
)
1093 if (edge
->src
== edge
->dst
)
1095 if (add_inter_validity_constraints(graph
, edge
) < 0)
1102 /* Add constraints to graph->lp that bound the dependence distance
1103 * for all dependence relations.
1104 * If a given proximity dependence is identical to a validity
1105 * dependence, then the dependence distance is already bounded
1106 * from below (by zero), so we only need to bound the distance
1108 * Otherwise, we need to bound the distance both from above and from below.
1110 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1114 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1115 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1116 if (!edge
->proximity
)
1118 if (edge
->src
== edge
->dst
&&
1119 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
1121 if (edge
->src
!= edge
->dst
&&
1122 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
1126 if (edge
->src
== edge
->dst
&&
1127 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
1129 if (edge
->src
!= edge
->dst
&&
1130 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1137 /* Compute a basis for the rows in the linear part of the schedule
1138 * and extend this basis to a full basis. The remaining rows
1139 * can then be used to force linear independence from the rows
1142 * In particular, given the schedule rows S, we compute
1146 * with H the Hermite normal form of S. That is, all but the
1147 * first rank columns of Q are zero and so each row in S is
1148 * a linear combination of the first rank rows of Q.
1149 * The matrix Q is then transposed because we will write the
1150 * coefficients of the next schedule row as a column vector s
1151 * and express this s as a linear combination s = Q c of the
1154 static int node_update_cmap(struct isl_sched_node
*node
)
1157 int n_row
= isl_mat_rows(node
->sched
);
1159 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1160 1 + node
->nparam
, node
->nvar
);
1162 H
= isl_mat_left_hermite(H
, 0, NULL
, &Q
);
1163 isl_mat_free(node
->cmap
);
1164 node
->cmap
= isl_mat_transpose(Q
);
1165 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1168 if (!node
->cmap
|| node
->rank
< 0)
1173 /* Count the number of equality and inequality constraints
1174 * that will be added for the given map.
1175 * If carry is set, then we are counting the number of (validity)
1176 * constraints that will be added in setup_carry_lp and we count
1177 * each edge exactly once. Otherwise, we count as follows
1178 * validity -> 1 (>= 0)
1179 * validity+proximity -> 2 (>= 0 and upper bound)
1180 * proximity -> 2 (lower and upper bound)
1182 static int count_map_constraints(struct isl_sched_graph
*graph
,
1183 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1184 int *n_eq
, int *n_ineq
, int carry
)
1186 isl_basic_set
*coef
;
1187 int f
= carry
? 1 : edge
->proximity
? 2 : 1;
1189 if (carry
&& !edge
->validity
) {
1194 if (edge
->src
== edge
->dst
)
1195 coef
= intra_coefficients(graph
, map
);
1197 coef
= inter_coefficients(graph
, map
);
1200 *n_eq
+= f
* coef
->n_eq
;
1201 *n_ineq
+= f
* coef
->n_ineq
;
1202 isl_basic_set_free(coef
);
1207 /* Count the number of equality and inequality constraints
1208 * that will be added to the main lp problem.
1209 * We count as follows
1210 * validity -> 1 (>= 0)
1211 * validity+proximity -> 2 (>= 0 and upper bound)
1212 * proximity -> 2 (lower and upper bound)
1214 static int count_constraints(struct isl_sched_graph
*graph
,
1215 int *n_eq
, int *n_ineq
)
1219 *n_eq
= *n_ineq
= 0;
1220 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1221 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1222 isl_map
*map
= isl_map_copy(edge
->map
);
1224 if (count_map_constraints(graph
, edge
, map
,
1225 n_eq
, n_ineq
, 0) < 0)
1232 /* Add constraints that bound the values of the variable and parameter
1233 * coefficients of the schedule.
1235 * The maximal value of the coefficients is defined by the option
1236 * 'schedule_max_coefficient'.
1238 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1239 struct isl_sched_graph
*graph
)
1242 int max_coefficient
;
1245 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1247 if (max_coefficient
== -1)
1250 total
= isl_basic_set_total_dim(graph
->lp
);
1252 for (i
= 0; i
< graph
->n
; ++i
) {
1253 struct isl_sched_node
*node
= &graph
->node
[i
];
1254 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1256 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1259 dim
= 1 + node
->start
+ 1 + j
;
1260 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1261 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1262 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1269 /* Construct an ILP problem for finding schedule coefficients
1270 * that result in non-negative, but small dependence distances
1271 * over all dependences.
1272 * In particular, the dependence distances over proximity edges
1273 * are bounded by m_0 + m_n n and we compute schedule coefficients
1274 * with small values (preferably zero) of m_n and m_0.
1276 * All variables of the ILP are non-negative. The actual coefficients
1277 * may be negative, so each coefficient is represented as the difference
1278 * of two non-negative variables. The negative part always appears
1279 * immediately before the positive part.
1280 * Other than that, the variables have the following order
1282 * - sum of positive and negative parts of m_n coefficients
1284 * - sum of positive and negative parts of all c_n coefficients
1285 * (unconstrained when computing non-parametric schedules)
1286 * - sum of positive and negative parts of all c_x coefficients
1287 * - positive and negative parts of m_n coefficients
1290 * - positive and negative parts of c_i_n (if parametric)
1291 * - positive and negative parts of c_i_x
1293 * The c_i_x are not represented directly, but through the columns of
1294 * node->cmap. That is, the computed values are for variable t_i_x
1295 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1297 * The constraints are those from the edges plus two or three equalities
1298 * to express the sums.
1300 * If force_zero is set, then we add equalities to ensure that
1301 * the sum of the m_n coefficients and m_0 are both zero.
1303 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1314 int max_constant_term
;
1315 int max_coefficient
;
1317 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1318 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1320 parametric
= ctx
->opt
->schedule_parametric
;
1321 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1323 total
= param_pos
+ 2 * nparam
;
1324 for (i
= 0; i
< graph
->n
; ++i
) {
1325 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1326 if (node_update_cmap(node
) < 0)
1328 node
->start
= total
;
1329 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1332 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1335 dim
= isl_space_set_alloc(ctx
, 0, total
);
1336 isl_basic_set_free(graph
->lp
);
1337 n_eq
+= 2 + parametric
+ force_zero
;
1338 if (max_constant_term
!= -1)
1340 if (max_coefficient
!= -1)
1341 for (i
= 0; i
< graph
->n
; ++i
)
1342 n_ineq
+= 2 * graph
->node
[i
].nparam
+
1343 2 * graph
->node
[i
].nvar
;
1345 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1347 k
= isl_basic_set_alloc_equality(graph
->lp
);
1350 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1352 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1353 for (i
= 0; i
< 2 * nparam
; ++i
)
1354 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1357 k
= isl_basic_set_alloc_equality(graph
->lp
);
1360 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1361 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1365 k
= isl_basic_set_alloc_equality(graph
->lp
);
1368 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1369 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1370 for (i
= 0; i
< graph
->n
; ++i
) {
1371 int pos
= 1 + graph
->node
[i
].start
+ 1;
1373 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1374 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1378 k
= isl_basic_set_alloc_equality(graph
->lp
);
1381 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1382 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1383 for (i
= 0; i
< graph
->n
; ++i
) {
1384 struct isl_sched_node
*node
= &graph
->node
[i
];
1385 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1387 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1388 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1391 if (max_constant_term
!= -1)
1392 for (i
= 0; i
< graph
->n
; ++i
) {
1393 struct isl_sched_node
*node
= &graph
->node
[i
];
1394 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1397 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1398 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1399 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1402 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1404 if (add_all_validity_constraints(graph
) < 0)
1406 if (add_all_proximity_constraints(graph
) < 0)
1412 /* Analyze the conflicting constraint found by
1413 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1414 * constraint of one of the edges between distinct nodes, living, moreover
1415 * in distinct SCCs, then record the source and sink SCC as this may
1416 * be a good place to cut between SCCs.
1418 static int check_conflict(int con
, void *user
)
1421 struct isl_sched_graph
*graph
= user
;
1423 if (graph
->src_scc
>= 0)
1426 con
-= graph
->lp
->n_eq
;
1428 if (con
>= graph
->lp
->n_ineq
)
1431 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1432 if (!graph
->edge
[i
].validity
)
1434 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1436 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1438 if (graph
->edge
[i
].start
> con
)
1440 if (graph
->edge
[i
].end
<= con
)
1442 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1443 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1449 /* Check whether the next schedule row of the given node needs to be
1450 * non-trivial. Lower-dimensional domains may have some trivial rows,
1451 * but as soon as the number of remaining required non-trivial rows
1452 * is as large as the number or remaining rows to be computed,
1453 * all remaining rows need to be non-trivial.
1455 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1457 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1460 /* Solve the ILP problem constructed in setup_lp.
1461 * For each node such that all the remaining rows of its schedule
1462 * need to be non-trivial, we construct a non-triviality region.
1463 * This region imposes that the next row is independent of previous rows.
1464 * In particular the coefficients c_i_x are represented by t_i_x
1465 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1466 * its first columns span the rows of the previously computed part
1467 * of the schedule. The non-triviality region enforces that at least
1468 * one of the remaining components of t_i_x is non-zero, i.e.,
1469 * that the new schedule row depends on at least one of the remaining
1472 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1478 for (i
= 0; i
< graph
->n
; ++i
) {
1479 struct isl_sched_node
*node
= &graph
->node
[i
];
1480 int skip
= node
->rank
;
1481 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1482 if (needs_row(graph
, node
))
1483 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1485 graph
->region
[i
].len
= 0;
1487 lp
= isl_basic_set_copy(graph
->lp
);
1488 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1489 graph
->region
, &check_conflict
, graph
);
1493 /* Update the schedules of all nodes based on the given solution
1494 * of the LP problem.
1495 * The new row is added to the current band.
1496 * All possibly negative coefficients are encoded as a difference
1497 * of two non-negative variables, so we need to perform the subtraction
1498 * here. Moreover, if use_cmap is set, then the solution does
1499 * not refer to the actual coefficients c_i_x, but instead to variables
1500 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1501 * In this case, we then also need to perform this multiplication
1502 * to obtain the values of c_i_x.
1504 * If check_zero is set, then the first two coordinates of sol are
1505 * assumed to correspond to the dependence distance. If these two
1506 * coordinates are zero, then the corresponding scheduling dimension
1507 * is marked as being zero distance.
1509 static int update_schedule(struct isl_sched_graph
*graph
,
1510 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1514 isl_vec
*csol
= NULL
;
1519 isl_die(sol
->ctx
, isl_error_internal
,
1520 "no solution found", goto error
);
1521 if (graph
->n_total_row
>= graph
->max_row
)
1522 isl_die(sol
->ctx
, isl_error_internal
,
1523 "too many schedule rows", goto error
);
1526 zero
= isl_int_is_zero(sol
->el
[1]) &&
1527 isl_int_is_zero(sol
->el
[2]);
1529 for (i
= 0; i
< graph
->n
; ++i
) {
1530 struct isl_sched_node
*node
= &graph
->node
[i
];
1531 int pos
= node
->start
;
1532 int row
= isl_mat_rows(node
->sched
);
1535 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1539 isl_map_free(node
->sched_map
);
1540 node
->sched_map
= NULL
;
1541 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1544 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1546 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1547 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1548 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1549 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1550 for (j
= 0; j
< node
->nparam
; ++j
)
1551 node
->sched
= isl_mat_set_element(node
->sched
,
1552 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1553 for (j
= 0; j
< node
->nvar
; ++j
)
1554 isl_int_set(csol
->el
[j
],
1555 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1557 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1561 for (j
= 0; j
< node
->nvar
; ++j
)
1562 node
->sched
= isl_mat_set_element(node
->sched
,
1563 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1564 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1565 node
->zero
[graph
->n_total_row
] = zero
;
1571 graph
->n_total_row
++;
1580 /* Convert node->sched into a multi_aff and return this multi_aff.
1582 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
1583 struct isl_sched_node
*node
)
1587 isl_local_space
*ls
;
1593 nrow
= isl_mat_rows(node
->sched
);
1594 ncol
= isl_mat_cols(node
->sched
) - 1;
1595 space
= isl_space_from_domain(isl_space_copy(node
->dim
));
1596 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
1597 ma
= isl_multi_aff_zero(space
);
1598 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
1602 for (i
= 0; i
< nrow
; ++i
) {
1603 aff
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1604 isl_mat_get_element(node
->sched
, i
, 0, &v
);
1605 aff
= isl_aff_set_constant(aff
, v
);
1606 for (j
= 0; j
< node
->nparam
; ++j
) {
1607 isl_mat_get_element(node
->sched
, i
, 1 + j
, &v
);
1608 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
1610 for (j
= 0; j
< node
->nvar
; ++j
) {
1611 isl_mat_get_element(node
->sched
,
1612 i
, 1 + node
->nparam
+ j
, &v
);
1613 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
1615 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
1620 isl_local_space_free(ls
);
1625 /* Convert node->sched into a map and return this map.
1627 * The result is cached in node->sched_map, which needs to be released
1628 * whenever node->sched is updated.
1630 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1632 if (!node
->sched_map
) {
1635 ma
= node_extract_schedule_multi_aff(node
);
1636 node
->sched_map
= isl_map_from_multi_aff(ma
);
1639 return isl_map_copy(node
->sched_map
);
1642 /* Update the given dependence relation based on the current schedule.
1643 * That is, intersect the dependence relation with a map expressing
1644 * that source and sink are executed within the same iteration of
1645 * the current schedule.
1646 * This is not the most efficient way, but this shouldn't be a critical
1649 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1650 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1652 isl_map
*src_sched
, *dst_sched
, *id
;
1654 src_sched
= node_extract_schedule(src
);
1655 dst_sched
= node_extract_schedule(dst
);
1656 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1657 return isl_map_intersect(map
, id
);
1660 /* Update the dependence relations of all edges based on the current schedule.
1661 * If a dependence is carried completely by the current schedule, then
1662 * it is removed from the edge_tables. It is kept in the list of edges
1663 * as otherwise all edge_tables would have to be recomputed.
1665 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1669 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1670 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1671 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1675 if (isl_map_plain_is_empty(edge
->map
))
1676 graph_remove_edge(graph
, edge
);
1682 static void next_band(struct isl_sched_graph
*graph
)
1684 graph
->band_start
= graph
->n_total_row
;
1688 /* Topologically sort statements mapped to the same schedule iteration
1689 * and add a row to the schedule corresponding to this order.
1691 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1698 if (update_edges(ctx
, graph
) < 0)
1701 if (graph
->n_edge
== 0)
1704 if (detect_sccs(ctx
, graph
) < 0)
1707 if (graph
->n_total_row
>= graph
->max_row
)
1708 isl_die(ctx
, isl_error_internal
,
1709 "too many schedule rows", return -1);
1711 for (i
= 0; i
< graph
->n
; ++i
) {
1712 struct isl_sched_node
*node
= &graph
->node
[i
];
1713 int row
= isl_mat_rows(node
->sched
);
1714 int cols
= isl_mat_cols(node
->sched
);
1716 isl_map_free(node
->sched_map
);
1717 node
->sched_map
= NULL
;
1718 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1721 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1723 for (j
= 1; j
< cols
; ++j
)
1724 node
->sched
= isl_mat_set_element_si(node
->sched
,
1726 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1729 graph
->n_total_row
++;
1735 /* Construct an isl_schedule based on the computed schedule stored
1736 * in graph and with parameters specified by dim.
1738 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1739 __isl_take isl_space
*dim
)
1743 isl_schedule
*sched
= NULL
;
1748 ctx
= isl_space_get_ctx(dim
);
1749 sched
= isl_calloc(ctx
, struct isl_schedule
,
1750 sizeof(struct isl_schedule
) +
1751 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1756 sched
->n
= graph
->n
;
1757 sched
->n_band
= graph
->n_band
;
1758 sched
->n_total_row
= graph
->n_total_row
;
1760 for (i
= 0; i
< sched
->n
; ++i
) {
1762 int *band_end
, *band_id
, *zero
;
1764 sched
->node
[i
].sched
=
1765 node_extract_schedule_multi_aff(&graph
->node
[i
]);
1766 if (!sched
->node
[i
].sched
)
1769 sched
->node
[i
].n_band
= graph
->n_band
;
1770 if (graph
->n_band
== 0)
1773 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1774 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1775 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1776 sched
->node
[i
].band_end
= band_end
;
1777 sched
->node
[i
].band_id
= band_id
;
1778 sched
->node
[i
].zero
= zero
;
1779 if (!band_end
|| !band_id
|| !zero
)
1782 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1783 zero
[r
] = graph
->node
[i
].zero
[r
];
1784 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1785 if (graph
->node
[i
].band
[r
] == b
)
1788 if (graph
->node
[i
].band
[r
] == -1)
1791 if (r
== graph
->n_total_row
)
1793 sched
->node
[i
].n_band
= b
;
1794 for (--b
; b
>= 0; --b
)
1795 band_id
[b
] = graph
->node
[i
].band_id
[b
];
1802 isl_space_free(dim
);
1803 isl_schedule_free(sched
);
1807 /* Copy nodes that satisfy node_pred from the src dependence graph
1808 * to the dst dependence graph.
1810 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
1811 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1816 for (i
= 0; i
< src
->n
; ++i
) {
1817 if (!node_pred(&src
->node
[i
], data
))
1819 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
1820 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
1821 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
1822 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
1823 dst
->node
[dst
->n
].sched_map
=
1824 isl_map_copy(src
->node
[i
].sched_map
);
1825 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
1826 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
1827 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
1834 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1835 * to the dst dependence graph.
1836 * If the source or destination node of the edge is not in the destination
1837 * graph, then it must be a backward proximity edge and it should simply
1840 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
1841 struct isl_sched_graph
*src
,
1842 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
1845 enum isl_edge_type t
;
1848 for (i
= 0; i
< src
->n_edge
; ++i
) {
1849 struct isl_sched_edge
*edge
= &src
->edge
[i
];
1851 struct isl_sched_node
*dst_src
, *dst_dst
;
1853 if (!edge_pred(edge
, data
))
1856 if (isl_map_plain_is_empty(edge
->map
))
1859 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
1860 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
1861 if (!dst_src
|| !dst_dst
) {
1863 isl_die(ctx
, isl_error_internal
,
1864 "backward validity edge", return -1);
1868 map
= isl_map_copy(edge
->map
);
1870 dst
->edge
[dst
->n_edge
].src
= dst_src
;
1871 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
1872 dst
->edge
[dst
->n_edge
].map
= map
;
1873 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
1874 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
1877 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
1879 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
1881 if (graph_edge_table_add(ctx
, dst
, t
,
1882 &dst
->edge
[dst
->n_edge
- 1]) < 0)
1890 /* Given a "src" dependence graph that contains the nodes from "dst"
1891 * that satisfy node_pred, copy the schedule computed in "src"
1892 * for those nodes back to "dst".
1894 static int copy_schedule(struct isl_sched_graph
*dst
,
1895 struct isl_sched_graph
*src
,
1896 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1901 for (i
= 0; i
< dst
->n
; ++i
) {
1902 if (!node_pred(&dst
->node
[i
], data
))
1904 isl_mat_free(dst
->node
[i
].sched
);
1905 isl_map_free(dst
->node
[i
].sched_map
);
1906 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
1907 dst
->node
[i
].sched_map
=
1908 isl_map_copy(src
->node
[src
->n
].sched_map
);
1912 dst
->max_row
= src
->max_row
;
1913 dst
->n_total_row
= src
->n_total_row
;
1914 dst
->n_band
= src
->n_band
;
1919 /* Compute the maximal number of variables over all nodes.
1920 * This is the maximal number of linearly independent schedule
1921 * rows that we need to compute.
1922 * Just in case we end up in a part of the dependence graph
1923 * with only lower-dimensional domains, we make sure we will
1924 * compute the required amount of extra linearly independent rows.
1926 static int compute_maxvar(struct isl_sched_graph
*graph
)
1931 for (i
= 0; i
< graph
->n
; ++i
) {
1932 struct isl_sched_node
*node
= &graph
->node
[i
];
1935 if (node_update_cmap(node
) < 0)
1937 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
1938 if (nvar
> graph
->maxvar
)
1939 graph
->maxvar
= nvar
;
1945 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1946 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1948 /* Compute a schedule for a subgraph of "graph". In particular, for
1949 * the graph composed of nodes that satisfy node_pred and edges that
1950 * that satisfy edge_pred. The caller should precompute the number
1951 * of nodes and edges that satisfy these predicates and pass them along
1952 * as "n" and "n_edge".
1953 * If the subgraph is known to consist of a single component, then wcc should
1954 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1955 * Otherwise, we call compute_schedule, which will check whether the subgraph
1958 static int compute_sub_schedule(isl_ctx
*ctx
,
1959 struct isl_sched_graph
*graph
, int n
, int n_edge
,
1960 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
1961 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
1964 struct isl_sched_graph split
= { 0 };
1967 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
1969 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
1971 if (graph_init_table(ctx
, &split
) < 0)
1973 for (t
= 0; t
<= isl_edge_last
; ++t
)
1974 split
.max_edge
[t
] = graph
->max_edge
[t
];
1975 if (graph_init_edge_tables(ctx
, &split
) < 0)
1977 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
1979 split
.n_row
= graph
->n_row
;
1980 split
.max_row
= graph
->max_row
;
1981 split
.n_total_row
= graph
->n_total_row
;
1982 split
.n_band
= graph
->n_band
;
1983 split
.band_start
= graph
->band_start
;
1985 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
1987 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
1990 copy_schedule(graph
, &split
, node_pred
, data
);
1992 graph_free(ctx
, &split
);
1995 graph_free(ctx
, &split
);
1999 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2001 return node
->scc
== scc
;
2004 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2006 return node
->scc
<= scc
;
2009 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2011 return node
->scc
>= scc
;
2014 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2016 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2019 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2021 return edge
->dst
->scc
<= scc
;
2024 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2026 return edge
->src
->scc
>= scc
;
2029 /* Pad the schedules of all nodes with zero rows such that in the end
2030 * they all have graph->n_total_row rows.
2031 * The extra rows don't belong to any band, so they get assigned band number -1.
2033 static int pad_schedule(struct isl_sched_graph
*graph
)
2037 for (i
= 0; i
< graph
->n
; ++i
) {
2038 struct isl_sched_node
*node
= &graph
->node
[i
];
2039 int row
= isl_mat_rows(node
->sched
);
2040 if (graph
->n_total_row
> row
) {
2041 isl_map_free(node
->sched_map
);
2042 node
->sched_map
= NULL
;
2044 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2045 graph
->n_total_row
- row
);
2048 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2055 /* Split the current graph into two parts and compute a schedule for each
2056 * part individually. In particular, one part consists of all SCCs up
2057 * to and including graph->src_scc, while the other part contains the other
2060 * The split is enforced in the schedule by constant rows with two different
2061 * values (0 and 1). These constant rows replace the previously computed rows
2062 * in the current band.
2063 * It would be possible to reuse them as the first rows in the next
2064 * band, but recomputing them may result in better rows as we are looking
2065 * at a smaller part of the dependence graph.
2066 * compute_split_schedule is only called when no zero-distance schedule row
2067 * could be found on the entire graph, so we wark the splitting row as
2068 * non zero-distance.
2070 * The band_id of the second group is set to n, where n is the number
2071 * of nodes in the first group. This ensures that the band_ids over
2072 * the two groups remain disjoint, even if either or both of the two
2073 * groups contain independent components.
2075 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2077 int i
, j
, n
, e1
, e2
;
2078 int n_total_row
, orig_total_row
;
2079 int n_band
, orig_band
;
2082 if (graph
->n_total_row
>= graph
->max_row
)
2083 isl_die(ctx
, isl_error_internal
,
2084 "too many schedule rows", return -1);
2086 drop
= graph
->n_total_row
- graph
->band_start
;
2087 graph
->n_total_row
-= drop
;
2088 graph
->n_row
-= drop
;
2091 for (i
= 0; i
< graph
->n
; ++i
) {
2092 struct isl_sched_node
*node
= &graph
->node
[i
];
2093 int row
= isl_mat_rows(node
->sched
) - drop
;
2094 int cols
= isl_mat_cols(node
->sched
);
2095 int before
= node
->scc
<= graph
->src_scc
;
2100 isl_map_free(node
->sched_map
);
2101 node
->sched_map
= NULL
;
2102 node
->sched
= isl_mat_drop_rows(node
->sched
,
2103 graph
->band_start
, drop
);
2104 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2107 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2109 for (j
= 1; j
< cols
; ++j
)
2110 node
->sched
= isl_mat_set_element_si(node
->sched
,
2112 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2113 node
->zero
[graph
->n_total_row
] = 0;
2117 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2118 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2120 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2124 graph
->n_total_row
++;
2127 for (i
= 0; i
< graph
->n
; ++i
) {
2128 struct isl_sched_node
*node
= &graph
->node
[i
];
2129 if (node
->scc
> graph
->src_scc
)
2130 node
->band_id
[graph
->n_band
] = n
;
2133 orig_total_row
= graph
->n_total_row
;
2134 orig_band
= graph
->n_band
;
2135 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2136 &node_scc_at_most
, &edge_dst_scc_at_most
,
2137 graph
->src_scc
, 0) < 0)
2139 n_total_row
= graph
->n_total_row
;
2140 graph
->n_total_row
= orig_total_row
;
2141 n_band
= graph
->n_band
;
2142 graph
->n_band
= orig_band
;
2143 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2144 &node_scc_at_least
, &edge_src_scc_at_least
,
2145 graph
->src_scc
+ 1, 0) < 0)
2147 if (n_total_row
> graph
->n_total_row
)
2148 graph
->n_total_row
= n_total_row
;
2149 if (n_band
> graph
->n_band
)
2150 graph
->n_band
= n_band
;
2152 return pad_schedule(graph
);
2155 /* Compute the next band of the schedule after updating the dependence
2156 * relations based on the the current schedule.
2158 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2160 if (update_edges(ctx
, graph
) < 0)
2164 return compute_schedule(ctx
, graph
);
2167 /* Add constraints to graph->lp that force the dependence "map" (which
2168 * is part of the dependence relation of "edge")
2169 * to be respected and attempt to carry it, where the edge is one from
2170 * a node j to itself. "pos" is the sequence number of the given map.
2171 * That is, add constraints that enforce
2173 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2174 * = c_j_x (y - x) >= e_i
2176 * for each (x,y) in R.
2177 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2178 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2179 * with each coefficient in c_j_x represented as a pair of non-negative
2182 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2183 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2186 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2188 isl_dim_map
*dim_map
;
2189 isl_basic_set
*coef
;
2190 struct isl_sched_node
*node
= edge
->src
;
2192 coef
= intra_coefficients(graph
, map
);
2196 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2198 total
= isl_basic_set_total_dim(graph
->lp
);
2199 dim_map
= isl_dim_map_alloc(ctx
, total
);
2200 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2201 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2202 isl_space_dim(dim
, isl_dim_set
), 1,
2204 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2205 isl_space_dim(dim
, isl_dim_set
), 1,
2207 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2208 coef
->n_eq
, coef
->n_ineq
);
2209 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2211 isl_space_free(dim
);
2216 /* Add constraints to graph->lp that force the dependence "map" (which
2217 * is part of the dependence relation of "edge")
2218 * to be respected and attempt to carry it, where the edge is one from
2219 * node j to node k. "pos" is the sequence number of the given map.
2220 * That is, add constraints that enforce
2222 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2224 * for each (x,y) in R.
2225 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2226 * of valid constraints for R and then plug in
2227 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2228 * with each coefficient (except e_i, c_k_0 and c_j_0)
2229 * represented as a pair of non-negative coefficients.
2231 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2232 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2235 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2237 isl_dim_map
*dim_map
;
2238 isl_basic_set
*coef
;
2239 struct isl_sched_node
*src
= edge
->src
;
2240 struct isl_sched_node
*dst
= edge
->dst
;
2242 coef
= inter_coefficients(graph
, map
);
2246 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2248 total
= isl_basic_set_total_dim(graph
->lp
);
2249 dim_map
= isl_dim_map_alloc(ctx
, total
);
2251 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2253 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2254 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2255 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2256 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2257 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2259 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2260 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2263 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2264 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2265 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2266 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2267 isl_space_dim(dim
, isl_dim_set
), 1,
2269 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2270 isl_space_dim(dim
, isl_dim_set
), 1,
2273 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2274 coef
->n_eq
, coef
->n_ineq
);
2275 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2277 isl_space_free(dim
);
2282 /* Add constraints to graph->lp that force all validity dependences
2283 * to be respected and attempt to carry them.
2285 static int add_all_constraints(struct isl_sched_graph
*graph
)
2291 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2292 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2294 if (!edge
->validity
)
2297 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2298 isl_basic_map
*bmap
;
2301 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2302 map
= isl_map_from_basic_map(bmap
);
2304 if (edge
->src
== edge
->dst
&&
2305 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2307 if (edge
->src
!= edge
->dst
&&
2308 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2317 /* Count the number of equality and inequality constraints
2318 * that will be added to the carry_lp problem.
2319 * We count each edge exactly once.
2321 static int count_all_constraints(struct isl_sched_graph
*graph
,
2322 int *n_eq
, int *n_ineq
)
2326 *n_eq
= *n_ineq
= 0;
2327 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2328 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2329 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2330 isl_basic_map
*bmap
;
2333 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2334 map
= isl_map_from_basic_map(bmap
);
2336 if (count_map_constraints(graph
, edge
, map
,
2337 n_eq
, n_ineq
, 1) < 0)
2345 /* Construct an LP problem for finding schedule coefficients
2346 * such that the schedule carries as many dependences as possible.
2347 * In particular, for each dependence i, we bound the dependence distance
2348 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2349 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2350 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2351 * Note that if the dependence relation is a union of basic maps,
2352 * then we have to consider each basic map individually as it may only
2353 * be possible to carry the dependences expressed by some of those
2354 * basic maps and not all off them.
2355 * Below, we consider each of those basic maps as a separate "edge".
2357 * All variables of the LP are non-negative. The actual coefficients
2358 * may be negative, so each coefficient is represented as the difference
2359 * of two non-negative variables. The negative part always appears
2360 * immediately before the positive part.
2361 * Other than that, the variables have the following order
2363 * - sum of (1 - e_i) over all edges
2364 * - sum of positive and negative parts of all c_n coefficients
2365 * (unconstrained when computing non-parametric schedules)
2366 * - sum of positive and negative parts of all c_x coefficients
2371 * - positive and negative parts of c_i_n (if parametric)
2372 * - positive and negative parts of c_i_x
2374 * The constraints are those from the (validity) edges plus three equalities
2375 * to express the sums and n_edge inequalities to express e_i <= 1.
2377 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2387 for (i
= 0; i
< graph
->n_edge
; ++i
)
2388 n_edge
+= graph
->edge
[i
].map
->n
;
2391 for (i
= 0; i
< graph
->n
; ++i
) {
2392 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2393 node
->start
= total
;
2394 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2397 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2400 dim
= isl_space_set_alloc(ctx
, 0, total
);
2401 isl_basic_set_free(graph
->lp
);
2404 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2405 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2407 k
= isl_basic_set_alloc_equality(graph
->lp
);
2410 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2411 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2412 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2413 for (i
= 0; i
< n_edge
; ++i
)
2414 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2416 k
= isl_basic_set_alloc_equality(graph
->lp
);
2419 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2420 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2421 for (i
= 0; i
< graph
->n
; ++i
) {
2422 int pos
= 1 + graph
->node
[i
].start
+ 1;
2424 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2425 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
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
][3], -1);
2433 for (i
= 0; i
< graph
->n
; ++i
) {
2434 struct isl_sched_node
*node
= &graph
->node
[i
];
2435 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2437 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2438 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2441 for (i
= 0; i
< n_edge
; ++i
) {
2442 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2445 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2446 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2447 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2450 if (add_all_constraints(graph
) < 0)
2456 /* If the schedule_split_scaled option is set and if the linear
2457 * parts of the scheduling rows for all nodes in the graphs have
2458 * non-trivial common divisor, then split off the constant term
2459 * from the linear part.
2460 * The constant term is then placed in a separate band and
2461 * the linear part is reduced.
2463 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2469 if (!ctx
->opt
->schedule_split_scaled
)
2474 if (graph
->n_total_row
>= graph
->max_row
)
2475 isl_die(ctx
, isl_error_internal
,
2476 "too many schedule rows", return -1);
2479 isl_int_init(gcd_i
);
2481 isl_int_set_si(gcd
, 0);
2483 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2485 for (i
= 0; i
< graph
->n
; ++i
) {
2486 struct isl_sched_node
*node
= &graph
->node
[i
];
2487 int cols
= isl_mat_cols(node
->sched
);
2489 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2490 isl_int_gcd(gcd
, gcd
, gcd_i
);
2493 isl_int_clear(gcd_i
);
2495 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2502 for (i
= 0; i
< graph
->n
; ++i
) {
2503 struct isl_sched_node
*node
= &graph
->node
[i
];
2505 isl_map_free(node
->sched_map
);
2506 node
->sched_map
= NULL
;
2507 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2510 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2511 node
->sched
->row
[row
][0], gcd
);
2512 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2513 node
->sched
->row
[row
][0], gcd
);
2514 isl_int_mul(node
->sched
->row
[row
][0],
2515 node
->sched
->row
[row
][0], gcd
);
2516 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2519 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2522 graph
->n_total_row
++;
2531 static int compute_component_schedule(isl_ctx
*ctx
,
2532 struct isl_sched_graph
*graph
);
2534 /* Is the schedule row "sol" trivial on node "node"?
2535 * That is, is the solution zero on the dimensions orthogonal to
2536 * the previously found solutions?
2537 * Each coefficient is represented as the difference between
2538 * two non-negative values in "sol". The coefficient is then
2539 * zero if those two values are equal to each other.
2541 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
2547 pos
= 1 + node
->start
+ 1 + 2 * (node
->nparam
+ node
->rank
);
2548 len
= 2 * (node
->nvar
- node
->rank
);
2553 for (i
= 0; i
< len
; i
+= 2)
2554 if (isl_int_ne(sol
->el
[pos
+ i
], sol
->el
[pos
+ i
+ 1]))
2560 /* Is the schedule row "sol" trivial on any node where it should
2563 static int is_any_trivial(struct isl_sched_graph
*graph
,
2564 __isl_keep isl_vec
*sol
)
2568 for (i
= 0; i
< graph
->n
; ++i
) {
2569 struct isl_sched_node
*node
= &graph
->node
[i
];
2571 if (!needs_row(graph
, node
))
2573 if (is_trivial(node
, sol
))
2580 /* Construct a schedule row for each node such that as many dependences
2581 * as possible are carried and then continue with the next band.
2583 * If the computed schedule row turns out to be trivial on one or
2584 * more nodes where it should not be trivial, then we throw it away
2585 * and try again on each component separately.
2587 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2595 for (i
= 0; i
< graph
->n_edge
; ++i
)
2596 n_edge
+= graph
->edge
[i
].map
->n
;
2598 if (setup_carry_lp(ctx
, graph
) < 0)
2601 lp
= isl_basic_set_copy(graph
->lp
);
2602 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2606 if (sol
->size
== 0) {
2608 isl_die(ctx
, isl_error_internal
,
2609 "error in schedule construction", return -1);
2612 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2614 isl_die(ctx
, isl_error_unknown
,
2615 "unable to carry dependences", return -1);
2618 if (is_any_trivial(graph
, sol
)) {
2621 return compute_component_schedule(ctx
, graph
);
2622 isl_die(ctx
, isl_error_unknown
,
2623 "unable to construct non-trivial solution", return -1);
2626 if (update_schedule(graph
, sol
, 0, 0) < 0)
2629 if (split_scaled(ctx
, graph
) < 0)
2632 return compute_next_band(ctx
, graph
);
2635 /* Are there any (non-empty) validity edges in the graph?
2637 static int has_validity_edges(struct isl_sched_graph
*graph
)
2641 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2644 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
2649 if (graph
->edge
[i
].validity
)
2656 /* Should we apply a Feautrier step?
2657 * That is, did the user request the Feautrier algorithm and are
2658 * there any validity dependences (left)?
2660 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2662 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2665 return has_validity_edges(graph
);
2668 /* Compute a schedule for a connected dependence graph using Feautrier's
2669 * multi-dimensional scheduling algorithm.
2670 * The original algorithm is described in [1].
2671 * The main idea is to minimize the number of scheduling dimensions, by
2672 * trying to satisfy as many dependences as possible per scheduling dimension.
2674 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2675 * Problem, Part II: Multi-Dimensional Time.
2676 * In Intl. Journal of Parallel Programming, 1992.
2678 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2679 struct isl_sched_graph
*graph
)
2681 return carry_dependences(ctx
, graph
);
2684 /* Compute a schedule for a connected dependence graph.
2685 * We try to find a sequence of as many schedule rows as possible that result
2686 * in non-negative dependence distances (independent of the previous rows
2687 * in the sequence, i.e., such that the sequence is tilable).
2688 * If we can't find any more rows we either
2689 * - split between SCCs and start over (assuming we found an interesting
2690 * pair of SCCs between which to split)
2691 * - continue with the next band (assuming the current band has at least
2693 * - try to carry as many dependences as possible and continue with the next
2696 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2697 * as many validity dependences as possible. When all validity dependences
2698 * are satisfied we extend the schedule to a full-dimensional schedule.
2700 * If we manage to complete the schedule, we finish off by topologically
2701 * sorting the statements based on the remaining dependences.
2703 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2704 * outermost dimension in the current band to be zero distance. If this
2705 * turns out to be impossible, we fall back on the general scheme above
2706 * and try to carry as many dependences as possible.
2708 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2712 if (detect_sccs(ctx
, graph
) < 0)
2714 if (sort_sccs(graph
) < 0)
2717 if (compute_maxvar(graph
) < 0)
2720 if (need_feautrier_step(ctx
, graph
))
2721 return compute_schedule_wcc_feautrier(ctx
, graph
);
2723 if (ctx
->opt
->schedule_outer_zero_distance
)
2726 while (graph
->n_row
< graph
->maxvar
) {
2729 graph
->src_scc
= -1;
2730 graph
->dst_scc
= -1;
2732 if (setup_lp(ctx
, graph
, force_zero
) < 0)
2734 sol
= solve_lp(graph
);
2737 if (sol
->size
== 0) {
2739 if (!ctx
->opt
->schedule_maximize_band_depth
&&
2740 graph
->n_total_row
> graph
->band_start
)
2741 return compute_next_band(ctx
, graph
);
2742 if (graph
->src_scc
>= 0)
2743 return compute_split_schedule(ctx
, graph
);
2744 if (graph
->n_total_row
> graph
->band_start
)
2745 return compute_next_band(ctx
, graph
);
2746 return carry_dependences(ctx
, graph
);
2748 if (update_schedule(graph
, sol
, 1, 1) < 0)
2753 if (graph
->n_total_row
> graph
->band_start
)
2755 return sort_statements(ctx
, graph
);
2758 /* Add a row to the schedules that separates the SCCs and move
2761 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2765 if (graph
->n_total_row
>= graph
->max_row
)
2766 isl_die(ctx
, isl_error_internal
,
2767 "too many schedule rows", return -1);
2769 for (i
= 0; i
< graph
->n
; ++i
) {
2770 struct isl_sched_node
*node
= &graph
->node
[i
];
2771 int row
= isl_mat_rows(node
->sched
);
2773 isl_map_free(node
->sched_map
);
2774 node
->sched_map
= NULL
;
2775 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2776 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2780 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2783 graph
->n_total_row
++;
2789 /* Compute a schedule for each component (identified by node->scc)
2790 * of the dependence graph separately and then combine the results.
2791 * Depending on the setting of schedule_fuse, a component may be
2792 * either weakly or strongly connected.
2794 * The band_id is adjusted such that each component has a separate id.
2795 * Note that the band_id may have already been set to a value different
2796 * from zero by compute_split_schedule.
2798 static int compute_component_schedule(isl_ctx
*ctx
,
2799 struct isl_sched_graph
*graph
)
2803 int n_total_row
, orig_total_row
;
2804 int n_band
, orig_band
;
2806 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
2807 ctx
->opt
->schedule_separate_components
)
2808 if (split_on_scc(ctx
, graph
) < 0)
2812 orig_total_row
= graph
->n_total_row
;
2814 orig_band
= graph
->n_band
;
2815 for (i
= 0; i
< graph
->n
; ++i
)
2816 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
2817 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
2819 for (i
= 0; i
< graph
->n
; ++i
)
2820 if (graph
->node
[i
].scc
== wcc
)
2823 for (i
= 0; i
< graph
->n_edge
; ++i
)
2824 if (graph
->edge
[i
].src
->scc
== wcc
&&
2825 graph
->edge
[i
].dst
->scc
== wcc
)
2828 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
2830 &edge_scc_exactly
, wcc
, 1) < 0)
2832 if (graph
->n_total_row
> n_total_row
)
2833 n_total_row
= graph
->n_total_row
;
2834 graph
->n_total_row
= orig_total_row
;
2835 if (graph
->n_band
> n_band
)
2836 n_band
= graph
->n_band
;
2837 graph
->n_band
= orig_band
;
2840 graph
->n_total_row
= n_total_row
;
2841 graph
->n_band
= n_band
;
2843 return pad_schedule(graph
);
2846 /* Compute a schedule for the given dependence graph.
2847 * We first check if the graph is connected (through validity dependences)
2848 * and, if not, compute a schedule for each component separately.
2849 * If schedule_fuse is set to minimal fusion, then we check for strongly
2850 * connected components instead and compute a separate schedule for
2851 * each such strongly connected component.
2853 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2855 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
2856 if (detect_sccs(ctx
, graph
) < 0)
2859 if (detect_wccs(ctx
, graph
) < 0)
2864 return compute_component_schedule(ctx
, graph
);
2866 return compute_schedule_wcc(ctx
, graph
);
2869 /* Compute a schedule for the given union of domains that respects
2870 * all the validity dependences.
2871 * If the default isl scheduling algorithm is used, it tries to minimize
2872 * the dependence distances over the proximity dependences.
2873 * If Feautrier's scheduling algorithm is used, the proximity dependence
2874 * distances are only minimized during the extension to a full-dimensional
2877 __isl_give isl_schedule
*isl_union_set_compute_schedule(
2878 __isl_take isl_union_set
*domain
,
2879 __isl_take isl_union_map
*validity
,
2880 __isl_take isl_union_map
*proximity
)
2882 isl_ctx
*ctx
= isl_union_set_get_ctx(domain
);
2884 struct isl_sched_graph graph
= { 0 };
2885 isl_schedule
*sched
;
2886 struct isl_extract_edge_data data
;
2888 domain
= isl_union_set_align_params(domain
,
2889 isl_union_map_get_space(validity
));
2890 domain
= isl_union_set_align_params(domain
,
2891 isl_union_map_get_space(proximity
));
2892 dim
= isl_union_set_get_space(domain
);
2893 validity
= isl_union_map_align_params(validity
, isl_space_copy(dim
));
2894 proximity
= isl_union_map_align_params(proximity
, dim
);
2899 graph
.n
= isl_union_set_n_set(domain
);
2902 if (graph_alloc(ctx
, &graph
, graph
.n
,
2903 isl_union_map_n_map(validity
) + isl_union_map_n_map(proximity
)) < 0)
2905 if (compute_max_row(&graph
, domain
) < 0)
2909 if (isl_union_set_foreach_set(domain
, &extract_node
, &graph
) < 0)
2911 if (graph_init_table(ctx
, &graph
) < 0)
2913 graph
.max_edge
[isl_edge_validity
] = isl_union_map_n_map(validity
);
2914 graph
.max_edge
[isl_edge_proximity
] = isl_union_map_n_map(proximity
);
2915 if (graph_init_edge_tables(ctx
, &graph
) < 0)
2918 data
.graph
= &graph
;
2919 data
.type
= isl_edge_validity
;
2920 if (isl_union_map_foreach_map(validity
, &extract_edge
, &data
) < 0)
2922 data
.type
= isl_edge_proximity
;
2923 if (isl_union_map_foreach_map(proximity
, &extract_edge
, &data
) < 0)
2926 if (compute_schedule(ctx
, &graph
) < 0)
2930 sched
= extract_schedule(&graph
, isl_union_set_get_space(domain
));
2932 graph_free(ctx
, &graph
);
2933 isl_union_set_free(domain
);
2934 isl_union_map_free(validity
);
2935 isl_union_map_free(proximity
);
2939 graph_free(ctx
, &graph
);
2940 isl_union_set_free(domain
);
2941 isl_union_map_free(validity
);
2942 isl_union_map_free(proximity
);
2946 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
2952 if (--sched
->ref
> 0)
2955 for (i
= 0; i
< sched
->n
; ++i
) {
2956 isl_multi_aff_free(sched
->node
[i
].sched
);
2957 free(sched
->node
[i
].band_end
);
2958 free(sched
->node
[i
].band_id
);
2959 free(sched
->node
[i
].zero
);
2961 isl_space_free(sched
->dim
);
2962 isl_band_list_free(sched
->band_forest
);
2967 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
2969 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
2972 /* Return an isl_union_map of the schedule. If we have already constructed
2973 * a band forest, then this band forest may have been modified so we need
2974 * to extract the isl_union_map from the forest rather than from
2975 * the originally computed schedule.
2977 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
2980 isl_union_map
*umap
;
2985 if (sched
->band_forest
)
2986 return isl_band_list_get_suffix_schedule(sched
->band_forest
);
2988 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
2989 for (i
= 0; i
< sched
->n
; ++i
) {
2992 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
2993 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
2999 static __isl_give isl_band_list
*construct_band_list(
3000 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3001 int band_nr
, int *parent_active
, int n_active
);
3003 /* Construct an isl_band structure for the band in the given schedule
3004 * with sequence number band_nr for the n_active nodes marked by active.
3005 * If the nodes don't have a band with the given sequence number,
3006 * then a band without members is created.
3008 * Because of the way the schedule is constructed, we know that
3009 * the position of the band inside the schedule of a node is the same
3010 * for all active nodes.
3012 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
3013 __isl_keep isl_band
*parent
,
3014 int band_nr
, int *active
, int n_active
)
3017 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3019 unsigned start
, end
;
3021 band
= isl_band_alloc(ctx
);
3025 band
->schedule
= schedule
;
3026 band
->parent
= parent
;
3028 for (i
= 0; i
< schedule
->n
; ++i
)
3029 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
3032 if (i
< schedule
->n
) {
3033 band
->children
= construct_band_list(schedule
, band
,
3034 band_nr
+ 1, active
, n_active
);
3035 if (!band
->children
)
3039 for (i
= 0; i
< schedule
->n
; ++i
)
3043 if (i
>= schedule
->n
)
3044 isl_die(ctx
, isl_error_internal
,
3045 "band without active statements", goto error
);
3047 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
3048 end
= band_nr
< schedule
->node
[i
].n_band
?
3049 schedule
->node
[i
].band_end
[band_nr
] : start
;
3050 band
->n
= end
- start
;
3052 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
3056 for (j
= 0; j
< band
->n
; ++j
)
3057 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
3059 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
3060 for (i
= 0; i
< schedule
->n
; ++i
) {
3062 isl_pw_multi_aff
*pma
;
3068 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
3069 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3070 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
3071 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
3072 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3073 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
3081 isl_band_free(band
);
3085 /* Construct a list of bands that start at the same position (with
3086 * sequence number band_nr) in the schedules of the nodes that
3087 * were active in the parent band.
3089 * A separate isl_band structure is created for each band_id
3090 * and for each node that does not have a band with sequence
3091 * number band_nr. In the latter case, a band without members
3093 * This ensures that if a band has any children, then each node
3094 * that was active in the band is active in exactly one of the children.
3096 static __isl_give isl_band_list
*construct_band_list(
3097 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3098 int band_nr
, int *parent_active
, int n_active
)
3101 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3104 isl_band_list
*list
;
3107 for (i
= 0; i
< n_active
; ++i
) {
3108 for (j
= 0; j
< schedule
->n
; ++j
) {
3109 if (!parent_active
[j
])
3111 if (schedule
->node
[j
].n_band
<= band_nr
)
3113 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
3119 for (j
= 0; j
< schedule
->n
; ++j
)
3120 if (schedule
->node
[j
].n_band
<= band_nr
)
3125 list
= isl_band_list_alloc(ctx
, n_band
);
3126 band
= construct_band(schedule
, parent
, band_nr
,
3127 parent_active
, n_active
);
3128 return isl_band_list_add(list
, band
);
3131 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3135 list
= isl_band_list_alloc(ctx
, n_band
);
3137 for (i
= 0; i
< n_active
; ++i
) {
3141 for (j
= 0; j
< schedule
->n
; ++j
) {
3142 active
[j
] = parent_active
[j
] &&
3143 schedule
->node
[j
].n_band
> band_nr
&&
3144 schedule
->node
[j
].band_id
[band_nr
] == i
;
3151 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
3153 list
= isl_band_list_add(list
, band
);
3155 for (i
= 0; i
< schedule
->n
; ++i
) {
3157 if (!parent_active
[i
])
3159 if (schedule
->node
[i
].n_band
> band_nr
)
3161 for (j
= 0; j
< schedule
->n
; ++j
)
3163 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
3164 list
= isl_band_list_add(list
, band
);
3172 /* Construct a band forest representation of the schedule and
3173 * return the list of roots.
3175 static __isl_give isl_band_list
*construct_forest(
3176 __isl_keep isl_schedule
*schedule
)
3179 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3180 isl_band_list
*forest
;
3183 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3187 for (i
= 0; i
< schedule
->n
; ++i
)
3190 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
3197 /* Return the roots of a band forest representation of the schedule.
3199 __isl_give isl_band_list
*isl_schedule_get_band_forest(
3200 __isl_keep isl_schedule
*schedule
)
3204 if (!schedule
->band_forest
)
3205 schedule
->band_forest
= construct_forest(schedule
);
3206 return isl_band_list_dup(schedule
->band_forest
);
3209 /* Call "fn" on each band in the schedule in depth-first post-order.
3211 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
3212 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
3215 isl_band_list
*forest
;
3220 forest
= isl_schedule_get_band_forest(sched
);
3221 r
= isl_band_list_foreach_band(forest
, fn
, user
);
3222 isl_band_list_free(forest
);
3227 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3228 __isl_keep isl_band_list
*list
);
3230 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
3231 __isl_keep isl_band
*band
)
3233 isl_band_list
*children
;
3235 p
= isl_printer_start_line(p
);
3236 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
3237 p
= isl_printer_end_line(p
);
3239 if (!isl_band_has_children(band
))
3242 children
= isl_band_get_children(band
);
3244 p
= isl_printer_indent(p
, 4);
3245 p
= print_band_list(p
, children
);
3246 p
= isl_printer_indent(p
, -4);
3248 isl_band_list_free(children
);
3253 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3254 __isl_keep isl_band_list
*list
)
3258 n
= isl_band_list_n_band(list
);
3259 for (i
= 0; i
< n
; ++i
) {
3261 band
= isl_band_list_get_band(list
, i
);
3262 p
= print_band(p
, band
);
3263 isl_band_free(band
);
3269 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
3270 __isl_keep isl_schedule
*schedule
)
3272 isl_band_list
*forest
;
3274 forest
= isl_schedule_get_band_forest(schedule
);
3276 p
= print_band_list(p
, forest
);
3278 isl_band_list_free(forest
);
3283 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
3285 isl_printer
*printer
;
3290 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
3291 printer
= isl_printer_print_schedule(printer
, schedule
);
3293 isl_printer_free(printer
);