2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_space_private.h>
16 #include <isl_aff_private.h>
18 #include <isl/constraint.h>
19 #include <isl/schedule.h>
20 #include <isl_mat_private.h>
21 #include <isl_vec_private.h>
25 #include <isl_dim_map.h>
26 #include <isl/map_to_basic_set.h>
28 #include <isl_schedule_private.h>
29 #include <isl_band_private.h>
30 #include <isl_options_private.h>
31 #include <isl_tarjan.h>
34 * The scheduling algorithm implemented in this file was inspired by
35 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
36 * Parallelization and Locality Optimization in the Polyhedral Model".
39 /* Construct an isl_schedule_constraints object for computing a schedule
40 * on "domain". The initial object does not impose any constraints.
42 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
43 __isl_take isl_union_set
*domain
)
47 isl_schedule_constraints
*sc
;
54 ctx
= isl_union_set_get_ctx(domain
);
55 sc
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
57 return isl_union_set_free(domain
);
59 space
= isl_union_set_get_space(domain
);
61 empty
= isl_union_map_empty(space
);
62 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
63 sc
->constraint
[i
] = isl_union_map_copy(empty
);
64 if (!sc
->constraint
[i
])
65 sc
->domain
= isl_union_set_free(sc
->domain
);
67 isl_union_map_free(empty
);
70 return isl_schedule_constraints_free(sc
);
75 /* Replace the validity constraints of "sc" by "validity".
77 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
78 __isl_take isl_schedule_constraints
*sc
,
79 __isl_take isl_union_map
*validity
)
84 isl_union_map_free(sc
->constraint
[isl_edge_validity
]);
85 sc
->constraint
[isl_edge_validity
] = validity
;
89 isl_schedule_constraints_free(sc
);
90 isl_union_map_free(validity
);
94 /* Replace the proximity constraints of "sc" by "proximity".
96 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
97 __isl_take isl_schedule_constraints
*sc
,
98 __isl_take isl_union_map
*proximity
)
100 if (!sc
|| !proximity
)
103 isl_union_map_free(sc
->constraint
[isl_edge_proximity
]);
104 sc
->constraint
[isl_edge_proximity
] = proximity
;
108 isl_schedule_constraints_free(sc
);
109 isl_union_map_free(proximity
);
113 void *isl_schedule_constraints_free(__isl_take isl_schedule_constraints
*sc
)
115 enum isl_edge_type i
;
120 isl_union_set_free(sc
->domain
);
121 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
122 isl_union_map_free(sc
->constraint
[i
]);
129 isl_ctx
*isl_schedule_constraints_get_ctx(
130 __isl_keep isl_schedule_constraints
*sc
)
132 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
135 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
140 fprintf(stderr
, "domain: ");
141 isl_union_set_dump(sc
->domain
);
142 fprintf(stderr
, "validity: ");
143 isl_union_map_dump(sc
->constraint
[isl_edge_validity
]);
144 fprintf(stderr
, "proximity: ");
145 isl_union_map_dump(sc
->constraint
[isl_edge_proximity
]);
148 /* Align the parameters of the fields of "sc".
150 static __isl_give isl_schedule_constraints
*
151 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
154 enum isl_edge_type i
;
159 space
= isl_union_set_get_space(sc
->domain
);
160 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
161 space
= isl_space_align_params(space
,
162 isl_union_map_get_space(sc
->constraint
[i
]));
164 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
165 sc
->constraint
[i
] = isl_union_map_align_params(
166 sc
->constraint
[i
], isl_space_copy(space
));
167 if (!sc
->constraint
[i
])
168 space
= isl_space_free(space
);
170 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
172 return isl_schedule_constraints_free(sc
);
177 /* Return the total number of isl_maps in the constraints of "sc".
179 static __isl_give
int isl_schedule_constraints_n_map(
180 __isl_keep isl_schedule_constraints
*sc
)
182 enum isl_edge_type i
;
185 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
186 n
+= isl_union_map_n_map(sc
->constraint
[i
]);
191 /* Internal information about a node that is used during the construction
193 * dim represents the space in which the domain lives
194 * sched is a matrix representation of the schedule being constructed
196 * sched_map is an isl_map representation of the same (partial) schedule
197 * sched_map may be NULL
198 * rank is the number of linearly independent rows in the linear part
200 * the columns of cmap represent a change of basis for the schedule
201 * coefficients; the first rank columns span the linear part of
203 * cinv is the inverse of cmap.
204 * start is the first variable in the LP problem in the sequences that
205 * represents the schedule coefficients of this node
206 * nvar is the dimension of the domain
207 * nparam is the number of parameters or 0 if we are not constructing
208 * a parametric schedule
210 * scc is the index of SCC (or WCC) this node belongs to
212 * band contains the band index for each of the rows of the schedule.
213 * band_id is used to differentiate between separate bands at the same
214 * level within the same parent band, i.e., bands that are separated
215 * by the parent band or bands that are independent of each other.
216 * zero contains a boolean for each of the rows of the schedule,
217 * indicating whether the corresponding scheduling dimension results
218 * in zero dependence distances within its band and with respect
219 * to the proximity edges.
221 struct isl_sched_node
{
239 static int node_has_dim(const void *entry
, const void *val
)
241 struct isl_sched_node
*node
= (struct isl_sched_node
*)entry
;
242 isl_space
*dim
= (isl_space
*)val
;
244 return isl_space_is_equal(node
->dim
, dim
);
247 /* An edge in the dependence graph. An edge may be used to
248 * ensure validity of the generated schedule, to minimize the dependence
251 * map is the dependence relation
252 * src is the source node
253 * dst is the sink node
254 * validity is set if the edge is used to ensure correctness
255 * proximity is set if the edge is used to minimize dependence distances
257 * For validity edges, start and end mark the sequence of inequality
258 * constraints in the LP problem that encode the validity constraint
259 * corresponding to this edge.
261 struct isl_sched_edge
{
264 struct isl_sched_node
*src
;
265 struct isl_sched_node
*dst
;
274 /* Internal information about the dependence graph used during
275 * the construction of the schedule.
277 * intra_hmap is a cache, mapping dependence relations to their dual,
278 * for dependences from a node to itself
279 * inter_hmap is a cache, mapping dependence relations to their dual,
280 * for dependences between distinct nodes
282 * n is the number of nodes
283 * node is the list of nodes
284 * maxvar is the maximal number of variables over all nodes
285 * max_row is the allocated number of rows in the schedule
286 * n_row is the current (maximal) number of linearly independent
287 * rows in the node schedules
288 * n_total_row is the current number of rows in the node schedules
289 * n_band is the current number of completed bands
290 * band_start is the starting row in the node schedules of the current band
291 * root is set if this graph is the original dependence graph,
292 * without any splitting
294 * sorted contains a list of node indices sorted according to the
295 * SCC to which a node belongs
297 * n_edge is the number of edges
298 * edge is the list of edges
299 * max_edge contains the maximal number of edges of each type;
300 * in particular, it contains the number of edges in the inital graph.
301 * edge_table contains pointers into the edge array, hashed on the source
302 * and sink spaces; there is one such table for each type;
303 * a given edge may be referenced from more than one table
304 * if the corresponding relation appears in more than of the
305 * sets of dependences
307 * node_table contains pointers into the node array, hashed on the space
309 * region contains a list of variable sequences that should be non-trivial
311 * lp contains the (I)LP problem used to obtain new schedule rows
313 * src_scc and dst_scc are the source and sink SCCs of an edge with
314 * conflicting constraints
316 * scc represents the number of components
318 struct isl_sched_graph
{
319 isl_map_to_basic_set
*intra_hmap
;
320 isl_map_to_basic_set
*inter_hmap
;
322 struct isl_sched_node
*node
;
336 struct isl_sched_edge
*edge
;
338 int max_edge
[isl_edge_last
+ 1];
339 struct isl_hash_table
*edge_table
[isl_edge_last
+ 1];
341 struct isl_hash_table
*node_table
;
342 struct isl_region
*region
;
352 /* Initialize node_table based on the list of nodes.
354 static int graph_init_table(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
358 graph
->node_table
= isl_hash_table_alloc(ctx
, graph
->n
);
359 if (!graph
->node_table
)
362 for (i
= 0; i
< graph
->n
; ++i
) {
363 struct isl_hash_table_entry
*entry
;
366 hash
= isl_space_get_hash(graph
->node
[i
].dim
);
367 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
369 graph
->node
[i
].dim
, 1);
372 entry
->data
= &graph
->node
[i
];
378 /* Return a pointer to the node that lives within the given space,
379 * or NULL if there is no such node.
381 static struct isl_sched_node
*graph_find_node(isl_ctx
*ctx
,
382 struct isl_sched_graph
*graph
, __isl_keep isl_space
*dim
)
384 struct isl_hash_table_entry
*entry
;
387 hash
= isl_space_get_hash(dim
);
388 entry
= isl_hash_table_find(ctx
, graph
->node_table
, hash
,
389 &node_has_dim
, dim
, 0);
391 return entry
? entry
->data
: NULL
;
394 static int edge_has_src_and_dst(const void *entry
, const void *val
)
396 const struct isl_sched_edge
*edge
= entry
;
397 const struct isl_sched_edge
*temp
= val
;
399 return edge
->src
== temp
->src
&& edge
->dst
== temp
->dst
;
402 /* Add the given edge to graph->edge_table[type].
404 static int graph_edge_table_add(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
405 enum isl_edge_type type
, struct isl_sched_edge
*edge
)
407 struct isl_hash_table_entry
*entry
;
410 hash
= isl_hash_init();
411 hash
= isl_hash_builtin(hash
, edge
->src
);
412 hash
= isl_hash_builtin(hash
, edge
->dst
);
413 entry
= isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
414 &edge_has_src_and_dst
, edge
, 1);
422 /* Allocate the edge_tables based on the maximal number of edges of
425 static int graph_init_edge_tables(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
429 for (i
= 0; i
<= isl_edge_last
; ++i
) {
430 graph
->edge_table
[i
] = isl_hash_table_alloc(ctx
,
432 if (!graph
->edge_table
[i
])
439 /* If graph->edge_table[type] contains an edge from the given source
440 * to the given destination, then return the hash table entry of this edge.
441 * Otherwise, return NULL.
443 static struct isl_hash_table_entry
*graph_find_edge_entry(
444 struct isl_sched_graph
*graph
,
445 enum isl_edge_type type
,
446 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
448 isl_ctx
*ctx
= isl_space_get_ctx(src
->dim
);
450 struct isl_sched_edge temp
= { .src
= src
, .dst
= dst
};
452 hash
= isl_hash_init();
453 hash
= isl_hash_builtin(hash
, temp
.src
);
454 hash
= isl_hash_builtin(hash
, temp
.dst
);
455 return isl_hash_table_find(ctx
, graph
->edge_table
[type
], hash
,
456 &edge_has_src_and_dst
, &temp
, 0);
460 /* If graph->edge_table[type] contains an edge from the given source
461 * to the given destination, then return this edge.
462 * Otherwise, return NULL.
464 static struct isl_sched_edge
*graph_find_edge(struct isl_sched_graph
*graph
,
465 enum isl_edge_type type
,
466 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
468 struct isl_hash_table_entry
*entry
;
470 entry
= graph_find_edge_entry(graph
, type
, src
, dst
);
477 /* Check whether the dependence graph has an edge of the given type
478 * between the given two nodes.
480 static int graph_has_edge(struct isl_sched_graph
*graph
,
481 enum isl_edge_type type
,
482 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
484 struct isl_sched_edge
*edge
;
487 edge
= graph_find_edge(graph
, type
, src
, dst
);
491 empty
= isl_map_plain_is_empty(edge
->map
);
498 /* If there is an edge from the given source to the given destination
499 * of any type then return this edge.
500 * Otherwise, return NULL.
502 static struct isl_sched_edge
*graph_find_any_edge(struct isl_sched_graph
*graph
,
503 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
505 enum isl_edge_type i
;
506 struct isl_sched_edge
*edge
;
508 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
509 edge
= graph_find_edge(graph
, i
, src
, dst
);
517 /* Remove the given edge from all the edge_tables that refer to it.
519 static void graph_remove_edge(struct isl_sched_graph
*graph
,
520 struct isl_sched_edge
*edge
)
522 isl_ctx
*ctx
= isl_map_get_ctx(edge
->map
);
523 enum isl_edge_type i
;
525 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
526 struct isl_hash_table_entry
*entry
;
528 entry
= graph_find_edge_entry(graph
, i
, edge
->src
, edge
->dst
);
531 if (entry
->data
!= edge
)
533 isl_hash_table_remove(ctx
, graph
->edge_table
[i
], entry
);
537 /* Check whether the dependence graph has any edge
538 * between the given two nodes.
540 static int graph_has_any_edge(struct isl_sched_graph
*graph
,
541 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
543 enum isl_edge_type i
;
546 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
547 r
= graph_has_edge(graph
, i
, src
, dst
);
555 /* Check whether the dependence graph has a validity edge
556 * between the given two nodes.
558 static int graph_has_validity_edge(struct isl_sched_graph
*graph
,
559 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
561 return graph_has_edge(graph
, isl_edge_validity
, src
, dst
);
564 static int graph_alloc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
565 int n_node
, int n_edge
)
570 graph
->n_edge
= n_edge
;
571 graph
->node
= isl_calloc_array(ctx
, struct isl_sched_node
, graph
->n
);
572 graph
->sorted
= isl_calloc_array(ctx
, int, graph
->n
);
573 graph
->region
= isl_alloc_array(ctx
, struct isl_region
, graph
->n
);
574 graph
->edge
= isl_calloc_array(ctx
,
575 struct isl_sched_edge
, graph
->n_edge
);
577 graph
->intra_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
578 graph
->inter_hmap
= isl_map_to_basic_set_alloc(ctx
, 2 * n_edge
);
580 if (!graph
->node
|| !graph
->region
|| (graph
->n_edge
&& !graph
->edge
) ||
584 for(i
= 0; i
< graph
->n
; ++i
)
585 graph
->sorted
[i
] = i
;
590 static void graph_free(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
594 isl_map_to_basic_set_free(graph
->intra_hmap
);
595 isl_map_to_basic_set_free(graph
->inter_hmap
);
597 for (i
= 0; i
< graph
->n
; ++i
) {
598 isl_space_free(graph
->node
[i
].dim
);
599 isl_mat_free(graph
->node
[i
].sched
);
600 isl_map_free(graph
->node
[i
].sched_map
);
601 isl_mat_free(graph
->node
[i
].cmap
);
602 isl_mat_free(graph
->node
[i
].cinv
);
604 free(graph
->node
[i
].band
);
605 free(graph
->node
[i
].band_id
);
606 free(graph
->node
[i
].zero
);
611 for (i
= 0; i
< graph
->n_edge
; ++i
)
612 isl_map_free(graph
->edge
[i
].map
);
615 for (i
= 0; i
<= isl_edge_last
; ++i
)
616 isl_hash_table_free(ctx
, graph
->edge_table
[i
]);
617 isl_hash_table_free(ctx
, graph
->node_table
);
618 isl_basic_set_free(graph
->lp
);
621 /* For each "set" on which this function is called, increment
622 * graph->n by one and update graph->maxvar.
624 static int init_n_maxvar(__isl_take isl_set
*set
, void *user
)
626 struct isl_sched_graph
*graph
= user
;
627 int nvar
= isl_set_dim(set
, isl_dim_set
);
630 if (nvar
> graph
->maxvar
)
631 graph
->maxvar
= nvar
;
638 /* Compute the number of rows that should be allocated for the schedule.
639 * The graph can be split at most "n - 1" times, there can be at most
640 * two rows for each dimension in the iteration domains (in particular,
641 * we usually have one row, but it may be split by split_scaled),
642 * and there can be one extra row for ordering the statements.
643 * Note that if we have actually split "n - 1" times, then no ordering
644 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
646 static int compute_max_row(struct isl_sched_graph
*graph
,
647 __isl_keep isl_union_set
*domain
)
651 if (isl_union_set_foreach_set(domain
, &init_n_maxvar
, graph
) < 0)
653 graph
->max_row
= graph
->n
+ 2 * graph
->maxvar
;
658 /* Add a new node to the graph representing the given set.
660 static int extract_node(__isl_take isl_set
*set
, void *user
)
666 struct isl_sched_graph
*graph
= user
;
667 int *band
, *band_id
, *zero
;
669 ctx
= isl_set_get_ctx(set
);
670 dim
= isl_set_get_space(set
);
672 nvar
= isl_space_dim(dim
, isl_dim_set
);
673 nparam
= isl_space_dim(dim
, isl_dim_param
);
674 if (!ctx
->opt
->schedule_parametric
)
676 sched
= isl_mat_alloc(ctx
, 0, 1 + nparam
+ nvar
);
677 graph
->node
[graph
->n
].dim
= dim
;
678 graph
->node
[graph
->n
].nvar
= nvar
;
679 graph
->node
[graph
->n
].nparam
= nparam
;
680 graph
->node
[graph
->n
].sched
= sched
;
681 graph
->node
[graph
->n
].sched_map
= NULL
;
682 band
= isl_alloc_array(ctx
, int, graph
->max_row
);
683 graph
->node
[graph
->n
].band
= band
;
684 band_id
= isl_calloc_array(ctx
, int, graph
->max_row
);
685 graph
->node
[graph
->n
].band_id
= band_id
;
686 zero
= isl_calloc_array(ctx
, int, graph
->max_row
);
687 graph
->node
[graph
->n
].zero
= zero
;
690 if (!sched
|| (graph
->max_row
&& (!band
|| !band_id
|| !zero
)))
696 struct isl_extract_edge_data
{
697 enum isl_edge_type type
;
698 struct isl_sched_graph
*graph
;
701 /* Merge edge2 into edge1, freeing the contents of edge2.
702 * "type" is the type of the schedule constraint from which edge2 was
704 * Return 0 on success and -1 on failure.
706 * edge1 and edge2 are assumed to have the same value for the map field.
708 static int merge_edge(enum isl_edge_type type
, struct isl_sched_edge
*edge1
,
709 struct isl_sched_edge
*edge2
)
711 edge1
->validity
|= edge2
->validity
;
712 edge1
->proximity
|= edge2
->proximity
;
713 isl_map_free(edge2
->map
);
718 /* Add a new edge to the graph based on the given map
719 * and add it to data->graph->edge_table[data->type].
720 * If a dependence relation of a given type happens to be identical
721 * to one of the dependence relations of a type that was added before,
722 * then we don't create a new edge, but instead mark the original edge
723 * as also representing a dependence of the current type.
725 static int extract_edge(__isl_take isl_map
*map
, void *user
)
727 isl_ctx
*ctx
= isl_map_get_ctx(map
);
728 struct isl_extract_edge_data
*data
= user
;
729 struct isl_sched_graph
*graph
= data
->graph
;
730 struct isl_sched_node
*src
, *dst
;
732 struct isl_sched_edge
*edge
;
735 dim
= isl_space_domain(isl_map_get_space(map
));
736 src
= graph_find_node(ctx
, graph
, dim
);
738 dim
= isl_space_range(isl_map_get_space(map
));
739 dst
= graph_find_node(ctx
, graph
, dim
);
747 graph
->edge
[graph
->n_edge
].src
= src
;
748 graph
->edge
[graph
->n_edge
].dst
= dst
;
749 graph
->edge
[graph
->n_edge
].map
= map
;
750 if (data
->type
== isl_edge_validity
) {
751 graph
->edge
[graph
->n_edge
].validity
= 1;
752 graph
->edge
[graph
->n_edge
].proximity
= 0;
754 if (data
->type
== isl_edge_proximity
) {
755 graph
->edge
[graph
->n_edge
].validity
= 0;
756 graph
->edge
[graph
->n_edge
].proximity
= 1;
760 edge
= graph_find_any_edge(graph
, src
, dst
);
762 return graph_edge_table_add(ctx
, graph
, data
->type
,
763 &graph
->edge
[graph
->n_edge
- 1]);
764 is_equal
= isl_map_plain_is_equal(map
, edge
->map
);
768 return graph_edge_table_add(ctx
, graph
, data
->type
,
769 &graph
->edge
[graph
->n_edge
- 1]);
772 if (merge_edge(data
->type
, edge
, &graph
->edge
[graph
->n_edge
]) < 0)
775 return graph_edge_table_add(ctx
, graph
, data
->type
, edge
);
778 /* Check whether there is any dependence from node[j] to node[i]
779 * or from node[i] to node[j].
781 static int node_follows_weak(int i
, int j
, void *user
)
784 struct isl_sched_graph
*graph
= user
;
786 f
= graph_has_any_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
789 return graph_has_any_edge(graph
, &graph
->node
[i
], &graph
->node
[j
]);
792 /* Check whether there is a validity dependence from node[j] to node[i],
793 * forcing node[i] to follow node[j].
795 static int node_follows_strong(int i
, int j
, void *user
)
797 struct isl_sched_graph
*graph
= user
;
799 return graph_has_validity_edge(graph
, &graph
->node
[j
], &graph
->node
[i
]);
802 /* Use Tarjan's algorithm for computing the strongly connected components
803 * in the dependence graph (only validity edges).
804 * If weak is set, we consider the graph to be undirected and
805 * we effectively compute the (weakly) connected components.
806 * Additionally, we also consider other edges when weak is set.
808 static int detect_ccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
, int weak
)
811 struct isl_tarjan_graph
*g
= NULL
;
813 g
= isl_tarjan_graph_init(ctx
, graph
->n
,
814 weak
? &node_follows_weak
: &node_follows_strong
, graph
);
822 while (g
->order
[i
] != -1) {
823 graph
->node
[g
->order
[i
]].scc
= graph
->scc
;
831 isl_tarjan_graph_free(g
);
836 /* Apply Tarjan's algorithm to detect the strongly connected components
837 * in the dependence graph.
839 static int detect_sccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
841 return detect_ccs(ctx
, graph
, 0);
844 /* Apply Tarjan's algorithm to detect the (weakly) connected components
845 * in the dependence graph.
847 static int detect_wccs(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
849 return detect_ccs(ctx
, graph
, 1);
852 static int cmp_scc(const void *a
, const void *b
, void *data
)
854 struct isl_sched_graph
*graph
= data
;
858 return graph
->node
[*i1
].scc
- graph
->node
[*i2
].scc
;
861 /* Sort the elements of graph->sorted according to the corresponding SCCs.
863 static int sort_sccs(struct isl_sched_graph
*graph
)
865 return isl_sort(graph
->sorted
, graph
->n
, sizeof(int), &cmp_scc
, graph
);
868 /* Given a dependence relation R from a node to itself,
869 * construct the set of coefficients of valid constraints for elements
870 * in that dependence relation.
871 * In particular, the result contains tuples of coefficients
872 * c_0, c_n, c_x such that
874 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
878 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
880 * We choose here to compute the dual of delta R.
881 * Alternatively, we could have computed the dual of R, resulting
882 * in a set of tuples c_0, c_n, c_x, c_y, and then
883 * plugged in (c_0, c_n, c_x, -c_x).
885 static __isl_give isl_basic_set
*intra_coefficients(
886 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
891 if (isl_map_to_basic_set_has(graph
->intra_hmap
, map
))
892 return isl_map_to_basic_set_get(graph
->intra_hmap
, map
);
894 delta
= isl_set_remove_divs(isl_map_deltas(isl_map_copy(map
)));
895 coef
= isl_set_coefficients(delta
);
896 graph
->intra_hmap
= isl_map_to_basic_set_set(graph
->intra_hmap
, map
,
897 isl_basic_set_copy(coef
));
902 /* Given a dependence relation R, * construct the set of coefficients
903 * of valid constraints for elements in that dependence relation.
904 * In particular, the result contains tuples of coefficients
905 * c_0, c_n, c_x, c_y such that
907 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
910 static __isl_give isl_basic_set
*inter_coefficients(
911 struct isl_sched_graph
*graph
, __isl_take isl_map
*map
)
916 if (isl_map_to_basic_set_has(graph
->inter_hmap
, map
))
917 return isl_map_to_basic_set_get(graph
->inter_hmap
, map
);
919 set
= isl_map_wrap(isl_map_remove_divs(isl_map_copy(map
)));
920 coef
= isl_set_coefficients(set
);
921 graph
->inter_hmap
= isl_map_to_basic_set_set(graph
->inter_hmap
, map
,
922 isl_basic_set_copy(coef
));
927 /* Add constraints to graph->lp that force validity for the given
928 * dependence from a node i to itself.
929 * That is, add constraints that enforce
931 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
932 * = c_i_x (y - x) >= 0
934 * for each (x,y) in R.
935 * We obtain general constraints on coefficients (c_0, c_n, c_x)
936 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
937 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
938 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
940 * Actually, we do not construct constraints for the c_i_x themselves,
941 * but for the coefficients of c_i_x written as a linear combination
942 * of the columns in node->cmap.
944 static int add_intra_validity_constraints(struct isl_sched_graph
*graph
,
945 struct isl_sched_edge
*edge
)
948 isl_map
*map
= isl_map_copy(edge
->map
);
949 isl_ctx
*ctx
= isl_map_get_ctx(map
);
951 isl_dim_map
*dim_map
;
953 struct isl_sched_node
*node
= edge
->src
;
955 coef
= intra_coefficients(graph
, map
);
957 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
959 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
960 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
964 total
= isl_basic_set_total_dim(graph
->lp
);
965 dim_map
= isl_dim_map_alloc(ctx
, total
);
966 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
967 isl_space_dim(dim
, isl_dim_set
), 1,
969 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
970 isl_space_dim(dim
, isl_dim_set
), 1,
972 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
973 coef
->n_eq
, coef
->n_ineq
);
974 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
984 /* Add constraints to graph->lp that force validity for the given
985 * dependence from node i to node j.
986 * That is, add constraints that enforce
988 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
990 * for each (x,y) in R.
991 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
992 * of valid constraints for R and then plug in
993 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
994 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
995 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
996 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
998 * Actually, we do not construct constraints for the c_*_x themselves,
999 * but for the coefficients of c_*_x written as a linear combination
1000 * of the columns in node->cmap.
1002 static int add_inter_validity_constraints(struct isl_sched_graph
*graph
,
1003 struct isl_sched_edge
*edge
)
1006 isl_map
*map
= isl_map_copy(edge
->map
);
1007 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1009 isl_dim_map
*dim_map
;
1010 isl_basic_set
*coef
;
1011 struct isl_sched_node
*src
= edge
->src
;
1012 struct isl_sched_node
*dst
= edge
->dst
;
1014 coef
= inter_coefficients(graph
, map
);
1016 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1018 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1019 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1020 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1021 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1022 isl_mat_copy(dst
->cmap
));
1026 total
= isl_basic_set_total_dim(graph
->lp
);
1027 dim_map
= isl_dim_map_alloc(ctx
, total
);
1029 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
1030 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
1031 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
1032 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1033 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1035 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1036 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1039 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
1040 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
1041 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
1042 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1043 isl_space_dim(dim
, isl_dim_set
), 1,
1045 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1046 isl_space_dim(dim
, isl_dim_set
), 1,
1049 edge
->start
= graph
->lp
->n_ineq
;
1050 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1051 coef
->n_eq
, coef
->n_ineq
);
1052 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1056 isl_space_free(dim
);
1057 edge
->end
= graph
->lp
->n_ineq
;
1061 isl_space_free(dim
);
1065 /* Add constraints to graph->lp that bound the dependence distance for the given
1066 * dependence from a node i to itself.
1067 * If s = 1, we add the constraint
1069 * c_i_x (y - x) <= m_0 + m_n n
1073 * -c_i_x (y - x) + m_0 + m_n n >= 0
1075 * for each (x,y) in R.
1076 * If s = -1, we add the constraint
1078 * -c_i_x (y - x) <= m_0 + m_n n
1082 * c_i_x (y - x) + m_0 + m_n n >= 0
1084 * for each (x,y) in R.
1085 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1086 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1087 * with each coefficient (except m_0) represented as a pair of non-negative
1090 * Actually, we do not construct constraints for the c_i_x themselves,
1091 * but for the coefficients of c_i_x written as a linear combination
1092 * of the columns in node->cmap.
1094 static int add_intra_proximity_constraints(struct isl_sched_graph
*graph
,
1095 struct isl_sched_edge
*edge
, int s
)
1099 isl_map
*map
= isl_map_copy(edge
->map
);
1100 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1102 isl_dim_map
*dim_map
;
1103 isl_basic_set
*coef
;
1104 struct isl_sched_node
*node
= edge
->src
;
1106 coef
= intra_coefficients(graph
, map
);
1108 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1110 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1111 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(node
->cmap
));
1115 nparam
= isl_space_dim(node
->dim
, isl_dim_param
);
1116 total
= isl_basic_set_total_dim(graph
->lp
);
1117 dim_map
= isl_dim_map_alloc(ctx
, total
);
1118 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1119 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1120 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1121 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
1122 isl_space_dim(dim
, isl_dim_set
), 1,
1124 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
1125 isl_space_dim(dim
, isl_dim_set
), 1,
1127 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1128 coef
->n_eq
, coef
->n_ineq
);
1129 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1131 isl_space_free(dim
);
1135 isl_space_free(dim
);
1139 /* Add constraints to graph->lp that bound the dependence distance for the given
1140 * dependence from node i to node j.
1141 * If s = 1, we add the constraint
1143 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1148 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1151 * for each (x,y) in R.
1152 * If s = -1, we add the constraint
1154 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1159 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1162 * for each (x,y) in R.
1163 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1164 * of valid constraints for R and then plug in
1165 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1167 * with each coefficient (except m_0, c_j_0 and c_i_0)
1168 * represented as a pair of non-negative coefficients.
1170 * Actually, we do not construct constraints for the c_*_x themselves,
1171 * but for the coefficients of c_*_x written as a linear combination
1172 * of the columns in node->cmap.
1174 static int add_inter_proximity_constraints(struct isl_sched_graph
*graph
,
1175 struct isl_sched_edge
*edge
, int s
)
1179 isl_map
*map
= isl_map_copy(edge
->map
);
1180 isl_ctx
*ctx
= isl_map_get_ctx(map
);
1182 isl_dim_map
*dim_map
;
1183 isl_basic_set
*coef
;
1184 struct isl_sched_node
*src
= edge
->src
;
1185 struct isl_sched_node
*dst
= edge
->dst
;
1187 coef
= inter_coefficients(graph
, map
);
1189 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
1191 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1192 isl_space_dim(dim
, isl_dim_set
), isl_mat_copy(src
->cmap
));
1193 coef
= isl_basic_set_transform_dims(coef
, isl_dim_set
,
1194 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
,
1195 isl_mat_copy(dst
->cmap
));
1199 nparam
= isl_space_dim(src
->dim
, isl_dim_param
);
1200 total
= isl_basic_set_total_dim(graph
->lp
);
1201 dim_map
= isl_dim_map_alloc(ctx
, total
);
1203 isl_dim_map_range(dim_map
, 1, 0, 0, 0, 1, 1);
1204 isl_dim_map_range(dim_map
, 4, 2, 1, 1, nparam
, -1);
1205 isl_dim_map_range(dim_map
, 5, 2, 1, 1, nparam
, 1);
1207 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, -s
);
1208 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, s
);
1209 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, -s
);
1210 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
1211 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1213 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
1214 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
1217 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, s
);
1218 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, -s
);
1219 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, s
);
1220 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
1221 isl_space_dim(dim
, isl_dim_set
), 1,
1223 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
1224 isl_space_dim(dim
, isl_dim_set
), 1,
1227 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
1228 coef
->n_eq
, coef
->n_ineq
);
1229 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
1231 isl_space_free(dim
);
1235 isl_space_free(dim
);
1239 static int add_all_validity_constraints(struct isl_sched_graph
*graph
)
1243 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1244 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1245 if (!edge
->validity
)
1247 if (edge
->src
!= edge
->dst
)
1249 if (add_intra_validity_constraints(graph
, edge
) < 0)
1253 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1254 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1255 if (!edge
->validity
)
1257 if (edge
->src
== edge
->dst
)
1259 if (add_inter_validity_constraints(graph
, edge
) < 0)
1266 /* Add constraints to graph->lp that bound the dependence distance
1267 * for all dependence relations.
1268 * If a given proximity dependence is identical to a validity
1269 * dependence, then the dependence distance is already bounded
1270 * from below (by zero), so we only need to bound the distance
1272 * Otherwise, we need to bound the distance both from above and from below.
1274 static int add_all_proximity_constraints(struct isl_sched_graph
*graph
)
1278 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1279 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1280 if (!edge
->proximity
)
1282 if (edge
->src
== edge
->dst
&&
1283 add_intra_proximity_constraints(graph
, edge
, 1) < 0)
1285 if (edge
->src
!= edge
->dst
&&
1286 add_inter_proximity_constraints(graph
, edge
, 1) < 0)
1290 if (edge
->src
== edge
->dst
&&
1291 add_intra_proximity_constraints(graph
, edge
, -1) < 0)
1293 if (edge
->src
!= edge
->dst
&&
1294 add_inter_proximity_constraints(graph
, edge
, -1) < 0)
1301 /* Compute a basis for the rows in the linear part of the schedule
1302 * and extend this basis to a full basis. The remaining rows
1303 * can then be used to force linear independence from the rows
1306 * In particular, given the schedule rows S, we compute
1311 * with H the Hermite normal form of S. That is, all but the
1312 * first rank columns of H are zero and so each row in S is
1313 * a linear combination of the first rank rows of Q.
1314 * The matrix Q is then transposed because we will write the
1315 * coefficients of the next schedule row as a column vector s
1316 * and express this s as a linear combination s = Q c of the
1318 * Similarly, the matrix U is transposed such that we can
1319 * compute the coefficients c = U s from a schedule row s.
1321 static int node_update_cmap(struct isl_sched_node
*node
)
1324 int n_row
= isl_mat_rows(node
->sched
);
1326 H
= isl_mat_sub_alloc(node
->sched
, 0, n_row
,
1327 1 + node
->nparam
, node
->nvar
);
1329 H
= isl_mat_left_hermite(H
, 0, &U
, &Q
);
1330 isl_mat_free(node
->cmap
);
1331 isl_mat_free(node
->cinv
);
1332 node
->cmap
= isl_mat_transpose(Q
);
1333 node
->cinv
= isl_mat_transpose(U
);
1334 node
->rank
= isl_mat_initial_non_zero_cols(H
);
1337 if (!node
->cmap
|| !node
->cinv
|| node
->rank
< 0)
1342 /* How many times should we count the constraints in "edge"?
1344 * If carry is set, then we are counting the number of (validity)
1345 * constraints that will be added in setup_carry_lp and we count
1346 * each edge exactly once. Otherwise, we count as follows
1347 * validity -> 1 (>= 0)
1348 * validity+proximity -> 2 (>= 0 and upper bound)
1349 * proximity -> 2 (lower and upper bound)
1351 static int edge_multiplicity(struct isl_sched_edge
*edge
, int carry
)
1353 if (carry
&& !edge
->validity
)
1357 if (edge
->proximity
)
1362 /* Count the number of equality and inequality constraints
1363 * that will be added for the given map.
1365 static int count_map_constraints(struct isl_sched_graph
*graph
,
1366 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
,
1367 int *n_eq
, int *n_ineq
, int carry
)
1369 isl_basic_set
*coef
;
1370 int f
= edge_multiplicity(edge
, carry
);
1377 if (edge
->src
== edge
->dst
)
1378 coef
= intra_coefficients(graph
, map
);
1380 coef
= inter_coefficients(graph
, map
);
1383 *n_eq
+= f
* coef
->n_eq
;
1384 *n_ineq
+= f
* coef
->n_ineq
;
1385 isl_basic_set_free(coef
);
1390 /* Count the number of equality and inequality constraints
1391 * that will be added to the main lp problem.
1392 * We count as follows
1393 * validity -> 1 (>= 0)
1394 * validity+proximity -> 2 (>= 0 and upper bound)
1395 * proximity -> 2 (lower and upper bound)
1397 static int count_constraints(struct isl_sched_graph
*graph
,
1398 int *n_eq
, int *n_ineq
)
1402 *n_eq
= *n_ineq
= 0;
1403 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1404 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1405 isl_map
*map
= isl_map_copy(edge
->map
);
1407 if (count_map_constraints(graph
, edge
, map
,
1408 n_eq
, n_ineq
, 0) < 0)
1415 /* Count the number of constraints that will be added by
1416 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1419 * In practice, add_bound_coefficient_constraints only adds inequalities.
1421 static int count_bound_coefficient_constraints(isl_ctx
*ctx
,
1422 struct isl_sched_graph
*graph
, int *n_eq
, int *n_ineq
)
1426 if (ctx
->opt
->schedule_max_coefficient
== -1)
1429 for (i
= 0; i
< graph
->n
; ++i
)
1430 *n_ineq
+= 2 * graph
->node
[i
].nparam
+ 2 * graph
->node
[i
].nvar
;
1435 /* Add constraints that bound the values of the variable and parameter
1436 * coefficients of the schedule.
1438 * The maximal value of the coefficients is defined by the option
1439 * 'schedule_max_coefficient'.
1441 static int add_bound_coefficient_constraints(isl_ctx
*ctx
,
1442 struct isl_sched_graph
*graph
)
1445 int max_coefficient
;
1448 max_coefficient
= ctx
->opt
->schedule_max_coefficient
;
1450 if (max_coefficient
== -1)
1453 total
= isl_basic_set_total_dim(graph
->lp
);
1455 for (i
= 0; i
< graph
->n
; ++i
) {
1456 struct isl_sched_node
*node
= &graph
->node
[i
];
1457 for (j
= 0; j
< 2 * node
->nparam
+ 2 * node
->nvar
; ++j
) {
1459 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1462 dim
= 1 + node
->start
+ 1 + j
;
1463 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1464 isl_int_set_si(graph
->lp
->ineq
[k
][dim
], -1);
1465 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_coefficient
);
1472 /* Construct an ILP problem for finding schedule coefficients
1473 * that result in non-negative, but small dependence distances
1474 * over all dependences.
1475 * In particular, the dependence distances over proximity edges
1476 * are bounded by m_0 + m_n n and we compute schedule coefficients
1477 * with small values (preferably zero) of m_n and m_0.
1479 * All variables of the ILP are non-negative. The actual coefficients
1480 * may be negative, so each coefficient is represented as the difference
1481 * of two non-negative variables. The negative part always appears
1482 * immediately before the positive part.
1483 * Other than that, the variables have the following order
1485 * - sum of positive and negative parts of m_n coefficients
1487 * - sum of positive and negative parts of all c_n coefficients
1488 * (unconstrained when computing non-parametric schedules)
1489 * - sum of positive and negative parts of all c_x coefficients
1490 * - positive and negative parts of m_n coefficients
1493 * - positive and negative parts of c_i_n (if parametric)
1494 * - positive and negative parts of c_i_x
1496 * The c_i_x are not represented directly, but through the columns of
1497 * node->cmap. That is, the computed values are for variable t_i_x
1498 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1500 * The constraints are those from the edges plus two or three equalities
1501 * to express the sums.
1503 * If force_zero is set, then we add equalities to ensure that
1504 * the sum of the m_n coefficients and m_0 are both zero.
1506 static int setup_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
,
1517 int max_constant_term
;
1519 max_constant_term
= ctx
->opt
->schedule_max_constant_term
;
1521 parametric
= ctx
->opt
->schedule_parametric
;
1522 nparam
= isl_space_dim(graph
->node
[0].dim
, isl_dim_param
);
1524 total
= param_pos
+ 2 * nparam
;
1525 for (i
= 0; i
< graph
->n
; ++i
) {
1526 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
1527 if (node_update_cmap(node
) < 0)
1529 node
->start
= total
;
1530 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
1533 if (count_constraints(graph
, &n_eq
, &n_ineq
) < 0)
1535 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
1538 dim
= isl_space_set_alloc(ctx
, 0, total
);
1539 isl_basic_set_free(graph
->lp
);
1540 n_eq
+= 2 + parametric
+ force_zero
;
1541 if (max_constant_term
!= -1)
1544 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
1546 k
= isl_basic_set_alloc_equality(graph
->lp
);
1549 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1551 isl_int_set_si(graph
->lp
->eq
[k
][1], -1);
1552 for (i
= 0; i
< 2 * nparam
; ++i
)
1553 isl_int_set_si(graph
->lp
->eq
[k
][1 + param_pos
+ i
], 1);
1556 k
= isl_basic_set_alloc_equality(graph
->lp
);
1559 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1560 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
1564 k
= isl_basic_set_alloc_equality(graph
->lp
);
1567 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1568 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
1569 for (i
= 0; i
< graph
->n
; ++i
) {
1570 int pos
= 1 + graph
->node
[i
].start
+ 1;
1572 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
1573 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1577 k
= isl_basic_set_alloc_equality(graph
->lp
);
1580 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
1581 isl_int_set_si(graph
->lp
->eq
[k
][4], -1);
1582 for (i
= 0; i
< graph
->n
; ++i
) {
1583 struct isl_sched_node
*node
= &graph
->node
[i
];
1584 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
1586 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
1587 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
1590 if (max_constant_term
!= -1)
1591 for (i
= 0; i
< graph
->n
; ++i
) {
1592 struct isl_sched_node
*node
= &graph
->node
[i
];
1593 k
= isl_basic_set_alloc_inequality(graph
->lp
);
1596 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
1597 isl_int_set_si(graph
->lp
->ineq
[k
][1 + node
->start
], -1);
1598 isl_int_set_si(graph
->lp
->ineq
[k
][0], max_constant_term
);
1601 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
1603 if (add_all_validity_constraints(graph
) < 0)
1605 if (add_all_proximity_constraints(graph
) < 0)
1611 /* Analyze the conflicting constraint found by
1612 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
1613 * constraint of one of the edges between distinct nodes, living, moreover
1614 * in distinct SCCs, then record the source and sink SCC as this may
1615 * be a good place to cut between SCCs.
1617 static int check_conflict(int con
, void *user
)
1620 struct isl_sched_graph
*graph
= user
;
1622 if (graph
->src_scc
>= 0)
1625 con
-= graph
->lp
->n_eq
;
1627 if (con
>= graph
->lp
->n_ineq
)
1630 for (i
= 0; i
< graph
->n_edge
; ++i
) {
1631 if (!graph
->edge
[i
].validity
)
1633 if (graph
->edge
[i
].src
== graph
->edge
[i
].dst
)
1635 if (graph
->edge
[i
].src
->scc
== graph
->edge
[i
].dst
->scc
)
1637 if (graph
->edge
[i
].start
> con
)
1639 if (graph
->edge
[i
].end
<= con
)
1641 graph
->src_scc
= graph
->edge
[i
].src
->scc
;
1642 graph
->dst_scc
= graph
->edge
[i
].dst
->scc
;
1648 /* Check whether the next schedule row of the given node needs to be
1649 * non-trivial. Lower-dimensional domains may have some trivial rows,
1650 * but as soon as the number of remaining required non-trivial rows
1651 * is as large as the number or remaining rows to be computed,
1652 * all remaining rows need to be non-trivial.
1654 static int needs_row(struct isl_sched_graph
*graph
, struct isl_sched_node
*node
)
1656 return node
->nvar
- node
->rank
>= graph
->maxvar
- graph
->n_row
;
1659 /* Solve the ILP problem constructed in setup_lp.
1660 * For each node such that all the remaining rows of its schedule
1661 * need to be non-trivial, we construct a non-triviality region.
1662 * This region imposes that the next row is independent of previous rows.
1663 * In particular the coefficients c_i_x are represented by t_i_x
1664 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1665 * its first columns span the rows of the previously computed part
1666 * of the schedule. The non-triviality region enforces that at least
1667 * one of the remaining components of t_i_x is non-zero, i.e.,
1668 * that the new schedule row depends on at least one of the remaining
1671 static __isl_give isl_vec
*solve_lp(struct isl_sched_graph
*graph
)
1677 for (i
= 0; i
< graph
->n
; ++i
) {
1678 struct isl_sched_node
*node
= &graph
->node
[i
];
1679 int skip
= node
->rank
;
1680 graph
->region
[i
].pos
= node
->start
+ 1 + 2*(node
->nparam
+skip
);
1681 if (needs_row(graph
, node
))
1682 graph
->region
[i
].len
= 2 * (node
->nvar
- skip
);
1684 graph
->region
[i
].len
= 0;
1686 lp
= isl_basic_set_copy(graph
->lp
);
1687 sol
= isl_tab_basic_set_non_trivial_lexmin(lp
, 2, graph
->n
,
1688 graph
->region
, &check_conflict
, graph
);
1692 /* Update the schedules of all nodes based on the given solution
1693 * of the LP problem.
1694 * The new row is added to the current band.
1695 * All possibly negative coefficients are encoded as a difference
1696 * of two non-negative variables, so we need to perform the subtraction
1697 * here. Moreover, if use_cmap is set, then the solution does
1698 * not refer to the actual coefficients c_i_x, but instead to variables
1699 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1700 * In this case, we then also need to perform this multiplication
1701 * to obtain the values of c_i_x.
1703 * If check_zero is set, then the first two coordinates of sol are
1704 * assumed to correspond to the dependence distance. If these two
1705 * coordinates are zero, then the corresponding scheduling dimension
1706 * is marked as being zero distance.
1708 static int update_schedule(struct isl_sched_graph
*graph
,
1709 __isl_take isl_vec
*sol
, int use_cmap
, int check_zero
)
1713 isl_vec
*csol
= NULL
;
1718 isl_die(sol
->ctx
, isl_error_internal
,
1719 "no solution found", goto error
);
1720 if (graph
->n_total_row
>= graph
->max_row
)
1721 isl_die(sol
->ctx
, isl_error_internal
,
1722 "too many schedule rows", goto error
);
1725 zero
= isl_int_is_zero(sol
->el
[1]) &&
1726 isl_int_is_zero(sol
->el
[2]);
1728 for (i
= 0; i
< graph
->n
; ++i
) {
1729 struct isl_sched_node
*node
= &graph
->node
[i
];
1730 int pos
= node
->start
;
1731 int row
= isl_mat_rows(node
->sched
);
1734 csol
= isl_vec_alloc(sol
->ctx
, node
->nvar
);
1738 isl_map_free(node
->sched_map
);
1739 node
->sched_map
= NULL
;
1740 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1743 node
->sched
= isl_mat_set_element(node
->sched
, row
, 0,
1745 for (j
= 0; j
< node
->nparam
+ node
->nvar
; ++j
)
1746 isl_int_sub(sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1747 sol
->el
[1 + pos
+ 1 + 2 * j
+ 1],
1748 sol
->el
[1 + pos
+ 1 + 2 * j
]);
1749 for (j
= 0; j
< node
->nparam
; ++j
)
1750 node
->sched
= isl_mat_set_element(node
->sched
,
1751 row
, 1 + j
, sol
->el
[1+pos
+1+2*j
+1]);
1752 for (j
= 0; j
< node
->nvar
; ++j
)
1753 isl_int_set(csol
->el
[j
],
1754 sol
->el
[1+pos
+1+2*(node
->nparam
+j
)+1]);
1756 csol
= isl_mat_vec_product(isl_mat_copy(node
->cmap
),
1760 for (j
= 0; j
< node
->nvar
; ++j
)
1761 node
->sched
= isl_mat_set_element(node
->sched
,
1762 row
, 1 + node
->nparam
+ j
, csol
->el
[j
]);
1763 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1764 node
->zero
[graph
->n_total_row
] = zero
;
1770 graph
->n_total_row
++;
1779 /* Convert row "row" of node->sched into an isl_aff living in "ls"
1780 * and return this isl_aff.
1782 static __isl_give isl_aff
*extract_schedule_row(__isl_take isl_local_space
*ls
,
1783 struct isl_sched_node
*node
, int row
)
1791 aff
= isl_aff_zero_on_domain(ls
);
1792 isl_mat_get_element(node
->sched
, row
, 0, &v
);
1793 aff
= isl_aff_set_constant(aff
, v
);
1794 for (j
= 0; j
< node
->nparam
; ++j
) {
1795 isl_mat_get_element(node
->sched
, row
, 1 + j
, &v
);
1796 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, j
, v
);
1798 for (j
= 0; j
< node
->nvar
; ++j
) {
1799 isl_mat_get_element(node
->sched
, row
, 1 + node
->nparam
+ j
, &v
);
1800 aff
= isl_aff_set_coefficient(aff
, isl_dim_in
, j
, v
);
1808 /* Convert node->sched into a multi_aff and return this multi_aff.
1810 static __isl_give isl_multi_aff
*node_extract_schedule_multi_aff(
1811 struct isl_sched_node
*node
)
1815 isl_local_space
*ls
;
1820 nrow
= isl_mat_rows(node
->sched
);
1821 ncol
= isl_mat_cols(node
->sched
) - 1;
1822 space
= isl_space_from_domain(isl_space_copy(node
->dim
));
1823 space
= isl_space_add_dims(space
, isl_dim_out
, nrow
);
1824 ma
= isl_multi_aff_zero(space
);
1825 ls
= isl_local_space_from_space(isl_space_copy(node
->dim
));
1827 for (i
= 0; i
< nrow
; ++i
) {
1828 aff
= extract_schedule_row(isl_local_space_copy(ls
), node
, i
);
1829 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
1832 isl_local_space_free(ls
);
1837 /* Convert node->sched into a map and return this map.
1839 * The result is cached in node->sched_map, which needs to be released
1840 * whenever node->sched is updated.
1842 static __isl_give isl_map
*node_extract_schedule(struct isl_sched_node
*node
)
1844 if (!node
->sched_map
) {
1847 ma
= node_extract_schedule_multi_aff(node
);
1848 node
->sched_map
= isl_map_from_multi_aff(ma
);
1851 return isl_map_copy(node
->sched_map
);
1854 /* Update the given dependence relation based on the current schedule.
1855 * That is, intersect the dependence relation with a map expressing
1856 * that source and sink are executed within the same iteration of
1857 * the current schedule.
1858 * This is not the most efficient way, but this shouldn't be a critical
1861 static __isl_give isl_map
*specialize(__isl_take isl_map
*map
,
1862 struct isl_sched_node
*src
, struct isl_sched_node
*dst
)
1864 isl_map
*src_sched
, *dst_sched
, *id
;
1866 src_sched
= node_extract_schedule(src
);
1867 dst_sched
= node_extract_schedule(dst
);
1868 id
= isl_map_apply_range(src_sched
, isl_map_reverse(dst_sched
));
1869 return isl_map_intersect(map
, id
);
1872 /* Update the dependence relations of all edges based on the current schedule.
1873 * If a dependence is carried completely by the current schedule, then
1874 * it is removed from the edge_tables. It is kept in the list of edges
1875 * as otherwise all edge_tables would have to be recomputed.
1877 static int update_edges(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1881 for (i
= graph
->n_edge
- 1; i
>= 0; --i
) {
1882 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
1883 edge
->map
= specialize(edge
->map
, edge
->src
, edge
->dst
);
1887 if (isl_map_plain_is_empty(edge
->map
))
1888 graph_remove_edge(graph
, edge
);
1894 static void next_band(struct isl_sched_graph
*graph
)
1896 graph
->band_start
= graph
->n_total_row
;
1900 /* Topologically sort statements mapped to the same schedule iteration
1901 * and add a row to the schedule corresponding to this order.
1903 static int sort_statements(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
1910 if (update_edges(ctx
, graph
) < 0)
1913 if (graph
->n_edge
== 0)
1916 if (detect_sccs(ctx
, graph
) < 0)
1919 if (graph
->n_total_row
>= graph
->max_row
)
1920 isl_die(ctx
, isl_error_internal
,
1921 "too many schedule rows", return -1);
1923 for (i
= 0; i
< graph
->n
; ++i
) {
1924 struct isl_sched_node
*node
= &graph
->node
[i
];
1925 int row
= isl_mat_rows(node
->sched
);
1926 int cols
= isl_mat_cols(node
->sched
);
1928 isl_map_free(node
->sched_map
);
1929 node
->sched_map
= NULL
;
1930 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
1933 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
1935 for (j
= 1; j
< cols
; ++j
)
1936 node
->sched
= isl_mat_set_element_si(node
->sched
,
1938 node
->band
[graph
->n_total_row
] = graph
->n_band
;
1941 graph
->n_total_row
++;
1947 /* Construct an isl_schedule based on the computed schedule stored
1948 * in graph and with parameters specified by dim.
1950 static __isl_give isl_schedule
*extract_schedule(struct isl_sched_graph
*graph
,
1951 __isl_take isl_space
*dim
)
1955 isl_schedule
*sched
= NULL
;
1960 ctx
= isl_space_get_ctx(dim
);
1961 sched
= isl_calloc(ctx
, struct isl_schedule
,
1962 sizeof(struct isl_schedule
) +
1963 (graph
->n
- 1) * sizeof(struct isl_schedule_node
));
1968 sched
->n
= graph
->n
;
1969 sched
->n_band
= graph
->n_band
;
1970 sched
->n_total_row
= graph
->n_total_row
;
1972 for (i
= 0; i
< sched
->n
; ++i
) {
1974 int *band_end
, *band_id
, *zero
;
1976 sched
->node
[i
].sched
=
1977 node_extract_schedule_multi_aff(&graph
->node
[i
]);
1978 if (!sched
->node
[i
].sched
)
1981 sched
->node
[i
].n_band
= graph
->n_band
;
1982 if (graph
->n_band
== 0)
1985 band_end
= isl_alloc_array(ctx
, int, graph
->n_band
);
1986 band_id
= isl_alloc_array(ctx
, int, graph
->n_band
);
1987 zero
= isl_alloc_array(ctx
, int, graph
->n_total_row
);
1988 sched
->node
[i
].band_end
= band_end
;
1989 sched
->node
[i
].band_id
= band_id
;
1990 sched
->node
[i
].zero
= zero
;
1991 if (!band_end
|| !band_id
|| !zero
)
1994 for (r
= 0; r
< graph
->n_total_row
; ++r
)
1995 zero
[r
] = graph
->node
[i
].zero
[r
];
1996 for (r
= b
= 0; r
< graph
->n_total_row
; ++r
) {
1997 if (graph
->node
[i
].band
[r
] == b
)
2000 if (graph
->node
[i
].band
[r
] == -1)
2003 if (r
== graph
->n_total_row
)
2005 sched
->node
[i
].n_band
= b
;
2006 for (--b
; b
>= 0; --b
)
2007 band_id
[b
] = graph
->node
[i
].band_id
[b
];
2014 isl_space_free(dim
);
2015 isl_schedule_free(sched
);
2019 /* Copy nodes that satisfy node_pred from the src dependence graph
2020 * to the dst dependence graph.
2022 static int copy_nodes(struct isl_sched_graph
*dst
, struct isl_sched_graph
*src
,
2023 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2028 for (i
= 0; i
< src
->n
; ++i
) {
2029 if (!node_pred(&src
->node
[i
], data
))
2031 dst
->node
[dst
->n
].dim
= isl_space_copy(src
->node
[i
].dim
);
2032 dst
->node
[dst
->n
].nvar
= src
->node
[i
].nvar
;
2033 dst
->node
[dst
->n
].nparam
= src
->node
[i
].nparam
;
2034 dst
->node
[dst
->n
].sched
= isl_mat_copy(src
->node
[i
].sched
);
2035 dst
->node
[dst
->n
].sched_map
=
2036 isl_map_copy(src
->node
[i
].sched_map
);
2037 dst
->node
[dst
->n
].band
= src
->node
[i
].band
;
2038 dst
->node
[dst
->n
].band_id
= src
->node
[i
].band_id
;
2039 dst
->node
[dst
->n
].zero
= src
->node
[i
].zero
;
2046 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2047 * to the dst dependence graph.
2048 * If the source or destination node of the edge is not in the destination
2049 * graph, then it must be a backward proximity edge and it should simply
2052 static int copy_edges(isl_ctx
*ctx
, struct isl_sched_graph
*dst
,
2053 struct isl_sched_graph
*src
,
2054 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
), int data
)
2057 enum isl_edge_type t
;
2060 for (i
= 0; i
< src
->n_edge
; ++i
) {
2061 struct isl_sched_edge
*edge
= &src
->edge
[i
];
2063 struct isl_sched_node
*dst_src
, *dst_dst
;
2065 if (!edge_pred(edge
, data
))
2068 if (isl_map_plain_is_empty(edge
->map
))
2071 dst_src
= graph_find_node(ctx
, dst
, edge
->src
->dim
);
2072 dst_dst
= graph_find_node(ctx
, dst
, edge
->dst
->dim
);
2073 if (!dst_src
|| !dst_dst
) {
2075 isl_die(ctx
, isl_error_internal
,
2076 "backward validity edge", return -1);
2080 map
= isl_map_copy(edge
->map
);
2082 dst
->edge
[dst
->n_edge
].src
= dst_src
;
2083 dst
->edge
[dst
->n_edge
].dst
= dst_dst
;
2084 dst
->edge
[dst
->n_edge
].map
= map
;
2085 dst
->edge
[dst
->n_edge
].validity
= edge
->validity
;
2086 dst
->edge
[dst
->n_edge
].proximity
= edge
->proximity
;
2089 for (t
= isl_edge_first
; t
<= isl_edge_last
; ++t
) {
2091 graph_find_edge(src
, t
, edge
->src
, edge
->dst
))
2093 if (graph_edge_table_add(ctx
, dst
, t
,
2094 &dst
->edge
[dst
->n_edge
- 1]) < 0)
2102 /* Given a "src" dependence graph that contains the nodes from "dst"
2103 * that satisfy node_pred, copy the schedule computed in "src"
2104 * for those nodes back to "dst".
2106 static int copy_schedule(struct isl_sched_graph
*dst
,
2107 struct isl_sched_graph
*src
,
2108 int (*node_pred
)(struct isl_sched_node
*node
, int data
), int data
)
2113 for (i
= 0; i
< dst
->n
; ++i
) {
2114 if (!node_pred(&dst
->node
[i
], data
))
2116 isl_mat_free(dst
->node
[i
].sched
);
2117 isl_map_free(dst
->node
[i
].sched_map
);
2118 dst
->node
[i
].sched
= isl_mat_copy(src
->node
[src
->n
].sched
);
2119 dst
->node
[i
].sched_map
=
2120 isl_map_copy(src
->node
[src
->n
].sched_map
);
2124 dst
->max_row
= src
->max_row
;
2125 dst
->n_total_row
= src
->n_total_row
;
2126 dst
->n_band
= src
->n_band
;
2131 /* Compute the maximal number of variables over all nodes.
2132 * This is the maximal number of linearly independent schedule
2133 * rows that we need to compute.
2134 * Just in case we end up in a part of the dependence graph
2135 * with only lower-dimensional domains, we make sure we will
2136 * compute the required amount of extra linearly independent rows.
2138 static int compute_maxvar(struct isl_sched_graph
*graph
)
2143 for (i
= 0; i
< graph
->n
; ++i
) {
2144 struct isl_sched_node
*node
= &graph
->node
[i
];
2147 if (node_update_cmap(node
) < 0)
2149 nvar
= node
->nvar
+ graph
->n_row
- node
->rank
;
2150 if (nvar
> graph
->maxvar
)
2151 graph
->maxvar
= nvar
;
2157 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2158 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
);
2160 /* Compute a schedule for a subgraph of "graph". In particular, for
2161 * the graph composed of nodes that satisfy node_pred and edges that
2162 * that satisfy edge_pred. The caller should precompute the number
2163 * of nodes and edges that satisfy these predicates and pass them along
2164 * as "n" and "n_edge".
2165 * If the subgraph is known to consist of a single component, then wcc should
2166 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2167 * Otherwise, we call compute_schedule, which will check whether the subgraph
2170 static int compute_sub_schedule(isl_ctx
*ctx
,
2171 struct isl_sched_graph
*graph
, int n
, int n_edge
,
2172 int (*node_pred
)(struct isl_sched_node
*node
, int data
),
2173 int (*edge_pred
)(struct isl_sched_edge
*edge
, int data
),
2176 struct isl_sched_graph split
= { 0 };
2179 if (graph_alloc(ctx
, &split
, n
, n_edge
) < 0)
2181 if (copy_nodes(&split
, graph
, node_pred
, data
) < 0)
2183 if (graph_init_table(ctx
, &split
) < 0)
2185 for (t
= 0; t
<= isl_edge_last
; ++t
)
2186 split
.max_edge
[t
] = graph
->max_edge
[t
];
2187 if (graph_init_edge_tables(ctx
, &split
) < 0)
2189 if (copy_edges(ctx
, &split
, graph
, edge_pred
, data
) < 0)
2191 split
.n_row
= graph
->n_row
;
2192 split
.max_row
= graph
->max_row
;
2193 split
.n_total_row
= graph
->n_total_row
;
2194 split
.n_band
= graph
->n_band
;
2195 split
.band_start
= graph
->band_start
;
2197 if (wcc
&& compute_schedule_wcc(ctx
, &split
) < 0)
2199 if (!wcc
&& compute_schedule(ctx
, &split
) < 0)
2202 copy_schedule(graph
, &split
, node_pred
, data
);
2204 graph_free(ctx
, &split
);
2207 graph_free(ctx
, &split
);
2211 static int node_scc_exactly(struct isl_sched_node
*node
, int scc
)
2213 return node
->scc
== scc
;
2216 static int node_scc_at_most(struct isl_sched_node
*node
, int scc
)
2218 return node
->scc
<= scc
;
2221 static int node_scc_at_least(struct isl_sched_node
*node
, int scc
)
2223 return node
->scc
>= scc
;
2226 static int edge_scc_exactly(struct isl_sched_edge
*edge
, int scc
)
2228 return edge
->src
->scc
== scc
&& edge
->dst
->scc
== scc
;
2231 static int edge_dst_scc_at_most(struct isl_sched_edge
*edge
, int scc
)
2233 return edge
->dst
->scc
<= scc
;
2236 static int edge_src_scc_at_least(struct isl_sched_edge
*edge
, int scc
)
2238 return edge
->src
->scc
>= scc
;
2241 /* Pad the schedules of all nodes with zero rows such that in the end
2242 * they all have graph->n_total_row rows.
2243 * The extra rows don't belong to any band, so they get assigned band number -1.
2245 static int pad_schedule(struct isl_sched_graph
*graph
)
2249 for (i
= 0; i
< graph
->n
; ++i
) {
2250 struct isl_sched_node
*node
= &graph
->node
[i
];
2251 int row
= isl_mat_rows(node
->sched
);
2252 if (graph
->n_total_row
> row
) {
2253 isl_map_free(node
->sched_map
);
2254 node
->sched_map
= NULL
;
2256 node
->sched
= isl_mat_add_zero_rows(node
->sched
,
2257 graph
->n_total_row
- row
);
2260 for (j
= row
; j
< graph
->n_total_row
; ++j
)
2267 /* Reset the current band by dropping all its schedule rows.
2269 static int reset_band(struct isl_sched_graph
*graph
)
2274 drop
= graph
->n_total_row
- graph
->band_start
;
2275 graph
->n_total_row
-= drop
;
2276 graph
->n_row
-= drop
;
2278 for (i
= 0; i
< graph
->n
; ++i
) {
2279 struct isl_sched_node
*node
= &graph
->node
[i
];
2281 isl_map_free(node
->sched_map
);
2282 node
->sched_map
= NULL
;
2284 node
->sched
= isl_mat_drop_rows(node
->sched
,
2285 graph
->band_start
, drop
);
2294 /* Split the current graph into two parts and compute a schedule for each
2295 * part individually. In particular, one part consists of all SCCs up
2296 * to and including graph->src_scc, while the other part contains the other
2299 * The split is enforced in the schedule by constant rows with two different
2300 * values (0 and 1). These constant rows replace the previously computed rows
2301 * in the current band.
2302 * It would be possible to reuse them as the first rows in the next
2303 * band, but recomputing them may result in better rows as we are looking
2304 * at a smaller part of the dependence graph.
2305 * compute_split_schedule is only called when no zero-distance schedule row
2306 * could be found on the entire graph, so we wark the splitting row as
2307 * non zero-distance.
2309 * The band_id of the second group is set to n, where n is the number
2310 * of nodes in the first group. This ensures that the band_ids over
2311 * the two groups remain disjoint, even if either or both of the two
2312 * groups contain independent components.
2314 static int compute_split_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2316 int i
, j
, n
, e1
, e2
;
2317 int n_total_row
, orig_total_row
;
2318 int n_band
, orig_band
;
2320 if (graph
->n_total_row
>= graph
->max_row
)
2321 isl_die(ctx
, isl_error_internal
,
2322 "too many schedule rows", return -1);
2324 if (reset_band(graph
) < 0)
2328 for (i
= 0; i
< graph
->n
; ++i
) {
2329 struct isl_sched_node
*node
= &graph
->node
[i
];
2330 int row
= isl_mat_rows(node
->sched
);
2331 int cols
= isl_mat_cols(node
->sched
);
2332 int before
= node
->scc
<= graph
->src_scc
;
2337 isl_map_free(node
->sched_map
);
2338 node
->sched_map
= NULL
;
2339 node
->sched
= isl_mat_add_rows(node
->sched
, 1);
2342 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
2344 for (j
= 1; j
< cols
; ++j
)
2345 node
->sched
= isl_mat_set_element_si(node
->sched
,
2347 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2348 node
->zero
[graph
->n_total_row
] = 0;
2352 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2353 if (graph
->edge
[i
].dst
->scc
<= graph
->src_scc
)
2355 if (graph
->edge
[i
].src
->scc
> graph
->src_scc
)
2359 graph
->n_total_row
++;
2362 for (i
= 0; i
< graph
->n
; ++i
) {
2363 struct isl_sched_node
*node
= &graph
->node
[i
];
2364 if (node
->scc
> graph
->src_scc
)
2365 node
->band_id
[graph
->n_band
] = n
;
2368 orig_total_row
= graph
->n_total_row
;
2369 orig_band
= graph
->n_band
;
2370 if (compute_sub_schedule(ctx
, graph
, n
, e1
,
2371 &node_scc_at_most
, &edge_dst_scc_at_most
,
2372 graph
->src_scc
, 0) < 0)
2374 n_total_row
= graph
->n_total_row
;
2375 graph
->n_total_row
= orig_total_row
;
2376 n_band
= graph
->n_band
;
2377 graph
->n_band
= orig_band
;
2378 if (compute_sub_schedule(ctx
, graph
, graph
->n
- n
, e2
,
2379 &node_scc_at_least
, &edge_src_scc_at_least
,
2380 graph
->src_scc
+ 1, 0) < 0)
2382 if (n_total_row
> graph
->n_total_row
)
2383 graph
->n_total_row
= n_total_row
;
2384 if (n_band
> graph
->n_band
)
2385 graph
->n_band
= n_band
;
2387 return pad_schedule(graph
);
2390 /* Compute the next band of the schedule after updating the dependence
2391 * relations based on the the current schedule.
2393 static int compute_next_band(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2395 if (update_edges(ctx
, graph
) < 0)
2399 return compute_schedule(ctx
, graph
);
2402 /* Add constraints to graph->lp that force the dependence "map" (which
2403 * is part of the dependence relation of "edge")
2404 * to be respected and attempt to carry it, where the edge is one from
2405 * a node j to itself. "pos" is the sequence number of the given map.
2406 * That is, add constraints that enforce
2408 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
2409 * = c_j_x (y - x) >= e_i
2411 * for each (x,y) in R.
2412 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2413 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
2414 * with each coefficient in c_j_x represented as a pair of non-negative
2417 static int add_intra_constraints(struct isl_sched_graph
*graph
,
2418 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2421 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2423 isl_dim_map
*dim_map
;
2424 isl_basic_set
*coef
;
2425 struct isl_sched_node
*node
= edge
->src
;
2427 coef
= intra_coefficients(graph
, map
);
2431 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2433 total
= isl_basic_set_total_dim(graph
->lp
);
2434 dim_map
= isl_dim_map_alloc(ctx
, total
);
2435 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2436 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 1, 2,
2437 isl_space_dim(dim
, isl_dim_set
), 1,
2439 isl_dim_map_range(dim_map
, node
->start
+ 2 * node
->nparam
+ 2, 2,
2440 isl_space_dim(dim
, isl_dim_set
), 1,
2442 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2443 coef
->n_eq
, coef
->n_ineq
);
2444 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2446 isl_space_free(dim
);
2451 /* Add constraints to graph->lp that force the dependence "map" (which
2452 * is part of the dependence relation of "edge")
2453 * to be respected and attempt to carry it, where the edge is one from
2454 * node j to node k. "pos" is the sequence number of the given map.
2455 * That is, add constraints that enforce
2457 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2459 * for each (x,y) in R.
2460 * We obtain general constraints on coefficients (c_0, c_n, c_x)
2461 * of valid constraints for R and then plug in
2462 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2463 * with each coefficient (except e_i, c_k_0 and c_j_0)
2464 * represented as a pair of non-negative coefficients.
2466 static int add_inter_constraints(struct isl_sched_graph
*graph
,
2467 struct isl_sched_edge
*edge
, __isl_take isl_map
*map
, int pos
)
2470 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2472 isl_dim_map
*dim_map
;
2473 isl_basic_set
*coef
;
2474 struct isl_sched_node
*src
= edge
->src
;
2475 struct isl_sched_node
*dst
= edge
->dst
;
2477 coef
= inter_coefficients(graph
, map
);
2481 dim
= isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef
)));
2483 total
= isl_basic_set_total_dim(graph
->lp
);
2484 dim_map
= isl_dim_map_alloc(ctx
, total
);
2486 isl_dim_map_range(dim_map
, 3 + pos
, 0, 0, 0, 1, -1);
2488 isl_dim_map_range(dim_map
, dst
->start
, 0, 0, 0, 1, 1);
2489 isl_dim_map_range(dim_map
, dst
->start
+ 1, 2, 1, 1, dst
->nparam
, -1);
2490 isl_dim_map_range(dim_map
, dst
->start
+ 2, 2, 1, 1, dst
->nparam
, 1);
2491 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 1, 2,
2492 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2494 isl_dim_map_range(dim_map
, dst
->start
+ 2 * dst
->nparam
+ 2, 2,
2495 isl_space_dim(dim
, isl_dim_set
) + src
->nvar
, 1,
2498 isl_dim_map_range(dim_map
, src
->start
, 0, 0, 0, 1, -1);
2499 isl_dim_map_range(dim_map
, src
->start
+ 1, 2, 1, 1, src
->nparam
, 1);
2500 isl_dim_map_range(dim_map
, src
->start
+ 2, 2, 1, 1, src
->nparam
, -1);
2501 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 1, 2,
2502 isl_space_dim(dim
, isl_dim_set
), 1,
2504 isl_dim_map_range(dim_map
, src
->start
+ 2 * src
->nparam
+ 2, 2,
2505 isl_space_dim(dim
, isl_dim_set
), 1,
2508 graph
->lp
= isl_basic_set_extend_constraints(graph
->lp
,
2509 coef
->n_eq
, coef
->n_ineq
);
2510 graph
->lp
= isl_basic_set_add_constraints_dim_map(graph
->lp
,
2512 isl_space_free(dim
);
2517 /* Add constraints to graph->lp that force all validity dependences
2518 * to be respected and attempt to carry them.
2520 static int add_all_constraints(struct isl_sched_graph
*graph
)
2526 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2527 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2529 if (!edge
->validity
)
2532 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2533 isl_basic_map
*bmap
;
2536 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2537 map
= isl_map_from_basic_map(bmap
);
2539 if (edge
->src
== edge
->dst
&&
2540 add_intra_constraints(graph
, edge
, map
, pos
) < 0)
2542 if (edge
->src
!= edge
->dst
&&
2543 add_inter_constraints(graph
, edge
, map
, pos
) < 0)
2552 /* Count the number of equality and inequality constraints
2553 * that will be added to the carry_lp problem.
2554 * We count each edge exactly once.
2556 static int count_all_constraints(struct isl_sched_graph
*graph
,
2557 int *n_eq
, int *n_ineq
)
2561 *n_eq
= *n_ineq
= 0;
2562 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2563 struct isl_sched_edge
*edge
= &graph
->edge
[i
];
2564 for (j
= 0; j
< edge
->map
->n
; ++j
) {
2565 isl_basic_map
*bmap
;
2568 bmap
= isl_basic_map_copy(edge
->map
->p
[j
]);
2569 map
= isl_map_from_basic_map(bmap
);
2571 if (count_map_constraints(graph
, edge
, map
,
2572 n_eq
, n_ineq
, 1) < 0)
2580 /* Construct an LP problem for finding schedule coefficients
2581 * such that the schedule carries as many dependences as possible.
2582 * In particular, for each dependence i, we bound the dependence distance
2583 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2584 * of all e_i's. Dependence with e_i = 0 in the solution are simply
2585 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2586 * Note that if the dependence relation is a union of basic maps,
2587 * then we have to consider each basic map individually as it may only
2588 * be possible to carry the dependences expressed by some of those
2589 * basic maps and not all off them.
2590 * Below, we consider each of those basic maps as a separate "edge".
2592 * All variables of the LP are non-negative. The actual coefficients
2593 * may be negative, so each coefficient is represented as the difference
2594 * of two non-negative variables. The negative part always appears
2595 * immediately before the positive part.
2596 * Other than that, the variables have the following order
2598 * - sum of (1 - e_i) over all edges
2599 * - sum of positive and negative parts of all c_n coefficients
2600 * (unconstrained when computing non-parametric schedules)
2601 * - sum of positive and negative parts of all c_x coefficients
2606 * - positive and negative parts of c_i_n (if parametric)
2607 * - positive and negative parts of c_i_x
2609 * The constraints are those from the (validity) edges plus three equalities
2610 * to express the sums and n_edge inequalities to express e_i <= 1.
2612 static int setup_carry_lp(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2622 for (i
= 0; i
< graph
->n_edge
; ++i
)
2623 n_edge
+= graph
->edge
[i
].map
->n
;
2626 for (i
= 0; i
< graph
->n
; ++i
) {
2627 struct isl_sched_node
*node
= &graph
->node
[graph
->sorted
[i
]];
2628 node
->start
= total
;
2629 total
+= 1 + 2 * (node
->nparam
+ node
->nvar
);
2632 if (count_all_constraints(graph
, &n_eq
, &n_ineq
) < 0)
2634 if (count_bound_coefficient_constraints(ctx
, graph
, &n_eq
, &n_ineq
) < 0)
2637 dim
= isl_space_set_alloc(ctx
, 0, total
);
2638 isl_basic_set_free(graph
->lp
);
2641 graph
->lp
= isl_basic_set_alloc_space(dim
, 0, n_eq
, n_ineq
);
2642 graph
->lp
= isl_basic_set_set_rational(graph
->lp
);
2644 k
= isl_basic_set_alloc_equality(graph
->lp
);
2647 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2648 isl_int_set_si(graph
->lp
->eq
[k
][0], -n_edge
);
2649 isl_int_set_si(graph
->lp
->eq
[k
][1], 1);
2650 for (i
= 0; i
< n_edge
; ++i
)
2651 isl_int_set_si(graph
->lp
->eq
[k
][4 + i
], 1);
2653 k
= isl_basic_set_alloc_equality(graph
->lp
);
2656 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2657 isl_int_set_si(graph
->lp
->eq
[k
][2], -1);
2658 for (i
= 0; i
< graph
->n
; ++i
) {
2659 int pos
= 1 + graph
->node
[i
].start
+ 1;
2661 for (j
= 0; j
< 2 * graph
->node
[i
].nparam
; ++j
)
2662 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2665 k
= isl_basic_set_alloc_equality(graph
->lp
);
2668 isl_seq_clr(graph
->lp
->eq
[k
], 1 + total
);
2669 isl_int_set_si(graph
->lp
->eq
[k
][3], -1);
2670 for (i
= 0; i
< graph
->n
; ++i
) {
2671 struct isl_sched_node
*node
= &graph
->node
[i
];
2672 int pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2674 for (j
= 0; j
< 2 * node
->nvar
; ++j
)
2675 isl_int_set_si(graph
->lp
->eq
[k
][pos
+ j
], 1);
2678 for (i
= 0; i
< n_edge
; ++i
) {
2679 k
= isl_basic_set_alloc_inequality(graph
->lp
);
2682 isl_seq_clr(graph
->lp
->ineq
[k
], 1 + total
);
2683 isl_int_set_si(graph
->lp
->ineq
[k
][4 + i
], -1);
2684 isl_int_set_si(graph
->lp
->ineq
[k
][0], 1);
2687 if (add_bound_coefficient_constraints(ctx
, graph
) < 0)
2689 if (add_all_constraints(graph
) < 0)
2695 /* If the schedule_split_scaled option is set and if the linear
2696 * parts of the scheduling rows for all nodes in the graphs have
2697 * non-trivial common divisor, then split off the constant term
2698 * from the linear part.
2699 * The constant term is then placed in a separate band and
2700 * the linear part is reduced.
2702 static int split_scaled(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2708 if (!ctx
->opt
->schedule_split_scaled
)
2713 if (graph
->n_total_row
>= graph
->max_row
)
2714 isl_die(ctx
, isl_error_internal
,
2715 "too many schedule rows", return -1);
2718 isl_int_init(gcd_i
);
2720 isl_int_set_si(gcd
, 0);
2722 row
= isl_mat_rows(graph
->node
[0].sched
) - 1;
2724 for (i
= 0; i
< graph
->n
; ++i
) {
2725 struct isl_sched_node
*node
= &graph
->node
[i
];
2726 int cols
= isl_mat_cols(node
->sched
);
2728 isl_seq_gcd(node
->sched
->row
[row
] + 1, cols
- 1, &gcd_i
);
2729 isl_int_gcd(gcd
, gcd
, gcd_i
);
2732 isl_int_clear(gcd_i
);
2734 if (isl_int_cmp_si(gcd
, 1) <= 0) {
2741 for (i
= 0; i
< graph
->n
; ++i
) {
2742 struct isl_sched_node
*node
= &graph
->node
[i
];
2744 isl_map_free(node
->sched_map
);
2745 node
->sched_map
= NULL
;
2746 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
2749 isl_int_fdiv_r(node
->sched
->row
[row
+ 1][0],
2750 node
->sched
->row
[row
][0], gcd
);
2751 isl_int_fdiv_q(node
->sched
->row
[row
][0],
2752 node
->sched
->row
[row
][0], gcd
);
2753 isl_int_mul(node
->sched
->row
[row
][0],
2754 node
->sched
->row
[row
][0], gcd
);
2755 node
->sched
= isl_mat_scale_down_row(node
->sched
, row
, gcd
);
2758 node
->band
[graph
->n_total_row
] = graph
->n_band
;
2761 graph
->n_total_row
++;
2770 static int compute_component_schedule(isl_ctx
*ctx
,
2771 struct isl_sched_graph
*graph
);
2773 /* Is the schedule row "sol" trivial on node "node"?
2774 * That is, is the solution zero on the dimensions orthogonal to
2775 * the previously found solutions?
2776 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
2778 * Each coefficient is represented as the difference between
2779 * two non-negative values in "sol". "sol" has been computed
2780 * in terms of the original iterators (i.e., without use of cmap).
2781 * We construct the schedule row s and write it as a linear
2782 * combination of (linear combinations of) previously computed schedule rows.
2783 * s = Q c or c = U s.
2784 * If the final entries of c are all zero, then the solution is trivial.
2786 static int is_trivial(struct isl_sched_node
*node
, __isl_keep isl_vec
*sol
)
2796 if (node
->nvar
== node
->rank
)
2799 ctx
= isl_vec_get_ctx(sol
);
2800 node_sol
= isl_vec_alloc(ctx
, node
->nvar
);
2804 pos
= 1 + node
->start
+ 1 + 2 * node
->nparam
;
2806 for (i
= 0; i
< node
->nvar
; ++i
)
2807 isl_int_sub(node_sol
->el
[i
],
2808 sol
->el
[pos
+ 2 * i
+ 1], sol
->el
[pos
+ 2 * i
]);
2810 node_sol
= isl_mat_vec_product(isl_mat_copy(node
->cinv
), node_sol
);
2815 trivial
= isl_seq_first_non_zero(node_sol
->el
+ node
->rank
,
2816 node
->nvar
- node
->rank
) == -1;
2818 isl_vec_free(node_sol
);
2823 /* Is the schedule row "sol" trivial on any node where it should
2825 * "sol" has been computed in terms of the original iterators
2826 * (i.e., without use of cmap).
2827 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
2829 static int is_any_trivial(struct isl_sched_graph
*graph
,
2830 __isl_keep isl_vec
*sol
)
2834 for (i
= 0; i
< graph
->n
; ++i
) {
2835 struct isl_sched_node
*node
= &graph
->node
[i
];
2838 if (!needs_row(graph
, node
))
2840 trivial
= is_trivial(node
, sol
);
2841 if (trivial
< 0 || trivial
)
2848 /* Construct a schedule row for each node such that as many dependences
2849 * as possible are carried and then continue with the next band.
2851 * If the computed schedule row turns out to be trivial on one or
2852 * more nodes where it should not be trivial, then we throw it away
2853 * and try again on each component separately.
2855 static int carry_dependences(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2864 for (i
= 0; i
< graph
->n_edge
; ++i
)
2865 n_edge
+= graph
->edge
[i
].map
->n
;
2867 if (setup_carry_lp(ctx
, graph
) < 0)
2870 lp
= isl_basic_set_copy(graph
->lp
);
2871 sol
= isl_tab_basic_set_non_neg_lexmin(lp
);
2875 if (sol
->size
== 0) {
2877 isl_die(ctx
, isl_error_internal
,
2878 "error in schedule construction", return -1);
2881 isl_int_divexact(sol
->el
[1], sol
->el
[1], sol
->el
[0]);
2882 if (isl_int_cmp_si(sol
->el
[1], n_edge
) >= 0) {
2884 isl_die(ctx
, isl_error_unknown
,
2885 "unable to carry dependences", return -1);
2888 trivial
= is_any_trivial(graph
, sol
);
2890 sol
= isl_vec_free(sol
);
2891 } else if (trivial
) {
2894 return compute_component_schedule(ctx
, graph
);
2895 isl_die(ctx
, isl_error_unknown
,
2896 "unable to construct non-trivial solution", return -1);
2899 if (update_schedule(graph
, sol
, 0, 0) < 0)
2902 if (split_scaled(ctx
, graph
) < 0)
2905 return compute_next_band(ctx
, graph
);
2908 /* Are there any (non-empty) validity edges in the graph?
2910 static int has_validity_edges(struct isl_sched_graph
*graph
)
2914 for (i
= 0; i
< graph
->n_edge
; ++i
) {
2917 empty
= isl_map_plain_is_empty(graph
->edge
[i
].map
);
2922 if (graph
->edge
[i
].validity
)
2929 /* Should we apply a Feautrier step?
2930 * That is, did the user request the Feautrier algorithm and are
2931 * there any validity dependences (left)?
2933 static int need_feautrier_step(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2935 if (ctx
->opt
->schedule_algorithm
!= ISL_SCHEDULE_ALGORITHM_FEAUTRIER
)
2938 return has_validity_edges(graph
);
2941 /* Compute a schedule for a connected dependence graph using Feautrier's
2942 * multi-dimensional scheduling algorithm.
2943 * The original algorithm is described in [1].
2944 * The main idea is to minimize the number of scheduling dimensions, by
2945 * trying to satisfy as many dependences as possible per scheduling dimension.
2947 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2948 * Problem, Part II: Multi-Dimensional Time.
2949 * In Intl. Journal of Parallel Programming, 1992.
2951 static int compute_schedule_wcc_feautrier(isl_ctx
*ctx
,
2952 struct isl_sched_graph
*graph
)
2954 return carry_dependences(ctx
, graph
);
2957 /* Compute a schedule for a connected dependence graph.
2958 * We try to find a sequence of as many schedule rows as possible that result
2959 * in non-negative dependence distances (independent of the previous rows
2960 * in the sequence, i.e., such that the sequence is tilable).
2961 * If we can't find any more rows we either
2962 * - split between SCCs and start over (assuming we found an interesting
2963 * pair of SCCs between which to split)
2964 * - continue with the next band (assuming the current band has at least
2966 * - try to carry as many dependences as possible and continue with the next
2969 * If Feautrier's algorithm is selected, we first recursively try to satisfy
2970 * as many validity dependences as possible. When all validity dependences
2971 * are satisfied we extend the schedule to a full-dimensional schedule.
2973 * If we manage to complete the schedule, we finish off by topologically
2974 * sorting the statements based on the remaining dependences.
2976 * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2977 * outermost dimension in the current band to be zero distance. If this
2978 * turns out to be impossible, we fall back on the general scheme above
2979 * and try to carry as many dependences as possible.
2981 static int compute_schedule_wcc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
2985 if (detect_sccs(ctx
, graph
) < 0)
2987 if (sort_sccs(graph
) < 0)
2990 if (compute_maxvar(graph
) < 0)
2993 if (need_feautrier_step(ctx
, graph
))
2994 return compute_schedule_wcc_feautrier(ctx
, graph
);
2996 if (ctx
->opt
->schedule_outer_zero_distance
)
2999 while (graph
->n_row
< graph
->maxvar
) {
3002 graph
->src_scc
= -1;
3003 graph
->dst_scc
= -1;
3005 if (setup_lp(ctx
, graph
, force_zero
) < 0)
3007 sol
= solve_lp(graph
);
3010 if (sol
->size
== 0) {
3012 if (!ctx
->opt
->schedule_maximize_band_depth
&&
3013 graph
->n_total_row
> graph
->band_start
)
3014 return compute_next_band(ctx
, graph
);
3015 if (graph
->src_scc
>= 0)
3016 return compute_split_schedule(ctx
, graph
);
3017 if (graph
->n_total_row
> graph
->band_start
)
3018 return compute_next_band(ctx
, graph
);
3019 return carry_dependences(ctx
, graph
);
3021 if (update_schedule(graph
, sol
, 1, 1) < 0)
3026 if (graph
->n_total_row
> graph
->band_start
)
3028 return sort_statements(ctx
, graph
);
3031 /* Add a row to the schedules that separates the SCCs and move
3034 static int split_on_scc(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3038 if (graph
->n_total_row
>= graph
->max_row
)
3039 isl_die(ctx
, isl_error_internal
,
3040 "too many schedule rows", return -1);
3042 for (i
= 0; i
< graph
->n
; ++i
) {
3043 struct isl_sched_node
*node
= &graph
->node
[i
];
3044 int row
= isl_mat_rows(node
->sched
);
3046 isl_map_free(node
->sched_map
);
3047 node
->sched_map
= NULL
;
3048 node
->sched
= isl_mat_add_zero_rows(node
->sched
, 1);
3049 node
->sched
= isl_mat_set_element_si(node
->sched
, row
, 0,
3053 node
->band
[graph
->n_total_row
] = graph
->n_band
;
3056 graph
->n_total_row
++;
3062 /* Compute a schedule for each component (identified by node->scc)
3063 * of the dependence graph separately and then combine the results.
3064 * Depending on the setting of schedule_fuse, a component may be
3065 * either weakly or strongly connected.
3067 * The band_id is adjusted such that each component has a separate id.
3068 * Note that the band_id may have already been set to a value different
3069 * from zero by compute_split_schedule.
3071 static int compute_component_schedule(isl_ctx
*ctx
,
3072 struct isl_sched_graph
*graph
)
3076 int n_total_row
, orig_total_row
;
3077 int n_band
, orig_band
;
3079 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
||
3080 ctx
->opt
->schedule_separate_components
)
3081 if (split_on_scc(ctx
, graph
) < 0)
3085 orig_total_row
= graph
->n_total_row
;
3087 orig_band
= graph
->n_band
;
3088 for (i
= 0; i
< graph
->n
; ++i
)
3089 graph
->node
[i
].band_id
[graph
->n_band
] += graph
->node
[i
].scc
;
3090 for (wcc
= 0; wcc
< graph
->scc
; ++wcc
) {
3092 for (i
= 0; i
< graph
->n
; ++i
)
3093 if (graph
->node
[i
].scc
== wcc
)
3096 for (i
= 0; i
< graph
->n_edge
; ++i
)
3097 if (graph
->edge
[i
].src
->scc
== wcc
&&
3098 graph
->edge
[i
].dst
->scc
== wcc
)
3101 if (compute_sub_schedule(ctx
, graph
, n
, n_edge
,
3103 &edge_scc_exactly
, wcc
, 1) < 0)
3105 if (graph
->n_total_row
> n_total_row
)
3106 n_total_row
= graph
->n_total_row
;
3107 graph
->n_total_row
= orig_total_row
;
3108 if (graph
->n_band
> n_band
)
3109 n_band
= graph
->n_band
;
3110 graph
->n_band
= orig_band
;
3113 graph
->n_total_row
= n_total_row
;
3114 graph
->n_band
= n_band
;
3116 return pad_schedule(graph
);
3119 /* Compute a schedule for the given dependence graph.
3120 * We first check if the graph is connected (through validity dependences)
3121 * and, if not, compute a schedule for each component separately.
3122 * If schedule_fuse is set to minimal fusion, then we check for strongly
3123 * connected components instead and compute a separate schedule for
3124 * each such strongly connected component.
3126 static int compute_schedule(isl_ctx
*ctx
, struct isl_sched_graph
*graph
)
3128 if (ctx
->opt
->schedule_fuse
== ISL_SCHEDULE_FUSE_MIN
) {
3129 if (detect_sccs(ctx
, graph
) < 0)
3132 if (detect_wccs(ctx
, graph
) < 0)
3137 return compute_component_schedule(ctx
, graph
);
3139 return compute_schedule_wcc(ctx
, graph
);
3142 /* Compute a schedule on sc->domain that respects the given schedule
3145 * In particular, the schedule respects all the validity dependences.
3146 * If the default isl scheduling algorithm is used, it tries to minimize
3147 * the dependence distances over the proximity dependences.
3148 * If Feautrier's scheduling algorithm is used, the proximity dependence
3149 * distances are only minimized during the extension to a full-dimensional
3152 __isl_give isl_schedule
*isl_schedule_constraints_compute_schedule(
3153 __isl_take isl_schedule_constraints
*sc
)
3155 isl_ctx
*ctx
= isl_schedule_constraints_get_ctx(sc
);
3156 struct isl_sched_graph graph
= { 0 };
3157 isl_schedule
*sched
;
3158 struct isl_extract_edge_data data
;
3159 enum isl_edge_type i
;
3161 sc
= isl_schedule_constraints_align_params(sc
);
3165 graph
.n
= isl_union_set_n_set(sc
->domain
);
3168 if (graph_alloc(ctx
, &graph
, graph
.n
,
3169 isl_schedule_constraints_n_map(sc
)) < 0)
3171 if (compute_max_row(&graph
, sc
->domain
) < 0)
3175 if (isl_union_set_foreach_set(sc
->domain
, &extract_node
, &graph
) < 0)
3177 if (graph_init_table(ctx
, &graph
) < 0)
3179 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
3180 graph
.max_edge
[i
] = isl_union_map_n_map(sc
->constraint
[i
]);
3181 if (graph_init_edge_tables(ctx
, &graph
) < 0)
3184 data
.graph
= &graph
;
3185 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
3187 if (isl_union_map_foreach_map(sc
->constraint
[i
],
3188 &extract_edge
, &data
) < 0)
3192 if (compute_schedule(ctx
, &graph
) < 0)
3196 sched
= extract_schedule(&graph
, isl_union_set_get_space(sc
->domain
));
3198 graph_free(ctx
, &graph
);
3199 isl_schedule_constraints_free(sc
);
3203 graph_free(ctx
, &graph
);
3204 isl_schedule_constraints_free(sc
);
3208 /* Compute a schedule for the given union of domains that respects
3209 * all the validity dependences and minimizes
3210 * the dependence distances over the proximity dependences.
3212 * This function is kept for backward compatibility.
3214 __isl_give isl_schedule
*isl_union_set_compute_schedule(
3215 __isl_take isl_union_set
*domain
,
3216 __isl_take isl_union_map
*validity
,
3217 __isl_take isl_union_map
*proximity
)
3219 isl_schedule_constraints
*sc
;
3221 sc
= isl_schedule_constraints_on_domain(domain
);
3222 sc
= isl_schedule_constraints_set_validity(sc
, validity
);
3223 sc
= isl_schedule_constraints_set_proximity(sc
, proximity
);
3225 return isl_schedule_constraints_compute_schedule(sc
);
3228 void *isl_schedule_free(__isl_take isl_schedule
*sched
)
3234 if (--sched
->ref
> 0)
3237 for (i
= 0; i
< sched
->n
; ++i
) {
3238 isl_multi_aff_free(sched
->node
[i
].sched
);
3239 free(sched
->node
[i
].band_end
);
3240 free(sched
->node
[i
].band_id
);
3241 free(sched
->node
[i
].zero
);
3243 isl_space_free(sched
->dim
);
3244 isl_band_list_free(sched
->band_forest
);
3249 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
3251 return schedule
? isl_space_get_ctx(schedule
->dim
) : NULL
;
3254 /* Set max_out to the maximal number of output dimensions over
3257 static int update_max_out(__isl_take isl_map
*map
, void *user
)
3259 int *max_out
= user
;
3260 int n_out
= isl_map_dim(map
, isl_dim_out
);
3262 if (n_out
> *max_out
)
3269 /* Internal data structure for map_pad_range.
3271 * "max_out" is the maximal schedule dimension.
3272 * "res" collects the results.
3274 struct isl_pad_schedule_map_data
{
3279 /* Pad the range of the given map with zeros to data->max_out and
3280 * then add the result to data->res.
3282 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
3284 struct isl_pad_schedule_map_data
*data
= user
;
3286 int n_out
= isl_map_dim(map
, isl_dim_out
);
3288 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
3289 for (i
= n_out
; i
< data
->max_out
; ++i
)
3290 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
3292 data
->res
= isl_union_map_add_map(data
->res
, map
);
3299 /* Pad the ranges of the maps in the union map with zeros such they all have
3300 * the same dimension.
3302 static __isl_give isl_union_map
*pad_schedule_map(
3303 __isl_take isl_union_map
*umap
)
3305 struct isl_pad_schedule_map_data data
;
3309 if (isl_union_map_n_map(umap
) <= 1)
3313 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
3314 return isl_union_map_free(umap
);
3316 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3317 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
3318 data
.res
= isl_union_map_free(data
.res
);
3320 isl_union_map_free(umap
);
3324 /* Return an isl_union_map of the schedule. If we have already constructed
3325 * a band forest, then this band forest may have been modified so we need
3326 * to extract the isl_union_map from the forest rather than from
3327 * the originally computed schedule. This reconstructed schedule map
3328 * then needs to be padded with zeros to unify the schedule space
3329 * since the result of isl_band_list_get_suffix_schedule may not have
3330 * a unified schedule space.
3332 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
3335 isl_union_map
*umap
;
3340 if (sched
->band_forest
) {
3341 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
3342 return pad_schedule_map(umap
);
3345 umap
= isl_union_map_empty(isl_space_copy(sched
->dim
));
3346 for (i
= 0; i
< sched
->n
; ++i
) {
3349 ma
= isl_multi_aff_copy(sched
->node
[i
].sched
);
3350 umap
= isl_union_map_add_map(umap
, isl_map_from_multi_aff(ma
));
3356 static __isl_give isl_band_list
*construct_band_list(
3357 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3358 int band_nr
, int *parent_active
, int n_active
);
3360 /* Construct an isl_band structure for the band in the given schedule
3361 * with sequence number band_nr for the n_active nodes marked by active.
3362 * If the nodes don't have a band with the given sequence number,
3363 * then a band without members is created.
3365 * Because of the way the schedule is constructed, we know that
3366 * the position of the band inside the schedule of a node is the same
3367 * for all active nodes.
3369 * The partial schedule for the band is created before the children
3370 * are created to that construct_band_list can refer to the partial
3371 * schedule of the parent.
3373 static __isl_give isl_band
*construct_band(__isl_keep isl_schedule
*schedule
,
3374 __isl_keep isl_band
*parent
,
3375 int band_nr
, int *active
, int n_active
)
3378 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3380 unsigned start
, end
;
3382 band
= isl_band_alloc(ctx
);
3386 band
->schedule
= schedule
;
3387 band
->parent
= parent
;
3389 for (i
= 0; i
< schedule
->n
; ++i
)
3393 if (i
>= schedule
->n
)
3394 isl_die(ctx
, isl_error_internal
,
3395 "band without active statements", goto error
);
3397 start
= band_nr
? schedule
->node
[i
].band_end
[band_nr
- 1] : 0;
3398 end
= band_nr
< schedule
->node
[i
].n_band
?
3399 schedule
->node
[i
].band_end
[band_nr
] : start
;
3400 band
->n
= end
- start
;
3402 band
->zero
= isl_alloc_array(ctx
, int, band
->n
);
3403 if (band
->n
&& !band
->zero
)
3406 for (j
= 0; j
< band
->n
; ++j
)
3407 band
->zero
[j
] = schedule
->node
[i
].zero
[start
+ j
];
3409 band
->pma
= isl_union_pw_multi_aff_empty(isl_space_copy(schedule
->dim
));
3410 for (i
= 0; i
< schedule
->n
; ++i
) {
3412 isl_pw_multi_aff
*pma
;
3418 ma
= isl_multi_aff_copy(schedule
->node
[i
].sched
);
3419 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3420 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, end
, n_out
- end
);
3421 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, start
);
3422 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3423 band
->pma
= isl_union_pw_multi_aff_add_pw_multi_aff(band
->pma
,
3429 for (i
= 0; i
< schedule
->n
; ++i
)
3430 if (active
[i
] && schedule
->node
[i
].n_band
> band_nr
+ 1)
3433 if (i
< schedule
->n
) {
3434 band
->children
= construct_band_list(schedule
, band
,
3435 band_nr
+ 1, active
, n_active
);
3436 if (!band
->children
)
3442 isl_band_free(band
);
3446 /* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
3448 * r is set to a negative value if anything goes wrong.
3450 * c1 stores the result of extract_int.
3451 * c2 is a temporary value used inside cmp_band_in_ancestor.
3452 * t is a temporary value used inside extract_int.
3454 * first and equal are used inside extract_int.
3455 * first is set if we are looking at the first isl_multi_aff inside
3456 * the isl_union_pw_multi_aff.
3457 * equal is set if all the isl_multi_affs have been equal so far.
3459 struct isl_cmp_band_data
{
3470 /* Check if "ma" assigns a constant value.
3471 * Note that this function is only called on isl_multi_affs
3472 * with a single output dimension.
3474 * If "ma" assigns a constant value then we compare it to data->c1
3475 * or assign it to data->c1 if this is the first isl_multi_aff we consider.
3476 * If "ma" does not assign a constant value or if it assigns a value
3477 * that is different from data->c1, then we set data->equal to zero
3478 * and terminate the check.
3480 static int multi_aff_extract_int(__isl_take isl_set
*set
,
3481 __isl_take isl_multi_aff
*ma
, void *user
)
3484 struct isl_cmp_band_data
*data
= user
;
3486 aff
= isl_multi_aff_get_aff(ma
, 0);
3487 data
->r
= isl_aff_is_cst(aff
);
3488 if (data
->r
>= 0 && data
->r
) {
3489 isl_aff_get_constant(aff
, &data
->t
);
3491 isl_int_set(data
->c1
, data
->t
);
3493 } else if (!isl_int_eq(data
->c1
, data
->t
))
3495 } else if (data
->r
>= 0 && !data
->r
)
3500 isl_multi_aff_free(ma
);
3509 /* This function is called for each isl_pw_multi_aff in
3510 * the isl_union_pw_multi_aff checked by extract_int.
3511 * Check all the isl_multi_affs inside "pma".
3513 static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff
*pma
,
3518 r
= isl_pw_multi_aff_foreach_piece(pma
, &multi_aff_extract_int
, user
);
3519 isl_pw_multi_aff_free(pma
);
3524 /* Check if "upma" assigns a single constant value to its domain.
3525 * If so, return 1 and store the result in data->c1.
3528 * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
3529 * means that either an error occurred or that we have broken off the check
3530 * because we already know the result is going to be negative.
3531 * In the latter case, data->equal is set to zero.
3533 static int extract_int(__isl_keep isl_union_pw_multi_aff
*upma
,
3534 struct isl_cmp_band_data
*data
)
3539 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
3540 &pw_multi_aff_extract_int
, data
) < 0) {
3546 return !data
->first
&& data
->equal
;
3549 /* Compare "b1" and "b2" based on the parent schedule of their ancestor
3552 * If the parent of "ancestor" also has a single member, then we
3553 * first try to compare the two band based on the partial schedule
3556 * Otherwise, or if the result is inconclusive, we look at the partial schedule
3557 * of "ancestor" itself.
3558 * In particular, we specialize the parent schedule based
3559 * on the domains of the child schedules, check if both assign
3560 * a single constant value and, if so, compare the two constant values.
3561 * If the specialized parent schedules do not assign a constant value,
3562 * then they cannot be used to order the two bands and so in this case
3565 static int cmp_band_in_ancestor(__isl_keep isl_band
*b1
,
3566 __isl_keep isl_band
*b2
, struct isl_cmp_band_data
*data
,
3567 __isl_keep isl_band
*ancestor
)
3569 isl_union_pw_multi_aff
*upma
;
3570 isl_union_set
*domain
;
3576 if (ancestor
->parent
&& ancestor
->parent
->n
== 1) {
3577 r
= cmp_band_in_ancestor(b1
, b2
, data
, ancestor
->parent
);
3584 upma
= isl_union_pw_multi_aff_copy(b1
->pma
);
3585 domain
= isl_union_pw_multi_aff_domain(upma
);
3586 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
3587 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
3588 r
= extract_int(upma
, data
);
3589 isl_union_pw_multi_aff_free(upma
);
3596 isl_int_set(data
->c2
, data
->c1
);
3598 upma
= isl_union_pw_multi_aff_copy(b2
->pma
);
3599 domain
= isl_union_pw_multi_aff_domain(upma
);
3600 upma
= isl_union_pw_multi_aff_copy(ancestor
->pma
);
3601 upma
= isl_union_pw_multi_aff_intersect_domain(upma
, domain
);
3602 r
= extract_int(upma
, data
);
3603 isl_union_pw_multi_aff_free(upma
);
3610 return isl_int_cmp(data
->c2
, data
->c1
);
3613 /* Compare "a" and "b" based on the parent schedule of their parent.
3615 static int cmp_band(const void *a
, const void *b
, void *user
)
3617 isl_band
*b1
= *(isl_band
* const *) a
;
3618 isl_band
*b2
= *(isl_band
* const *) b
;
3619 struct isl_cmp_band_data
*data
= user
;
3621 return cmp_band_in_ancestor(b1
, b2
, data
, b1
->parent
);
3624 /* Sort the elements in "list" based on the partial schedules of its parent
3625 * (and ancestors). In particular if the parent assigns constant values
3626 * to the domains of the bands in "list", then the elements are sorted
3627 * according to that order.
3628 * This order should be a more "natural" order for the user, but otherwise
3629 * shouldn't have any effect.
3630 * If we would be constructing an isl_band forest directly in
3631 * isl_schedule_constraints_compute_schedule then there wouldn't be any need
3632 * for a reordering, since the children would be added to the list
3633 * in their natural order automatically.
3635 * If there is only one element in the list, then there is no need to sort
3637 * If the partial schedule of the parent has more than one member
3638 * (or if there is no parent), then it's
3639 * defnitely not assigning constant values to the different children in
3640 * the list and so we wouldn't be able to use it to sort the list.
3642 static __isl_give isl_band_list
*sort_band_list(__isl_take isl_band_list
*list
,
3643 __isl_keep isl_band
*parent
)
3645 struct isl_cmp_band_data data
;
3651 if (!parent
|| parent
->n
!= 1)
3655 isl_int_init(data
.c1
);
3656 isl_int_init(data
.c2
);
3657 isl_int_init(data
.t
);
3658 isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]), &cmp_band
, &data
);
3660 list
= isl_band_list_free(list
);
3661 isl_int_clear(data
.c1
);
3662 isl_int_clear(data
.c2
);
3663 isl_int_clear(data
.t
);
3668 /* Construct a list of bands that start at the same position (with
3669 * sequence number band_nr) in the schedules of the nodes that
3670 * were active in the parent band.
3672 * A separate isl_band structure is created for each band_id
3673 * and for each node that does not have a band with sequence
3674 * number band_nr. In the latter case, a band without members
3676 * This ensures that if a band has any children, then each node
3677 * that was active in the band is active in exactly one of the children.
3679 static __isl_give isl_band_list
*construct_band_list(
3680 __isl_keep isl_schedule
*schedule
, __isl_keep isl_band
*parent
,
3681 int band_nr
, int *parent_active
, int n_active
)
3684 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3687 isl_band_list
*list
;
3690 for (i
= 0; i
< n_active
; ++i
) {
3691 for (j
= 0; j
< schedule
->n
; ++j
) {
3692 if (!parent_active
[j
])
3694 if (schedule
->node
[j
].n_band
<= band_nr
)
3696 if (schedule
->node
[j
].band_id
[band_nr
] == i
) {
3702 for (j
= 0; j
< schedule
->n
; ++j
)
3703 if (schedule
->node
[j
].n_band
<= band_nr
)
3708 list
= isl_band_list_alloc(ctx
, n_band
);
3709 band
= construct_band(schedule
, parent
, band_nr
,
3710 parent_active
, n_active
);
3711 return isl_band_list_add(list
, band
);
3714 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3715 if (schedule
->n
&& !active
)
3718 list
= isl_band_list_alloc(ctx
, n_band
);
3720 for (i
= 0; i
< n_active
; ++i
) {
3724 for (j
= 0; j
< schedule
->n
; ++j
) {
3725 active
[j
] = parent_active
[j
] &&
3726 schedule
->node
[j
].n_band
> band_nr
&&
3727 schedule
->node
[j
].band_id
[band_nr
] == i
;
3734 band
= construct_band(schedule
, parent
, band_nr
, active
, n
);
3736 list
= isl_band_list_add(list
, band
);
3738 for (i
= 0; i
< schedule
->n
; ++i
) {
3740 if (!parent_active
[i
])
3742 if (schedule
->node
[i
].n_band
> band_nr
)
3744 for (j
= 0; j
< schedule
->n
; ++j
)
3746 band
= construct_band(schedule
, parent
, band_nr
, active
, 1);
3747 list
= isl_band_list_add(list
, band
);
3752 list
= sort_band_list(list
, parent
);
3757 /* Construct a band forest representation of the schedule and
3758 * return the list of roots.
3760 static __isl_give isl_band_list
*construct_forest(
3761 __isl_keep isl_schedule
*schedule
)
3764 isl_ctx
*ctx
= isl_schedule_get_ctx(schedule
);
3765 isl_band_list
*forest
;
3768 active
= isl_alloc_array(ctx
, int, schedule
->n
);
3769 if (schedule
->n
&& !active
)
3772 for (i
= 0; i
< schedule
->n
; ++i
)
3775 forest
= construct_band_list(schedule
, NULL
, 0, active
, schedule
->n
);
3782 /* Return the roots of a band forest representation of the schedule.
3784 __isl_give isl_band_list
*isl_schedule_get_band_forest(
3785 __isl_keep isl_schedule
*schedule
)
3789 if (!schedule
->band_forest
)
3790 schedule
->band_forest
= construct_forest(schedule
);
3791 return isl_band_list_dup(schedule
->band_forest
);
3794 /* Call "fn" on each band in the schedule in depth-first post-order.
3796 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
3797 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
3800 isl_band_list
*forest
;
3805 forest
= isl_schedule_get_band_forest(sched
);
3806 r
= isl_band_list_foreach_band(forest
, fn
, user
);
3807 isl_band_list_free(forest
);
3812 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3813 __isl_keep isl_band_list
*list
);
3815 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
3816 __isl_keep isl_band
*band
)
3818 isl_band_list
*children
;
3820 p
= isl_printer_start_line(p
);
3821 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
3822 p
= isl_printer_end_line(p
);
3824 if (!isl_band_has_children(band
))
3827 children
= isl_band_get_children(band
);
3829 p
= isl_printer_indent(p
, 4);
3830 p
= print_band_list(p
, children
);
3831 p
= isl_printer_indent(p
, -4);
3833 isl_band_list_free(children
);
3838 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
3839 __isl_keep isl_band_list
*list
)
3843 n
= isl_band_list_n_band(list
);
3844 for (i
= 0; i
< n
; ++i
) {
3846 band
= isl_band_list_get_band(list
, i
);
3847 p
= print_band(p
, band
);
3848 isl_band_free(band
);
3854 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
3855 __isl_keep isl_schedule
*schedule
)
3857 isl_band_list
*forest
;
3859 forest
= isl_schedule_get_band_forest(schedule
);
3861 p
= print_band_list(p
, forest
);
3863 isl_band_list_free(forest
);
3868 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
3870 isl_printer
*printer
;
3875 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
3876 printer
= isl_printer_print_schedule(printer
, schedule
);
3878 isl_printer_free(printer
);