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
;
127 /* Internal information about the dependence graph used during
128 * the construction of the schedule.
130 * intra_hmap is a cache, mapping dependence relations to their dual,
131 * for dependences from a node to itself
132 * inter_hmap is a cache, mapping dependence relations to their dual,
133 * for dependences between distinct nodes
135 * n is the number of nodes
136 * node is the list of nodes
137 * maxvar is the maximal number of variables over all nodes
138 * n_row is the current (maximal) number of linearly independent
139 * rows in the node schedules
140 * n_total_row is the current number of rows in the node schedules
141 * n_band is the current number of completed bands
142 * band_start is the starting row in the node schedules of the current band
143 * root is set if this graph is the original dependence graph,
144 * without any splitting
146 * sorted contains a list of node indices sorted according to the
147 * SCC to which a node belongs
149 * n_edge is the number of edges
150 * edge is the list of edges
151 * edge_table contains pointers into the edge array, hashed on the source
152 * and sink spaces; the table only contains edges that represent
153 * validity constraints (and that may or may not also represent proximity
156 * node_table contains pointers into the node array, hashed on the space
158 * region contains a list of variable sequences that should be non-trivial
160 * lp contains the (I)LP problem used to obtain new schedule rows
162 * src_scc and dst_scc are the source and sink SCCs of an edge with
163 * conflicting constraints
165 * scc, sp, index and stack are used during the detection of SCCs
166 * scc is the number of the next SCC
167 * stack contains the nodes on the path from the root to the current node
168 * sp is the stack pointer
169 * index is the index of the last node visited
171 struct isl_sched_graph
{
172 isl_hmap_map_basic_set
*intra_hmap
;
173 isl_hmap_map_basic_set
*inter_hmap
;
175 struct isl_sched_node
*node
;
188 struct isl_sched_edge
*edge
;
190 struct isl_hash_table
*edge_table
;
192 struct isl_hash_table
*node_table
;
193 struct isl_region
*region
;
207 /* Initialize node_table based on the list of nodes.
209 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
213 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
214 if (!graph
->node_table
)
217 for (i
= 0; i
< graph
->n
; ++i
) {
218 struct isl_hash_table_entry
*entry
;
221 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
222 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
224 graph
->node
[i
].dim
, 1);
227 entry
->data
= &graph
->node
[i
];
233 /* Return a pointer to the node that lives within the given space,
234 * or NULL if there is no such node.
236 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
237 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
239 struct isl_hash_table_entry
*entry
;
242 hash
= isl_space_get_hash(dim
);
243 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
244 &node_has_dim
, dim
, 0);
246 return entry
? entry
->data
: NULL
;
249 static int edge_has_src_and_dst(const void *entry
, const void *val
)
251 const struct isl_sched_edge
*edge
= entry
;
252 const struct isl_sched_edge
*temp
= val
;
254 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
257 /* Initialize edge_table based on the list of edges.
258 * Only edges with validity set are added to the table.
260 static int graph_init_edge_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
264 graph
->edge_table
= isl_hash_table_alloc(ctx
, graph
->n_edge
);
265 if (!graph
->edge_table
)
268 for (i
= 0; i
< graph
->n_edge
; ++i
) {
269 struct isl_hash_table_entry
*entry
;
272 if (!graph
->edge
[i
].validity
)
275 hash
= isl_hash_init();
276 hash
= isl_hash_builtin(hash
, graph
->edge
[i
].src
);
277 hash
= isl_hash_builtin(hash
, graph
->edge
[i
].dst
);
278 entry
= isl_hash_table_find(ctx
, graph
->edge_table
, hash
,
279 &edge_has_src_and_dst
,
283 entry
->data
= &graph
->edge
[i
];
289 /* Check whether the dependence graph has a (validity) edge
290 * between the given two nodes.
292 static int graph_has_edge(struct isl_sched_graph
*graph
,
293 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
295 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
296 struct isl_hash_table_entry
*entry
;
298 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
299 struct isl_sched_edge
*edge
;
302 hash
= isl_hash_init();
303 hash
= isl_hash_builtin(hash
, temp
.src
);
304 hash
= isl_hash_builtin(hash
, temp
.dst
);
305 entry
= isl_hash_table_find(ctx
, graph
->edge_table
, hash
,
306 &edge_has_src_and_dst
, &temp
, 0);
311 empty
= isl_map_plain_is_empty(edge
->map
);
318 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
319 int n_node
, int n_edge
)
324 graph
->n_edge
= n_edge
;
325 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
326 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
327 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
328 graph
->stack
= isl_alloc_array(ctx
, int, graph
->n
);
329 graph
->edge
= isl_calloc_array(ctx
,
330 struct isl_sched_edge
, graph
->n_edge
);
332 graph
->intra_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
333 graph
->inter_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
335 if (!graph
->node
|| !graph
->region
|| !graph
->stack
|| !graph
->edge
||
339 for(i
= 0; i
< graph
->n
; ++i
)
340 graph
->sorted
[i
] = i
;
345 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
349 isl_hmap_map_basic_set_free(ctx
, graph
->intra_hmap
);
350 isl_hmap_map_basic_set_free(ctx
, graph
->inter_hmap
);
352 for (i
= 0; i
< graph
->n
; ++i
) {
353 isl_space_free(graph
->node
[i
].dim
);
354 isl_mat_free(graph
->node
[i
].sched
);
355 isl_map_free(graph
->node
[i
].sched_map
);
356 isl_mat_free(graph
->node
[i
].cmap
);
358 free(graph
->node
[i
].band
);
359 free(graph
->node
[i
].band_id
);
360 free(graph
->node
[i
].zero
);
365 for (i
= 0; i
< graph
->n_edge
; ++i
)
366 isl_map_free(graph
->edge
[i
].map
);
370 isl_hash_table_free(ctx
, graph
->edge_table
);
371 isl_hash_table_free(ctx
, graph
->node_table
);
372 isl_basic_set_free(graph
->lp
);
375 /* Add a new node to the graph representing the given set.
377 static int extract_node(__isl_take isl_set
*set
, void *user
)
383 struct isl_sched_graph
*graph
= user
;
384 int *band
, *band_id
, *zero
;
386 ctx
= isl_set_get_ctx(set
);
387 dim
= isl_set_get_space(set
);
389 nvar
= isl_space_dim(dim
, isl_dim_set
);
390 nparam
= isl_space_dim(dim
, isl_dim_param
);
391 if (!ctx
->opt
->schedule_parametric
)
393 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
394 graph
->node
[graph
->n
].dim
= dim
;
395 graph
->node
[graph
->n
].nvar
= nvar
;
396 graph
->node
[graph
->n
].nparam
= nparam
;
397 graph
->node
[graph
->n
].sched
= sched
;
398 graph
->node
[graph
->n
].sched_map
= NULL
;
399 band
= isl_alloc_array(ctx
, int, graph
->n_edge
+ nvar
);
400 graph
->node
[graph
->n
].band
= band
;
401 band_id
= isl_calloc_array(ctx
, int, graph
->n_edge
+ nvar
);
402 graph
->node
[graph
->n
].band_id
= band_id
;
403 zero
= isl_calloc_array(ctx
, int, graph
->n_edge
+ nvar
);
404 graph
->node
[graph
->n
].zero
= zero
;
407 if (!sched
|| !band
|| !band_id
|| !zero
)
413 /* Add a new edge to the graph based on the given map.
414 * Edges are first extracted from the validity dependences,
415 * from which the edge_table is constructed.
416 * Afterwards, the proximity dependences are added. If a proximity
417 * dependence relation happens to be identical to one of the
418 * validity dependence relations added before, then we don't create
419 * a new edge, but instead mark the original edge as also representing
420 * a proximity dependence.
422 static int extract_edge(__isl_take isl_map
*map
, void *user
)
424 isl_ctx
*ctx
= isl_map_get_ctx(map
);
425 struct isl_sched_graph
*graph
= user
;
426 struct isl_sched_node
*src
, *dst
;
429 dim
= isl_space_domain(isl_map_get_space(map
));
430 src
= graph_find_node(ctx
, graph
, dim
);
432 dim
= isl_space_range(isl_map_get_space(map
));
433 dst
= graph_find_node(ctx
, graph
, dim
);
441 graph
->edge
[graph
->n_edge
].src
= src
;
442 graph
->edge
[graph
->n_edge
].dst
= dst
;
443 graph
->edge
[graph
->n_edge
].map
= map
;
444 graph
->edge
[graph
->n_edge
].validity
= !graph
->edge_table
;
445 graph
->edge
[graph
->n_edge
].proximity
= !!graph
->edge_table
;
448 if (graph
->edge_table
) {
450 struct isl_hash_table_entry
*entry
;
451 struct isl_sched_edge
*edge
;
454 hash
= isl_hash_init();
455 hash
= isl_hash_builtin(hash
, src
);
456 hash
= isl_hash_builtin(hash
, dst
);
457 entry
= isl_hash_table_find(ctx
, graph
->edge_table
, hash
,
458 &edge_has_src_and_dst
,
459 &graph
->edge
[graph
->n_edge
- 1], 0);
463 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
477 /* Check whether there is a validity dependence from src to dst,
478 * forcing dst to follow src.
480 static int node_follows(struct isl_sched_graph
*graph
,
481 struct isl_sched_node
*dst
, struct isl_sched_node
*src
)
483 return graph_has_edge(graph
, src
, dst
);
486 /* Perform Tarjan's algorithm for computing the strongly connected components
487 * in the dependence graph (only validity edges).
488 * If directed is not set, we consider the graph to be undirected and
489 * we effectively compute the (weakly) connected components.
491 static int detect_sccs_tarjan(struct isl_sched_graph
*g
, int i
, int directed
)
495 g
->node
[i
].index
= g
->index
;
496 g
->node
[i
].min_index
= g
->index
;
497 g
->node
[i
].on_stack
= 1;
499 g
->stack
[g
->sp
++] = i
;
501 for (j
= g
->n
- 1; j
>= 0; --j
) {
506 if (g
->node
[j
].index
>= 0 &&
507 (!g
->node
[j
].on_stack
||
508 g
->node
[j
].index
> g
->node
[i
].min_index
))
511 f
= node_follows(g
, &g
->node
[i
], &g
->node
[j
]);
514 if (!f
&& !directed
) {
515 f
= node_follows(g
, &g
->node
[j
], &g
->node
[i
]);
521 if (g
->node
[j
].index
< 0) {
522 detect_sccs_tarjan(g
, j
, directed
);
523 if (g
->node
[j
].min_index
< g
->node
[i
].min_index
)
524 g
->node
[i
].min_index
= g
->node
[j
].min_index
;
525 } else if (g
->node
[j
].index
< g
->node
[i
].min_index
)
526 g
->node
[i
].min_index
= g
->node
[j
].index
;
529 if (g
->node
[i
].index
!= g
->node
[i
].min_index
)
533 j
= g
->stack
[--g
->sp
];
534 g
->node
[j
].on_stack
= 0;
535 g
->node
[j
].scc
= g
->scc
;
542 static int detect_ccs(struct isl_sched_graph
*graph
, int directed
)
549 for (i
= graph
->n
- 1; i
>= 0; --i
)
550 graph
->node
[i
].index
= -1;
552 for (i
= graph
->n
- 1; i
>= 0; --i
) {
553 if (graph
->node
[i
].index
>= 0)
555 if (detect_sccs_tarjan(graph
, i
, directed
) < 0)
562 /* Apply Tarjan's algorithm to detect the strongly connected components
563 * in the dependence graph.
565 static int detect_sccs(struct isl_sched_graph
*graph
)
567 return detect_ccs(graph
, 1);
570 /* Apply Tarjan's algorithm to detect the (weakly) connected components
571 * in the dependence graph.
573 static int detect_wccs(struct isl_sched_graph
*graph
)
575 return detect_ccs(graph
, 0);
578 static int cmp_scc(const void *a
, const void *b
, void *data
)
580 struct isl_sched_graph
*graph
= data
;
584 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
587 /* Sort the elements of graph->sorted according to the corresponding SCCs.
589 static void sort_sccs(struct isl_sched_graph
*graph
)
591 isl_quicksort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
594 /* Given a dependence relation R from a node to itself,
595 * construct the set of coefficients of valid constraints for elements
596 * in that dependence relation.
597 * In particular, the result contains tuples of coefficients
598 * c_0, c_n, c_x such that
600 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
604 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
606 * We choose here to compute the dual of delta R.
607 * Alternatively, we could have computed the dual of R, resulting
608 * in a set of tuples c_0, c_n, c_x, c_y, and then
609 * plugged in (c_0, c_n, c_x, -c_x).
611 static __isl_give isl_basic_set
*intra_coefficients(
612 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
614 isl_ctx
*ctx
= isl_map_get_ctx(map
);
618 if (isl_hmap_map_basic_set_has(ctx
, graph
->intra_hmap
, map
))
619 return isl_hmap_map_basic_set_get(ctx
, graph
->intra_hmap
, map
);
621 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
622 coef
= isl_set_coefficients(delta
);
623 isl_hmap_map_basic_set_set(ctx
, graph
->intra_hmap
, map
,
624 isl_basic_set_copy(coef
));
629 /* Given a dependence relation R, * construct the set of coefficients
630 * of valid constraints for elements in that dependence relation.
631 * In particular, the result contains tuples of coefficients
632 * c_0, c_n, c_x, c_y such that
634 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
637 static __isl_give isl_basic_set
*inter_coefficients(
638 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
640 isl_ctx
*ctx
= isl_map_get_ctx(map
);
644 if (isl_hmap_map_basic_set_has(ctx
, graph
->inter_hmap
, map
))
645 return isl_hmap_map_basic_set_get(ctx
, graph
->inter_hmap
, map
);
647 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
648 coef
= isl_set_coefficients(set
);
649 isl_hmap_map_basic_set_set(ctx
, graph
->inter_hmap
, map
,
650 isl_basic_set_copy(coef
));
655 /* Add constraints to graph->lp that force validity for the given
656 * dependence from a node i to itself.
657 * That is, add constraints that enforce
659 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
660 * = c_i_x (y - x) >= 0
662 * for each (x,y) in R.
663 * We obtain general constraints on coefficients (c_0, c_n, c_x)
664 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
665 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
666 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
668 * Actually, we do not construct constraints for the c_i_x themselves,
669 * but for the coefficients of c_i_x written as a linear combination
670 * of the columns in node->cmap.
672 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
673 struct isl_sched_edge
*edge
)
676 isl_map
*map
= isl_map_copy(edge
->map
);
677 isl_ctx
*ctx
= isl_map_get_ctx(map
);
679 isl_dim_map
*dim_map
;
681 struct isl_sched_node
*node
= edge
->src
;
683 coef
= intra_coefficients(graph
, map
);
685 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
687 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
688 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
690 total
= isl_basic_set_total_dim(graph
->lp
);
691 dim_map
= isl_dim_map_alloc(ctx
, total
);
692 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
693 isl_space_dim(dim
, isl_dim_set
), 1,
695 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
696 isl_space_dim(dim
, isl_dim_set
), 1,
698 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
699 coef
->n_eq
, coef
->n_ineq
);
700 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
707 /* Add constraints to graph->lp that force validity for the given
708 * dependence from node i to node j.
709 * That is, add constraints that enforce
711 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
713 * for each (x,y) in R.
714 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
715 * of valid constraints for R and then plug in
716 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
717 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
718 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
719 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
721 * Actually, we do not construct constraints for the c_*_x themselves,
722 * but for the coefficients of c_*_x written as a linear combination
723 * of the columns in node->cmap.
725 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
726 struct isl_sched_edge
*edge
)
729 isl_map
*map
= isl_map_copy(edge
->map
);
730 isl_ctx
*ctx
= isl_map_get_ctx(map
);
732 isl_dim_map
*dim_map
;
734 struct isl_sched_node
*src
= edge
->src
;
735 struct isl_sched_node
*dst
= edge
->dst
;
737 coef
= inter_coefficients(graph
, map
);
739 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
741 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
742 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
743 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
744 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
745 isl_mat_copy(dst
->cmap
));
747 total
= isl_basic_set_total_dim(graph
->lp
);
748 dim_map
= isl_dim_map_alloc(ctx
, total
);
750 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
751 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
752 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
753 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
754 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
756 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
757 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
760 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
761 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
762 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
763 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
764 isl_space_dim(dim
, isl_dim_set
), 1,
766 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
767 isl_space_dim(dim
, isl_dim_set
), 1,
770 edge
->start
= graph
->lp
->n_ineq
;
771 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
772 coef
->n_eq
, coef
->n_ineq
);
773 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
776 edge
->end
= graph
->lp
->n_ineq
;
781 /* Add constraints to graph->lp that bound the dependence distance for the given
782 * dependence from a node i to itself.
783 * If s = 1, we add the constraint
785 * c_i_x (y - x) <= m_0 + m_n n
789 * -c_i_x (y - x) + m_0 + m_n n >= 0
791 * for each (x,y) in R.
792 * If s = -1, we add the constraint
794 * -c_i_x (y - x) <= m_0 + m_n n
798 * c_i_x (y - x) + m_0 + m_n n >= 0
800 * for each (x,y) in R.
801 * We obtain general constraints on coefficients (c_0, c_n, c_x)
802 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
803 * with each coefficient (except m_0) represented as a pair of non-negative
806 * Actually, we do not construct constraints for the c_i_x themselves,
807 * but for the coefficients of c_i_x written as a linear combination
808 * of the columns in node->cmap.
810 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
811 struct isl_sched_edge
*edge
, int s
)
815 isl_map
*map
= isl_map_copy(edge
->map
);
816 isl_ctx
*ctx
= isl_map_get_ctx(map
);
818 isl_dim_map
*dim_map
;
820 struct isl_sched_node
*node
= edge
->src
;
822 coef
= intra_coefficients(graph
, map
);
824 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
826 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
827 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
829 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
830 total
= isl_basic_set_total_dim(graph
->lp
);
831 dim_map
= isl_dim_map_alloc(ctx
, total
);
832 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
833 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
834 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
835 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
836 isl_space_dim(dim
, isl_dim_set
), 1,
838 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
839 isl_space_dim(dim
, isl_dim_set
), 1,
841 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
842 coef
->n_eq
, coef
->n_ineq
);
843 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
850 /* Add constraints to graph->lp that bound the dependence distance for the given
851 * dependence from node i to node j.
852 * If s = 1, we add the constraint
854 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
859 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
862 * for each (x,y) in R.
863 * If s = -1, we add the constraint
865 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
870 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
873 * for each (x,y) in R.
874 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
875 * of valid constraints for R and then plug in
876 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
878 * with each coefficient (except m_0, c_j_0 and c_i_0)
879 * represented as a pair of non-negative coefficients.
881 * Actually, we do not construct constraints for the c_*_x themselves,
882 * but for the coefficients of c_*_x written as a linear combination
883 * of the columns in node->cmap.
885 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
886 struct isl_sched_edge
*edge
, int s
)
890 isl_map
*map
= isl_map_copy(edge
->map
);
891 isl_ctx
*ctx
= isl_map_get_ctx(map
);
893 isl_dim_map
*dim_map
;
895 struct isl_sched_node
*src
= edge
->src
;
896 struct isl_sched_node
*dst
= edge
->dst
;
898 coef
= inter_coefficients(graph
, map
);
900 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
902 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
903 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
904 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
905 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
906 isl_mat_copy(dst
->cmap
));
908 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
909 total
= isl_basic_set_total_dim(graph
->lp
);
910 dim_map
= isl_dim_map_alloc(ctx
, total
);
912 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
913 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
914 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
916 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
917 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
918 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
919 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
920 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
922 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
923 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
926 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
927 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
928 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
929 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
930 isl_space_dim(dim
, isl_dim_set
), 1,
932 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
933 isl_space_dim(dim
, isl_dim_set
), 1,
936 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
937 coef
->n_eq
, coef
->n_ineq
);
938 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
945 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
949 for (i
= 0; i
< graph
->n_edge
; ++i
) {
950 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
953 if (edge
->src
!= edge
->dst
)
955 if (add_intra_validity_constraints(graph
, edge
) < 0)
959 for (i
= 0; i
< graph
->n_edge
; ++i
) {
960 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
963 if (edge
->src
== edge
->dst
)
965 if (add_inter_validity_constraints(graph
, edge
) < 0)
972 /* Add constraints to graph->lp that bound the dependence distance
973 * for all dependence relations.
974 * If a given proximity dependence is identical to a validity
975 * dependence, then the dependence distance is already bounded
976 * from below (by zero), so we only need to bound the distance
978 * Otherwise, we need to bound the distance both from above and from below.
980 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
984 for (i
= 0; i
< graph
->n_edge
; ++i
) {
985 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
986 if (!edge
->proximity
)
988 if (edge
->src
== edge
->dst
&&
989 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
991 if (edge
->src
!= edge
->dst
&&
992 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
996 if (edge
->src
== edge
->dst
&&
997 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
999 if (edge
->src
!= edge
->dst
&&
1000 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1007 /* Compute a basis for the rows in the linear part of the schedule
1008 * and extend this basis to a full basis. The remaining rows
1009 * can then be used to force linear independence from the rows
1012 * In particular, given the schedule rows S, we compute
1016 * with H the Hermite normal form of S. That is, all but the
1017 * first rank columns of Q are zero and so each row in S is
1018 * a linear combination of the first rank rows of Q.
1019 * The matrix Q is then transposed because we will write the
1020 * coefficients of the next schedule row as a column vector s
1021 * and express this s as a linear combination s = Q c of the
1024 static int node_update_cmap(struct isl_sched_node
*node
)
1027 int n_row
= isl_mat_rows(node
->sched
);
1029 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1030 1 + node
->nparam
, node
->nvar
);
1032 H
= isl_mat_left_hermite(H
, 0, NULL
, &Q
);
1033 isl_mat_free(node
->cmap
);
1034 node
->cmap
= isl_mat_transpose(Q
);
1035 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1038 if (!node
->cmap
|| node
->rank
< 0)
1043 /* Count the number of equality and inequality constraints
1044 * that will be added for the given map.
1045 * If once is set, then we count
1046 * each edge exactly once. Otherwise, we count as follows
1047 * validity -> 1 (>= 0)
1048 * validity+proximity -> 2 (>= 0 and upper bound)
1049 * proximity -> 2 (lower and upper bound)
1051 static int count_map_constraints(struct isl_sched_graph
*graph
,
1052 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1053 int *n_eq
, int *n_ineq
, int once
)
1055 isl_basic_set
*coef
;
1056 int f
= once
? 1 : edge
->proximity
? 2 : 1;
1058 if (edge
->src
== edge
->dst
)
1059 coef
= intra_coefficients(graph
, map
);
1061 coef
= inter_coefficients(graph
, map
);
1064 *n_eq
+= f
* coef
->n_eq
;
1065 *n_ineq
+= f
* coef
->n_ineq
;
1066 isl_basic_set_free(coef
);
1071 /* Count the number of equality and inequality constraints
1072 * that will be added to the main lp problem.
1073 * If once is set, then we count
1074 * each edge exactly once. Otherwise, we count as follows
1075 * validity -> 1 (>= 0)
1076 * validity+proximity -> 2 (>= 0 and upper bound)
1077 * proximity -> 2 (lower and upper bound)
1079 static int count_constraints(struct isl_sched_graph
*graph
,
1080 int *n_eq
, int *n_ineq
, int once
)
1084 *n_eq
= *n_ineq
= 0;
1085 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1086 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1087 isl_map
*map
= isl_map_copy(edge
->map
);
1089 if (count_map_constraints(graph
, edge
, map
,
1090 n_eq
, n_ineq
, once
) < 0)
1097 /* Add constraints that bound the values of the variable and parameter
1098 * coefficients of the schedule.
1100 * The maximal value of the coefficients is defined by the option
1101 * 'schedule_max_coefficient'.
1103 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1104 struct isl_sched_graph
*graph
)
1107 int max_coefficient
;
1110 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1112 if (max_coefficient
== -1)
1115 total
= isl_basic_set_total_dim(graph
->lp
);
1117 for (i
= 0; i
< graph
->n
; ++i
) {
1118 struct isl_sched_node
*node
= &graph
->node
[i
];
1119 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1121 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1124 dim
= 1 + node
->start
+ 1 + j
;
1125 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1126 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1127 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1134 /* Construct an ILP problem for finding schedule coefficients
1135 * that result in non-negative, but small dependence distances
1136 * over all dependences.
1137 * In particular, the dependence distances over proximity edges
1138 * are bounded by m_0 + m_n n and we compute schedule coefficients
1139 * with small values (preferably zero) of m_n and m_0.
1141 * All variables of the ILP are non-negative. The actual coefficients
1142 * may be negative, so each coefficient is represented as the difference
1143 * of two non-negative variables. The negative part always appears
1144 * immediately before the positive part.
1145 * Other than that, the variables have the following order
1147 * - sum of positive and negative parts of m_n coefficients
1149 * - sum of positive and negative parts of all c_n coefficients
1150 * (unconstrained when computing non-parametric schedules)
1151 * - sum of positive and negative parts of all c_x coefficients
1152 * - positive and negative parts of m_n coefficients
1155 * - positive and negative parts of c_i_n (if parametric)
1156 * - positive and negative parts of c_i_x
1158 * The c_i_x are not represented directly, but through the columns of
1159 * node->cmap. That is, the computed values are for variable t_i_x
1160 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1162 * The constraints are those from the edges plus two or three equalities
1163 * to express the sums.
1165 * If force_zero is set, then we add equalities to ensure that
1166 * the sum of the m_n coefficients and m_0 are both zero.
1168 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1179 int max_constant_term
;
1180 int max_coefficient
;
1182 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1183 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1185 parametric
= ctx
->opt
->schedule_parametric
;
1186 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1188 total
= param_pos
+ 2 * nparam
;
1189 for (i
= 0; i
< graph
->n
; ++i
) {
1190 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1191 if (node_update_cmap(node
) < 0)
1193 node
->start
= total
;
1194 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1197 if (count_constraints(graph
, &n_eq
, &n_ineq
, 0) < 0)
1200 dim
= isl_space_set_alloc(ctx
, 0, total
);
1201 isl_basic_set_free(graph
->lp
);
1202 n_eq
+= 2 + parametric
+ force_zero
;
1203 if (max_constant_term
!= -1)
1205 if (max_coefficient
!= -1)
1206 for (i
= 0; i
< graph
->n
; ++i
)
1207 n_ineq
+= 2 * graph
->node
[i
].nparam
+
1208 2 * graph
->node
[i
].nvar
;
1210 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1212 k
= isl_basic_set_alloc_equality(graph
->lp
);
1215 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1217 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1218 for (i
= 0; i
< 2 * nparam
; ++i
)
1219 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1222 k
= isl_basic_set_alloc_equality(graph
->lp
);
1225 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1226 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1230 k
= isl_basic_set_alloc_equality(graph
->lp
);
1233 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1234 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1235 for (i
= 0; i
< graph
->n
; ++i
) {
1236 int pos
= 1 + graph
->node
[i
].start
+ 1;
1238 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1239 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1243 k
= isl_basic_set_alloc_equality(graph
->lp
);
1246 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1247 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1248 for (i
= 0; i
< graph
->n
; ++i
) {
1249 struct isl_sched_node
*node
= &graph
->node
[i
];
1250 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1252 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1253 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1256 if (max_constant_term
!= -1)
1257 for (i
= 0; i
< graph
->n
; ++i
) {
1258 struct isl_sched_node
*node
= &graph
->node
[i
];
1259 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1262 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1263 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1264 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1267 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1269 if (add_all_validity_constraints(graph
) < 0)
1271 if (add_all_proximity_constraints(graph
) < 0)
1277 /* Analyze the conflicting constraint found by
1278 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1279 * constraint of one of the edges between distinct nodes, living, moreover
1280 * in distinct SCCs, then record the source and sink SCC as this may
1281 * be a good place to cut between SCCs.
1283 static int check_conflict(int con
, void *user
)
1286 struct isl_sched_graph
*graph
= user
;
1288 if (graph
->src_scc
>= 0)
1291 con
-= graph
->lp
->n_eq
;
1293 if (con
>= graph
->lp
->n_ineq
)
1296 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1297 if (!graph
->edge
[i
].validity
)
1299 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1301 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1303 if (graph
->edge
[i
].start
> con
)
1305 if (graph
->edge
[i
].end
<= con
)
1307 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1308 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1314 /* Check whether the next schedule row of the given node needs to be
1315 * non-trivial. Lower-dimensional domains may have some trivial rows,
1316 * but as soon as the number of remaining required non-trivial rows
1317 * is as large as the number or remaining rows to be computed,
1318 * all remaining rows need to be non-trivial.
1320 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1322 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1325 /* Solve the ILP problem constructed in setup_lp.
1326 * For each node such that all the remaining rows of its schedule
1327 * need to be non-trivial, we construct a non-triviality region.
1328 * This region imposes that the next row is independent of previous rows.
1329 * In particular the coefficients c_i_x are represented by t_i_x
1330 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1331 * its first columns span the rows of the previously computed part
1332 * of the schedule. The non-triviality region enforces that at least
1333 * one of the remaining components of t_i_x is non-zero, i.e.,
1334 * that the new schedule row depends on at least one of the remaining
1337 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1343 for (i
= 0; i
< graph
->n
; ++i
) {
1344 struct isl_sched_node
*node
= &graph
->node
[i
];
1345 int skip
= node
->rank
;
1346 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1347 if (needs_row(graph
, node
))
1348 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1350 graph
->region
[i
].len
= 0;
1352 lp
= isl_basic_set_copy(graph
->lp
);
1353 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1354 graph
->region
, &check_conflict
, graph
);
1358 /* Update the schedules of all nodes based on the given solution
1359 * of the LP problem.
1360 * The new row is added to the current band.
1361 * All possibly negative coefficients are encoded as a difference
1362 * of two non-negative variables, so we need to perform the subtraction
1363 * here. Moreover, if use_cmap is set, then the solution does
1364 * not refer to the actual coefficients c_i_x, but instead to variables
1365 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1366 * In this case, we then also need to perform this multiplication
1367 * to obtain the values of c_i_x.
1369 * If check_zero is set, then the first two coordinates of sol are
1370 * assumed to correspond to the dependence distance. If these two
1371 * coordinates are zero, then the corresponding scheduling dimension
1372 * is marked as being zero distance.
1374 static int update_schedule(struct isl_sched_graph
*graph
,
1375 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1379 isl_vec
*csol
= NULL
;
1384 isl_die(sol
->ctx
, isl_error_internal
,
1385 "no solution found", goto error
);
1388 zero
= isl_int_is_zero(sol
->el
[1]) &&
1389 isl_int_is_zero(sol
->el
[2]);
1391 for (i
= 0; i
< graph
->n
; ++i
) {
1392 struct isl_sched_node
*node
= &graph
->node
[i
];
1393 int pos
= node
->start
;
1394 int row
= isl_mat_rows(node
->sched
);
1397 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1401 isl_map_free(node
->sched_map
);
1402 node
->sched_map
= NULL
;
1403 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1406 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1408 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1409 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1410 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1411 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1412 for (j
= 0; j
< node
->nparam
; ++j
)
1413 node
->sched
= isl_mat_set_element(node
->sched
,
1414 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1415 for (j
= 0; j
< node
->nvar
; ++j
)
1416 isl_int_set(csol
->el
[j
],
1417 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1419 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1423 for (j
= 0; j
< node
->nvar
; ++j
)
1424 node
->sched
= isl_mat_set_element(node
->sched
,
1425 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1426 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1427 node
->zero
[graph
->n_total_row
] = zero
;
1433 graph
->n_total_row
++;
1442 /* Convert node->sched into a map and return this map.
1443 * We simply add equality constraints that express each output variable
1444 * as the affine combination of parameters and input variables specified
1445 * by the schedule matrix.
1447 * The result is cached in node->sched_map, which needs to be released
1448 * whenever node->sched is updated.
1450 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1454 isl_local_space
*ls
;
1455 isl_basic_map
*bmap
;
1460 if (node
->sched_map
)
1461 return isl_map_copy(node
->sched_map
);
1463 nrow
= isl_mat_rows(node
->sched
);
1464 ncol
= isl_mat_cols(node
->sched
) - 1;
1465 dim
= isl_space_from_domain(isl_space_copy(node
->dim
));
1466 dim
= isl_space_add_dims(dim
, isl_dim_out
, nrow
);
1467 bmap
= isl_basic_map_universe(isl_space_copy(dim
));
1468 ls
= isl_local_space_from_space(dim
);
1472 for (i
= 0; i
< nrow
; ++i
) {
1473 c
= isl_equality_alloc(isl_local_space_copy(ls
));
1474 isl_constraint_set_coefficient_si(c
, isl_dim_out
, i
, -1);
1475 isl_mat_get_element(node
->sched
, i
, 0, &v
);
1476 isl_constraint_set_constant(c
, v
);
1477 for (j
= 0; j
< node
->nparam
; ++j
) {
1478 isl_mat_get_element(node
->sched
, i
, 1 + j
, &v
);
1479 isl_constraint_set_coefficient(c
, isl_dim_param
, j
, v
);
1481 for (j
= 0; j
< node
->nvar
; ++j
) {
1482 isl_mat_get_element(node
->sched
,
1483 i
, 1 + node
->nparam
+ j
, &v
);
1484 isl_constraint_set_coefficient(c
, isl_dim_in
, j
, v
);
1486 bmap
= isl_basic_map_add_constraint(bmap
, c
);
1491 isl_local_space_free(ls
);
1493 node
->sched_map
= isl_map_from_basic_map(bmap
);
1494 return isl_map_copy(node
->sched_map
);
1497 /* Update the given dependence relation based on the current schedule.
1498 * That is, intersect the dependence relation with a map expressing
1499 * that source and sink are executed within the same iteration of
1500 * the current schedule.
1501 * This is not the most efficient way, but this shouldn't be a critical
1504 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1505 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1507 isl_map
*src_sched
, *dst_sched
, *id
;
1509 src_sched
= node_extract_schedule(src
);
1510 dst_sched
= node_extract_schedule(dst
);
1511 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1512 return isl_map_intersect(map
, id
);
1515 /* Update the dependence relations of all edges based on the current schedule.
1516 * If a dependence is carried completely by the current schedule, then
1517 * it is removed and edge_table is updated accordingly.
1519 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1522 int reset_table
= 0;
1524 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1525 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1526 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1530 if (isl_map_plain_is_empty(edge
->map
)) {
1532 isl_map_free(edge
->map
);
1533 if (i
!= graph
->n_edge
- 1)
1534 graph
->edge
[i
] = graph
->edge
[graph
->n_edge
- 1];
1540 isl_hash_table_free(ctx
, graph
->edge_table
);
1541 graph
->edge_table
= NULL
;
1542 return graph_init_edge_table(ctx
, graph
);
1548 static void next_band(struct isl_sched_graph
*graph
)
1550 graph
->band_start
= graph
->n_total_row
;
1554 /* Topologically sort statements mapped to same schedule iteration
1555 * and add a row to the schedule corresponding to this order.
1557 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1564 if (update_edges(ctx
, graph
) < 0)
1567 if (graph
->n_edge
== 0)
1570 if (detect_sccs(graph
) < 0)
1573 for (i
= 0; i
< graph
->n
; ++i
) {
1574 struct isl_sched_node
*node
= &graph
->node
[i
];
1575 int row
= isl_mat_rows(node
->sched
);
1576 int cols
= isl_mat_cols(node
->sched
);
1578 isl_map_free(node
->sched_map
);
1579 node
->sched_map
= NULL
;
1580 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1583 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1585 for (j
= 1; j
< cols
; ++j
)
1586 node
->sched
= isl_mat_set_element_si(node
->sched
,
1588 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1591 graph
->n_total_row
++;
1597 /* Construct an isl_schedule based on the computed schedule stored
1598 * in graph and with parameters specified by dim.
1600 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1601 __isl_take isl_space
*dim
)
1605 isl_schedule
*sched
= NULL
;
1610 ctx
= isl_space_get_ctx(dim
);
1611 sched
= isl_calloc(ctx
, struct isl_schedule
,
1612 sizeof(struct isl_schedule
) +
1613 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1618 sched
->n
= graph
->n
;
1619 sched
->n_band
= graph
->n_band
;
1620 sched
->n_total_row
= graph
->n_total_row
;
1622 for (i
= 0; i
< sched
->n
; ++i
) {
1624 int *band_end
, *band_id
, *zero
;
1626 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1627 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1628 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1629 sched
->node
[i
].sched
= node_extract_schedule(&graph
->node
[i
]);
1630 sched
->node
[i
].band_end
= band_end
;
1631 sched
->node
[i
].band_id
= band_id
;
1632 sched
->node
[i
].zero
= zero
;
1633 if (!band_end
|| !band_id
|| !zero
)
1636 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1637 zero
[r
] = graph
->node
[i
].zero
[r
];
1638 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1639 if (graph
->node
[i
].band
[r
] == b
)
1642 if (graph
->node
[i
].band
[r
] == -1)
1645 if (r
== graph
->n_total_row
)
1647 sched
->node
[i
].n_band
= b
;
1648 for (--b
; b
>= 0; --b
)
1649 band_id
[b
] = graph
->node
[i
].band_id
[b
];
1656 isl_space_free(dim
);
1657 isl_schedule_free(sched
);
1661 /* Copy nodes that satisfy node_pred from the src dependence graph
1662 * to the dst dependence graph.
1664 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
1665 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1670 for (i
= 0; i
< src
->n
; ++i
) {
1671 if (!node_pred(&src
->node
[i
], data
))
1673 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
1674 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
1675 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
1676 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
1677 dst
->node
[dst
->n
].sched_map
=
1678 isl_map_copy(src
->node
[i
].sched_map
);
1679 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
1680 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
1681 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
1688 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1689 * to the dst dependence graph.
1691 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
1692 struct isl_sched_graph
*src
,
1693 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
1698 for (i
= 0; i
< src
->n_edge
; ++i
) {
1699 struct isl_sched_edge
*edge
= &src
->edge
[i
];
1702 if (!edge_pred(edge
, data
))
1705 if (isl_map_plain_is_empty(edge
->map
))
1708 map
= isl_map_copy(edge
->map
);
1710 dst
->edge
[dst
->n_edge
].src
=
1711 graph_find_node(ctx
, dst
, edge
->src
->dim
);
1712 dst
->edge
[dst
->n_edge
].dst
=
1713 graph_find_node(ctx
, dst
, edge
->dst
->dim
);
1714 dst
->edge
[dst
->n_edge
].map
= map
;
1715 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
1716 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
1723 /* Given a "src" dependence graph that contains the nodes from "dst"
1724 * that satisfy node_pred, copy the schedule computed in "src"
1725 * for those nodes back to "dst".
1727 static int copy_schedule(struct isl_sched_graph
*dst
,
1728 struct isl_sched_graph
*src
,
1729 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1734 for (i
= 0; i
< dst
->n
; ++i
) {
1735 if (!node_pred(&dst
->node
[i
], data
))
1737 isl_mat_free(dst
->node
[i
].sched
);
1738 isl_map_free(dst
->node
[i
].sched_map
);
1739 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
1740 dst
->node
[i
].sched_map
=
1741 isl_map_copy(src
->node
[src
->n
].sched_map
);
1745 dst
->n_total_row
= src
->n_total_row
;
1746 dst
->n_band
= src
->n_band
;
1751 /* Compute the maximal number of variables over all nodes.
1752 * This is the maximal number of linearly independent schedule
1753 * rows that we need to compute.
1754 * Just in case we end up in a part of the dependence graph
1755 * with only lower-dimensional domains, we make sure we will
1756 * compute the required amount of extra linearly independent rows.
1758 static int compute_maxvar(struct isl_sched_graph
*graph
)
1763 for (i
= 0; i
< graph
->n
; ++i
) {
1764 struct isl_sched_node
*node
= &graph
->node
[i
];
1767 if (node_update_cmap(node
) < 0)
1769 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
1770 if (nvar
> graph
->maxvar
)
1771 graph
->maxvar
= nvar
;
1777 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1778 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1780 /* Compute a schedule for a subgraph of "graph". In particular, for
1781 * the graph composed of nodes that satisfy node_pred and edges that
1782 * that satisfy edge_pred. The caller should precompute the number
1783 * of nodes and edges that satisfy these predicates and pass them along
1784 * as "n" and "n_edge".
1785 * If the subgraph is known to consist of a single component, then wcc should
1786 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1787 * Otherwise, we call compute_schedule, which will check whether the subgraph
1790 static int compute_sub_schedule(isl_ctx
*ctx
,
1791 struct isl_sched_graph
*graph
, int n
, int n_edge
,
1792 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
1793 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
1796 struct isl_sched_graph split
= { 0 };
1798 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
1800 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
1802 if (graph_init_table(ctx
, &split
) < 0)
1804 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
1806 if (graph_init_edge_table(ctx
, &split
) < 0)
1808 split
.n_row
= graph
->n_row
;
1809 split
.n_total_row
= graph
->n_total_row
;
1810 split
.n_band
= graph
->n_band
;
1811 split
.band_start
= graph
->band_start
;
1813 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
1815 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
1818 copy_schedule(graph
, &split
, node_pred
, data
);
1820 graph_free(ctx
, &split
);
1823 graph_free(ctx
, &split
);
1827 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
1829 return node
->scc
== scc
;
1832 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
1834 return node
->scc
<= scc
;
1837 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
1839 return node
->scc
>= scc
;
1842 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
1844 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
1847 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
1849 return edge
->dst
->scc
<= scc
;
1852 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
1854 return edge
->src
->scc
>= scc
;
1857 /* Pad the schedules of all nodes with zero rows such that in the end
1858 * they all have graph->n_total_row rows.
1859 * The extra rows don't belong to any band, so they get assigned band number -1.
1861 static int pad_schedule(struct isl_sched_graph
*graph
)
1865 for (i
= 0; i
< graph
->n
; ++i
) {
1866 struct isl_sched_node
*node
= &graph
->node
[i
];
1867 int row
= isl_mat_rows(node
->sched
);
1868 if (graph
->n_total_row
> row
) {
1869 isl_map_free(node
->sched_map
);
1870 node
->sched_map
= NULL
;
1872 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
1873 graph
->n_total_row
- row
);
1876 for (j
= row
; j
< graph
->n_total_row
; ++j
)
1883 /* Split the current graph into two parts and compute a schedule for each
1884 * part individually. In particular, one part consists of all SCCs up
1885 * to and including graph->src_scc, while the other part contains the other
1888 * The split is enforced in the schedule by constant rows with two different
1889 * values (0 and 1). These constant rows replace the previously computed rows
1890 * in the current band.
1891 * It would be possible to reuse them as the first rows in the next
1892 * band, but recomputing them may result in better rows as we are looking
1893 * at a smaller part of the dependence graph.
1894 * compute_split_schedule is only called when no zero-distance schedule row
1895 * could be found on the entire graph, so we wark the splitting row as
1896 * non zero-distance.
1898 * The band_id of the second group is set to n, where n is the number
1899 * of nodes in the first group. This ensures that the band_ids over
1900 * the two groups remain disjoint, even if either or both of the two
1901 * groups contain independent components.
1903 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1905 int i
, j
, n
, e1
, e2
;
1906 int n_total_row
, orig_total_row
;
1907 int n_band
, orig_band
;
1910 drop
= graph
->n_total_row
- graph
->band_start
;
1911 graph
->n_total_row
-= drop
;
1912 graph
->n_row
-= drop
;
1915 for (i
= 0; i
< graph
->n
; ++i
) {
1916 struct isl_sched_node
*node
= &graph
->node
[i
];
1917 int row
= isl_mat_rows(node
->sched
) - drop
;
1918 int cols
= isl_mat_cols(node
->sched
);
1919 int before
= node
->scc
<= graph
->src_scc
;
1924 isl_map_free(node
->sched_map
);
1925 node
->sched_map
= NULL
;
1926 node
->sched
= isl_mat_drop_rows(node
->sched
,
1927 graph
->band_start
, drop
);
1928 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1931 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1933 for (j
= 1; j
< cols
; ++j
)
1934 node
->sched
= isl_mat_set_element_si(node
->sched
,
1936 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1937 node
->zero
[graph
->n_total_row
] = 0;
1941 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1942 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
1944 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
1948 graph
->n_total_row
++;
1951 for (i
= 0; i
< graph
->n
; ++i
) {
1952 struct isl_sched_node
*node
= &graph
->node
[i
];
1953 if (node
->scc
> graph
->src_scc
)
1954 node
->band_id
[graph
->n_band
] = n
;
1957 orig_total_row
= graph
->n_total_row
;
1958 orig_band
= graph
->n_band
;
1959 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
1960 &node_scc_at_most
, &edge_dst_scc_at_most
,
1961 graph
->src_scc
, 0) < 0)
1963 n_total_row
= graph
->n_total_row
;
1964 graph
->n_total_row
= orig_total_row
;
1965 n_band
= graph
->n_band
;
1966 graph
->n_band
= orig_band
;
1967 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
1968 &node_scc_at_least
, &edge_src_scc_at_least
,
1969 graph
->src_scc
+ 1, 0) < 0)
1971 if (n_total_row
> graph
->n_total_row
)
1972 graph
->n_total_row
= n_total_row
;
1973 if (n_band
> graph
->n_band
)
1974 graph
->n_band
= n_band
;
1976 return pad_schedule(graph
);
1979 /* Compute the next band of the schedule after updating the dependence
1980 * relations based on the the current schedule.
1982 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1984 if (update_edges(ctx
, graph
) < 0)
1988 return compute_schedule(ctx
, graph
);
1991 /* Add constraints to graph->lp that force the dependence "map" (which
1992 * is part of the dependence relation of "edge")
1993 * to be respected and attempt to carry it, where the edge is one from
1994 * a node j to itself. "pos" is the sequence number of the given map.
1995 * That is, add constraints that enforce
1997 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
1998 * = c_j_x (y - x) >= e_i
2000 * for each (x,y) in R.
2001 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2002 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2003 * with each coefficient in c_j_x represented as a pair of non-negative
2006 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2007 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2010 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2012 isl_dim_map
*dim_map
;
2013 isl_basic_set
*coef
;
2014 struct isl_sched_node
*node
= edge
->src
;
2016 coef
= intra_coefficients(graph
, map
);
2018 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2020 total
= isl_basic_set_total_dim(graph
->lp
);
2021 dim_map
= isl_dim_map_alloc(ctx
, total
);
2022 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2023 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2024 isl_space_dim(dim
, isl_dim_set
), 1,
2026 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2027 isl_space_dim(dim
, isl_dim_set
), 1,
2029 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2030 coef
->n_eq
, coef
->n_ineq
);
2031 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2033 isl_space_free(dim
);
2038 /* Add constraints to graph->lp that force the dependence "map" (which
2039 * is part of the dependence relation of "edge")
2040 * to be respected and attempt to carry it, where the edge is one from
2041 * node j to node k. "pos" is the sequence number of the given map.
2042 * That is, add constraints that enforce
2044 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2046 * for each (x,y) in R.
2047 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2048 * of valid constraints for R and then plug in
2049 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2050 * with each coefficient (except e_i, c_k_0 and c_j_0)
2051 * represented as a pair of non-negative coefficients.
2053 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2054 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2057 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2059 isl_dim_map
*dim_map
;
2060 isl_basic_set
*coef
;
2061 struct isl_sched_node
*src
= edge
->src
;
2062 struct isl_sched_node
*dst
= edge
->dst
;
2064 coef
= inter_coefficients(graph
, map
);
2066 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2068 total
= isl_basic_set_total_dim(graph
->lp
);
2069 dim_map
= isl_dim_map_alloc(ctx
, total
);
2071 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2073 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2074 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2075 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2076 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2077 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2079 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2080 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2083 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2084 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2085 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2086 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2087 isl_space_dim(dim
, isl_dim_set
), 1,
2089 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2090 isl_space_dim(dim
, isl_dim_set
), 1,
2093 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2094 coef
->n_eq
, coef
->n_ineq
);
2095 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2097 isl_space_free(dim
);
2102 /* Add constraints to graph->lp that force all dependence
2103 * to be respected and attempt to carry it.
2105 static int add_all_constraints(struct isl_sched_graph
*graph
)
2111 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2112 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2113 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2114 isl_basic_map
*bmap
;
2117 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2118 map
= isl_map_from_basic_map(bmap
);
2120 if (edge
->src
== edge
->dst
&&
2121 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2123 if (edge
->src
!= edge
->dst
&&
2124 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2133 /* Count the number of equality and inequality constraints
2134 * that will be added to the carry_lp problem.
2135 * If once is set, then we count
2136 * each edge exactly once. Otherwise, we count as follows
2137 * validity -> 1 (>= 0)
2138 * validity+proximity -> 2 (>= 0 and upper bound)
2139 * proximity -> 2 (lower and upper bound)
2141 static int count_all_constraints(struct isl_sched_graph
*graph
,
2142 int *n_eq
, int *n_ineq
, int once
)
2146 *n_eq
= *n_ineq
= 0;
2147 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2148 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2149 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2150 isl_basic_map
*bmap
;
2153 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2154 map
= isl_map_from_basic_map(bmap
);
2156 if (count_map_constraints(graph
, edge
, map
,
2157 n_eq
, n_ineq
, once
) < 0)
2165 /* Construct an LP problem for finding schedule coefficients
2166 * such that the schedule carries as many dependences as possible.
2167 * In particular, for each dependence i, we bound the dependence distance
2168 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2169 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2170 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2171 * Note that if the dependence relation is a union of basic maps,
2172 * then we have to consider each basic map individually as it may only
2173 * be possible to carry the dependences expressed by some of those
2174 * basic maps and not all off them.
2175 * Below, we consider each of those basic maps as a separate "edge".
2177 * All variables of the LP are non-negative. The actual coefficients
2178 * may be negative, so each coefficient is represented as the difference
2179 * of two non-negative variables. The negative part always appears
2180 * immediately before the positive part.
2181 * Other than that, the variables have the following order
2183 * - sum of (1 - e_i) over all edges
2184 * - sum of positive and negative parts of all c_n coefficients
2185 * (unconstrained when computing non-parametric schedules)
2186 * - sum of positive and negative parts of all c_x coefficients
2191 * - positive and negative parts of c_i_n (if parametric)
2192 * - positive and negative parts of c_i_x
2194 * The constraints are those from the edges plus three equalities
2195 * to express the sums and n_edge inequalities to express e_i <= 1.
2197 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2207 for (i
= 0; i
< graph
->n_edge
; ++i
)
2208 n_edge
+= graph
->edge
[i
].map
->n
;
2211 for (i
= 0; i
< graph
->n
; ++i
) {
2212 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2213 node
->start
= total
;
2214 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2217 if (count_all_constraints(graph
, &n_eq
, &n_ineq
, 1) < 0)
2220 dim
= isl_space_set_alloc(ctx
, 0, total
);
2221 isl_basic_set_free(graph
->lp
);
2224 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2225 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2227 k
= isl_basic_set_alloc_equality(graph
->lp
);
2230 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2231 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2232 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2233 for (i
= 0; i
< n_edge
; ++i
)
2234 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2236 k
= isl_basic_set_alloc_equality(graph
->lp
);
2239 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2240 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2241 for (i
= 0; i
< graph
->n
; ++i
) {
2242 int pos
= 1 + graph
->node
[i
].start
+ 1;
2244 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2245 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2248 k
= isl_basic_set_alloc_equality(graph
->lp
);
2251 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2252 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2253 for (i
= 0; i
< graph
->n
; ++i
) {
2254 struct isl_sched_node
*node
= &graph
->node
[i
];
2255 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2257 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2258 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2261 for (i
= 0; i
< n_edge
; ++i
) {
2262 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2265 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2266 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2267 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2270 if (add_all_constraints(graph
) < 0)
2276 /* If the schedule_split_scaled option is set and if the linear
2277 * parts of the scheduling rows for all nodes in the graphs have
2278 * non-trivial common divisor, then split off the constant term
2279 * from the linear part.
2280 * The constant term is then placed in a separate band and
2281 * the linear part is reduced.
2283 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2289 if (!ctx
->opt
->schedule_split_scaled
)
2295 isl_int_init(gcd_i
);
2297 isl_int_set_si(gcd
, 0);
2299 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2301 for (i
= 0; i
< graph
->n
; ++i
) {
2302 struct isl_sched_node
*node
= &graph
->node
[i
];
2303 int cols
= isl_mat_cols(node
->sched
);
2305 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2306 isl_int_gcd(gcd
, gcd
, gcd_i
);
2309 isl_int_clear(gcd_i
);
2311 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2318 for (i
= 0; i
< graph
->n
; ++i
) {
2319 struct isl_sched_node
*node
= &graph
->node
[i
];
2321 isl_map_free(node
->sched_map
);
2322 node
->sched_map
= NULL
;
2323 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2326 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2327 node
->sched
->row
[row
][0], gcd
);
2328 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2329 node
->sched
->row
[row
][0], gcd
);
2330 isl_int_mul(node
->sched
->row
[row
][0],
2331 node
->sched
->row
[row
][0], gcd
);
2332 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2335 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2338 graph
->n_total_row
++;
2347 /* Construct a schedule row for each node such that as many dependences
2348 * as possible are carried and then continue with the next band.
2350 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2358 for (i
= 0; i
< graph
->n_edge
; ++i
)
2359 n_edge
+= graph
->edge
[i
].map
->n
;
2361 if (setup_carry_lp(ctx
, graph
) < 0)
2364 lp
= isl_basic_set_copy(graph
->lp
);
2365 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2369 if (sol
->size
== 0) {
2371 isl_die(ctx
, isl_error_internal
,
2372 "error in schedule construction", return -1);
2375 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2377 isl_die(ctx
, isl_error_unknown
,
2378 "unable to carry dependences", return -1);
2381 if (update_schedule(graph
, sol
, 0, 0) < 0)
2384 if (split_scaled(ctx
, graph
) < 0)
2387 return compute_next_band(ctx
, graph
);
2390 /* Are there any validity edges in the graph?
2392 static int has_validity_edges(struct isl_sched_graph
*graph
)
2396 for (i
= 0; i
< graph
->n_edge
; ++i
)
2397 if (graph
->edge
[i
].validity
)
2403 /* Should we apply a Feautrier step?
2404 * That is, did the user request the Feautrier algorithm and are
2405 * there any validity dependences (left)?
2407 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2409 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2412 return has_validity_edges(graph
);
2415 /* Compute a schedule for a connected dependence graph using Feautrier's
2416 * multi-dimensional scheduling algorithm.
2417 * The original algorithm is described in [1].
2418 * The main idea is to minimize the number of scheduling dimensions, by
2419 * trying to satisfy as many dependences as possible per scheduling dimension.
2421 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2422 * Problem, Part II: Multi-Dimensional Time.
2423 * In Intl. Journal of Parallel Programming, 1992.
2425 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2426 struct isl_sched_graph
*graph
)
2428 return carry_dependences(ctx
, graph
);
2431 /* Compute a schedule for a connected dependence graph.
2432 * We try to find a sequence of as many schedule rows as possible that result
2433 * in non-negative dependence distances (independent of the previous rows
2434 * in the sequence, i.e., such that the sequence is tilable).
2435 * If we can't find any more rows we either
2436 * - split between SCCs and start over (assuming we found an interesting
2437 * pair of SCCs between which to split)
2438 * - continue with the next band (assuming the current band has at least
2440 * - try to carry as many dependences as possible and continue with the next
2443 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2444 * as many validity dependences as possible. When all validity dependences
2445 * are satisfied we extend the schedule to a full-dimensional schedule.
2447 * If we manage to complete the schedule, we finish off by topologically
2448 * sorting the statements based on the remaining dependences.
2450 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2451 * outermost dimension in the current band to be zero distance. If this
2452 * turns out to be impossible, we fall back on the general scheme above
2453 * and try to carry as many dependences as possible.
2455 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2459 if (detect_sccs(graph
) < 0)
2463 if (compute_maxvar(graph
) < 0)
2466 if (need_feautrier_step(ctx
, graph
))
2467 return compute_schedule_wcc_feautrier(ctx
, graph
);
2469 if (ctx
->opt
->schedule_outer_zero_distance
)
2472 while (graph
->n_row
< graph
->maxvar
) {
2475 graph
->src_scc
= -1;
2476 graph
->dst_scc
= -1;
2478 if (setup_lp(ctx
, graph
, force_zero
) < 0)
2480 sol
= solve_lp(graph
);
2483 if (sol
->size
== 0) {
2485 if (!ctx
->opt
->schedule_maximize_band_depth
&&
2486 graph
->n_total_row
> graph
->band_start
)
2487 return compute_next_band(ctx
, graph
);
2488 if (graph
->src_scc
>= 0)
2489 return compute_split_schedule(ctx
, graph
);
2490 if (graph
->n_total_row
> graph
->band_start
)
2491 return compute_next_band(ctx
, graph
);
2492 return carry_dependences(ctx
, graph
);
2494 if (update_schedule(graph
, sol
, 1, 1) < 0)
2499 if (graph
->n_total_row
> graph
->band_start
)
2501 return sort_statements(ctx
, graph
);
2504 /* Add a row to the schedules that separates the SCCs and move
2507 static int split_on_scc(struct isl_sched_graph
*graph
)
2511 for (i
= 0; i
< graph
->n
; ++i
) {
2512 struct isl_sched_node
*node
= &graph
->node
[i
];
2513 int row
= isl_mat_rows(node
->sched
);
2515 isl_map_free(node
->sched_map
);
2516 node
->sched_map
= NULL
;
2517 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2518 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2522 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2525 graph
->n_total_row
++;
2531 /* Compute a schedule for each component (identified by node->scc)
2532 * of the dependence graph separately and then combine the results.
2533 * Depending on the setting of schedule_fuse, a component may be
2534 * either weakly or strongly connected.
2536 * The band_id is adjusted such that each component has a separate id.
2537 * Note that the band_id may have already been set to a value different
2538 * from zero by compute_split_schedule.
2540 static int compute_component_schedule(isl_ctx
*ctx
,
2541 struct isl_sched_graph
*graph
)
2545 int n_total_row
, orig_total_row
;
2546 int n_band
, orig_band
;
2548 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
)
2549 split_on_scc(graph
);
2552 orig_total_row
= graph
->n_total_row
;
2554 orig_band
= graph
->n_band
;
2555 for (i
= 0; i
< graph
->n
; ++i
)
2556 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
2557 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
2559 for (i
= 0; i
< graph
->n
; ++i
)
2560 if (graph
->node
[i
].scc
== wcc
)
2563 for (i
= 0; i
< graph
->n_edge
; ++i
)
2564 if (graph
->edge
[i
].src
->scc
== wcc
&&
2565 graph
->edge
[i
].dst
->scc
== wcc
)
2568 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
2570 &edge_scc_exactly
, wcc
, 1) < 0)
2572 if (graph
->n_total_row
> n_total_row
)
2573 n_total_row
= graph
->n_total_row
;
2574 graph
->n_total_row
= orig_total_row
;
2575 if (graph
->n_band
> n_band
)
2576 n_band
= graph
->n_band
;
2577 graph
->n_band
= orig_band
;
2580 graph
->n_total_row
= n_total_row
;
2581 graph
->n_band
= n_band
;
2583 return pad_schedule(graph
);
2586 /* Compute a schedule for the given dependence graph.
2587 * We first check if the graph is connected (through validity dependences)
2588 * and, if not, compute a schedule for each component separately.
2589 * If schedule_fuse is set to minimal fusion, then we check for strongly
2590 * connected components instead and compute a separate schedule for
2591 * each such strongly connected component.
2593 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2595 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
2596 if (detect_sccs(graph
) < 0)
2599 if (detect_wccs(graph
) < 0)
2604 return compute_component_schedule(ctx
, graph
);
2606 return compute_schedule_wcc(ctx
, graph
);
2609 /* Compute a schedule for the given union of domains that respects
2610 * all the validity dependences.
2611 * If the default isl scheduling algorithm is used, it tries to minimize
2612 * the dependence distances over the proximity dependences.
2613 * If Feautrier's scheduling algorithm is used, the proximity dependence
2614 * distances are only minimized during the extension to a full-dimensional
2617 __isl_give isl_schedule
*isl_union_set_compute_schedule(
2618 __isl_take isl_union_set
*domain
,
2619 __isl_take isl_union_map
*validity
,
2620 __isl_take isl_union_map
*proximity
)
2622 isl_ctx
*ctx
= isl_union_set_get_ctx(domain
);
2624 struct isl_sched_graph graph
= { 0 };
2625 isl_schedule
*sched
;
2627 domain
= isl_union_set_align_params(domain
,
2628 isl_union_map_get_space(validity
));
2629 domain
= isl_union_set_align_params(domain
,
2630 isl_union_map_get_space(proximity
));
2631 dim
= isl_union_set_get_space(domain
);
2632 validity
= isl_union_map_align_params(validity
, isl_space_copy(dim
));
2633 proximity
= isl_union_map_align_params(proximity
, dim
);
2638 graph
.n
= isl_union_set_n_set(domain
);
2641 if (graph_alloc(ctx
, &graph
, graph
.n
,
2642 isl_union_map_n_map(validity
) + isl_union_map_n_map(proximity
)) < 0)
2646 if (isl_union_set_foreach_set(domain
, &extract_node
, &graph
) < 0)
2648 if (graph_init_table(ctx
, &graph
) < 0)
2651 if (isl_union_map_foreach_map(validity
, &extract_edge
, &graph
) < 0)
2653 if (graph_init_edge_table(ctx
, &graph
) < 0)
2655 if (isl_union_map_foreach_map(proximity
, &extract_edge
, &graph
) < 0)
2658 if (compute_schedule(ctx
, &graph
) < 0)
2662 sched
= extract_schedule(&graph
, isl_union_set_get_space(domain
));
2664 graph_free(ctx
, &graph
);
2665 isl_union_set_free(domain
);
2666 isl_union_map_free(validity
);
2667 isl_union_map_free(proximity
);
2671 graph_free(ctx
, &graph
);
2672 isl_union_set_free(domain
);
2673 isl_union_map_free(validity
);
2674 isl_union_map_free(proximity
);
2678 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
2684 if (--sched
->ref
> 0)
2687 for (i
= 0; i
< sched
->n
; ++i
) {
2688 isl_map_free(sched
->node
[i
].sched
);
2689 free(sched
->node
[i
].band_end
);
2690 free(sched
->node
[i
].band_id
);
2691 free(sched
->node
[i
].zero
);
2693 isl_space_free(sched
->dim
);
2694 isl_band_list_free(sched
->band_forest
);
2699 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
2701 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
2704 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
2707 isl_union_map
*umap
;
2712 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
2713 for (i
= 0; i
< sched
->n
; ++i
)
2714 umap
= isl_union_map_add_map(umap
,
2715 isl_map_copy(sched
->node
[i
].sched
));
2720 static __isl_give isl_band_list
*construct_band_list(
2721 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2722 int band_nr
, int *parent_active
, int n_active
);
2724 /* Construct an isl_band structure for the band in the given schedule
2725 * with sequence number band_nr for the n_active nodes marked by active.
2726 * If the nodes don't have a band with the given sequence number,
2727 * then a band without members is created.
2729 * Because of the way the schedule is constructed, we know that
2730 * the position of the band inside the schedule of a node is the same
2731 * for all active nodes.
2733 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
2734 __isl_keep isl_band
*parent
,
2735 int band_nr
, int *active
, int n_active
)
2738 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2740 unsigned start
, end
;
2742 band
= isl_calloc_type(ctx
, isl_band
);
2747 band
->schedule
= schedule
;
2748 band
->parent
= parent
;
2750 for (i
= 0; i
< schedule
->n
; ++i
)
2751 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
2754 if (i
< schedule
->n
) {
2755 band
->children
= construct_band_list(schedule
, band
,
2756 band_nr
+ 1, active
, n_active
);
2757 if (!band
->children
)
2761 for (i
= 0; i
< schedule
->n
; ++i
)
2765 if (i
>= schedule
->n
)
2766 isl_die(ctx
, isl_error_internal
,
2767 "band without active statements", goto error
);
2769 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
2770 end
= band_nr
< schedule
->node
[i
].n_band
?
2771 schedule
->node
[i
].band_end
[band_nr
] : start
;
2772 band
->n
= end
- start
;
2774 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
2778 for (j
= 0; j
< band
->n
; ++j
)
2779 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
2781 band
->map
= isl_union_map_empty(isl_space_copy(schedule
->dim
));
2782 for (i
= 0; i
< schedule
->n
; ++i
) {
2789 map
= isl_map_copy(schedule
->node
[i
].sched
);
2790 n_out
= isl_map_dim(map
, isl_dim_out
);
2791 map
= isl_map_project_out(map
, isl_dim_out
, end
, n_out
- end
);
2792 map
= isl_map_project_out(map
, isl_dim_out
, 0, start
);
2793 band
->map
= isl_union_map_union(band
->map
,
2794 isl_union_map_from_map(map
));
2801 isl_band_free(band
);
2805 /* Construct a list of bands that start at the same position (with
2806 * sequence number band_nr) in the schedules of the nodes that
2807 * were active in the parent band.
2809 * A separate isl_band structure is created for each band_id
2810 * and for each node that does not have a band with sequence
2811 * number band_nr. In the latter case, a band without members
2813 * This ensures that if a band has any children, then each node
2814 * that was active in the band is active in exactly one of the children.
2816 static __isl_give isl_band_list
*construct_band_list(
2817 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2818 int band_nr
, int *parent_active
, int n_active
)
2821 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2824 isl_band_list
*list
;
2827 for (i
= 0; i
< n_active
; ++i
) {
2828 for (j
= 0; j
< schedule
->n
; ++j
) {
2829 if (!parent_active
[j
])
2831 if (schedule
->node
[j
].n_band
<= band_nr
)
2833 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
2839 for (j
= 0; j
< schedule
->n
; ++j
)
2840 if (schedule
->node
[j
].n_band
<= band_nr
)
2845 list
= isl_band_list_alloc(ctx
, n_band
);
2846 band
= construct_band(schedule
, parent
, band_nr
,
2847 parent_active
, n_active
);
2848 return isl_band_list_add(list
, band
);
2851 active
= isl_alloc_array(ctx
, int, schedule
->n
);
2855 list
= isl_band_list_alloc(ctx
, n_band
);
2857 for (i
= 0; i
< n_active
; ++i
) {
2861 for (j
= 0; j
< schedule
->n
; ++j
) {
2862 active
[j
] = parent_active
[j
] &&
2863 schedule
->node
[j
].n_band
> band_nr
&&
2864 schedule
->node
[j
].band_id
[band_nr
] == i
;
2871 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
2873 list
= isl_band_list_add(list
, band
);
2875 for (i
= 0; i
< schedule
->n
; ++i
) {
2877 if (!parent_active
[i
])
2879 if (schedule
->node
[i
].n_band
> band_nr
)
2881 for (j
= 0; j
< schedule
->n
; ++j
)
2883 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
2884 list
= isl_band_list_add(list
, band
);
2892 /* Construct a band forest representation of the schedule and
2893 * return the list of roots.
2895 static __isl_give isl_band_list
*construct_forest(
2896 __isl_keep isl_schedule
*schedule
)
2899 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2900 isl_band_list
*forest
;
2903 active
= isl_alloc_array(ctx
, int, schedule
->n
);
2907 for (i
= 0; i
< schedule
->n
; ++i
)
2910 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
2917 /* Return the roots of a band forest representation of the schedule.
2919 __isl_give isl_band_list
*isl_schedule_get_band_forest(
2920 __isl_keep isl_schedule
*schedule
)
2924 if (!schedule
->band_forest
)
2925 schedule
->band_forest
= construct_forest(schedule
);
2926 return isl_band_list_dup(schedule
->band_forest
);
2929 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
2930 __isl_keep isl_band_list
*list
);
2932 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
2933 __isl_keep isl_band
*band
)
2935 isl_band_list
*children
;
2937 p
= isl_printer_start_line(p
);
2938 p
= isl_printer_print_union_map(p
, band
->map
);
2939 p
= isl_printer_end_line(p
);
2941 if (!isl_band_has_children(band
))
2944 children
= isl_band_get_children(band
);
2946 p
= isl_printer_indent(p
, 4);
2947 p
= print_band_list(p
, children
);
2948 p
= isl_printer_indent(p
, -4);
2950 isl_band_list_free(children
);
2955 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
2956 __isl_keep isl_band_list
*list
)
2960 n
= isl_band_list_n_band(list
);
2961 for (i
= 0; i
< n
; ++i
) {
2963 band
= isl_band_list_get_band(list
, i
);
2964 p
= print_band(p
, band
);
2965 isl_band_free(band
);
2971 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
2972 __isl_keep isl_schedule
*schedule
)
2974 isl_band_list
*forest
;
2976 forest
= isl_schedule_get_band_forest(schedule
);
2978 p
= print_band_list(p
, forest
);
2980 isl_band_list_free(forest
);
2985 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
2987 isl_printer
*printer
;
2992 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
2993 printer
= isl_printer_print_schedule(printer
, schedule
);
2995 isl_printer_free(printer
);