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 a validity edge
403 * between the given two nodes.
405 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
406 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
408 return graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
411 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
412 int n_node
, int n_edge
)
417 graph
->n_edge
= n_edge
;
418 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
419 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
420 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
421 graph
->stack
= isl_alloc_array(ctx
, int, graph
->n
);
422 graph
->edge
= isl_calloc_array(ctx
,
423 struct isl_sched_edge
, graph
->n_edge
);
425 graph
->intra_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
426 graph
->inter_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
428 if (!graph
->node
|| !graph
->region
|| !graph
->stack
|| !graph
->edge
||
432 for(i
= 0; i
< graph
->n
; ++i
)
433 graph
->sorted
[i
] = i
;
438 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
442 isl_hmap_map_basic_set_free(ctx
, graph
->intra_hmap
);
443 isl_hmap_map_basic_set_free(ctx
, graph
->inter_hmap
);
445 for (i
= 0; i
< graph
->n
; ++i
) {
446 isl_space_free(graph
->node
[i
].dim
);
447 isl_mat_free(graph
->node
[i
].sched
);
448 isl_map_free(graph
->node
[i
].sched_map
);
449 isl_mat_free(graph
->node
[i
].cmap
);
451 free(graph
->node
[i
].band
);
452 free(graph
->node
[i
].band_id
);
453 free(graph
->node
[i
].zero
);
458 for (i
= 0; i
< graph
->n_edge
; ++i
)
459 isl_map_free(graph
->edge
[i
].map
);
463 for (i
= 0; i
<= isl_edge_last
; ++i
)
464 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
465 isl_hash_table_free(ctx
, graph
->node_table
);
466 isl_basic_set_free(graph
->lp
);
469 /* Add a new node to the graph representing the given set.
471 static int extract_node(__isl_take isl_set
*set
, void *user
)
477 struct isl_sched_graph
*graph
= user
;
478 int *band
, *band_id
, *zero
;
480 ctx
= isl_set_get_ctx(set
);
481 dim
= isl_set_get_space(set
);
483 nvar
= isl_space_dim(dim
, isl_dim_set
);
484 nparam
= isl_space_dim(dim
, isl_dim_param
);
485 if (!ctx
->opt
->schedule_parametric
)
487 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
488 graph
->node
[graph
->n
].dim
= dim
;
489 graph
->node
[graph
->n
].nvar
= nvar
;
490 graph
->node
[graph
->n
].nparam
= nparam
;
491 graph
->node
[graph
->n
].sched
= sched
;
492 graph
->node
[graph
->n
].sched_map
= NULL
;
493 band
= isl_alloc_array(ctx
, int, graph
->n_edge
+ nvar
);
494 graph
->node
[graph
->n
].band
= band
;
495 band_id
= isl_calloc_array(ctx
, int, graph
->n_edge
+ nvar
);
496 graph
->node
[graph
->n
].band_id
= band_id
;
497 zero
= isl_calloc_array(ctx
, int, graph
->n_edge
+ nvar
);
498 graph
->node
[graph
->n
].zero
= zero
;
501 if (!sched
|| !band
|| !band_id
|| !zero
)
507 struct isl_extract_edge_data
{
508 enum isl_edge_type type
;
509 struct isl_sched_graph
*graph
;
512 /* Add a new edge to the graph based on the given map
513 * and add it to data->graph->edge_table[data->type].
514 * If a dependence relation of a given type happens to be identical
515 * to one of the dependence relations of a type that was added before,
516 * then we don't create a new edge, but instead mark the original edge
517 * as also representing a dependence of the current type.
519 static int extract_edge(__isl_take isl_map
*map
, void *user
)
521 isl_ctx
*ctx
= isl_map_get_ctx(map
);
522 struct isl_extract_edge_data
*data
= user
;
523 struct isl_sched_graph
*graph
= data
->graph
;
524 struct isl_sched_node
*src
, *dst
;
526 struct isl_sched_edge
*edge
;
529 dim
= isl_space_domain(isl_map_get_space(map
));
530 src
= graph_find_node(ctx
, graph
, dim
);
532 dim
= isl_space_range(isl_map_get_space(map
));
533 dst
= graph_find_node(ctx
, graph
, dim
);
541 graph
->edge
[graph
->n_edge
].src
= src
;
542 graph
->edge
[graph
->n_edge
].dst
= dst
;
543 graph
->edge
[graph
->n_edge
].map
= map
;
544 if (data
->type
== isl_edge_validity
) {
545 graph
->edge
[graph
->n_edge
].validity
= 1;
546 graph
->edge
[graph
->n_edge
].proximity
= 0;
548 if (data
->type
== isl_edge_proximity
) {
549 graph
->edge
[graph
->n_edge
].validity
= 0;
550 graph
->edge
[graph
->n_edge
].proximity
= 1;
554 edge
= graph_find_any_edge(graph
, src
, dst
);
556 return graph_edge_table_add(ctx
, graph
, data
->type
,
557 &graph
->edge
[graph
->n_edge
- 1]);
558 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
562 return graph_edge_table_add(ctx
, graph
, data
->type
,
563 &graph
->edge
[graph
->n_edge
- 1]);
566 edge
->validity
|= graph
->edge
[graph
->n_edge
].validity
;
567 edge
->proximity
|= graph
->edge
[graph
->n_edge
].proximity
;
570 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
573 /* Check whether there is a validity dependence from src to dst,
574 * forcing dst to follow src.
576 static int node_follows(struct isl_sched_graph
*graph
,
577 struct isl_sched_node
*dst
, struct isl_sched_node
*src
)
579 return graph_has_validity_edge(graph
, src
, dst
);
582 /* Perform Tarjan's algorithm for computing the strongly connected components
583 * in the dependence graph (only validity edges).
584 * If directed is not set, we consider the graph to be undirected and
585 * we effectively compute the (weakly) connected components.
587 static int detect_sccs_tarjan(struct isl_sched_graph
*g
, int i
, int directed
)
591 g
->node
[i
].index
= g
->index
;
592 g
->node
[i
].min_index
= g
->index
;
593 g
->node
[i
].on_stack
= 1;
595 g
->stack
[g
->sp
++] = i
;
597 for (j
= g
->n
- 1; j
>= 0; --j
) {
602 if (g
->node
[j
].index
>= 0 &&
603 (!g
->node
[j
].on_stack
||
604 g
->node
[j
].index
> g
->node
[i
].min_index
))
607 f
= node_follows(g
, &g
->node
[i
], &g
->node
[j
]);
610 if (!f
&& !directed
) {
611 f
= node_follows(g
, &g
->node
[j
], &g
->node
[i
]);
617 if (g
->node
[j
].index
< 0) {
618 detect_sccs_tarjan(g
, j
, directed
);
619 if (g
->node
[j
].min_index
< g
->node
[i
].min_index
)
620 g
->node
[i
].min_index
= g
->node
[j
].min_index
;
621 } else if (g
->node
[j
].index
< g
->node
[i
].min_index
)
622 g
->node
[i
].min_index
= g
->node
[j
].index
;
625 if (g
->node
[i
].index
!= g
->node
[i
].min_index
)
629 j
= g
->stack
[--g
->sp
];
630 g
->node
[j
].on_stack
= 0;
631 g
->node
[j
].scc
= g
->scc
;
638 static int detect_ccs(struct isl_sched_graph
*graph
, int directed
)
645 for (i
= graph
->n
- 1; i
>= 0; --i
)
646 graph
->node
[i
].index
= -1;
648 for (i
= graph
->n
- 1; i
>= 0; --i
) {
649 if (graph
->node
[i
].index
>= 0)
651 if (detect_sccs_tarjan(graph
, i
, directed
) < 0)
658 /* Apply Tarjan's algorithm to detect the strongly connected components
659 * in the dependence graph.
661 static int detect_sccs(struct isl_sched_graph
*graph
)
663 return detect_ccs(graph
, 1);
666 /* Apply Tarjan's algorithm to detect the (weakly) connected components
667 * in the dependence graph.
669 static int detect_wccs(struct isl_sched_graph
*graph
)
671 return detect_ccs(graph
, 0);
674 static int cmp_scc(const void *a
, const void *b
, void *data
)
676 struct isl_sched_graph
*graph
= data
;
680 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
683 /* Sort the elements of graph->sorted according to the corresponding SCCs.
685 static void sort_sccs(struct isl_sched_graph
*graph
)
687 isl_quicksort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
690 /* Given a dependence relation R from a node to itself,
691 * construct the set of coefficients of valid constraints for elements
692 * in that dependence relation.
693 * In particular, the result contains tuples of coefficients
694 * c_0, c_n, c_x such that
696 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
700 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
702 * We choose here to compute the dual of delta R.
703 * Alternatively, we could have computed the dual of R, resulting
704 * in a set of tuples c_0, c_n, c_x, c_y, and then
705 * plugged in (c_0, c_n, c_x, -c_x).
707 static __isl_give isl_basic_set
*intra_coefficients(
708 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
710 isl_ctx
*ctx
= isl_map_get_ctx(map
);
714 if (isl_hmap_map_basic_set_has(ctx
, graph
->intra_hmap
, map
))
715 return isl_hmap_map_basic_set_get(ctx
, graph
->intra_hmap
, map
);
717 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
718 coef
= isl_set_coefficients(delta
);
719 isl_hmap_map_basic_set_set(ctx
, graph
->intra_hmap
, map
,
720 isl_basic_set_copy(coef
));
725 /* Given a dependence relation R, * construct the set of coefficients
726 * of valid constraints for elements in that dependence relation.
727 * In particular, the result contains tuples of coefficients
728 * c_0, c_n, c_x, c_y such that
730 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
733 static __isl_give isl_basic_set
*inter_coefficients(
734 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
736 isl_ctx
*ctx
= isl_map_get_ctx(map
);
740 if (isl_hmap_map_basic_set_has(ctx
, graph
->inter_hmap
, map
))
741 return isl_hmap_map_basic_set_get(ctx
, graph
->inter_hmap
, map
);
743 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
744 coef
= isl_set_coefficients(set
);
745 isl_hmap_map_basic_set_set(ctx
, graph
->inter_hmap
, map
,
746 isl_basic_set_copy(coef
));
751 /* Add constraints to graph->lp that force validity for the given
752 * dependence from a node i to itself.
753 * That is, add constraints that enforce
755 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
756 * = c_i_x (y - x) >= 0
758 * for each (x,y) in R.
759 * We obtain general constraints on coefficients (c_0, c_n, c_x)
760 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
761 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
762 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
764 * Actually, we do not construct constraints for the c_i_x themselves,
765 * but for the coefficients of c_i_x written as a linear combination
766 * of the columns in node->cmap.
768 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
769 struct isl_sched_edge
*edge
)
772 isl_map
*map
= isl_map_copy(edge
->map
);
773 isl_ctx
*ctx
= isl_map_get_ctx(map
);
775 isl_dim_map
*dim_map
;
777 struct isl_sched_node
*node
= edge
->src
;
779 coef
= intra_coefficients(graph
, map
);
781 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
783 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
784 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
786 total
= isl_basic_set_total_dim(graph
->lp
);
787 dim_map
= isl_dim_map_alloc(ctx
, total
);
788 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
789 isl_space_dim(dim
, isl_dim_set
), 1,
791 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
792 isl_space_dim(dim
, isl_dim_set
), 1,
794 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
795 coef
->n_eq
, coef
->n_ineq
);
796 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
803 /* Add constraints to graph->lp that force validity for the given
804 * dependence from node i to node j.
805 * That is, add constraints that enforce
807 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
809 * for each (x,y) in R.
810 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
811 * of valid constraints for R and then plug in
812 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
813 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
814 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
815 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
817 * Actually, we do not construct constraints for the c_*_x themselves,
818 * but for the coefficients of c_*_x written as a linear combination
819 * of the columns in node->cmap.
821 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
822 struct isl_sched_edge
*edge
)
825 isl_map
*map
= isl_map_copy(edge
->map
);
826 isl_ctx
*ctx
= isl_map_get_ctx(map
);
828 isl_dim_map
*dim_map
;
830 struct isl_sched_node
*src
= edge
->src
;
831 struct isl_sched_node
*dst
= edge
->dst
;
833 coef
= inter_coefficients(graph
, map
);
835 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
837 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
838 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
839 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
840 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
841 isl_mat_copy(dst
->cmap
));
843 total
= isl_basic_set_total_dim(graph
->lp
);
844 dim_map
= isl_dim_map_alloc(ctx
, total
);
846 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
847 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
848 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
849 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
850 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
852 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
853 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
856 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
857 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
858 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
859 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
860 isl_space_dim(dim
, isl_dim_set
), 1,
862 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
863 isl_space_dim(dim
, isl_dim_set
), 1,
866 edge
->start
= graph
->lp
->n_ineq
;
867 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
868 coef
->n_eq
, coef
->n_ineq
);
869 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
872 edge
->end
= graph
->lp
->n_ineq
;
877 /* Add constraints to graph->lp that bound the dependence distance for the given
878 * dependence from a node i to itself.
879 * If s = 1, we add the constraint
881 * c_i_x (y - x) <= m_0 + m_n n
885 * -c_i_x (y - x) + m_0 + m_n n >= 0
887 * for each (x,y) in R.
888 * If s = -1, we add the constraint
890 * -c_i_x (y - x) <= m_0 + m_n n
894 * c_i_x (y - x) + m_0 + m_n n >= 0
896 * for each (x,y) in R.
897 * We obtain general constraints on coefficients (c_0, c_n, c_x)
898 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
899 * with each coefficient (except m_0) represented as a pair of non-negative
902 * Actually, we do not construct constraints for the c_i_x themselves,
903 * but for the coefficients of c_i_x written as a linear combination
904 * of the columns in node->cmap.
906 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
907 struct isl_sched_edge
*edge
, int s
)
911 isl_map
*map
= isl_map_copy(edge
->map
);
912 isl_ctx
*ctx
= isl_map_get_ctx(map
);
914 isl_dim_map
*dim_map
;
916 struct isl_sched_node
*node
= edge
->src
;
918 coef
= intra_coefficients(graph
, map
);
920 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
922 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
923 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
925 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
926 total
= isl_basic_set_total_dim(graph
->lp
);
927 dim_map
= isl_dim_map_alloc(ctx
, total
);
928 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
929 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
930 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
931 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
932 isl_space_dim(dim
, isl_dim_set
), 1,
934 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
935 isl_space_dim(dim
, isl_dim_set
), 1,
937 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
938 coef
->n_eq
, coef
->n_ineq
);
939 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
946 /* Add constraints to graph->lp that bound the dependence distance for the given
947 * dependence from node i to node j.
948 * If s = 1, we add the constraint
950 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
955 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
958 * for each (x,y) in R.
959 * If s = -1, we add the constraint
961 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
966 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
969 * for each (x,y) in R.
970 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
971 * of valid constraints for R and then plug in
972 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
974 * with each coefficient (except m_0, c_j_0 and c_i_0)
975 * represented as a pair of non-negative coefficients.
977 * Actually, we do not construct constraints for the c_*_x themselves,
978 * but for the coefficients of c_*_x written as a linear combination
979 * of the columns in node->cmap.
981 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
982 struct isl_sched_edge
*edge
, int s
)
986 isl_map
*map
= isl_map_copy(edge
->map
);
987 isl_ctx
*ctx
= isl_map_get_ctx(map
);
989 isl_dim_map
*dim_map
;
991 struct isl_sched_node
*src
= edge
->src
;
992 struct isl_sched_node
*dst
= edge
->dst
;
994 coef
= inter_coefficients(graph
, map
);
996 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
998 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
999 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1000 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1001 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1002 isl_mat_copy(dst
->cmap
));
1004 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1005 total
= isl_basic_set_total_dim(graph
->lp
);
1006 dim_map
= isl_dim_map_alloc(ctx
, total
);
1008 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1009 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1010 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1012 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1013 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1014 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1015 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1016 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1018 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1019 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1022 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1023 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1024 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1025 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1026 isl_space_dim(dim
, isl_dim_set
), 1,
1028 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1029 isl_space_dim(dim
, isl_dim_set
), 1,
1032 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1033 coef
->n_eq
, coef
->n_ineq
);
1034 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1036 isl_space_free(dim
);
1041 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1045 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1046 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1047 if (!edge
->validity
)
1049 if (edge
->src
!= edge
->dst
)
1051 if (add_intra_validity_constraints(graph
, edge
) < 0)
1055 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1056 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1057 if (!edge
->validity
)
1059 if (edge
->src
== edge
->dst
)
1061 if (add_inter_validity_constraints(graph
, edge
) < 0)
1068 /* Add constraints to graph->lp that bound the dependence distance
1069 * for all dependence relations.
1070 * If a given proximity dependence is identical to a validity
1071 * dependence, then the dependence distance is already bounded
1072 * from below (by zero), so we only need to bound the distance
1074 * Otherwise, we need to bound the distance both from above and from below.
1076 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1080 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1081 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1082 if (!edge
->proximity
)
1084 if (edge
->src
== edge
->dst
&&
1085 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
1087 if (edge
->src
!= edge
->dst
&&
1088 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
1092 if (edge
->src
== edge
->dst
&&
1093 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
1095 if (edge
->src
!= edge
->dst
&&
1096 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1103 /* Compute a basis for the rows in the linear part of the schedule
1104 * and extend this basis to a full basis. The remaining rows
1105 * can then be used to force linear independence from the rows
1108 * In particular, given the schedule rows S, we compute
1112 * with H the Hermite normal form of S. That is, all but the
1113 * first rank columns of Q are zero and so each row in S is
1114 * a linear combination of the first rank rows of Q.
1115 * The matrix Q is then transposed because we will write the
1116 * coefficients of the next schedule row as a column vector s
1117 * and express this s as a linear combination s = Q c of the
1120 static int node_update_cmap(struct isl_sched_node
*node
)
1123 int n_row
= isl_mat_rows(node
->sched
);
1125 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1126 1 + node
->nparam
, node
->nvar
);
1128 H
= isl_mat_left_hermite(H
, 0, NULL
, &Q
);
1129 isl_mat_free(node
->cmap
);
1130 node
->cmap
= isl_mat_transpose(Q
);
1131 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1134 if (!node
->cmap
|| node
->rank
< 0)
1139 /* Count the number of equality and inequality constraints
1140 * that will be added for the given map.
1141 * If carry is set, then we are counting the number of (validity)
1142 * constraints that will be added in setup_carry_lp and we count
1143 * each edge exactly once. Otherwise, we count as follows
1144 * validity -> 1 (>= 0)
1145 * validity+proximity -> 2 (>= 0 and upper bound)
1146 * proximity -> 2 (lower and upper bound)
1148 static int count_map_constraints(struct isl_sched_graph
*graph
,
1149 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1150 int *n_eq
, int *n_ineq
, int carry
)
1152 isl_basic_set
*coef
;
1153 int f
= carry
? 1 : edge
->proximity
? 2 : 1;
1155 if (carry
&& !edge
->validity
) {
1160 if (edge
->src
== edge
->dst
)
1161 coef
= intra_coefficients(graph
, map
);
1163 coef
= inter_coefficients(graph
, map
);
1166 *n_eq
+= f
* coef
->n_eq
;
1167 *n_ineq
+= f
* coef
->n_ineq
;
1168 isl_basic_set_free(coef
);
1173 /* Count the number of equality and inequality constraints
1174 * that will be added to the main lp problem.
1175 * We count as follows
1176 * validity -> 1 (>= 0)
1177 * validity+proximity -> 2 (>= 0 and upper bound)
1178 * proximity -> 2 (lower and upper bound)
1180 static int count_constraints(struct isl_sched_graph
*graph
,
1181 int *n_eq
, int *n_ineq
)
1185 *n_eq
= *n_ineq
= 0;
1186 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1187 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1188 isl_map
*map
= isl_map_copy(edge
->map
);
1190 if (count_map_constraints(graph
, edge
, map
,
1191 n_eq
, n_ineq
, 0) < 0)
1198 /* Add constraints that bound the values of the variable and parameter
1199 * coefficients of the schedule.
1201 * The maximal value of the coefficients is defined by the option
1202 * 'schedule_max_coefficient'.
1204 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1205 struct isl_sched_graph
*graph
)
1208 int max_coefficient
;
1211 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1213 if (max_coefficient
== -1)
1216 total
= isl_basic_set_total_dim(graph
->lp
);
1218 for (i
= 0; i
< graph
->n
; ++i
) {
1219 struct isl_sched_node
*node
= &graph
->node
[i
];
1220 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1222 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1225 dim
= 1 + node
->start
+ 1 + j
;
1226 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1227 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1228 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1235 /* Construct an ILP problem for finding schedule coefficients
1236 * that result in non-negative, but small dependence distances
1237 * over all dependences.
1238 * In particular, the dependence distances over proximity edges
1239 * are bounded by m_0 + m_n n and we compute schedule coefficients
1240 * with small values (preferably zero) of m_n and m_0.
1242 * All variables of the ILP are non-negative. The actual coefficients
1243 * may be negative, so each coefficient is represented as the difference
1244 * of two non-negative variables. The negative part always appears
1245 * immediately before the positive part.
1246 * Other than that, the variables have the following order
1248 * - sum of positive and negative parts of m_n coefficients
1250 * - sum of positive and negative parts of all c_n coefficients
1251 * (unconstrained when computing non-parametric schedules)
1252 * - sum of positive and negative parts of all c_x coefficients
1253 * - positive and negative parts of m_n coefficients
1256 * - positive and negative parts of c_i_n (if parametric)
1257 * - positive and negative parts of c_i_x
1259 * The c_i_x are not represented directly, but through the columns of
1260 * node->cmap. That is, the computed values are for variable t_i_x
1261 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1263 * The constraints are those from the edges plus two or three equalities
1264 * to express the sums.
1266 * If force_zero is set, then we add equalities to ensure that
1267 * the sum of the m_n coefficients and m_0 are both zero.
1269 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1280 int max_constant_term
;
1281 int max_coefficient
;
1283 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1284 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1286 parametric
= ctx
->opt
->schedule_parametric
;
1287 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1289 total
= param_pos
+ 2 * nparam
;
1290 for (i
= 0; i
< graph
->n
; ++i
) {
1291 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1292 if (node_update_cmap(node
) < 0)
1294 node
->start
= total
;
1295 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1298 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1301 dim
= isl_space_set_alloc(ctx
, 0, total
);
1302 isl_basic_set_free(graph
->lp
);
1303 n_eq
+= 2 + parametric
+ force_zero
;
1304 if (max_constant_term
!= -1)
1306 if (max_coefficient
!= -1)
1307 for (i
= 0; i
< graph
->n
; ++i
)
1308 n_ineq
+= 2 * graph
->node
[i
].nparam
+
1309 2 * graph
->node
[i
].nvar
;
1311 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1313 k
= isl_basic_set_alloc_equality(graph
->lp
);
1316 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1318 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1319 for (i
= 0; i
< 2 * nparam
; ++i
)
1320 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1323 k
= isl_basic_set_alloc_equality(graph
->lp
);
1326 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1327 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1331 k
= isl_basic_set_alloc_equality(graph
->lp
);
1334 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1335 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1336 for (i
= 0; i
< graph
->n
; ++i
) {
1337 int pos
= 1 + graph
->node
[i
].start
+ 1;
1339 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1340 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1344 k
= isl_basic_set_alloc_equality(graph
->lp
);
1347 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1348 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1349 for (i
= 0; i
< graph
->n
; ++i
) {
1350 struct isl_sched_node
*node
= &graph
->node
[i
];
1351 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1353 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1354 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1357 if (max_constant_term
!= -1)
1358 for (i
= 0; i
< graph
->n
; ++i
) {
1359 struct isl_sched_node
*node
= &graph
->node
[i
];
1360 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1363 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1364 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1365 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1368 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1370 if (add_all_validity_constraints(graph
) < 0)
1372 if (add_all_proximity_constraints(graph
) < 0)
1378 /* Analyze the conflicting constraint found by
1379 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1380 * constraint of one of the edges between distinct nodes, living, moreover
1381 * in distinct SCCs, then record the source and sink SCC as this may
1382 * be a good place to cut between SCCs.
1384 static int check_conflict(int con
, void *user
)
1387 struct isl_sched_graph
*graph
= user
;
1389 if (graph
->src_scc
>= 0)
1392 con
-= graph
->lp
->n_eq
;
1394 if (con
>= graph
->lp
->n_ineq
)
1397 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1398 if (!graph
->edge
[i
].validity
)
1400 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1402 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1404 if (graph
->edge
[i
].start
> con
)
1406 if (graph
->edge
[i
].end
<= con
)
1408 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1409 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1415 /* Check whether the next schedule row of the given node needs to be
1416 * non-trivial. Lower-dimensional domains may have some trivial rows,
1417 * but as soon as the number of remaining required non-trivial rows
1418 * is as large as the number or remaining rows to be computed,
1419 * all remaining rows need to be non-trivial.
1421 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1423 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1426 /* Solve the ILP problem constructed in setup_lp.
1427 * For each node such that all the remaining rows of its schedule
1428 * need to be non-trivial, we construct a non-triviality region.
1429 * This region imposes that the next row is independent of previous rows.
1430 * In particular the coefficients c_i_x are represented by t_i_x
1431 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1432 * its first columns span the rows of the previously computed part
1433 * of the schedule. The non-triviality region enforces that at least
1434 * one of the remaining components of t_i_x is non-zero, i.e.,
1435 * that the new schedule row depends on at least one of the remaining
1438 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1444 for (i
= 0; i
< graph
->n
; ++i
) {
1445 struct isl_sched_node
*node
= &graph
->node
[i
];
1446 int skip
= node
->rank
;
1447 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1448 if (needs_row(graph
, node
))
1449 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1451 graph
->region
[i
].len
= 0;
1453 lp
= isl_basic_set_copy(graph
->lp
);
1454 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1455 graph
->region
, &check_conflict
, graph
);
1459 /* Update the schedules of all nodes based on the given solution
1460 * of the LP problem.
1461 * The new row is added to the current band.
1462 * All possibly negative coefficients are encoded as a difference
1463 * of two non-negative variables, so we need to perform the subtraction
1464 * here. Moreover, if use_cmap is set, then the solution does
1465 * not refer to the actual coefficients c_i_x, but instead to variables
1466 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1467 * In this case, we then also need to perform this multiplication
1468 * to obtain the values of c_i_x.
1470 * If check_zero is set, then the first two coordinates of sol are
1471 * assumed to correspond to the dependence distance. If these two
1472 * coordinates are zero, then the corresponding scheduling dimension
1473 * is marked as being zero distance.
1475 static int update_schedule(struct isl_sched_graph
*graph
,
1476 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1480 isl_vec
*csol
= NULL
;
1485 isl_die(sol
->ctx
, isl_error_internal
,
1486 "no solution found", goto error
);
1489 zero
= isl_int_is_zero(sol
->el
[1]) &&
1490 isl_int_is_zero(sol
->el
[2]);
1492 for (i
= 0; i
< graph
->n
; ++i
) {
1493 struct isl_sched_node
*node
= &graph
->node
[i
];
1494 int pos
= node
->start
;
1495 int row
= isl_mat_rows(node
->sched
);
1498 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1502 isl_map_free(node
->sched_map
);
1503 node
->sched_map
= NULL
;
1504 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1507 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1509 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1510 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1511 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1512 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1513 for (j
= 0; j
< node
->nparam
; ++j
)
1514 node
->sched
= isl_mat_set_element(node
->sched
,
1515 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1516 for (j
= 0; j
< node
->nvar
; ++j
)
1517 isl_int_set(csol
->el
[j
],
1518 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1520 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1524 for (j
= 0; j
< node
->nvar
; ++j
)
1525 node
->sched
= isl_mat_set_element(node
->sched
,
1526 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1527 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1528 node
->zero
[graph
->n_total_row
] = zero
;
1534 graph
->n_total_row
++;
1543 /* Convert node->sched into a map and return this map.
1544 * We simply add equality constraints that express each output variable
1545 * as the affine combination of parameters and input variables specified
1546 * by the schedule matrix.
1548 * The result is cached in node->sched_map, which needs to be released
1549 * whenever node->sched is updated.
1551 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1555 isl_local_space
*ls
;
1556 isl_basic_map
*bmap
;
1561 if (node
->sched_map
)
1562 return isl_map_copy(node
->sched_map
);
1564 nrow
= isl_mat_rows(node
->sched
);
1565 ncol
= isl_mat_cols(node
->sched
) - 1;
1566 dim
= isl_space_from_domain(isl_space_copy(node
->dim
));
1567 dim
= isl_space_add_dims(dim
, isl_dim_out
, nrow
);
1568 bmap
= isl_basic_map_universe(isl_space_copy(dim
));
1569 ls
= isl_local_space_from_space(dim
);
1573 for (i
= 0; i
< nrow
; ++i
) {
1574 c
= isl_equality_alloc(isl_local_space_copy(ls
));
1575 isl_constraint_set_coefficient_si(c
, isl_dim_out
, i
, -1);
1576 isl_mat_get_element(node
->sched
, i
, 0, &v
);
1577 isl_constraint_set_constant(c
, v
);
1578 for (j
= 0; j
< node
->nparam
; ++j
) {
1579 isl_mat_get_element(node
->sched
, i
, 1 + j
, &v
);
1580 isl_constraint_set_coefficient(c
, isl_dim_param
, j
, v
);
1582 for (j
= 0; j
< node
->nvar
; ++j
) {
1583 isl_mat_get_element(node
->sched
,
1584 i
, 1 + node
->nparam
+ j
, &v
);
1585 isl_constraint_set_coefficient(c
, isl_dim_in
, j
, v
);
1587 bmap
= isl_basic_map_add_constraint(bmap
, c
);
1592 isl_local_space_free(ls
);
1594 node
->sched_map
= isl_map_from_basic_map(bmap
);
1595 return isl_map_copy(node
->sched_map
);
1598 /* Update the given dependence relation based on the current schedule.
1599 * That is, intersect the dependence relation with a map expressing
1600 * that source and sink are executed within the same iteration of
1601 * the current schedule.
1602 * This is not the most efficient way, but this shouldn't be a critical
1605 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1606 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1608 isl_map
*src_sched
, *dst_sched
, *id
;
1610 src_sched
= node_extract_schedule(src
);
1611 dst_sched
= node_extract_schedule(dst
);
1612 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1613 return isl_map_intersect(map
, id
);
1616 /* Update the dependence relations of all edges based on the current schedule.
1617 * If a dependence is carried completely by the current schedule, then
1618 * it is removed from the edge_tables. It is kept in the list of edges
1619 * as otherwise all edge_tables would have to be recomputed.
1621 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1625 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1626 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1627 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1631 if (isl_map_plain_is_empty(edge
->map
))
1632 graph_remove_edge(graph
, edge
);
1638 static void next_band(struct isl_sched_graph
*graph
)
1640 graph
->band_start
= graph
->n_total_row
;
1644 /* Topologically sort statements mapped to the same schedule iteration
1645 * and add a row to the schedule corresponding to this order.
1647 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1654 if (update_edges(ctx
, graph
) < 0)
1657 if (graph
->n_edge
== 0)
1660 if (detect_sccs(graph
) < 0)
1663 for (i
= 0; i
< graph
->n
; ++i
) {
1664 struct isl_sched_node
*node
= &graph
->node
[i
];
1665 int row
= isl_mat_rows(node
->sched
);
1666 int cols
= isl_mat_cols(node
->sched
);
1668 isl_map_free(node
->sched_map
);
1669 node
->sched_map
= NULL
;
1670 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1673 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1675 for (j
= 1; j
< cols
; ++j
)
1676 node
->sched
= isl_mat_set_element_si(node
->sched
,
1678 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1681 graph
->n_total_row
++;
1687 /* Construct an isl_schedule based on the computed schedule stored
1688 * in graph and with parameters specified by dim.
1690 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1691 __isl_take isl_space
*dim
)
1695 isl_schedule
*sched
= NULL
;
1700 ctx
= isl_space_get_ctx(dim
);
1701 sched
= isl_calloc(ctx
, struct isl_schedule
,
1702 sizeof(struct isl_schedule
) +
1703 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1708 sched
->n
= graph
->n
;
1709 sched
->n_band
= graph
->n_band
;
1710 sched
->n_total_row
= graph
->n_total_row
;
1712 for (i
= 0; i
< sched
->n
; ++i
) {
1714 int *band_end
, *band_id
, *zero
;
1716 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1717 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1718 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1719 sched
->node
[i
].sched
= node_extract_schedule(&graph
->node
[i
]);
1720 sched
->node
[i
].band_end
= band_end
;
1721 sched
->node
[i
].band_id
= band_id
;
1722 sched
->node
[i
].zero
= zero
;
1723 if (!band_end
|| !band_id
|| !zero
)
1726 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1727 zero
[r
] = graph
->node
[i
].zero
[r
];
1728 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1729 if (graph
->node
[i
].band
[r
] == b
)
1732 if (graph
->node
[i
].band
[r
] == -1)
1735 if (r
== graph
->n_total_row
)
1737 sched
->node
[i
].n_band
= b
;
1738 for (--b
; b
>= 0; --b
)
1739 band_id
[b
] = graph
->node
[i
].band_id
[b
];
1746 isl_space_free(dim
);
1747 isl_schedule_free(sched
);
1751 /* Copy nodes that satisfy node_pred from the src dependence graph
1752 * to the dst dependence graph.
1754 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
1755 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1760 for (i
= 0; i
< src
->n
; ++i
) {
1761 if (!node_pred(&src
->node
[i
], data
))
1763 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
1764 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
1765 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
1766 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
1767 dst
->node
[dst
->n
].sched_map
=
1768 isl_map_copy(src
->node
[i
].sched_map
);
1769 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
1770 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
1771 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
1778 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1779 * to the dst dependence graph.
1780 * If the source or destination node of the edge is not in the destination
1781 * graph, then it must be a backward proximity edge and it should simply
1784 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
1785 struct isl_sched_graph
*src
,
1786 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
1792 for (i
= 0; i
< src
->n_edge
; ++i
) {
1793 struct isl_sched_edge
*edge
= &src
->edge
[i
];
1795 struct isl_sched_node
*dst_src
, *dst_dst
;
1797 if (!edge_pred(edge
, data
))
1800 if (isl_map_plain_is_empty(edge
->map
))
1803 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
1804 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
1805 if (!dst_src
|| !dst_dst
) {
1807 isl_die(ctx
, isl_error_internal
,
1808 "backward validity edge", return -1);
1812 map
= isl_map_copy(edge
->map
);
1814 dst
->edge
[dst
->n_edge
].src
= dst_src
;
1815 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
1816 dst
->edge
[dst
->n_edge
].map
= map
;
1817 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
1818 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
1821 for (t
= 0; t
<= isl_edge_last
; ++t
) {
1823 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
1825 if (graph_edge_table_add(ctx
, dst
, t
,
1826 &dst
->edge
[dst
->n_edge
- 1]) < 0)
1834 /* Given a "src" dependence graph that contains the nodes from "dst"
1835 * that satisfy node_pred, copy the schedule computed in "src"
1836 * for those nodes back to "dst".
1838 static int copy_schedule(struct isl_sched_graph
*dst
,
1839 struct isl_sched_graph
*src
,
1840 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1845 for (i
= 0; i
< dst
->n
; ++i
) {
1846 if (!node_pred(&dst
->node
[i
], data
))
1848 isl_mat_free(dst
->node
[i
].sched
);
1849 isl_map_free(dst
->node
[i
].sched_map
);
1850 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
1851 dst
->node
[i
].sched_map
=
1852 isl_map_copy(src
->node
[src
->n
].sched_map
);
1856 dst
->n_total_row
= src
->n_total_row
;
1857 dst
->n_band
= src
->n_band
;
1862 /* Compute the maximal number of variables over all nodes.
1863 * This is the maximal number of linearly independent schedule
1864 * rows that we need to compute.
1865 * Just in case we end up in a part of the dependence graph
1866 * with only lower-dimensional domains, we make sure we will
1867 * compute the required amount of extra linearly independent rows.
1869 static int compute_maxvar(struct isl_sched_graph
*graph
)
1874 for (i
= 0; i
< graph
->n
; ++i
) {
1875 struct isl_sched_node
*node
= &graph
->node
[i
];
1878 if (node_update_cmap(node
) < 0)
1880 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
1881 if (nvar
> graph
->maxvar
)
1882 graph
->maxvar
= nvar
;
1888 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1889 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1891 /* Compute a schedule for a subgraph of "graph". In particular, for
1892 * the graph composed of nodes that satisfy node_pred and edges that
1893 * that satisfy edge_pred. The caller should precompute the number
1894 * of nodes and edges that satisfy these predicates and pass them along
1895 * as "n" and "n_edge".
1896 * If the subgraph is known to consist of a single component, then wcc should
1897 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1898 * Otherwise, we call compute_schedule, which will check whether the subgraph
1901 static int compute_sub_schedule(isl_ctx
*ctx
,
1902 struct isl_sched_graph
*graph
, int n
, int n_edge
,
1903 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
1904 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
1907 struct isl_sched_graph split
= { 0 };
1910 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
1912 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
1914 if (graph_init_table(ctx
, &split
) < 0)
1916 for (t
= 0; t
<= isl_edge_last
; ++t
)
1917 split
.max_edge
[t
] = graph
->max_edge
[t
];
1918 if (graph_init_edge_tables(ctx
, &split
) < 0)
1920 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
1922 split
.n_row
= graph
->n_row
;
1923 split
.n_total_row
= graph
->n_total_row
;
1924 split
.n_band
= graph
->n_band
;
1925 split
.band_start
= graph
->band_start
;
1927 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
1929 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
1932 copy_schedule(graph
, &split
, node_pred
, data
);
1934 graph_free(ctx
, &split
);
1937 graph_free(ctx
, &split
);
1941 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
1943 return node
->scc
== scc
;
1946 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
1948 return node
->scc
<= scc
;
1951 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
1953 return node
->scc
>= scc
;
1956 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
1958 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
1961 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
1963 return edge
->dst
->scc
<= scc
;
1966 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
1968 return edge
->src
->scc
>= scc
;
1971 /* Pad the schedules of all nodes with zero rows such that in the end
1972 * they all have graph->n_total_row rows.
1973 * The extra rows don't belong to any band, so they get assigned band number -1.
1975 static int pad_schedule(struct isl_sched_graph
*graph
)
1979 for (i
= 0; i
< graph
->n
; ++i
) {
1980 struct isl_sched_node
*node
= &graph
->node
[i
];
1981 int row
= isl_mat_rows(node
->sched
);
1982 if (graph
->n_total_row
> row
) {
1983 isl_map_free(node
->sched_map
);
1984 node
->sched_map
= NULL
;
1986 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
1987 graph
->n_total_row
- row
);
1990 for (j
= row
; j
< graph
->n_total_row
; ++j
)
1997 /* Split the current graph into two parts and compute a schedule for each
1998 * part individually. In particular, one part consists of all SCCs up
1999 * to and including graph->src_scc, while the other part contains the other
2002 * The split is enforced in the schedule by constant rows with two different
2003 * values (0 and 1). These constant rows replace the previously computed rows
2004 * in the current band.
2005 * It would be possible to reuse them as the first rows in the next
2006 * band, but recomputing them may result in better rows as we are looking
2007 * at a smaller part of the dependence graph.
2008 * compute_split_schedule is only called when no zero-distance schedule row
2009 * could be found on the entire graph, so we wark the splitting row as
2010 * non zero-distance.
2012 * The band_id of the second group is set to n, where n is the number
2013 * of nodes in the first group. This ensures that the band_ids over
2014 * the two groups remain disjoint, even if either or both of the two
2015 * groups contain independent components.
2017 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2019 int i
, j
, n
, e1
, e2
;
2020 int n_total_row
, orig_total_row
;
2021 int n_band
, orig_band
;
2024 drop
= graph
->n_total_row
- graph
->band_start
;
2025 graph
->n_total_row
-= drop
;
2026 graph
->n_row
-= drop
;
2029 for (i
= 0; i
< graph
->n
; ++i
) {
2030 struct isl_sched_node
*node
= &graph
->node
[i
];
2031 int row
= isl_mat_rows(node
->sched
) - drop
;
2032 int cols
= isl_mat_cols(node
->sched
);
2033 int before
= node
->scc
<= graph
->src_scc
;
2038 isl_map_free(node
->sched_map
);
2039 node
->sched_map
= NULL
;
2040 node
->sched
= isl_mat_drop_rows(node
->sched
,
2041 graph
->band_start
, drop
);
2042 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2045 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2047 for (j
= 1; j
< cols
; ++j
)
2048 node
->sched
= isl_mat_set_element_si(node
->sched
,
2050 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2051 node
->zero
[graph
->n_total_row
] = 0;
2055 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2056 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2058 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2062 graph
->n_total_row
++;
2065 for (i
= 0; i
< graph
->n
; ++i
) {
2066 struct isl_sched_node
*node
= &graph
->node
[i
];
2067 if (node
->scc
> graph
->src_scc
)
2068 node
->band_id
[graph
->n_band
] = n
;
2071 orig_total_row
= graph
->n_total_row
;
2072 orig_band
= graph
->n_band
;
2073 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2074 &node_scc_at_most
, &edge_dst_scc_at_most
,
2075 graph
->src_scc
, 0) < 0)
2077 n_total_row
= graph
->n_total_row
;
2078 graph
->n_total_row
= orig_total_row
;
2079 n_band
= graph
->n_band
;
2080 graph
->n_band
= orig_band
;
2081 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2082 &node_scc_at_least
, &edge_src_scc_at_least
,
2083 graph
->src_scc
+ 1, 0) < 0)
2085 if (n_total_row
> graph
->n_total_row
)
2086 graph
->n_total_row
= n_total_row
;
2087 if (n_band
> graph
->n_band
)
2088 graph
->n_band
= n_band
;
2090 return pad_schedule(graph
);
2093 /* Compute the next band of the schedule after updating the dependence
2094 * relations based on the the current schedule.
2096 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2098 if (update_edges(ctx
, graph
) < 0)
2102 return compute_schedule(ctx
, graph
);
2105 /* Add constraints to graph->lp that force the dependence "map" (which
2106 * is part of the dependence relation of "edge")
2107 * to be respected and attempt to carry it, where the edge is one from
2108 * a node j to itself. "pos" is the sequence number of the given map.
2109 * That is, add constraints that enforce
2111 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2112 * = c_j_x (y - x) >= e_i
2114 * for each (x,y) in R.
2115 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2116 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2117 * with each coefficient in c_j_x represented as a pair of non-negative
2120 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2121 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2124 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2126 isl_dim_map
*dim_map
;
2127 isl_basic_set
*coef
;
2128 struct isl_sched_node
*node
= edge
->src
;
2130 coef
= intra_coefficients(graph
, map
);
2132 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2134 total
= isl_basic_set_total_dim(graph
->lp
);
2135 dim_map
= isl_dim_map_alloc(ctx
, total
);
2136 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2137 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2138 isl_space_dim(dim
, isl_dim_set
), 1,
2140 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2141 isl_space_dim(dim
, isl_dim_set
), 1,
2143 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2144 coef
->n_eq
, coef
->n_ineq
);
2145 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2147 isl_space_free(dim
);
2152 /* Add constraints to graph->lp that force the dependence "map" (which
2153 * is part of the dependence relation of "edge")
2154 * to be respected and attempt to carry it, where the edge is one from
2155 * node j to node k. "pos" is the sequence number of the given map.
2156 * That is, add constraints that enforce
2158 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2160 * for each (x,y) in R.
2161 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2162 * of valid constraints for R and then plug in
2163 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2164 * with each coefficient (except e_i, c_k_0 and c_j_0)
2165 * represented as a pair of non-negative coefficients.
2167 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2168 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2171 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2173 isl_dim_map
*dim_map
;
2174 isl_basic_set
*coef
;
2175 struct isl_sched_node
*src
= edge
->src
;
2176 struct isl_sched_node
*dst
= edge
->dst
;
2178 coef
= inter_coefficients(graph
, map
);
2180 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2182 total
= isl_basic_set_total_dim(graph
->lp
);
2183 dim_map
= isl_dim_map_alloc(ctx
, total
);
2185 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2187 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2188 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2189 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2190 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2191 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2193 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2194 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2197 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2198 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2199 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2200 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2201 isl_space_dim(dim
, isl_dim_set
), 1,
2203 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2204 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 all validity dependences
2217 * to be respected and attempt to carry them.
2219 static int add_all_constraints(struct isl_sched_graph
*graph
)
2225 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2226 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2228 if (!edge
->validity
)
2231 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2232 isl_basic_map
*bmap
;
2235 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2236 map
= isl_map_from_basic_map(bmap
);
2238 if (edge
->src
== edge
->dst
&&
2239 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2241 if (edge
->src
!= edge
->dst
&&
2242 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2251 /* Count the number of equality and inequality constraints
2252 * that will be added to the carry_lp problem.
2253 * We count each edge exactly once.
2255 static int count_all_constraints(struct isl_sched_graph
*graph
,
2256 int *n_eq
, int *n_ineq
)
2260 *n_eq
= *n_ineq
= 0;
2261 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2262 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2263 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2264 isl_basic_map
*bmap
;
2267 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2268 map
= isl_map_from_basic_map(bmap
);
2270 if (count_map_constraints(graph
, edge
, map
,
2271 n_eq
, n_ineq
, 1) < 0)
2279 /* Construct an LP problem for finding schedule coefficients
2280 * such that the schedule carries as many dependences as possible.
2281 * In particular, for each dependence i, we bound the dependence distance
2282 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2283 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2284 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2285 * Note that if the dependence relation is a union of basic maps,
2286 * then we have to consider each basic map individually as it may only
2287 * be possible to carry the dependences expressed by some of those
2288 * basic maps and not all off them.
2289 * Below, we consider each of those basic maps as a separate "edge".
2291 * All variables of the LP are non-negative. The actual coefficients
2292 * may be negative, so each coefficient is represented as the difference
2293 * of two non-negative variables. The negative part always appears
2294 * immediately before the positive part.
2295 * Other than that, the variables have the following order
2297 * - sum of (1 - e_i) over all edges
2298 * - sum of positive and negative parts of all c_n coefficients
2299 * (unconstrained when computing non-parametric schedules)
2300 * - sum of positive and negative parts of all c_x coefficients
2305 * - positive and negative parts of c_i_n (if parametric)
2306 * - positive and negative parts of c_i_x
2308 * The constraints are those from the (validity) edges plus three equalities
2309 * to express the sums and n_edge inequalities to express e_i <= 1.
2311 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2321 for (i
= 0; i
< graph
->n_edge
; ++i
)
2322 n_edge
+= graph
->edge
[i
].map
->n
;
2325 for (i
= 0; i
< graph
->n
; ++i
) {
2326 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2327 node
->start
= total
;
2328 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2331 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2334 dim
= isl_space_set_alloc(ctx
, 0, total
);
2335 isl_basic_set_free(graph
->lp
);
2338 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2339 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2341 k
= isl_basic_set_alloc_equality(graph
->lp
);
2344 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2345 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2346 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2347 for (i
= 0; i
< n_edge
; ++i
)
2348 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2350 k
= isl_basic_set_alloc_equality(graph
->lp
);
2353 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2354 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2355 for (i
= 0; i
< graph
->n
; ++i
) {
2356 int pos
= 1 + graph
->node
[i
].start
+ 1;
2358 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2359 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2362 k
= isl_basic_set_alloc_equality(graph
->lp
);
2365 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2366 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2367 for (i
= 0; i
< graph
->n
; ++i
) {
2368 struct isl_sched_node
*node
= &graph
->node
[i
];
2369 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2371 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2372 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2375 for (i
= 0; i
< n_edge
; ++i
) {
2376 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2379 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2380 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2381 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2384 if (add_all_constraints(graph
) < 0)
2390 /* If the schedule_split_scaled option is set and if the linear
2391 * parts of the scheduling rows for all nodes in the graphs have
2392 * non-trivial common divisor, then split off the constant term
2393 * from the linear part.
2394 * The constant term is then placed in a separate band and
2395 * the linear part is reduced.
2397 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2403 if (!ctx
->opt
->schedule_split_scaled
)
2409 isl_int_init(gcd_i
);
2411 isl_int_set_si(gcd
, 0);
2413 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2415 for (i
= 0; i
< graph
->n
; ++i
) {
2416 struct isl_sched_node
*node
= &graph
->node
[i
];
2417 int cols
= isl_mat_cols(node
->sched
);
2419 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2420 isl_int_gcd(gcd
, gcd
, gcd_i
);
2423 isl_int_clear(gcd_i
);
2425 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2432 for (i
= 0; i
< graph
->n
; ++i
) {
2433 struct isl_sched_node
*node
= &graph
->node
[i
];
2435 isl_map_free(node
->sched_map
);
2436 node
->sched_map
= NULL
;
2437 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2440 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2441 node
->sched
->row
[row
][0], gcd
);
2442 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2443 node
->sched
->row
[row
][0], gcd
);
2444 isl_int_mul(node
->sched
->row
[row
][0],
2445 node
->sched
->row
[row
][0], gcd
);
2446 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2449 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2452 graph
->n_total_row
++;
2461 /* Construct a schedule row for each node such that as many dependences
2462 * as possible are carried and then continue with the next band.
2464 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2472 for (i
= 0; i
< graph
->n_edge
; ++i
)
2473 n_edge
+= graph
->edge
[i
].map
->n
;
2475 if (setup_carry_lp(ctx
, graph
) < 0)
2478 lp
= isl_basic_set_copy(graph
->lp
);
2479 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2483 if (sol
->size
== 0) {
2485 isl_die(ctx
, isl_error_internal
,
2486 "error in schedule construction", return -1);
2489 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2491 isl_die(ctx
, isl_error_unknown
,
2492 "unable to carry dependences", return -1);
2495 if (update_schedule(graph
, sol
, 0, 0) < 0)
2498 if (split_scaled(ctx
, graph
) < 0)
2501 return compute_next_band(ctx
, graph
);
2504 /* Are there any (non-empty) validity edges in the graph?
2506 static int has_validity_edges(struct isl_sched_graph
*graph
)
2510 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2513 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
2518 if (graph
->edge
[i
].validity
)
2525 /* Should we apply a Feautrier step?
2526 * That is, did the user request the Feautrier algorithm and are
2527 * there any validity dependences (left)?
2529 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2531 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2534 return has_validity_edges(graph
);
2537 /* Compute a schedule for a connected dependence graph using Feautrier's
2538 * multi-dimensional scheduling algorithm.
2539 * The original algorithm is described in [1].
2540 * The main idea is to minimize the number of scheduling dimensions, by
2541 * trying to satisfy as many dependences as possible per scheduling dimension.
2543 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2544 * Problem, Part II: Multi-Dimensional Time.
2545 * In Intl. Journal of Parallel Programming, 1992.
2547 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2548 struct isl_sched_graph
*graph
)
2550 return carry_dependences(ctx
, graph
);
2553 /* Compute a schedule for a connected dependence graph.
2554 * We try to find a sequence of as many schedule rows as possible that result
2555 * in non-negative dependence distances (independent of the previous rows
2556 * in the sequence, i.e., such that the sequence is tilable).
2557 * If we can't find any more rows we either
2558 * - split between SCCs and start over (assuming we found an interesting
2559 * pair of SCCs between which to split)
2560 * - continue with the next band (assuming the current band has at least
2562 * - try to carry as many dependences as possible and continue with the next
2565 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2566 * as many validity dependences as possible. When all validity dependences
2567 * are satisfied we extend the schedule to a full-dimensional schedule.
2569 * If we manage to complete the schedule, we finish off by topologically
2570 * sorting the statements based on the remaining dependences.
2572 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2573 * outermost dimension in the current band to be zero distance. If this
2574 * turns out to be impossible, we fall back on the general scheme above
2575 * and try to carry as many dependences as possible.
2577 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2581 if (detect_sccs(graph
) < 0)
2585 if (compute_maxvar(graph
) < 0)
2588 if (need_feautrier_step(ctx
, graph
))
2589 return compute_schedule_wcc_feautrier(ctx
, graph
);
2591 if (ctx
->opt
->schedule_outer_zero_distance
)
2594 while (graph
->n_row
< graph
->maxvar
) {
2597 graph
->src_scc
= -1;
2598 graph
->dst_scc
= -1;
2600 if (setup_lp(ctx
, graph
, force_zero
) < 0)
2602 sol
= solve_lp(graph
);
2605 if (sol
->size
== 0) {
2607 if (!ctx
->opt
->schedule_maximize_band_depth
&&
2608 graph
->n_total_row
> graph
->band_start
)
2609 return compute_next_band(ctx
, graph
);
2610 if (graph
->src_scc
>= 0)
2611 return compute_split_schedule(ctx
, graph
);
2612 if (graph
->n_total_row
> graph
->band_start
)
2613 return compute_next_band(ctx
, graph
);
2614 return carry_dependences(ctx
, graph
);
2616 if (update_schedule(graph
, sol
, 1, 1) < 0)
2621 if (graph
->n_total_row
> graph
->band_start
)
2623 return sort_statements(ctx
, graph
);
2626 /* Add a row to the schedules that separates the SCCs and move
2629 static int split_on_scc(struct isl_sched_graph
*graph
)
2633 for (i
= 0; i
< graph
->n
; ++i
) {
2634 struct isl_sched_node
*node
= &graph
->node
[i
];
2635 int row
= isl_mat_rows(node
->sched
);
2637 isl_map_free(node
->sched_map
);
2638 node
->sched_map
= NULL
;
2639 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2640 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2644 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2647 graph
->n_total_row
++;
2653 /* Compute a schedule for each component (identified by node->scc)
2654 * of the dependence graph separately and then combine the results.
2655 * Depending on the setting of schedule_fuse, a component may be
2656 * either weakly or strongly connected.
2658 * The band_id is adjusted such that each component has a separate id.
2659 * Note that the band_id may have already been set to a value different
2660 * from zero by compute_split_schedule.
2662 static int compute_component_schedule(isl_ctx
*ctx
,
2663 struct isl_sched_graph
*graph
)
2667 int n_total_row
, orig_total_row
;
2668 int n_band
, orig_band
;
2670 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
)
2671 split_on_scc(graph
);
2674 orig_total_row
= graph
->n_total_row
;
2676 orig_band
= graph
->n_band
;
2677 for (i
= 0; i
< graph
->n
; ++i
)
2678 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
2679 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
2681 for (i
= 0; i
< graph
->n
; ++i
)
2682 if (graph
->node
[i
].scc
== wcc
)
2685 for (i
= 0; i
< graph
->n_edge
; ++i
)
2686 if (graph
->edge
[i
].src
->scc
== wcc
&&
2687 graph
->edge
[i
].dst
->scc
== wcc
)
2690 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
2692 &edge_scc_exactly
, wcc
, 1) < 0)
2694 if (graph
->n_total_row
> n_total_row
)
2695 n_total_row
= graph
->n_total_row
;
2696 graph
->n_total_row
= orig_total_row
;
2697 if (graph
->n_band
> n_band
)
2698 n_band
= graph
->n_band
;
2699 graph
->n_band
= orig_band
;
2702 graph
->n_total_row
= n_total_row
;
2703 graph
->n_band
= n_band
;
2705 return pad_schedule(graph
);
2708 /* Compute a schedule for the given dependence graph.
2709 * We first check if the graph is connected (through validity dependences)
2710 * and, if not, compute a schedule for each component separately.
2711 * If schedule_fuse is set to minimal fusion, then we check for strongly
2712 * connected components instead and compute a separate schedule for
2713 * each such strongly connected component.
2715 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2717 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
2718 if (detect_sccs(graph
) < 0)
2721 if (detect_wccs(graph
) < 0)
2726 return compute_component_schedule(ctx
, graph
);
2728 return compute_schedule_wcc(ctx
, graph
);
2731 /* Compute a schedule for the given union of domains that respects
2732 * all the validity dependences.
2733 * If the default isl scheduling algorithm is used, it tries to minimize
2734 * the dependence distances over the proximity dependences.
2735 * If Feautrier's scheduling algorithm is used, the proximity dependence
2736 * distances are only minimized during the extension to a full-dimensional
2739 __isl_give isl_schedule
*isl_union_set_compute_schedule(
2740 __isl_take isl_union_set
*domain
,
2741 __isl_take isl_union_map
*validity
,
2742 __isl_take isl_union_map
*proximity
)
2744 isl_ctx
*ctx
= isl_union_set_get_ctx(domain
);
2746 struct isl_sched_graph graph
= { 0 };
2747 isl_schedule
*sched
;
2748 struct isl_extract_edge_data data
;
2750 domain
= isl_union_set_align_params(domain
,
2751 isl_union_map_get_space(validity
));
2752 domain
= isl_union_set_align_params(domain
,
2753 isl_union_map_get_space(proximity
));
2754 dim
= isl_union_set_get_space(domain
);
2755 validity
= isl_union_map_align_params(validity
, isl_space_copy(dim
));
2756 proximity
= isl_union_map_align_params(proximity
, dim
);
2761 graph
.n
= isl_union_set_n_set(domain
);
2764 if (graph_alloc(ctx
, &graph
, graph
.n
,
2765 isl_union_map_n_map(validity
) + isl_union_map_n_map(proximity
)) < 0)
2769 if (isl_union_set_foreach_set(domain
, &extract_node
, &graph
) < 0)
2771 if (graph_init_table(ctx
, &graph
) < 0)
2773 graph
.max_edge
[isl_edge_validity
] = isl_union_map_n_map(validity
);
2774 graph
.max_edge
[isl_edge_proximity
] = isl_union_map_n_map(proximity
);
2775 if (graph_init_edge_tables(ctx
, &graph
) < 0)
2778 data
.graph
= &graph
;
2779 data
.type
= isl_edge_validity
;
2780 if (isl_union_map_foreach_map(validity
, &extract_edge
, &data
) < 0)
2782 data
.type
= isl_edge_proximity
;
2783 if (isl_union_map_foreach_map(proximity
, &extract_edge
, &data
) < 0)
2786 if (compute_schedule(ctx
, &graph
) < 0)
2790 sched
= extract_schedule(&graph
, isl_union_set_get_space(domain
));
2792 graph_free(ctx
, &graph
);
2793 isl_union_set_free(domain
);
2794 isl_union_map_free(validity
);
2795 isl_union_map_free(proximity
);
2799 graph_free(ctx
, &graph
);
2800 isl_union_set_free(domain
);
2801 isl_union_map_free(validity
);
2802 isl_union_map_free(proximity
);
2806 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
2812 if (--sched
->ref
> 0)
2815 for (i
= 0; i
< sched
->n
; ++i
) {
2816 isl_map_free(sched
->node
[i
].sched
);
2817 free(sched
->node
[i
].band_end
);
2818 free(sched
->node
[i
].band_id
);
2819 free(sched
->node
[i
].zero
);
2821 isl_space_free(sched
->dim
);
2822 isl_band_list_free(sched
->band_forest
);
2827 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
2829 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
2832 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
2835 isl_union_map
*umap
;
2840 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
2841 for (i
= 0; i
< sched
->n
; ++i
)
2842 umap
= isl_union_map_add_map(umap
,
2843 isl_map_copy(sched
->node
[i
].sched
));
2848 static __isl_give isl_band_list
*construct_band_list(
2849 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2850 int band_nr
, int *parent_active
, int n_active
);
2852 /* Construct an isl_band structure for the band in the given schedule
2853 * with sequence number band_nr for the n_active nodes marked by active.
2854 * If the nodes don't have a band with the given sequence number,
2855 * then a band without members is created.
2857 * Because of the way the schedule is constructed, we know that
2858 * the position of the band inside the schedule of a node is the same
2859 * for all active nodes.
2861 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
2862 __isl_keep isl_band
*parent
,
2863 int band_nr
, int *active
, int n_active
)
2866 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2868 unsigned start
, end
;
2870 band
= isl_calloc_type(ctx
, isl_band
);
2875 band
->schedule
= schedule
;
2876 band
->parent
= parent
;
2878 for (i
= 0; i
< schedule
->n
; ++i
)
2879 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
2882 if (i
< schedule
->n
) {
2883 band
->children
= construct_band_list(schedule
, band
,
2884 band_nr
+ 1, active
, n_active
);
2885 if (!band
->children
)
2889 for (i
= 0; i
< schedule
->n
; ++i
)
2893 if (i
>= schedule
->n
)
2894 isl_die(ctx
, isl_error_internal
,
2895 "band without active statements", goto error
);
2897 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
2898 end
= band_nr
< schedule
->node
[i
].n_band
?
2899 schedule
->node
[i
].band_end
[band_nr
] : start
;
2900 band
->n
= end
- start
;
2902 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
2906 for (j
= 0; j
< band
->n
; ++j
)
2907 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
2909 band
->map
= isl_union_map_empty(isl_space_copy(schedule
->dim
));
2910 for (i
= 0; i
< schedule
->n
; ++i
) {
2917 map
= isl_map_copy(schedule
->node
[i
].sched
);
2918 n_out
= isl_map_dim(map
, isl_dim_out
);
2919 map
= isl_map_project_out(map
, isl_dim_out
, end
, n_out
- end
);
2920 map
= isl_map_project_out(map
, isl_dim_out
, 0, start
);
2921 band
->map
= isl_union_map_union(band
->map
,
2922 isl_union_map_from_map(map
));
2929 isl_band_free(band
);
2933 /* Construct a list of bands that start at the same position (with
2934 * sequence number band_nr) in the schedules of the nodes that
2935 * were active in the parent band.
2937 * A separate isl_band structure is created for each band_id
2938 * and for each node that does not have a band with sequence
2939 * number band_nr. In the latter case, a band without members
2941 * This ensures that if a band has any children, then each node
2942 * that was active in the band is active in exactly one of the children.
2944 static __isl_give isl_band_list
*construct_band_list(
2945 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2946 int band_nr
, int *parent_active
, int n_active
)
2949 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2952 isl_band_list
*list
;
2955 for (i
= 0; i
< n_active
; ++i
) {
2956 for (j
= 0; j
< schedule
->n
; ++j
) {
2957 if (!parent_active
[j
])
2959 if (schedule
->node
[j
].n_band
<= band_nr
)
2961 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
2967 for (j
= 0; j
< schedule
->n
; ++j
)
2968 if (schedule
->node
[j
].n_band
<= band_nr
)
2973 list
= isl_band_list_alloc(ctx
, n_band
);
2974 band
= construct_band(schedule
, parent
, band_nr
,
2975 parent_active
, n_active
);
2976 return isl_band_list_add(list
, band
);
2979 active
= isl_alloc_array(ctx
, int, schedule
->n
);
2983 list
= isl_band_list_alloc(ctx
, n_band
);
2985 for (i
= 0; i
< n_active
; ++i
) {
2989 for (j
= 0; j
< schedule
->n
; ++j
) {
2990 active
[j
] = parent_active
[j
] &&
2991 schedule
->node
[j
].n_band
> band_nr
&&
2992 schedule
->node
[j
].band_id
[band_nr
] == i
;
2999 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
3001 list
= isl_band_list_add(list
, band
);
3003 for (i
= 0; i
< schedule
->n
; ++i
) {
3005 if (!parent_active
[i
])
3007 if (schedule
->node
[i
].n_band
> band_nr
)
3009 for (j
= 0; j
< schedule
->n
; ++j
)
3011 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
3012 list
= isl_band_list_add(list
, band
);
3020 /* Construct a band forest representation of the schedule and
3021 * return the list of roots.
3023 static __isl_give isl_band_list
*construct_forest(
3024 __isl_keep isl_schedule
*schedule
)
3027 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3028 isl_band_list
*forest
;
3031 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3035 for (i
= 0; i
< schedule
->n
; ++i
)
3038 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
3045 /* Return the roots of a band forest representation of the schedule.
3047 __isl_give isl_band_list
*isl_schedule_get_band_forest(
3048 __isl_keep isl_schedule
*schedule
)
3052 if (!schedule
->band_forest
)
3053 schedule
->band_forest
= construct_forest(schedule
);
3054 return isl_band_list_dup(schedule
->band_forest
);
3057 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3058 __isl_keep isl_band_list
*list
);
3060 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
3061 __isl_keep isl_band
*band
)
3063 isl_band_list
*children
;
3065 p
= isl_printer_start_line(p
);
3066 p
= isl_printer_print_union_map(p
, band
->map
);
3067 p
= isl_printer_end_line(p
);
3069 if (!isl_band_has_children(band
))
3072 children
= isl_band_get_children(band
);
3074 p
= isl_printer_indent(p
, 4);
3075 p
= print_band_list(p
, children
);
3076 p
= isl_printer_indent(p
, -4);
3078 isl_band_list_free(children
);
3083 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3084 __isl_keep isl_band_list
*list
)
3088 n
= isl_band_list_n_band(list
);
3089 for (i
= 0; i
< n
; ++i
) {
3091 band
= isl_band_list_get_band(list
, i
);
3092 p
= print_band(p
, band
);
3093 isl_band_free(band
);
3099 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
3100 __isl_keep isl_schedule
*schedule
)
3102 isl_band_list
*forest
;
3104 forest
= isl_schedule_get_band_forest(schedule
);
3106 p
= print_band_list(p
, forest
);
3108 isl_band_list_free(forest
);
3113 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
3115 isl_printer
*printer
;
3120 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
3121 printer
= isl_printer_print_schedule(printer
, schedule
);
3123 isl_printer_free(printer
);