2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 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>
15 #include <isl/constraint.h>
16 #include <isl/schedule.h>
17 #include <isl_mat_private.h>
21 #include <isl_dim_map.h>
22 #include <isl_hmap_map_basic_set.h>
23 #include <isl_qsort.h>
24 #include <isl_schedule_private.h>
25 #include <isl_band_private.h>
26 #include <isl_list_private.h>
27 #include <isl_options_private.h>
30 * The scheduling algorithm implemented in this file was inspired by
31 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
32 * Parallelization and Locality Optimization in the Polyhedral Model".
36 /* Internal information about a node that is used during the construction
38 * dim represents the space in which the domain lives
39 * sched is a matrix representation of the schedule being constructed
41 * sched_map is an isl_map representation of the same (partial) schedule
42 * sched_map may be NULL
43 * rank is the number of linearly independent rows in the linear part
45 * the columns of cmap represent a change of basis for the schedule
46 * coefficients; the first rank columns span the linear part of
48 * start is the first variable in the LP problem in the sequences that
49 * represents the schedule coefficients of this node
50 * nvar is the dimension of the domain
51 * nparam is the number of parameters or 0 if we are not constructing
52 * a parametric schedule
54 * scc is the index of SCC (or WCC) this node belongs to
56 * band contains the band index for each of the rows of the schedule.
57 * band_id is used to differentiate between separate bands at the same
58 * level within the same parent band, i.e., bands that are separated
59 * by the parent band or bands that are independent of each other.
60 * zero contains a boolean for each of the rows of the schedule,
61 * indicating whether the corresponding scheduling dimension results
62 * in zero dependence distances within its band and with respect
63 * to the proximity edges.
65 * index, min_index and on_stack are used during the SCC detection
66 * index represents the order in which nodes are visited.
67 * min_index is the index of the root of a (sub)component.
68 * on_stack indicates whether the node is currently on the stack.
70 struct isl_sched_node
{
92 static int node_has_dim(const void *entry
, const void *val
)
94 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
95 isl_space
*dim
= (isl_space
*)val
;
97 return isl_space_is_equal(node
->dim
, dim
);
100 /* An edge in the dependence graph. An edge may be used to
101 * ensure validity of the generated schedule, to minimize the dependence
104 * map is the dependence relation
105 * src is the source node
106 * dst is the sink node
107 * validity is set if the edge is used to ensure correctness
108 * proximity is set if the edge is used to minimize dependence distances
110 * For validity edges, start and end mark the sequence of inequality
111 * constraints in the LP problem that encode the validity constraint
112 * corresponding to this edge.
114 struct isl_sched_edge
{
117 struct isl_sched_node
*src
;
118 struct isl_sched_node
*dst
;
128 isl_edge_validity
= 0,
130 isl_edge_last
= isl_edge_proximity
133 /* Internal information about the dependence graph used during
134 * the construction of the schedule.
136 * intra_hmap is a cache, mapping dependence relations to their dual,
137 * for dependences from a node to itself
138 * inter_hmap is a cache, mapping dependence relations to their dual,
139 * for dependences between distinct nodes
141 * n is the number of nodes
142 * node is the list of nodes
143 * maxvar is the maximal number of variables over all nodes
144 * n_row is the current (maximal) number of linearly independent
145 * rows in the node schedules
146 * n_total_row is the current number of rows in the node schedules
147 * n_band is the current number of completed bands
148 * band_start is the starting row in the node schedules of the current band
149 * root is set if this graph is the original dependence graph,
150 * without any splitting
152 * sorted contains a list of node indices sorted according to the
153 * SCC to which a node belongs
155 * n_edge is the number of edges
156 * edge is the list of edges
157 * max_edge contains the maximal number of edges of each type;
158 * in particular, it contains the number of edges in the inital graph.
159 * edge_table contains pointers into the edge array, hashed on the source
160 * and sink spaces; there is one such table for each type;
161 * a given edge may be referenced from more than one table
162 * if the corresponding relation appears in more than of the
163 * sets of dependences
165 * node_table contains pointers into the node array, hashed on the space
167 * region contains a list of variable sequences that should be non-trivial
169 * lp contains the (I)LP problem used to obtain new schedule rows
171 * src_scc and dst_scc are the source and sink SCCs of an edge with
172 * conflicting constraints
174 * scc, sp, index and stack are used during the detection of SCCs
175 * scc is the number of the next SCC
176 * stack contains the nodes on the path from the root to the current node
177 * sp is the stack pointer
178 * index is the index of the last node visited
180 struct isl_sched_graph
{
181 isl_hmap_map_basic_set
*intra_hmap
;
182 isl_hmap_map_basic_set
*inter_hmap
;
184 struct isl_sched_node
*node
;
197 struct isl_sched_edge
*edge
;
199 int max_edge
[isl_edge_last
+ 1];
200 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
202 struct isl_hash_table
*node_table
;
203 struct isl_region
*region
;
217 /* Initialize node_table based on the list of nodes.
219 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
223 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
224 if (!graph
->node_table
)
227 for (i
= 0; i
< graph
->n
; ++i
) {
228 struct isl_hash_table_entry
*entry
;
231 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
232 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
234 graph
->node
[i
].dim
, 1);
237 entry
->data
= &graph
->node
[i
];
243 /* Return a pointer to the node that lives within the given space,
244 * or NULL if there is no such node.
246 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
247 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
249 struct isl_hash_table_entry
*entry
;
252 hash
= isl_space_get_hash(dim
);
253 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
254 &node_has_dim
, dim
, 0);
256 return entry
? entry
->data
: NULL
;
259 static int edge_has_src_and_dst(const void *entry
, const void *val
)
261 const struct isl_sched_edge
*edge
= entry
;
262 const struct isl_sched_edge
*temp
= val
;
264 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
267 /* Add the given edge to graph->edge_table[type].
269 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
270 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
272 struct isl_hash_table_entry
*entry
;
275 hash
= isl_hash_init();
276 hash
= isl_hash_builtin(hash
, edge
->src
);
277 hash
= isl_hash_builtin(hash
, edge
->dst
);
278 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
279 &edge_has_src_and_dst
, edge
, 1);
287 /* Allocate the edge_tables based on the maximal number of edges of
290 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
294 for (i
= 0; i
<= isl_edge_last
; ++i
) {
295 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
297 if (!graph
->edge_table
[i
])
304 /* If graph->edge_table[type] contains an edge from the given source
305 * to the given destination, then return the hash table entry of this edge.
306 * Otherwise, return NULL.
308 static struct isl_hash_table_entry
*graph_find_edge_entry(
309 struct isl_sched_graph
*graph
,
310 enum isl_edge_type type
,
311 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
313 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
315 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
317 hash
= isl_hash_init();
318 hash
= isl_hash_builtin(hash
, temp
.src
);
319 hash
= isl_hash_builtin(hash
, temp
.dst
);
320 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
321 &edge_has_src_and_dst
, &temp
, 0);
325 /* If graph->edge_table[type] contains an edge from the given source
326 * to the given destination, then return this edge.
327 * Otherwise, return NULL.
329 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
330 enum isl_edge_type type
,
331 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
333 struct isl_hash_table_entry
*entry
;
335 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
342 /* Check whether the dependence graph has an edge of the give type
343 * between the given two nodes.
345 static int graph_has_edge(struct isl_sched_graph
*graph
,
346 enum isl_edge_type type
,
347 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
349 struct isl_sched_edge
*edge
;
352 edge
= graph_find_edge(graph
, type
, src
, dst
);
356 empty
= isl_map_plain_is_empty(edge
->map
);
363 /* If there is an edge from the given source to the given destination
364 * of any type then return this edge.
365 * Otherwise, return NULL.
367 static struct isl_sched_edge
*graph_find_any_edge(struct isl_sched_graph
*graph
,
368 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
371 struct isl_sched_edge
*edge
;
373 for (i
= 0; i
<= isl_edge_last
; ++i
) {
374 edge
= graph_find_edge(graph
, i
, src
, dst
);
382 /* Remove the given edge from all the edge_tables that refer to it.
384 static void graph_remove_edge(struct isl_sched_graph
*graph
,
385 struct isl_sched_edge
*edge
)
387 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
390 for (i
= 0; i
<= isl_edge_last
; ++i
) {
391 struct isl_hash_table_entry
*entry
;
393 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
396 if (entry
->data
!= edge
)
398 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
402 /* Check whether the dependence graph has any edge
403 * between the given two nodes.
405 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
406 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
411 for (i
= 0; i
<= isl_edge_last
; ++i
) {
412 r
= graph_has_edge(graph
, i
, src
, dst
);
420 /* Check whether the dependence graph has a validity edge
421 * between the given two nodes.
423 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
424 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
426 return graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
429 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
430 int n_node
, int n_edge
)
435 graph
->n_edge
= n_edge
;
436 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
437 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
438 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
439 graph
->stack
= isl_alloc_array(ctx
, int, graph
->n
);
440 graph
->edge
= isl_calloc_array(ctx
,
441 struct isl_sched_edge
, graph
->n_edge
);
443 graph
->intra_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
444 graph
->inter_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
446 if (!graph
->node
|| !graph
->region
|| !graph
->stack
|| !graph
->edge
||
450 for(i
= 0; i
< graph
->n
; ++i
)
451 graph
->sorted
[i
] = i
;
456 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
460 isl_hmap_map_basic_set_free(ctx
, graph
->intra_hmap
);
461 isl_hmap_map_basic_set_free(ctx
, graph
->inter_hmap
);
463 for (i
= 0; i
< graph
->n
; ++i
) {
464 isl_space_free(graph
->node
[i
].dim
);
465 isl_mat_free(graph
->node
[i
].sched
);
466 isl_map_free(graph
->node
[i
].sched_map
);
467 isl_mat_free(graph
->node
[i
].cmap
);
469 free(graph
->node
[i
].band
);
470 free(graph
->node
[i
].band_id
);
471 free(graph
->node
[i
].zero
);
476 for (i
= 0; i
< graph
->n_edge
; ++i
)
477 isl_map_free(graph
->edge
[i
].map
);
481 for (i
= 0; i
<= isl_edge_last
; ++i
)
482 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
483 isl_hash_table_free(ctx
, graph
->node_table
);
484 isl_basic_set_free(graph
->lp
);
487 /* Add a new node to the graph representing the given set.
489 static int extract_node(__isl_take isl_set
*set
, void *user
)
495 struct isl_sched_graph
*graph
= user
;
496 int *band
, *band_id
, *zero
;
498 ctx
= isl_set_get_ctx(set
);
499 dim
= isl_set_get_space(set
);
501 nvar
= isl_space_dim(dim
, isl_dim_set
);
502 nparam
= isl_space_dim(dim
, isl_dim_param
);
503 if (!ctx
->opt
->schedule_parametric
)
505 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
506 graph
->node
[graph
->n
].dim
= dim
;
507 graph
->node
[graph
->n
].nvar
= nvar
;
508 graph
->node
[graph
->n
].nparam
= nparam
;
509 graph
->node
[graph
->n
].sched
= sched
;
510 graph
->node
[graph
->n
].sched_map
= NULL
;
511 band
= isl_alloc_array(ctx
, int, graph
->n_edge
+ nvar
);
512 graph
->node
[graph
->n
].band
= band
;
513 band_id
= isl_calloc_array(ctx
, int, graph
->n_edge
+ nvar
);
514 graph
->node
[graph
->n
].band_id
= band_id
;
515 zero
= isl_calloc_array(ctx
, int, graph
->n_edge
+ nvar
);
516 graph
->node
[graph
->n
].zero
= zero
;
519 if (!sched
|| !band
|| !band_id
|| !zero
)
525 struct isl_extract_edge_data
{
526 enum isl_edge_type type
;
527 struct isl_sched_graph
*graph
;
530 /* Add a new edge to the graph based on the given map
531 * and add it to data->graph->edge_table[data->type].
532 * If a dependence relation of a given type happens to be identical
533 * to one of the dependence relations of a type that was added before,
534 * then we don't create a new edge, but instead mark the original edge
535 * as also representing a dependence of the current type.
537 static int extract_edge(__isl_take isl_map
*map
, void *user
)
539 isl_ctx
*ctx
= isl_map_get_ctx(map
);
540 struct isl_extract_edge_data
*data
= user
;
541 struct isl_sched_graph
*graph
= data
->graph
;
542 struct isl_sched_node
*src
, *dst
;
544 struct isl_sched_edge
*edge
;
547 dim
= isl_space_domain(isl_map_get_space(map
));
548 src
= graph_find_node(ctx
, graph
, dim
);
550 dim
= isl_space_range(isl_map_get_space(map
));
551 dst
= graph_find_node(ctx
, graph
, dim
);
559 graph
->edge
[graph
->n_edge
].src
= src
;
560 graph
->edge
[graph
->n_edge
].dst
= dst
;
561 graph
->edge
[graph
->n_edge
].map
= map
;
562 if (data
->type
== isl_edge_validity
) {
563 graph
->edge
[graph
->n_edge
].validity
= 1;
564 graph
->edge
[graph
->n_edge
].proximity
= 0;
566 if (data
->type
== isl_edge_proximity
) {
567 graph
->edge
[graph
->n_edge
].validity
= 0;
568 graph
->edge
[graph
->n_edge
].proximity
= 1;
572 edge
= graph_find_any_edge(graph
, src
, dst
);
574 return graph_edge_table_add(ctx
, graph
, data
->type
,
575 &graph
->edge
[graph
->n_edge
- 1]);
576 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
580 return graph_edge_table_add(ctx
, graph
, data
->type
,
581 &graph
->edge
[graph
->n_edge
- 1]);
584 edge
->validity
|= graph
->edge
[graph
->n_edge
].validity
;
585 edge
->proximity
|= graph
->edge
[graph
->n_edge
].proximity
;
588 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
591 /* Check whether there is a validity dependence from src to dst,
592 * forcing dst to follow src (if weak is not set).
593 * If weak is set, then check if there is any dependence from src to dst.
595 static int node_follows(struct isl_sched_graph
*graph
,
596 struct isl_sched_node
*dst
, struct isl_sched_node
*src
, int weak
)
599 return graph_has_any_edge(graph
, src
, dst
);
601 return graph_has_validity_edge(graph
, src
, dst
);
604 /* Perform Tarjan's algorithm for computing the strongly connected components
605 * in the dependence graph (only validity edges).
606 * If weak is set, we consider the graph to be undirected and
607 * we effectively compute the (weakly) connected components.
608 * Additionally, we also consider other edges when weak is set.
610 static int detect_sccs_tarjan(struct isl_sched_graph
*g
, int i
, int weak
)
614 g
->node
[i
].index
= g
->index
;
615 g
->node
[i
].min_index
= g
->index
;
616 g
->node
[i
].on_stack
= 1;
618 g
->stack
[g
->sp
++] = i
;
620 for (j
= g
->n
- 1; j
>= 0; --j
) {
625 if (g
->node
[j
].index
>= 0 &&
626 (!g
->node
[j
].on_stack
||
627 g
->node
[j
].index
> g
->node
[i
].min_index
))
630 f
= node_follows(g
, &g
->node
[i
], &g
->node
[j
], weak
);
634 f
= node_follows(g
, &g
->node
[j
], &g
->node
[i
], weak
);
640 if (g
->node
[j
].index
< 0) {
641 detect_sccs_tarjan(g
, j
, weak
);
642 if (g
->node
[j
].min_index
< g
->node
[i
].min_index
)
643 g
->node
[i
].min_index
= g
->node
[j
].min_index
;
644 } else if (g
->node
[j
].index
< g
->node
[i
].min_index
)
645 g
->node
[i
].min_index
= g
->node
[j
].index
;
648 if (g
->node
[i
].index
!= g
->node
[i
].min_index
)
652 j
= g
->stack
[--g
->sp
];
653 g
->node
[j
].on_stack
= 0;
654 g
->node
[j
].scc
= g
->scc
;
661 static int detect_ccs(struct isl_sched_graph
*graph
, int weak
)
668 for (i
= graph
->n
- 1; i
>= 0; --i
)
669 graph
->node
[i
].index
= -1;
671 for (i
= graph
->n
- 1; i
>= 0; --i
) {
672 if (graph
->node
[i
].index
>= 0)
674 if (detect_sccs_tarjan(graph
, i
, weak
) < 0)
681 /* Apply Tarjan's algorithm to detect the strongly connected components
682 * in the dependence graph.
684 static int detect_sccs(struct isl_sched_graph
*graph
)
686 return detect_ccs(graph
, 0);
689 /* Apply Tarjan's algorithm to detect the (weakly) connected components
690 * in the dependence graph.
692 static int detect_wccs(struct isl_sched_graph
*graph
)
694 return detect_ccs(graph
, 1);
697 static int cmp_scc(const void *a
, const void *b
, void *data
)
699 struct isl_sched_graph
*graph
= data
;
703 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
706 /* Sort the elements of graph->sorted according to the corresponding SCCs.
708 static void sort_sccs(struct isl_sched_graph
*graph
)
710 isl_quicksort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
713 /* Given a dependence relation R from a node to itself,
714 * construct the set of coefficients of valid constraints for elements
715 * in that dependence relation.
716 * In particular, the result contains tuples of coefficients
717 * c_0, c_n, c_x such that
719 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
723 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
725 * We choose here to compute the dual of delta R.
726 * Alternatively, we could have computed the dual of R, resulting
727 * in a set of tuples c_0, c_n, c_x, c_y, and then
728 * plugged in (c_0, c_n, c_x, -c_x).
730 static __isl_give isl_basic_set
*intra_coefficients(
731 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
733 isl_ctx
*ctx
= isl_map_get_ctx(map
);
737 if (isl_hmap_map_basic_set_has(ctx
, graph
->intra_hmap
, map
))
738 return isl_hmap_map_basic_set_get(ctx
, graph
->intra_hmap
, map
);
740 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
741 coef
= isl_set_coefficients(delta
);
742 isl_hmap_map_basic_set_set(ctx
, graph
->intra_hmap
, map
,
743 isl_basic_set_copy(coef
));
748 /* Given a dependence relation R, * construct the set of coefficients
749 * of valid constraints for elements in that dependence relation.
750 * In particular, the result contains tuples of coefficients
751 * c_0, c_n, c_x, c_y such that
753 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
756 static __isl_give isl_basic_set
*inter_coefficients(
757 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
759 isl_ctx
*ctx
= isl_map_get_ctx(map
);
763 if (isl_hmap_map_basic_set_has(ctx
, graph
->inter_hmap
, map
))
764 return isl_hmap_map_basic_set_get(ctx
, graph
->inter_hmap
, map
);
766 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
767 coef
= isl_set_coefficients(set
);
768 isl_hmap_map_basic_set_set(ctx
, graph
->inter_hmap
, map
,
769 isl_basic_set_copy(coef
));
774 /* Add constraints to graph->lp that force validity for the given
775 * dependence from a node i to itself.
776 * That is, add constraints that enforce
778 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
779 * = c_i_x (y - x) >= 0
781 * for each (x,y) in R.
782 * We obtain general constraints on coefficients (c_0, c_n, c_x)
783 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
784 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
785 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
787 * Actually, we do not construct constraints for the c_i_x themselves,
788 * but for the coefficients of c_i_x written as a linear combination
789 * of the columns in node->cmap.
791 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
792 struct isl_sched_edge
*edge
)
795 isl_map
*map
= isl_map_copy(edge
->map
);
796 isl_ctx
*ctx
= isl_map_get_ctx(map
);
798 isl_dim_map
*dim_map
;
800 struct isl_sched_node
*node
= edge
->src
;
802 coef
= intra_coefficients(graph
, map
);
804 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
806 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
807 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
809 total
= isl_basic_set_total_dim(graph
->lp
);
810 dim_map
= isl_dim_map_alloc(ctx
, total
);
811 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
812 isl_space_dim(dim
, isl_dim_set
), 1,
814 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
815 isl_space_dim(dim
, isl_dim_set
), 1,
817 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
818 coef
->n_eq
, coef
->n_ineq
);
819 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
826 /* Add constraints to graph->lp that force validity for the given
827 * dependence from node i to node j.
828 * That is, add constraints that enforce
830 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
832 * for each (x,y) in R.
833 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
834 * of valid constraints for R and then plug in
835 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
836 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
837 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
838 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
840 * Actually, we do not construct constraints for the c_*_x themselves,
841 * but for the coefficients of c_*_x written as a linear combination
842 * of the columns in node->cmap.
844 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
845 struct isl_sched_edge
*edge
)
848 isl_map
*map
= isl_map_copy(edge
->map
);
849 isl_ctx
*ctx
= isl_map_get_ctx(map
);
851 isl_dim_map
*dim_map
;
853 struct isl_sched_node
*src
= edge
->src
;
854 struct isl_sched_node
*dst
= edge
->dst
;
856 coef
= inter_coefficients(graph
, map
);
858 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
860 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
861 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
862 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
863 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
864 isl_mat_copy(dst
->cmap
));
866 total
= isl_basic_set_total_dim(graph
->lp
);
867 dim_map
= isl_dim_map_alloc(ctx
, total
);
869 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
870 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
871 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
872 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
873 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
875 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
876 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
879 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
880 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
881 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
882 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
883 isl_space_dim(dim
, isl_dim_set
), 1,
885 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
886 isl_space_dim(dim
, isl_dim_set
), 1,
889 edge
->start
= graph
->lp
->n_ineq
;
890 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
891 coef
->n_eq
, coef
->n_ineq
);
892 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
895 edge
->end
= graph
->lp
->n_ineq
;
900 /* Add constraints to graph->lp that bound the dependence distance for the given
901 * dependence from a node i to itself.
902 * If s = 1, we add the constraint
904 * c_i_x (y - x) <= m_0 + m_n n
908 * -c_i_x (y - x) + m_0 + m_n n >= 0
910 * for each (x,y) in R.
911 * If s = -1, we add the constraint
913 * -c_i_x (y - x) <= m_0 + m_n n
917 * c_i_x (y - x) + m_0 + m_n n >= 0
919 * for each (x,y) in R.
920 * We obtain general constraints on coefficients (c_0, c_n, c_x)
921 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
922 * with each coefficient (except m_0) represented as a pair of non-negative
925 * Actually, we do not construct constraints for the c_i_x themselves,
926 * but for the coefficients of c_i_x written as a linear combination
927 * of the columns in node->cmap.
929 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
930 struct isl_sched_edge
*edge
, int s
)
934 isl_map
*map
= isl_map_copy(edge
->map
);
935 isl_ctx
*ctx
= isl_map_get_ctx(map
);
937 isl_dim_map
*dim_map
;
939 struct isl_sched_node
*node
= edge
->src
;
941 coef
= intra_coefficients(graph
, map
);
943 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
945 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
946 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
948 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
949 total
= isl_basic_set_total_dim(graph
->lp
);
950 dim_map
= isl_dim_map_alloc(ctx
, total
);
951 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
952 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
953 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
954 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
955 isl_space_dim(dim
, isl_dim_set
), 1,
957 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
958 isl_space_dim(dim
, isl_dim_set
), 1,
960 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
961 coef
->n_eq
, coef
->n_ineq
);
962 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
969 /* Add constraints to graph->lp that bound the dependence distance for the given
970 * dependence from node i to node j.
971 * If s = 1, we add the constraint
973 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
978 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
981 * for each (x,y) in R.
982 * If s = -1, we add the constraint
984 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
989 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
992 * for each (x,y) in R.
993 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
994 * of valid constraints for R and then plug in
995 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
997 * with each coefficient (except m_0, c_j_0 and c_i_0)
998 * represented as a pair of non-negative coefficients.
1000 * Actually, we do not construct constraints for the c_*_x themselves,
1001 * but for the coefficients of c_*_x written as a linear combination
1002 * of the columns in node->cmap.
1004 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1005 struct isl_sched_edge
*edge
, int s
)
1009 isl_map
*map
= isl_map_copy(edge
->map
);
1010 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1012 isl_dim_map
*dim_map
;
1013 isl_basic_set
*coef
;
1014 struct isl_sched_node
*src
= edge
->src
;
1015 struct isl_sched_node
*dst
= edge
->dst
;
1017 coef
= inter_coefficients(graph
, map
);
1019 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1021 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1022 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1023 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1024 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1025 isl_mat_copy(dst
->cmap
));
1027 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1028 total
= isl_basic_set_total_dim(graph
->lp
);
1029 dim_map
= isl_dim_map_alloc(ctx
, total
);
1031 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1032 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1033 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1035 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1036 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1037 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1038 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1039 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1041 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1042 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1045 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1046 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1047 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1048 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1049 isl_space_dim(dim
, isl_dim_set
), 1,
1051 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1052 isl_space_dim(dim
, isl_dim_set
), 1,
1055 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1056 coef
->n_eq
, coef
->n_ineq
);
1057 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1059 isl_space_free(dim
);
1064 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1068 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1069 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1070 if (!edge
->validity
)
1072 if (edge
->src
!= edge
->dst
)
1074 if (add_intra_validity_constraints(graph
, edge
) < 0)
1078 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1079 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1080 if (!edge
->validity
)
1082 if (edge
->src
== edge
->dst
)
1084 if (add_inter_validity_constraints(graph
, edge
) < 0)
1091 /* Add constraints to graph->lp that bound the dependence distance
1092 * for all dependence relations.
1093 * If a given proximity dependence is identical to a validity
1094 * dependence, then the dependence distance is already bounded
1095 * from below (by zero), so we only need to bound the distance
1097 * Otherwise, we need to bound the distance both from above and from below.
1099 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1103 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1104 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1105 if (!edge
->proximity
)
1107 if (edge
->src
== edge
->dst
&&
1108 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
1110 if (edge
->src
!= edge
->dst
&&
1111 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
1115 if (edge
->src
== edge
->dst
&&
1116 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
1118 if (edge
->src
!= edge
->dst
&&
1119 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1126 /* Compute a basis for the rows in the linear part of the schedule
1127 * and extend this basis to a full basis. The remaining rows
1128 * can then be used to force linear independence from the rows
1131 * In particular, given the schedule rows S, we compute
1135 * with H the Hermite normal form of S. That is, all but the
1136 * first rank columns of Q are zero and so each row in S is
1137 * a linear combination of the first rank rows of Q.
1138 * The matrix Q is then transposed because we will write the
1139 * coefficients of the next schedule row as a column vector s
1140 * and express this s as a linear combination s = Q c of the
1143 static int node_update_cmap(struct isl_sched_node
*node
)
1146 int n_row
= isl_mat_rows(node
->sched
);
1148 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1149 1 + node
->nparam
, node
->nvar
);
1151 H
= isl_mat_left_hermite(H
, 0, NULL
, &Q
);
1152 isl_mat_free(node
->cmap
);
1153 node
->cmap
= isl_mat_transpose(Q
);
1154 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1157 if (!node
->cmap
|| node
->rank
< 0)
1162 /* Count the number of equality and inequality constraints
1163 * that will be added for the given map.
1164 * If carry is set, then we are counting the number of (validity)
1165 * constraints that will be added in setup_carry_lp and we count
1166 * each edge exactly once. Otherwise, we count as follows
1167 * validity -> 1 (>= 0)
1168 * validity+proximity -> 2 (>= 0 and upper bound)
1169 * proximity -> 2 (lower and upper bound)
1171 static int count_map_constraints(struct isl_sched_graph
*graph
,
1172 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1173 int *n_eq
, int *n_ineq
, int carry
)
1175 isl_basic_set
*coef
;
1176 int f
= carry
? 1 : edge
->proximity
? 2 : 1;
1178 if (carry
&& !edge
->validity
) {
1183 if (edge
->src
== edge
->dst
)
1184 coef
= intra_coefficients(graph
, map
);
1186 coef
= inter_coefficients(graph
, map
);
1189 *n_eq
+= f
* coef
->n_eq
;
1190 *n_ineq
+= f
* coef
->n_ineq
;
1191 isl_basic_set_free(coef
);
1196 /* Count the number of equality and inequality constraints
1197 * that will be added to the main lp problem.
1198 * We count as follows
1199 * validity -> 1 (>= 0)
1200 * validity+proximity -> 2 (>= 0 and upper bound)
1201 * proximity -> 2 (lower and upper bound)
1203 static int count_constraints(struct isl_sched_graph
*graph
,
1204 int *n_eq
, int *n_ineq
)
1208 *n_eq
= *n_ineq
= 0;
1209 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1210 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1211 isl_map
*map
= isl_map_copy(edge
->map
);
1213 if (count_map_constraints(graph
, edge
, map
,
1214 n_eq
, n_ineq
, 0) < 0)
1221 /* Add constraints that bound the values of the variable and parameter
1222 * coefficients of the schedule.
1224 * The maximal value of the coefficients is defined by the option
1225 * 'schedule_max_coefficient'.
1227 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1228 struct isl_sched_graph
*graph
)
1231 int max_coefficient
;
1234 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1236 if (max_coefficient
== -1)
1239 total
= isl_basic_set_total_dim(graph
->lp
);
1241 for (i
= 0; i
< graph
->n
; ++i
) {
1242 struct isl_sched_node
*node
= &graph
->node
[i
];
1243 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1245 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1248 dim
= 1 + node
->start
+ 1 + j
;
1249 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1250 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1251 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1258 /* Construct an ILP problem for finding schedule coefficients
1259 * that result in non-negative, but small dependence distances
1260 * over all dependences.
1261 * In particular, the dependence distances over proximity edges
1262 * are bounded by m_0 + m_n n and we compute schedule coefficients
1263 * with small values (preferably zero) of m_n and m_0.
1265 * All variables of the ILP are non-negative. The actual coefficients
1266 * may be negative, so each coefficient is represented as the difference
1267 * of two non-negative variables. The negative part always appears
1268 * immediately before the positive part.
1269 * Other than that, the variables have the following order
1271 * - sum of positive and negative parts of m_n coefficients
1273 * - sum of positive and negative parts of all c_n coefficients
1274 * (unconstrained when computing non-parametric schedules)
1275 * - sum of positive and negative parts of all c_x coefficients
1276 * - positive and negative parts of m_n coefficients
1279 * - positive and negative parts of c_i_n (if parametric)
1280 * - positive and negative parts of c_i_x
1282 * The c_i_x are not represented directly, but through the columns of
1283 * node->cmap. That is, the computed values are for variable t_i_x
1284 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1286 * The constraints are those from the edges plus two or three equalities
1287 * to express the sums.
1289 * If force_zero is set, then we add equalities to ensure that
1290 * the sum of the m_n coefficients and m_0 are both zero.
1292 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1303 int max_constant_term
;
1304 int max_coefficient
;
1306 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1307 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1309 parametric
= ctx
->opt
->schedule_parametric
;
1310 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1312 total
= param_pos
+ 2 * nparam
;
1313 for (i
= 0; i
< graph
->n
; ++i
) {
1314 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1315 if (node_update_cmap(node
) < 0)
1317 node
->start
= total
;
1318 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1321 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1324 dim
= isl_space_set_alloc(ctx
, 0, total
);
1325 isl_basic_set_free(graph
->lp
);
1326 n_eq
+= 2 + parametric
+ force_zero
;
1327 if (max_constant_term
!= -1)
1329 if (max_coefficient
!= -1)
1330 for (i
= 0; i
< graph
->n
; ++i
)
1331 n_ineq
+= 2 * graph
->node
[i
].nparam
+
1332 2 * graph
->node
[i
].nvar
;
1334 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1336 k
= isl_basic_set_alloc_equality(graph
->lp
);
1339 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1341 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1342 for (i
= 0; i
< 2 * nparam
; ++i
)
1343 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1346 k
= isl_basic_set_alloc_equality(graph
->lp
);
1349 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1350 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1354 k
= isl_basic_set_alloc_equality(graph
->lp
);
1357 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1358 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1359 for (i
= 0; i
< graph
->n
; ++i
) {
1360 int pos
= 1 + graph
->node
[i
].start
+ 1;
1362 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1363 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1367 k
= isl_basic_set_alloc_equality(graph
->lp
);
1370 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1371 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1372 for (i
= 0; i
< graph
->n
; ++i
) {
1373 struct isl_sched_node
*node
= &graph
->node
[i
];
1374 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1376 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1377 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1380 if (max_constant_term
!= -1)
1381 for (i
= 0; i
< graph
->n
; ++i
) {
1382 struct isl_sched_node
*node
= &graph
->node
[i
];
1383 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1386 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1387 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1388 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1391 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1393 if (add_all_validity_constraints(graph
) < 0)
1395 if (add_all_proximity_constraints(graph
) < 0)
1401 /* Analyze the conflicting constraint found by
1402 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1403 * constraint of one of the edges between distinct nodes, living, moreover
1404 * in distinct SCCs, then record the source and sink SCC as this may
1405 * be a good place to cut between SCCs.
1407 static int check_conflict(int con
, void *user
)
1410 struct isl_sched_graph
*graph
= user
;
1412 if (graph
->src_scc
>= 0)
1415 con
-= graph
->lp
->n_eq
;
1417 if (con
>= graph
->lp
->n_ineq
)
1420 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1421 if (!graph
->edge
[i
].validity
)
1423 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1425 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1427 if (graph
->edge
[i
].start
> con
)
1429 if (graph
->edge
[i
].end
<= con
)
1431 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1432 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1438 /* Check whether the next schedule row of the given node needs to be
1439 * non-trivial. Lower-dimensional domains may have some trivial rows,
1440 * but as soon as the number of remaining required non-trivial rows
1441 * is as large as the number or remaining rows to be computed,
1442 * all remaining rows need to be non-trivial.
1444 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1446 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1449 /* Solve the ILP problem constructed in setup_lp.
1450 * For each node such that all the remaining rows of its schedule
1451 * need to be non-trivial, we construct a non-triviality region.
1452 * This region imposes that the next row is independent of previous rows.
1453 * In particular the coefficients c_i_x are represented by t_i_x
1454 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1455 * its first columns span the rows of the previously computed part
1456 * of the schedule. The non-triviality region enforces that at least
1457 * one of the remaining components of t_i_x is non-zero, i.e.,
1458 * that the new schedule row depends on at least one of the remaining
1461 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1467 for (i
= 0; i
< graph
->n
; ++i
) {
1468 struct isl_sched_node
*node
= &graph
->node
[i
];
1469 int skip
= node
->rank
;
1470 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1471 if (needs_row(graph
, node
))
1472 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1474 graph
->region
[i
].len
= 0;
1476 lp
= isl_basic_set_copy(graph
->lp
);
1477 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1478 graph
->region
, &check_conflict
, graph
);
1482 /* Update the schedules of all nodes based on the given solution
1483 * of the LP problem.
1484 * The new row is added to the current band.
1485 * All possibly negative coefficients are encoded as a difference
1486 * of two non-negative variables, so we need to perform the subtraction
1487 * here. Moreover, if use_cmap is set, then the solution does
1488 * not refer to the actual coefficients c_i_x, but instead to variables
1489 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1490 * In this case, we then also need to perform this multiplication
1491 * to obtain the values of c_i_x.
1493 * If check_zero is set, then the first two coordinates of sol are
1494 * assumed to correspond to the dependence distance. If these two
1495 * coordinates are zero, then the corresponding scheduling dimension
1496 * is marked as being zero distance.
1498 static int update_schedule(struct isl_sched_graph
*graph
,
1499 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1503 isl_vec
*csol
= NULL
;
1508 isl_die(sol
->ctx
, isl_error_internal
,
1509 "no solution found", goto error
);
1512 zero
= isl_int_is_zero(sol
->el
[1]) &&
1513 isl_int_is_zero(sol
->el
[2]);
1515 for (i
= 0; i
< graph
->n
; ++i
) {
1516 struct isl_sched_node
*node
= &graph
->node
[i
];
1517 int pos
= node
->start
;
1518 int row
= isl_mat_rows(node
->sched
);
1521 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1525 isl_map_free(node
->sched_map
);
1526 node
->sched_map
= NULL
;
1527 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1530 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1532 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1533 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1534 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1535 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1536 for (j
= 0; j
< node
->nparam
; ++j
)
1537 node
->sched
= isl_mat_set_element(node
->sched
,
1538 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1539 for (j
= 0; j
< node
->nvar
; ++j
)
1540 isl_int_set(csol
->el
[j
],
1541 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1543 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1547 for (j
= 0; j
< node
->nvar
; ++j
)
1548 node
->sched
= isl_mat_set_element(node
->sched
,
1549 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1550 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1551 node
->zero
[graph
->n_total_row
] = zero
;
1557 graph
->n_total_row
++;
1566 /* Convert node->sched into a map and return this map.
1567 * We simply add equality constraints that express each output variable
1568 * as the affine combination of parameters and input variables specified
1569 * by the schedule matrix.
1571 * The result is cached in node->sched_map, which needs to be released
1572 * whenever node->sched is updated.
1574 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1578 isl_local_space
*ls
;
1579 isl_basic_map
*bmap
;
1584 if (node
->sched_map
)
1585 return isl_map_copy(node
->sched_map
);
1587 nrow
= isl_mat_rows(node
->sched
);
1588 ncol
= isl_mat_cols(node
->sched
) - 1;
1589 dim
= isl_space_from_domain(isl_space_copy(node
->dim
));
1590 dim
= isl_space_add_dims(dim
, isl_dim_out
, nrow
);
1591 bmap
= isl_basic_map_universe(isl_space_copy(dim
));
1592 ls
= isl_local_space_from_space(dim
);
1596 for (i
= 0; i
< nrow
; ++i
) {
1597 c
= isl_equality_alloc(isl_local_space_copy(ls
));
1598 isl_constraint_set_coefficient_si(c
, isl_dim_out
, i
, -1);
1599 isl_mat_get_element(node
->sched
, i
, 0, &v
);
1600 isl_constraint_set_constant(c
, v
);
1601 for (j
= 0; j
< node
->nparam
; ++j
) {
1602 isl_mat_get_element(node
->sched
, i
, 1 + j
, &v
);
1603 isl_constraint_set_coefficient(c
, isl_dim_param
, j
, v
);
1605 for (j
= 0; j
< node
->nvar
; ++j
) {
1606 isl_mat_get_element(node
->sched
,
1607 i
, 1 + node
->nparam
+ j
, &v
);
1608 isl_constraint_set_coefficient(c
, isl_dim_in
, j
, v
);
1610 bmap
= isl_basic_map_add_constraint(bmap
, c
);
1615 isl_local_space_free(ls
);
1617 node
->sched_map
= isl_map_from_basic_map(bmap
);
1618 return isl_map_copy(node
->sched_map
);
1621 /* Update the given dependence relation based on the current schedule.
1622 * That is, intersect the dependence relation with a map expressing
1623 * that source and sink are executed within the same iteration of
1624 * the current schedule.
1625 * This is not the most efficient way, but this shouldn't be a critical
1628 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1629 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1631 isl_map
*src_sched
, *dst_sched
, *id
;
1633 src_sched
= node_extract_schedule(src
);
1634 dst_sched
= node_extract_schedule(dst
);
1635 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1636 return isl_map_intersect(map
, id
);
1639 /* Update the dependence relations of all edges based on the current schedule.
1640 * If a dependence is carried completely by the current schedule, then
1641 * it is removed from the edge_tables. It is kept in the list of edges
1642 * as otherwise all edge_tables would have to be recomputed.
1644 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1648 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1649 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1650 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1654 if (isl_map_plain_is_empty(edge
->map
))
1655 graph_remove_edge(graph
, edge
);
1661 static void next_band(struct isl_sched_graph
*graph
)
1663 graph
->band_start
= graph
->n_total_row
;
1667 /* Topologically sort statements mapped to the same schedule iteration
1668 * and add a row to the schedule corresponding to this order.
1670 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1677 if (update_edges(ctx
, graph
) < 0)
1680 if (graph
->n_edge
== 0)
1683 if (detect_sccs(graph
) < 0)
1686 for (i
= 0; i
< graph
->n
; ++i
) {
1687 struct isl_sched_node
*node
= &graph
->node
[i
];
1688 int row
= isl_mat_rows(node
->sched
);
1689 int cols
= isl_mat_cols(node
->sched
);
1691 isl_map_free(node
->sched_map
);
1692 node
->sched_map
= NULL
;
1693 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1696 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1698 for (j
= 1; j
< cols
; ++j
)
1699 node
->sched
= isl_mat_set_element_si(node
->sched
,
1701 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1704 graph
->n_total_row
++;
1710 /* Construct an isl_schedule based on the computed schedule stored
1711 * in graph and with parameters specified by dim.
1713 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1714 __isl_take isl_space
*dim
)
1718 isl_schedule
*sched
= NULL
;
1723 ctx
= isl_space_get_ctx(dim
);
1724 sched
= isl_calloc(ctx
, struct isl_schedule
,
1725 sizeof(struct isl_schedule
) +
1726 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1731 sched
->n
= graph
->n
;
1732 sched
->n_band
= graph
->n_band
;
1733 sched
->n_total_row
= graph
->n_total_row
;
1735 for (i
= 0; i
< sched
->n
; ++i
) {
1737 int *band_end
, *band_id
, *zero
;
1739 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1740 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1741 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1742 sched
->node
[i
].sched
= node_extract_schedule(&graph
->node
[i
]);
1743 sched
->node
[i
].band_end
= band_end
;
1744 sched
->node
[i
].band_id
= band_id
;
1745 sched
->node
[i
].zero
= zero
;
1746 if (!band_end
|| !band_id
|| !zero
)
1749 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1750 zero
[r
] = graph
->node
[i
].zero
[r
];
1751 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1752 if (graph
->node
[i
].band
[r
] == b
)
1755 if (graph
->node
[i
].band
[r
] == -1)
1758 if (r
== graph
->n_total_row
)
1760 sched
->node
[i
].n_band
= b
;
1761 for (--b
; b
>= 0; --b
)
1762 band_id
[b
] = graph
->node
[i
].band_id
[b
];
1769 isl_space_free(dim
);
1770 isl_schedule_free(sched
);
1774 /* Copy nodes that satisfy node_pred from the src dependence graph
1775 * to the dst dependence graph.
1777 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
1778 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1783 for (i
= 0; i
< src
->n
; ++i
) {
1784 if (!node_pred(&src
->node
[i
], data
))
1786 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
1787 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
1788 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
1789 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
1790 dst
->node
[dst
->n
].sched_map
=
1791 isl_map_copy(src
->node
[i
].sched_map
);
1792 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
1793 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
1794 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
1801 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1802 * to the dst dependence graph.
1803 * If the source or destination node of the edge is not in the destination
1804 * graph, then it must be a backward proximity edge and it should simply
1807 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
1808 struct isl_sched_graph
*src
,
1809 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
1815 for (i
= 0; i
< src
->n_edge
; ++i
) {
1816 struct isl_sched_edge
*edge
= &src
->edge
[i
];
1818 struct isl_sched_node
*dst_src
, *dst_dst
;
1820 if (!edge_pred(edge
, data
))
1823 if (isl_map_plain_is_empty(edge
->map
))
1826 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
1827 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
1828 if (!dst_src
|| !dst_dst
) {
1830 isl_die(ctx
, isl_error_internal
,
1831 "backward validity edge", return -1);
1835 map
= isl_map_copy(edge
->map
);
1837 dst
->edge
[dst
->n_edge
].src
= dst_src
;
1838 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
1839 dst
->edge
[dst
->n_edge
].map
= map
;
1840 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
1841 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
1844 for (t
= 0; t
<= isl_edge_last
; ++t
) {
1846 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
1848 if (graph_edge_table_add(ctx
, dst
, t
,
1849 &dst
->edge
[dst
->n_edge
- 1]) < 0)
1857 /* Given a "src" dependence graph that contains the nodes from "dst"
1858 * that satisfy node_pred, copy the schedule computed in "src"
1859 * for those nodes back to "dst".
1861 static int copy_schedule(struct isl_sched_graph
*dst
,
1862 struct isl_sched_graph
*src
,
1863 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1868 for (i
= 0; i
< dst
->n
; ++i
) {
1869 if (!node_pred(&dst
->node
[i
], data
))
1871 isl_mat_free(dst
->node
[i
].sched
);
1872 isl_map_free(dst
->node
[i
].sched_map
);
1873 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
1874 dst
->node
[i
].sched_map
=
1875 isl_map_copy(src
->node
[src
->n
].sched_map
);
1879 dst
->n_total_row
= src
->n_total_row
;
1880 dst
->n_band
= src
->n_band
;
1885 /* Compute the maximal number of variables over all nodes.
1886 * This is the maximal number of linearly independent schedule
1887 * rows that we need to compute.
1888 * Just in case we end up in a part of the dependence graph
1889 * with only lower-dimensional domains, we make sure we will
1890 * compute the required amount of extra linearly independent rows.
1892 static int compute_maxvar(struct isl_sched_graph
*graph
)
1897 for (i
= 0; i
< graph
->n
; ++i
) {
1898 struct isl_sched_node
*node
= &graph
->node
[i
];
1901 if (node_update_cmap(node
) < 0)
1903 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
1904 if (nvar
> graph
->maxvar
)
1905 graph
->maxvar
= nvar
;
1911 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1912 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1914 /* Compute a schedule for a subgraph of "graph". In particular, for
1915 * the graph composed of nodes that satisfy node_pred and edges that
1916 * that satisfy edge_pred. The caller should precompute the number
1917 * of nodes and edges that satisfy these predicates and pass them along
1918 * as "n" and "n_edge".
1919 * If the subgraph is known to consist of a single component, then wcc should
1920 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1921 * Otherwise, we call compute_schedule, which will check whether the subgraph
1924 static int compute_sub_schedule(isl_ctx
*ctx
,
1925 struct isl_sched_graph
*graph
, int n
, int n_edge
,
1926 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
1927 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
1930 struct isl_sched_graph split
= { 0 };
1933 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
1935 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
1937 if (graph_init_table(ctx
, &split
) < 0)
1939 for (t
= 0; t
<= isl_edge_last
; ++t
)
1940 split
.max_edge
[t
] = graph
->max_edge
[t
];
1941 if (graph_init_edge_tables(ctx
, &split
) < 0)
1943 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
1945 split
.n_row
= graph
->n_row
;
1946 split
.n_total_row
= graph
->n_total_row
;
1947 split
.n_band
= graph
->n_band
;
1948 split
.band_start
= graph
->band_start
;
1950 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
1952 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
1955 copy_schedule(graph
, &split
, node_pred
, data
);
1957 graph_free(ctx
, &split
);
1960 graph_free(ctx
, &split
);
1964 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
1966 return node
->scc
== scc
;
1969 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
1971 return node
->scc
<= scc
;
1974 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
1976 return node
->scc
>= scc
;
1979 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
1981 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
1984 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
1986 return edge
->dst
->scc
<= scc
;
1989 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
1991 return edge
->src
->scc
>= scc
;
1994 /* Pad the schedules of all nodes with zero rows such that in the end
1995 * they all have graph->n_total_row rows.
1996 * The extra rows don't belong to any band, so they get assigned band number -1.
1998 static int pad_schedule(struct isl_sched_graph
*graph
)
2002 for (i
= 0; i
< graph
->n
; ++i
) {
2003 struct isl_sched_node
*node
= &graph
->node
[i
];
2004 int row
= isl_mat_rows(node
->sched
);
2005 if (graph
->n_total_row
> row
) {
2006 isl_map_free(node
->sched_map
);
2007 node
->sched_map
= NULL
;
2009 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2010 graph
->n_total_row
- row
);
2013 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2020 /* Split the current graph into two parts and compute a schedule for each
2021 * part individually. In particular, one part consists of all SCCs up
2022 * to and including graph->src_scc, while the other part contains the other
2025 * The split is enforced in the schedule by constant rows with two different
2026 * values (0 and 1). These constant rows replace the previously computed rows
2027 * in the current band.
2028 * It would be possible to reuse them as the first rows in the next
2029 * band, but recomputing them may result in better rows as we are looking
2030 * at a smaller part of the dependence graph.
2031 * compute_split_schedule is only called when no zero-distance schedule row
2032 * could be found on the entire graph, so we wark the splitting row as
2033 * non zero-distance.
2035 * The band_id of the second group is set to n, where n is the number
2036 * of nodes in the first group. This ensures that the band_ids over
2037 * the two groups remain disjoint, even if either or both of the two
2038 * groups contain independent components.
2040 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2042 int i
, j
, n
, e1
, e2
;
2043 int n_total_row
, orig_total_row
;
2044 int n_band
, orig_band
;
2047 drop
= graph
->n_total_row
- graph
->band_start
;
2048 graph
->n_total_row
-= drop
;
2049 graph
->n_row
-= drop
;
2052 for (i
= 0; i
< graph
->n
; ++i
) {
2053 struct isl_sched_node
*node
= &graph
->node
[i
];
2054 int row
= isl_mat_rows(node
->sched
) - drop
;
2055 int cols
= isl_mat_cols(node
->sched
);
2056 int before
= node
->scc
<= graph
->src_scc
;
2061 isl_map_free(node
->sched_map
);
2062 node
->sched_map
= NULL
;
2063 node
->sched
= isl_mat_drop_rows(node
->sched
,
2064 graph
->band_start
, drop
);
2065 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2068 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2070 for (j
= 1; j
< cols
; ++j
)
2071 node
->sched
= isl_mat_set_element_si(node
->sched
,
2073 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2074 node
->zero
[graph
->n_total_row
] = 0;
2078 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2079 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2081 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2085 graph
->n_total_row
++;
2088 for (i
= 0; i
< graph
->n
; ++i
) {
2089 struct isl_sched_node
*node
= &graph
->node
[i
];
2090 if (node
->scc
> graph
->src_scc
)
2091 node
->band_id
[graph
->n_band
] = n
;
2094 orig_total_row
= graph
->n_total_row
;
2095 orig_band
= graph
->n_band
;
2096 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2097 &node_scc_at_most
, &edge_dst_scc_at_most
,
2098 graph
->src_scc
, 0) < 0)
2100 n_total_row
= graph
->n_total_row
;
2101 graph
->n_total_row
= orig_total_row
;
2102 n_band
= graph
->n_band
;
2103 graph
->n_band
= orig_band
;
2104 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2105 &node_scc_at_least
, &edge_src_scc_at_least
,
2106 graph
->src_scc
+ 1, 0) < 0)
2108 if (n_total_row
> graph
->n_total_row
)
2109 graph
->n_total_row
= n_total_row
;
2110 if (n_band
> graph
->n_band
)
2111 graph
->n_band
= n_band
;
2113 return pad_schedule(graph
);
2116 /* Compute the next band of the schedule after updating the dependence
2117 * relations based on the the current schedule.
2119 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2121 if (update_edges(ctx
, graph
) < 0)
2125 return compute_schedule(ctx
, graph
);
2128 /* Add constraints to graph->lp that force the dependence "map" (which
2129 * is part of the dependence relation of "edge")
2130 * to be respected and attempt to carry it, where the edge is one from
2131 * a node j to itself. "pos" is the sequence number of the given map.
2132 * That is, add constraints that enforce
2134 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2135 * = c_j_x (y - x) >= e_i
2137 * for each (x,y) in R.
2138 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2139 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2140 * with each coefficient in c_j_x represented as a pair of non-negative
2143 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2144 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2147 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2149 isl_dim_map
*dim_map
;
2150 isl_basic_set
*coef
;
2151 struct isl_sched_node
*node
= edge
->src
;
2153 coef
= intra_coefficients(graph
, map
);
2155 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2157 total
= isl_basic_set_total_dim(graph
->lp
);
2158 dim_map
= isl_dim_map_alloc(ctx
, total
);
2159 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2160 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2161 isl_space_dim(dim
, isl_dim_set
), 1,
2163 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2164 isl_space_dim(dim
, isl_dim_set
), 1,
2166 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2167 coef
->n_eq
, coef
->n_ineq
);
2168 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2170 isl_space_free(dim
);
2175 /* Add constraints to graph->lp that force the dependence "map" (which
2176 * is part of the dependence relation of "edge")
2177 * to be respected and attempt to carry it, where the edge is one from
2178 * node j to node k. "pos" is the sequence number of the given map.
2179 * That is, add constraints that enforce
2181 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2183 * for each (x,y) in R.
2184 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2185 * of valid constraints for R and then plug in
2186 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2187 * with each coefficient (except e_i, c_k_0 and c_j_0)
2188 * represented as a pair of non-negative coefficients.
2190 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2191 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2194 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2196 isl_dim_map
*dim_map
;
2197 isl_basic_set
*coef
;
2198 struct isl_sched_node
*src
= edge
->src
;
2199 struct isl_sched_node
*dst
= edge
->dst
;
2201 coef
= inter_coefficients(graph
, map
);
2203 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2205 total
= isl_basic_set_total_dim(graph
->lp
);
2206 dim_map
= isl_dim_map_alloc(ctx
, total
);
2208 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2210 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2211 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2212 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2213 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2214 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2216 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2217 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2220 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2221 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2222 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2223 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2224 isl_space_dim(dim
, isl_dim_set
), 1,
2226 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2227 isl_space_dim(dim
, isl_dim_set
), 1,
2230 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2231 coef
->n_eq
, coef
->n_ineq
);
2232 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2234 isl_space_free(dim
);
2239 /* Add constraints to graph->lp that force all validity dependences
2240 * to be respected and attempt to carry them.
2242 static int add_all_constraints(struct isl_sched_graph
*graph
)
2248 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2249 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2251 if (!edge
->validity
)
2254 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2255 isl_basic_map
*bmap
;
2258 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2259 map
= isl_map_from_basic_map(bmap
);
2261 if (edge
->src
== edge
->dst
&&
2262 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2264 if (edge
->src
!= edge
->dst
&&
2265 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2274 /* Count the number of equality and inequality constraints
2275 * that will be added to the carry_lp problem.
2276 * We count each edge exactly once.
2278 static int count_all_constraints(struct isl_sched_graph
*graph
,
2279 int *n_eq
, int *n_ineq
)
2283 *n_eq
= *n_ineq
= 0;
2284 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2285 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2286 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2287 isl_basic_map
*bmap
;
2290 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2291 map
= isl_map_from_basic_map(bmap
);
2293 if (count_map_constraints(graph
, edge
, map
,
2294 n_eq
, n_ineq
, 1) < 0)
2302 /* Construct an LP problem for finding schedule coefficients
2303 * such that the schedule carries as many dependences as possible.
2304 * In particular, for each dependence i, we bound the dependence distance
2305 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2306 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2307 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2308 * Note that if the dependence relation is a union of basic maps,
2309 * then we have to consider each basic map individually as it may only
2310 * be possible to carry the dependences expressed by some of those
2311 * basic maps and not all off them.
2312 * Below, we consider each of those basic maps as a separate "edge".
2314 * All variables of the LP are non-negative. The actual coefficients
2315 * may be negative, so each coefficient is represented as the difference
2316 * of two non-negative variables. The negative part always appears
2317 * immediately before the positive part.
2318 * Other than that, the variables have the following order
2320 * - sum of (1 - e_i) over all edges
2321 * - sum of positive and negative parts of all c_n coefficients
2322 * (unconstrained when computing non-parametric schedules)
2323 * - sum of positive and negative parts of all c_x coefficients
2328 * - positive and negative parts of c_i_n (if parametric)
2329 * - positive and negative parts of c_i_x
2331 * The constraints are those from the (validity) edges plus three equalities
2332 * to express the sums and n_edge inequalities to express e_i <= 1.
2334 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2344 for (i
= 0; i
< graph
->n_edge
; ++i
)
2345 n_edge
+= graph
->edge
[i
].map
->n
;
2348 for (i
= 0; i
< graph
->n
; ++i
) {
2349 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2350 node
->start
= total
;
2351 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2354 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2357 dim
= isl_space_set_alloc(ctx
, 0, total
);
2358 isl_basic_set_free(graph
->lp
);
2361 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2362 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2364 k
= isl_basic_set_alloc_equality(graph
->lp
);
2367 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2368 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2369 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2370 for (i
= 0; i
< n_edge
; ++i
)
2371 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2373 k
= isl_basic_set_alloc_equality(graph
->lp
);
2376 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2377 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2378 for (i
= 0; i
< graph
->n
; ++i
) {
2379 int pos
= 1 + graph
->node
[i
].start
+ 1;
2381 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2382 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2385 k
= isl_basic_set_alloc_equality(graph
->lp
);
2388 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2389 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2390 for (i
= 0; i
< graph
->n
; ++i
) {
2391 struct isl_sched_node
*node
= &graph
->node
[i
];
2392 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2394 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2395 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2398 for (i
= 0; i
< n_edge
; ++i
) {
2399 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2402 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2403 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2404 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2407 if (add_all_constraints(graph
) < 0)
2413 /* If the schedule_split_scaled option is set and if the linear
2414 * parts of the scheduling rows for all nodes in the graphs have
2415 * non-trivial common divisor, then split off the constant term
2416 * from the linear part.
2417 * The constant term is then placed in a separate band and
2418 * the linear part is reduced.
2420 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2426 if (!ctx
->opt
->schedule_split_scaled
)
2432 isl_int_init(gcd_i
);
2434 isl_int_set_si(gcd
, 0);
2436 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2438 for (i
= 0; i
< graph
->n
; ++i
) {
2439 struct isl_sched_node
*node
= &graph
->node
[i
];
2440 int cols
= isl_mat_cols(node
->sched
);
2442 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2443 isl_int_gcd(gcd
, gcd
, gcd_i
);
2446 isl_int_clear(gcd_i
);
2448 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2455 for (i
= 0; i
< graph
->n
; ++i
) {
2456 struct isl_sched_node
*node
= &graph
->node
[i
];
2458 isl_map_free(node
->sched_map
);
2459 node
->sched_map
= NULL
;
2460 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2463 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2464 node
->sched
->row
[row
][0], gcd
);
2465 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2466 node
->sched
->row
[row
][0], gcd
);
2467 isl_int_mul(node
->sched
->row
[row
][0],
2468 node
->sched
->row
[row
][0], gcd
);
2469 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2472 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2475 graph
->n_total_row
++;
2484 /* Construct a schedule row for each node such that as many dependences
2485 * as possible are carried and then continue with the next band.
2487 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2495 for (i
= 0; i
< graph
->n_edge
; ++i
)
2496 n_edge
+= graph
->edge
[i
].map
->n
;
2498 if (setup_carry_lp(ctx
, graph
) < 0)
2501 lp
= isl_basic_set_copy(graph
->lp
);
2502 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2506 if (sol
->size
== 0) {
2508 isl_die(ctx
, isl_error_internal
,
2509 "error in schedule construction", return -1);
2512 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2514 isl_die(ctx
, isl_error_unknown
,
2515 "unable to carry dependences", return -1);
2518 if (update_schedule(graph
, sol
, 0, 0) < 0)
2521 if (split_scaled(ctx
, graph
) < 0)
2524 return compute_next_band(ctx
, graph
);
2527 /* Are there any (non-empty) validity edges in the graph?
2529 static int has_validity_edges(struct isl_sched_graph
*graph
)
2533 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2536 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
2541 if (graph
->edge
[i
].validity
)
2548 /* Should we apply a Feautrier step?
2549 * That is, did the user request the Feautrier algorithm and are
2550 * there any validity dependences (left)?
2552 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2554 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2557 return has_validity_edges(graph
);
2560 /* Compute a schedule for a connected dependence graph using Feautrier's
2561 * multi-dimensional scheduling algorithm.
2562 * The original algorithm is described in [1].
2563 * The main idea is to minimize the number of scheduling dimensions, by
2564 * trying to satisfy as many dependences as possible per scheduling dimension.
2566 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2567 * Problem, Part II: Multi-Dimensional Time.
2568 * In Intl. Journal of Parallel Programming, 1992.
2570 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2571 struct isl_sched_graph
*graph
)
2573 return carry_dependences(ctx
, graph
);
2576 /* Compute a schedule for a connected dependence graph.
2577 * We try to find a sequence of as many schedule rows as possible that result
2578 * in non-negative dependence distances (independent of the previous rows
2579 * in the sequence, i.e., such that the sequence is tilable).
2580 * If we can't find any more rows we either
2581 * - split between SCCs and start over (assuming we found an interesting
2582 * pair of SCCs between which to split)
2583 * - continue with the next band (assuming the current band has at least
2585 * - try to carry as many dependences as possible and continue with the next
2588 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2589 * as many validity dependences as possible. When all validity dependences
2590 * are satisfied we extend the schedule to a full-dimensional schedule.
2592 * If we manage to complete the schedule, we finish off by topologically
2593 * sorting the statements based on the remaining dependences.
2595 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2596 * outermost dimension in the current band to be zero distance. If this
2597 * turns out to be impossible, we fall back on the general scheme above
2598 * and try to carry as many dependences as possible.
2600 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2604 if (detect_sccs(graph
) < 0)
2608 if (compute_maxvar(graph
) < 0)
2611 if (need_feautrier_step(ctx
, graph
))
2612 return compute_schedule_wcc_feautrier(ctx
, graph
);
2614 if (ctx
->opt
->schedule_outer_zero_distance
)
2617 while (graph
->n_row
< graph
->maxvar
) {
2620 graph
->src_scc
= -1;
2621 graph
->dst_scc
= -1;
2623 if (setup_lp(ctx
, graph
, force_zero
) < 0)
2625 sol
= solve_lp(graph
);
2628 if (sol
->size
== 0) {
2630 if (!ctx
->opt
->schedule_maximize_band_depth
&&
2631 graph
->n_total_row
> graph
->band_start
)
2632 return compute_next_band(ctx
, graph
);
2633 if (graph
->src_scc
>= 0)
2634 return compute_split_schedule(ctx
, graph
);
2635 if (graph
->n_total_row
> graph
->band_start
)
2636 return compute_next_band(ctx
, graph
);
2637 return carry_dependences(ctx
, graph
);
2639 if (update_schedule(graph
, sol
, 1, 1) < 0)
2644 if (graph
->n_total_row
> graph
->band_start
)
2646 return sort_statements(ctx
, graph
);
2649 /* Add a row to the schedules that separates the SCCs and move
2652 static int split_on_scc(struct isl_sched_graph
*graph
)
2656 for (i
= 0; i
< graph
->n
; ++i
) {
2657 struct isl_sched_node
*node
= &graph
->node
[i
];
2658 int row
= isl_mat_rows(node
->sched
);
2660 isl_map_free(node
->sched_map
);
2661 node
->sched_map
= NULL
;
2662 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2663 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2667 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2670 graph
->n_total_row
++;
2676 /* Compute a schedule for each component (identified by node->scc)
2677 * of the dependence graph separately and then combine the results.
2678 * Depending on the setting of schedule_fuse, a component may be
2679 * either weakly or strongly connected.
2681 * The band_id is adjusted such that each component has a separate id.
2682 * Note that the band_id may have already been set to a value different
2683 * from zero by compute_split_schedule.
2685 static int compute_component_schedule(isl_ctx
*ctx
,
2686 struct isl_sched_graph
*graph
)
2690 int n_total_row
, orig_total_row
;
2691 int n_band
, orig_band
;
2693 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
)
2694 split_on_scc(graph
);
2697 orig_total_row
= graph
->n_total_row
;
2699 orig_band
= graph
->n_band
;
2700 for (i
= 0; i
< graph
->n
; ++i
)
2701 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
2702 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
2704 for (i
= 0; i
< graph
->n
; ++i
)
2705 if (graph
->node
[i
].scc
== wcc
)
2708 for (i
= 0; i
< graph
->n_edge
; ++i
)
2709 if (graph
->edge
[i
].src
->scc
== wcc
&&
2710 graph
->edge
[i
].dst
->scc
== wcc
)
2713 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
2715 &edge_scc_exactly
, wcc
, 1) < 0)
2717 if (graph
->n_total_row
> n_total_row
)
2718 n_total_row
= graph
->n_total_row
;
2719 graph
->n_total_row
= orig_total_row
;
2720 if (graph
->n_band
> n_band
)
2721 n_band
= graph
->n_band
;
2722 graph
->n_band
= orig_band
;
2725 graph
->n_total_row
= n_total_row
;
2726 graph
->n_band
= n_band
;
2728 return pad_schedule(graph
);
2731 /* Compute a schedule for the given dependence graph.
2732 * We first check if the graph is connected (through validity dependences)
2733 * and, if not, compute a schedule for each component separately.
2734 * If schedule_fuse is set to minimal fusion, then we check for strongly
2735 * connected components instead and compute a separate schedule for
2736 * each such strongly connected component.
2738 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2740 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
2741 if (detect_sccs(graph
) < 0)
2744 if (detect_wccs(graph
) < 0)
2749 return compute_component_schedule(ctx
, graph
);
2751 return compute_schedule_wcc(ctx
, graph
);
2754 /* Compute a schedule for the given union of domains that respects
2755 * all the validity dependences.
2756 * If the default isl scheduling algorithm is used, it tries to minimize
2757 * the dependence distances over the proximity dependences.
2758 * If Feautrier's scheduling algorithm is used, the proximity dependence
2759 * distances are only minimized during the extension to a full-dimensional
2762 __isl_give isl_schedule
*isl_union_set_compute_schedule(
2763 __isl_take isl_union_set
*domain
,
2764 __isl_take isl_union_map
*validity
,
2765 __isl_take isl_union_map
*proximity
)
2767 isl_ctx
*ctx
= isl_union_set_get_ctx(domain
);
2769 struct isl_sched_graph graph
= { 0 };
2770 isl_schedule
*sched
;
2771 struct isl_extract_edge_data data
;
2773 domain
= isl_union_set_align_params(domain
,
2774 isl_union_map_get_space(validity
));
2775 domain
= isl_union_set_align_params(domain
,
2776 isl_union_map_get_space(proximity
));
2777 dim
= isl_union_set_get_space(domain
);
2778 validity
= isl_union_map_align_params(validity
, isl_space_copy(dim
));
2779 proximity
= isl_union_map_align_params(proximity
, dim
);
2784 graph
.n
= isl_union_set_n_set(domain
);
2787 if (graph_alloc(ctx
, &graph
, graph
.n
,
2788 isl_union_map_n_map(validity
) + isl_union_map_n_map(proximity
)) < 0)
2792 if (isl_union_set_foreach_set(domain
, &extract_node
, &graph
) < 0)
2794 if (graph_init_table(ctx
, &graph
) < 0)
2796 graph
.max_edge
[isl_edge_validity
] = isl_union_map_n_map(validity
);
2797 graph
.max_edge
[isl_edge_proximity
] = isl_union_map_n_map(proximity
);
2798 if (graph_init_edge_tables(ctx
, &graph
) < 0)
2801 data
.graph
= &graph
;
2802 data
.type
= isl_edge_validity
;
2803 if (isl_union_map_foreach_map(validity
, &extract_edge
, &data
) < 0)
2805 data
.type
= isl_edge_proximity
;
2806 if (isl_union_map_foreach_map(proximity
, &extract_edge
, &data
) < 0)
2809 if (compute_schedule(ctx
, &graph
) < 0)
2813 sched
= extract_schedule(&graph
, isl_union_set_get_space(domain
));
2815 graph_free(ctx
, &graph
);
2816 isl_union_set_free(domain
);
2817 isl_union_map_free(validity
);
2818 isl_union_map_free(proximity
);
2822 graph_free(ctx
, &graph
);
2823 isl_union_set_free(domain
);
2824 isl_union_map_free(validity
);
2825 isl_union_map_free(proximity
);
2829 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
2835 if (--sched
->ref
> 0)
2838 for (i
= 0; i
< sched
->n
; ++i
) {
2839 isl_map_free(sched
->node
[i
].sched
);
2840 free(sched
->node
[i
].band_end
);
2841 free(sched
->node
[i
].band_id
);
2842 free(sched
->node
[i
].zero
);
2844 isl_space_free(sched
->dim
);
2845 isl_band_list_free(sched
->band_forest
);
2850 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
2852 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
2855 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
2858 isl_union_map
*umap
;
2863 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
2864 for (i
= 0; i
< sched
->n
; ++i
)
2865 umap
= isl_union_map_add_map(umap
,
2866 isl_map_copy(sched
->node
[i
].sched
));
2871 static __isl_give isl_band_list
*construct_band_list(
2872 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2873 int band_nr
, int *parent_active
, int n_active
);
2875 /* Construct an isl_band structure for the band in the given schedule
2876 * with sequence number band_nr for the n_active nodes marked by active.
2877 * If the nodes don't have a band with the given sequence number,
2878 * then a band without members is created.
2880 * Because of the way the schedule is constructed, we know that
2881 * the position of the band inside the schedule of a node is the same
2882 * for all active nodes.
2884 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
2885 __isl_keep isl_band
*parent
,
2886 int band_nr
, int *active
, int n_active
)
2889 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2891 unsigned start
, end
;
2893 band
= isl_calloc_type(ctx
, isl_band
);
2898 band
->schedule
= schedule
;
2899 band
->parent
= parent
;
2901 for (i
= 0; i
< schedule
->n
; ++i
)
2902 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
2905 if (i
< schedule
->n
) {
2906 band
->children
= construct_band_list(schedule
, band
,
2907 band_nr
+ 1, active
, n_active
);
2908 if (!band
->children
)
2912 for (i
= 0; i
< schedule
->n
; ++i
)
2916 if (i
>= schedule
->n
)
2917 isl_die(ctx
, isl_error_internal
,
2918 "band without active statements", goto error
);
2920 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
2921 end
= band_nr
< schedule
->node
[i
].n_band
?
2922 schedule
->node
[i
].band_end
[band_nr
] : start
;
2923 band
->n
= end
- start
;
2925 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
2929 for (j
= 0; j
< band
->n
; ++j
)
2930 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
2932 band
->map
= isl_union_map_empty(isl_space_copy(schedule
->dim
));
2933 for (i
= 0; i
< schedule
->n
; ++i
) {
2940 map
= isl_map_copy(schedule
->node
[i
].sched
);
2941 n_out
= isl_map_dim(map
, isl_dim_out
);
2942 map
= isl_map_project_out(map
, isl_dim_out
, end
, n_out
- end
);
2943 map
= isl_map_project_out(map
, isl_dim_out
, 0, start
);
2944 band
->map
= isl_union_map_union(band
->map
,
2945 isl_union_map_from_map(map
));
2952 isl_band_free(band
);
2956 /* Construct a list of bands that start at the same position (with
2957 * sequence number band_nr) in the schedules of the nodes that
2958 * were active in the parent band.
2960 * A separate isl_band structure is created for each band_id
2961 * and for each node that does not have a band with sequence
2962 * number band_nr. In the latter case, a band without members
2964 * This ensures that if a band has any children, then each node
2965 * that was active in the band is active in exactly one of the children.
2967 static __isl_give isl_band_list
*construct_band_list(
2968 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2969 int band_nr
, int *parent_active
, int n_active
)
2972 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2975 isl_band_list
*list
;
2978 for (i
= 0; i
< n_active
; ++i
) {
2979 for (j
= 0; j
< schedule
->n
; ++j
) {
2980 if (!parent_active
[j
])
2982 if (schedule
->node
[j
].n_band
<= band_nr
)
2984 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
2990 for (j
= 0; j
< schedule
->n
; ++j
)
2991 if (schedule
->node
[j
].n_band
<= band_nr
)
2996 list
= isl_band_list_alloc(ctx
, n_band
);
2997 band
= construct_band(schedule
, parent
, band_nr
,
2998 parent_active
, n_active
);
2999 return isl_band_list_add(list
, band
);
3002 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3006 list
= isl_band_list_alloc(ctx
, n_band
);
3008 for (i
= 0; i
< n_active
; ++i
) {
3012 for (j
= 0; j
< schedule
->n
; ++j
) {
3013 active
[j
] = parent_active
[j
] &&
3014 schedule
->node
[j
].n_band
> band_nr
&&
3015 schedule
->node
[j
].band_id
[band_nr
] == i
;
3022 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
3024 list
= isl_band_list_add(list
, band
);
3026 for (i
= 0; i
< schedule
->n
; ++i
) {
3028 if (!parent_active
[i
])
3030 if (schedule
->node
[i
].n_band
> band_nr
)
3032 for (j
= 0; j
< schedule
->n
; ++j
)
3034 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
3035 list
= isl_band_list_add(list
, band
);
3043 /* Construct a band forest representation of the schedule and
3044 * return the list of roots.
3046 static __isl_give isl_band_list
*construct_forest(
3047 __isl_keep isl_schedule
*schedule
)
3050 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3051 isl_band_list
*forest
;
3054 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3058 for (i
= 0; i
< schedule
->n
; ++i
)
3061 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
3068 /* Return the roots of a band forest representation of the schedule.
3070 __isl_give isl_band_list
*isl_schedule_get_band_forest(
3071 __isl_keep isl_schedule
*schedule
)
3075 if (!schedule
->band_forest
)
3076 schedule
->band_forest
= construct_forest(schedule
);
3077 return isl_band_list_dup(schedule
->band_forest
);
3080 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3081 __isl_keep isl_band_list
*list
);
3083 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
3084 __isl_keep isl_band
*band
)
3086 isl_band_list
*children
;
3088 p
= isl_printer_start_line(p
);
3089 p
= isl_printer_print_union_map(p
, band
->map
);
3090 p
= isl_printer_end_line(p
);
3092 if (!isl_band_has_children(band
))
3095 children
= isl_band_get_children(band
);
3097 p
= isl_printer_indent(p
, 4);
3098 p
= print_band_list(p
, children
);
3099 p
= isl_printer_indent(p
, -4);
3101 isl_band_list_free(children
);
3106 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3107 __isl_keep isl_band_list
*list
)
3111 n
= isl_band_list_n_band(list
);
3112 for (i
= 0; i
< n
; ++i
) {
3114 band
= isl_band_list_get_band(list
, i
);
3115 p
= print_band(p
, band
);
3116 isl_band_free(band
);
3122 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
3123 __isl_keep isl_schedule
*schedule
)
3125 isl_band_list
*forest
;
3127 forest
= isl_schedule_get_band_forest(schedule
);
3129 p
= print_band_list(p
, forest
);
3131 isl_band_list_free(forest
);
3136 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
3138 isl_printer
*printer
;
3143 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
3144 printer
= isl_printer_print_schedule(printer
, schedule
);
3146 isl_printer_free(printer
);