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>
16 #include <isl/constraint.h>
17 #include <isl/schedule.h>
18 #include <isl_mat_private.h>
22 #include <isl_dim_map.h>
23 #include <isl_hmap_map_basic_set.h>
25 #include <isl_schedule_private.h>
26 #include <isl_band_private.h>
27 #include <isl_list_private.h>
28 #include <isl_options_private.h>
31 * The scheduling algorithm implemented in this file was inspired by
32 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
33 * Parallelization and Locality Optimization in the Polyhedral Model".
37 /* Internal information about a node that is used during the construction
39 * dim represents the space in which the domain lives
40 * sched is a matrix representation of the schedule being constructed
42 * sched_map is an isl_map representation of the same (partial) schedule
43 * sched_map may be NULL
44 * rank is the number of linearly independent rows in the linear part
46 * the columns of cmap represent a change of basis for the schedule
47 * coefficients; the first rank columns span the linear part of
49 * start is the first variable in the LP problem in the sequences that
50 * represents the schedule coefficients of this node
51 * nvar is the dimension of the domain
52 * nparam is the number of parameters or 0 if we are not constructing
53 * a parametric schedule
55 * scc is the index of SCC (or WCC) this node belongs to
57 * band contains the band index for each of the rows of the schedule.
58 * band_id is used to differentiate between separate bands at the same
59 * level within the same parent band, i.e., bands that are separated
60 * by the parent band or bands that are independent of each other.
61 * zero contains a boolean for each of the rows of the schedule,
62 * indicating whether the corresponding scheduling dimension results
63 * in zero dependence distances within its band and with respect
64 * to the proximity edges.
66 * index, min_index and on_stack are used during the SCC detection
67 * index represents the order in which nodes are visited.
68 * min_index is the index of the root of a (sub)component.
69 * on_stack indicates whether the node is currently on the stack.
71 struct isl_sched_node
{
93 static int node_has_dim(const void *entry
, const void *val
)
95 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
96 isl_space
*dim
= (isl_space
*)val
;
98 return isl_space_is_equal(node
->dim
, dim
);
101 /* An edge in the dependence graph. An edge may be used to
102 * ensure validity of the generated schedule, to minimize the dependence
105 * map is the dependence relation
106 * src is the source node
107 * dst is the sink node
108 * validity is set if the edge is used to ensure correctness
109 * proximity is set if the edge is used to minimize dependence distances
111 * For validity edges, start and end mark the sequence of inequality
112 * constraints in the LP problem that encode the validity constraint
113 * corresponding to this edge.
115 struct isl_sched_edge
{
118 struct isl_sched_node
*src
;
119 struct isl_sched_node
*dst
;
129 isl_edge_validity
= 0,
130 isl_edge_first
= isl_edge_validity
,
132 isl_edge_last
= isl_edge_proximity
135 /* Internal information about the dependence graph used during
136 * the construction of the schedule.
138 * intra_hmap is a cache, mapping dependence relations to their dual,
139 * for dependences from a node to itself
140 * inter_hmap is a cache, mapping dependence relations to their dual,
141 * for dependences between distinct nodes
143 * n is the number of nodes
144 * node is the list of nodes
145 * maxvar is the maximal number of variables over all nodes
146 * max_row is the allocated number of rows in the schedule
147 * n_row is the current (maximal) number of linearly independent
148 * rows in the node schedules
149 * n_total_row is the current number of rows in the node schedules
150 * n_band is the current number of completed bands
151 * band_start is the starting row in the node schedules of the current band
152 * root is set if this graph is the original dependence graph,
153 * without any splitting
155 * sorted contains a list of node indices sorted according to the
156 * SCC to which a node belongs
158 * n_edge is the number of edges
159 * edge is the list of edges
160 * max_edge contains the maximal number of edges of each type;
161 * in particular, it contains the number of edges in the inital graph.
162 * edge_table contains pointers into the edge array, hashed on the source
163 * and sink spaces; there is one such table for each type;
164 * a given edge may be referenced from more than one table
165 * if the corresponding relation appears in more than of the
166 * sets of dependences
168 * node_table contains pointers into the node array, hashed on the space
170 * region contains a list of variable sequences that should be non-trivial
172 * lp contains the (I)LP problem used to obtain new schedule rows
174 * src_scc and dst_scc are the source and sink SCCs of an edge with
175 * conflicting constraints
177 * scc, sp, index and stack are used during the detection of SCCs
178 * scc is the number of the next SCC
179 * stack contains the nodes on the path from the root to the current node
180 * sp is the stack pointer
181 * index is the index of the last node visited
183 struct isl_sched_graph
{
184 isl_hmap_map_basic_set
*intra_hmap
;
185 isl_hmap_map_basic_set
*inter_hmap
;
187 struct isl_sched_node
*node
;
201 struct isl_sched_edge
*edge
;
203 int max_edge
[isl_edge_last
+ 1];
204 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
206 struct isl_hash_table
*node_table
;
207 struct isl_region
*region
;
221 /* Initialize node_table based on the list of nodes.
223 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
227 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
228 if (!graph
->node_table
)
231 for (i
= 0; i
< graph
->n
; ++i
) {
232 struct isl_hash_table_entry
*entry
;
235 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
236 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
238 graph
->node
[i
].dim
, 1);
241 entry
->data
= &graph
->node
[i
];
247 /* Return a pointer to the node that lives within the given space,
248 * or NULL if there is no such node.
250 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
251 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
253 struct isl_hash_table_entry
*entry
;
256 hash
= isl_space_get_hash(dim
);
257 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
258 &node_has_dim
, dim
, 0);
260 return entry
? entry
->data
: NULL
;
263 static int edge_has_src_and_dst(const void *entry
, const void *val
)
265 const struct isl_sched_edge
*edge
= entry
;
266 const struct isl_sched_edge
*temp
= val
;
268 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
271 /* Add the given edge to graph->edge_table[type].
273 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
274 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
276 struct isl_hash_table_entry
*entry
;
279 hash
= isl_hash_init();
280 hash
= isl_hash_builtin(hash
, edge
->src
);
281 hash
= isl_hash_builtin(hash
, edge
->dst
);
282 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
283 &edge_has_src_and_dst
, edge
, 1);
291 /* Allocate the edge_tables based on the maximal number of edges of
294 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
298 for (i
= 0; i
<= isl_edge_last
; ++i
) {
299 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
301 if (!graph
->edge_table
[i
])
308 /* If graph->edge_table[type] contains an edge from the given source
309 * to the given destination, then return the hash table entry of this edge.
310 * Otherwise, return NULL.
312 static struct isl_hash_table_entry
*graph_find_edge_entry(
313 struct isl_sched_graph
*graph
,
314 enum isl_edge_type type
,
315 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
317 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
319 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
321 hash
= isl_hash_init();
322 hash
= isl_hash_builtin(hash
, temp
.src
);
323 hash
= isl_hash_builtin(hash
, temp
.dst
);
324 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
325 &edge_has_src_and_dst
, &temp
, 0);
329 /* If graph->edge_table[type] contains an edge from the given source
330 * to the given destination, then return this edge.
331 * Otherwise, return NULL.
333 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
334 enum isl_edge_type type
,
335 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
337 struct isl_hash_table_entry
*entry
;
339 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
346 /* Check whether the dependence graph has an edge of the give type
347 * between the given two nodes.
349 static int graph_has_edge(struct isl_sched_graph
*graph
,
350 enum isl_edge_type type
,
351 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
353 struct isl_sched_edge
*edge
;
356 edge
= graph_find_edge(graph
, type
, src
, dst
);
360 empty
= isl_map_plain_is_empty(edge
->map
);
367 /* If there is an edge from the given source to the given destination
368 * of any type then return this edge.
369 * Otherwise, return NULL.
371 static struct isl_sched_edge
*graph_find_any_edge(struct isl_sched_graph
*graph
,
372 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
374 enum isl_edge_type i
;
375 struct isl_sched_edge
*edge
;
377 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
378 edge
= graph_find_edge(graph
, i
, src
, dst
);
386 /* Remove the given edge from all the edge_tables that refer to it.
388 static void graph_remove_edge(struct isl_sched_graph
*graph
,
389 struct isl_sched_edge
*edge
)
391 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
392 enum isl_edge_type i
;
394 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
395 struct isl_hash_table_entry
*entry
;
397 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
400 if (entry
->data
!= edge
)
402 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
406 /* Check whether the dependence graph has any edge
407 * between the given two nodes.
409 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
410 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
412 enum isl_edge_type i
;
415 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
416 r
= graph_has_edge(graph
, i
, src
, dst
);
424 /* Check whether the dependence graph has a validity edge
425 * between the given two nodes.
427 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
428 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
430 return graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
433 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
434 int n_node
, int n_edge
)
439 graph
->n_edge
= n_edge
;
440 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
441 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
442 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
443 graph
->stack
= isl_alloc_array(ctx
, int, graph
->n
);
444 graph
->edge
= isl_calloc_array(ctx
,
445 struct isl_sched_edge
, graph
->n_edge
);
447 graph
->intra_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
448 graph
->inter_hmap
= isl_hmap_map_basic_set_alloc(ctx
, 2 * n_edge
);
450 if (!graph
->node
|| !graph
->region
|| !graph
->stack
|| !graph
->edge
||
454 for(i
= 0; i
< graph
->n
; ++i
)
455 graph
->sorted
[i
] = i
;
460 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
464 isl_hmap_map_basic_set_free(ctx
, graph
->intra_hmap
);
465 isl_hmap_map_basic_set_free(ctx
, graph
->inter_hmap
);
467 for (i
= 0; i
< graph
->n
; ++i
) {
468 isl_space_free(graph
->node
[i
].dim
);
469 isl_mat_free(graph
->node
[i
].sched
);
470 isl_map_free(graph
->node
[i
].sched_map
);
471 isl_mat_free(graph
->node
[i
].cmap
);
473 free(graph
->node
[i
].band
);
474 free(graph
->node
[i
].band_id
);
475 free(graph
->node
[i
].zero
);
480 for (i
= 0; i
< graph
->n_edge
; ++i
)
481 isl_map_free(graph
->edge
[i
].map
);
485 for (i
= 0; i
<= isl_edge_last
; ++i
)
486 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
487 isl_hash_table_free(ctx
, graph
->node_table
);
488 isl_basic_set_free(graph
->lp
);
491 /* For each "set" on which this function is called, increment
492 * graph->n by one and update graph->maxvar.
494 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
496 struct isl_sched_graph
*graph
= user
;
497 int nvar
= isl_set_dim(set
, isl_dim_set
);
500 if (nvar
> graph
->maxvar
)
501 graph
->maxvar
= nvar
;
508 /* Compute the number of rows that should be allocated for the schedule.
509 * The graph can be split at most "n - 1" times, there can be at most
510 * two rows for each dimension in the iteration domains (in particular,
511 * we usually have one row, but it may be split by split_scaled),
512 * and there can be one extra row for ordering the statements.
513 * Note that if we have actually split "n - 1" times, then no ordering
514 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
516 static int compute_max_row(struct isl_sched_graph
*graph
,
517 __isl_keep isl_union_set
*domain
)
521 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
523 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
528 /* Add a new node to the graph representing the given set.
530 static int extract_node(__isl_take isl_set
*set
, void *user
)
536 struct isl_sched_graph
*graph
= user
;
537 int *band
, *band_id
, *zero
;
539 ctx
= isl_set_get_ctx(set
);
540 dim
= isl_set_get_space(set
);
542 nvar
= isl_space_dim(dim
, isl_dim_set
);
543 nparam
= isl_space_dim(dim
, isl_dim_param
);
544 if (!ctx
->opt
->schedule_parametric
)
546 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
547 graph
->node
[graph
->n
].dim
= dim
;
548 graph
->node
[graph
->n
].nvar
= nvar
;
549 graph
->node
[graph
->n
].nparam
= nparam
;
550 graph
->node
[graph
->n
].sched
= sched
;
551 graph
->node
[graph
->n
].sched_map
= NULL
;
552 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
553 graph
->node
[graph
->n
].band
= band
;
554 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
555 graph
->node
[graph
->n
].band_id
= band_id
;
556 zero
= isl_calloc_array(ctx
, int, graph
->max_row
);
557 graph
->node
[graph
->n
].zero
= zero
;
560 if (!sched
|| !band
|| !band_id
|| !zero
)
566 struct isl_extract_edge_data
{
567 enum isl_edge_type type
;
568 struct isl_sched_graph
*graph
;
571 /* Add a new edge to the graph based on the given map
572 * and add it to data->graph->edge_table[data->type].
573 * If a dependence relation of a given type happens to be identical
574 * to one of the dependence relations of a type that was added before,
575 * then we don't create a new edge, but instead mark the original edge
576 * as also representing a dependence of the current type.
578 static int extract_edge(__isl_take isl_map
*map
, void *user
)
580 isl_ctx
*ctx
= isl_map_get_ctx(map
);
581 struct isl_extract_edge_data
*data
= user
;
582 struct isl_sched_graph
*graph
= data
->graph
;
583 struct isl_sched_node
*src
, *dst
;
585 struct isl_sched_edge
*edge
;
588 dim
= isl_space_domain(isl_map_get_space(map
));
589 src
= graph_find_node(ctx
, graph
, dim
);
591 dim
= isl_space_range(isl_map_get_space(map
));
592 dst
= graph_find_node(ctx
, graph
, dim
);
600 graph
->edge
[graph
->n_edge
].src
= src
;
601 graph
->edge
[graph
->n_edge
].dst
= dst
;
602 graph
->edge
[graph
->n_edge
].map
= map
;
603 if (data
->type
== isl_edge_validity
) {
604 graph
->edge
[graph
->n_edge
].validity
= 1;
605 graph
->edge
[graph
->n_edge
].proximity
= 0;
607 if (data
->type
== isl_edge_proximity
) {
608 graph
->edge
[graph
->n_edge
].validity
= 0;
609 graph
->edge
[graph
->n_edge
].proximity
= 1;
613 edge
= graph_find_any_edge(graph
, src
, dst
);
615 return graph_edge_table_add(ctx
, graph
, data
->type
,
616 &graph
->edge
[graph
->n_edge
- 1]);
617 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
621 return graph_edge_table_add(ctx
, graph
, data
->type
,
622 &graph
->edge
[graph
->n_edge
- 1]);
625 edge
->validity
|= graph
->edge
[graph
->n_edge
].validity
;
626 edge
->proximity
|= graph
->edge
[graph
->n_edge
].proximity
;
629 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
632 /* Check whether there is a validity dependence from src to dst,
633 * forcing dst to follow src (if weak is not set).
634 * If weak is set, then check if there is any dependence from src to dst.
636 static int node_follows(struct isl_sched_graph
*graph
,
637 struct isl_sched_node
*dst
, struct isl_sched_node
*src
, int weak
)
640 return graph_has_any_edge(graph
, src
, dst
);
642 return graph_has_validity_edge(graph
, src
, dst
);
645 /* Perform Tarjan's algorithm for computing the strongly connected components
646 * in the dependence graph (only validity edges).
647 * If weak is set, we consider the graph to be undirected and
648 * we effectively compute the (weakly) connected components.
649 * Additionally, we also consider other edges when weak is set.
651 static int detect_sccs_tarjan(struct isl_sched_graph
*g
, int i
, int weak
)
655 g
->node
[i
].index
= g
->index
;
656 g
->node
[i
].min_index
= g
->index
;
657 g
->node
[i
].on_stack
= 1;
659 g
->stack
[g
->sp
++] = i
;
661 for (j
= g
->n
- 1; j
>= 0; --j
) {
666 if (g
->node
[j
].index
>= 0 &&
667 (!g
->node
[j
].on_stack
||
668 g
->node
[j
].index
> g
->node
[i
].min_index
))
671 f
= node_follows(g
, &g
->node
[i
], &g
->node
[j
], weak
);
675 f
= node_follows(g
, &g
->node
[j
], &g
->node
[i
], weak
);
681 if (g
->node
[j
].index
< 0) {
682 detect_sccs_tarjan(g
, j
, weak
);
683 if (g
->node
[j
].min_index
< g
->node
[i
].min_index
)
684 g
->node
[i
].min_index
= g
->node
[j
].min_index
;
685 } else if (g
->node
[j
].index
< g
->node
[i
].min_index
)
686 g
->node
[i
].min_index
= g
->node
[j
].index
;
689 if (g
->node
[i
].index
!= g
->node
[i
].min_index
)
693 j
= g
->stack
[--g
->sp
];
694 g
->node
[j
].on_stack
= 0;
695 g
->node
[j
].scc
= g
->scc
;
702 static int detect_ccs(struct isl_sched_graph
*graph
, int weak
)
709 for (i
= graph
->n
- 1; i
>= 0; --i
)
710 graph
->node
[i
].index
= -1;
712 for (i
= graph
->n
- 1; i
>= 0; --i
) {
713 if (graph
->node
[i
].index
>= 0)
715 if (detect_sccs_tarjan(graph
, i
, weak
) < 0)
722 /* Apply Tarjan's algorithm to detect the strongly connected components
723 * in the dependence graph.
725 static int detect_sccs(struct isl_sched_graph
*graph
)
727 return detect_ccs(graph
, 0);
730 /* Apply Tarjan's algorithm to detect the (weakly) connected components
731 * in the dependence graph.
733 static int detect_wccs(struct isl_sched_graph
*graph
)
735 return detect_ccs(graph
, 1);
738 static int cmp_scc(const void *a
, const void *b
, void *data
)
740 struct isl_sched_graph
*graph
= data
;
744 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
747 /* Sort the elements of graph->sorted according to the corresponding SCCs.
749 static int sort_sccs(struct isl_sched_graph
*graph
)
751 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
754 /* Given a dependence relation R from a node to itself,
755 * construct the set of coefficients of valid constraints for elements
756 * in that dependence relation.
757 * In particular, the result contains tuples of coefficients
758 * c_0, c_n, c_x such that
760 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
764 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
766 * We choose here to compute the dual of delta R.
767 * Alternatively, we could have computed the dual of R, resulting
768 * in a set of tuples c_0, c_n, c_x, c_y, and then
769 * plugged in (c_0, c_n, c_x, -c_x).
771 static __isl_give isl_basic_set
*intra_coefficients(
772 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
774 isl_ctx
*ctx
= isl_map_get_ctx(map
);
778 if (isl_hmap_map_basic_set_has(ctx
, graph
->intra_hmap
, map
))
779 return isl_hmap_map_basic_set_get(ctx
, graph
->intra_hmap
, map
);
781 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
782 coef
= isl_set_coefficients(delta
);
783 isl_hmap_map_basic_set_set(ctx
, graph
->intra_hmap
, map
,
784 isl_basic_set_copy(coef
));
789 /* Given a dependence relation R, * construct the set of coefficients
790 * of valid constraints for elements in that dependence relation.
791 * In particular, the result contains tuples of coefficients
792 * c_0, c_n, c_x, c_y such that
794 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
797 static __isl_give isl_basic_set
*inter_coefficients(
798 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
800 isl_ctx
*ctx
= isl_map_get_ctx(map
);
804 if (isl_hmap_map_basic_set_has(ctx
, graph
->inter_hmap
, map
))
805 return isl_hmap_map_basic_set_get(ctx
, graph
->inter_hmap
, map
);
807 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
808 coef
= isl_set_coefficients(set
);
809 isl_hmap_map_basic_set_set(ctx
, graph
->inter_hmap
, map
,
810 isl_basic_set_copy(coef
));
815 /* Add constraints to graph->lp that force validity for the given
816 * dependence from a node i to itself.
817 * That is, add constraints that enforce
819 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
820 * = c_i_x (y - x) >= 0
822 * for each (x,y) in R.
823 * We obtain general constraints on coefficients (c_0, c_n, c_x)
824 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
825 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
826 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
828 * Actually, we do not construct constraints for the c_i_x themselves,
829 * but for the coefficients of c_i_x written as a linear combination
830 * of the columns in node->cmap.
832 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
833 struct isl_sched_edge
*edge
)
836 isl_map
*map
= isl_map_copy(edge
->map
);
837 isl_ctx
*ctx
= isl_map_get_ctx(map
);
839 isl_dim_map
*dim_map
;
841 struct isl_sched_node
*node
= edge
->src
;
843 coef
= intra_coefficients(graph
, map
);
845 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
847 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
848 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
850 total
= isl_basic_set_total_dim(graph
->lp
);
851 dim_map
= isl_dim_map_alloc(ctx
, total
);
852 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
853 isl_space_dim(dim
, isl_dim_set
), 1,
855 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
856 isl_space_dim(dim
, isl_dim_set
), 1,
858 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
859 coef
->n_eq
, coef
->n_ineq
);
860 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
867 /* Add constraints to graph->lp that force validity for the given
868 * dependence from node i to node j.
869 * That is, add constraints that enforce
871 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
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 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
877 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
878 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
879 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
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_validity_constraints(struct isl_sched_graph
*graph
,
886 struct isl_sched_edge
*edge
)
889 isl_map
*map
= isl_map_copy(edge
->map
);
890 isl_ctx
*ctx
= isl_map_get_ctx(map
);
892 isl_dim_map
*dim_map
;
894 struct isl_sched_node
*src
= edge
->src
;
895 struct isl_sched_node
*dst
= edge
->dst
;
897 coef
= inter_coefficients(graph
, map
);
899 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
901 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
902 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
903 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
904 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
905 isl_mat_copy(dst
->cmap
));
907 total
= isl_basic_set_total_dim(graph
->lp
);
908 dim_map
= isl_dim_map_alloc(ctx
, total
);
910 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
911 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
912 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
913 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
914 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
916 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
917 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
920 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
921 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
922 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
923 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
924 isl_space_dim(dim
, isl_dim_set
), 1,
926 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
927 isl_space_dim(dim
, isl_dim_set
), 1,
930 edge
->start
= graph
->lp
->n_ineq
;
931 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
932 coef
->n_eq
, coef
->n_ineq
);
933 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
936 edge
->end
= graph
->lp
->n_ineq
;
941 /* Add constraints to graph->lp that bound the dependence distance for the given
942 * dependence from a node i to itself.
943 * If s = 1, we add the constraint
945 * c_i_x (y - x) <= m_0 + m_n n
949 * -c_i_x (y - x) + m_0 + m_n n >= 0
951 * for each (x,y) in R.
952 * If s = -1, we add the constraint
954 * -c_i_x (y - x) <= m_0 + m_n n
958 * c_i_x (y - x) + m_0 + m_n n >= 0
960 * for each (x,y) in R.
961 * We obtain general constraints on coefficients (c_0, c_n, c_x)
962 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
963 * with each coefficient (except m_0) represented as a pair of non-negative
966 * Actually, we do not construct constraints for the c_i_x themselves,
967 * but for the coefficients of c_i_x written as a linear combination
968 * of the columns in node->cmap.
970 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
971 struct isl_sched_edge
*edge
, int s
)
975 isl_map
*map
= isl_map_copy(edge
->map
);
976 isl_ctx
*ctx
= isl_map_get_ctx(map
);
978 isl_dim_map
*dim_map
;
980 struct isl_sched_node
*node
= edge
->src
;
982 coef
= intra_coefficients(graph
, map
);
984 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
986 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
987 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
989 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
990 total
= isl_basic_set_total_dim(graph
->lp
);
991 dim_map
= isl_dim_map_alloc(ctx
, total
);
992 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
993 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
994 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
995 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
996 isl_space_dim(dim
, isl_dim_set
), 1,
998 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
999 isl_space_dim(dim
, isl_dim_set
), 1,
1001 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1002 coef
->n_eq
, coef
->n_ineq
);
1003 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1005 isl_space_free(dim
);
1010 /* Add constraints to graph->lp that bound the dependence distance for the given
1011 * dependence from node i to node j.
1012 * If s = 1, we add the constraint
1014 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1019 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1022 * for each (x,y) in R.
1023 * If s = -1, we add the constraint
1025 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1030 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1033 * for each (x,y) in R.
1034 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1035 * of valid constraints for R and then plug in
1036 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1038 * with each coefficient (except m_0, c_j_0 and c_i_0)
1039 * represented as a pair of non-negative coefficients.
1041 * Actually, we do not construct constraints for the c_*_x themselves,
1042 * but for the coefficients of c_*_x written as a linear combination
1043 * of the columns in node->cmap.
1045 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1046 struct isl_sched_edge
*edge
, int s
)
1050 isl_map
*map
= isl_map_copy(edge
->map
);
1051 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1053 isl_dim_map
*dim_map
;
1054 isl_basic_set
*coef
;
1055 struct isl_sched_node
*src
= edge
->src
;
1056 struct isl_sched_node
*dst
= edge
->dst
;
1058 coef
= inter_coefficients(graph
, map
);
1060 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1062 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1063 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1064 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1065 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1066 isl_mat_copy(dst
->cmap
));
1068 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1069 total
= isl_basic_set_total_dim(graph
->lp
);
1070 dim_map
= isl_dim_map_alloc(ctx
, total
);
1072 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1073 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1074 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1076 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1077 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1078 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1079 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1080 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1082 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1083 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1086 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1087 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1088 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1089 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1090 isl_space_dim(dim
, isl_dim_set
), 1,
1092 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1093 isl_space_dim(dim
, isl_dim_set
), 1,
1096 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1097 coef
->n_eq
, coef
->n_ineq
);
1098 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1100 isl_space_free(dim
);
1105 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1109 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1110 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1111 if (!edge
->validity
)
1113 if (edge
->src
!= edge
->dst
)
1115 if (add_intra_validity_constraints(graph
, edge
) < 0)
1119 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1120 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1121 if (!edge
->validity
)
1123 if (edge
->src
== edge
->dst
)
1125 if (add_inter_validity_constraints(graph
, edge
) < 0)
1132 /* Add constraints to graph->lp that bound the dependence distance
1133 * for all dependence relations.
1134 * If a given proximity dependence is identical to a validity
1135 * dependence, then the dependence distance is already bounded
1136 * from below (by zero), so we only need to bound the distance
1138 * Otherwise, we need to bound the distance both from above and from below.
1140 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1144 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1145 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1146 if (!edge
->proximity
)
1148 if (edge
->src
== edge
->dst
&&
1149 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
1151 if (edge
->src
!= edge
->dst
&&
1152 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
1156 if (edge
->src
== edge
->dst
&&
1157 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
1159 if (edge
->src
!= edge
->dst
&&
1160 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1167 /* Compute a basis for the rows in the linear part of the schedule
1168 * and extend this basis to a full basis. The remaining rows
1169 * can then be used to force linear independence from the rows
1172 * In particular, given the schedule rows S, we compute
1176 * with H the Hermite normal form of S. That is, all but the
1177 * first rank columns of Q are zero and so each row in S is
1178 * a linear combination of the first rank rows of Q.
1179 * The matrix Q is then transposed because we will write the
1180 * coefficients of the next schedule row as a column vector s
1181 * and express this s as a linear combination s = Q c of the
1184 static int node_update_cmap(struct isl_sched_node
*node
)
1187 int n_row
= isl_mat_rows(node
->sched
);
1189 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1190 1 + node
->nparam
, node
->nvar
);
1192 H
= isl_mat_left_hermite(H
, 0, NULL
, &Q
);
1193 isl_mat_free(node
->cmap
);
1194 node
->cmap
= isl_mat_transpose(Q
);
1195 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1198 if (!node
->cmap
|| node
->rank
< 0)
1203 /* Count the number of equality and inequality constraints
1204 * that will be added for the given map.
1205 * If carry is set, then we are counting the number of (validity)
1206 * constraints that will be added in setup_carry_lp and we count
1207 * each edge exactly once. Otherwise, we count as follows
1208 * validity -> 1 (>= 0)
1209 * validity+proximity -> 2 (>= 0 and upper bound)
1210 * proximity -> 2 (lower and upper bound)
1212 static int count_map_constraints(struct isl_sched_graph
*graph
,
1213 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1214 int *n_eq
, int *n_ineq
, int carry
)
1216 isl_basic_set
*coef
;
1217 int f
= carry
? 1 : edge
->proximity
? 2 : 1;
1219 if (carry
&& !edge
->validity
) {
1224 if (edge
->src
== edge
->dst
)
1225 coef
= intra_coefficients(graph
, map
);
1227 coef
= inter_coefficients(graph
, map
);
1230 *n_eq
+= f
* coef
->n_eq
;
1231 *n_ineq
+= f
* coef
->n_ineq
;
1232 isl_basic_set_free(coef
);
1237 /* Count the number of equality and inequality constraints
1238 * that will be added to the main lp problem.
1239 * We count as follows
1240 * validity -> 1 (>= 0)
1241 * validity+proximity -> 2 (>= 0 and upper bound)
1242 * proximity -> 2 (lower and upper bound)
1244 static int count_constraints(struct isl_sched_graph
*graph
,
1245 int *n_eq
, int *n_ineq
)
1249 *n_eq
= *n_ineq
= 0;
1250 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1251 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1252 isl_map
*map
= isl_map_copy(edge
->map
);
1254 if (count_map_constraints(graph
, edge
, map
,
1255 n_eq
, n_ineq
, 0) < 0)
1262 /* Add constraints that bound the values of the variable and parameter
1263 * coefficients of the schedule.
1265 * The maximal value of the coefficients is defined by the option
1266 * 'schedule_max_coefficient'.
1268 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1269 struct isl_sched_graph
*graph
)
1272 int max_coefficient
;
1275 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1277 if (max_coefficient
== -1)
1280 total
= isl_basic_set_total_dim(graph
->lp
);
1282 for (i
= 0; i
< graph
->n
; ++i
) {
1283 struct isl_sched_node
*node
= &graph
->node
[i
];
1284 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1286 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1289 dim
= 1 + node
->start
+ 1 + j
;
1290 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1291 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1292 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1299 /* Construct an ILP problem for finding schedule coefficients
1300 * that result in non-negative, but small dependence distances
1301 * over all dependences.
1302 * In particular, the dependence distances over proximity edges
1303 * are bounded by m_0 + m_n n and we compute schedule coefficients
1304 * with small values (preferably zero) of m_n and m_0.
1306 * All variables of the ILP are non-negative. The actual coefficients
1307 * may be negative, so each coefficient is represented as the difference
1308 * of two non-negative variables. The negative part always appears
1309 * immediately before the positive part.
1310 * Other than that, the variables have the following order
1312 * - sum of positive and negative parts of m_n coefficients
1314 * - sum of positive and negative parts of all c_n coefficients
1315 * (unconstrained when computing non-parametric schedules)
1316 * - sum of positive and negative parts of all c_x coefficients
1317 * - positive and negative parts of m_n coefficients
1320 * - positive and negative parts of c_i_n (if parametric)
1321 * - positive and negative parts of c_i_x
1323 * The c_i_x are not represented directly, but through the columns of
1324 * node->cmap. That is, the computed values are for variable t_i_x
1325 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1327 * The constraints are those from the edges plus two or three equalities
1328 * to express the sums.
1330 * If force_zero is set, then we add equalities to ensure that
1331 * the sum of the m_n coefficients and m_0 are both zero.
1333 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1344 int max_constant_term
;
1345 int max_coefficient
;
1347 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1348 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1350 parametric
= ctx
->opt
->schedule_parametric
;
1351 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1353 total
= param_pos
+ 2 * nparam
;
1354 for (i
= 0; i
< graph
->n
; ++i
) {
1355 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1356 if (node_update_cmap(node
) < 0)
1358 node
->start
= total
;
1359 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1362 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1365 dim
= isl_space_set_alloc(ctx
, 0, total
);
1366 isl_basic_set_free(graph
->lp
);
1367 n_eq
+= 2 + parametric
+ force_zero
;
1368 if (max_constant_term
!= -1)
1370 if (max_coefficient
!= -1)
1371 for (i
= 0; i
< graph
->n
; ++i
)
1372 n_ineq
+= 2 * graph
->node
[i
].nparam
+
1373 2 * graph
->node
[i
].nvar
;
1375 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1377 k
= isl_basic_set_alloc_equality(graph
->lp
);
1380 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1382 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1383 for (i
= 0; i
< 2 * nparam
; ++i
)
1384 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1387 k
= isl_basic_set_alloc_equality(graph
->lp
);
1390 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1391 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1395 k
= isl_basic_set_alloc_equality(graph
->lp
);
1398 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1399 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1400 for (i
= 0; i
< graph
->n
; ++i
) {
1401 int pos
= 1 + graph
->node
[i
].start
+ 1;
1403 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1404 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1408 k
= isl_basic_set_alloc_equality(graph
->lp
);
1411 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1412 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1413 for (i
= 0; i
< graph
->n
; ++i
) {
1414 struct isl_sched_node
*node
= &graph
->node
[i
];
1415 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1417 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1418 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1421 if (max_constant_term
!= -1)
1422 for (i
= 0; i
< graph
->n
; ++i
) {
1423 struct isl_sched_node
*node
= &graph
->node
[i
];
1424 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1427 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1428 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1429 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1432 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1434 if (add_all_validity_constraints(graph
) < 0)
1436 if (add_all_proximity_constraints(graph
) < 0)
1442 /* Analyze the conflicting constraint found by
1443 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1444 * constraint of one of the edges between distinct nodes, living, moreover
1445 * in distinct SCCs, then record the source and sink SCC as this may
1446 * be a good place to cut between SCCs.
1448 static int check_conflict(int con
, void *user
)
1451 struct isl_sched_graph
*graph
= user
;
1453 if (graph
->src_scc
>= 0)
1456 con
-= graph
->lp
->n_eq
;
1458 if (con
>= graph
->lp
->n_ineq
)
1461 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1462 if (!graph
->edge
[i
].validity
)
1464 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1466 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1468 if (graph
->edge
[i
].start
> con
)
1470 if (graph
->edge
[i
].end
<= con
)
1472 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1473 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1479 /* Check whether the next schedule row of the given node needs to be
1480 * non-trivial. Lower-dimensional domains may have some trivial rows,
1481 * but as soon as the number of remaining required non-trivial rows
1482 * is as large as the number or remaining rows to be computed,
1483 * all remaining rows need to be non-trivial.
1485 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1487 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1490 /* Solve the ILP problem constructed in setup_lp.
1491 * For each node such that all the remaining rows of its schedule
1492 * need to be non-trivial, we construct a non-triviality region.
1493 * This region imposes that the next row is independent of previous rows.
1494 * In particular the coefficients c_i_x are represented by t_i_x
1495 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1496 * its first columns span the rows of the previously computed part
1497 * of the schedule. The non-triviality region enforces that at least
1498 * one of the remaining components of t_i_x is non-zero, i.e.,
1499 * that the new schedule row depends on at least one of the remaining
1502 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1508 for (i
= 0; i
< graph
->n
; ++i
) {
1509 struct isl_sched_node
*node
= &graph
->node
[i
];
1510 int skip
= node
->rank
;
1511 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1512 if (needs_row(graph
, node
))
1513 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1515 graph
->region
[i
].len
= 0;
1517 lp
= isl_basic_set_copy(graph
->lp
);
1518 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1519 graph
->region
, &check_conflict
, graph
);
1523 /* Update the schedules of all nodes based on the given solution
1524 * of the LP problem.
1525 * The new row is added to the current band.
1526 * All possibly negative coefficients are encoded as a difference
1527 * of two non-negative variables, so we need to perform the subtraction
1528 * here. Moreover, if use_cmap is set, then the solution does
1529 * not refer to the actual coefficients c_i_x, but instead to variables
1530 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1531 * In this case, we then also need to perform this multiplication
1532 * to obtain the values of c_i_x.
1534 * If check_zero is set, then the first two coordinates of sol are
1535 * assumed to correspond to the dependence distance. If these two
1536 * coordinates are zero, then the corresponding scheduling dimension
1537 * is marked as being zero distance.
1539 static int update_schedule(struct isl_sched_graph
*graph
,
1540 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1544 isl_vec
*csol
= NULL
;
1549 isl_die(sol
->ctx
, isl_error_internal
,
1550 "no solution found", goto error
);
1553 zero
= isl_int_is_zero(sol
->el
[1]) &&
1554 isl_int_is_zero(sol
->el
[2]);
1556 for (i
= 0; i
< graph
->n
; ++i
) {
1557 struct isl_sched_node
*node
= &graph
->node
[i
];
1558 int pos
= node
->start
;
1559 int row
= isl_mat_rows(node
->sched
);
1562 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1566 isl_map_free(node
->sched_map
);
1567 node
->sched_map
= NULL
;
1568 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1571 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1573 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1574 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1575 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1576 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1577 for (j
= 0; j
< node
->nparam
; ++j
)
1578 node
->sched
= isl_mat_set_element(node
->sched
,
1579 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1580 for (j
= 0; j
< node
->nvar
; ++j
)
1581 isl_int_set(csol
->el
[j
],
1582 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1584 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1588 for (j
= 0; j
< node
->nvar
; ++j
)
1589 node
->sched
= isl_mat_set_element(node
->sched
,
1590 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1591 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1592 node
->zero
[graph
->n_total_row
] = zero
;
1598 graph
->n_total_row
++;
1607 /* Convert node->sched into a multi_aff and return this multi_aff.
1609 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
1610 struct isl_sched_node
*node
)
1614 isl_local_space
*ls
;
1620 nrow
= isl_mat_rows(node
->sched
);
1621 ncol
= isl_mat_cols(node
->sched
) - 1;
1622 space
= isl_space_from_domain(isl_space_copy(node
->dim
));
1623 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
1624 ma
= isl_multi_aff_zero(space
);
1625 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
1629 for (i
= 0; i
< nrow
; ++i
) {
1630 aff
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1631 isl_mat_get_element(node
->sched
, i
, 0, &v
);
1632 aff
= isl_aff_set_constant(aff
, v
);
1633 for (j
= 0; j
< node
->nparam
; ++j
) {
1634 isl_mat_get_element(node
->sched
, i
, 1 + j
, &v
);
1635 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
1637 for (j
= 0; j
< node
->nvar
; ++j
) {
1638 isl_mat_get_element(node
->sched
,
1639 i
, 1 + node
->nparam
+ j
, &v
);
1640 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
1642 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
1647 isl_local_space_free(ls
);
1652 /* Convert node->sched into a map and return this map.
1654 * The result is cached in node->sched_map, which needs to be released
1655 * whenever node->sched is updated.
1657 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1659 if (!node
->sched_map
) {
1662 ma
= node_extract_schedule_multi_aff(node
);
1663 node
->sched_map
= isl_map_from_multi_aff(ma
);
1666 return isl_map_copy(node
->sched_map
);
1669 /* Update the given dependence relation based on the current schedule.
1670 * That is, intersect the dependence relation with a map expressing
1671 * that source and sink are executed within the same iteration of
1672 * the current schedule.
1673 * This is not the most efficient way, but this shouldn't be a critical
1676 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1677 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1679 isl_map
*src_sched
, *dst_sched
, *id
;
1681 src_sched
= node_extract_schedule(src
);
1682 dst_sched
= node_extract_schedule(dst
);
1683 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1684 return isl_map_intersect(map
, id
);
1687 /* Update the dependence relations of all edges based on the current schedule.
1688 * If a dependence is carried completely by the current schedule, then
1689 * it is removed from the edge_tables. It is kept in the list of edges
1690 * as otherwise all edge_tables would have to be recomputed.
1692 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1696 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1697 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1698 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1702 if (isl_map_plain_is_empty(edge
->map
))
1703 graph_remove_edge(graph
, edge
);
1709 static void next_band(struct isl_sched_graph
*graph
)
1711 graph
->band_start
= graph
->n_total_row
;
1715 /* Topologically sort statements mapped to the same schedule iteration
1716 * and add a row to the schedule corresponding to this order.
1718 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1725 if (update_edges(ctx
, graph
) < 0)
1728 if (graph
->n_edge
== 0)
1731 if (detect_sccs(graph
) < 0)
1734 for (i
= 0; i
< graph
->n
; ++i
) {
1735 struct isl_sched_node
*node
= &graph
->node
[i
];
1736 int row
= isl_mat_rows(node
->sched
);
1737 int cols
= isl_mat_cols(node
->sched
);
1739 isl_map_free(node
->sched_map
);
1740 node
->sched_map
= NULL
;
1741 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1744 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1746 for (j
= 1; j
< cols
; ++j
)
1747 node
->sched
= isl_mat_set_element_si(node
->sched
,
1749 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1752 graph
->n_total_row
++;
1758 /* Construct an isl_schedule based on the computed schedule stored
1759 * in graph and with parameters specified by dim.
1761 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1762 __isl_take isl_space
*dim
)
1766 isl_schedule
*sched
= NULL
;
1771 ctx
= isl_space_get_ctx(dim
);
1772 sched
= isl_calloc(ctx
, struct isl_schedule
,
1773 sizeof(struct isl_schedule
) +
1774 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1779 sched
->n
= graph
->n
;
1780 sched
->n_band
= graph
->n_band
;
1781 sched
->n_total_row
= graph
->n_total_row
;
1783 for (i
= 0; i
< sched
->n
; ++i
) {
1785 int *band_end
, *band_id
, *zero
;
1787 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1788 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1789 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1790 sched
->node
[i
].sched
=
1791 node_extract_schedule_multi_aff(&graph
->node
[i
]);
1792 sched
->node
[i
].band_end
= band_end
;
1793 sched
->node
[i
].band_id
= band_id
;
1794 sched
->node
[i
].zero
= zero
;
1795 if (!band_end
|| !band_id
|| !zero
)
1798 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1799 zero
[r
] = graph
->node
[i
].zero
[r
];
1800 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1801 if (graph
->node
[i
].band
[r
] == b
)
1804 if (graph
->node
[i
].band
[r
] == -1)
1807 if (r
== graph
->n_total_row
)
1809 sched
->node
[i
].n_band
= b
;
1810 for (--b
; b
>= 0; --b
)
1811 band_id
[b
] = graph
->node
[i
].band_id
[b
];
1818 isl_space_free(dim
);
1819 isl_schedule_free(sched
);
1823 /* Copy nodes that satisfy node_pred from the src dependence graph
1824 * to the dst dependence graph.
1826 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
1827 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1832 for (i
= 0; i
< src
->n
; ++i
) {
1833 if (!node_pred(&src
->node
[i
], data
))
1835 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
1836 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
1837 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
1838 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
1839 dst
->node
[dst
->n
].sched_map
=
1840 isl_map_copy(src
->node
[i
].sched_map
);
1841 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
1842 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
1843 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
1850 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1851 * to the dst dependence graph.
1852 * If the source or destination node of the edge is not in the destination
1853 * graph, then it must be a backward proximity edge and it should simply
1856 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
1857 struct isl_sched_graph
*src
,
1858 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
1861 enum isl_edge_type t
;
1864 for (i
= 0; i
< src
->n_edge
; ++i
) {
1865 struct isl_sched_edge
*edge
= &src
->edge
[i
];
1867 struct isl_sched_node
*dst_src
, *dst_dst
;
1869 if (!edge_pred(edge
, data
))
1872 if (isl_map_plain_is_empty(edge
->map
))
1875 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
1876 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
1877 if (!dst_src
|| !dst_dst
) {
1879 isl_die(ctx
, isl_error_internal
,
1880 "backward validity edge", return -1);
1884 map
= isl_map_copy(edge
->map
);
1886 dst
->edge
[dst
->n_edge
].src
= dst_src
;
1887 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
1888 dst
->edge
[dst
->n_edge
].map
= map
;
1889 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
1890 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
1893 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
1895 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
1897 if (graph_edge_table_add(ctx
, dst
, t
,
1898 &dst
->edge
[dst
->n_edge
- 1]) < 0)
1906 /* Given a "src" dependence graph that contains the nodes from "dst"
1907 * that satisfy node_pred, copy the schedule computed in "src"
1908 * for those nodes back to "dst".
1910 static int copy_schedule(struct isl_sched_graph
*dst
,
1911 struct isl_sched_graph
*src
,
1912 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
1917 for (i
= 0; i
< dst
->n
; ++i
) {
1918 if (!node_pred(&dst
->node
[i
], data
))
1920 isl_mat_free(dst
->node
[i
].sched
);
1921 isl_map_free(dst
->node
[i
].sched_map
);
1922 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
1923 dst
->node
[i
].sched_map
=
1924 isl_map_copy(src
->node
[src
->n
].sched_map
);
1928 dst
->n_total_row
= src
->n_total_row
;
1929 dst
->n_band
= src
->n_band
;
1934 /* Compute the maximal number of variables over all nodes.
1935 * This is the maximal number of linearly independent schedule
1936 * rows that we need to compute.
1937 * Just in case we end up in a part of the dependence graph
1938 * with only lower-dimensional domains, we make sure we will
1939 * compute the required amount of extra linearly independent rows.
1941 static int compute_maxvar(struct isl_sched_graph
*graph
)
1946 for (i
= 0; i
< graph
->n
; ++i
) {
1947 struct isl_sched_node
*node
= &graph
->node
[i
];
1950 if (node_update_cmap(node
) < 0)
1952 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
1953 if (nvar
> graph
->maxvar
)
1954 graph
->maxvar
= nvar
;
1960 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1961 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
1963 /* Compute a schedule for a subgraph of "graph". In particular, for
1964 * the graph composed of nodes that satisfy node_pred and edges that
1965 * that satisfy edge_pred. The caller should precompute the number
1966 * of nodes and edges that satisfy these predicates and pass them along
1967 * as "n" and "n_edge".
1968 * If the subgraph is known to consist of a single component, then wcc should
1969 * be set and then we call compute_schedule_wcc on the constructed subgraph.
1970 * Otherwise, we call compute_schedule, which will check whether the subgraph
1973 static int compute_sub_schedule(isl_ctx
*ctx
,
1974 struct isl_sched_graph
*graph
, int n
, int n_edge
,
1975 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
1976 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
1979 struct isl_sched_graph split
= { 0 };
1982 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
1984 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
1986 if (graph_init_table(ctx
, &split
) < 0)
1988 for (t
= 0; t
<= isl_edge_last
; ++t
)
1989 split
.max_edge
[t
] = graph
->max_edge
[t
];
1990 if (graph_init_edge_tables(ctx
, &split
) < 0)
1992 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
1994 split
.n_row
= graph
->n_row
;
1995 split
.n_total_row
= graph
->n_total_row
;
1996 split
.n_band
= graph
->n_band
;
1997 split
.band_start
= graph
->band_start
;
1999 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2001 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2004 copy_schedule(graph
, &split
, node_pred
, data
);
2006 graph_free(ctx
, &split
);
2009 graph_free(ctx
, &split
);
2013 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2015 return node
->scc
== scc
;
2018 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2020 return node
->scc
<= scc
;
2023 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2025 return node
->scc
>= scc
;
2028 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2030 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2033 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2035 return edge
->dst
->scc
<= scc
;
2038 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2040 return edge
->src
->scc
>= scc
;
2043 /* Pad the schedules of all nodes with zero rows such that in the end
2044 * they all have graph->n_total_row rows.
2045 * The extra rows don't belong to any band, so they get assigned band number -1.
2047 static int pad_schedule(struct isl_sched_graph
*graph
)
2051 for (i
= 0; i
< graph
->n
; ++i
) {
2052 struct isl_sched_node
*node
= &graph
->node
[i
];
2053 int row
= isl_mat_rows(node
->sched
);
2054 if (graph
->n_total_row
> row
) {
2055 isl_map_free(node
->sched_map
);
2056 node
->sched_map
= NULL
;
2058 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2059 graph
->n_total_row
- row
);
2062 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2069 /* Split the current graph into two parts and compute a schedule for each
2070 * part individually. In particular, one part consists of all SCCs up
2071 * to and including graph->src_scc, while the other part contains the other
2074 * The split is enforced in the schedule by constant rows with two different
2075 * values (0 and 1). These constant rows replace the previously computed rows
2076 * in the current band.
2077 * It would be possible to reuse them as the first rows in the next
2078 * band, but recomputing them may result in better rows as we are looking
2079 * at a smaller part of the dependence graph.
2080 * compute_split_schedule is only called when no zero-distance schedule row
2081 * could be found on the entire graph, so we wark the splitting row as
2082 * non zero-distance.
2084 * The band_id of the second group is set to n, where n is the number
2085 * of nodes in the first group. This ensures that the band_ids over
2086 * the two groups remain disjoint, even if either or both of the two
2087 * groups contain independent components.
2089 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2091 int i
, j
, n
, e1
, e2
;
2092 int n_total_row
, orig_total_row
;
2093 int n_band
, orig_band
;
2096 drop
= graph
->n_total_row
- graph
->band_start
;
2097 graph
->n_total_row
-= drop
;
2098 graph
->n_row
-= drop
;
2101 for (i
= 0; i
< graph
->n
; ++i
) {
2102 struct isl_sched_node
*node
= &graph
->node
[i
];
2103 int row
= isl_mat_rows(node
->sched
) - drop
;
2104 int cols
= isl_mat_cols(node
->sched
);
2105 int before
= node
->scc
<= graph
->src_scc
;
2110 isl_map_free(node
->sched_map
);
2111 node
->sched_map
= NULL
;
2112 node
->sched
= isl_mat_drop_rows(node
->sched
,
2113 graph
->band_start
, drop
);
2114 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2117 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2119 for (j
= 1; j
< cols
; ++j
)
2120 node
->sched
= isl_mat_set_element_si(node
->sched
,
2122 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2123 node
->zero
[graph
->n_total_row
] = 0;
2127 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2128 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2130 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2134 graph
->n_total_row
++;
2137 for (i
= 0; i
< graph
->n
; ++i
) {
2138 struct isl_sched_node
*node
= &graph
->node
[i
];
2139 if (node
->scc
> graph
->src_scc
)
2140 node
->band_id
[graph
->n_band
] = n
;
2143 orig_total_row
= graph
->n_total_row
;
2144 orig_band
= graph
->n_band
;
2145 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2146 &node_scc_at_most
, &edge_dst_scc_at_most
,
2147 graph
->src_scc
, 0) < 0)
2149 n_total_row
= graph
->n_total_row
;
2150 graph
->n_total_row
= orig_total_row
;
2151 n_band
= graph
->n_band
;
2152 graph
->n_band
= orig_band
;
2153 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2154 &node_scc_at_least
, &edge_src_scc_at_least
,
2155 graph
->src_scc
+ 1, 0) < 0)
2157 if (n_total_row
> graph
->n_total_row
)
2158 graph
->n_total_row
= n_total_row
;
2159 if (n_band
> graph
->n_band
)
2160 graph
->n_band
= n_band
;
2162 return pad_schedule(graph
);
2165 /* Compute the next band of the schedule after updating the dependence
2166 * relations based on the the current schedule.
2168 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2170 if (update_edges(ctx
, graph
) < 0)
2174 return compute_schedule(ctx
, graph
);
2177 /* Add constraints to graph->lp that force the dependence "map" (which
2178 * is part of the dependence relation of "edge")
2179 * to be respected and attempt to carry it, where the edge is one from
2180 * a node j to itself. "pos" is the sequence number of the given map.
2181 * That is, add constraints that enforce
2183 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2184 * = c_j_x (y - x) >= e_i
2186 * for each (x,y) in R.
2187 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2188 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2189 * with each coefficient in c_j_x represented as a pair of non-negative
2192 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2193 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2196 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2198 isl_dim_map
*dim_map
;
2199 isl_basic_set
*coef
;
2200 struct isl_sched_node
*node
= edge
->src
;
2202 coef
= intra_coefficients(graph
, map
);
2204 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2206 total
= isl_basic_set_total_dim(graph
->lp
);
2207 dim_map
= isl_dim_map_alloc(ctx
, total
);
2208 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2209 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2210 isl_space_dim(dim
, isl_dim_set
), 1,
2212 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2213 isl_space_dim(dim
, isl_dim_set
), 1,
2215 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2216 coef
->n_eq
, coef
->n_ineq
);
2217 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2219 isl_space_free(dim
);
2224 /* Add constraints to graph->lp that force the dependence "map" (which
2225 * is part of the dependence relation of "edge")
2226 * to be respected and attempt to carry it, where the edge is one from
2227 * node j to node k. "pos" is the sequence number of the given map.
2228 * That is, add constraints that enforce
2230 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2232 * for each (x,y) in R.
2233 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2234 * of valid constraints for R and then plug in
2235 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2236 * with each coefficient (except e_i, c_k_0 and c_j_0)
2237 * represented as a pair of non-negative coefficients.
2239 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2240 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2243 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2245 isl_dim_map
*dim_map
;
2246 isl_basic_set
*coef
;
2247 struct isl_sched_node
*src
= edge
->src
;
2248 struct isl_sched_node
*dst
= edge
->dst
;
2250 coef
= inter_coefficients(graph
, map
);
2252 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2254 total
= isl_basic_set_total_dim(graph
->lp
);
2255 dim_map
= isl_dim_map_alloc(ctx
, total
);
2257 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2259 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2260 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2261 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2262 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2263 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2265 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2266 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2269 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2270 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2271 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2272 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2273 isl_space_dim(dim
, isl_dim_set
), 1,
2275 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2276 isl_space_dim(dim
, isl_dim_set
), 1,
2279 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2280 coef
->n_eq
, coef
->n_ineq
);
2281 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2283 isl_space_free(dim
);
2288 /* Add constraints to graph->lp that force all validity dependences
2289 * to be respected and attempt to carry them.
2291 static int add_all_constraints(struct isl_sched_graph
*graph
)
2297 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2298 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2300 if (!edge
->validity
)
2303 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2304 isl_basic_map
*bmap
;
2307 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2308 map
= isl_map_from_basic_map(bmap
);
2310 if (edge
->src
== edge
->dst
&&
2311 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2313 if (edge
->src
!= edge
->dst
&&
2314 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2323 /* Count the number of equality and inequality constraints
2324 * that will be added to the carry_lp problem.
2325 * We count each edge exactly once.
2327 static int count_all_constraints(struct isl_sched_graph
*graph
,
2328 int *n_eq
, int *n_ineq
)
2332 *n_eq
= *n_ineq
= 0;
2333 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2334 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2335 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2336 isl_basic_map
*bmap
;
2339 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2340 map
= isl_map_from_basic_map(bmap
);
2342 if (count_map_constraints(graph
, edge
, map
,
2343 n_eq
, n_ineq
, 1) < 0)
2351 /* Construct an LP problem for finding schedule coefficients
2352 * such that the schedule carries as many dependences as possible.
2353 * In particular, for each dependence i, we bound the dependence distance
2354 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2355 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2356 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2357 * Note that if the dependence relation is a union of basic maps,
2358 * then we have to consider each basic map individually as it may only
2359 * be possible to carry the dependences expressed by some of those
2360 * basic maps and not all off them.
2361 * Below, we consider each of those basic maps as a separate "edge".
2363 * All variables of the LP are non-negative. The actual coefficients
2364 * may be negative, so each coefficient is represented as the difference
2365 * of two non-negative variables. The negative part always appears
2366 * immediately before the positive part.
2367 * Other than that, the variables have the following order
2369 * - sum of (1 - e_i) over all edges
2370 * - sum of positive and negative parts of all c_n coefficients
2371 * (unconstrained when computing non-parametric schedules)
2372 * - sum of positive and negative parts of all c_x coefficients
2377 * - positive and negative parts of c_i_n (if parametric)
2378 * - positive and negative parts of c_i_x
2380 * The constraints are those from the (validity) edges plus three equalities
2381 * to express the sums and n_edge inequalities to express e_i <= 1.
2383 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2393 for (i
= 0; i
< graph
->n_edge
; ++i
)
2394 n_edge
+= graph
->edge
[i
].map
->n
;
2397 for (i
= 0; i
< graph
->n
; ++i
) {
2398 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2399 node
->start
= total
;
2400 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2403 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2406 dim
= isl_space_set_alloc(ctx
, 0, total
);
2407 isl_basic_set_free(graph
->lp
);
2410 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2411 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2413 k
= isl_basic_set_alloc_equality(graph
->lp
);
2416 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2417 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2418 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2419 for (i
= 0; i
< n_edge
; ++i
)
2420 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2422 k
= isl_basic_set_alloc_equality(graph
->lp
);
2425 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2426 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2427 for (i
= 0; i
< graph
->n
; ++i
) {
2428 int pos
= 1 + graph
->node
[i
].start
+ 1;
2430 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2431 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2434 k
= isl_basic_set_alloc_equality(graph
->lp
);
2437 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2438 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2439 for (i
= 0; i
< graph
->n
; ++i
) {
2440 struct isl_sched_node
*node
= &graph
->node
[i
];
2441 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2443 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2444 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2447 for (i
= 0; i
< n_edge
; ++i
) {
2448 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2451 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2452 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2453 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2456 if (add_all_constraints(graph
) < 0)
2462 /* If the schedule_split_scaled option is set and if the linear
2463 * parts of the scheduling rows for all nodes in the graphs have
2464 * non-trivial common divisor, then split off the constant term
2465 * from the linear part.
2466 * The constant term is then placed in a separate band and
2467 * the linear part is reduced.
2469 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2475 if (!ctx
->opt
->schedule_split_scaled
)
2481 isl_int_init(gcd_i
);
2483 isl_int_set_si(gcd
, 0);
2485 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2487 for (i
= 0; i
< graph
->n
; ++i
) {
2488 struct isl_sched_node
*node
= &graph
->node
[i
];
2489 int cols
= isl_mat_cols(node
->sched
);
2491 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2492 isl_int_gcd(gcd
, gcd
, gcd_i
);
2495 isl_int_clear(gcd_i
);
2497 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2504 for (i
= 0; i
< graph
->n
; ++i
) {
2505 struct isl_sched_node
*node
= &graph
->node
[i
];
2507 isl_map_free(node
->sched_map
);
2508 node
->sched_map
= NULL
;
2509 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2512 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2513 node
->sched
->row
[row
][0], gcd
);
2514 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2515 node
->sched
->row
[row
][0], gcd
);
2516 isl_int_mul(node
->sched
->row
[row
][0],
2517 node
->sched
->row
[row
][0], gcd
);
2518 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2521 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2524 graph
->n_total_row
++;
2533 /* Construct a schedule row for each node such that as many dependences
2534 * as possible are carried and then continue with the next band.
2536 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2544 for (i
= 0; i
< graph
->n_edge
; ++i
)
2545 n_edge
+= graph
->edge
[i
].map
->n
;
2547 if (setup_carry_lp(ctx
, graph
) < 0)
2550 lp
= isl_basic_set_copy(graph
->lp
);
2551 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2555 if (sol
->size
== 0) {
2557 isl_die(ctx
, isl_error_internal
,
2558 "error in schedule construction", return -1);
2561 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2563 isl_die(ctx
, isl_error_unknown
,
2564 "unable to carry dependences", return -1);
2567 if (update_schedule(graph
, sol
, 0, 0) < 0)
2570 if (split_scaled(ctx
, graph
) < 0)
2573 return compute_next_band(ctx
, graph
);
2576 /* Are there any (non-empty) validity edges in the graph?
2578 static int has_validity_edges(struct isl_sched_graph
*graph
)
2582 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2585 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
2590 if (graph
->edge
[i
].validity
)
2597 /* Should we apply a Feautrier step?
2598 * That is, did the user request the Feautrier algorithm and are
2599 * there any validity dependences (left)?
2601 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2603 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2606 return has_validity_edges(graph
);
2609 /* Compute a schedule for a connected dependence graph using Feautrier's
2610 * multi-dimensional scheduling algorithm.
2611 * The original algorithm is described in [1].
2612 * The main idea is to minimize the number of scheduling dimensions, by
2613 * trying to satisfy as many dependences as possible per scheduling dimension.
2615 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2616 * Problem, Part II: Multi-Dimensional Time.
2617 * In Intl. Journal of Parallel Programming, 1992.
2619 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2620 struct isl_sched_graph
*graph
)
2622 return carry_dependences(ctx
, graph
);
2625 /* Compute a schedule for a connected dependence graph.
2626 * We try to find a sequence of as many schedule rows as possible that result
2627 * in non-negative dependence distances (independent of the previous rows
2628 * in the sequence, i.e., such that the sequence is tilable).
2629 * If we can't find any more rows we either
2630 * - split between SCCs and start over (assuming we found an interesting
2631 * pair of SCCs between which to split)
2632 * - continue with the next band (assuming the current band has at least
2634 * - try to carry as many dependences as possible and continue with the next
2637 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2638 * as many validity dependences as possible. When all validity dependences
2639 * are satisfied we extend the schedule to a full-dimensional schedule.
2641 * If we manage to complete the schedule, we finish off by topologically
2642 * sorting the statements based on the remaining dependences.
2644 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2645 * outermost dimension in the current band to be zero distance. If this
2646 * turns out to be impossible, we fall back on the general scheme above
2647 * and try to carry as many dependences as possible.
2649 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2653 if (detect_sccs(graph
) < 0)
2655 if (sort_sccs(graph
) < 0)
2658 if (compute_maxvar(graph
) < 0)
2661 if (need_feautrier_step(ctx
, graph
))
2662 return compute_schedule_wcc_feautrier(ctx
, graph
);
2664 if (ctx
->opt
->schedule_outer_zero_distance
)
2667 while (graph
->n_row
< graph
->maxvar
) {
2670 graph
->src_scc
= -1;
2671 graph
->dst_scc
= -1;
2673 if (setup_lp(ctx
, graph
, force_zero
) < 0)
2675 sol
= solve_lp(graph
);
2678 if (sol
->size
== 0) {
2680 if (!ctx
->opt
->schedule_maximize_band_depth
&&
2681 graph
->n_total_row
> graph
->band_start
)
2682 return compute_next_band(ctx
, graph
);
2683 if (graph
->src_scc
>= 0)
2684 return compute_split_schedule(ctx
, graph
);
2685 if (graph
->n_total_row
> graph
->band_start
)
2686 return compute_next_band(ctx
, graph
);
2687 return carry_dependences(ctx
, graph
);
2689 if (update_schedule(graph
, sol
, 1, 1) < 0)
2694 if (graph
->n_total_row
> graph
->band_start
)
2696 return sort_statements(ctx
, graph
);
2699 /* Add a row to the schedules that separates the SCCs and move
2702 static int split_on_scc(struct isl_sched_graph
*graph
)
2706 for (i
= 0; i
< graph
->n
; ++i
) {
2707 struct isl_sched_node
*node
= &graph
->node
[i
];
2708 int row
= isl_mat_rows(node
->sched
);
2710 isl_map_free(node
->sched_map
);
2711 node
->sched_map
= NULL
;
2712 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2713 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2717 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2720 graph
->n_total_row
++;
2726 /* Compute a schedule for each component (identified by node->scc)
2727 * of the dependence graph separately and then combine the results.
2728 * Depending on the setting of schedule_fuse, a component may be
2729 * either weakly or strongly connected.
2731 * The band_id is adjusted such that each component has a separate id.
2732 * Note that the band_id may have already been set to a value different
2733 * from zero by compute_split_schedule.
2735 static int compute_component_schedule(isl_ctx
*ctx
,
2736 struct isl_sched_graph
*graph
)
2740 int n_total_row
, orig_total_row
;
2741 int n_band
, orig_band
;
2743 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
2744 ctx
->opt
->schedule_separate_components
)
2745 split_on_scc(graph
);
2748 orig_total_row
= graph
->n_total_row
;
2750 orig_band
= graph
->n_band
;
2751 for (i
= 0; i
< graph
->n
; ++i
)
2752 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
2753 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
2755 for (i
= 0; i
< graph
->n
; ++i
)
2756 if (graph
->node
[i
].scc
== wcc
)
2759 for (i
= 0; i
< graph
->n_edge
; ++i
)
2760 if (graph
->edge
[i
].src
->scc
== wcc
&&
2761 graph
->edge
[i
].dst
->scc
== wcc
)
2764 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
2766 &edge_scc_exactly
, wcc
, 1) < 0)
2768 if (graph
->n_total_row
> n_total_row
)
2769 n_total_row
= graph
->n_total_row
;
2770 graph
->n_total_row
= orig_total_row
;
2771 if (graph
->n_band
> n_band
)
2772 n_band
= graph
->n_band
;
2773 graph
->n_band
= orig_band
;
2776 graph
->n_total_row
= n_total_row
;
2777 graph
->n_band
= n_band
;
2779 return pad_schedule(graph
);
2782 /* Compute a schedule for the given dependence graph.
2783 * We first check if the graph is connected (through validity dependences)
2784 * and, if not, compute a schedule for each component separately.
2785 * If schedule_fuse is set to minimal fusion, then we check for strongly
2786 * connected components instead and compute a separate schedule for
2787 * each such strongly connected component.
2789 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2791 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
2792 if (detect_sccs(graph
) < 0)
2795 if (detect_wccs(graph
) < 0)
2800 return compute_component_schedule(ctx
, graph
);
2802 return compute_schedule_wcc(ctx
, graph
);
2805 /* Compute a schedule for the given union of domains that respects
2806 * all the validity dependences.
2807 * If the default isl scheduling algorithm is used, it tries to minimize
2808 * the dependence distances over the proximity dependences.
2809 * If Feautrier's scheduling algorithm is used, the proximity dependence
2810 * distances are only minimized during the extension to a full-dimensional
2813 __isl_give isl_schedule
*isl_union_set_compute_schedule(
2814 __isl_take isl_union_set
*domain
,
2815 __isl_take isl_union_map
*validity
,
2816 __isl_take isl_union_map
*proximity
)
2818 isl_ctx
*ctx
= isl_union_set_get_ctx(domain
);
2820 struct isl_sched_graph graph
= { 0 };
2821 isl_schedule
*sched
;
2822 struct isl_extract_edge_data data
;
2824 domain
= isl_union_set_align_params(domain
,
2825 isl_union_map_get_space(validity
));
2826 domain
= isl_union_set_align_params(domain
,
2827 isl_union_map_get_space(proximity
));
2828 dim
= isl_union_set_get_space(domain
);
2829 validity
= isl_union_map_align_params(validity
, isl_space_copy(dim
));
2830 proximity
= isl_union_map_align_params(proximity
, dim
);
2835 graph
.n
= isl_union_set_n_set(domain
);
2838 if (graph_alloc(ctx
, &graph
, graph
.n
,
2839 isl_union_map_n_map(validity
) + isl_union_map_n_map(proximity
)) < 0)
2841 if (compute_max_row(&graph
, domain
) < 0)
2845 if (isl_union_set_foreach_set(domain
, &extract_node
, &graph
) < 0)
2847 if (graph_init_table(ctx
, &graph
) < 0)
2849 graph
.max_edge
[isl_edge_validity
] = isl_union_map_n_map(validity
);
2850 graph
.max_edge
[isl_edge_proximity
] = isl_union_map_n_map(proximity
);
2851 if (graph_init_edge_tables(ctx
, &graph
) < 0)
2854 data
.graph
= &graph
;
2855 data
.type
= isl_edge_validity
;
2856 if (isl_union_map_foreach_map(validity
, &extract_edge
, &data
) < 0)
2858 data
.type
= isl_edge_proximity
;
2859 if (isl_union_map_foreach_map(proximity
, &extract_edge
, &data
) < 0)
2862 if (compute_schedule(ctx
, &graph
) < 0)
2866 sched
= extract_schedule(&graph
, isl_union_set_get_space(domain
));
2868 graph_free(ctx
, &graph
);
2869 isl_union_set_free(domain
);
2870 isl_union_map_free(validity
);
2871 isl_union_map_free(proximity
);
2875 graph_free(ctx
, &graph
);
2876 isl_union_set_free(domain
);
2877 isl_union_map_free(validity
);
2878 isl_union_map_free(proximity
);
2882 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
2888 if (--sched
->ref
> 0)
2891 for (i
= 0; i
< sched
->n
; ++i
) {
2892 isl_multi_aff_free(sched
->node
[i
].sched
);
2893 free(sched
->node
[i
].band_end
);
2894 free(sched
->node
[i
].band_id
);
2895 free(sched
->node
[i
].zero
);
2897 isl_space_free(sched
->dim
);
2898 isl_band_list_free(sched
->band_forest
);
2903 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
2905 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
2908 /* Return an isl_union_map of the schedule. If we have already constructed
2909 * a band forest, then this band forest may have been modified so we need
2910 * to extract the isl_union_map from the forest rather than from
2911 * the originally computed schedule.
2913 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
2916 isl_union_map
*umap
;
2921 if (sched
->band_forest
)
2922 return isl_band_list_get_suffix_schedule(sched
->band_forest
);
2924 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
2925 for (i
= 0; i
< sched
->n
; ++i
) {
2928 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
2929 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
2935 static __isl_give isl_band_list
*construct_band_list(
2936 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
2937 int band_nr
, int *parent_active
, int n_active
);
2939 /* Construct an isl_band structure for the band in the given schedule
2940 * with sequence number band_nr for the n_active nodes marked by active.
2941 * If the nodes don't have a band with the given sequence number,
2942 * then a band without members is created.
2944 * Because of the way the schedule is constructed, we know that
2945 * the position of the band inside the schedule of a node is the same
2946 * for all active nodes.
2948 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
2949 __isl_keep isl_band
*parent
,
2950 int band_nr
, int *active
, int n_active
)
2953 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
2955 unsigned start
, end
;
2957 band
= isl_band_alloc(ctx
);
2961 band
->schedule
= schedule
;
2962 band
->parent
= parent
;
2964 for (i
= 0; i
< schedule
->n
; ++i
)
2965 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
2968 if (i
< schedule
->n
) {
2969 band
->children
= construct_band_list(schedule
, band
,
2970 band_nr
+ 1, active
, n_active
);
2971 if (!band
->children
)
2975 for (i
= 0; i
< schedule
->n
; ++i
)
2979 if (i
>= schedule
->n
)
2980 isl_die(ctx
, isl_error_internal
,
2981 "band without active statements", goto error
);
2983 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
2984 end
= band_nr
< schedule
->node
[i
].n_band
?
2985 schedule
->node
[i
].band_end
[band_nr
] : start
;
2986 band
->n
= end
- start
;
2988 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
2992 for (j
= 0; j
< band
->n
; ++j
)
2993 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
2995 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
2996 for (i
= 0; i
< schedule
->n
; ++i
) {
2998 isl_pw_multi_aff
*pma
;
3004 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
3005 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3006 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
3007 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
3008 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3009 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
3017 isl_band_free(band
);
3021 /* Construct a list of bands that start at the same position (with
3022 * sequence number band_nr) in the schedules of the nodes that
3023 * were active in the parent band.
3025 * A separate isl_band structure is created for each band_id
3026 * and for each node that does not have a band with sequence
3027 * number band_nr. In the latter case, a band without members
3029 * This ensures that if a band has any children, then each node
3030 * that was active in the band is active in exactly one of the children.
3032 static __isl_give isl_band_list
*construct_band_list(
3033 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3034 int band_nr
, int *parent_active
, int n_active
)
3037 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3040 isl_band_list
*list
;
3043 for (i
= 0; i
< n_active
; ++i
) {
3044 for (j
= 0; j
< schedule
->n
; ++j
) {
3045 if (!parent_active
[j
])
3047 if (schedule
->node
[j
].n_band
<= band_nr
)
3049 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
3055 for (j
= 0; j
< schedule
->n
; ++j
)
3056 if (schedule
->node
[j
].n_band
<= band_nr
)
3061 list
= isl_band_list_alloc(ctx
, n_band
);
3062 band
= construct_band(schedule
, parent
, band_nr
,
3063 parent_active
, n_active
);
3064 return isl_band_list_add(list
, band
);
3067 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3071 list
= isl_band_list_alloc(ctx
, n_band
);
3073 for (i
= 0; i
< n_active
; ++i
) {
3077 for (j
= 0; j
< schedule
->n
; ++j
) {
3078 active
[j
] = parent_active
[j
] &&
3079 schedule
->node
[j
].n_band
> band_nr
&&
3080 schedule
->node
[j
].band_id
[band_nr
] == i
;
3087 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
3089 list
= isl_band_list_add(list
, band
);
3091 for (i
= 0; i
< schedule
->n
; ++i
) {
3093 if (!parent_active
[i
])
3095 if (schedule
->node
[i
].n_band
> band_nr
)
3097 for (j
= 0; j
< schedule
->n
; ++j
)
3099 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
3100 list
= isl_band_list_add(list
, band
);
3108 /* Construct a band forest representation of the schedule and
3109 * return the list of roots.
3111 static __isl_give isl_band_list
*construct_forest(
3112 __isl_keep isl_schedule
*schedule
)
3115 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3116 isl_band_list
*forest
;
3119 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3123 for (i
= 0; i
< schedule
->n
; ++i
)
3126 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
3133 /* Return the roots of a band forest representation of the schedule.
3135 __isl_give isl_band_list
*isl_schedule_get_band_forest(
3136 __isl_keep isl_schedule
*schedule
)
3140 if (!schedule
->band_forest
)
3141 schedule
->band_forest
= construct_forest(schedule
);
3142 return isl_band_list_dup(schedule
->band_forest
);
3145 /* Call "fn" on each band in the schedule in depth-first post-order.
3147 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
3148 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
3151 isl_band_list
*forest
;
3156 forest
= isl_schedule_get_band_forest(sched
);
3157 r
= isl_band_list_foreach_band(forest
, fn
, user
);
3158 isl_band_list_free(forest
);
3163 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3164 __isl_keep isl_band_list
*list
);
3166 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
3167 __isl_keep isl_band
*band
)
3169 isl_band_list
*children
;
3171 p
= isl_printer_start_line(p
);
3172 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
3173 p
= isl_printer_end_line(p
);
3175 if (!isl_band_has_children(band
))
3178 children
= isl_band_get_children(band
);
3180 p
= isl_printer_indent(p
, 4);
3181 p
= print_band_list(p
, children
);
3182 p
= isl_printer_indent(p
, -4);
3184 isl_band_list_free(children
);
3189 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3190 __isl_keep isl_band_list
*list
)
3194 n
= isl_band_list_n_band(list
);
3195 for (i
= 0; i
< n
; ++i
) {
3197 band
= isl_band_list_get_band(list
, i
);
3198 p
= print_band(p
, band
);
3199 isl_band_free(band
);
3205 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
3206 __isl_keep isl_schedule
*schedule
)
3208 isl_band_list
*forest
;
3210 forest
= isl_schedule_get_band_forest(schedule
);
3212 p
= print_band_list(p
, forest
);
3214 isl_band_list_free(forest
);
3219 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
3221 isl_printer
*printer
;
3226 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
3227 printer
= isl_printer_print_schedule(printer
, schedule
);
3229 isl_printer_free(printer
);