isl_coalesce.c: extract out shared find_eq and find_ineq
[isl.git] / isl_scheduler.c
blobc395a5ca18b2d72b2350558ea7b7cc4982978250
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015-2016 Sven Verdoolaege
5 * Copyright 2016 INRIA Paris
6 * Copyright 2017 Sven Verdoolaege
8 * Use of this software is governed by the MIT license
10 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
11 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 * 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
15 * CS 42112, 75589 Paris Cedex 12, France
18 #include <isl_ctx_private.h>
19 #include <isl_map_private.h>
20 #include <isl_space_private.h>
21 #include <isl_aff_private.h>
22 #include <isl/hash.h>
23 #include <isl/constraint.h>
24 #include <isl/schedule.h>
25 #include <isl_schedule_constraints.h>
26 #include <isl/schedule_node.h>
27 #include <isl_mat_private.h>
28 #include <isl_vec_private.h>
29 #include <isl/set.h>
30 #include <isl_union_set_private.h>
31 #include <isl_seq.h>
32 #include <isl_tab.h>
33 #include <isl_dim_map.h>
34 #include <isl/map_to_basic_set.h>
35 #include <isl_sort.h>
36 #include <isl_options_private.h>
37 #include <isl_tarjan.h>
38 #include <isl_morph.h>
39 #include <isl/ilp.h>
40 #include <isl_val_private.h>
43 * The scheduling algorithm implemented in this file was inspired by
44 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
45 * Parallelization and Locality Optimization in the Polyhedral Model".
49 /* Internal information about a node that is used during the construction
50 * of a schedule.
51 * space represents the original space in which the domain lives;
52 * that is, the space is not affected by compression
53 * sched is a matrix representation of the schedule being constructed
54 * for this node; if compressed is set, then this schedule is
55 * defined over the compressed domain space
56 * sched_map is an isl_map representation of the same (partial) schedule
57 * sched_map may be NULL; if compressed is set, then this map
58 * is defined over the uncompressed domain space
59 * rank is the number of linearly independent rows in the linear part
60 * of sched
61 * the rows of "vmap" represent a change of basis for the node
62 * variables; the first rank rows span the linear part of
63 * the schedule rows; the remaining rows are linearly independent
64 * the rows of "indep" represent linear combinations of the schedule
65 * coefficients that are non-zero when the schedule coefficients are
66 * linearly independent of previously computed schedule rows.
67 * start is the first variable in the LP problem in the sequences that
68 * represents the schedule coefficients of this node
69 * nvar is the dimension of the domain
70 * nparam is the number of parameters or 0 if we are not constructing
71 * a parametric schedule
73 * If compressed is set, then hull represents the constraints
74 * that were used to derive the compression, while compress and
75 * decompress map the original space to the compressed space and
76 * vice versa.
78 * scc is the index of SCC (or WCC) this node belongs to
80 * "cluster" is only used inside extract_clusters and identifies
81 * the cluster of SCCs that the node belongs to.
83 * coincident contains a boolean for each of the rows of the schedule,
84 * indicating whether the corresponding scheduling dimension satisfies
85 * the coincidence constraints in the sense that the corresponding
86 * dependence distances are zero.
88 * If the schedule_treat_coalescing option is set, then
89 * "sizes" contains the sizes of the (compressed) instance set
90 * in each direction. If there is no fixed size in a given direction,
91 * then the corresponding size value is set to infinity.
92 * If the schedule_treat_coalescing option or the schedule_max_coefficient
93 * option is set, then "max" contains the maximal values for
94 * schedule coefficients of the (compressed) variables. If no bound
95 * needs to be imposed on a particular variable, then the corresponding
96 * value is negative.
97 * If not NULL, then "bounds" contains a non-parametric set
98 * in the compressed space that is bounded by the size in each direction.
100 struct isl_sched_node {
101 isl_space *space;
102 int compressed;
103 isl_set *hull;
104 isl_multi_aff *compress;
105 isl_multi_aff *decompress;
106 isl_mat *sched;
107 isl_map *sched_map;
108 int rank;
109 isl_mat *indep;
110 isl_mat *vmap;
111 int start;
112 int nvar;
113 int nparam;
115 int scc;
116 int cluster;
118 int *coincident;
120 isl_multi_val *sizes;
121 isl_basic_set *bounds;
122 isl_vec *max;
125 static int node_has_tuples(const void *entry, const void *val)
127 struct isl_sched_node *node = (struct isl_sched_node *)entry;
128 isl_space *space = (isl_space *) val;
130 return isl_space_has_equal_tuples(node->space, space);
133 static int node_scc_exactly(struct isl_sched_node *node, int scc)
135 return node->scc == scc;
138 static int node_scc_at_most(struct isl_sched_node *node, int scc)
140 return node->scc <= scc;
143 static int node_scc_at_least(struct isl_sched_node *node, int scc)
145 return node->scc >= scc;
148 /* An edge in the dependence graph. An edge may be used to
149 * ensure validity of the generated schedule, to minimize the dependence
150 * distance or both
152 * map is the dependence relation, with i -> j in the map if j depends on i
153 * tagged_condition and tagged_validity contain the union of all tagged
154 * condition or conditional validity dependence relations that
155 * specialize the dependence relation "map"; that is,
156 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
157 * or "tagged_validity", then i -> j is an element of "map".
158 * If these fields are NULL, then they represent the empty relation.
159 * src is the source node
160 * dst is the sink node
162 * types is a bit vector containing the types of this edge.
163 * validity is set if the edge is used to ensure correctness
164 * coincidence is used to enforce zero dependence distances
165 * proximity is set if the edge is used to minimize dependence distances
166 * condition is set if the edge represents a condition
167 * for a conditional validity schedule constraint
168 * local can only be set for condition edges and indicates that
169 * the dependence distance over the edge should be zero
170 * conditional_validity is set if the edge is used to conditionally
171 * ensure correctness
173 * For validity edges, start and end mark the sequence of inequality
174 * constraints in the LP problem that encode the validity constraint
175 * corresponding to this edge.
177 * During clustering, an edge may be marked "no_merge" if it should
178 * not be used to merge clusters.
179 * The weight is also only used during clustering and it is
180 * an indication of how many schedule dimensions on either side
181 * of the schedule constraints can be aligned.
182 * If the weight is negative, then this means that this edge was postponed
183 * by has_bounded_distances or any_no_merge. The original weight can
184 * be retrieved by adding 1 + graph->max_weight, with "graph"
185 * the graph containing this edge.
187 struct isl_sched_edge {
188 isl_map *map;
189 isl_union_map *tagged_condition;
190 isl_union_map *tagged_validity;
192 struct isl_sched_node *src;
193 struct isl_sched_node *dst;
195 unsigned types;
197 int start;
198 int end;
200 int no_merge;
201 int weight;
204 /* Is "edge" marked as being of type "type"?
206 static int is_type(struct isl_sched_edge *edge, enum isl_edge_type type)
208 return ISL_FL_ISSET(edge->types, 1 << type);
211 /* Mark "edge" as being of type "type".
213 static void set_type(struct isl_sched_edge *edge, enum isl_edge_type type)
215 ISL_FL_SET(edge->types, 1 << type);
218 /* No longer mark "edge" as being of type "type"?
220 static void clear_type(struct isl_sched_edge *edge, enum isl_edge_type type)
222 ISL_FL_CLR(edge->types, 1 << type);
225 /* Is "edge" marked as a validity edge?
227 static int is_validity(struct isl_sched_edge *edge)
229 return is_type(edge, isl_edge_validity);
232 /* Mark "edge" as a validity edge.
234 static void set_validity(struct isl_sched_edge *edge)
236 set_type(edge, isl_edge_validity);
239 /* Is "edge" marked as a proximity edge?
241 static int is_proximity(struct isl_sched_edge *edge)
243 return is_type(edge, isl_edge_proximity);
246 /* Is "edge" marked as a local edge?
248 static int is_local(struct isl_sched_edge *edge)
250 return is_type(edge, isl_edge_local);
253 /* Mark "edge" as a local edge.
255 static void set_local(struct isl_sched_edge *edge)
257 set_type(edge, isl_edge_local);
260 /* No longer mark "edge" as a local edge.
262 static void clear_local(struct isl_sched_edge *edge)
264 clear_type(edge, isl_edge_local);
267 /* Is "edge" marked as a coincidence edge?
269 static int is_coincidence(struct isl_sched_edge *edge)
271 return is_type(edge, isl_edge_coincidence);
274 /* Is "edge" marked as a condition edge?
276 static int is_condition(struct isl_sched_edge *edge)
278 return is_type(edge, isl_edge_condition);
281 /* Is "edge" marked as a conditional validity edge?
283 static int is_conditional_validity(struct isl_sched_edge *edge)
285 return is_type(edge, isl_edge_conditional_validity);
288 /* Is "edge" of a type that can appear multiple times between
289 * the same pair of nodes?
291 * Condition edges and conditional validity edges may have tagged
292 * dependence relations, in which case an edge is added for each
293 * pair of tags.
295 static int is_multi_edge_type(struct isl_sched_edge *edge)
297 return is_condition(edge) || is_conditional_validity(edge);
300 /* Internal information about the dependence graph used during
301 * the construction of the schedule.
303 * intra_hmap is a cache, mapping dependence relations to their dual,
304 * for dependences from a node to itself, possibly without
305 * coefficients for the parameters
306 * intra_hmap_param is a cache, mapping dependence relations to their dual,
307 * for dependences from a node to itself, including coefficients
308 * for the parameters
309 * inter_hmap is a cache, mapping dependence relations to their dual,
310 * for dependences between distinct nodes
311 * if compression is involved then the key for these maps
312 * is the original, uncompressed dependence relation, while
313 * the value is the dual of the compressed dependence relation.
315 * n is the number of nodes
316 * node is the list of nodes
317 * maxvar is the maximal number of variables over all nodes
318 * max_row is the allocated number of rows in the schedule
319 * n_row is the current (maximal) number of linearly independent
320 * rows in the node schedules
321 * n_total_row is the current number of rows in the node schedules
322 * band_start is the starting row in the node schedules of the current band
323 * root is set to the the original dependence graph from which this graph
324 * is derived through splitting. If this graph is not the result of
325 * splitting, then the root field points to the graph itself.
327 * sorted contains a list of node indices sorted according to the
328 * SCC to which a node belongs
330 * n_edge is the number of edges
331 * edge is the list of edges
332 * max_edge contains the maximal number of edges of each type;
333 * in particular, it contains the number of edges in the inital graph.
334 * edge_table contains pointers into the edge array, hashed on the source
335 * and sink spaces; there is one such table for each type;
336 * a given edge may be referenced from more than one table
337 * if the corresponding relation appears in more than one of the
338 * sets of dependences; however, for each type there is only
339 * a single edge between a given pair of source and sink space
340 * in the entire graph
342 * node_table contains pointers into the node array, hashed on the space tuples
344 * region contains a list of variable sequences that should be non-trivial
346 * lp contains the (I)LP problem used to obtain new schedule rows
348 * src_scc and dst_scc are the source and sink SCCs of an edge with
349 * conflicting constraints
351 * scc represents the number of components
352 * weak is set if the components are weakly connected
354 * max_weight is used during clustering and represents the maximal
355 * weight of the relevant proximity edges.
357 struct isl_sched_graph {
358 isl_map_to_basic_set *intra_hmap;
359 isl_map_to_basic_set *intra_hmap_param;
360 isl_map_to_basic_set *inter_hmap;
362 struct isl_sched_node *node;
363 int n;
364 int maxvar;
365 int max_row;
366 int n_row;
368 int *sorted;
370 int n_total_row;
371 int band_start;
373 struct isl_sched_graph *root;
375 struct isl_sched_edge *edge;
376 int n_edge;
377 int max_edge[isl_edge_last + 1];
378 struct isl_hash_table *edge_table[isl_edge_last + 1];
380 struct isl_hash_table *node_table;
381 struct isl_trivial_region *region;
383 isl_basic_set *lp;
385 int src_scc;
386 int dst_scc;
388 int scc;
389 int weak;
391 int max_weight;
394 /* Initialize node_table based on the list of nodes.
396 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
398 int i;
400 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
401 if (!graph->node_table)
402 return -1;
404 for (i = 0; i < graph->n; ++i) {
405 struct isl_hash_table_entry *entry;
406 uint32_t hash;
408 hash = isl_space_get_tuple_hash(graph->node[i].space);
409 entry = isl_hash_table_find(ctx, graph->node_table, hash,
410 &node_has_tuples,
411 graph->node[i].space, 1);
412 if (!entry)
413 return -1;
414 entry->data = &graph->node[i];
417 return 0;
420 /* Return a pointer to the node that lives within the given space,
421 * or NULL if there is no such node.
423 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
424 struct isl_sched_graph *graph, __isl_keep isl_space *space)
426 struct isl_hash_table_entry *entry;
427 uint32_t hash;
429 hash = isl_space_get_tuple_hash(space);
430 entry = isl_hash_table_find(ctx, graph->node_table, hash,
431 &node_has_tuples, space, 0);
433 return entry ? entry->data : NULL;
436 /* Is "node" a node in "graph"?
438 static int is_node(struct isl_sched_graph *graph,
439 struct isl_sched_node *node)
441 return node && node >= &graph->node[0] && node < &graph->node[graph->n];
444 static int edge_has_src_and_dst(const void *entry, const void *val)
446 const struct isl_sched_edge *edge = entry;
447 const struct isl_sched_edge *temp = val;
449 return edge->src == temp->src && edge->dst == temp->dst;
452 /* Add the given edge to graph->edge_table[type].
454 static isl_stat graph_edge_table_add(isl_ctx *ctx,
455 struct isl_sched_graph *graph, enum isl_edge_type type,
456 struct isl_sched_edge *edge)
458 struct isl_hash_table_entry *entry;
459 uint32_t hash;
461 hash = isl_hash_init();
462 hash = isl_hash_builtin(hash, edge->src);
463 hash = isl_hash_builtin(hash, edge->dst);
464 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
465 &edge_has_src_and_dst, edge, 1);
466 if (!entry)
467 return isl_stat_error;
468 entry->data = edge;
470 return isl_stat_ok;
473 /* Add "edge" to all relevant edge tables.
474 * That is, for every type of the edge, add it to the corresponding table.
476 static isl_stat graph_edge_tables_add(isl_ctx *ctx,
477 struct isl_sched_graph *graph, struct isl_sched_edge *edge)
479 enum isl_edge_type t;
481 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
482 if (!is_type(edge, t))
483 continue;
484 if (graph_edge_table_add(ctx, graph, t, edge) < 0)
485 return isl_stat_error;
488 return isl_stat_ok;
491 /* Allocate the edge_tables based on the maximal number of edges of
492 * each type.
494 static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
496 int i;
498 for (i = 0; i <= isl_edge_last; ++i) {
499 graph->edge_table[i] = isl_hash_table_alloc(ctx,
500 graph->max_edge[i]);
501 if (!graph->edge_table[i])
502 return -1;
505 return 0;
508 /* If graph->edge_table[type] contains an edge from the given source
509 * to the given destination, then return the hash table entry of this edge.
510 * Otherwise, return NULL.
512 static struct isl_hash_table_entry *graph_find_edge_entry(
513 struct isl_sched_graph *graph,
514 enum isl_edge_type type,
515 struct isl_sched_node *src, struct isl_sched_node *dst)
517 isl_ctx *ctx = isl_space_get_ctx(src->space);
518 uint32_t hash;
519 struct isl_sched_edge temp = { .src = src, .dst = dst };
521 hash = isl_hash_init();
522 hash = isl_hash_builtin(hash, temp.src);
523 hash = isl_hash_builtin(hash, temp.dst);
524 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
525 &edge_has_src_and_dst, &temp, 0);
529 /* If graph->edge_table[type] contains an edge from the given source
530 * to the given destination, then return this edge.
531 * Otherwise, return NULL.
533 static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
534 enum isl_edge_type type,
535 struct isl_sched_node *src, struct isl_sched_node *dst)
537 struct isl_hash_table_entry *entry;
539 entry = graph_find_edge_entry(graph, type, src, dst);
540 if (!entry)
541 return NULL;
543 return entry->data;
546 /* Check whether the dependence graph has an edge of the given type
547 * between the given two nodes.
549 static isl_bool graph_has_edge(struct isl_sched_graph *graph,
550 enum isl_edge_type type,
551 struct isl_sched_node *src, struct isl_sched_node *dst)
553 struct isl_sched_edge *edge;
554 isl_bool empty;
556 edge = graph_find_edge(graph, type, src, dst);
557 if (!edge)
558 return 0;
560 empty = isl_map_plain_is_empty(edge->map);
561 if (empty < 0)
562 return isl_bool_error;
564 return !empty;
567 /* Look for any edge with the same src, dst and map fields as "model".
569 * Return the matching edge if one can be found.
570 * Return "model" if no matching edge is found.
571 * Return NULL on error.
573 static struct isl_sched_edge *graph_find_matching_edge(
574 struct isl_sched_graph *graph, struct isl_sched_edge *model)
576 enum isl_edge_type i;
577 struct isl_sched_edge *edge;
579 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
580 int is_equal;
582 edge = graph_find_edge(graph, i, model->src, model->dst);
583 if (!edge)
584 continue;
585 is_equal = isl_map_plain_is_equal(model->map, edge->map);
586 if (is_equal < 0)
587 return NULL;
588 if (is_equal)
589 return edge;
592 return model;
595 /* Remove the given edge from all the edge_tables that refer to it.
597 static void graph_remove_edge(struct isl_sched_graph *graph,
598 struct isl_sched_edge *edge)
600 isl_ctx *ctx = isl_map_get_ctx(edge->map);
601 enum isl_edge_type i;
603 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
604 struct isl_hash_table_entry *entry;
606 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
607 if (!entry)
608 continue;
609 if (entry->data != edge)
610 continue;
611 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
615 /* Check whether the dependence graph has any edge
616 * between the given two nodes.
618 static isl_bool graph_has_any_edge(struct isl_sched_graph *graph,
619 struct isl_sched_node *src, struct isl_sched_node *dst)
621 enum isl_edge_type i;
622 isl_bool r;
624 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
625 r = graph_has_edge(graph, i, src, dst);
626 if (r < 0 || r)
627 return r;
630 return r;
633 /* Check whether the dependence graph has a validity edge
634 * between the given two nodes.
636 * Conditional validity edges are essentially validity edges that
637 * can be ignored if the corresponding condition edges are iteration private.
638 * Here, we are only checking for the presence of validity
639 * edges, so we need to consider the conditional validity edges too.
640 * In particular, this function is used during the detection
641 * of strongly connected components and we cannot ignore
642 * conditional validity edges during this detection.
644 static isl_bool graph_has_validity_edge(struct isl_sched_graph *graph,
645 struct isl_sched_node *src, struct isl_sched_node *dst)
647 isl_bool r;
649 r = graph_has_edge(graph, isl_edge_validity, src, dst);
650 if (r < 0 || r)
651 return r;
653 return graph_has_edge(graph, isl_edge_conditional_validity, src, dst);
656 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
657 int n_node, int n_edge)
659 int i;
661 graph->n = n_node;
662 graph->n_edge = n_edge;
663 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
664 graph->sorted = isl_calloc_array(ctx, int, graph->n);
665 graph->region = isl_alloc_array(ctx,
666 struct isl_trivial_region, graph->n);
667 graph->edge = isl_calloc_array(ctx,
668 struct isl_sched_edge, graph->n_edge);
670 graph->intra_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
671 graph->intra_hmap_param = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
672 graph->inter_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
674 if (!graph->node || !graph->region || (graph->n_edge && !graph->edge) ||
675 !graph->sorted)
676 return -1;
678 for(i = 0; i < graph->n; ++i)
679 graph->sorted[i] = i;
681 return 0;
684 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
686 int i;
688 isl_map_to_basic_set_free(graph->intra_hmap);
689 isl_map_to_basic_set_free(graph->intra_hmap_param);
690 isl_map_to_basic_set_free(graph->inter_hmap);
692 if (graph->node)
693 for (i = 0; i < graph->n; ++i) {
694 isl_space_free(graph->node[i].space);
695 isl_set_free(graph->node[i].hull);
696 isl_multi_aff_free(graph->node[i].compress);
697 isl_multi_aff_free(graph->node[i].decompress);
698 isl_mat_free(graph->node[i].sched);
699 isl_map_free(graph->node[i].sched_map);
700 isl_mat_free(graph->node[i].indep);
701 isl_mat_free(graph->node[i].vmap);
702 if (graph->root == graph)
703 free(graph->node[i].coincident);
704 isl_multi_val_free(graph->node[i].sizes);
705 isl_basic_set_free(graph->node[i].bounds);
706 isl_vec_free(graph->node[i].max);
708 free(graph->node);
709 free(graph->sorted);
710 if (graph->edge)
711 for (i = 0; i < graph->n_edge; ++i) {
712 isl_map_free(graph->edge[i].map);
713 isl_union_map_free(graph->edge[i].tagged_condition);
714 isl_union_map_free(graph->edge[i].tagged_validity);
716 free(graph->edge);
717 free(graph->region);
718 for (i = 0; i <= isl_edge_last; ++i)
719 isl_hash_table_free(ctx, graph->edge_table[i]);
720 isl_hash_table_free(ctx, graph->node_table);
721 isl_basic_set_free(graph->lp);
724 /* For each "set" on which this function is called, increment
725 * graph->n by one and update graph->maxvar.
727 static isl_stat init_n_maxvar(__isl_take isl_set *set, void *user)
729 struct isl_sched_graph *graph = user;
730 int nvar = isl_set_dim(set, isl_dim_set);
732 graph->n++;
733 if (nvar > graph->maxvar)
734 graph->maxvar = nvar;
736 isl_set_free(set);
738 return isl_stat_ok;
741 /* Compute the number of rows that should be allocated for the schedule.
742 * In particular, we need one row for each variable or one row
743 * for each basic map in the dependences.
744 * Note that it is practically impossible to exhaust both
745 * the number of dependences and the number of variables.
747 static isl_stat compute_max_row(struct isl_sched_graph *graph,
748 __isl_keep isl_schedule_constraints *sc)
750 int n_edge;
751 isl_stat r;
752 isl_union_set *domain;
754 graph->n = 0;
755 graph->maxvar = 0;
756 domain = isl_schedule_constraints_get_domain(sc);
757 r = isl_union_set_foreach_set(domain, &init_n_maxvar, graph);
758 isl_union_set_free(domain);
759 if (r < 0)
760 return isl_stat_error;
761 n_edge = isl_schedule_constraints_n_basic_map(sc);
762 if (n_edge < 0)
763 return isl_stat_error;
764 graph->max_row = n_edge + graph->maxvar;
766 return isl_stat_ok;
769 /* Does "bset" have any defining equalities for its set variables?
771 static isl_bool has_any_defining_equality(__isl_keep isl_basic_set *bset)
773 int i, n;
775 if (!bset)
776 return isl_bool_error;
778 n = isl_basic_set_dim(bset, isl_dim_set);
779 for (i = 0; i < n; ++i) {
780 isl_bool has;
782 has = isl_basic_set_has_defining_equality(bset, isl_dim_set, i,
783 NULL);
784 if (has < 0 || has)
785 return has;
788 return isl_bool_false;
791 /* Set the entries of node->max to the value of the schedule_max_coefficient
792 * option, if set.
794 static isl_stat set_max_coefficient(isl_ctx *ctx, struct isl_sched_node *node)
796 int max;
798 max = isl_options_get_schedule_max_coefficient(ctx);
799 if (max == -1)
800 return isl_stat_ok;
802 node->max = isl_vec_alloc(ctx, node->nvar);
803 node->max = isl_vec_set_si(node->max, max);
804 if (!node->max)
805 return isl_stat_error;
807 return isl_stat_ok;
810 /* Set the entries of node->max to the minimum of the schedule_max_coefficient
811 * option (if set) and half of the minimum of the sizes in the other
812 * dimensions. Round up when computing the half such that
813 * if the minimum of the sizes is one, half of the size is taken to be one
814 * rather than zero.
815 * If the global minimum is unbounded (i.e., if both
816 * the schedule_max_coefficient is not set and the sizes in the other
817 * dimensions are unbounded), then store a negative value.
818 * If the schedule coefficient is close to the size of the instance set
819 * in another dimension, then the schedule may represent a loop
820 * coalescing transformation (especially if the coefficient
821 * in that other dimension is one). Forcing the coefficient to be
822 * smaller than or equal to half the minimal size should avoid this
823 * situation.
825 static isl_stat compute_max_coefficient(isl_ctx *ctx,
826 struct isl_sched_node *node)
828 int max;
829 int i, j;
830 isl_vec *v;
832 max = isl_options_get_schedule_max_coefficient(ctx);
833 v = isl_vec_alloc(ctx, node->nvar);
834 if (!v)
835 return isl_stat_error;
837 for (i = 0; i < node->nvar; ++i) {
838 isl_int_set_si(v->el[i], max);
839 isl_int_mul_si(v->el[i], v->el[i], 2);
842 for (i = 0; i < node->nvar; ++i) {
843 isl_val *size;
845 size = isl_multi_val_get_val(node->sizes, i);
846 if (!size)
847 goto error;
848 if (!isl_val_is_int(size)) {
849 isl_val_free(size);
850 continue;
852 for (j = 0; j < node->nvar; ++j) {
853 if (j == i)
854 continue;
855 if (isl_int_is_neg(v->el[j]) ||
856 isl_int_gt(v->el[j], size->n))
857 isl_int_set(v->el[j], size->n);
859 isl_val_free(size);
862 for (i = 0; i < node->nvar; ++i)
863 isl_int_cdiv_q_ui(v->el[i], v->el[i], 2);
865 node->max = v;
866 return isl_stat_ok;
867 error:
868 isl_vec_free(v);
869 return isl_stat_error;
872 /* Compute and return the size of "set" in dimension "dim".
873 * The size is taken to be the difference in values for that variable
874 * for fixed values of the other variables.
875 * This assumes that "set" is convex.
876 * In particular, the variable is first isolated from the other variables
877 * in the range of a map
879 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
881 * and then duplicated
883 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
885 * The shared variables are then projected out and the maximal value
886 * of i_dim' - i_dim is computed.
888 static __isl_give isl_val *compute_size(__isl_take isl_set *set, int dim)
890 isl_map *map;
891 isl_local_space *ls;
892 isl_aff *obj;
893 isl_val *v;
895 map = isl_set_project_onto_map(set, isl_dim_set, dim, 1);
896 map = isl_map_project_out(map, isl_dim_in, dim, 1);
897 map = isl_map_range_product(map, isl_map_copy(map));
898 map = isl_set_unwrap(isl_map_range(map));
899 set = isl_map_deltas(map);
900 ls = isl_local_space_from_space(isl_set_get_space(set));
901 obj = isl_aff_var_on_domain(ls, isl_dim_set, 0);
902 v = isl_set_max_val(set, obj);
903 isl_aff_free(obj);
904 isl_set_free(set);
906 return v;
909 /* Compute the size of the instance set "set" of "node", after compression,
910 * as well as bounds on the corresponding coefficients, if needed.
912 * The sizes are needed when the schedule_treat_coalescing option is set.
913 * The bounds are needed when the schedule_treat_coalescing option or
914 * the schedule_max_coefficient option is set.
916 * If the schedule_treat_coalescing option is not set, then at most
917 * the bounds need to be set and this is done in set_max_coefficient.
918 * Otherwise, compress the domain if needed, compute the size
919 * in each direction and store the results in node->size.
920 * If the domain is not convex, then the sizes are computed
921 * on a convex superset in order to avoid picking up sizes
922 * that are valid for the individual disjuncts, but not for
923 * the domain as a whole.
924 * Finally, set the bounds on the coefficients based on the sizes
925 * and the schedule_max_coefficient option in compute_max_coefficient.
927 static isl_stat compute_sizes_and_max(isl_ctx *ctx, struct isl_sched_node *node,
928 __isl_take isl_set *set)
930 int j, n;
931 isl_multi_val *mv;
933 if (!isl_options_get_schedule_treat_coalescing(ctx)) {
934 isl_set_free(set);
935 return set_max_coefficient(ctx, node);
938 if (node->compressed)
939 set = isl_set_preimage_multi_aff(set,
940 isl_multi_aff_copy(node->decompress));
941 set = isl_set_from_basic_set(isl_set_simple_hull(set));
942 mv = isl_multi_val_zero(isl_set_get_space(set));
943 n = isl_set_dim(set, isl_dim_set);
944 for (j = 0; j < n; ++j) {
945 isl_val *v;
947 v = compute_size(isl_set_copy(set), j);
948 mv = isl_multi_val_set_val(mv, j, v);
950 node->sizes = mv;
951 isl_set_free(set);
952 if (!node->sizes)
953 return isl_stat_error;
954 return compute_max_coefficient(ctx, node);
957 /* Add a new node to the graph representing the given instance set.
958 * "nvar" is the (possibly compressed) number of variables and
959 * may be smaller than then number of set variables in "set"
960 * if "compressed" is set.
961 * If "compressed" is set, then "hull" represents the constraints
962 * that were used to derive the compression, while "compress" and
963 * "decompress" map the original space to the compressed space and
964 * vice versa.
965 * If "compressed" is not set, then "hull", "compress" and "decompress"
966 * should be NULL.
968 * Compute the size of the instance set and bounds on the coefficients,
969 * if needed.
971 static isl_stat add_node(struct isl_sched_graph *graph,
972 __isl_take isl_set *set, int nvar, int compressed,
973 __isl_take isl_set *hull, __isl_take isl_multi_aff *compress,
974 __isl_take isl_multi_aff *decompress)
976 int nparam;
977 isl_ctx *ctx;
978 isl_mat *sched;
979 isl_space *space;
980 int *coincident;
981 struct isl_sched_node *node;
983 if (!set)
984 return isl_stat_error;
986 ctx = isl_set_get_ctx(set);
987 nparam = isl_set_dim(set, isl_dim_param);
988 if (!ctx->opt->schedule_parametric)
989 nparam = 0;
990 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
991 node = &graph->node[graph->n];
992 graph->n++;
993 space = isl_set_get_space(set);
994 node->space = space;
995 node->nvar = nvar;
996 node->nparam = nparam;
997 node->sched = sched;
998 node->sched_map = NULL;
999 coincident = isl_calloc_array(ctx, int, graph->max_row);
1000 node->coincident = coincident;
1001 node->compressed = compressed;
1002 node->hull = hull;
1003 node->compress = compress;
1004 node->decompress = decompress;
1005 if (compute_sizes_and_max(ctx, node, set) < 0)
1006 return isl_stat_error;
1008 if (!space || !sched || (graph->max_row && !coincident))
1009 return isl_stat_error;
1010 if (compressed && (!hull || !compress || !decompress))
1011 return isl_stat_error;
1013 return isl_stat_ok;
1016 /* Construct an identifier for node "node", which will represent "set".
1017 * The name of the identifier is either "compressed" or
1018 * "compressed_<name>", with <name> the name of the space of "set".
1019 * The user pointer of the identifier points to "node".
1021 static __isl_give isl_id *construct_compressed_id(__isl_keep isl_set *set,
1022 struct isl_sched_node *node)
1024 isl_bool has_name;
1025 isl_ctx *ctx;
1026 isl_id *id;
1027 isl_printer *p;
1028 const char *name;
1029 char *id_name;
1031 has_name = isl_set_has_tuple_name(set);
1032 if (has_name < 0)
1033 return NULL;
1035 ctx = isl_set_get_ctx(set);
1036 if (!has_name)
1037 return isl_id_alloc(ctx, "compressed", node);
1039 p = isl_printer_to_str(ctx);
1040 name = isl_set_get_tuple_name(set);
1041 p = isl_printer_print_str(p, "compressed_");
1042 p = isl_printer_print_str(p, name);
1043 id_name = isl_printer_get_str(p);
1044 isl_printer_free(p);
1046 id = isl_id_alloc(ctx, id_name, node);
1047 free(id_name);
1049 return id;
1052 /* Add a new node to the graph representing the given set.
1054 * If any of the set variables is defined by an equality, then
1055 * we perform variable compression such that we can perform
1056 * the scheduling on the compressed domain.
1057 * In this case, an identifier is used that references the new node
1058 * such that each compressed space is unique and
1059 * such that the node can be recovered from the compressed space.
1061 static isl_stat extract_node(__isl_take isl_set *set, void *user)
1063 int nvar;
1064 isl_bool has_equality;
1065 isl_id *id;
1066 isl_basic_set *hull;
1067 isl_set *hull_set;
1068 isl_morph *morph;
1069 isl_multi_aff *compress, *decompress;
1070 struct isl_sched_graph *graph = user;
1072 hull = isl_set_affine_hull(isl_set_copy(set));
1073 hull = isl_basic_set_remove_divs(hull);
1074 nvar = isl_set_dim(set, isl_dim_set);
1075 has_equality = has_any_defining_equality(hull);
1077 if (has_equality < 0)
1078 goto error;
1079 if (!has_equality) {
1080 isl_basic_set_free(hull);
1081 return add_node(graph, set, nvar, 0, NULL, NULL, NULL);
1084 id = construct_compressed_id(set, &graph->node[graph->n]);
1085 morph = isl_basic_set_variable_compression_with_id(hull,
1086 isl_dim_set, id);
1087 isl_id_free(id);
1088 nvar = isl_morph_ran_dim(morph, isl_dim_set);
1089 compress = isl_morph_get_var_multi_aff(morph);
1090 morph = isl_morph_inverse(morph);
1091 decompress = isl_morph_get_var_multi_aff(morph);
1092 isl_morph_free(morph);
1094 hull_set = isl_set_from_basic_set(hull);
1095 return add_node(graph, set, nvar, 1, hull_set, compress, decompress);
1096 error:
1097 isl_basic_set_free(hull);
1098 isl_set_free(set);
1099 return isl_stat_error;
1102 struct isl_extract_edge_data {
1103 enum isl_edge_type type;
1104 struct isl_sched_graph *graph;
1107 /* Merge edge2 into edge1, freeing the contents of edge2.
1108 * Return 0 on success and -1 on failure.
1110 * edge1 and edge2 are assumed to have the same value for the map field.
1112 static int merge_edge(struct isl_sched_edge *edge1,
1113 struct isl_sched_edge *edge2)
1115 edge1->types |= edge2->types;
1116 isl_map_free(edge2->map);
1118 if (is_condition(edge2)) {
1119 if (!edge1->tagged_condition)
1120 edge1->tagged_condition = edge2->tagged_condition;
1121 else
1122 edge1->tagged_condition =
1123 isl_union_map_union(edge1->tagged_condition,
1124 edge2->tagged_condition);
1127 if (is_conditional_validity(edge2)) {
1128 if (!edge1->tagged_validity)
1129 edge1->tagged_validity = edge2->tagged_validity;
1130 else
1131 edge1->tagged_validity =
1132 isl_union_map_union(edge1->tagged_validity,
1133 edge2->tagged_validity);
1136 if (is_condition(edge2) && !edge1->tagged_condition)
1137 return -1;
1138 if (is_conditional_validity(edge2) && !edge1->tagged_validity)
1139 return -1;
1141 return 0;
1144 /* Insert dummy tags in domain and range of "map".
1146 * In particular, if "map" is of the form
1148 * A -> B
1150 * then return
1152 * [A -> dummy_tag] -> [B -> dummy_tag]
1154 * where the dummy_tags are identical and equal to any dummy tags
1155 * introduced by any other call to this function.
1157 static __isl_give isl_map *insert_dummy_tags(__isl_take isl_map *map)
1159 static char dummy;
1160 isl_ctx *ctx;
1161 isl_id *id;
1162 isl_space *space;
1163 isl_set *domain, *range;
1165 ctx = isl_map_get_ctx(map);
1167 id = isl_id_alloc(ctx, NULL, &dummy);
1168 space = isl_space_params(isl_map_get_space(map));
1169 space = isl_space_set_from_params(space);
1170 space = isl_space_set_tuple_id(space, isl_dim_set, id);
1171 space = isl_space_map_from_set(space);
1173 domain = isl_map_wrap(map);
1174 range = isl_map_wrap(isl_map_universe(space));
1175 map = isl_map_from_domain_and_range(domain, range);
1176 map = isl_map_zip(map);
1178 return map;
1181 /* Given that at least one of "src" or "dst" is compressed, return
1182 * a map between the spaces of these nodes restricted to the affine
1183 * hull that was used in the compression.
1185 static __isl_give isl_map *extract_hull(struct isl_sched_node *src,
1186 struct isl_sched_node *dst)
1188 isl_set *dom, *ran;
1190 if (src->compressed)
1191 dom = isl_set_copy(src->hull);
1192 else
1193 dom = isl_set_universe(isl_space_copy(src->space));
1194 if (dst->compressed)
1195 ran = isl_set_copy(dst->hull);
1196 else
1197 ran = isl_set_universe(isl_space_copy(dst->space));
1199 return isl_map_from_domain_and_range(dom, ran);
1202 /* Intersect the domains of the nested relations in domain and range
1203 * of "tagged" with "map".
1205 static __isl_give isl_map *map_intersect_domains(__isl_take isl_map *tagged,
1206 __isl_keep isl_map *map)
1208 isl_set *set;
1210 tagged = isl_map_zip(tagged);
1211 set = isl_map_wrap(isl_map_copy(map));
1212 tagged = isl_map_intersect_domain(tagged, set);
1213 tagged = isl_map_zip(tagged);
1214 return tagged;
1217 /* Return a pointer to the node that lives in the domain space of "map"
1218 * or NULL if there is no such node.
1220 static struct isl_sched_node *find_domain_node(isl_ctx *ctx,
1221 struct isl_sched_graph *graph, __isl_keep isl_map *map)
1223 struct isl_sched_node *node;
1224 isl_space *space;
1226 space = isl_space_domain(isl_map_get_space(map));
1227 node = graph_find_node(ctx, graph, space);
1228 isl_space_free(space);
1230 return node;
1233 /* Return a pointer to the node that lives in the range space of "map"
1234 * or NULL if there is no such node.
1236 static struct isl_sched_node *find_range_node(isl_ctx *ctx,
1237 struct isl_sched_graph *graph, __isl_keep isl_map *map)
1239 struct isl_sched_node *node;
1240 isl_space *space;
1242 space = isl_space_range(isl_map_get_space(map));
1243 node = graph_find_node(ctx, graph, space);
1244 isl_space_free(space);
1246 return node;
1249 /* Refrain from adding a new edge based on "map".
1250 * Instead, just free the map.
1251 * "tagged" is either a copy of "map" with additional tags or NULL.
1253 static isl_stat skip_edge(__isl_take isl_map *map, __isl_take isl_map *tagged)
1255 isl_map_free(map);
1256 isl_map_free(tagged);
1258 return isl_stat_ok;
1261 /* Add a new edge to the graph based on the given map
1262 * and add it to data->graph->edge_table[data->type].
1263 * If a dependence relation of a given type happens to be identical
1264 * to one of the dependence relations of a type that was added before,
1265 * then we don't create a new edge, but instead mark the original edge
1266 * as also representing a dependence of the current type.
1268 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1269 * may be specified as "tagged" dependence relations. That is, "map"
1270 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1271 * the dependence on iterations and a and b are tags.
1272 * edge->map is set to the relation containing the elements i -> j,
1273 * while edge->tagged_condition and edge->tagged_validity contain
1274 * the union of all the "map" relations
1275 * for which extract_edge is called that result in the same edge->map.
1277 * If the source or the destination node is compressed, then
1278 * intersect both "map" and "tagged" with the constraints that
1279 * were used to construct the compression.
1280 * This ensures that there are no schedule constraints defined
1281 * outside of these domains, while the scheduler no longer has
1282 * any control over those outside parts.
1284 static isl_stat extract_edge(__isl_take isl_map *map, void *user)
1286 isl_bool empty;
1287 isl_ctx *ctx = isl_map_get_ctx(map);
1288 struct isl_extract_edge_data *data = user;
1289 struct isl_sched_graph *graph = data->graph;
1290 struct isl_sched_node *src, *dst;
1291 struct isl_sched_edge *edge;
1292 isl_map *tagged = NULL;
1294 if (data->type == isl_edge_condition ||
1295 data->type == isl_edge_conditional_validity) {
1296 if (isl_map_can_zip(map)) {
1297 tagged = isl_map_copy(map);
1298 map = isl_set_unwrap(isl_map_domain(isl_map_zip(map)));
1299 } else {
1300 tagged = insert_dummy_tags(isl_map_copy(map));
1304 src = find_domain_node(ctx, graph, map);
1305 dst = find_range_node(ctx, graph, map);
1307 if (!src || !dst)
1308 return skip_edge(map, tagged);
1310 if (src->compressed || dst->compressed) {
1311 isl_map *hull;
1312 hull = extract_hull(src, dst);
1313 if (tagged)
1314 tagged = map_intersect_domains(tagged, hull);
1315 map = isl_map_intersect(map, hull);
1318 empty = isl_map_plain_is_empty(map);
1319 if (empty < 0)
1320 goto error;
1321 if (empty)
1322 return skip_edge(map, tagged);
1324 graph->edge[graph->n_edge].src = src;
1325 graph->edge[graph->n_edge].dst = dst;
1326 graph->edge[graph->n_edge].map = map;
1327 graph->edge[graph->n_edge].types = 0;
1328 graph->edge[graph->n_edge].tagged_condition = NULL;
1329 graph->edge[graph->n_edge].tagged_validity = NULL;
1330 set_type(&graph->edge[graph->n_edge], data->type);
1331 if (data->type == isl_edge_condition)
1332 graph->edge[graph->n_edge].tagged_condition =
1333 isl_union_map_from_map(tagged);
1334 if (data->type == isl_edge_conditional_validity)
1335 graph->edge[graph->n_edge].tagged_validity =
1336 isl_union_map_from_map(tagged);
1338 edge = graph_find_matching_edge(graph, &graph->edge[graph->n_edge]);
1339 if (!edge) {
1340 graph->n_edge++;
1341 return isl_stat_error;
1343 if (edge == &graph->edge[graph->n_edge])
1344 return graph_edge_table_add(ctx, graph, data->type,
1345 &graph->edge[graph->n_edge++]);
1347 if (merge_edge(edge, &graph->edge[graph->n_edge]) < 0)
1348 return isl_stat_error;
1350 return graph_edge_table_add(ctx, graph, data->type, edge);
1351 error:
1352 isl_map_free(map);
1353 isl_map_free(tagged);
1354 return isl_stat_error;
1357 /* Initialize the schedule graph "graph" from the schedule constraints "sc".
1359 * The context is included in the domain before the nodes of
1360 * the graphs are extracted in order to be able to exploit
1361 * any possible additional equalities.
1362 * Note that this intersection is only performed locally here.
1364 static isl_stat graph_init(struct isl_sched_graph *graph,
1365 __isl_keep isl_schedule_constraints *sc)
1367 isl_ctx *ctx;
1368 isl_union_set *domain;
1369 isl_union_map *c;
1370 struct isl_extract_edge_data data;
1371 enum isl_edge_type i;
1372 isl_stat r;
1374 if (!sc)
1375 return isl_stat_error;
1377 ctx = isl_schedule_constraints_get_ctx(sc);
1379 domain = isl_schedule_constraints_get_domain(sc);
1380 graph->n = isl_union_set_n_set(domain);
1381 isl_union_set_free(domain);
1383 if (graph_alloc(ctx, graph, graph->n,
1384 isl_schedule_constraints_n_map(sc)) < 0)
1385 return isl_stat_error;
1387 if (compute_max_row(graph, sc) < 0)
1388 return isl_stat_error;
1389 graph->root = graph;
1390 graph->n = 0;
1391 domain = isl_schedule_constraints_get_domain(sc);
1392 domain = isl_union_set_intersect_params(domain,
1393 isl_schedule_constraints_get_context(sc));
1394 r = isl_union_set_foreach_set(domain, &extract_node, graph);
1395 isl_union_set_free(domain);
1396 if (r < 0)
1397 return isl_stat_error;
1398 if (graph_init_table(ctx, graph) < 0)
1399 return isl_stat_error;
1400 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
1401 c = isl_schedule_constraints_get(sc, i);
1402 graph->max_edge[i] = isl_union_map_n_map(c);
1403 isl_union_map_free(c);
1404 if (!c)
1405 return isl_stat_error;
1407 if (graph_init_edge_tables(ctx, graph) < 0)
1408 return isl_stat_error;
1409 graph->n_edge = 0;
1410 data.graph = graph;
1411 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
1412 isl_stat r;
1414 data.type = i;
1415 c = isl_schedule_constraints_get(sc, i);
1416 r = isl_union_map_foreach_map(c, &extract_edge, &data);
1417 isl_union_map_free(c);
1418 if (r < 0)
1419 return isl_stat_error;
1422 return isl_stat_ok;
1425 /* Check whether there is any dependence from node[j] to node[i]
1426 * or from node[i] to node[j].
1428 static isl_bool node_follows_weak(int i, int j, void *user)
1430 isl_bool f;
1431 struct isl_sched_graph *graph = user;
1433 f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]);
1434 if (f < 0 || f)
1435 return f;
1436 return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]);
1439 /* Check whether there is a (conditional) validity dependence from node[j]
1440 * to node[i], forcing node[i] to follow node[j].
1442 static isl_bool node_follows_strong(int i, int j, void *user)
1444 struct isl_sched_graph *graph = user;
1446 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
1449 /* Use Tarjan's algorithm for computing the strongly connected components
1450 * in the dependence graph only considering those edges defined by "follows".
1452 static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph,
1453 isl_bool (*follows)(int i, int j, void *user))
1455 int i, n;
1456 struct isl_tarjan_graph *g = NULL;
1458 g = isl_tarjan_graph_init(ctx, graph->n, follows, graph);
1459 if (!g)
1460 return -1;
1462 graph->scc = 0;
1463 i = 0;
1464 n = graph->n;
1465 while (n) {
1466 while (g->order[i] != -1) {
1467 graph->node[g->order[i]].scc = graph->scc;
1468 --n;
1469 ++i;
1471 ++i;
1472 graph->scc++;
1475 isl_tarjan_graph_free(g);
1477 return 0;
1480 /* Apply Tarjan's algorithm to detect the strongly connected components
1481 * in the dependence graph.
1482 * Only consider the (conditional) validity dependences and clear "weak".
1484 static int detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1486 graph->weak = 0;
1487 return detect_ccs(ctx, graph, &node_follows_strong);
1490 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1491 * in the dependence graph.
1492 * Consider all dependences and set "weak".
1494 static int detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1496 graph->weak = 1;
1497 return detect_ccs(ctx, graph, &node_follows_weak);
1500 static int cmp_scc(const void *a, const void *b, void *data)
1502 struct isl_sched_graph *graph = data;
1503 const int *i1 = a;
1504 const int *i2 = b;
1506 return graph->node[*i1].scc - graph->node[*i2].scc;
1509 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1511 static int sort_sccs(struct isl_sched_graph *graph)
1513 return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
1516 /* Return a non-parametric set in the compressed space of "node" that is
1517 * bounded by the size in each direction
1519 * { [x] : -S_i <= x_i <= S_i }
1521 * If S_i is infinity in direction i, then there are no constraints
1522 * in that direction.
1524 * Cache the result in node->bounds.
1526 static __isl_give isl_basic_set *get_size_bounds(struct isl_sched_node *node)
1528 isl_space *space;
1529 isl_basic_set *bounds;
1530 int i;
1531 unsigned nparam;
1533 if (node->bounds)
1534 return isl_basic_set_copy(node->bounds);
1536 if (node->compressed)
1537 space = isl_multi_aff_get_domain_space(node->decompress);
1538 else
1539 space = isl_space_copy(node->space);
1540 nparam = isl_space_dim(space, isl_dim_param);
1541 space = isl_space_drop_dims(space, isl_dim_param, 0, nparam);
1542 bounds = isl_basic_set_universe(space);
1544 for (i = 0; i < node->nvar; ++i) {
1545 isl_val *size;
1547 size = isl_multi_val_get_val(node->sizes, i);
1548 if (!size)
1549 return isl_basic_set_free(bounds);
1550 if (!isl_val_is_int(size)) {
1551 isl_val_free(size);
1552 continue;
1554 bounds = isl_basic_set_upper_bound_val(bounds, isl_dim_set, i,
1555 isl_val_copy(size));
1556 bounds = isl_basic_set_lower_bound_val(bounds, isl_dim_set, i,
1557 isl_val_neg(size));
1560 node->bounds = isl_basic_set_copy(bounds);
1561 return bounds;
1564 /* Drop some constraints from "delta" that could be exploited
1565 * to construct loop coalescing schedules.
1566 * In particular, drop those constraint that bound the difference
1567 * to the size of the domain.
1568 * First project out the parameters to improve the effectiveness.
1570 static __isl_give isl_set *drop_coalescing_constraints(
1571 __isl_take isl_set *delta, struct isl_sched_node *node)
1573 unsigned nparam;
1574 isl_basic_set *bounds;
1576 bounds = get_size_bounds(node);
1578 nparam = isl_set_dim(delta, isl_dim_param);
1579 delta = isl_set_project_out(delta, isl_dim_param, 0, nparam);
1580 delta = isl_set_remove_divs(delta);
1581 delta = isl_set_plain_gist_basic_set(delta, bounds);
1582 return delta;
1585 /* Given a dependence relation R from "node" to itself,
1586 * construct the set of coefficients of valid constraints for elements
1587 * in that dependence relation.
1588 * In particular, the result contains tuples of coefficients
1589 * c_0, c_n, c_x such that
1591 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1593 * or, equivalently,
1595 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1597 * We choose here to compute the dual of delta R.
1598 * Alternatively, we could have computed the dual of R, resulting
1599 * in a set of tuples c_0, c_n, c_x, c_y, and then
1600 * plugged in (c_0, c_n, c_x, -c_x).
1602 * If "need_param" is set, then the resulting coefficients effectively
1603 * include coefficients for the parameters c_n. Otherwise, they may
1604 * have been projected out already.
1605 * Since the constraints may be different for these two cases,
1606 * they are stored in separate caches.
1607 * In particular, if no parameter coefficients are required and
1608 * the schedule_treat_coalescing option is set, then the parameters
1609 * are projected out and some constraints that could be exploited
1610 * to construct coalescing schedules are removed before the dual
1611 * is computed.
1613 * If "node" has been compressed, then the dependence relation
1614 * is also compressed before the set of coefficients is computed.
1616 static __isl_give isl_basic_set *intra_coefficients(
1617 struct isl_sched_graph *graph, struct isl_sched_node *node,
1618 __isl_take isl_map *map, int need_param)
1620 isl_ctx *ctx;
1621 isl_set *delta;
1622 isl_map *key;
1623 isl_basic_set *coef;
1624 isl_maybe_isl_basic_set m;
1625 isl_map_to_basic_set **hmap = &graph->intra_hmap;
1626 int treat;
1628 if (!map)
1629 return NULL;
1631 ctx = isl_map_get_ctx(map);
1632 treat = !need_param && isl_options_get_schedule_treat_coalescing(ctx);
1633 if (!treat)
1634 hmap = &graph->intra_hmap_param;
1635 m = isl_map_to_basic_set_try_get(*hmap, map);
1636 if (m.valid < 0 || m.valid) {
1637 isl_map_free(map);
1638 return m.value;
1641 key = isl_map_copy(map);
1642 if (node->compressed) {
1643 map = isl_map_preimage_domain_multi_aff(map,
1644 isl_multi_aff_copy(node->decompress));
1645 map = isl_map_preimage_range_multi_aff(map,
1646 isl_multi_aff_copy(node->decompress));
1648 delta = isl_map_deltas(map);
1649 if (treat)
1650 delta = drop_coalescing_constraints(delta, node);
1651 delta = isl_set_remove_divs(delta);
1652 coef = isl_set_coefficients(delta);
1653 *hmap = isl_map_to_basic_set_set(*hmap, key, isl_basic_set_copy(coef));
1655 return coef;
1658 /* Given a dependence relation R, construct the set of coefficients
1659 * of valid constraints for elements in that dependence relation.
1660 * In particular, the result contains tuples of coefficients
1661 * c_0, c_n, c_x, c_y such that
1663 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1665 * If the source or destination nodes of "edge" have been compressed,
1666 * then the dependence relation is also compressed before
1667 * the set of coefficients is computed.
1669 static __isl_give isl_basic_set *inter_coefficients(
1670 struct isl_sched_graph *graph, struct isl_sched_edge *edge,
1671 __isl_take isl_map *map)
1673 isl_set *set;
1674 isl_map *key;
1675 isl_basic_set *coef;
1676 isl_maybe_isl_basic_set m;
1678 m = isl_map_to_basic_set_try_get(graph->inter_hmap, map);
1679 if (m.valid < 0 || m.valid) {
1680 isl_map_free(map);
1681 return m.value;
1684 key = isl_map_copy(map);
1685 if (edge->src->compressed)
1686 map = isl_map_preimage_domain_multi_aff(map,
1687 isl_multi_aff_copy(edge->src->decompress));
1688 if (edge->dst->compressed)
1689 map = isl_map_preimage_range_multi_aff(map,
1690 isl_multi_aff_copy(edge->dst->decompress));
1691 set = isl_map_wrap(isl_map_remove_divs(map));
1692 coef = isl_set_coefficients(set);
1693 graph->inter_hmap = isl_map_to_basic_set_set(graph->inter_hmap, key,
1694 isl_basic_set_copy(coef));
1696 return coef;
1699 /* Return the position of the coefficients of the variables in
1700 * the coefficients constraints "coef".
1702 * The space of "coef" is of the form
1704 * { coefficients[[cst, params] -> S] }
1706 * Return the position of S.
1708 static int coef_var_offset(__isl_keep isl_basic_set *coef)
1710 int offset;
1711 isl_space *space;
1713 space = isl_space_unwrap(isl_basic_set_get_space(coef));
1714 offset = isl_space_dim(space, isl_dim_in);
1715 isl_space_free(space);
1717 return offset;
1720 /* Return the offset of the coefficient of the constant term of "node"
1721 * within the (I)LP.
1723 * Within each node, the coefficients have the following order:
1724 * - positive and negative parts of c_i_x
1725 * - c_i_n (if parametric)
1726 * - c_i_0
1728 static int node_cst_coef_offset(struct isl_sched_node *node)
1730 return node->start + 2 * node->nvar + node->nparam;
1733 /* Return the offset of the coefficients of the parameters of "node"
1734 * within the (I)LP.
1736 * Within each node, the coefficients have the following order:
1737 * - positive and negative parts of c_i_x
1738 * - c_i_n (if parametric)
1739 * - c_i_0
1741 static int node_par_coef_offset(struct isl_sched_node *node)
1743 return node->start + 2 * node->nvar;
1746 /* Return the offset of the coefficients of the variables of "node"
1747 * within the (I)LP.
1749 * Within each node, the coefficients have the following order:
1750 * - positive and negative parts of c_i_x
1751 * - c_i_n (if parametric)
1752 * - c_i_0
1754 static int node_var_coef_offset(struct isl_sched_node *node)
1756 return node->start;
1759 /* Return the position of the pair of variables encoding
1760 * coefficient "i" of "node".
1762 * The order of these variable pairs is the opposite of
1763 * that of the coefficients, with 2 variables per coefficient.
1765 static int node_var_coef_pos(struct isl_sched_node *node, int i)
1767 return node_var_coef_offset(node) + 2 * (node->nvar - 1 - i);
1770 /* Construct an isl_dim_map for mapping constraints on coefficients
1771 * for "node" to the corresponding positions in graph->lp.
1772 * "offset" is the offset of the coefficients for the variables
1773 * in the input constraints.
1774 * "s" is the sign of the mapping.
1776 * The input constraints are given in terms of the coefficients
1777 * (c_0, c_x) or (c_0, c_n, c_x).
1778 * The mapping produced by this function essentially plugs in
1779 * (0, c_i_x^+ - c_i_x^-) if s = 1 and
1780 * (0, -c_i_x^+ + c_i_x^-) if s = -1 or
1781 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1782 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1783 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1784 * Furthermore, the order of these pairs is the opposite of that
1785 * of the corresponding coefficients.
1787 * The caller can extend the mapping to also map the other coefficients
1788 * (and therefore not plug in 0).
1790 static __isl_give isl_dim_map *intra_dim_map(isl_ctx *ctx,
1791 struct isl_sched_graph *graph, struct isl_sched_node *node,
1792 int offset, int s)
1794 int pos;
1795 unsigned total;
1796 isl_dim_map *dim_map;
1798 if (!node || !graph->lp)
1799 return NULL;
1801 total = isl_basic_set_total_dim(graph->lp);
1802 pos = node_var_coef_pos(node, 0);
1803 dim_map = isl_dim_map_alloc(ctx, total);
1804 isl_dim_map_range(dim_map, pos, -2, offset, 1, node->nvar, -s);
1805 isl_dim_map_range(dim_map, pos + 1, -2, offset, 1, node->nvar, s);
1807 return dim_map;
1810 /* Construct an isl_dim_map for mapping constraints on coefficients
1811 * for "src" (node i) and "dst" (node j) to the corresponding positions
1812 * in graph->lp.
1813 * "offset" is the offset of the coefficients for the variables of "src"
1814 * in the input constraints.
1815 * "s" is the sign of the mapping.
1817 * The input constraints are given in terms of the coefficients
1818 * (c_0, c_n, c_x, c_y).
1819 * The mapping produced by this function essentially plugs in
1820 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1821 * -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-) if s = 1 and
1822 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1823 * c_i_x^+ - c_i_x^-, -(c_j_x^+ - c_j_x^-)) if s = -1.
1824 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1825 * Furthermore, the order of these pairs is the opposite of that
1826 * of the corresponding coefficients.
1828 * The caller can further extend the mapping.
1830 static __isl_give isl_dim_map *inter_dim_map(isl_ctx *ctx,
1831 struct isl_sched_graph *graph, struct isl_sched_node *src,
1832 struct isl_sched_node *dst, int offset, int s)
1834 int pos;
1835 unsigned total;
1836 isl_dim_map *dim_map;
1838 if (!src || !dst || !graph->lp)
1839 return NULL;
1841 total = isl_basic_set_total_dim(graph->lp);
1842 dim_map = isl_dim_map_alloc(ctx, total);
1844 pos = node_cst_coef_offset(dst);
1845 isl_dim_map_range(dim_map, pos, 0, 0, 0, 1, s);
1846 pos = node_par_coef_offset(dst);
1847 isl_dim_map_range(dim_map, pos, 1, 1, 1, dst->nparam, s);
1848 pos = node_var_coef_pos(dst, 0);
1849 isl_dim_map_range(dim_map, pos, -2, offset + src->nvar, 1,
1850 dst->nvar, -s);
1851 isl_dim_map_range(dim_map, pos + 1, -2, offset + src->nvar, 1,
1852 dst->nvar, s);
1854 pos = node_cst_coef_offset(src);
1855 isl_dim_map_range(dim_map, pos, 0, 0, 0, 1, -s);
1856 pos = node_par_coef_offset(src);
1857 isl_dim_map_range(dim_map, pos, 1, 1, 1, src->nparam, -s);
1858 pos = node_var_coef_pos(src, 0);
1859 isl_dim_map_range(dim_map, pos, -2, offset, 1, src->nvar, s);
1860 isl_dim_map_range(dim_map, pos + 1, -2, offset, 1, src->nvar, -s);
1862 return dim_map;
1865 /* Add the constraints from "src" to "dst" using "dim_map",
1866 * after making sure there is enough room in "dst" for the extra constraints.
1868 static __isl_give isl_basic_set *add_constraints_dim_map(
1869 __isl_take isl_basic_set *dst, __isl_take isl_basic_set *src,
1870 __isl_take isl_dim_map *dim_map)
1872 int n_eq, n_ineq;
1874 n_eq = isl_basic_set_n_equality(src);
1875 n_ineq = isl_basic_set_n_inequality(src);
1876 dst = isl_basic_set_extend_constraints(dst, n_eq, n_ineq);
1877 dst = isl_basic_set_add_constraints_dim_map(dst, src, dim_map);
1878 return dst;
1881 /* Add constraints to graph->lp that force validity for the given
1882 * dependence from a node i to itself.
1883 * That is, add constraints that enforce
1885 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1886 * = c_i_x (y - x) >= 0
1888 * for each (x,y) in R.
1889 * We obtain general constraints on coefficients (c_0, c_x)
1890 * of valid constraints for (y - x) and then plug in (0, c_i_x^+ - c_i_x^-),
1891 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1892 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1893 * Note that the result of intra_coefficients may also contain
1894 * parameter coefficients c_n, in which case 0 is plugged in for them as well.
1896 static isl_stat add_intra_validity_constraints(struct isl_sched_graph *graph,
1897 struct isl_sched_edge *edge)
1899 int offset;
1900 isl_map *map = isl_map_copy(edge->map);
1901 isl_ctx *ctx = isl_map_get_ctx(map);
1902 isl_dim_map *dim_map;
1903 isl_basic_set *coef;
1904 struct isl_sched_node *node = edge->src;
1906 coef = intra_coefficients(graph, node, map, 0);
1908 offset = coef_var_offset(coef);
1910 if (!coef)
1911 return isl_stat_error;
1913 dim_map = intra_dim_map(ctx, graph, node, offset, 1);
1914 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
1916 return isl_stat_ok;
1919 /* Add constraints to graph->lp that force validity for the given
1920 * dependence from node i to node j.
1921 * That is, add constraints that enforce
1923 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1925 * for each (x,y) in R.
1926 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1927 * of valid constraints for R and then plug in
1928 * (c_j_0 - c_i_0, c_j_n - c_i_n, -(c_i_x^+ - c_i_x^-), c_j_x^+ - c_j_x^-),
1929 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1930 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1932 static isl_stat add_inter_validity_constraints(struct isl_sched_graph *graph,
1933 struct isl_sched_edge *edge)
1935 int offset;
1936 isl_map *map;
1937 isl_ctx *ctx;
1938 isl_dim_map *dim_map;
1939 isl_basic_set *coef;
1940 struct isl_sched_node *src = edge->src;
1941 struct isl_sched_node *dst = edge->dst;
1943 if (!graph->lp)
1944 return isl_stat_error;
1946 map = isl_map_copy(edge->map);
1947 ctx = isl_map_get_ctx(map);
1948 coef = inter_coefficients(graph, edge, map);
1950 offset = coef_var_offset(coef);
1952 if (!coef)
1953 return isl_stat_error;
1955 dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1);
1957 edge->start = graph->lp->n_ineq;
1958 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
1959 if (!graph->lp)
1960 return isl_stat_error;
1961 edge->end = graph->lp->n_ineq;
1963 return isl_stat_ok;
1966 /* Add constraints to graph->lp that bound the dependence distance for the given
1967 * dependence from a node i to itself.
1968 * If s = 1, we add the constraint
1970 * c_i_x (y - x) <= m_0 + m_n n
1972 * or
1974 * -c_i_x (y - x) + m_0 + m_n n >= 0
1976 * for each (x,y) in R.
1977 * If s = -1, we add the constraint
1979 * -c_i_x (y - x) <= m_0 + m_n n
1981 * or
1983 * c_i_x (y - x) + m_0 + m_n n >= 0
1985 * for each (x,y) in R.
1986 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1987 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1988 * with each coefficient (except m_0) represented as a pair of non-negative
1989 * coefficients.
1992 * If "local" is set, then we add constraints
1994 * c_i_x (y - x) <= 0
1996 * or
1998 * -c_i_x (y - x) <= 0
2000 * instead, forcing the dependence distance to be (less than or) equal to 0.
2001 * That is, we plug in (0, 0, -s * c_i_x),
2002 * intra_coefficients is not required to have c_n in its result when
2003 * "local" is set. If they are missing, then (0, -s * c_i_x) is plugged in.
2004 * Note that dependences marked local are treated as validity constraints
2005 * by add_all_validity_constraints and therefore also have
2006 * their distances bounded by 0 from below.
2008 static isl_stat add_intra_proximity_constraints(struct isl_sched_graph *graph,
2009 struct isl_sched_edge *edge, int s, int local)
2011 int offset;
2012 unsigned nparam;
2013 isl_map *map = isl_map_copy(edge->map);
2014 isl_ctx *ctx = isl_map_get_ctx(map);
2015 isl_dim_map *dim_map;
2016 isl_basic_set *coef;
2017 struct isl_sched_node *node = edge->src;
2019 coef = intra_coefficients(graph, node, map, !local);
2021 offset = coef_var_offset(coef);
2023 if (!coef)
2024 return isl_stat_error;
2026 nparam = isl_space_dim(node->space, isl_dim_param);
2027 dim_map = intra_dim_map(ctx, graph, node, offset, -s);
2029 if (!local) {
2030 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
2031 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
2032 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
2034 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
2036 return isl_stat_ok;
2039 /* Add constraints to graph->lp that bound the dependence distance for the given
2040 * dependence from node i to node j.
2041 * If s = 1, we add the constraint
2043 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
2044 * <= m_0 + m_n n
2046 * or
2048 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
2049 * m_0 + m_n n >= 0
2051 * for each (x,y) in R.
2052 * If s = -1, we add the constraint
2054 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
2055 * <= m_0 + m_n n
2057 * or
2059 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
2060 * m_0 + m_n n >= 0
2062 * for each (x,y) in R.
2063 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
2064 * of valid constraints for R and then plug in
2065 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
2066 * s*c_i_x, -s*c_j_x)
2067 * with each coefficient (except m_0, c_*_0 and c_*_n)
2068 * represented as a pair of non-negative coefficients.
2071 * If "local" is set (and s = 1), then we add constraints
2073 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
2075 * or
2077 * -((c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x)) >= 0
2079 * instead, forcing the dependence distance to be (less than or) equal to 0.
2080 * That is, we plug in
2081 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, s*c_i_x, -s*c_j_x).
2082 * Note that dependences marked local are treated as validity constraints
2083 * by add_all_validity_constraints and therefore also have
2084 * their distances bounded by 0 from below.
2086 static isl_stat add_inter_proximity_constraints(struct isl_sched_graph *graph,
2087 struct isl_sched_edge *edge, int s, int local)
2089 int offset;
2090 unsigned nparam;
2091 isl_map *map = isl_map_copy(edge->map);
2092 isl_ctx *ctx = isl_map_get_ctx(map);
2093 isl_dim_map *dim_map;
2094 isl_basic_set *coef;
2095 struct isl_sched_node *src = edge->src;
2096 struct isl_sched_node *dst = edge->dst;
2098 coef = inter_coefficients(graph, edge, map);
2100 offset = coef_var_offset(coef);
2102 if (!coef)
2103 return isl_stat_error;
2105 nparam = isl_space_dim(src->space, isl_dim_param);
2106 dim_map = inter_dim_map(ctx, graph, src, dst, offset, -s);
2108 if (!local) {
2109 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
2110 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
2111 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
2114 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
2116 return isl_stat_ok;
2119 /* Should the distance over "edge" be forced to zero?
2120 * That is, is it marked as a local edge?
2121 * If "use_coincidence" is set, then coincidence edges are treated
2122 * as local edges.
2124 static int force_zero(struct isl_sched_edge *edge, int use_coincidence)
2126 return is_local(edge) || (use_coincidence && is_coincidence(edge));
2129 /* Add all validity constraints to graph->lp.
2131 * An edge that is forced to be local needs to have its dependence
2132 * distances equal to zero. We take care of bounding them by 0 from below
2133 * here. add_all_proximity_constraints takes care of bounding them by 0
2134 * from above.
2136 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2137 * Otherwise, we ignore them.
2139 static int add_all_validity_constraints(struct isl_sched_graph *graph,
2140 int use_coincidence)
2142 int i;
2144 for (i = 0; i < graph->n_edge; ++i) {
2145 struct isl_sched_edge *edge = &graph->edge[i];
2146 int zero;
2148 zero = force_zero(edge, use_coincidence);
2149 if (!is_validity(edge) && !zero)
2150 continue;
2151 if (edge->src != edge->dst)
2152 continue;
2153 if (add_intra_validity_constraints(graph, edge) < 0)
2154 return -1;
2157 for (i = 0; i < graph->n_edge; ++i) {
2158 struct isl_sched_edge *edge = &graph->edge[i];
2159 int zero;
2161 zero = force_zero(edge, use_coincidence);
2162 if (!is_validity(edge) && !zero)
2163 continue;
2164 if (edge->src == edge->dst)
2165 continue;
2166 if (add_inter_validity_constraints(graph, edge) < 0)
2167 return -1;
2170 return 0;
2173 /* Add constraints to graph->lp that bound the dependence distance
2174 * for all dependence relations.
2175 * If a given proximity dependence is identical to a validity
2176 * dependence, then the dependence distance is already bounded
2177 * from below (by zero), so we only need to bound the distance
2178 * from above. (This includes the case of "local" dependences
2179 * which are treated as validity dependence by add_all_validity_constraints.)
2180 * Otherwise, we need to bound the distance both from above and from below.
2182 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2183 * Otherwise, we ignore them.
2185 static int add_all_proximity_constraints(struct isl_sched_graph *graph,
2186 int use_coincidence)
2188 int i;
2190 for (i = 0; i < graph->n_edge; ++i) {
2191 struct isl_sched_edge *edge = &graph->edge[i];
2192 int zero;
2194 zero = force_zero(edge, use_coincidence);
2195 if (!is_proximity(edge) && !zero)
2196 continue;
2197 if (edge->src == edge->dst &&
2198 add_intra_proximity_constraints(graph, edge, 1, zero) < 0)
2199 return -1;
2200 if (edge->src != edge->dst &&
2201 add_inter_proximity_constraints(graph, edge, 1, zero) < 0)
2202 return -1;
2203 if (is_validity(edge) || zero)
2204 continue;
2205 if (edge->src == edge->dst &&
2206 add_intra_proximity_constraints(graph, edge, -1, 0) < 0)
2207 return -1;
2208 if (edge->src != edge->dst &&
2209 add_inter_proximity_constraints(graph, edge, -1, 0) < 0)
2210 return -1;
2213 return 0;
2216 /* Normalize the rows of "indep" such that all rows are lexicographically
2217 * positive and such that each row contains as many final zeros as possible,
2218 * given the choice for the previous rows.
2219 * Do this by performing elementary row operations.
2221 static __isl_give isl_mat *normalize_independent(__isl_take isl_mat *indep)
2223 indep = isl_mat_reverse_gauss(indep);
2224 indep = isl_mat_lexnonneg_rows(indep);
2225 return indep;
2228 /* Compute a basis for the rows in the linear part of the schedule
2229 * and extend this basis to a full basis. The remaining rows
2230 * can then be used to force linear independence from the rows
2231 * in the schedule.
2233 * In particular, given the schedule rows S, we compute
2235 * S = H Q
2236 * S U = H
2238 * with H the Hermite normal form of S. That is, all but the
2239 * first rank columns of H are zero and so each row in S is
2240 * a linear combination of the first rank rows of Q.
2241 * The matrix Q can be used as a variable transformation
2242 * that isolates the directions of S in the first rank rows.
2243 * Transposing S U = H yields
2245 * U^T S^T = H^T
2247 * with all but the first rank rows of H^T zero.
2248 * The last rows of U^T are therefore linear combinations
2249 * of schedule coefficients that are all zero on schedule
2250 * coefficients that are linearly dependent on the rows of S.
2251 * At least one of these combinations is non-zero on
2252 * linearly independent schedule coefficients.
2253 * The rows are normalized to involve as few of the last
2254 * coefficients as possible and to have a positive initial value.
2256 static int node_update_vmap(struct isl_sched_node *node)
2258 isl_mat *H, *U, *Q;
2259 int n_row = isl_mat_rows(node->sched);
2261 H = isl_mat_sub_alloc(node->sched, 0, n_row,
2262 1 + node->nparam, node->nvar);
2264 H = isl_mat_left_hermite(H, 0, &U, &Q);
2265 isl_mat_free(node->indep);
2266 isl_mat_free(node->vmap);
2267 node->vmap = Q;
2268 node->indep = isl_mat_transpose(U);
2269 node->rank = isl_mat_initial_non_zero_cols(H);
2270 node->indep = isl_mat_drop_rows(node->indep, 0, node->rank);
2271 node->indep = normalize_independent(node->indep);
2272 isl_mat_free(H);
2274 if (!node->indep || !node->vmap || node->rank < 0)
2275 return -1;
2276 return 0;
2279 /* Is "edge" marked as a validity or a conditional validity edge?
2281 static int is_any_validity(struct isl_sched_edge *edge)
2283 return is_validity(edge) || is_conditional_validity(edge);
2286 /* How many times should we count the constraints in "edge"?
2288 * We count as follows
2289 * validity -> 1 (>= 0)
2290 * validity+proximity -> 2 (>= 0 and upper bound)
2291 * proximity -> 2 (lower and upper bound)
2292 * local(+any) -> 2 (>= 0 and <= 0)
2294 * If an edge is only marked conditional_validity then it counts
2295 * as zero since it is only checked afterwards.
2297 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2298 * Otherwise, we ignore them.
2300 static int edge_multiplicity(struct isl_sched_edge *edge, int use_coincidence)
2302 if (is_proximity(edge) || force_zero(edge, use_coincidence))
2303 return 2;
2304 if (is_validity(edge))
2305 return 1;
2306 return 0;
2309 /* How many times should the constraints in "edge" be counted
2310 * as a parametric intra-node constraint?
2312 * Only proximity edges that are not forced zero need
2313 * coefficient constraints that include coefficients for parameters.
2314 * If the edge is also a validity edge, then only
2315 * an upper bound is introduced. Otherwise, both lower and upper bounds
2316 * are introduced.
2318 static int parametric_intra_edge_multiplicity(struct isl_sched_edge *edge,
2319 int use_coincidence)
2321 if (edge->src != edge->dst)
2322 return 0;
2323 if (!is_proximity(edge))
2324 return 0;
2325 if (force_zero(edge, use_coincidence))
2326 return 0;
2327 if (is_validity(edge))
2328 return 1;
2329 else
2330 return 2;
2333 /* Add "f" times the number of equality and inequality constraints of "bset"
2334 * to "n_eq" and "n_ineq" and free "bset".
2336 static isl_stat update_count(__isl_take isl_basic_set *bset,
2337 int f, int *n_eq, int *n_ineq)
2339 if (!bset)
2340 return isl_stat_error;
2342 *n_eq += isl_basic_set_n_equality(bset);
2343 *n_ineq += isl_basic_set_n_inequality(bset);
2344 isl_basic_set_free(bset);
2346 return isl_stat_ok;
2349 /* Count the number of equality and inequality constraints
2350 * that will be added for the given map.
2352 * The edges that require parameter coefficients are counted separately.
2354 * "use_coincidence" is set if we should take into account coincidence edges.
2356 static isl_stat count_map_constraints(struct isl_sched_graph *graph,
2357 struct isl_sched_edge *edge, __isl_take isl_map *map,
2358 int *n_eq, int *n_ineq, int use_coincidence)
2360 isl_map *copy;
2361 isl_basic_set *coef;
2362 int f = edge_multiplicity(edge, use_coincidence);
2363 int fp = parametric_intra_edge_multiplicity(edge, use_coincidence);
2365 if (f == 0) {
2366 isl_map_free(map);
2367 return isl_stat_ok;
2370 if (edge->src != edge->dst) {
2371 coef = inter_coefficients(graph, edge, map);
2372 return update_count(coef, f, n_eq, n_ineq);
2375 if (fp > 0) {
2376 copy = isl_map_copy(map);
2377 coef = intra_coefficients(graph, edge->src, copy, 1);
2378 if (update_count(coef, fp, n_eq, n_ineq) < 0)
2379 goto error;
2382 if (f > fp) {
2383 copy = isl_map_copy(map);
2384 coef = intra_coefficients(graph, edge->src, copy, 0);
2385 if (update_count(coef, f - fp, n_eq, n_ineq) < 0)
2386 goto error;
2389 isl_map_free(map);
2390 return isl_stat_ok;
2391 error:
2392 isl_map_free(map);
2393 return isl_stat_error;
2396 /* Count the number of equality and inequality constraints
2397 * that will be added to the main lp problem.
2398 * We count as follows
2399 * validity -> 1 (>= 0)
2400 * validity+proximity -> 2 (>= 0 and upper bound)
2401 * proximity -> 2 (lower and upper bound)
2402 * local(+any) -> 2 (>= 0 and <= 0)
2404 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2405 * Otherwise, we ignore them.
2407 static int count_constraints(struct isl_sched_graph *graph,
2408 int *n_eq, int *n_ineq, int use_coincidence)
2410 int i;
2412 *n_eq = *n_ineq = 0;
2413 for (i = 0; i < graph->n_edge; ++i) {
2414 struct isl_sched_edge *edge = &graph->edge[i];
2415 isl_map *map = isl_map_copy(edge->map);
2417 if (count_map_constraints(graph, edge, map, n_eq, n_ineq,
2418 use_coincidence) < 0)
2419 return -1;
2422 return 0;
2425 /* Count the number of constraints that will be added by
2426 * add_bound_constant_constraints to bound the values of the constant terms
2427 * and increment *n_eq and *n_ineq accordingly.
2429 * In practice, add_bound_constant_constraints only adds inequalities.
2431 static isl_stat count_bound_constant_constraints(isl_ctx *ctx,
2432 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2434 if (isl_options_get_schedule_max_constant_term(ctx) == -1)
2435 return isl_stat_ok;
2437 *n_ineq += graph->n;
2439 return isl_stat_ok;
2442 /* Add constraints to bound the values of the constant terms in the schedule,
2443 * if requested by the user.
2445 * The maximal value of the constant terms is defined by the option
2446 * "schedule_max_constant_term".
2448 static isl_stat add_bound_constant_constraints(isl_ctx *ctx,
2449 struct isl_sched_graph *graph)
2451 int i, k;
2452 int max;
2453 int total;
2455 max = isl_options_get_schedule_max_constant_term(ctx);
2456 if (max == -1)
2457 return isl_stat_ok;
2459 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2461 for (i = 0; i < graph->n; ++i) {
2462 struct isl_sched_node *node = &graph->node[i];
2463 int pos;
2465 k = isl_basic_set_alloc_inequality(graph->lp);
2466 if (k < 0)
2467 return isl_stat_error;
2468 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2469 pos = node_cst_coef_offset(node);
2470 isl_int_set_si(graph->lp->ineq[k][1 + pos], -1);
2471 isl_int_set_si(graph->lp->ineq[k][0], max);
2474 return isl_stat_ok;
2477 /* Count the number of constraints that will be added by
2478 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2479 * accordingly.
2481 * In practice, add_bound_coefficient_constraints only adds inequalities.
2483 static int count_bound_coefficient_constraints(isl_ctx *ctx,
2484 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2486 int i;
2488 if (isl_options_get_schedule_max_coefficient(ctx) == -1 &&
2489 !isl_options_get_schedule_treat_coalescing(ctx))
2490 return 0;
2492 for (i = 0; i < graph->n; ++i)
2493 *n_ineq += graph->node[i].nparam + 2 * graph->node[i].nvar;
2495 return 0;
2498 /* Add constraints to graph->lp that bound the values of
2499 * the parameter schedule coefficients of "node" to "max" and
2500 * the variable schedule coefficients to the corresponding entry
2501 * in node->max.
2502 * In either case, a negative value means that no bound needs to be imposed.
2504 * For parameter coefficients, this amounts to adding a constraint
2506 * c_n <= max
2508 * i.e.,
2510 * -c_n + max >= 0
2512 * The variables coefficients are, however, not represented directly.
2513 * Instead, the variable coefficients c_x are written as differences
2514 * c_x = c_x^+ - c_x^-.
2515 * That is,
2517 * -max_i <= c_x_i <= max_i
2519 * is encoded as
2521 * -max_i <= c_x_i^+ - c_x_i^- <= max_i
2523 * or
2525 * -(c_x_i^+ - c_x_i^-) + max_i >= 0
2526 * c_x_i^+ - c_x_i^- + max_i >= 0
2528 static isl_stat node_add_coefficient_constraints(isl_ctx *ctx,
2529 struct isl_sched_graph *graph, struct isl_sched_node *node, int max)
2531 int i, j, k;
2532 int total;
2533 isl_vec *ineq;
2535 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2537 for (j = 0; j < node->nparam; ++j) {
2538 int dim;
2540 if (max < 0)
2541 continue;
2543 k = isl_basic_set_alloc_inequality(graph->lp);
2544 if (k < 0)
2545 return isl_stat_error;
2546 dim = 1 + node_par_coef_offset(node) + j;
2547 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2548 isl_int_set_si(graph->lp->ineq[k][dim], -1);
2549 isl_int_set_si(graph->lp->ineq[k][0], max);
2552 ineq = isl_vec_alloc(ctx, 1 + total);
2553 ineq = isl_vec_clr(ineq);
2554 if (!ineq)
2555 return isl_stat_error;
2556 for (i = 0; i < node->nvar; ++i) {
2557 int pos = 1 + node_var_coef_pos(node, i);
2559 if (isl_int_is_neg(node->max->el[i]))
2560 continue;
2562 isl_int_set_si(ineq->el[pos], 1);
2563 isl_int_set_si(ineq->el[pos + 1], -1);
2564 isl_int_set(ineq->el[0], node->max->el[i]);
2566 k = isl_basic_set_alloc_inequality(graph->lp);
2567 if (k < 0)
2568 goto error;
2569 isl_seq_cpy(graph->lp->ineq[k], ineq->el, 1 + total);
2571 isl_seq_neg(ineq->el + pos, ineq->el + pos, 2);
2572 k = isl_basic_set_alloc_inequality(graph->lp);
2573 if (k < 0)
2574 goto error;
2575 isl_seq_cpy(graph->lp->ineq[k], ineq->el, 1 + total);
2577 isl_seq_clr(ineq->el + pos, 2);
2579 isl_vec_free(ineq);
2581 return isl_stat_ok;
2582 error:
2583 isl_vec_free(ineq);
2584 return isl_stat_error;
2587 /* Add constraints that bound the values of the variable and parameter
2588 * coefficients of the schedule.
2590 * The maximal value of the coefficients is defined by the option
2591 * 'schedule_max_coefficient' and the entries in node->max.
2592 * These latter entries are only set if either the schedule_max_coefficient
2593 * option or the schedule_treat_coalescing option is set.
2595 static isl_stat add_bound_coefficient_constraints(isl_ctx *ctx,
2596 struct isl_sched_graph *graph)
2598 int i;
2599 int max;
2601 max = isl_options_get_schedule_max_coefficient(ctx);
2603 if (max == -1 && !isl_options_get_schedule_treat_coalescing(ctx))
2604 return isl_stat_ok;
2606 for (i = 0; i < graph->n; ++i) {
2607 struct isl_sched_node *node = &graph->node[i];
2609 if (node_add_coefficient_constraints(ctx, graph, node, max) < 0)
2610 return isl_stat_error;
2613 return isl_stat_ok;
2616 /* Add a constraint to graph->lp that equates the value at position
2617 * "sum_pos" to the sum of the "n" values starting at "first".
2619 static isl_stat add_sum_constraint(struct isl_sched_graph *graph,
2620 int sum_pos, int first, int n)
2622 int i, k;
2623 int total;
2625 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2627 k = isl_basic_set_alloc_equality(graph->lp);
2628 if (k < 0)
2629 return isl_stat_error;
2630 isl_seq_clr(graph->lp->eq[k], 1 + total);
2631 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1);
2632 for (i = 0; i < n; ++i)
2633 isl_int_set_si(graph->lp->eq[k][1 + first + i], 1);
2635 return isl_stat_ok;
2638 /* Add a constraint to graph->lp that equates the value at position
2639 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2641 static isl_stat add_param_sum_constraint(struct isl_sched_graph *graph,
2642 int sum_pos)
2644 int i, j, k;
2645 int total;
2647 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2649 k = isl_basic_set_alloc_equality(graph->lp);
2650 if (k < 0)
2651 return isl_stat_error;
2652 isl_seq_clr(graph->lp->eq[k], 1 + total);
2653 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1);
2654 for (i = 0; i < graph->n; ++i) {
2655 int pos = 1 + node_par_coef_offset(&graph->node[i]);
2657 for (j = 0; j < graph->node[i].nparam; ++j)
2658 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2661 return isl_stat_ok;
2664 /* Add a constraint to graph->lp that equates the value at position
2665 * "sum_pos" to the sum of the variable coefficients of all nodes.
2667 static isl_stat add_var_sum_constraint(struct isl_sched_graph *graph,
2668 int sum_pos)
2670 int i, j, k;
2671 int total;
2673 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2675 k = isl_basic_set_alloc_equality(graph->lp);
2676 if (k < 0)
2677 return isl_stat_error;
2678 isl_seq_clr(graph->lp->eq[k], 1 + total);
2679 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1);
2680 for (i = 0; i < graph->n; ++i) {
2681 struct isl_sched_node *node = &graph->node[i];
2682 int pos = 1 + node_var_coef_offset(node);
2684 for (j = 0; j < 2 * node->nvar; ++j)
2685 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2688 return isl_stat_ok;
2691 /* Construct an ILP problem for finding schedule coefficients
2692 * that result in non-negative, but small dependence distances
2693 * over all dependences.
2694 * In particular, the dependence distances over proximity edges
2695 * are bounded by m_0 + m_n n and we compute schedule coefficients
2696 * with small values (preferably zero) of m_n and m_0.
2698 * All variables of the ILP are non-negative. The actual coefficients
2699 * may be negative, so each coefficient is represented as the difference
2700 * of two non-negative variables. The negative part always appears
2701 * immediately before the positive part.
2702 * Other than that, the variables have the following order
2704 * - sum of positive and negative parts of m_n coefficients
2705 * - m_0
2706 * - sum of all c_n coefficients
2707 * (unconstrained when computing non-parametric schedules)
2708 * - sum of positive and negative parts of all c_x coefficients
2709 * - positive and negative parts of m_n coefficients
2710 * - for each node
2711 * - positive and negative parts of c_i_x, in opposite order
2712 * - c_i_n (if parametric)
2713 * - c_i_0
2715 * The constraints are those from the edges plus two or three equalities
2716 * to express the sums.
2718 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2719 * Otherwise, we ignore them.
2721 static isl_stat setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
2722 int use_coincidence)
2724 int i;
2725 unsigned nparam;
2726 unsigned total;
2727 isl_space *space;
2728 int parametric;
2729 int param_pos;
2730 int n_eq, n_ineq;
2732 parametric = ctx->opt->schedule_parametric;
2733 nparam = isl_space_dim(graph->node[0].space, isl_dim_param);
2734 param_pos = 4;
2735 total = param_pos + 2 * nparam;
2736 for (i = 0; i < graph->n; ++i) {
2737 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2738 if (node_update_vmap(node) < 0)
2739 return isl_stat_error;
2740 node->start = total;
2741 total += 1 + node->nparam + 2 * node->nvar;
2744 if (count_constraints(graph, &n_eq, &n_ineq, use_coincidence) < 0)
2745 return isl_stat_error;
2746 if (count_bound_constant_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2747 return isl_stat_error;
2748 if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2749 return isl_stat_error;
2751 space = isl_space_set_alloc(ctx, 0, total);
2752 isl_basic_set_free(graph->lp);
2753 n_eq += 2 + parametric;
2755 graph->lp = isl_basic_set_alloc_space(space, 0, n_eq, n_ineq);
2757 if (add_sum_constraint(graph, 0, param_pos, 2 * nparam) < 0)
2758 return isl_stat_error;
2759 if (parametric && add_param_sum_constraint(graph, 2) < 0)
2760 return isl_stat_error;
2761 if (add_var_sum_constraint(graph, 3) < 0)
2762 return isl_stat_error;
2763 if (add_bound_constant_constraints(ctx, graph) < 0)
2764 return isl_stat_error;
2765 if (add_bound_coefficient_constraints(ctx, graph) < 0)
2766 return isl_stat_error;
2767 if (add_all_validity_constraints(graph, use_coincidence) < 0)
2768 return isl_stat_error;
2769 if (add_all_proximity_constraints(graph, use_coincidence) < 0)
2770 return isl_stat_error;
2772 return isl_stat_ok;
2775 /* Analyze the conflicting constraint found by
2776 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2777 * constraint of one of the edges between distinct nodes, living, moreover
2778 * in distinct SCCs, then record the source and sink SCC as this may
2779 * be a good place to cut between SCCs.
2781 static int check_conflict(int con, void *user)
2783 int i;
2784 struct isl_sched_graph *graph = user;
2786 if (graph->src_scc >= 0)
2787 return 0;
2789 con -= graph->lp->n_eq;
2791 if (con >= graph->lp->n_ineq)
2792 return 0;
2794 for (i = 0; i < graph->n_edge; ++i) {
2795 if (!is_validity(&graph->edge[i]))
2796 continue;
2797 if (graph->edge[i].src == graph->edge[i].dst)
2798 continue;
2799 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
2800 continue;
2801 if (graph->edge[i].start > con)
2802 continue;
2803 if (graph->edge[i].end <= con)
2804 continue;
2805 graph->src_scc = graph->edge[i].src->scc;
2806 graph->dst_scc = graph->edge[i].dst->scc;
2809 return 0;
2812 /* Check whether the next schedule row of the given node needs to be
2813 * non-trivial. Lower-dimensional domains may have some trivial rows,
2814 * but as soon as the number of remaining required non-trivial rows
2815 * is as large as the number or remaining rows to be computed,
2816 * all remaining rows need to be non-trivial.
2818 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
2820 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
2823 /* Construct a non-triviality region with triviality directions
2824 * corresponding to the rows of "indep".
2825 * The rows of "indep" are expressed in terms of the schedule coefficients c_i,
2826 * while the triviality directions are expressed in terms of
2827 * pairs of non-negative variables c^+_i - c^-_i, with c^-_i appearing
2828 * before c^+_i. Furthermore,
2829 * the pairs of non-negative variables representing the coefficients
2830 * are stored in the opposite order.
2832 static __isl_give isl_mat *construct_trivial(__isl_keep isl_mat *indep)
2834 isl_ctx *ctx;
2835 isl_mat *mat;
2836 int i, j, n, n_var;
2838 if (!indep)
2839 return NULL;
2841 ctx = isl_mat_get_ctx(indep);
2842 n = isl_mat_rows(indep);
2843 n_var = isl_mat_cols(indep);
2844 mat = isl_mat_alloc(ctx, n, 2 * n_var);
2845 if (!mat)
2846 return NULL;
2847 for (i = 0; i < n; ++i) {
2848 for (j = 0; j < n_var; ++j) {
2849 int nj = n_var - 1 - j;
2850 isl_int_neg(mat->row[i][2 * nj], indep->row[i][j]);
2851 isl_int_set(mat->row[i][2 * nj + 1], indep->row[i][j]);
2855 return mat;
2858 /* Solve the ILP problem constructed in setup_lp.
2859 * For each node such that all the remaining rows of its schedule
2860 * need to be non-trivial, we construct a non-triviality region.
2861 * This region imposes that the next row is independent of previous rows.
2862 * In particular, the non-triviality region enforces that at least
2863 * one of the linear combinations in the rows of node->indep is non-zero.
2865 static __isl_give isl_vec *solve_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2867 int i;
2868 isl_vec *sol;
2869 isl_basic_set *lp;
2871 for (i = 0; i < graph->n; ++i) {
2872 struct isl_sched_node *node = &graph->node[i];
2873 isl_mat *trivial;
2875 graph->region[i].pos = node_var_coef_offset(node);
2876 if (needs_row(graph, node))
2877 trivial = construct_trivial(node->indep);
2878 else
2879 trivial = isl_mat_zero(ctx, 0, 0);
2880 graph->region[i].trivial = trivial;
2882 lp = isl_basic_set_copy(graph->lp);
2883 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
2884 graph->region, &check_conflict, graph);
2885 for (i = 0; i < graph->n; ++i)
2886 isl_mat_free(graph->region[i].trivial);
2887 return sol;
2890 /* Extract the coefficients for the variables of "node" from "sol".
2892 * Each schedule coefficient c_i_x is represented as the difference
2893 * between two non-negative variables c_i_x^+ - c_i_x^-.
2894 * The c_i_x^- appear before their c_i_x^+ counterpart.
2895 * Furthermore, the order of these pairs is the opposite of that
2896 * of the corresponding coefficients.
2898 * Return c_i_x = c_i_x^+ - c_i_x^-
2900 static __isl_give isl_vec *extract_var_coef(struct isl_sched_node *node,
2901 __isl_keep isl_vec *sol)
2903 int i;
2904 int pos;
2905 isl_vec *csol;
2907 if (!sol)
2908 return NULL;
2909 csol = isl_vec_alloc(isl_vec_get_ctx(sol), node->nvar);
2910 if (!csol)
2911 return NULL;
2913 pos = 1 + node_var_coef_offset(node);
2914 for (i = 0; i < node->nvar; ++i)
2915 isl_int_sub(csol->el[node->nvar - 1 - i],
2916 sol->el[pos + 2 * i + 1], sol->el[pos + 2 * i]);
2918 return csol;
2921 /* Update the schedules of all nodes based on the given solution
2922 * of the LP problem.
2923 * The new row is added to the current band.
2924 * All possibly negative coefficients are encoded as a difference
2925 * of two non-negative variables, so we need to perform the subtraction
2926 * here.
2928 * If coincident is set, then the caller guarantees that the new
2929 * row satisfies the coincidence constraints.
2931 static int update_schedule(struct isl_sched_graph *graph,
2932 __isl_take isl_vec *sol, int coincident)
2934 int i, j;
2935 isl_vec *csol = NULL;
2937 if (!sol)
2938 goto error;
2939 if (sol->size == 0)
2940 isl_die(sol->ctx, isl_error_internal,
2941 "no solution found", goto error);
2942 if (graph->n_total_row >= graph->max_row)
2943 isl_die(sol->ctx, isl_error_internal,
2944 "too many schedule rows", goto error);
2946 for (i = 0; i < graph->n; ++i) {
2947 struct isl_sched_node *node = &graph->node[i];
2948 int pos;
2949 int row = isl_mat_rows(node->sched);
2951 isl_vec_free(csol);
2952 csol = extract_var_coef(node, sol);
2953 if (!csol)
2954 goto error;
2956 isl_map_free(node->sched_map);
2957 node->sched_map = NULL;
2958 node->sched = isl_mat_add_rows(node->sched, 1);
2959 if (!node->sched)
2960 goto error;
2961 pos = node_cst_coef_offset(node);
2962 node->sched = isl_mat_set_element(node->sched,
2963 row, 0, sol->el[1 + pos]);
2964 pos = node_par_coef_offset(node);
2965 for (j = 0; j < node->nparam; ++j)
2966 node->sched = isl_mat_set_element(node->sched,
2967 row, 1 + j, sol->el[1 + pos + j]);
2968 for (j = 0; j < node->nvar; ++j)
2969 node->sched = isl_mat_set_element(node->sched,
2970 row, 1 + node->nparam + j, csol->el[j]);
2971 node->coincident[graph->n_total_row] = coincident;
2973 isl_vec_free(sol);
2974 isl_vec_free(csol);
2976 graph->n_row++;
2977 graph->n_total_row++;
2979 return 0;
2980 error:
2981 isl_vec_free(sol);
2982 isl_vec_free(csol);
2983 return -1;
2986 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2987 * and return this isl_aff.
2989 static __isl_give isl_aff *extract_schedule_row(__isl_take isl_local_space *ls,
2990 struct isl_sched_node *node, int row)
2992 int j;
2993 isl_int v;
2994 isl_aff *aff;
2996 isl_int_init(v);
2998 aff = isl_aff_zero_on_domain(ls);
2999 if (isl_mat_get_element(node->sched, row, 0, &v) < 0)
3000 goto error;
3001 aff = isl_aff_set_constant(aff, v);
3002 for (j = 0; j < node->nparam; ++j) {
3003 if (isl_mat_get_element(node->sched, row, 1 + j, &v) < 0)
3004 goto error;
3005 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
3007 for (j = 0; j < node->nvar; ++j) {
3008 if (isl_mat_get_element(node->sched, row,
3009 1 + node->nparam + j, &v) < 0)
3010 goto error;
3011 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
3014 isl_int_clear(v);
3016 return aff;
3017 error:
3018 isl_int_clear(v);
3019 isl_aff_free(aff);
3020 return NULL;
3023 /* Convert the "n" rows starting at "first" of node->sched into a multi_aff
3024 * and return this multi_aff.
3026 * The result is defined over the uncompressed node domain.
3028 static __isl_give isl_multi_aff *node_extract_partial_schedule_multi_aff(
3029 struct isl_sched_node *node, int first, int n)
3031 int i;
3032 isl_space *space;
3033 isl_local_space *ls;
3034 isl_aff *aff;
3035 isl_multi_aff *ma;
3036 int nrow;
3038 if (!node)
3039 return NULL;
3040 nrow = isl_mat_rows(node->sched);
3041 if (node->compressed)
3042 space = isl_multi_aff_get_domain_space(node->decompress);
3043 else
3044 space = isl_space_copy(node->space);
3045 ls = isl_local_space_from_space(isl_space_copy(space));
3046 space = isl_space_from_domain(space);
3047 space = isl_space_add_dims(space, isl_dim_out, n);
3048 ma = isl_multi_aff_zero(space);
3050 for (i = first; i < first + n; ++i) {
3051 aff = extract_schedule_row(isl_local_space_copy(ls), node, i);
3052 ma = isl_multi_aff_set_aff(ma, i - first, aff);
3055 isl_local_space_free(ls);
3057 if (node->compressed)
3058 ma = isl_multi_aff_pullback_multi_aff(ma,
3059 isl_multi_aff_copy(node->compress));
3061 return ma;
3064 /* Convert node->sched into a multi_aff and return this multi_aff.
3066 * The result is defined over the uncompressed node domain.
3068 static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
3069 struct isl_sched_node *node)
3071 int nrow;
3073 nrow = isl_mat_rows(node->sched);
3074 return node_extract_partial_schedule_multi_aff(node, 0, nrow);
3077 /* Convert node->sched into a map and return this map.
3079 * The result is cached in node->sched_map, which needs to be released
3080 * whenever node->sched is updated.
3081 * It is defined over the uncompressed node domain.
3083 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
3085 if (!node->sched_map) {
3086 isl_multi_aff *ma;
3088 ma = node_extract_schedule_multi_aff(node);
3089 node->sched_map = isl_map_from_multi_aff(ma);
3092 return isl_map_copy(node->sched_map);
3095 /* Construct a map that can be used to update a dependence relation
3096 * based on the current schedule.
3097 * That is, construct a map expressing that source and sink
3098 * are executed within the same iteration of the current schedule.
3099 * This map can then be intersected with the dependence relation.
3100 * This is not the most efficient way, but this shouldn't be a critical
3101 * operation.
3103 static __isl_give isl_map *specializer(struct isl_sched_node *src,
3104 struct isl_sched_node *dst)
3106 isl_map *src_sched, *dst_sched;
3108 src_sched = node_extract_schedule(src);
3109 dst_sched = node_extract_schedule(dst);
3110 return isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
3113 /* Intersect the domains of the nested relations in domain and range
3114 * of "umap" with "map".
3116 static __isl_give isl_union_map *intersect_domains(
3117 __isl_take isl_union_map *umap, __isl_keep isl_map *map)
3119 isl_union_set *uset;
3121 umap = isl_union_map_zip(umap);
3122 uset = isl_union_set_from_set(isl_map_wrap(isl_map_copy(map)));
3123 umap = isl_union_map_intersect_domain(umap, uset);
3124 umap = isl_union_map_zip(umap);
3125 return umap;
3128 /* Update the dependence relation of the given edge based
3129 * on the current schedule.
3130 * If the dependence is carried completely by the current schedule, then
3131 * it is removed from the edge_tables. It is kept in the list of edges
3132 * as otherwise all edge_tables would have to be recomputed.
3134 * If the edge is of a type that can appear multiple times
3135 * between the same pair of nodes, then it is added to
3136 * the edge table (again). This prevents the situation
3137 * where none of these edges is referenced from the edge table
3138 * because the one that was referenced turned out to be empty and
3139 * was therefore removed from the table.
3141 static int update_edge(isl_ctx *ctx, struct isl_sched_graph *graph,
3142 struct isl_sched_edge *edge)
3144 int empty;
3145 isl_map *id;
3147 id = specializer(edge->src, edge->dst);
3148 edge->map = isl_map_intersect(edge->map, isl_map_copy(id));
3149 if (!edge->map)
3150 goto error;
3152 if (edge->tagged_condition) {
3153 edge->tagged_condition =
3154 intersect_domains(edge->tagged_condition, id);
3155 if (!edge->tagged_condition)
3156 goto error;
3158 if (edge->tagged_validity) {
3159 edge->tagged_validity =
3160 intersect_domains(edge->tagged_validity, id);
3161 if (!edge->tagged_validity)
3162 goto error;
3165 empty = isl_map_plain_is_empty(edge->map);
3166 if (empty < 0)
3167 goto error;
3168 if (empty) {
3169 graph_remove_edge(graph, edge);
3170 } else if (is_multi_edge_type(edge)) {
3171 if (graph_edge_tables_add(ctx, graph, edge) < 0)
3172 goto error;
3175 isl_map_free(id);
3176 return 0;
3177 error:
3178 isl_map_free(id);
3179 return -1;
3182 /* Does the domain of "umap" intersect "uset"?
3184 static int domain_intersects(__isl_keep isl_union_map *umap,
3185 __isl_keep isl_union_set *uset)
3187 int empty;
3189 umap = isl_union_map_copy(umap);
3190 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(uset));
3191 empty = isl_union_map_is_empty(umap);
3192 isl_union_map_free(umap);
3194 return empty < 0 ? -1 : !empty;
3197 /* Does the range of "umap" intersect "uset"?
3199 static int range_intersects(__isl_keep isl_union_map *umap,
3200 __isl_keep isl_union_set *uset)
3202 int empty;
3204 umap = isl_union_map_copy(umap);
3205 umap = isl_union_map_intersect_range(umap, isl_union_set_copy(uset));
3206 empty = isl_union_map_is_empty(umap);
3207 isl_union_map_free(umap);
3209 return empty < 0 ? -1 : !empty;
3212 /* Are the condition dependences of "edge" local with respect to
3213 * the current schedule?
3215 * That is, are domain and range of the condition dependences mapped
3216 * to the same point?
3218 * In other words, is the condition false?
3220 static int is_condition_false(struct isl_sched_edge *edge)
3222 isl_union_map *umap;
3223 isl_map *map, *sched, *test;
3224 int empty, local;
3226 empty = isl_union_map_is_empty(edge->tagged_condition);
3227 if (empty < 0 || empty)
3228 return empty;
3230 umap = isl_union_map_copy(edge->tagged_condition);
3231 umap = isl_union_map_zip(umap);
3232 umap = isl_union_set_unwrap(isl_union_map_domain(umap));
3233 map = isl_map_from_union_map(umap);
3235 sched = node_extract_schedule(edge->src);
3236 map = isl_map_apply_domain(map, sched);
3237 sched = node_extract_schedule(edge->dst);
3238 map = isl_map_apply_range(map, sched);
3240 test = isl_map_identity(isl_map_get_space(map));
3241 local = isl_map_is_subset(map, test);
3242 isl_map_free(map);
3243 isl_map_free(test);
3245 return local;
3248 /* For each conditional validity constraint that is adjacent
3249 * to a condition with domain in condition_source or range in condition_sink,
3250 * turn it into an unconditional validity constraint.
3252 static int unconditionalize_adjacent_validity(struct isl_sched_graph *graph,
3253 __isl_take isl_union_set *condition_source,
3254 __isl_take isl_union_set *condition_sink)
3256 int i;
3258 condition_source = isl_union_set_coalesce(condition_source);
3259 condition_sink = isl_union_set_coalesce(condition_sink);
3261 for (i = 0; i < graph->n_edge; ++i) {
3262 int adjacent;
3263 isl_union_map *validity;
3265 if (!is_conditional_validity(&graph->edge[i]))
3266 continue;
3267 if (is_validity(&graph->edge[i]))
3268 continue;
3270 validity = graph->edge[i].tagged_validity;
3271 adjacent = domain_intersects(validity, condition_sink);
3272 if (adjacent >= 0 && !adjacent)
3273 adjacent = range_intersects(validity, condition_source);
3274 if (adjacent < 0)
3275 goto error;
3276 if (!adjacent)
3277 continue;
3279 set_validity(&graph->edge[i]);
3282 isl_union_set_free(condition_source);
3283 isl_union_set_free(condition_sink);
3284 return 0;
3285 error:
3286 isl_union_set_free(condition_source);
3287 isl_union_set_free(condition_sink);
3288 return -1;
3291 /* Update the dependence relations of all edges based on the current schedule
3292 * and enforce conditional validity constraints that are adjacent
3293 * to satisfied condition constraints.
3295 * First check if any of the condition constraints are satisfied
3296 * (i.e., not local to the outer schedule) and keep track of
3297 * their domain and range.
3298 * Then update all dependence relations (which removes the non-local
3299 * constraints).
3300 * Finally, if any condition constraints turned out to be satisfied,
3301 * then turn all adjacent conditional validity constraints into
3302 * unconditional validity constraints.
3304 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
3306 int i;
3307 int any = 0;
3308 isl_union_set *source, *sink;
3310 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3311 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3312 for (i = 0; i < graph->n_edge; ++i) {
3313 int local;
3314 isl_union_set *uset;
3315 isl_union_map *umap;
3317 if (!is_condition(&graph->edge[i]))
3318 continue;
3319 if (is_local(&graph->edge[i]))
3320 continue;
3321 local = is_condition_false(&graph->edge[i]);
3322 if (local < 0)
3323 goto error;
3324 if (local)
3325 continue;
3327 any = 1;
3329 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
3330 uset = isl_union_map_domain(umap);
3331 source = isl_union_set_union(source, uset);
3333 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
3334 uset = isl_union_map_range(umap);
3335 sink = isl_union_set_union(sink, uset);
3338 for (i = 0; i < graph->n_edge; ++i) {
3339 if (update_edge(ctx, graph, &graph->edge[i]) < 0)
3340 goto error;
3343 if (any)
3344 return unconditionalize_adjacent_validity(graph, source, sink);
3346 isl_union_set_free(source);
3347 isl_union_set_free(sink);
3348 return 0;
3349 error:
3350 isl_union_set_free(source);
3351 isl_union_set_free(sink);
3352 return -1;
3355 static void next_band(struct isl_sched_graph *graph)
3357 graph->band_start = graph->n_total_row;
3360 /* Return the union of the universe domains of the nodes in "graph"
3361 * that satisfy "pred".
3363 static __isl_give isl_union_set *isl_sched_graph_domain(isl_ctx *ctx,
3364 struct isl_sched_graph *graph,
3365 int (*pred)(struct isl_sched_node *node, int data), int data)
3367 int i;
3368 isl_set *set;
3369 isl_union_set *dom;
3371 for (i = 0; i < graph->n; ++i)
3372 if (pred(&graph->node[i], data))
3373 break;
3375 if (i >= graph->n)
3376 isl_die(ctx, isl_error_internal,
3377 "empty component", return NULL);
3379 set = isl_set_universe(isl_space_copy(graph->node[i].space));
3380 dom = isl_union_set_from_set(set);
3382 for (i = i + 1; i < graph->n; ++i) {
3383 if (!pred(&graph->node[i], data))
3384 continue;
3385 set = isl_set_universe(isl_space_copy(graph->node[i].space));
3386 dom = isl_union_set_union(dom, isl_union_set_from_set(set));
3389 return dom;
3392 /* Return a list of unions of universe domains, where each element
3393 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3395 static __isl_give isl_union_set_list *extract_sccs(isl_ctx *ctx,
3396 struct isl_sched_graph *graph)
3398 int i;
3399 isl_union_set_list *filters;
3401 filters = isl_union_set_list_alloc(ctx, graph->scc);
3402 for (i = 0; i < graph->scc; ++i) {
3403 isl_union_set *dom;
3405 dom = isl_sched_graph_domain(ctx, graph, &node_scc_exactly, i);
3406 filters = isl_union_set_list_add(filters, dom);
3409 return filters;
3412 /* Return a list of two unions of universe domains, one for the SCCs up
3413 * to and including graph->src_scc and another for the other SCCs.
3415 static __isl_give isl_union_set_list *extract_split(isl_ctx *ctx,
3416 struct isl_sched_graph *graph)
3418 isl_union_set *dom;
3419 isl_union_set_list *filters;
3421 filters = isl_union_set_list_alloc(ctx, 2);
3422 dom = isl_sched_graph_domain(ctx, graph,
3423 &node_scc_at_most, graph->src_scc);
3424 filters = isl_union_set_list_add(filters, dom);
3425 dom = isl_sched_graph_domain(ctx, graph,
3426 &node_scc_at_least, graph->src_scc + 1);
3427 filters = isl_union_set_list_add(filters, dom);
3429 return filters;
3432 /* Copy nodes that satisfy node_pred from the src dependence graph
3433 * to the dst dependence graph.
3435 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
3436 int (*node_pred)(struct isl_sched_node *node, int data), int data)
3438 int i;
3440 dst->n = 0;
3441 for (i = 0; i < src->n; ++i) {
3442 int j;
3444 if (!node_pred(&src->node[i], data))
3445 continue;
3447 j = dst->n;
3448 dst->node[j].space = isl_space_copy(src->node[i].space);
3449 dst->node[j].compressed = src->node[i].compressed;
3450 dst->node[j].hull = isl_set_copy(src->node[i].hull);
3451 dst->node[j].compress =
3452 isl_multi_aff_copy(src->node[i].compress);
3453 dst->node[j].decompress =
3454 isl_multi_aff_copy(src->node[i].decompress);
3455 dst->node[j].nvar = src->node[i].nvar;
3456 dst->node[j].nparam = src->node[i].nparam;
3457 dst->node[j].sched = isl_mat_copy(src->node[i].sched);
3458 dst->node[j].sched_map = isl_map_copy(src->node[i].sched_map);
3459 dst->node[j].coincident = src->node[i].coincident;
3460 dst->node[j].sizes = isl_multi_val_copy(src->node[i].sizes);
3461 dst->node[j].bounds = isl_basic_set_copy(src->node[i].bounds);
3462 dst->node[j].max = isl_vec_copy(src->node[i].max);
3463 dst->n++;
3465 if (!dst->node[j].space || !dst->node[j].sched)
3466 return -1;
3467 if (dst->node[j].compressed &&
3468 (!dst->node[j].hull || !dst->node[j].compress ||
3469 !dst->node[j].decompress))
3470 return -1;
3473 return 0;
3476 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3477 * to the dst dependence graph.
3478 * If the source or destination node of the edge is not in the destination
3479 * graph, then it must be a backward proximity edge and it should simply
3480 * be ignored.
3482 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
3483 struct isl_sched_graph *src,
3484 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
3486 int i;
3488 dst->n_edge = 0;
3489 for (i = 0; i < src->n_edge; ++i) {
3490 struct isl_sched_edge *edge = &src->edge[i];
3491 isl_map *map;
3492 isl_union_map *tagged_condition;
3493 isl_union_map *tagged_validity;
3494 struct isl_sched_node *dst_src, *dst_dst;
3496 if (!edge_pred(edge, data))
3497 continue;
3499 if (isl_map_plain_is_empty(edge->map))
3500 continue;
3502 dst_src = graph_find_node(ctx, dst, edge->src->space);
3503 dst_dst = graph_find_node(ctx, dst, edge->dst->space);
3504 if (!dst_src || !dst_dst) {
3505 if (is_validity(edge) || is_conditional_validity(edge))
3506 isl_die(ctx, isl_error_internal,
3507 "backward (conditional) validity edge",
3508 return -1);
3509 continue;
3512 map = isl_map_copy(edge->map);
3513 tagged_condition = isl_union_map_copy(edge->tagged_condition);
3514 tagged_validity = isl_union_map_copy(edge->tagged_validity);
3516 dst->edge[dst->n_edge].src = dst_src;
3517 dst->edge[dst->n_edge].dst = dst_dst;
3518 dst->edge[dst->n_edge].map = map;
3519 dst->edge[dst->n_edge].tagged_condition = tagged_condition;
3520 dst->edge[dst->n_edge].tagged_validity = tagged_validity;
3521 dst->edge[dst->n_edge].types = edge->types;
3522 dst->n_edge++;
3524 if (edge->tagged_condition && !tagged_condition)
3525 return -1;
3526 if (edge->tagged_validity && !tagged_validity)
3527 return -1;
3529 if (graph_edge_tables_add(ctx, dst,
3530 &dst->edge[dst->n_edge - 1]) < 0)
3531 return -1;
3534 return 0;
3537 /* Compute the maximal number of variables over all nodes.
3538 * This is the maximal number of linearly independent schedule
3539 * rows that we need to compute.
3540 * Just in case we end up in a part of the dependence graph
3541 * with only lower-dimensional domains, we make sure we will
3542 * compute the required amount of extra linearly independent rows.
3544 static int compute_maxvar(struct isl_sched_graph *graph)
3546 int i;
3548 graph->maxvar = 0;
3549 for (i = 0; i < graph->n; ++i) {
3550 struct isl_sched_node *node = &graph->node[i];
3551 int nvar;
3553 if (node_update_vmap(node) < 0)
3554 return -1;
3555 nvar = node->nvar + graph->n_row - node->rank;
3556 if (nvar > graph->maxvar)
3557 graph->maxvar = nvar;
3560 return 0;
3563 /* Extract the subgraph of "graph" that consists of the nodes satisfying
3564 * "node_pred" and the edges satisfying "edge_pred" and store
3565 * the result in "sub".
3567 static int extract_sub_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
3568 int (*node_pred)(struct isl_sched_node *node, int data),
3569 int (*edge_pred)(struct isl_sched_edge *edge, int data),
3570 int data, struct isl_sched_graph *sub)
3572 int i, n = 0, n_edge = 0;
3573 int t;
3575 for (i = 0; i < graph->n; ++i)
3576 if (node_pred(&graph->node[i], data))
3577 ++n;
3578 for (i = 0; i < graph->n_edge; ++i)
3579 if (edge_pred(&graph->edge[i], data))
3580 ++n_edge;
3581 if (graph_alloc(ctx, sub, n, n_edge) < 0)
3582 return -1;
3583 sub->root = graph->root;
3584 if (copy_nodes(sub, graph, node_pred, data) < 0)
3585 return -1;
3586 if (graph_init_table(ctx, sub) < 0)
3587 return -1;
3588 for (t = 0; t <= isl_edge_last; ++t)
3589 sub->max_edge[t] = graph->max_edge[t];
3590 if (graph_init_edge_tables(ctx, sub) < 0)
3591 return -1;
3592 if (copy_edges(ctx, sub, graph, edge_pred, data) < 0)
3593 return -1;
3594 sub->n_row = graph->n_row;
3595 sub->max_row = graph->max_row;
3596 sub->n_total_row = graph->n_total_row;
3597 sub->band_start = graph->band_start;
3599 return 0;
3602 static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
3603 struct isl_sched_graph *graph);
3604 static __isl_give isl_schedule_node *compute_schedule_wcc(
3605 isl_schedule_node *node, struct isl_sched_graph *graph);
3607 /* Compute a schedule for a subgraph of "graph". In particular, for
3608 * the graph composed of nodes that satisfy node_pred and edges that
3609 * that satisfy edge_pred.
3610 * If the subgraph is known to consist of a single component, then wcc should
3611 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3612 * Otherwise, we call compute_schedule, which will check whether the subgraph
3613 * is connected.
3615 * The schedule is inserted at "node" and the updated schedule node
3616 * is returned.
3618 static __isl_give isl_schedule_node *compute_sub_schedule(
3619 __isl_take isl_schedule_node *node, isl_ctx *ctx,
3620 struct isl_sched_graph *graph,
3621 int (*node_pred)(struct isl_sched_node *node, int data),
3622 int (*edge_pred)(struct isl_sched_edge *edge, int data),
3623 int data, int wcc)
3625 struct isl_sched_graph split = { 0 };
3627 if (extract_sub_graph(ctx, graph, node_pred, edge_pred, data,
3628 &split) < 0)
3629 goto error;
3631 if (wcc)
3632 node = compute_schedule_wcc(node, &split);
3633 else
3634 node = compute_schedule(node, &split);
3636 graph_free(ctx, &split);
3637 return node;
3638 error:
3639 graph_free(ctx, &split);
3640 return isl_schedule_node_free(node);
3643 static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
3645 return edge->src->scc == scc && edge->dst->scc == scc;
3648 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
3650 return edge->dst->scc <= scc;
3653 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
3655 return edge->src->scc >= scc;
3658 /* Reset the current band by dropping all its schedule rows.
3660 static int reset_band(struct isl_sched_graph *graph)
3662 int i;
3663 int drop;
3665 drop = graph->n_total_row - graph->band_start;
3666 graph->n_total_row -= drop;
3667 graph->n_row -= drop;
3669 for (i = 0; i < graph->n; ++i) {
3670 struct isl_sched_node *node = &graph->node[i];
3672 isl_map_free(node->sched_map);
3673 node->sched_map = NULL;
3675 node->sched = isl_mat_drop_rows(node->sched,
3676 graph->band_start, drop);
3678 if (!node->sched)
3679 return -1;
3682 return 0;
3685 /* Split the current graph into two parts and compute a schedule for each
3686 * part individually. In particular, one part consists of all SCCs up
3687 * to and including graph->src_scc, while the other part contains the other
3688 * SCCs. The split is enforced by a sequence node inserted at position "node"
3689 * in the schedule tree. Return the updated schedule node.
3690 * If either of these two parts consists of a sequence, then it is spliced
3691 * into the sequence containing the two parts.
3693 * The current band is reset. It would be possible to reuse
3694 * the previously computed rows as the first rows in the next
3695 * band, but recomputing them may result in better rows as we are looking
3696 * at a smaller part of the dependence graph.
3698 static __isl_give isl_schedule_node *compute_split_schedule(
3699 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3701 int is_seq;
3702 isl_ctx *ctx;
3703 isl_union_set_list *filters;
3705 if (!node)
3706 return NULL;
3708 if (reset_band(graph) < 0)
3709 return isl_schedule_node_free(node);
3711 next_band(graph);
3713 ctx = isl_schedule_node_get_ctx(node);
3714 filters = extract_split(ctx, graph);
3715 node = isl_schedule_node_insert_sequence(node, filters);
3716 node = isl_schedule_node_child(node, 1);
3717 node = isl_schedule_node_child(node, 0);
3719 node = compute_sub_schedule(node, ctx, graph,
3720 &node_scc_at_least, &edge_src_scc_at_least,
3721 graph->src_scc + 1, 0);
3722 is_seq = isl_schedule_node_get_type(node) == isl_schedule_node_sequence;
3723 node = isl_schedule_node_parent(node);
3724 node = isl_schedule_node_parent(node);
3725 if (is_seq)
3726 node = isl_schedule_node_sequence_splice_child(node, 1);
3727 node = isl_schedule_node_child(node, 0);
3728 node = isl_schedule_node_child(node, 0);
3729 node = compute_sub_schedule(node, ctx, graph,
3730 &node_scc_at_most, &edge_dst_scc_at_most,
3731 graph->src_scc, 0);
3732 is_seq = isl_schedule_node_get_type(node) == isl_schedule_node_sequence;
3733 node = isl_schedule_node_parent(node);
3734 node = isl_schedule_node_parent(node);
3735 if (is_seq)
3736 node = isl_schedule_node_sequence_splice_child(node, 0);
3738 return node;
3741 /* Insert a band node at position "node" in the schedule tree corresponding
3742 * to the current band in "graph". Mark the band node permutable
3743 * if "permutable" is set.
3744 * The partial schedules and the coincidence property are extracted
3745 * from the graph nodes.
3746 * Return the updated schedule node.
3748 static __isl_give isl_schedule_node *insert_current_band(
3749 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
3750 int permutable)
3752 int i;
3753 int start, end, n;
3754 isl_multi_aff *ma;
3755 isl_multi_pw_aff *mpa;
3756 isl_multi_union_pw_aff *mupa;
3758 if (!node)
3759 return NULL;
3761 if (graph->n < 1)
3762 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
3763 "graph should have at least one node",
3764 return isl_schedule_node_free(node));
3766 start = graph->band_start;
3767 end = graph->n_total_row;
3768 n = end - start;
3770 ma = node_extract_partial_schedule_multi_aff(&graph->node[0], start, n);
3771 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3772 mupa = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3774 for (i = 1; i < graph->n; ++i) {
3775 isl_multi_union_pw_aff *mupa_i;
3777 ma = node_extract_partial_schedule_multi_aff(&graph->node[i],
3778 start, n);
3779 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3780 mupa_i = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3781 mupa = isl_multi_union_pw_aff_union_add(mupa, mupa_i);
3783 node = isl_schedule_node_insert_partial_schedule(node, mupa);
3785 for (i = 0; i < n; ++i)
3786 node = isl_schedule_node_band_member_set_coincident(node, i,
3787 graph->node[0].coincident[start + i]);
3788 node = isl_schedule_node_band_set_permutable(node, permutable);
3790 return node;
3793 /* Update the dependence relations based on the current schedule,
3794 * add the current band to "node" and then continue with the computation
3795 * of the next band.
3796 * Return the updated schedule node.
3798 static __isl_give isl_schedule_node *compute_next_band(
3799 __isl_take isl_schedule_node *node,
3800 struct isl_sched_graph *graph, int permutable)
3802 isl_ctx *ctx;
3804 if (!node)
3805 return NULL;
3807 ctx = isl_schedule_node_get_ctx(node);
3808 if (update_edges(ctx, graph) < 0)
3809 return isl_schedule_node_free(node);
3810 node = insert_current_band(node, graph, permutable);
3811 next_band(graph);
3813 node = isl_schedule_node_child(node, 0);
3814 node = compute_schedule(node, graph);
3815 node = isl_schedule_node_parent(node);
3817 return node;
3820 /* Add the constraints "coef" derived from an edge from "node" to itself
3821 * to graph->lp in order to respect the dependences and to try and carry them.
3822 * "pos" is the sequence number of the edge that needs to be carried.
3823 * "coef" represents general constraints on coefficients (c_0, c_x)
3824 * of valid constraints for (y - x) with x and y instances of the node.
3826 * The constraints added to graph->lp need to enforce
3828 * (c_j_0 + c_j_x y) - (c_j_0 + c_j_x x)
3829 * = c_j_x (y - x) >= e_i
3831 * for each (x,y) in the dependence relation of the edge.
3832 * That is, (-e_i, c_j_x) needs to be plugged in for (c_0, c_x),
3833 * taking into account that each coefficient in c_j_x is represented
3834 * as a pair of non-negative coefficients.
3836 static isl_stat add_intra_constraints(struct isl_sched_graph *graph,
3837 struct isl_sched_node *node, __isl_take isl_basic_set *coef, int pos)
3839 int offset;
3840 isl_ctx *ctx;
3841 isl_dim_map *dim_map;
3843 if (!coef)
3844 return isl_stat_error;
3846 ctx = isl_basic_set_get_ctx(coef);
3847 offset = coef_var_offset(coef);
3848 dim_map = intra_dim_map(ctx, graph, node, offset, 1);
3849 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3850 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
3852 return isl_stat_ok;
3855 /* Add the constraints "coef" derived from an edge from "src" to "dst"
3856 * to graph->lp in order to respect the dependences and to try and carry them.
3857 * "pos" is the sequence number of the edge that needs to be carried or
3858 * -1 if no attempt should be made to carry the dependences.
3859 * "coef" represents general constraints on coefficients (c_0, c_n, c_x, c_y)
3860 * of valid constraints for (x, y) with x and y instances of "src" and "dst".
3862 * The constraints added to graph->lp need to enforce
3864 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3866 * for each (x,y) in the dependence relation of the edge or
3868 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= 0
3870 * if pos is -1.
3871 * That is,
3872 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3873 * or
3874 * (c_k_0 - c_j_0, c_k_n - c_j_n, -c_j_x, c_k_x)
3875 * needs to be plugged in for (c_0, c_n, c_x, c_y),
3876 * taking into account that each coefficient in c_j_x and c_k_x is represented
3877 * as a pair of non-negative coefficients.
3879 static isl_stat add_inter_constraints(struct isl_sched_graph *graph,
3880 struct isl_sched_node *src, struct isl_sched_node *dst,
3881 __isl_take isl_basic_set *coef, int pos)
3883 int offset;
3884 isl_ctx *ctx;
3885 isl_dim_map *dim_map;
3887 if (!coef)
3888 return isl_stat_error;
3890 ctx = isl_basic_set_get_ctx(coef);
3891 offset = coef_var_offset(coef);
3892 dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1);
3893 if (pos >= 0)
3894 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3895 graph->lp = add_constraints_dim_map(graph->lp, coef, dim_map);
3897 return isl_stat_ok;
3900 /* Data structure for keeping track of the data needed
3901 * to exploit non-trivial lineality spaces.
3903 * "any_non_trivial" is true if there are any non-trivial lineality spaces.
3904 * If "any_non_trivial" is not true, then "equivalent" and "mask" may be NULL.
3905 * "equivalent" connects instances to other instances on the same line(s).
3906 * "mask" contains the domain spaces of "equivalent".
3907 * Any instance set not in "mask" does not have a non-trivial lineality space.
3909 struct isl_exploit_lineality_data {
3910 isl_bool any_non_trivial;
3911 isl_union_map *equivalent;
3912 isl_union_set *mask;
3915 /* Data structure collecting information used during the construction
3916 * of an LP for carrying dependences.
3918 * "intra" is a sequence of coefficient constraints for intra-node edges.
3919 * "inter" is a sequence of coefficient constraints for inter-node edges.
3920 * "lineality" contains data used to exploit non-trivial lineality spaces.
3922 struct isl_carry {
3923 isl_basic_set_list *intra;
3924 isl_basic_set_list *inter;
3925 struct isl_exploit_lineality_data lineality;
3928 /* Free all the data stored in "carry".
3930 static void isl_carry_clear(struct isl_carry *carry)
3932 isl_basic_set_list_free(carry->intra);
3933 isl_basic_set_list_free(carry->inter);
3934 isl_union_map_free(carry->lineality.equivalent);
3935 isl_union_set_free(carry->lineality.mask);
3938 /* Return a pointer to the node in "graph" that lives in "space".
3939 * If the requested node has been compressed, then "space"
3940 * corresponds to the compressed space.
3942 * First try and see if "space" is the space of an uncompressed node.
3943 * If so, return that node.
3944 * Otherwise, "space" was constructed by construct_compressed_id and
3945 * contains a user pointer pointing to the node in the tuple id.
3946 * However, this node belongs to the original dependence graph.
3947 * If "graph" is a subgraph of this original dependence graph,
3948 * then the node with the same space still needs to be looked up
3949 * in the current graph.
3951 static struct isl_sched_node *graph_find_compressed_node(isl_ctx *ctx,
3952 struct isl_sched_graph *graph, __isl_keep isl_space *space)
3954 isl_id *id;
3955 struct isl_sched_node *node;
3957 if (!space)
3958 return NULL;
3960 node = graph_find_node(ctx, graph, space);
3961 if (node)
3962 return node;
3964 id = isl_space_get_tuple_id(space, isl_dim_set);
3965 node = isl_id_get_user(id);
3966 isl_id_free(id);
3968 if (!node)
3969 return NULL;
3971 if (!is_node(graph->root, node))
3972 isl_die(ctx, isl_error_internal,
3973 "space points to invalid node", return NULL);
3974 if (graph != graph->root)
3975 node = graph_find_node(ctx, graph, node->space);
3977 return node;
3980 /* Internal data structure for add_all_constraints.
3982 * "graph" is the schedule constraint graph for which an LP problem
3983 * is being constructed.
3984 * "carry_inter" indicates whether inter-node edges should be carried.
3985 * "pos" is the position of the next edge that needs to be carried.
3987 struct isl_add_all_constraints_data {
3988 isl_ctx *ctx;
3989 struct isl_sched_graph *graph;
3990 int carry_inter;
3991 int pos;
3994 /* Add the constraints "coef" derived from an edge from a node to itself
3995 * to data->graph->lp in order to respect the dependences and
3996 * to try and carry them.
3998 * The space of "coef" is of the form
4000 * coefficients[[c_cst] -> S[c_x]]
4002 * with S[c_x] the (compressed) space of the node.
4003 * Extract the node from the space and call add_intra_constraints.
4005 static isl_stat lp_add_intra(__isl_take isl_basic_set *coef, void *user)
4007 struct isl_add_all_constraints_data *data = user;
4008 isl_space *space;
4009 struct isl_sched_node *node;
4011 space = isl_basic_set_get_space(coef);
4012 space = isl_space_range(isl_space_unwrap(space));
4013 node = graph_find_compressed_node(data->ctx, data->graph, space);
4014 isl_space_free(space);
4015 return add_intra_constraints(data->graph, node, coef, data->pos++);
4018 /* Add the constraints "coef" derived from an edge from a node j
4019 * to a node k to data->graph->lp in order to respect the dependences and
4020 * to try and carry them (provided data->carry_inter is set).
4022 * The space of "coef" is of the form
4024 * coefficients[[c_cst, c_n] -> [S_j[c_x] -> S_k[c_y]]]
4026 * with S_j[c_x] and S_k[c_y] the (compressed) spaces of the nodes.
4027 * Extract the nodes from the space and call add_inter_constraints.
4029 static isl_stat lp_add_inter(__isl_take isl_basic_set *coef, void *user)
4031 struct isl_add_all_constraints_data *data = user;
4032 isl_space *space, *dom;
4033 struct isl_sched_node *src, *dst;
4034 int pos;
4036 space = isl_basic_set_get_space(coef);
4037 space = isl_space_unwrap(isl_space_range(isl_space_unwrap(space)));
4038 dom = isl_space_domain(isl_space_copy(space));
4039 src = graph_find_compressed_node(data->ctx, data->graph, dom);
4040 isl_space_free(dom);
4041 space = isl_space_range(space);
4042 dst = graph_find_compressed_node(data->ctx, data->graph, space);
4043 isl_space_free(space);
4045 pos = data->carry_inter ? data->pos++ : -1;
4046 return add_inter_constraints(data->graph, src, dst, coef, pos);
4049 /* Add constraints to graph->lp that force all (conditional) validity
4050 * dependences to be respected and attempt to carry them.
4051 * "intra" is the sequence of coefficient constraints for intra-node edges.
4052 * "inter" is the sequence of coefficient constraints for inter-node edges.
4053 * "carry_inter" indicates whether inter-node edges should be carried or
4054 * only respected.
4056 static isl_stat add_all_constraints(isl_ctx *ctx, struct isl_sched_graph *graph,
4057 __isl_keep isl_basic_set_list *intra,
4058 __isl_keep isl_basic_set_list *inter, int carry_inter)
4060 struct isl_add_all_constraints_data data = { ctx, graph, carry_inter };
4062 data.pos = 0;
4063 if (isl_basic_set_list_foreach(intra, &lp_add_intra, &data) < 0)
4064 return isl_stat_error;
4065 if (isl_basic_set_list_foreach(inter, &lp_add_inter, &data) < 0)
4066 return isl_stat_error;
4067 return isl_stat_ok;
4070 /* Internal data structure for count_all_constraints
4071 * for keeping track of the number of equality and inequality constraints.
4073 struct isl_sched_count {
4074 int n_eq;
4075 int n_ineq;
4078 /* Add the number of equality and inequality constraints of "bset"
4079 * to data->n_eq and data->n_ineq.
4081 static isl_stat bset_update_count(__isl_take isl_basic_set *bset, void *user)
4083 struct isl_sched_count *data = user;
4085 return update_count(bset, 1, &data->n_eq, &data->n_ineq);
4088 /* Count the number of equality and inequality constraints
4089 * that will be added to the carry_lp problem.
4090 * We count each edge exactly once.
4091 * "intra" is the sequence of coefficient constraints for intra-node edges.
4092 * "inter" is the sequence of coefficient constraints for inter-node edges.
4094 static isl_stat count_all_constraints(__isl_keep isl_basic_set_list *intra,
4095 __isl_keep isl_basic_set_list *inter, int *n_eq, int *n_ineq)
4097 struct isl_sched_count data;
4099 data.n_eq = data.n_ineq = 0;
4100 if (isl_basic_set_list_foreach(inter, &bset_update_count, &data) < 0)
4101 return isl_stat_error;
4102 if (isl_basic_set_list_foreach(intra, &bset_update_count, &data) < 0)
4103 return isl_stat_error;
4105 *n_eq = data.n_eq;
4106 *n_ineq = data.n_ineq;
4108 return isl_stat_ok;
4111 /* Construct an LP problem for finding schedule coefficients
4112 * such that the schedule carries as many validity dependences as possible.
4113 * In particular, for each dependence i, we bound the dependence distance
4114 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
4115 * of all e_i's. Dependences with e_i = 0 in the solution are simply
4116 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
4117 * "intra" is the sequence of coefficient constraints for intra-node edges.
4118 * "inter" is the sequence of coefficient constraints for inter-node edges.
4119 * "n_edge" is the total number of edges.
4120 * "carry_inter" indicates whether inter-node edges should be carried or
4121 * only respected. That is, if "carry_inter" is not set, then
4122 * no e_i variables are introduced for the inter-node edges.
4124 * All variables of the LP are non-negative. The actual coefficients
4125 * may be negative, so each coefficient is represented as the difference
4126 * of two non-negative variables. The negative part always appears
4127 * immediately before the positive part.
4128 * Other than that, the variables have the following order
4130 * - sum of (1 - e_i) over all edges
4131 * - sum of all c_n coefficients
4132 * (unconstrained when computing non-parametric schedules)
4133 * - sum of positive and negative parts of all c_x coefficients
4134 * - for each edge
4135 * - e_i
4136 * - for each node
4137 * - positive and negative parts of c_i_x, in opposite order
4138 * - c_i_n (if parametric)
4139 * - c_i_0
4141 * The constraints are those from the (validity) edges plus three equalities
4142 * to express the sums and n_edge inequalities to express e_i <= 1.
4144 static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
4145 int n_edge, __isl_keep isl_basic_set_list *intra,
4146 __isl_keep isl_basic_set_list *inter, int carry_inter)
4148 int i;
4149 int k;
4150 isl_space *dim;
4151 unsigned total;
4152 int n_eq, n_ineq;
4154 total = 3 + n_edge;
4155 for (i = 0; i < graph->n; ++i) {
4156 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
4157 node->start = total;
4158 total += 1 + node->nparam + 2 * node->nvar;
4161 if (count_all_constraints(intra, inter, &n_eq, &n_ineq) < 0)
4162 return isl_stat_error;
4164 dim = isl_space_set_alloc(ctx, 0, total);
4165 isl_basic_set_free(graph->lp);
4166 n_eq += 3;
4167 n_ineq += n_edge;
4168 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
4169 graph->lp = isl_basic_set_set_rational(graph->lp);
4171 k = isl_basic_set_alloc_equality(graph->lp);
4172 if (k < 0)
4173 return isl_stat_error;
4174 isl_seq_clr(graph->lp->eq[k], 1 + total);
4175 isl_int_set_si(graph->lp->eq[k][0], -n_edge);
4176 isl_int_set_si(graph->lp->eq[k][1], 1);
4177 for (i = 0; i < n_edge; ++i)
4178 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
4180 if (add_param_sum_constraint(graph, 1) < 0)
4181 return isl_stat_error;
4182 if (add_var_sum_constraint(graph, 2) < 0)
4183 return isl_stat_error;
4185 for (i = 0; i < n_edge; ++i) {
4186 k = isl_basic_set_alloc_inequality(graph->lp);
4187 if (k < 0)
4188 return isl_stat_error;
4189 isl_seq_clr(graph->lp->ineq[k], 1 + total);
4190 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
4191 isl_int_set_si(graph->lp->ineq[k][0], 1);
4194 if (add_all_constraints(ctx, graph, intra, inter, carry_inter) < 0)
4195 return isl_stat_error;
4197 return isl_stat_ok;
4200 static __isl_give isl_schedule_node *compute_component_schedule(
4201 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
4202 int wcc);
4204 /* If the schedule_split_scaled option is set and if the linear
4205 * parts of the scheduling rows for all nodes in the graphs have
4206 * a non-trivial common divisor, then remove this
4207 * common divisor from the linear part.
4208 * Otherwise, insert a band node directly and continue with
4209 * the construction of the schedule.
4211 * If a non-trivial common divisor is found, then
4212 * the linear part is reduced and the remainder is ignored.
4213 * The pieces of the graph that are assigned different remainders
4214 * form (groups of) strongly connected components within
4215 * the scaled down band. If needed, they can therefore
4216 * be ordered along this remainder in a sequence node.
4217 * However, this ordering is not enforced here in order to allow
4218 * the scheduler to combine some of the strongly connected components.
4220 static __isl_give isl_schedule_node *split_scaled(
4221 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
4223 int i;
4224 int row;
4225 isl_ctx *ctx;
4226 isl_int gcd, gcd_i;
4228 if (!node)
4229 return NULL;
4231 ctx = isl_schedule_node_get_ctx(node);
4232 if (!ctx->opt->schedule_split_scaled)
4233 return compute_next_band(node, graph, 0);
4234 if (graph->n <= 1)
4235 return compute_next_band(node, graph, 0);
4237 isl_int_init(gcd);
4238 isl_int_init(gcd_i);
4240 isl_int_set_si(gcd, 0);
4242 row = isl_mat_rows(graph->node[0].sched) - 1;
4244 for (i = 0; i < graph->n; ++i) {
4245 struct isl_sched_node *node = &graph->node[i];
4246 int cols = isl_mat_cols(node->sched);
4248 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
4249 isl_int_gcd(gcd, gcd, gcd_i);
4252 isl_int_clear(gcd_i);
4254 if (isl_int_cmp_si(gcd, 1) <= 0) {
4255 isl_int_clear(gcd);
4256 return compute_next_band(node, graph, 0);
4259 for (i = 0; i < graph->n; ++i) {
4260 struct isl_sched_node *node = &graph->node[i];
4262 isl_int_fdiv_q(node->sched->row[row][0],
4263 node->sched->row[row][0], gcd);
4264 isl_int_mul(node->sched->row[row][0],
4265 node->sched->row[row][0], gcd);
4266 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
4267 if (!node->sched)
4268 goto error;
4271 isl_int_clear(gcd);
4273 return compute_next_band(node, graph, 0);
4274 error:
4275 isl_int_clear(gcd);
4276 return isl_schedule_node_free(node);
4279 /* Is the schedule row "sol" trivial on node "node"?
4280 * That is, is the solution zero on the dimensions linearly independent of
4281 * the previously found solutions?
4282 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
4284 * Each coefficient is represented as the difference between
4285 * two non-negative values in "sol".
4286 * We construct the schedule row s and check if it is linearly
4287 * independent of previously computed schedule rows
4288 * by computing T s, with T the linear combinations that are zero
4289 * on linearly dependent schedule rows.
4290 * If the result consists of all zeros, then the solution is trivial.
4292 static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
4294 int trivial;
4295 isl_vec *node_sol;
4297 if (!sol)
4298 return -1;
4299 if (node->nvar == node->rank)
4300 return 0;
4302 node_sol = extract_var_coef(node, sol);
4303 node_sol = isl_mat_vec_product(isl_mat_copy(node->indep), node_sol);
4304 if (!node_sol)
4305 return -1;
4307 trivial = isl_seq_first_non_zero(node_sol->el,
4308 node->nvar - node->rank) == -1;
4310 isl_vec_free(node_sol);
4312 return trivial;
4315 /* Is the schedule row "sol" trivial on any node where it should
4316 * not be trivial?
4317 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
4319 static int is_any_trivial(struct isl_sched_graph *graph,
4320 __isl_keep isl_vec *sol)
4322 int i;
4324 for (i = 0; i < graph->n; ++i) {
4325 struct isl_sched_node *node = &graph->node[i];
4326 int trivial;
4328 if (!needs_row(graph, node))
4329 continue;
4330 trivial = is_trivial(node, sol);
4331 if (trivial < 0 || trivial)
4332 return trivial;
4335 return 0;
4338 /* Does the schedule represented by "sol" perform loop coalescing on "node"?
4339 * If so, return the position of the coalesced dimension.
4340 * Otherwise, return node->nvar or -1 on error.
4342 * In particular, look for pairs of coefficients c_i and c_j such that
4343 * |c_j/c_i| > ceil(size_i/2), i.e., |c_j| > |c_i * ceil(size_i/2)|.
4344 * If any such pair is found, then return i.
4345 * If size_i is infinity, then no check on c_i needs to be performed.
4347 static int find_node_coalescing(struct isl_sched_node *node,
4348 __isl_keep isl_vec *sol)
4350 int i, j;
4351 isl_int max;
4352 isl_vec *csol;
4354 if (node->nvar <= 1)
4355 return node->nvar;
4357 csol = extract_var_coef(node, sol);
4358 if (!csol)
4359 return -1;
4360 isl_int_init(max);
4361 for (i = 0; i < node->nvar; ++i) {
4362 isl_val *v;
4364 if (isl_int_is_zero(csol->el[i]))
4365 continue;
4366 v = isl_multi_val_get_val(node->sizes, i);
4367 if (!v)
4368 goto error;
4369 if (!isl_val_is_int(v)) {
4370 isl_val_free(v);
4371 continue;
4373 v = isl_val_div_ui(v, 2);
4374 v = isl_val_ceil(v);
4375 if (!v)
4376 goto error;
4377 isl_int_mul(max, v->n, csol->el[i]);
4378 isl_val_free(v);
4380 for (j = 0; j < node->nvar; ++j) {
4381 if (j == i)
4382 continue;
4383 if (isl_int_abs_gt(csol->el[j], max))
4384 break;
4386 if (j < node->nvar)
4387 break;
4390 isl_int_clear(max);
4391 isl_vec_free(csol);
4392 return i;
4393 error:
4394 isl_int_clear(max);
4395 isl_vec_free(csol);
4396 return -1;
4399 /* Force the schedule coefficient at position "pos" of "node" to be zero
4400 * in "tl".
4401 * The coefficient is encoded as the difference between two non-negative
4402 * variables. Force these two variables to have the same value.
4404 static __isl_give isl_tab_lexmin *zero_out_node_coef(
4405 __isl_take isl_tab_lexmin *tl, struct isl_sched_node *node, int pos)
4407 int dim;
4408 isl_ctx *ctx;
4409 isl_vec *eq;
4411 ctx = isl_space_get_ctx(node->space);
4412 dim = isl_tab_lexmin_dim(tl);
4413 if (dim < 0)
4414 return isl_tab_lexmin_free(tl);
4415 eq = isl_vec_alloc(ctx, 1 + dim);
4416 eq = isl_vec_clr(eq);
4417 if (!eq)
4418 return isl_tab_lexmin_free(tl);
4420 pos = 1 + node_var_coef_pos(node, pos);
4421 isl_int_set_si(eq->el[pos], 1);
4422 isl_int_set_si(eq->el[pos + 1], -1);
4423 tl = isl_tab_lexmin_add_eq(tl, eq->el);
4424 isl_vec_free(eq);
4426 return tl;
4429 /* Return the lexicographically smallest rational point in the basic set
4430 * from which "tl" was constructed, double checking that this input set
4431 * was not empty.
4433 static __isl_give isl_vec *non_empty_solution(__isl_keep isl_tab_lexmin *tl)
4435 isl_vec *sol;
4437 sol = isl_tab_lexmin_get_solution(tl);
4438 if (!sol)
4439 return NULL;
4440 if (sol->size == 0)
4441 isl_die(isl_vec_get_ctx(sol), isl_error_internal,
4442 "error in schedule construction",
4443 return isl_vec_free(sol));
4444 return sol;
4447 /* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4448 * carry any of the "n_edge" groups of dependences?
4449 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4450 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4451 * by the edge are carried by the solution.
4452 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4453 * one of those is carried.
4455 * Note that despite the fact that the problem is solved using a rational
4456 * solver, the solution is guaranteed to be integral.
4457 * Specifically, the dependence distance lower bounds e_i (and therefore
4458 * also their sum) are integers. See Lemma 5 of [1].
4460 * Any potential denominator of the sum is cleared by this function.
4461 * The denominator is not relevant for any of the other elements
4462 * in the solution.
4464 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4465 * Problem, Part II: Multi-Dimensional Time.
4466 * In Intl. Journal of Parallel Programming, 1992.
4468 static int carries_dependences(__isl_keep isl_vec *sol, int n_edge)
4470 isl_int_divexact(sol->el[1], sol->el[1], sol->el[0]);
4471 isl_int_set_si(sol->el[0], 1);
4472 return isl_int_cmp_si(sol->el[1], n_edge) < 0;
4475 /* Return the lexicographically smallest rational point in "lp",
4476 * assuming that all variables are non-negative and performing some
4477 * additional sanity checks.
4478 * If "want_integral" is set, then compute the lexicographically smallest
4479 * integer point instead.
4480 * In particular, "lp" should not be empty by construction.
4481 * Double check that this is the case.
4482 * If dependences are not carried for any of the "n_edge" edges,
4483 * then return an empty vector.
4485 * If the schedule_treat_coalescing option is set and
4486 * if the computed schedule performs loop coalescing on a given node,
4487 * i.e., if it is of the form
4489 * c_i i + c_j j + ...
4491 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4492 * to cut out this solution. Repeat this process until no more loop
4493 * coalescing occurs or until no more dependences can be carried.
4494 * In the latter case, revert to the previously computed solution.
4496 * If the caller requests an integral solution and if coalescing should
4497 * be treated, then perform the coalescing treatment first as
4498 * an integral solution computed before coalescing treatment
4499 * would carry the same number of edges and would therefore probably
4500 * also be coalescing.
4502 * To allow the coalescing treatment to be performed first,
4503 * the initial solution is allowed to be rational and it is only
4504 * cut out (if needed) in the next iteration, if no coalescing measures
4505 * were taken.
4507 static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph,
4508 __isl_take isl_basic_set *lp, int n_edge, int want_integral)
4510 int i, pos, cut;
4511 isl_ctx *ctx;
4512 isl_tab_lexmin *tl;
4513 isl_vec *sol, *prev = NULL;
4514 int treat_coalescing;
4516 if (!lp)
4517 return NULL;
4518 ctx = isl_basic_set_get_ctx(lp);
4519 treat_coalescing = isl_options_get_schedule_treat_coalescing(ctx);
4520 tl = isl_tab_lexmin_from_basic_set(lp);
4522 cut = 0;
4523 do {
4524 int integral;
4526 if (cut)
4527 tl = isl_tab_lexmin_cut_to_integer(tl);
4528 sol = non_empty_solution(tl);
4529 if (!sol)
4530 goto error;
4532 integral = isl_int_is_one(sol->el[0]);
4533 if (!carries_dependences(sol, n_edge)) {
4534 if (!prev)
4535 prev = isl_vec_alloc(ctx, 0);
4536 isl_vec_free(sol);
4537 sol = prev;
4538 break;
4540 prev = isl_vec_free(prev);
4541 cut = want_integral && !integral;
4542 if (cut)
4543 prev = sol;
4544 if (!treat_coalescing)
4545 continue;
4546 for (i = 0; i < graph->n; ++i) {
4547 struct isl_sched_node *node = &graph->node[i];
4549 pos = find_node_coalescing(node, sol);
4550 if (pos < 0)
4551 goto error;
4552 if (pos < node->nvar)
4553 break;
4555 if (i < graph->n) {
4556 prev = sol;
4557 tl = zero_out_node_coef(tl, &graph->node[i], pos);
4558 cut = 0;
4560 } while (prev);
4562 isl_tab_lexmin_free(tl);
4564 return sol;
4565 error:
4566 isl_tab_lexmin_free(tl);
4567 isl_vec_free(prev);
4568 isl_vec_free(sol);
4569 return NULL;
4572 /* If "edge" is an edge from a node to itself, then add the corresponding
4573 * dependence relation to "umap".
4574 * If "node" has been compressed, then the dependence relation
4575 * is also compressed first.
4577 static __isl_give isl_union_map *add_intra(__isl_take isl_union_map *umap,
4578 struct isl_sched_edge *edge)
4580 isl_map *map;
4581 struct isl_sched_node *node = edge->src;
4583 if (edge->src != edge->dst)
4584 return umap;
4586 map = isl_map_copy(edge->map);
4587 if (node->compressed) {
4588 map = isl_map_preimage_domain_multi_aff(map,
4589 isl_multi_aff_copy(node->decompress));
4590 map = isl_map_preimage_range_multi_aff(map,
4591 isl_multi_aff_copy(node->decompress));
4593 umap = isl_union_map_add_map(umap, map);
4594 return umap;
4597 /* If "edge" is an edge from a node to another node, then add the corresponding
4598 * dependence relation to "umap".
4599 * If the source or destination nodes of "edge" have been compressed,
4600 * then the dependence relation is also compressed first.
4602 static __isl_give isl_union_map *add_inter(__isl_take isl_union_map *umap,
4603 struct isl_sched_edge *edge)
4605 isl_map *map;
4607 if (edge->src == edge->dst)
4608 return umap;
4610 map = isl_map_copy(edge->map);
4611 if (edge->src->compressed)
4612 map = isl_map_preimage_domain_multi_aff(map,
4613 isl_multi_aff_copy(edge->src->decompress));
4614 if (edge->dst->compressed)
4615 map = isl_map_preimage_range_multi_aff(map,
4616 isl_multi_aff_copy(edge->dst->decompress));
4617 umap = isl_union_map_add_map(umap, map);
4618 return umap;
4621 /* Internal data structure used by union_drop_coalescing_constraints
4622 * to collect bounds on all relevant statements.
4624 * "graph" is the schedule constraint graph for which an LP problem
4625 * is being constructed.
4626 * "bounds" collects the bounds.
4628 struct isl_collect_bounds_data {
4629 isl_ctx *ctx;
4630 struct isl_sched_graph *graph;
4631 isl_union_set *bounds;
4634 /* Add the size bounds for the node with instance deltas in "set"
4635 * to data->bounds.
4637 static isl_stat collect_bounds(__isl_take isl_set *set, void *user)
4639 struct isl_collect_bounds_data *data = user;
4640 struct isl_sched_node *node;
4641 isl_space *space;
4642 isl_set *bounds;
4644 space = isl_set_get_space(set);
4645 isl_set_free(set);
4647 node = graph_find_compressed_node(data->ctx, data->graph, space);
4648 isl_space_free(space);
4650 bounds = isl_set_from_basic_set(get_size_bounds(node));
4651 data->bounds = isl_union_set_add_set(data->bounds, bounds);
4653 return isl_stat_ok;
4656 /* Drop some constraints from "delta" that could be exploited
4657 * to construct loop coalescing schedules.
4658 * In particular, drop those constraint that bound the difference
4659 * to the size of the domain.
4660 * Do this for each set/node in "delta" separately.
4661 * The parameters are assumed to have been projected out by the caller.
4663 static __isl_give isl_union_set *union_drop_coalescing_constraints(isl_ctx *ctx,
4664 struct isl_sched_graph *graph, __isl_take isl_union_set *delta)
4666 struct isl_collect_bounds_data data = { ctx, graph };
4668 data.bounds = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
4669 if (isl_union_set_foreach_set(delta, &collect_bounds, &data) < 0)
4670 data.bounds = isl_union_set_free(data.bounds);
4671 delta = isl_union_set_plain_gist(delta, data.bounds);
4673 return delta;
4676 /* Given a non-trivial lineality space "lineality", add the corresponding
4677 * universe set to data->mask and add a map from elements to
4678 * other elements along the lines in "lineality" to data->equivalent.
4679 * If this is the first time this function gets called
4680 * (data->any_non_trivial is still false), then set data->any_non_trivial and
4681 * initialize data->mask and data->equivalent.
4683 * In particular, if the lineality space is defined by equality constraints
4685 * E x = 0
4687 * then construct an affine mapping
4689 * f : x -> E x
4691 * and compute the equivalence relation of having the same image under f:
4693 * { x -> x' : E x = E x' }
4695 static isl_stat add_non_trivial_lineality(__isl_take isl_basic_set *lineality,
4696 struct isl_exploit_lineality_data *data)
4698 isl_mat *eq;
4699 isl_space *space;
4700 isl_set *univ;
4701 isl_multi_aff *ma;
4702 isl_multi_pw_aff *mpa;
4703 isl_map *map;
4704 int n;
4706 if (!lineality)
4707 return isl_stat_error;
4708 if (isl_basic_set_dim(lineality, isl_dim_div) != 0)
4709 isl_die(isl_basic_set_get_ctx(lineality), isl_error_internal,
4710 "local variables not allowed", goto error);
4712 space = isl_basic_set_get_space(lineality);
4713 if (!data->any_non_trivial) {
4714 data->equivalent = isl_union_map_empty(isl_space_copy(space));
4715 data->mask = isl_union_set_empty(isl_space_copy(space));
4717 data->any_non_trivial = isl_bool_true;
4719 univ = isl_set_universe(isl_space_copy(space));
4720 data->mask = isl_union_set_add_set(data->mask, univ);
4722 eq = isl_basic_set_extract_equalities(lineality);
4723 n = isl_mat_rows(eq);
4724 eq = isl_mat_insert_zero_rows(eq, 0, 1);
4725 eq = isl_mat_set_element_si(eq, 0, 0, 1);
4726 space = isl_space_from_domain(space);
4727 space = isl_space_add_dims(space, isl_dim_out, n);
4728 ma = isl_multi_aff_from_aff_mat(space, eq);
4729 mpa = isl_multi_pw_aff_from_multi_aff(ma);
4730 map = isl_multi_pw_aff_eq_map(mpa, isl_multi_pw_aff_copy(mpa));
4731 data->equivalent = isl_union_map_add_map(data->equivalent, map);
4733 isl_basic_set_free(lineality);
4734 return isl_stat_ok;
4735 error:
4736 isl_basic_set_free(lineality);
4737 return isl_stat_error;
4740 /* Check if the lineality space "set" is non-trivial (i.e., is not just
4741 * the origin or, in other words, satisfies a number of equality constraints
4742 * that is smaller than the dimension of the set).
4743 * If so, extend data->mask and data->equivalent accordingly.
4745 * The input should not have any local variables already, but
4746 * isl_set_remove_divs is called to make sure it does not.
4748 static isl_stat add_lineality(__isl_take isl_set *set, void *user)
4750 struct isl_exploit_lineality_data *data = user;
4751 isl_basic_set *hull;
4752 int dim, n_eq;
4754 set = isl_set_remove_divs(set);
4755 hull = isl_set_unshifted_simple_hull(set);
4756 dim = isl_basic_set_dim(hull, isl_dim_set);
4757 n_eq = isl_basic_set_n_equality(hull);
4758 if (!hull)
4759 return isl_stat_error;
4760 if (dim != n_eq)
4761 return add_non_trivial_lineality(hull, data);
4762 isl_basic_set_free(hull);
4763 return isl_stat_ok;
4766 /* Check if the difference set on intra-node schedule constraints "intra"
4767 * has any non-trivial lineality space.
4768 * If so, then extend the difference set to a difference set
4769 * on equivalent elements. That is, if "intra" is
4771 * { y - x : (x,y) \in V }
4773 * and elements are equivalent if they have the same image under f,
4774 * then return
4776 * { y' - x' : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4778 * or, since f is linear,
4780 * { y' - x' : (x,y) \in V and f(y - x) = f(y' - x') }
4782 * The results of the search for non-trivial lineality spaces is stored
4783 * in "data".
4785 static __isl_give isl_union_set *exploit_intra_lineality(
4786 __isl_take isl_union_set *intra,
4787 struct isl_exploit_lineality_data *data)
4789 isl_union_set *lineality;
4790 isl_union_set *uset;
4792 data->any_non_trivial = isl_bool_false;
4793 lineality = isl_union_set_copy(intra);
4794 lineality = isl_union_set_combined_lineality_space(lineality);
4795 if (isl_union_set_foreach_set(lineality, &add_lineality, data) < 0)
4796 data->any_non_trivial = isl_bool_error;
4797 isl_union_set_free(lineality);
4799 if (data->any_non_trivial < 0)
4800 return isl_union_set_free(intra);
4801 if (!data->any_non_trivial)
4802 return intra;
4804 uset = isl_union_set_copy(intra);
4805 intra = isl_union_set_subtract(intra, isl_union_set_copy(data->mask));
4806 uset = isl_union_set_apply(uset, isl_union_map_copy(data->equivalent));
4807 intra = isl_union_set_union(intra, uset);
4809 intra = isl_union_set_remove_divs(intra);
4811 return intra;
4814 /* If the difference set on intra-node schedule constraints was found to have
4815 * any non-trivial lineality space by exploit_intra_lineality,
4816 * as recorded in "data", then extend the inter-node
4817 * schedule constraints "inter" to schedule constraints on equivalent elements.
4818 * That is, if "inter" is V and
4819 * elements are equivalent if they have the same image under f, then return
4821 * { (x', y') : (x,y) \in V and f(x) = f(x') and f(y) = f(y') }
4823 static __isl_give isl_union_map *exploit_inter_lineality(
4824 __isl_take isl_union_map *inter,
4825 struct isl_exploit_lineality_data *data)
4827 isl_union_map *umap;
4829 if (data->any_non_trivial < 0)
4830 return isl_union_map_free(inter);
4831 if (!data->any_non_trivial)
4832 return inter;
4834 umap = isl_union_map_copy(inter);
4835 inter = isl_union_map_subtract_range(inter,
4836 isl_union_set_copy(data->mask));
4837 umap = isl_union_map_apply_range(umap,
4838 isl_union_map_copy(data->equivalent));
4839 inter = isl_union_map_union(inter, umap);
4840 umap = isl_union_map_copy(inter);
4841 inter = isl_union_map_subtract_domain(inter,
4842 isl_union_set_copy(data->mask));
4843 umap = isl_union_map_apply_range(isl_union_map_copy(data->equivalent),
4844 umap);
4845 inter = isl_union_map_union(inter, umap);
4847 inter = isl_union_map_remove_divs(inter);
4849 return inter;
4852 /* For each (conditional) validity edge in "graph",
4853 * add the corresponding dependence relation using "add"
4854 * to a collection of dependence relations and return the result.
4855 * If "coincidence" is set, then coincidence edges are considered as well.
4857 static __isl_give isl_union_map *collect_validity(struct isl_sched_graph *graph,
4858 __isl_give isl_union_map *(*add)(__isl_take isl_union_map *umap,
4859 struct isl_sched_edge *edge), int coincidence)
4861 int i;
4862 isl_space *space;
4863 isl_union_map *umap;
4865 space = isl_space_copy(graph->node[0].space);
4866 umap = isl_union_map_empty(space);
4868 for (i = 0; i < graph->n_edge; ++i) {
4869 struct isl_sched_edge *edge = &graph->edge[i];
4871 if (!is_any_validity(edge) &&
4872 (!coincidence || !is_coincidence(edge)))
4873 continue;
4875 umap = add(umap, edge);
4878 return umap;
4881 /* Project out all parameters from "uset" and return the result.
4883 static __isl_give isl_union_set *union_set_drop_parameters(
4884 __isl_take isl_union_set *uset)
4886 unsigned nparam;
4888 nparam = isl_union_set_dim(uset, isl_dim_param);
4889 return isl_union_set_project_out(uset, isl_dim_param, 0, nparam);
4892 /* For each dependence relation on a (conditional) validity edge
4893 * from a node to itself,
4894 * construct the set of coefficients of valid constraints for elements
4895 * in that dependence relation and collect the results.
4896 * If "coincidence" is set, then coincidence edges are considered as well.
4898 * In particular, for each dependence relation R, constraints
4899 * on coefficients (c_0, c_x) are constructed such that
4901 * c_0 + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
4903 * If the schedule_treat_coalescing option is set, then some constraints
4904 * that could be exploited to construct coalescing schedules
4905 * are removed before the dual is computed, but after the parameters
4906 * have been projected out.
4907 * The entire computation is essentially the same as that performed
4908 * by intra_coefficients, except that it operates on multiple
4909 * edges together and that the parameters are always projected out.
4911 * Additionally, exploit any non-trivial lineality space
4912 * in the difference set after removing coalescing constraints and
4913 * store the results of the non-trivial lineality space detection in "data".
4914 * The procedure is currently run unconditionally, but it is unlikely
4915 * to find any non-trivial lineality spaces if no coalescing constraints
4916 * have been removed.
4918 * Note that if a dependence relation is a union of basic maps,
4919 * then each basic map needs to be treated individually as it may only
4920 * be possible to carry the dependences expressed by some of those
4921 * basic maps and not all of them.
4922 * The collected validity constraints are therefore not coalesced and
4923 * it is assumed that they are not coalesced automatically.
4924 * Duplicate basic maps can be removed, however.
4925 * In particular, if the same basic map appears as a disjunct
4926 * in multiple edges, then it only needs to be carried once.
4928 static __isl_give isl_basic_set_list *collect_intra_validity(isl_ctx *ctx,
4929 struct isl_sched_graph *graph, int coincidence,
4930 struct isl_exploit_lineality_data *data)
4932 isl_union_map *intra;
4933 isl_union_set *delta;
4934 isl_basic_set_list *list;
4936 intra = collect_validity(graph, &add_intra, coincidence);
4937 delta = isl_union_map_deltas(intra);
4938 delta = union_set_drop_parameters(delta);
4939 delta = isl_union_set_remove_divs(delta);
4940 if (isl_options_get_schedule_treat_coalescing(ctx))
4941 delta = union_drop_coalescing_constraints(ctx, graph, delta);
4942 delta = exploit_intra_lineality(delta, data);
4943 list = isl_union_set_get_basic_set_list(delta);
4944 isl_union_set_free(delta);
4946 return isl_basic_set_list_coefficients(list);
4949 /* For each dependence relation on a (conditional) validity edge
4950 * from a node to some other node,
4951 * construct the set of coefficients of valid constraints for elements
4952 * in that dependence relation and collect the results.
4953 * If "coincidence" is set, then coincidence edges are considered as well.
4955 * In particular, for each dependence relation R, constraints
4956 * on coefficients (c_0, c_n, c_x, c_y) are constructed such that
4958 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
4960 * This computation is essentially the same as that performed
4961 * by inter_coefficients, except that it operates on multiple
4962 * edges together.
4964 * Additionally, exploit any non-trivial lineality space
4965 * that may have been discovered by collect_intra_validity
4966 * (as stored in "data").
4968 * Note that if a dependence relation is a union of basic maps,
4969 * then each basic map needs to be treated individually as it may only
4970 * be possible to carry the dependences expressed by some of those
4971 * basic maps and not all of them.
4972 * The collected validity constraints are therefore not coalesced and
4973 * it is assumed that they are not coalesced automatically.
4974 * Duplicate basic maps can be removed, however.
4975 * In particular, if the same basic map appears as a disjunct
4976 * in multiple edges, then it only needs to be carried once.
4978 static __isl_give isl_basic_set_list *collect_inter_validity(
4979 struct isl_sched_graph *graph, int coincidence,
4980 struct isl_exploit_lineality_data *data)
4982 isl_union_map *inter;
4983 isl_union_set *wrap;
4984 isl_basic_set_list *list;
4986 inter = collect_validity(graph, &add_inter, coincidence);
4987 inter = exploit_inter_lineality(inter, data);
4988 inter = isl_union_map_remove_divs(inter);
4989 wrap = isl_union_map_wrap(inter);
4990 list = isl_union_set_get_basic_set_list(wrap);
4991 isl_union_set_free(wrap);
4992 return isl_basic_set_list_coefficients(list);
4995 /* Construct an LP problem for finding schedule coefficients
4996 * such that the schedule carries as many of the "n_edge" groups of
4997 * dependences as possible based on the corresponding coefficient
4998 * constraints and return the lexicographically smallest non-trivial solution.
4999 * "intra" is the sequence of coefficient constraints for intra-node edges.
5000 * "inter" is the sequence of coefficient constraints for inter-node edges.
5001 * If "want_integral" is set, then compute an integral solution
5002 * for the coefficients rather than using the numerators
5003 * of a rational solution.
5004 * "carry_inter" indicates whether inter-node edges should be carried or
5005 * only respected.
5007 * If none of the "n_edge" groups can be carried
5008 * then return an empty vector.
5010 static __isl_give isl_vec *compute_carrying_sol_coef(isl_ctx *ctx,
5011 struct isl_sched_graph *graph, int n_edge,
5012 __isl_keep isl_basic_set_list *intra,
5013 __isl_keep isl_basic_set_list *inter, int want_integral,
5014 int carry_inter)
5016 isl_basic_set *lp;
5018 if (setup_carry_lp(ctx, graph, n_edge, intra, inter, carry_inter) < 0)
5019 return NULL;
5021 lp = isl_basic_set_copy(graph->lp);
5022 return non_neg_lexmin(graph, lp, n_edge, want_integral);
5025 /* Construct an LP problem for finding schedule coefficients
5026 * such that the schedule carries as many of the validity dependences
5027 * as possible and
5028 * return the lexicographically smallest non-trivial solution.
5029 * If "fallback" is set, then the carrying is performed as a fallback
5030 * for the Pluto-like scheduler.
5031 * If "coincidence" is set, then try and carry coincidence edges as well.
5033 * The variable "n_edge" stores the number of groups that should be carried.
5034 * If none of the "n_edge" groups can be carried
5035 * then return an empty vector.
5036 * If, moreover, "n_edge" is zero, then the LP problem does not even
5037 * need to be constructed.
5039 * If a fallback solution is being computed, then compute an integral solution
5040 * for the coefficients rather than using the numerators
5041 * of a rational solution.
5043 * If a fallback solution is being computed, if there are any intra-node
5044 * dependences, and if requested by the user, then first try
5045 * to only carry those intra-node dependences.
5046 * If this fails to carry any dependences, then try again
5047 * with the inter-node dependences included.
5049 static __isl_give isl_vec *compute_carrying_sol(isl_ctx *ctx,
5050 struct isl_sched_graph *graph, int fallback, int coincidence)
5052 int n_intra, n_inter;
5053 int n_edge;
5054 struct isl_carry carry = { 0 };
5055 isl_vec *sol;
5057 carry.intra = collect_intra_validity(ctx, graph, coincidence,
5058 &carry.lineality);
5059 carry.inter = collect_inter_validity(graph, coincidence,
5060 &carry.lineality);
5061 if (!carry.intra || !carry.inter)
5062 goto error;
5063 n_intra = isl_basic_set_list_n_basic_set(carry.intra);
5064 n_inter = isl_basic_set_list_n_basic_set(carry.inter);
5066 if (fallback && n_intra > 0 &&
5067 isl_options_get_schedule_carry_self_first(ctx)) {
5068 sol = compute_carrying_sol_coef(ctx, graph, n_intra,
5069 carry.intra, carry.inter, fallback, 0);
5070 if (!sol || sol->size != 0 || n_inter == 0) {
5071 isl_carry_clear(&carry);
5072 return sol;
5074 isl_vec_free(sol);
5077 n_edge = n_intra + n_inter;
5078 if (n_edge == 0) {
5079 isl_carry_clear(&carry);
5080 return isl_vec_alloc(ctx, 0);
5083 sol = compute_carrying_sol_coef(ctx, graph, n_edge,
5084 carry.intra, carry.inter, fallback, 1);
5085 isl_carry_clear(&carry);
5086 return sol;
5087 error:
5088 isl_carry_clear(&carry);
5089 return NULL;
5092 /* Construct a schedule row for each node such that as many validity dependences
5093 * as possible are carried and then continue with the next band.
5094 * If "fallback" is set, then the carrying is performed as a fallback
5095 * for the Pluto-like scheduler.
5096 * If "coincidence" is set, then try and carry coincidence edges as well.
5098 * If there are no validity dependences, then no dependence can be carried and
5099 * the procedure is guaranteed to fail. If there is more than one component,
5100 * then try computing a schedule on each component separately
5101 * to prevent or at least postpone this failure.
5103 * If a schedule row is computed, then check that dependences are carried
5104 * for at least one of the edges.
5106 * If the computed schedule row turns out to be trivial on one or
5107 * more nodes where it should not be trivial, then we throw it away
5108 * and try again on each component separately.
5110 * If there is only one component, then we accept the schedule row anyway,
5111 * but we do not consider it as a complete row and therefore do not
5112 * increment graph->n_row. Note that the ranks of the nodes that
5113 * do get a non-trivial schedule part will get updated regardless and
5114 * graph->maxvar is computed based on these ranks. The test for
5115 * whether more schedule rows are required in compute_schedule_wcc
5116 * is therefore not affected.
5118 * Insert a band corresponding to the schedule row at position "node"
5119 * of the schedule tree and continue with the construction of the schedule.
5120 * This insertion and the continued construction is performed by split_scaled
5121 * after optionally checking for non-trivial common divisors.
5123 static __isl_give isl_schedule_node *carry(__isl_take isl_schedule_node *node,
5124 struct isl_sched_graph *graph, int fallback, int coincidence)
5126 int trivial;
5127 isl_ctx *ctx;
5128 isl_vec *sol;
5130 if (!node)
5131 return NULL;
5133 ctx = isl_schedule_node_get_ctx(node);
5134 sol = compute_carrying_sol(ctx, graph, fallback, coincidence);
5135 if (!sol)
5136 return isl_schedule_node_free(node);
5137 if (sol->size == 0) {
5138 isl_vec_free(sol);
5139 if (graph->scc > 1)
5140 return compute_component_schedule(node, graph, 1);
5141 isl_die(ctx, isl_error_unknown, "unable to carry dependences",
5142 return isl_schedule_node_free(node));
5145 trivial = is_any_trivial(graph, sol);
5146 if (trivial < 0) {
5147 sol = isl_vec_free(sol);
5148 } else if (trivial && graph->scc > 1) {
5149 isl_vec_free(sol);
5150 return compute_component_schedule(node, graph, 1);
5153 if (update_schedule(graph, sol, 0) < 0)
5154 return isl_schedule_node_free(node);
5155 if (trivial)
5156 graph->n_row--;
5158 return split_scaled(node, graph);
5161 /* Construct a schedule row for each node such that as many validity dependences
5162 * as possible are carried and then continue with the next band.
5163 * Do so as a fallback for the Pluto-like scheduler.
5164 * If "coincidence" is set, then try and carry coincidence edges as well.
5166 static __isl_give isl_schedule_node *carry_fallback(
5167 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
5168 int coincidence)
5170 return carry(node, graph, 1, coincidence);
5173 /* Construct a schedule row for each node such that as many validity dependences
5174 * as possible are carried and then continue with the next band.
5175 * Do so for the case where the Feautrier scheduler was selected
5176 * by the user.
5178 static __isl_give isl_schedule_node *carry_feautrier(
5179 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5181 return carry(node, graph, 0, 0);
5184 /* Construct a schedule row for each node such that as many validity dependences
5185 * as possible are carried and then continue with the next band.
5186 * Do so as a fallback for the Pluto-like scheduler.
5188 static __isl_give isl_schedule_node *carry_dependences(
5189 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5191 return carry_fallback(node, graph, 0);
5194 /* Construct a schedule row for each node such that as many validity or
5195 * coincidence dependences as possible are carried and
5196 * then continue with the next band.
5197 * Do so as a fallback for the Pluto-like scheduler.
5199 static __isl_give isl_schedule_node *carry_coincidence(
5200 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5202 return carry_fallback(node, graph, 1);
5205 /* Topologically sort statements mapped to the same schedule iteration
5206 * and add insert a sequence node in front of "node"
5207 * corresponding to this order.
5208 * If "initialized" is set, then it may be assumed that compute_maxvar
5209 * has been called on the current band. Otherwise, call
5210 * compute_maxvar if and before carry_dependences gets called.
5212 * If it turns out to be impossible to sort the statements apart,
5213 * because different dependences impose different orderings
5214 * on the statements, then we extend the schedule such that
5215 * it carries at least one more dependence.
5217 static __isl_give isl_schedule_node *sort_statements(
5218 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
5219 int initialized)
5221 isl_ctx *ctx;
5222 isl_union_set_list *filters;
5224 if (!node)
5225 return NULL;
5227 ctx = isl_schedule_node_get_ctx(node);
5228 if (graph->n < 1)
5229 isl_die(ctx, isl_error_internal,
5230 "graph should have at least one node",
5231 return isl_schedule_node_free(node));
5233 if (graph->n == 1)
5234 return node;
5236 if (update_edges(ctx, graph) < 0)
5237 return isl_schedule_node_free(node);
5239 if (graph->n_edge == 0)
5240 return node;
5242 if (detect_sccs(ctx, graph) < 0)
5243 return isl_schedule_node_free(node);
5245 next_band(graph);
5246 if (graph->scc < graph->n) {
5247 if (!initialized && compute_maxvar(graph) < 0)
5248 return isl_schedule_node_free(node);
5249 return carry_dependences(node, graph);
5252 filters = extract_sccs(ctx, graph);
5253 node = isl_schedule_node_insert_sequence(node, filters);
5255 return node;
5258 /* Are there any (non-empty) (conditional) validity edges in the graph?
5260 static int has_validity_edges(struct isl_sched_graph *graph)
5262 int i;
5264 for (i = 0; i < graph->n_edge; ++i) {
5265 int empty;
5267 empty = isl_map_plain_is_empty(graph->edge[i].map);
5268 if (empty < 0)
5269 return -1;
5270 if (empty)
5271 continue;
5272 if (is_any_validity(&graph->edge[i]))
5273 return 1;
5276 return 0;
5279 /* Should we apply a Feautrier step?
5280 * That is, did the user request the Feautrier algorithm and are
5281 * there any validity dependences (left)?
5283 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
5285 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
5286 return 0;
5288 return has_validity_edges(graph);
5291 /* Compute a schedule for a connected dependence graph using Feautrier's
5292 * multi-dimensional scheduling algorithm and return the updated schedule node.
5294 * The original algorithm is described in [1].
5295 * The main idea is to minimize the number of scheduling dimensions, by
5296 * trying to satisfy as many dependences as possible per scheduling dimension.
5298 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
5299 * Problem, Part II: Multi-Dimensional Time.
5300 * In Intl. Journal of Parallel Programming, 1992.
5302 static __isl_give isl_schedule_node *compute_schedule_wcc_feautrier(
5303 isl_schedule_node *node, struct isl_sched_graph *graph)
5305 return carry_feautrier(node, graph);
5308 /* Turn off the "local" bit on all (condition) edges.
5310 static void clear_local_edges(struct isl_sched_graph *graph)
5312 int i;
5314 for (i = 0; i < graph->n_edge; ++i)
5315 if (is_condition(&graph->edge[i]))
5316 clear_local(&graph->edge[i]);
5319 /* Does "graph" have both condition and conditional validity edges?
5321 static int need_condition_check(struct isl_sched_graph *graph)
5323 int i;
5324 int any_condition = 0;
5325 int any_conditional_validity = 0;
5327 for (i = 0; i < graph->n_edge; ++i) {
5328 if (is_condition(&graph->edge[i]))
5329 any_condition = 1;
5330 if (is_conditional_validity(&graph->edge[i]))
5331 any_conditional_validity = 1;
5334 return any_condition && any_conditional_validity;
5337 /* Does "graph" contain any coincidence edge?
5339 static int has_any_coincidence(struct isl_sched_graph *graph)
5341 int i;
5343 for (i = 0; i < graph->n_edge; ++i)
5344 if (is_coincidence(&graph->edge[i]))
5345 return 1;
5347 return 0;
5350 /* Extract the final schedule row as a map with the iteration domain
5351 * of "node" as domain.
5353 static __isl_give isl_map *final_row(struct isl_sched_node *node)
5355 isl_multi_aff *ma;
5356 int row;
5358 row = isl_mat_rows(node->sched) - 1;
5359 ma = node_extract_partial_schedule_multi_aff(node, row, 1);
5360 return isl_map_from_multi_aff(ma);
5363 /* Is the conditional validity dependence in the edge with index "edge_index"
5364 * violated by the latest (i.e., final) row of the schedule?
5365 * That is, is i scheduled after j
5366 * for any conditional validity dependence i -> j?
5368 static int is_violated(struct isl_sched_graph *graph, int edge_index)
5370 isl_map *src_sched, *dst_sched, *map;
5371 struct isl_sched_edge *edge = &graph->edge[edge_index];
5372 int empty;
5374 src_sched = final_row(edge->src);
5375 dst_sched = final_row(edge->dst);
5376 map = isl_map_copy(edge->map);
5377 map = isl_map_apply_domain(map, src_sched);
5378 map = isl_map_apply_range(map, dst_sched);
5379 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);
5380 empty = isl_map_is_empty(map);
5381 isl_map_free(map);
5383 if (empty < 0)
5384 return -1;
5386 return !empty;
5389 /* Does "graph" have any satisfied condition edges that
5390 * are adjacent to the conditional validity constraint with
5391 * domain "conditional_source" and range "conditional_sink"?
5393 * A satisfied condition is one that is not local.
5394 * If a condition was forced to be local already (i.e., marked as local)
5395 * then there is no need to check if it is in fact local.
5397 * Additionally, mark all adjacent condition edges found as local.
5399 static int has_adjacent_true_conditions(struct isl_sched_graph *graph,
5400 __isl_keep isl_union_set *conditional_source,
5401 __isl_keep isl_union_set *conditional_sink)
5403 int i;
5404 int any = 0;
5406 for (i = 0; i < graph->n_edge; ++i) {
5407 int adjacent, local;
5408 isl_union_map *condition;
5410 if (!is_condition(&graph->edge[i]))
5411 continue;
5412 if (is_local(&graph->edge[i]))
5413 continue;
5415 condition = graph->edge[i].tagged_condition;
5416 adjacent = domain_intersects(condition, conditional_sink);
5417 if (adjacent >= 0 && !adjacent)
5418 adjacent = range_intersects(condition,
5419 conditional_source);
5420 if (adjacent < 0)
5421 return -1;
5422 if (!adjacent)
5423 continue;
5425 set_local(&graph->edge[i]);
5427 local = is_condition_false(&graph->edge[i]);
5428 if (local < 0)
5429 return -1;
5430 if (!local)
5431 any = 1;
5434 return any;
5437 /* Are there any violated conditional validity dependences with
5438 * adjacent condition dependences that are not local with respect
5439 * to the current schedule?
5440 * That is, is the conditional validity constraint violated?
5442 * Additionally, mark all those adjacent condition dependences as local.
5443 * We also mark those adjacent condition dependences that were not marked
5444 * as local before, but just happened to be local already. This ensures
5445 * that they remain local if the schedule is recomputed.
5447 * We first collect domain and range of all violated conditional validity
5448 * dependences and then check if there are any adjacent non-local
5449 * condition dependences.
5451 static int has_violated_conditional_constraint(isl_ctx *ctx,
5452 struct isl_sched_graph *graph)
5454 int i;
5455 int any = 0;
5456 isl_union_set *source, *sink;
5458 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
5459 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
5460 for (i = 0; i < graph->n_edge; ++i) {
5461 isl_union_set *uset;
5462 isl_union_map *umap;
5463 int violated;
5465 if (!is_conditional_validity(&graph->edge[i]))
5466 continue;
5468 violated = is_violated(graph, i);
5469 if (violated < 0)
5470 goto error;
5471 if (!violated)
5472 continue;
5474 any = 1;
5476 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
5477 uset = isl_union_map_domain(umap);
5478 source = isl_union_set_union(source, uset);
5479 source = isl_union_set_coalesce(source);
5481 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
5482 uset = isl_union_map_range(umap);
5483 sink = isl_union_set_union(sink, uset);
5484 sink = isl_union_set_coalesce(sink);
5487 if (any)
5488 any = has_adjacent_true_conditions(graph, source, sink);
5490 isl_union_set_free(source);
5491 isl_union_set_free(sink);
5492 return any;
5493 error:
5494 isl_union_set_free(source);
5495 isl_union_set_free(sink);
5496 return -1;
5499 /* Examine the current band (the rows between graph->band_start and
5500 * graph->n_total_row), deciding whether to drop it or add it to "node"
5501 * and then continue with the computation of the next band, if any.
5502 * If "initialized" is set, then it may be assumed that compute_maxvar
5503 * has been called on the current band. Otherwise, call
5504 * compute_maxvar if and before carry_dependences gets called.
5506 * The caller keeps looking for a new row as long as
5507 * graph->n_row < graph->maxvar. If the latest attempt to find
5508 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
5509 * then we either
5510 * - split between SCCs and start over (assuming we found an interesting
5511 * pair of SCCs between which to split)
5512 * - continue with the next band (assuming the current band has at least
5513 * one row)
5514 * - if there is more than one SCC left, then split along all SCCs
5515 * - if outer coincidence needs to be enforced, then try to carry as many
5516 * validity or coincidence dependences as possible and
5517 * continue with the next band
5518 * - try to carry as many validity dependences as possible and
5519 * continue with the next band
5520 * In each case, we first insert a band node in the schedule tree
5521 * if any rows have been computed.
5523 * If the caller managed to complete the schedule and the current band
5524 * is empty, then finish off by topologically
5525 * sorting the statements based on the remaining dependences.
5526 * If, on the other hand, the current band has at least one row,
5527 * then continue with the next band. Note that this next band
5528 * will necessarily be empty, but the graph may still be split up
5529 * into weakly connected components before arriving back here.
5531 static __isl_give isl_schedule_node *compute_schedule_finish_band(
5532 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
5533 int initialized)
5535 int empty;
5537 if (!node)
5538 return NULL;
5540 empty = graph->n_total_row == graph->band_start;
5541 if (graph->n_row < graph->maxvar) {
5542 isl_ctx *ctx;
5544 ctx = isl_schedule_node_get_ctx(node);
5545 if (!ctx->opt->schedule_maximize_band_depth && !empty)
5546 return compute_next_band(node, graph, 1);
5547 if (graph->src_scc >= 0)
5548 return compute_split_schedule(node, graph);
5549 if (!empty)
5550 return compute_next_band(node, graph, 1);
5551 if (graph->scc > 1)
5552 return compute_component_schedule(node, graph, 1);
5553 if (!initialized && compute_maxvar(graph) < 0)
5554 return isl_schedule_node_free(node);
5555 if (isl_options_get_schedule_outer_coincidence(ctx))
5556 return carry_coincidence(node, graph);
5557 return carry_dependences(node, graph);
5560 if (!empty)
5561 return compute_next_band(node, graph, 1);
5562 return sort_statements(node, graph, initialized);
5565 /* Construct a band of schedule rows for a connected dependence graph.
5566 * The caller is responsible for determining the strongly connected
5567 * components and calling compute_maxvar first.
5569 * We try to find a sequence of as many schedule rows as possible that result
5570 * in non-negative dependence distances (independent of the previous rows
5571 * in the sequence, i.e., such that the sequence is tilable), with as
5572 * many of the initial rows as possible satisfying the coincidence constraints.
5573 * The computation stops if we can't find any more rows or if we have found
5574 * all the rows we wanted to find.
5576 * If ctx->opt->schedule_outer_coincidence is set, then we force the
5577 * outermost dimension to satisfy the coincidence constraints. If this
5578 * turns out to be impossible, we fall back on the general scheme above
5579 * and try to carry as many dependences as possible.
5581 * If "graph" contains both condition and conditional validity dependences,
5582 * then we need to check that that the conditional schedule constraint
5583 * is satisfied, i.e., there are no violated conditional validity dependences
5584 * that are adjacent to any non-local condition dependences.
5585 * If there are, then we mark all those adjacent condition dependences
5586 * as local and recompute the current band. Those dependences that
5587 * are marked local will then be forced to be local.
5588 * The initial computation is performed with no dependences marked as local.
5589 * If we are lucky, then there will be no violated conditional validity
5590 * dependences adjacent to any non-local condition dependences.
5591 * Otherwise, we mark some additional condition dependences as local and
5592 * recompute. We continue this process until there are no violations left or
5593 * until we are no longer able to compute a schedule.
5594 * Since there are only a finite number of dependences,
5595 * there will only be a finite number of iterations.
5597 static isl_stat compute_schedule_wcc_band(isl_ctx *ctx,
5598 struct isl_sched_graph *graph)
5600 int has_coincidence;
5601 int use_coincidence;
5602 int force_coincidence = 0;
5603 int check_conditional;
5605 if (sort_sccs(graph) < 0)
5606 return isl_stat_error;
5608 clear_local_edges(graph);
5609 check_conditional = need_condition_check(graph);
5610 has_coincidence = has_any_coincidence(graph);
5612 if (ctx->opt->schedule_outer_coincidence)
5613 force_coincidence = 1;
5615 use_coincidence = has_coincidence;
5616 while (graph->n_row < graph->maxvar) {
5617 isl_vec *sol;
5618 int violated;
5619 int coincident;
5621 graph->src_scc = -1;
5622 graph->dst_scc = -1;
5624 if (setup_lp(ctx, graph, use_coincidence) < 0)
5625 return isl_stat_error;
5626 sol = solve_lp(ctx, graph);
5627 if (!sol)
5628 return isl_stat_error;
5629 if (sol->size == 0) {
5630 int empty = graph->n_total_row == graph->band_start;
5632 isl_vec_free(sol);
5633 if (use_coincidence && (!force_coincidence || !empty)) {
5634 use_coincidence = 0;
5635 continue;
5637 return isl_stat_ok;
5639 coincident = !has_coincidence || use_coincidence;
5640 if (update_schedule(graph, sol, coincident) < 0)
5641 return isl_stat_error;
5643 if (!check_conditional)
5644 continue;
5645 violated = has_violated_conditional_constraint(ctx, graph);
5646 if (violated < 0)
5647 return isl_stat_error;
5648 if (!violated)
5649 continue;
5650 if (reset_band(graph) < 0)
5651 return isl_stat_error;
5652 use_coincidence = has_coincidence;
5655 return isl_stat_ok;
5658 /* Compute a schedule for a connected dependence graph by considering
5659 * the graph as a whole and return the updated schedule node.
5661 * The actual schedule rows of the current band are computed by
5662 * compute_schedule_wcc_band. compute_schedule_finish_band takes
5663 * care of integrating the band into "node" and continuing
5664 * the computation.
5666 static __isl_give isl_schedule_node *compute_schedule_wcc_whole(
5667 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
5669 isl_ctx *ctx;
5671 if (!node)
5672 return NULL;
5674 ctx = isl_schedule_node_get_ctx(node);
5675 if (compute_schedule_wcc_band(ctx, graph) < 0)
5676 return isl_schedule_node_free(node);
5678 return compute_schedule_finish_band(node, graph, 1);
5681 /* Clustering information used by compute_schedule_wcc_clustering.
5683 * "n" is the number of SCCs in the original dependence graph
5684 * "scc" is an array of "n" elements, each representing an SCC
5685 * of the original dependence graph. All entries in the same cluster
5686 * have the same number of schedule rows.
5687 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
5688 * where each cluster is represented by the index of the first SCC
5689 * in the cluster. Initially, each SCC belongs to a cluster containing
5690 * only that SCC.
5692 * "scc_in_merge" is used by merge_clusters_along_edge to keep
5693 * track of which SCCs need to be merged.
5695 * "cluster" contains the merged clusters of SCCs after the clustering
5696 * has completed.
5698 * "scc_node" is a temporary data structure used inside copy_partial.
5699 * For each SCC, it keeps track of the number of nodes in the SCC
5700 * that have already been copied.
5702 struct isl_clustering {
5703 int n;
5704 struct isl_sched_graph *scc;
5705 struct isl_sched_graph *cluster;
5706 int *scc_cluster;
5707 int *scc_node;
5708 int *scc_in_merge;
5711 /* Initialize the clustering data structure "c" from "graph".
5713 * In particular, allocate memory, extract the SCCs from "graph"
5714 * into c->scc, initialize scc_cluster and construct
5715 * a band of schedule rows for each SCC.
5716 * Within each SCC, there is only one SCC by definition.
5717 * Each SCC initially belongs to a cluster containing only that SCC.
5719 static isl_stat clustering_init(isl_ctx *ctx, struct isl_clustering *c,
5720 struct isl_sched_graph *graph)
5722 int i;
5724 c->n = graph->scc;
5725 c->scc = isl_calloc_array(ctx, struct isl_sched_graph, c->n);
5726 c->cluster = isl_calloc_array(ctx, struct isl_sched_graph, c->n);
5727 c->scc_cluster = isl_calloc_array(ctx, int, c->n);
5728 c->scc_node = isl_calloc_array(ctx, int, c->n);
5729 c->scc_in_merge = isl_calloc_array(ctx, int, c->n);
5730 if (!c->scc || !c->cluster ||
5731 !c->scc_cluster || !c->scc_node || !c->scc_in_merge)
5732 return isl_stat_error;
5734 for (i = 0; i < c->n; ++i) {
5735 if (extract_sub_graph(ctx, graph, &node_scc_exactly,
5736 &edge_scc_exactly, i, &c->scc[i]) < 0)
5737 return isl_stat_error;
5738 c->scc[i].scc = 1;
5739 if (compute_maxvar(&c->scc[i]) < 0)
5740 return isl_stat_error;
5741 if (compute_schedule_wcc_band(ctx, &c->scc[i]) < 0)
5742 return isl_stat_error;
5743 c->scc_cluster[i] = i;
5746 return isl_stat_ok;
5749 /* Free all memory allocated for "c".
5751 static void clustering_free(isl_ctx *ctx, struct isl_clustering *c)
5753 int i;
5755 if (c->scc)
5756 for (i = 0; i < c->n; ++i)
5757 graph_free(ctx, &c->scc[i]);
5758 free(c->scc);
5759 if (c->cluster)
5760 for (i = 0; i < c->n; ++i)
5761 graph_free(ctx, &c->cluster[i]);
5762 free(c->cluster);
5763 free(c->scc_cluster);
5764 free(c->scc_node);
5765 free(c->scc_in_merge);
5768 /* Should we refrain from merging the cluster in "graph" with
5769 * any other cluster?
5770 * In particular, is its current schedule band empty and incomplete.
5772 static int bad_cluster(struct isl_sched_graph *graph)
5774 return graph->n_row < graph->maxvar &&
5775 graph->n_total_row == graph->band_start;
5778 /* Is "edge" a proximity edge with a non-empty dependence relation?
5780 static isl_bool is_non_empty_proximity(struct isl_sched_edge *edge)
5782 if (!is_proximity(edge))
5783 return isl_bool_false;
5784 return isl_bool_not(isl_map_plain_is_empty(edge->map));
5787 /* Return the index of an edge in "graph" that can be used to merge
5788 * two clusters in "c".
5789 * Return graph->n_edge if no such edge can be found.
5790 * Return -1 on error.
5792 * In particular, return a proximity edge between two clusters
5793 * that is not marked "no_merge" and such that neither of the
5794 * two clusters has an incomplete, empty band.
5796 * If there are multiple such edges, then try and find the most
5797 * appropriate edge to use for merging. In particular, pick the edge
5798 * with the greatest weight. If there are multiple of those,
5799 * then pick one with the shortest distance between
5800 * the two cluster representatives.
5802 static int find_proximity(struct isl_sched_graph *graph,
5803 struct isl_clustering *c)
5805 int i, best = graph->n_edge, best_dist, best_weight;
5807 for (i = 0; i < graph->n_edge; ++i) {
5808 struct isl_sched_edge *edge = &graph->edge[i];
5809 int dist, weight;
5810 isl_bool prox;
5812 prox = is_non_empty_proximity(edge);
5813 if (prox < 0)
5814 return -1;
5815 if (!prox)
5816 continue;
5817 if (edge->no_merge)
5818 continue;
5819 if (bad_cluster(&c->scc[edge->src->scc]) ||
5820 bad_cluster(&c->scc[edge->dst->scc]))
5821 continue;
5822 dist = c->scc_cluster[edge->dst->scc] -
5823 c->scc_cluster[edge->src->scc];
5824 if (dist == 0)
5825 continue;
5826 weight = edge->weight;
5827 if (best < graph->n_edge) {
5828 if (best_weight > weight)
5829 continue;
5830 if (best_weight == weight && best_dist <= dist)
5831 continue;
5833 best = i;
5834 best_dist = dist;
5835 best_weight = weight;
5838 return best;
5841 /* Internal data structure used in mark_merge_sccs.
5843 * "graph" is the dependence graph in which a strongly connected
5844 * component is constructed.
5845 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
5846 * "src" and "dst" are the indices of the nodes that are being merged.
5848 struct isl_mark_merge_sccs_data {
5849 struct isl_sched_graph *graph;
5850 int *scc_cluster;
5851 int src;
5852 int dst;
5855 /* Check whether the cluster containing node "i" depends on the cluster
5856 * containing node "j". If "i" and "j" belong to the same cluster,
5857 * then they are taken to depend on each other to ensure that
5858 * the resulting strongly connected component consists of complete
5859 * clusters. Furthermore, if "i" and "j" are the two nodes that
5860 * are being merged, then they are taken to depend on each other as well.
5861 * Otherwise, check if there is a (conditional) validity dependence
5862 * from node[j] to node[i], forcing node[i] to follow node[j].
5864 static isl_bool cluster_follows(int i, int j, void *user)
5866 struct isl_mark_merge_sccs_data *data = user;
5867 struct isl_sched_graph *graph = data->graph;
5868 int *scc_cluster = data->scc_cluster;
5870 if (data->src == i && data->dst == j)
5871 return isl_bool_true;
5872 if (data->src == j && data->dst == i)
5873 return isl_bool_true;
5874 if (scc_cluster[graph->node[i].scc] == scc_cluster[graph->node[j].scc])
5875 return isl_bool_true;
5877 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
5880 /* Mark all SCCs that belong to either of the two clusters in "c"
5881 * connected by the edge in "graph" with index "edge", or to any
5882 * of the intermediate clusters.
5883 * The marking is recorded in c->scc_in_merge.
5885 * The given edge has been selected for merging two clusters,
5886 * meaning that there is at least a proximity edge between the two nodes.
5887 * However, there may also be (indirect) validity dependences
5888 * between the two nodes. When merging the two clusters, all clusters
5889 * containing one or more of the intermediate nodes along the
5890 * indirect validity dependences need to be merged in as well.
5892 * First collect all such nodes by computing the strongly connected
5893 * component (SCC) containing the two nodes connected by the edge, where
5894 * the two nodes are considered to depend on each other to make
5895 * sure they end up in the same SCC. Similarly, each node is considered
5896 * to depend on every other node in the same cluster to ensure
5897 * that the SCC consists of complete clusters.
5899 * Then the original SCCs that contain any of these nodes are marked
5900 * in c->scc_in_merge.
5902 static isl_stat mark_merge_sccs(isl_ctx *ctx, struct isl_sched_graph *graph,
5903 int edge, struct isl_clustering *c)
5905 struct isl_mark_merge_sccs_data data;
5906 struct isl_tarjan_graph *g;
5907 int i;
5909 for (i = 0; i < c->n; ++i)
5910 c->scc_in_merge[i] = 0;
5912 data.graph = graph;
5913 data.scc_cluster = c->scc_cluster;
5914 data.src = graph->edge[edge].src - graph->node;
5915 data.dst = graph->edge[edge].dst - graph->node;
5917 g = isl_tarjan_graph_component(ctx, graph->n, data.dst,
5918 &cluster_follows, &data);
5919 if (!g)
5920 goto error;
5922 i = g->op;
5923 if (i < 3)
5924 isl_die(ctx, isl_error_internal,
5925 "expecting at least two nodes in component",
5926 goto error);
5927 if (g->order[--i] != -1)
5928 isl_die(ctx, isl_error_internal,
5929 "expecting end of component marker", goto error);
5931 for (--i; i >= 0 && g->order[i] != -1; --i) {
5932 int scc = graph->node[g->order[i]].scc;
5933 c->scc_in_merge[scc] = 1;
5936 isl_tarjan_graph_free(g);
5937 return isl_stat_ok;
5938 error:
5939 isl_tarjan_graph_free(g);
5940 return isl_stat_error;
5943 /* Construct the identifier "cluster_i".
5945 static __isl_give isl_id *cluster_id(isl_ctx *ctx, int i)
5947 char name[40];
5949 snprintf(name, sizeof(name), "cluster_%d", i);
5950 return isl_id_alloc(ctx, name, NULL);
5953 /* Construct the space of the cluster with index "i" containing
5954 * the strongly connected component "scc".
5956 * In particular, construct a space called cluster_i with dimension equal
5957 * to the number of schedule rows in the current band of "scc".
5959 static __isl_give isl_space *cluster_space(struct isl_sched_graph *scc, int i)
5961 int nvar;
5962 isl_space *space;
5963 isl_id *id;
5965 nvar = scc->n_total_row - scc->band_start;
5966 space = isl_space_copy(scc->node[0].space);
5967 space = isl_space_params(space);
5968 space = isl_space_set_from_params(space);
5969 space = isl_space_add_dims(space, isl_dim_set, nvar);
5970 id = cluster_id(isl_space_get_ctx(space), i);
5971 space = isl_space_set_tuple_id(space, isl_dim_set, id);
5973 return space;
5976 /* Collect the domain of the graph for merging clusters.
5978 * In particular, for each cluster with first SCC "i", construct
5979 * a set in the space called cluster_i with dimension equal
5980 * to the number of schedule rows in the current band of the cluster.
5982 static __isl_give isl_union_set *collect_domain(isl_ctx *ctx,
5983 struct isl_sched_graph *graph, struct isl_clustering *c)
5985 int i;
5986 isl_space *space;
5987 isl_union_set *domain;
5989 space = isl_space_params_alloc(ctx, 0);
5990 domain = isl_union_set_empty(space);
5992 for (i = 0; i < graph->scc; ++i) {
5993 isl_space *space;
5995 if (!c->scc_in_merge[i])
5996 continue;
5997 if (c->scc_cluster[i] != i)
5998 continue;
5999 space = cluster_space(&c->scc[i], i);
6000 domain = isl_union_set_add_set(domain, isl_set_universe(space));
6003 return domain;
6006 /* Construct a map from the original instances to the corresponding
6007 * cluster instance in the current bands of the clusters in "c".
6009 static __isl_give isl_union_map *collect_cluster_map(isl_ctx *ctx,
6010 struct isl_sched_graph *graph, struct isl_clustering *c)
6012 int i, j;
6013 isl_space *space;
6014 isl_union_map *cluster_map;
6016 space = isl_space_params_alloc(ctx, 0);
6017 cluster_map = isl_union_map_empty(space);
6018 for (i = 0; i < graph->scc; ++i) {
6019 int start, n;
6020 isl_id *id;
6022 if (!c->scc_in_merge[i])
6023 continue;
6025 id = cluster_id(ctx, c->scc_cluster[i]);
6026 start = c->scc[i].band_start;
6027 n = c->scc[i].n_total_row - start;
6028 for (j = 0; j < c->scc[i].n; ++j) {
6029 isl_multi_aff *ma;
6030 isl_map *map;
6031 struct isl_sched_node *node = &c->scc[i].node[j];
6033 ma = node_extract_partial_schedule_multi_aff(node,
6034 start, n);
6035 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out,
6036 isl_id_copy(id));
6037 map = isl_map_from_multi_aff(ma);
6038 cluster_map = isl_union_map_add_map(cluster_map, map);
6040 isl_id_free(id);
6043 return cluster_map;
6046 /* Add "umap" to the schedule constraints "sc" of all types of "edge"
6047 * that are not isl_edge_condition or isl_edge_conditional_validity.
6049 static __isl_give isl_schedule_constraints *add_non_conditional_constraints(
6050 struct isl_sched_edge *edge, __isl_keep isl_union_map *umap,
6051 __isl_take isl_schedule_constraints *sc)
6053 enum isl_edge_type t;
6055 if (!sc)
6056 return NULL;
6058 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
6059 if (t == isl_edge_condition ||
6060 t == isl_edge_conditional_validity)
6061 continue;
6062 if (!is_type(edge, t))
6063 continue;
6064 sc = isl_schedule_constraints_add(sc, t,
6065 isl_union_map_copy(umap));
6068 return sc;
6071 /* Add schedule constraints of types isl_edge_condition and
6072 * isl_edge_conditional_validity to "sc" by applying "umap" to
6073 * the domains of the wrapped relations in domain and range
6074 * of the corresponding tagged constraints of "edge".
6076 static __isl_give isl_schedule_constraints *add_conditional_constraints(
6077 struct isl_sched_edge *edge, __isl_keep isl_union_map *umap,
6078 __isl_take isl_schedule_constraints *sc)
6080 enum isl_edge_type t;
6081 isl_union_map *tagged;
6083 for (t = isl_edge_condition; t <= isl_edge_conditional_validity; ++t) {
6084 if (!is_type(edge, t))
6085 continue;
6086 if (t == isl_edge_condition)
6087 tagged = isl_union_map_copy(edge->tagged_condition);
6088 else
6089 tagged = isl_union_map_copy(edge->tagged_validity);
6090 tagged = isl_union_map_zip(tagged);
6091 tagged = isl_union_map_apply_domain(tagged,
6092 isl_union_map_copy(umap));
6093 tagged = isl_union_map_zip(tagged);
6094 sc = isl_schedule_constraints_add(sc, t, tagged);
6095 if (!sc)
6096 return NULL;
6099 return sc;
6102 /* Given a mapping "cluster_map" from the original instances to
6103 * the cluster instances, add schedule constraints on the clusters
6104 * to "sc" corresponding to the original constraints represented by "edge".
6106 * For non-tagged dependence constraints, the cluster constraints
6107 * are obtained by applying "cluster_map" to the edge->map.
6109 * For tagged dependence constraints, "cluster_map" needs to be applied
6110 * to the domains of the wrapped relations in domain and range
6111 * of the tagged dependence constraints. Pick out the mappings
6112 * from these domains from "cluster_map" and construct their product.
6113 * This mapping can then be applied to the pair of domains.
6115 static __isl_give isl_schedule_constraints *collect_edge_constraints(
6116 struct isl_sched_edge *edge, __isl_keep isl_union_map *cluster_map,
6117 __isl_take isl_schedule_constraints *sc)
6119 isl_union_map *umap;
6120 isl_space *space;
6121 isl_union_set *uset;
6122 isl_union_map *umap1, *umap2;
6124 if (!sc)
6125 return NULL;
6127 umap = isl_union_map_from_map(isl_map_copy(edge->map));
6128 umap = isl_union_map_apply_domain(umap,
6129 isl_union_map_copy(cluster_map));
6130 umap = isl_union_map_apply_range(umap,
6131 isl_union_map_copy(cluster_map));
6132 sc = add_non_conditional_constraints(edge, umap, sc);
6133 isl_union_map_free(umap);
6135 if (!sc || (!is_condition(edge) && !is_conditional_validity(edge)))
6136 return sc;
6138 space = isl_space_domain(isl_map_get_space(edge->map));
6139 uset = isl_union_set_from_set(isl_set_universe(space));
6140 umap1 = isl_union_map_copy(cluster_map);
6141 umap1 = isl_union_map_intersect_domain(umap1, uset);
6142 space = isl_space_range(isl_map_get_space(edge->map));
6143 uset = isl_union_set_from_set(isl_set_universe(space));
6144 umap2 = isl_union_map_copy(cluster_map);
6145 umap2 = isl_union_map_intersect_domain(umap2, uset);
6146 umap = isl_union_map_product(umap1, umap2);
6148 sc = add_conditional_constraints(edge, umap, sc);
6150 isl_union_map_free(umap);
6151 return sc;
6154 /* Given a mapping "cluster_map" from the original instances to
6155 * the cluster instances, add schedule constraints on the clusters
6156 * to "sc" corresponding to all edges in "graph" between nodes that
6157 * belong to SCCs that are marked for merging in "scc_in_merge".
6159 static __isl_give isl_schedule_constraints *collect_constraints(
6160 struct isl_sched_graph *graph, int *scc_in_merge,
6161 __isl_keep isl_union_map *cluster_map,
6162 __isl_take isl_schedule_constraints *sc)
6164 int i;
6166 for (i = 0; i < graph->n_edge; ++i) {
6167 struct isl_sched_edge *edge = &graph->edge[i];
6169 if (!scc_in_merge[edge->src->scc])
6170 continue;
6171 if (!scc_in_merge[edge->dst->scc])
6172 continue;
6173 sc = collect_edge_constraints(edge, cluster_map, sc);
6176 return sc;
6179 /* Construct a dependence graph for scheduling clusters with respect
6180 * to each other and store the result in "merge_graph".
6181 * In particular, the nodes of the graph correspond to the schedule
6182 * dimensions of the current bands of those clusters that have been
6183 * marked for merging in "c".
6185 * First construct an isl_schedule_constraints object for this domain
6186 * by transforming the edges in "graph" to the domain.
6187 * Then initialize a dependence graph for scheduling from these
6188 * constraints.
6190 static isl_stat init_merge_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
6191 struct isl_clustering *c, struct isl_sched_graph *merge_graph)
6193 isl_union_set *domain;
6194 isl_union_map *cluster_map;
6195 isl_schedule_constraints *sc;
6196 isl_stat r;
6198 domain = collect_domain(ctx, graph, c);
6199 sc = isl_schedule_constraints_on_domain(domain);
6200 if (!sc)
6201 return isl_stat_error;
6202 cluster_map = collect_cluster_map(ctx, graph, c);
6203 sc = collect_constraints(graph, c->scc_in_merge, cluster_map, sc);
6204 isl_union_map_free(cluster_map);
6206 r = graph_init(merge_graph, sc);
6208 isl_schedule_constraints_free(sc);
6210 return r;
6213 /* Compute the maximal number of remaining schedule rows that still need
6214 * to be computed for the nodes that belong to clusters with the maximal
6215 * dimension for the current band (i.e., the band that is to be merged).
6216 * Only clusters that are about to be merged are considered.
6217 * "maxvar" is the maximal dimension for the current band.
6218 * "c" contains information about the clusters.
6220 * Return the maximal number of remaining schedule rows or -1 on error.
6222 static int compute_maxvar_max_slack(int maxvar, struct isl_clustering *c)
6224 int i, j;
6225 int max_slack;
6227 max_slack = 0;
6228 for (i = 0; i < c->n; ++i) {
6229 int nvar;
6230 struct isl_sched_graph *scc;
6232 if (!c->scc_in_merge[i])
6233 continue;
6234 scc = &c->scc[i];
6235 nvar = scc->n_total_row - scc->band_start;
6236 if (nvar != maxvar)
6237 continue;
6238 for (j = 0; j < scc->n; ++j) {
6239 struct isl_sched_node *node = &scc->node[j];
6240 int slack;
6242 if (node_update_vmap(node) < 0)
6243 return -1;
6244 slack = node->nvar - node->rank;
6245 if (slack > max_slack)
6246 max_slack = slack;
6250 return max_slack;
6253 /* If there are any clusters where the dimension of the current band
6254 * (i.e., the band that is to be merged) is smaller than "maxvar" and
6255 * if there are any nodes in such a cluster where the number
6256 * of remaining schedule rows that still need to be computed
6257 * is greater than "max_slack", then return the smallest current band
6258 * dimension of all these clusters. Otherwise return the original value
6259 * of "maxvar". Return -1 in case of any error.
6260 * Only clusters that are about to be merged are considered.
6261 * "c" contains information about the clusters.
6263 static int limit_maxvar_to_slack(int maxvar, int max_slack,
6264 struct isl_clustering *c)
6266 int i, j;
6268 for (i = 0; i < c->n; ++i) {
6269 int nvar;
6270 struct isl_sched_graph *scc;
6272 if (!c->scc_in_merge[i])
6273 continue;
6274 scc = &c->scc[i];
6275 nvar = scc->n_total_row - scc->band_start;
6276 if (nvar >= maxvar)
6277 continue;
6278 for (j = 0; j < scc->n; ++j) {
6279 struct isl_sched_node *node = &scc->node[j];
6280 int slack;
6282 if (node_update_vmap(node) < 0)
6283 return -1;
6284 slack = node->nvar - node->rank;
6285 if (slack > max_slack) {
6286 maxvar = nvar;
6287 break;
6292 return maxvar;
6295 /* Adjust merge_graph->maxvar based on the number of remaining schedule rows
6296 * that still need to be computed. In particular, if there is a node
6297 * in a cluster where the dimension of the current band is smaller
6298 * than merge_graph->maxvar, but the number of remaining schedule rows
6299 * is greater than that of any node in a cluster with the maximal
6300 * dimension for the current band (i.e., merge_graph->maxvar),
6301 * then adjust merge_graph->maxvar to the (smallest) current band dimension
6302 * of those clusters. Without this adjustment, the total number of
6303 * schedule dimensions would be increased, resulting in a skewed view
6304 * of the number of coincident dimensions.
6305 * "c" contains information about the clusters.
6307 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
6308 * then there is no point in attempting any merge since it will be rejected
6309 * anyway. Set merge_graph->maxvar to zero in such cases.
6311 static isl_stat adjust_maxvar_to_slack(isl_ctx *ctx,
6312 struct isl_sched_graph *merge_graph, struct isl_clustering *c)
6314 int max_slack, maxvar;
6316 max_slack = compute_maxvar_max_slack(merge_graph->maxvar, c);
6317 if (max_slack < 0)
6318 return isl_stat_error;
6319 maxvar = limit_maxvar_to_slack(merge_graph->maxvar, max_slack, c);
6320 if (maxvar < 0)
6321 return isl_stat_error;
6323 if (maxvar < merge_graph->maxvar) {
6324 if (isl_options_get_schedule_maximize_band_depth(ctx))
6325 merge_graph->maxvar = 0;
6326 else
6327 merge_graph->maxvar = maxvar;
6330 return isl_stat_ok;
6333 /* Return the number of coincident dimensions in the current band of "graph",
6334 * where the nodes of "graph" are assumed to be scheduled by a single band.
6336 static int get_n_coincident(struct isl_sched_graph *graph)
6338 int i;
6340 for (i = graph->band_start; i < graph->n_total_row; ++i)
6341 if (!graph->node[0].coincident[i])
6342 break;
6344 return i - graph->band_start;
6347 /* Should the clusters be merged based on the cluster schedule
6348 * in the current (and only) band of "merge_graph", given that
6349 * coincidence should be maximized?
6351 * If the number of coincident schedule dimensions in the merged band
6352 * would be less than the maximal number of coincident schedule dimensions
6353 * in any of the merged clusters, then the clusters should not be merged.
6355 static isl_bool ok_to_merge_coincident(struct isl_clustering *c,
6356 struct isl_sched_graph *merge_graph)
6358 int i;
6359 int n_coincident;
6360 int max_coincident;
6362 max_coincident = 0;
6363 for (i = 0; i < c->n; ++i) {
6364 if (!c->scc_in_merge[i])
6365 continue;
6366 n_coincident = get_n_coincident(&c->scc[i]);
6367 if (n_coincident > max_coincident)
6368 max_coincident = n_coincident;
6371 n_coincident = get_n_coincident(merge_graph);
6373 return n_coincident >= max_coincident;
6376 /* Return the transformation on "node" expressed by the current (and only)
6377 * band of "merge_graph" applied to the clusters in "c".
6379 * First find the representation of "node" in its SCC in "c" and
6380 * extract the transformation expressed by the current band.
6381 * Then extract the transformation applied by "merge_graph"
6382 * to the cluster to which this SCC belongs.
6383 * Combine the two to obtain the complete transformation on the node.
6385 * Note that the range of the first transformation is an anonymous space,
6386 * while the domain of the second is named "cluster_X". The range
6387 * of the former therefore needs to be adjusted before the two
6388 * can be combined.
6390 static __isl_give isl_map *extract_node_transformation(isl_ctx *ctx,
6391 struct isl_sched_node *node, struct isl_clustering *c,
6392 struct isl_sched_graph *merge_graph)
6394 struct isl_sched_node *scc_node, *cluster_node;
6395 int start, n;
6396 isl_id *id;
6397 isl_space *space;
6398 isl_multi_aff *ma, *ma2;
6400 scc_node = graph_find_node(ctx, &c->scc[node->scc], node->space);
6401 start = c->scc[node->scc].band_start;
6402 n = c->scc[node->scc].n_total_row - start;
6403 ma = node_extract_partial_schedule_multi_aff(scc_node, start, n);
6404 space = cluster_space(&c->scc[node->scc], c->scc_cluster[node->scc]);
6405 cluster_node = graph_find_node(ctx, merge_graph, space);
6406 if (space && !cluster_node)
6407 isl_die(ctx, isl_error_internal, "unable to find cluster",
6408 space = isl_space_free(space));
6409 id = isl_space_get_tuple_id(space, isl_dim_set);
6410 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out, id);
6411 isl_space_free(space);
6412 n = merge_graph->n_total_row;
6413 ma2 = node_extract_partial_schedule_multi_aff(cluster_node, 0, n);
6414 ma = isl_multi_aff_pullback_multi_aff(ma2, ma);
6416 return isl_map_from_multi_aff(ma);
6419 /* Give a set of distances "set", are they bounded by a small constant
6420 * in direction "pos"?
6421 * In practice, check if they are bounded by 2 by checking that there
6422 * are no elements with a value greater than or equal to 3 or
6423 * smaller than or equal to -3.
6425 static isl_bool distance_is_bounded(__isl_keep isl_set *set, int pos)
6427 isl_bool bounded;
6428 isl_set *test;
6430 if (!set)
6431 return isl_bool_error;
6433 test = isl_set_copy(set);
6434 test = isl_set_lower_bound_si(test, isl_dim_set, pos, 3);
6435 bounded = isl_set_is_empty(test);
6436 isl_set_free(test);
6438 if (bounded < 0 || !bounded)
6439 return bounded;
6441 test = isl_set_copy(set);
6442 test = isl_set_upper_bound_si(test, isl_dim_set, pos, -3);
6443 bounded = isl_set_is_empty(test);
6444 isl_set_free(test);
6446 return bounded;
6449 /* Does the set "set" have a fixed (but possible parametric) value
6450 * at dimension "pos"?
6452 static isl_bool has_single_value(__isl_keep isl_set *set, int pos)
6454 int n;
6455 isl_bool single;
6457 if (!set)
6458 return isl_bool_error;
6459 set = isl_set_copy(set);
6460 n = isl_set_dim(set, isl_dim_set);
6461 set = isl_set_project_out(set, isl_dim_set, pos + 1, n - (pos + 1));
6462 set = isl_set_project_out(set, isl_dim_set, 0, pos);
6463 single = isl_set_is_singleton(set);
6464 isl_set_free(set);
6466 return single;
6469 /* Does "map" have a fixed (but possible parametric) value
6470 * at dimension "pos" of either its domain or its range?
6472 static isl_bool has_singular_src_or_dst(__isl_keep isl_map *map, int pos)
6474 isl_set *set;
6475 isl_bool single;
6477 set = isl_map_domain(isl_map_copy(map));
6478 single = has_single_value(set, pos);
6479 isl_set_free(set);
6481 if (single < 0 || single)
6482 return single;
6484 set = isl_map_range(isl_map_copy(map));
6485 single = has_single_value(set, pos);
6486 isl_set_free(set);
6488 return single;
6491 /* Does the edge "edge" from "graph" have bounded dependence distances
6492 * in the merged graph "merge_graph" of a selection of clusters in "c"?
6494 * Extract the complete transformations of the source and destination
6495 * nodes of the edge, apply them to the edge constraints and
6496 * compute the differences. Finally, check if these differences are bounded
6497 * in each direction.
6499 * If the dimension of the band is greater than the number of
6500 * dimensions that can be expected to be optimized by the edge
6501 * (based on its weight), then also allow the differences to be unbounded
6502 * in the remaining dimensions, but only if either the source or
6503 * the destination has a fixed value in that direction.
6504 * This allows a statement that produces values that are used by
6505 * several instances of another statement to be merged with that
6506 * other statement.
6507 * However, merging such clusters will introduce an inherently
6508 * large proximity distance inside the merged cluster, meaning
6509 * that proximity distances will no longer be optimized in
6510 * subsequent merges. These merges are therefore only allowed
6511 * after all other possible merges have been tried.
6512 * The first time such a merge is encountered, the weight of the edge
6513 * is replaced by a negative weight. The second time (i.e., after
6514 * all merges over edges with a non-negative weight have been tried),
6515 * the merge is allowed.
6517 static isl_bool has_bounded_distances(isl_ctx *ctx, struct isl_sched_edge *edge,
6518 struct isl_sched_graph *graph, struct isl_clustering *c,
6519 struct isl_sched_graph *merge_graph)
6521 int i, n, n_slack;
6522 isl_bool bounded;
6523 isl_map *map, *t;
6524 isl_set *dist;
6526 map = isl_map_copy(edge->map);
6527 t = extract_node_transformation(ctx, edge->src, c, merge_graph);
6528 map = isl_map_apply_domain(map, t);
6529 t = extract_node_transformation(ctx, edge->dst, c, merge_graph);
6530 map = isl_map_apply_range(map, t);
6531 dist = isl_map_deltas(isl_map_copy(map));
6533 bounded = isl_bool_true;
6534 n = isl_set_dim(dist, isl_dim_set);
6535 n_slack = n - edge->weight;
6536 if (edge->weight < 0)
6537 n_slack -= graph->max_weight + 1;
6538 for (i = 0; i < n; ++i) {
6539 isl_bool bounded_i, singular_i;
6541 bounded_i = distance_is_bounded(dist, i);
6542 if (bounded_i < 0)
6543 goto error;
6544 if (bounded_i)
6545 continue;
6546 if (edge->weight >= 0)
6547 bounded = isl_bool_false;
6548 n_slack--;
6549 if (n_slack < 0)
6550 break;
6551 singular_i = has_singular_src_or_dst(map, i);
6552 if (singular_i < 0)
6553 goto error;
6554 if (singular_i)
6555 continue;
6556 bounded = isl_bool_false;
6557 break;
6559 if (!bounded && i >= n && edge->weight >= 0)
6560 edge->weight -= graph->max_weight + 1;
6561 isl_map_free(map);
6562 isl_set_free(dist);
6564 return bounded;
6565 error:
6566 isl_map_free(map);
6567 isl_set_free(dist);
6568 return isl_bool_error;
6571 /* Should the clusters be merged based on the cluster schedule
6572 * in the current (and only) band of "merge_graph"?
6573 * "graph" is the original dependence graph, while "c" records
6574 * which SCCs are involved in the latest merge.
6576 * In particular, is there at least one proximity constraint
6577 * that is optimized by the merge?
6579 * A proximity constraint is considered to be optimized
6580 * if the dependence distances are small.
6582 static isl_bool ok_to_merge_proximity(isl_ctx *ctx,
6583 struct isl_sched_graph *graph, struct isl_clustering *c,
6584 struct isl_sched_graph *merge_graph)
6586 int i;
6588 for (i = 0; i < graph->n_edge; ++i) {
6589 struct isl_sched_edge *edge = &graph->edge[i];
6590 isl_bool bounded;
6592 if (!is_proximity(edge))
6593 continue;
6594 if (!c->scc_in_merge[edge->src->scc])
6595 continue;
6596 if (!c->scc_in_merge[edge->dst->scc])
6597 continue;
6598 if (c->scc_cluster[edge->dst->scc] ==
6599 c->scc_cluster[edge->src->scc])
6600 continue;
6601 bounded = has_bounded_distances(ctx, edge, graph, c,
6602 merge_graph);
6603 if (bounded < 0 || bounded)
6604 return bounded;
6607 return isl_bool_false;
6610 /* Should the clusters be merged based on the cluster schedule
6611 * in the current (and only) band of "merge_graph"?
6612 * "graph" is the original dependence graph, while "c" records
6613 * which SCCs are involved in the latest merge.
6615 * If the current band is empty, then the clusters should not be merged.
6617 * If the band depth should be maximized and the merge schedule
6618 * is incomplete (meaning that the dimension of some of the schedule
6619 * bands in the original schedule will be reduced), then the clusters
6620 * should not be merged.
6622 * If the schedule_maximize_coincidence option is set, then check that
6623 * the number of coincident schedule dimensions is not reduced.
6625 * Finally, only allow the merge if at least one proximity
6626 * constraint is optimized.
6628 static isl_bool ok_to_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
6629 struct isl_clustering *c, struct isl_sched_graph *merge_graph)
6631 if (merge_graph->n_total_row == merge_graph->band_start)
6632 return isl_bool_false;
6634 if (isl_options_get_schedule_maximize_band_depth(ctx) &&
6635 merge_graph->n_total_row < merge_graph->maxvar)
6636 return isl_bool_false;
6638 if (isl_options_get_schedule_maximize_coincidence(ctx)) {
6639 isl_bool ok;
6641 ok = ok_to_merge_coincident(c, merge_graph);
6642 if (ok < 0 || !ok)
6643 return ok;
6646 return ok_to_merge_proximity(ctx, graph, c, merge_graph);
6649 /* Apply the schedule in "t_node" to the "n" rows starting at "first"
6650 * of the schedule in "node" and return the result.
6652 * That is, essentially compute
6654 * T * N(first:first+n-1)
6656 * taking into account the constant term and the parameter coefficients
6657 * in "t_node".
6659 static __isl_give isl_mat *node_transformation(isl_ctx *ctx,
6660 struct isl_sched_node *t_node, struct isl_sched_node *node,
6661 int first, int n)
6663 int i, j;
6664 isl_mat *t;
6665 int n_row, n_col, n_param, n_var;
6667 n_param = node->nparam;
6668 n_var = node->nvar;
6669 n_row = isl_mat_rows(t_node->sched);
6670 n_col = isl_mat_cols(node->sched);
6671 t = isl_mat_alloc(ctx, n_row, n_col);
6672 if (!t)
6673 return NULL;
6674 for (i = 0; i < n_row; ++i) {
6675 isl_seq_cpy(t->row[i], t_node->sched->row[i], 1 + n_param);
6676 isl_seq_clr(t->row[i] + 1 + n_param, n_var);
6677 for (j = 0; j < n; ++j)
6678 isl_seq_addmul(t->row[i],
6679 t_node->sched->row[i][1 + n_param + j],
6680 node->sched->row[first + j],
6681 1 + n_param + n_var);
6683 return t;
6686 /* Apply the cluster schedule in "t_node" to the current band
6687 * schedule of the nodes in "graph".
6689 * In particular, replace the rows starting at band_start
6690 * by the result of applying the cluster schedule in "t_node"
6691 * to the original rows.
6693 * The coincidence of the schedule is determined by the coincidence
6694 * of the cluster schedule.
6696 static isl_stat transform(isl_ctx *ctx, struct isl_sched_graph *graph,
6697 struct isl_sched_node *t_node)
6699 int i, j;
6700 int n_new;
6701 int start, n;
6703 start = graph->band_start;
6704 n = graph->n_total_row - start;
6706 n_new = isl_mat_rows(t_node->sched);
6707 for (i = 0; i < graph->n; ++i) {
6708 struct isl_sched_node *node = &graph->node[i];
6709 isl_mat *t;
6711 t = node_transformation(ctx, t_node, node, start, n);
6712 node->sched = isl_mat_drop_rows(node->sched, start, n);
6713 node->sched = isl_mat_concat(node->sched, t);
6714 node->sched_map = isl_map_free(node->sched_map);
6715 if (!node->sched)
6716 return isl_stat_error;
6717 for (j = 0; j < n_new; ++j)
6718 node->coincident[start + j] = t_node->coincident[j];
6720 graph->n_total_row -= n;
6721 graph->n_row -= n;
6722 graph->n_total_row += n_new;
6723 graph->n_row += n_new;
6725 return isl_stat_ok;
6728 /* Merge the clusters marked for merging in "c" into a single
6729 * cluster using the cluster schedule in the current band of "merge_graph".
6730 * The representative SCC for the new cluster is the SCC with
6731 * the smallest index.
6733 * The current band schedule of each SCC in the new cluster is obtained
6734 * by applying the schedule of the corresponding original cluster
6735 * to the original band schedule.
6736 * All SCCs in the new cluster have the same number of schedule rows.
6738 static isl_stat merge(isl_ctx *ctx, struct isl_clustering *c,
6739 struct isl_sched_graph *merge_graph)
6741 int i;
6742 int cluster = -1;
6743 isl_space *space;
6745 for (i = 0; i < c->n; ++i) {
6746 struct isl_sched_node *node;
6748 if (!c->scc_in_merge[i])
6749 continue;
6750 if (cluster < 0)
6751 cluster = i;
6752 space = cluster_space(&c->scc[i], c->scc_cluster[i]);
6753 if (!space)
6754 return isl_stat_error;
6755 node = graph_find_node(ctx, merge_graph, space);
6756 isl_space_free(space);
6757 if (!node)
6758 isl_die(ctx, isl_error_internal,
6759 "unable to find cluster",
6760 return isl_stat_error);
6761 if (transform(ctx, &c->scc[i], node) < 0)
6762 return isl_stat_error;
6763 c->scc_cluster[i] = cluster;
6766 return isl_stat_ok;
6769 /* Try and merge the clusters of SCCs marked in c->scc_in_merge
6770 * by scheduling the current cluster bands with respect to each other.
6772 * Construct a dependence graph with a space for each cluster and
6773 * with the coordinates of each space corresponding to the schedule
6774 * dimensions of the current band of that cluster.
6775 * Construct a cluster schedule in this cluster dependence graph and
6776 * apply it to the current cluster bands if it is applicable
6777 * according to ok_to_merge.
6779 * If the number of remaining schedule dimensions in a cluster
6780 * with a non-maximal current schedule dimension is greater than
6781 * the number of remaining schedule dimensions in clusters
6782 * with a maximal current schedule dimension, then restrict
6783 * the number of rows to be computed in the cluster schedule
6784 * to the minimal such non-maximal current schedule dimension.
6785 * Do this by adjusting merge_graph.maxvar.
6787 * Return isl_bool_true if the clusters have effectively been merged
6788 * into a single cluster.
6790 * Note that since the standard scheduling algorithm minimizes the maximal
6791 * distance over proximity constraints, the proximity constraints between
6792 * the merged clusters may not be optimized any further than what is
6793 * sufficient to bring the distances within the limits of the internal
6794 * proximity constraints inside the individual clusters.
6795 * It may therefore make sense to perform an additional translation step
6796 * to bring the clusters closer to each other, while maintaining
6797 * the linear part of the merging schedule found using the standard
6798 * scheduling algorithm.
6800 static isl_bool try_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
6801 struct isl_clustering *c)
6803 struct isl_sched_graph merge_graph = { 0 };
6804 isl_bool merged;
6806 if (init_merge_graph(ctx, graph, c, &merge_graph) < 0)
6807 goto error;
6809 if (compute_maxvar(&merge_graph) < 0)
6810 goto error;
6811 if (adjust_maxvar_to_slack(ctx, &merge_graph,c) < 0)
6812 goto error;
6813 if (compute_schedule_wcc_band(ctx, &merge_graph) < 0)
6814 goto error;
6815 merged = ok_to_merge(ctx, graph, c, &merge_graph);
6816 if (merged && merge(ctx, c, &merge_graph) < 0)
6817 goto error;
6819 graph_free(ctx, &merge_graph);
6820 return merged;
6821 error:
6822 graph_free(ctx, &merge_graph);
6823 return isl_bool_error;
6826 /* Is there any edge marked "no_merge" between two SCCs that are
6827 * about to be merged (i.e., that are set in "scc_in_merge")?
6828 * "merge_edge" is the proximity edge along which the clusters of SCCs
6829 * are going to be merged.
6831 * If there is any edge between two SCCs with a negative weight,
6832 * while the weight of "merge_edge" is non-negative, then this
6833 * means that the edge was postponed. "merge_edge" should then
6834 * also be postponed since merging along the edge with negative weight should
6835 * be postponed until all edges with non-negative weight have been tried.
6836 * Replace the weight of "merge_edge" by a negative weight as well and
6837 * tell the caller not to attempt a merge.
6839 static int any_no_merge(struct isl_sched_graph *graph, int *scc_in_merge,
6840 struct isl_sched_edge *merge_edge)
6842 int i;
6844 for (i = 0; i < graph->n_edge; ++i) {
6845 struct isl_sched_edge *edge = &graph->edge[i];
6847 if (!scc_in_merge[edge->src->scc])
6848 continue;
6849 if (!scc_in_merge[edge->dst->scc])
6850 continue;
6851 if (edge->no_merge)
6852 return 1;
6853 if (merge_edge->weight >= 0 && edge->weight < 0) {
6854 merge_edge->weight -= graph->max_weight + 1;
6855 return 1;
6859 return 0;
6862 /* Merge the two clusters in "c" connected by the edge in "graph"
6863 * with index "edge" into a single cluster.
6864 * If it turns out to be impossible to merge these two clusters,
6865 * then mark the edge as "no_merge" such that it will not be
6866 * considered again.
6868 * First mark all SCCs that need to be merged. This includes the SCCs
6869 * in the two clusters, but it may also include the SCCs
6870 * of intermediate clusters.
6871 * If there is already a no_merge edge between any pair of such SCCs,
6872 * then simply mark the current edge as no_merge as well.
6873 * Likewise, if any of those edges was postponed by has_bounded_distances,
6874 * then postpone the current edge as well.
6875 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
6876 * if the clusters did not end up getting merged, unless the non-merge
6877 * is due to the fact that the edge was postponed. This postponement
6878 * can be recognized by a change in weight (from non-negative to negative).
6880 static isl_stat merge_clusters_along_edge(isl_ctx *ctx,
6881 struct isl_sched_graph *graph, int edge, struct isl_clustering *c)
6883 isl_bool merged;
6884 int edge_weight = graph->edge[edge].weight;
6886 if (mark_merge_sccs(ctx, graph, edge, c) < 0)
6887 return isl_stat_error;
6889 if (any_no_merge(graph, c->scc_in_merge, &graph->edge[edge]))
6890 merged = isl_bool_false;
6891 else
6892 merged = try_merge(ctx, graph, c);
6893 if (merged < 0)
6894 return isl_stat_error;
6895 if (!merged && edge_weight == graph->edge[edge].weight)
6896 graph->edge[edge].no_merge = 1;
6898 return isl_stat_ok;
6901 /* Does "node" belong to the cluster identified by "cluster"?
6903 static int node_cluster_exactly(struct isl_sched_node *node, int cluster)
6905 return node->cluster == cluster;
6908 /* Does "edge" connect two nodes belonging to the cluster
6909 * identified by "cluster"?
6911 static int edge_cluster_exactly(struct isl_sched_edge *edge, int cluster)
6913 return edge->src->cluster == cluster && edge->dst->cluster == cluster;
6916 /* Swap the schedule of "node1" and "node2".
6917 * Both nodes have been derived from the same node in a common parent graph.
6918 * Since the "coincident" field is shared with that node
6919 * in the parent graph, there is no need to also swap this field.
6921 static void swap_sched(struct isl_sched_node *node1,
6922 struct isl_sched_node *node2)
6924 isl_mat *sched;
6925 isl_map *sched_map;
6927 sched = node1->sched;
6928 node1->sched = node2->sched;
6929 node2->sched = sched;
6931 sched_map = node1->sched_map;
6932 node1->sched_map = node2->sched_map;
6933 node2->sched_map = sched_map;
6936 /* Copy the current band schedule from the SCCs that form the cluster
6937 * with index "pos" to the actual cluster at position "pos".
6938 * By construction, the index of the first SCC that belongs to the cluster
6939 * is also "pos".
6941 * The order of the nodes inside both the SCCs and the cluster
6942 * is assumed to be same as the order in the original "graph".
6944 * Since the SCC graphs will no longer be used after this function,
6945 * the schedules are actually swapped rather than copied.
6947 static isl_stat copy_partial(struct isl_sched_graph *graph,
6948 struct isl_clustering *c, int pos)
6950 int i, j;
6952 c->cluster[pos].n_total_row = c->scc[pos].n_total_row;
6953 c->cluster[pos].n_row = c->scc[pos].n_row;
6954 c->cluster[pos].maxvar = c->scc[pos].maxvar;
6955 j = 0;
6956 for (i = 0; i < graph->n; ++i) {
6957 int k;
6958 int s;
6960 if (graph->node[i].cluster != pos)
6961 continue;
6962 s = graph->node[i].scc;
6963 k = c->scc_node[s]++;
6964 swap_sched(&c->cluster[pos].node[j], &c->scc[s].node[k]);
6965 if (c->scc[s].maxvar > c->cluster[pos].maxvar)
6966 c->cluster[pos].maxvar = c->scc[s].maxvar;
6967 ++j;
6970 return isl_stat_ok;
6973 /* Is there a (conditional) validity dependence from node[j] to node[i],
6974 * forcing node[i] to follow node[j] or do the nodes belong to the same
6975 * cluster?
6977 static isl_bool node_follows_strong_or_same_cluster(int i, int j, void *user)
6979 struct isl_sched_graph *graph = user;
6981 if (graph->node[i].cluster == graph->node[j].cluster)
6982 return isl_bool_true;
6983 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
6986 /* Extract the merged clusters of SCCs in "graph", sort them, and
6987 * store them in c->clusters. Update c->scc_cluster accordingly.
6989 * First keep track of the cluster containing the SCC to which a node
6990 * belongs in the node itself.
6991 * Then extract the clusters into c->clusters, copying the current
6992 * band schedule from the SCCs that belong to the cluster.
6993 * Do this only once per cluster.
6995 * Finally, topologically sort the clusters and update c->scc_cluster
6996 * to match the new scc numbering. While the SCCs were originally
6997 * sorted already, some SCCs that depend on some other SCCs may
6998 * have been merged with SCCs that appear before these other SCCs.
6999 * A reordering may therefore be required.
7001 static isl_stat extract_clusters(isl_ctx *ctx, struct isl_sched_graph *graph,
7002 struct isl_clustering *c)
7004 int i;
7006 for (i = 0; i < graph->n; ++i)
7007 graph->node[i].cluster = c->scc_cluster[graph->node[i].scc];
7009 for (i = 0; i < graph->scc; ++i) {
7010 if (c->scc_cluster[i] != i)
7011 continue;
7012 if (extract_sub_graph(ctx, graph, &node_cluster_exactly,
7013 &edge_cluster_exactly, i, &c->cluster[i]) < 0)
7014 return isl_stat_error;
7015 c->cluster[i].src_scc = -1;
7016 c->cluster[i].dst_scc = -1;
7017 if (copy_partial(graph, c, i) < 0)
7018 return isl_stat_error;
7021 if (detect_ccs(ctx, graph, &node_follows_strong_or_same_cluster) < 0)
7022 return isl_stat_error;
7023 for (i = 0; i < graph->n; ++i)
7024 c->scc_cluster[graph->node[i].scc] = graph->node[i].cluster;
7026 return isl_stat_ok;
7029 /* Compute weights on the proximity edges of "graph" that can
7030 * be used by find_proximity to find the most appropriate
7031 * proximity edge to use to merge two clusters in "c".
7032 * The weights are also used by has_bounded_distances to determine
7033 * whether the merge should be allowed.
7034 * Store the maximum of the computed weights in graph->max_weight.
7036 * The computed weight is a measure for the number of remaining schedule
7037 * dimensions that can still be completely aligned.
7038 * In particular, compute the number of equalities between
7039 * input dimensions and output dimensions in the proximity constraints.
7040 * The directions that are already handled by outer schedule bands
7041 * are projected out prior to determining this number.
7043 * Edges that will never be considered by find_proximity are ignored.
7045 static isl_stat compute_weights(struct isl_sched_graph *graph,
7046 struct isl_clustering *c)
7048 int i;
7050 graph->max_weight = 0;
7052 for (i = 0; i < graph->n_edge; ++i) {
7053 struct isl_sched_edge *edge = &graph->edge[i];
7054 struct isl_sched_node *src = edge->src;
7055 struct isl_sched_node *dst = edge->dst;
7056 isl_basic_map *hull;
7057 isl_bool prox;
7058 int n_in, n_out;
7060 prox = is_non_empty_proximity(edge);
7061 if (prox < 0)
7062 return isl_stat_error;
7063 if (!prox)
7064 continue;
7065 if (bad_cluster(&c->scc[edge->src->scc]) ||
7066 bad_cluster(&c->scc[edge->dst->scc]))
7067 continue;
7068 if (c->scc_cluster[edge->dst->scc] ==
7069 c->scc_cluster[edge->src->scc])
7070 continue;
7072 hull = isl_map_affine_hull(isl_map_copy(edge->map));
7073 hull = isl_basic_map_transform_dims(hull, isl_dim_in, 0,
7074 isl_mat_copy(src->vmap));
7075 hull = isl_basic_map_transform_dims(hull, isl_dim_out, 0,
7076 isl_mat_copy(dst->vmap));
7077 hull = isl_basic_map_project_out(hull,
7078 isl_dim_in, 0, src->rank);
7079 hull = isl_basic_map_project_out(hull,
7080 isl_dim_out, 0, dst->rank);
7081 hull = isl_basic_map_remove_divs(hull);
7082 n_in = isl_basic_map_dim(hull, isl_dim_in);
7083 n_out = isl_basic_map_dim(hull, isl_dim_out);
7084 hull = isl_basic_map_drop_constraints_not_involving_dims(hull,
7085 isl_dim_in, 0, n_in);
7086 hull = isl_basic_map_drop_constraints_not_involving_dims(hull,
7087 isl_dim_out, 0, n_out);
7088 if (!hull)
7089 return isl_stat_error;
7090 edge->weight = isl_basic_map_n_equality(hull);
7091 isl_basic_map_free(hull);
7093 if (edge->weight > graph->max_weight)
7094 graph->max_weight = edge->weight;
7097 return isl_stat_ok;
7100 /* Call compute_schedule_finish_band on each of the clusters in "c"
7101 * in their topological order. This order is determined by the scc
7102 * fields of the nodes in "graph".
7103 * Combine the results in a sequence expressing the topological order.
7105 * If there is only one cluster left, then there is no need to introduce
7106 * a sequence node. Also, in this case, the cluster necessarily contains
7107 * the SCC at position 0 in the original graph and is therefore also
7108 * stored in the first cluster of "c".
7110 static __isl_give isl_schedule_node *finish_bands_clustering(
7111 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
7112 struct isl_clustering *c)
7114 int i;
7115 isl_ctx *ctx;
7116 isl_union_set_list *filters;
7118 if (graph->scc == 1)
7119 return compute_schedule_finish_band(node, &c->cluster[0], 0);
7121 ctx = isl_schedule_node_get_ctx(node);
7123 filters = extract_sccs(ctx, graph);
7124 node = isl_schedule_node_insert_sequence(node, filters);
7126 for (i = 0; i < graph->scc; ++i) {
7127 int j = c->scc_cluster[i];
7128 node = isl_schedule_node_child(node, i);
7129 node = isl_schedule_node_child(node, 0);
7130 node = compute_schedule_finish_band(node, &c->cluster[j], 0);
7131 node = isl_schedule_node_parent(node);
7132 node = isl_schedule_node_parent(node);
7135 return node;
7138 /* Compute a schedule for a connected dependence graph by first considering
7139 * each strongly connected component (SCC) in the graph separately and then
7140 * incrementally combining them into clusters.
7141 * Return the updated schedule node.
7143 * Initially, each cluster consists of a single SCC, each with its
7144 * own band schedule. The algorithm then tries to merge pairs
7145 * of clusters along a proximity edge until no more suitable
7146 * proximity edges can be found. During this merging, the schedule
7147 * is maintained in the individual SCCs.
7148 * After the merging is completed, the full resulting clusters
7149 * are extracted and in finish_bands_clustering,
7150 * compute_schedule_finish_band is called on each of them to integrate
7151 * the band into "node" and to continue the computation.
7153 * compute_weights initializes the weights that are used by find_proximity.
7155 static __isl_give isl_schedule_node *compute_schedule_wcc_clustering(
7156 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
7158 isl_ctx *ctx;
7159 struct isl_clustering c;
7160 int i;
7162 ctx = isl_schedule_node_get_ctx(node);
7164 if (clustering_init(ctx, &c, graph) < 0)
7165 goto error;
7167 if (compute_weights(graph, &c) < 0)
7168 goto error;
7170 for (;;) {
7171 i = find_proximity(graph, &c);
7172 if (i < 0)
7173 goto error;
7174 if (i >= graph->n_edge)
7175 break;
7176 if (merge_clusters_along_edge(ctx, graph, i, &c) < 0)
7177 goto error;
7180 if (extract_clusters(ctx, graph, &c) < 0)
7181 goto error;
7183 node = finish_bands_clustering(node, graph, &c);
7185 clustering_free(ctx, &c);
7186 return node;
7187 error:
7188 clustering_free(ctx, &c);
7189 return isl_schedule_node_free(node);
7192 /* Compute a schedule for a connected dependence graph and return
7193 * the updated schedule node.
7195 * If Feautrier's algorithm is selected, we first recursively try to satisfy
7196 * as many validity dependences as possible. When all validity dependences
7197 * are satisfied we extend the schedule to a full-dimensional schedule.
7199 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
7200 * depending on whether the user has selected the option to try and
7201 * compute a schedule for the entire (weakly connected) component first.
7202 * If there is only a single strongly connected component (SCC), then
7203 * there is no point in trying to combine SCCs
7204 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
7205 * is called instead.
7207 static __isl_give isl_schedule_node *compute_schedule_wcc(
7208 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
7210 isl_ctx *ctx;
7212 if (!node)
7213 return NULL;
7215 ctx = isl_schedule_node_get_ctx(node);
7216 if (detect_sccs(ctx, graph) < 0)
7217 return isl_schedule_node_free(node);
7219 if (compute_maxvar(graph) < 0)
7220 return isl_schedule_node_free(node);
7222 if (need_feautrier_step(ctx, graph))
7223 return compute_schedule_wcc_feautrier(node, graph);
7225 if (graph->scc <= 1 || isl_options_get_schedule_whole_component(ctx))
7226 return compute_schedule_wcc_whole(node, graph);
7227 else
7228 return compute_schedule_wcc_clustering(node, graph);
7231 /* Compute a schedule for each group of nodes identified by node->scc
7232 * separately and then combine them in a sequence node (or as set node
7233 * if graph->weak is set) inserted at position "node" of the schedule tree.
7234 * Return the updated schedule node.
7236 * If "wcc" is set then each of the groups belongs to a single
7237 * weakly connected component in the dependence graph so that
7238 * there is no need for compute_sub_schedule to look for weakly
7239 * connected components.
7241 * If a set node would be introduced and if the number of components
7242 * is equal to the number of nodes, then check if the schedule
7243 * is already complete. If so, a redundant set node would be introduced
7244 * (without any further descendants) stating that the statements
7245 * can be executed in arbitrary order, which is also expressed
7246 * by the absence of any node. Refrain from inserting any nodes
7247 * in this case and simply return.
7249 static __isl_give isl_schedule_node *compute_component_schedule(
7250 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
7251 int wcc)
7253 int component;
7254 isl_ctx *ctx;
7255 isl_union_set_list *filters;
7257 if (!node)
7258 return NULL;
7260 if (graph->weak && graph->scc == graph->n) {
7261 if (compute_maxvar(graph) < 0)
7262 return isl_schedule_node_free(node);
7263 if (graph->n_row >= graph->maxvar)
7264 return node;
7267 ctx = isl_schedule_node_get_ctx(node);
7268 filters = extract_sccs(ctx, graph);
7269 if (graph->weak)
7270 node = isl_schedule_node_insert_set(node, filters);
7271 else
7272 node = isl_schedule_node_insert_sequence(node, filters);
7274 for (component = 0; component < graph->scc; ++component) {
7275 node = isl_schedule_node_child(node, component);
7276 node = isl_schedule_node_child(node, 0);
7277 node = compute_sub_schedule(node, ctx, graph,
7278 &node_scc_exactly,
7279 &edge_scc_exactly, component, wcc);
7280 node = isl_schedule_node_parent(node);
7281 node = isl_schedule_node_parent(node);
7284 return node;
7287 /* Compute a schedule for the given dependence graph and insert it at "node".
7288 * Return the updated schedule node.
7290 * We first check if the graph is connected (through validity and conditional
7291 * validity dependences) and, if not, compute a schedule
7292 * for each component separately.
7293 * If the schedule_serialize_sccs option is set, then we check for strongly
7294 * connected components instead and compute a separate schedule for
7295 * each such strongly connected component.
7297 static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
7298 struct isl_sched_graph *graph)
7300 isl_ctx *ctx;
7302 if (!node)
7303 return NULL;
7305 ctx = isl_schedule_node_get_ctx(node);
7306 if (isl_options_get_schedule_serialize_sccs(ctx)) {
7307 if (detect_sccs(ctx, graph) < 0)
7308 return isl_schedule_node_free(node);
7309 } else {
7310 if (detect_wccs(ctx, graph) < 0)
7311 return isl_schedule_node_free(node);
7314 if (graph->scc > 1)
7315 return compute_component_schedule(node, graph, 1);
7317 return compute_schedule_wcc(node, graph);
7320 /* Compute a schedule on sc->domain that respects the given schedule
7321 * constraints.
7323 * In particular, the schedule respects all the validity dependences.
7324 * If the default isl scheduling algorithm is used, it tries to minimize
7325 * the dependence distances over the proximity dependences.
7326 * If Feautrier's scheduling algorithm is used, the proximity dependence
7327 * distances are only minimized during the extension to a full-dimensional
7328 * schedule.
7330 * If there are any condition and conditional validity dependences,
7331 * then the conditional validity dependences may be violated inside
7332 * a tilable band, provided they have no adjacent non-local
7333 * condition dependences.
7335 __isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
7336 __isl_take isl_schedule_constraints *sc)
7338 isl_ctx *ctx = isl_schedule_constraints_get_ctx(sc);
7339 struct isl_sched_graph graph = { 0 };
7340 isl_schedule *sched;
7341 isl_schedule_node *node;
7342 isl_union_set *domain;
7344 sc = isl_schedule_constraints_align_params(sc);
7346 domain = isl_schedule_constraints_get_domain(sc);
7347 if (isl_union_set_n_set(domain) == 0) {
7348 isl_schedule_constraints_free(sc);
7349 return isl_schedule_from_domain(domain);
7352 if (graph_init(&graph, sc) < 0)
7353 domain = isl_union_set_free(domain);
7355 node = isl_schedule_node_from_domain(domain);
7356 node = isl_schedule_node_child(node, 0);
7357 if (graph.n > 0)
7358 node = compute_schedule(node, &graph);
7359 sched = isl_schedule_node_get_schedule(node);
7360 isl_schedule_node_free(node);
7362 graph_free(ctx, &graph);
7363 isl_schedule_constraints_free(sc);
7365 return sched;
7368 /* Compute a schedule for the given union of domains that respects
7369 * all the validity dependences and minimizes
7370 * the dependence distances over the proximity dependences.
7372 * This function is kept for backward compatibility.
7374 __isl_give isl_schedule *isl_union_set_compute_schedule(
7375 __isl_take isl_union_set *domain,
7376 __isl_take isl_union_map *validity,
7377 __isl_take isl_union_map *proximity)
7379 isl_schedule_constraints *sc;
7381 sc = isl_schedule_constraints_on_domain(domain);
7382 sc = isl_schedule_constraints_set_validity(sc, validity);
7383 sc = isl_schedule_constraints_set_proximity(sc, proximity);
7385 return isl_schedule_constraints_compute_schedule(sc);