add isl_aff_coefficient_sgn
[isl.git] / isl_scheduler.c
blob4a7428045e0fca5b824eadf7894979eeb7b0394c
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_space_private.h>
16 #include <isl_aff_private.h>
17 #include <isl/hash.h>
18 #include <isl/constraint.h>
19 #include <isl/schedule.h>
20 #include <isl_mat_private.h>
21 #include <isl_vec_private.h>
22 #include <isl/set.h>
23 #include <isl_seq.h>
24 #include <isl_tab.h>
25 #include <isl_dim_map.h>
26 #include <isl/map_to_basic_set.h>
27 #include <isl_sort.h>
28 #include <isl_schedule_private.h>
29 #include <isl_options_private.h>
30 #include <isl_tarjan.h>
31 #include <isl_morph.h>
34 * The scheduling algorithm implemented in this file was inspired by
35 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
36 * Parallelization and Locality Optimization in the Polyhedral Model".
39 enum isl_edge_type {
40 isl_edge_validity = 0,
41 isl_edge_first = isl_edge_validity,
42 isl_edge_coincidence,
43 isl_edge_condition,
44 isl_edge_conditional_validity,
45 isl_edge_proximity,
46 isl_edge_last = isl_edge_proximity
49 /* The constraints that need to be satisfied by a schedule on "domain".
51 * "validity" constraints map domain elements i to domain elements
52 * that should be scheduled after i. (Hard constraint)
53 * "proximity" constraints map domain elements i to domains elements
54 * that should be scheduled as early as possible after i (or before i).
55 * (Soft constraint)
57 * "condition" and "conditional_validity" constraints map possibly "tagged"
58 * domain elements i -> s to "tagged" domain elements j -> t.
59 * The elements of the "conditional_validity" constraints, but without the
60 * tags (i.e., the elements i -> j) are treated as validity constraints,
61 * except that during the construction of a tilable band,
62 * the elements of the "conditional_validity" constraints may be violated
63 * provided that all adjacent elements of the "condition" constraints
64 * are local within the band.
65 * A dependence is local within a band if domain and range are mapped
66 * to the same schedule point by the band.
68 struct isl_schedule_constraints {
69 isl_union_set *domain;
71 isl_union_map *constraint[isl_edge_last + 1];
74 __isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
75 __isl_keep isl_schedule_constraints *sc)
77 isl_ctx *ctx;
78 isl_schedule_constraints *sc_copy;
79 enum isl_edge_type i;
81 ctx = isl_union_set_get_ctx(sc->domain);
82 sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);
83 if (!sc_copy)
84 return NULL;
86 sc_copy->domain = isl_union_set_copy(sc->domain);
87 if (!sc_copy->domain)
88 return isl_schedule_constraints_free(sc_copy);
90 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
91 sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);
92 if (!sc_copy->constraint[i])
93 return isl_schedule_constraints_free(sc_copy);
96 return sc_copy;
100 /* Construct an isl_schedule_constraints object for computing a schedule
101 * on "domain". The initial object does not impose any constraints.
103 __isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
104 __isl_take isl_union_set *domain)
106 isl_ctx *ctx;
107 isl_space *space;
108 isl_schedule_constraints *sc;
109 isl_union_map *empty;
110 enum isl_edge_type i;
112 if (!domain)
113 return NULL;
115 ctx = isl_union_set_get_ctx(domain);
116 sc = isl_calloc_type(ctx, struct isl_schedule_constraints);
117 if (!sc)
118 goto error;
120 space = isl_union_set_get_space(domain);
121 sc->domain = domain;
122 empty = isl_union_map_empty(space);
123 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
124 sc->constraint[i] = isl_union_map_copy(empty);
125 if (!sc->constraint[i])
126 sc->domain = isl_union_set_free(sc->domain);
128 isl_union_map_free(empty);
130 if (!sc->domain)
131 return isl_schedule_constraints_free(sc);
133 return sc;
134 error:
135 isl_union_set_free(domain);
136 return NULL;
139 /* Replace the validity constraints of "sc" by "validity".
141 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
142 __isl_take isl_schedule_constraints *sc,
143 __isl_take isl_union_map *validity)
145 if (!sc || !validity)
146 goto error;
148 isl_union_map_free(sc->constraint[isl_edge_validity]);
149 sc->constraint[isl_edge_validity] = validity;
151 return sc;
152 error:
153 isl_schedule_constraints_free(sc);
154 isl_union_map_free(validity);
155 return NULL;
158 /* Replace the coincidence constraints of "sc" by "coincidence".
160 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
161 __isl_take isl_schedule_constraints *sc,
162 __isl_take isl_union_map *coincidence)
164 if (!sc || !coincidence)
165 goto error;
167 isl_union_map_free(sc->constraint[isl_edge_coincidence]);
168 sc->constraint[isl_edge_coincidence] = coincidence;
170 return sc;
171 error:
172 isl_schedule_constraints_free(sc);
173 isl_union_map_free(coincidence);
174 return NULL;
177 /* Replace the proximity constraints of "sc" by "proximity".
179 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
180 __isl_take isl_schedule_constraints *sc,
181 __isl_take isl_union_map *proximity)
183 if (!sc || !proximity)
184 goto error;
186 isl_union_map_free(sc->constraint[isl_edge_proximity]);
187 sc->constraint[isl_edge_proximity] = proximity;
189 return sc;
190 error:
191 isl_schedule_constraints_free(sc);
192 isl_union_map_free(proximity);
193 return NULL;
196 /* Replace the conditional validity constraints of "sc" by "condition"
197 * and "validity".
199 __isl_give isl_schedule_constraints *
200 isl_schedule_constraints_set_conditional_validity(
201 __isl_take isl_schedule_constraints *sc,
202 __isl_take isl_union_map *condition,
203 __isl_take isl_union_map *validity)
205 if (!sc || !condition || !validity)
206 goto error;
208 isl_union_map_free(sc->constraint[isl_edge_condition]);
209 sc->constraint[isl_edge_condition] = condition;
210 isl_union_map_free(sc->constraint[isl_edge_conditional_validity]);
211 sc->constraint[isl_edge_conditional_validity] = validity;
213 return sc;
214 error:
215 isl_schedule_constraints_free(sc);
216 isl_union_map_free(condition);
217 isl_union_map_free(validity);
218 return NULL;
221 __isl_null isl_schedule_constraints *isl_schedule_constraints_free(
222 __isl_take isl_schedule_constraints *sc)
224 enum isl_edge_type i;
226 if (!sc)
227 return NULL;
229 isl_union_set_free(sc->domain);
230 for (i = isl_edge_first; i <= isl_edge_last; ++i)
231 isl_union_map_free(sc->constraint[i]);
233 free(sc);
235 return NULL;
238 isl_ctx *isl_schedule_constraints_get_ctx(
239 __isl_keep isl_schedule_constraints *sc)
241 return sc ? isl_union_set_get_ctx(sc->domain) : NULL;
244 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc)
246 if (!sc)
247 return;
249 fprintf(stderr, "domain: ");
250 isl_union_set_dump(sc->domain);
251 fprintf(stderr, "validity: ");
252 isl_union_map_dump(sc->constraint[isl_edge_validity]);
253 fprintf(stderr, "proximity: ");
254 isl_union_map_dump(sc->constraint[isl_edge_proximity]);
255 fprintf(stderr, "coincidence: ");
256 isl_union_map_dump(sc->constraint[isl_edge_coincidence]);
257 fprintf(stderr, "condition: ");
258 isl_union_map_dump(sc->constraint[isl_edge_condition]);
259 fprintf(stderr, "conditional_validity: ");
260 isl_union_map_dump(sc->constraint[isl_edge_conditional_validity]);
263 /* Align the parameters of the fields of "sc".
265 static __isl_give isl_schedule_constraints *
266 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)
268 isl_space *space;
269 enum isl_edge_type i;
271 if (!sc)
272 return NULL;
274 space = isl_union_set_get_space(sc->domain);
275 for (i = isl_edge_first; i <= isl_edge_last; ++i)
276 space = isl_space_align_params(space,
277 isl_union_map_get_space(sc->constraint[i]));
279 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
280 sc->constraint[i] = isl_union_map_align_params(
281 sc->constraint[i], isl_space_copy(space));
282 if (!sc->constraint[i])
283 space = isl_space_free(space);
285 sc->domain = isl_union_set_align_params(sc->domain, space);
286 if (!sc->domain)
287 return isl_schedule_constraints_free(sc);
289 return sc;
292 /* Return the total number of isl_maps in the constraints of "sc".
294 static __isl_give int isl_schedule_constraints_n_map(
295 __isl_keep isl_schedule_constraints *sc)
297 enum isl_edge_type i;
298 int n = 0;
300 for (i = isl_edge_first; i <= isl_edge_last; ++i)
301 n += isl_union_map_n_map(sc->constraint[i]);
303 return n;
306 /* Internal information about a node that is used during the construction
307 * of a schedule.
308 * space represents the space in which the domain lives
309 * sched is a matrix representation of the schedule being constructed
310 * for this node; if compressed is set, then this schedule is
311 * defined over the compressed domain space
312 * sched_map is an isl_map representation of the same (partial) schedule
313 * sched_map may be NULL; if compressed is set, then this map
314 * is defined over the uncompressed domain space
315 * rank is the number of linearly independent rows in the linear part
316 * of sched
317 * the columns of cmap represent a change of basis for the schedule
318 * coefficients; the first rank columns span the linear part of
319 * the schedule rows
320 * cinv is the inverse of cmap.
321 * start is the first variable in the LP problem in the sequences that
322 * represents the schedule coefficients of this node
323 * nvar is the dimension of the domain
324 * nparam is the number of parameters or 0 if we are not constructing
325 * a parametric schedule
327 * If compressed is set, then hull represents the constraints
328 * that were used to derive the compression, while compress and
329 * decompress map the original space to the compressed space and
330 * vice versa.
332 * scc is the index of SCC (or WCC) this node belongs to
334 * band contains the band index for each of the rows of the schedule.
335 * band_id is used to differentiate between separate bands at the same
336 * level within the same parent band, i.e., bands that are separated
337 * by the parent band or bands that are independent of each other.
338 * coincident contains a boolean for each of the rows of the schedule,
339 * indicating whether the corresponding scheduling dimension satisfies
340 * the coincidence constraints in the sense that the corresponding
341 * dependence distances are zero.
343 struct isl_sched_node {
344 isl_space *space;
345 int compressed;
346 isl_set *hull;
347 isl_multi_aff *compress;
348 isl_multi_aff *decompress;
349 isl_mat *sched;
350 isl_map *sched_map;
351 int rank;
352 isl_mat *cmap;
353 isl_mat *cinv;
354 int start;
355 int nvar;
356 int nparam;
358 int scc;
360 int *band;
361 int *band_id;
362 int *coincident;
365 static int node_has_space(const void *entry, const void *val)
367 struct isl_sched_node *node = (struct isl_sched_node *)entry;
368 isl_space *dim = (isl_space *)val;
370 return isl_space_is_equal(node->space, dim);
373 /* An edge in the dependence graph. An edge may be used to
374 * ensure validity of the generated schedule, to minimize the dependence
375 * distance or both
377 * map is the dependence relation, with i -> j in the map if j depends on i
378 * tagged_condition and tagged_validity contain the union of all tagged
379 * condition or conditional validity dependence relations that
380 * specialize the dependence relation "map"; that is,
381 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
382 * or "tagged_validity", then i -> j is an element of "map".
383 * If these fields are NULL, then they represent the empty relation.
384 * src is the source node
385 * dst is the sink node
386 * validity is set if the edge is used to ensure correctness
387 * coincidence is used to enforce zero dependence distances
388 * proximity is set if the edge is used to minimize dependence distances
389 * condition is set if the edge represents a condition
390 * for a conditional validity schedule constraint
391 * local can only be set for condition edges and indicates that
392 * the dependence distance over the edge should be zero
393 * conditional_validity is set if the edge is used to conditionally
394 * ensure correctness
396 * For validity edges, start and end mark the sequence of inequality
397 * constraints in the LP problem that encode the validity constraint
398 * corresponding to this edge.
400 struct isl_sched_edge {
401 isl_map *map;
402 isl_union_map *tagged_condition;
403 isl_union_map *tagged_validity;
405 struct isl_sched_node *src;
406 struct isl_sched_node *dst;
408 unsigned validity : 1;
409 unsigned coincidence : 1;
410 unsigned proximity : 1;
411 unsigned local : 1;
412 unsigned condition : 1;
413 unsigned conditional_validity : 1;
415 int start;
416 int end;
419 /* Internal information about the dependence graph used during
420 * the construction of the schedule.
422 * intra_hmap is a cache, mapping dependence relations to their dual,
423 * for dependences from a node to itself
424 * inter_hmap is a cache, mapping dependence relations to their dual,
425 * for dependences between distinct nodes
426 * if compression is involved then the key for these maps
427 * it the original, uncompressed dependence relation, while
428 * the value is the dual of the compressed dependence relation.
430 * n is the number of nodes
431 * node is the list of nodes
432 * maxvar is the maximal number of variables over all nodes
433 * max_row is the allocated number of rows in the schedule
434 * n_row is the current (maximal) number of linearly independent
435 * rows in the node schedules
436 * n_total_row is the current number of rows in the node schedules
437 * n_band is the current number of completed bands
438 * band_start is the starting row in the node schedules of the current band
439 * root is set if this graph is the original dependence graph,
440 * without any splitting
442 * sorted contains a list of node indices sorted according to the
443 * SCC to which a node belongs
445 * n_edge is the number of edges
446 * edge is the list of edges
447 * max_edge contains the maximal number of edges of each type;
448 * in particular, it contains the number of edges in the inital graph.
449 * edge_table contains pointers into the edge array, hashed on the source
450 * and sink spaces; there is one such table for each type;
451 * a given edge may be referenced from more than one table
452 * if the corresponding relation appears in more than of the
453 * sets of dependences
455 * node_table contains pointers into the node array, hashed on the space
457 * region contains a list of variable sequences that should be non-trivial
459 * lp contains the (I)LP problem used to obtain new schedule rows
461 * src_scc and dst_scc are the source and sink SCCs of an edge with
462 * conflicting constraints
464 * scc represents the number of components
466 struct isl_sched_graph {
467 isl_map_to_basic_set *intra_hmap;
468 isl_map_to_basic_set *inter_hmap;
470 struct isl_sched_node *node;
471 int n;
472 int maxvar;
473 int max_row;
474 int n_row;
476 int *sorted;
478 int n_band;
479 int n_total_row;
480 int band_start;
482 int root;
484 struct isl_sched_edge *edge;
485 int n_edge;
486 int max_edge[isl_edge_last + 1];
487 struct isl_hash_table *edge_table[isl_edge_last + 1];
489 struct isl_hash_table *node_table;
490 struct isl_region *region;
492 isl_basic_set *lp;
494 int src_scc;
495 int dst_scc;
497 int scc;
500 /* Initialize node_table based on the list of nodes.
502 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
504 int i;
506 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
507 if (!graph->node_table)
508 return -1;
510 for (i = 0; i < graph->n; ++i) {
511 struct isl_hash_table_entry *entry;
512 uint32_t hash;
514 hash = isl_space_get_hash(graph->node[i].space);
515 entry = isl_hash_table_find(ctx, graph->node_table, hash,
516 &node_has_space,
517 graph->node[i].space, 1);
518 if (!entry)
519 return -1;
520 entry->data = &graph->node[i];
523 return 0;
526 /* Return a pointer to the node that lives within the given space,
527 * or NULL if there is no such node.
529 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
530 struct isl_sched_graph *graph, __isl_keep isl_space *dim)
532 struct isl_hash_table_entry *entry;
533 uint32_t hash;
535 hash = isl_space_get_hash(dim);
536 entry = isl_hash_table_find(ctx, graph->node_table, hash,
537 &node_has_space, dim, 0);
539 return entry ? entry->data : NULL;
542 static int edge_has_src_and_dst(const void *entry, const void *val)
544 const struct isl_sched_edge *edge = entry;
545 const struct isl_sched_edge *temp = val;
547 return edge->src == temp->src && edge->dst == temp->dst;
550 /* Add the given edge to graph->edge_table[type].
552 static int graph_edge_table_add(isl_ctx *ctx, struct isl_sched_graph *graph,
553 enum isl_edge_type type, struct isl_sched_edge *edge)
555 struct isl_hash_table_entry *entry;
556 uint32_t hash;
558 hash = isl_hash_init();
559 hash = isl_hash_builtin(hash, edge->src);
560 hash = isl_hash_builtin(hash, edge->dst);
561 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
562 &edge_has_src_and_dst, edge, 1);
563 if (!entry)
564 return -1;
565 entry->data = edge;
567 return 0;
570 /* Allocate the edge_tables based on the maximal number of edges of
571 * each type.
573 static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
575 int i;
577 for (i = 0; i <= isl_edge_last; ++i) {
578 graph->edge_table[i] = isl_hash_table_alloc(ctx,
579 graph->max_edge[i]);
580 if (!graph->edge_table[i])
581 return -1;
584 return 0;
587 /* If graph->edge_table[type] contains an edge from the given source
588 * to the given destination, then return the hash table entry of this edge.
589 * Otherwise, return NULL.
591 static struct isl_hash_table_entry *graph_find_edge_entry(
592 struct isl_sched_graph *graph,
593 enum isl_edge_type type,
594 struct isl_sched_node *src, struct isl_sched_node *dst)
596 isl_ctx *ctx = isl_space_get_ctx(src->space);
597 uint32_t hash;
598 struct isl_sched_edge temp = { .src = src, .dst = dst };
600 hash = isl_hash_init();
601 hash = isl_hash_builtin(hash, temp.src);
602 hash = isl_hash_builtin(hash, temp.dst);
603 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
604 &edge_has_src_and_dst, &temp, 0);
608 /* If graph->edge_table[type] contains an edge from the given source
609 * to the given destination, then return this edge.
610 * Otherwise, return NULL.
612 static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
613 enum isl_edge_type type,
614 struct isl_sched_node *src, struct isl_sched_node *dst)
616 struct isl_hash_table_entry *entry;
618 entry = graph_find_edge_entry(graph, type, src, dst);
619 if (!entry)
620 return NULL;
622 return entry->data;
625 /* Check whether the dependence graph has an edge of the given type
626 * between the given two nodes.
628 static int graph_has_edge(struct isl_sched_graph *graph,
629 enum isl_edge_type type,
630 struct isl_sched_node *src, struct isl_sched_node *dst)
632 struct isl_sched_edge *edge;
633 int empty;
635 edge = graph_find_edge(graph, type, src, dst);
636 if (!edge)
637 return 0;
639 empty = isl_map_plain_is_empty(edge->map);
640 if (empty < 0)
641 return -1;
643 return !empty;
646 /* Look for any edge with the same src, dst and map fields as "model".
648 * Return the matching edge if one can be found.
649 * Return "model" if no matching edge is found.
650 * Return NULL on error.
652 static struct isl_sched_edge *graph_find_matching_edge(
653 struct isl_sched_graph *graph, struct isl_sched_edge *model)
655 enum isl_edge_type i;
656 struct isl_sched_edge *edge;
658 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
659 int is_equal;
661 edge = graph_find_edge(graph, i, model->src, model->dst);
662 if (!edge)
663 continue;
664 is_equal = isl_map_plain_is_equal(model->map, edge->map);
665 if (is_equal < 0)
666 return NULL;
667 if (is_equal)
668 return edge;
671 return model;
674 /* Remove the given edge from all the edge_tables that refer to it.
676 static void graph_remove_edge(struct isl_sched_graph *graph,
677 struct isl_sched_edge *edge)
679 isl_ctx *ctx = isl_map_get_ctx(edge->map);
680 enum isl_edge_type i;
682 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
683 struct isl_hash_table_entry *entry;
685 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
686 if (!entry)
687 continue;
688 if (entry->data != edge)
689 continue;
690 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
694 /* Check whether the dependence graph has any edge
695 * between the given two nodes.
697 static int graph_has_any_edge(struct isl_sched_graph *graph,
698 struct isl_sched_node *src, struct isl_sched_node *dst)
700 enum isl_edge_type i;
701 int r;
703 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
704 r = graph_has_edge(graph, i, src, dst);
705 if (r < 0 || r)
706 return r;
709 return r;
712 /* Check whether the dependence graph has a validity edge
713 * between the given two nodes.
715 * Conditional validity edges are essentially validity edges that
716 * can be ignored if the corresponding condition edges are iteration private.
717 * Here, we are only checking for the presence of validity
718 * edges, so we need to consider the conditional validity edges too.
719 * In particular, this function is used during the detection
720 * of strongly connected components and we cannot ignore
721 * conditional validity edges during this detection.
723 static int graph_has_validity_edge(struct isl_sched_graph *graph,
724 struct isl_sched_node *src, struct isl_sched_node *dst)
726 int r;
728 r = graph_has_edge(graph, isl_edge_validity, src, dst);
729 if (r < 0 || r)
730 return r;
732 return graph_has_edge(graph, isl_edge_conditional_validity, src, dst);
735 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
736 int n_node, int n_edge)
738 int i;
740 graph->n = n_node;
741 graph->n_edge = n_edge;
742 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
743 graph->sorted = isl_calloc_array(ctx, int, graph->n);
744 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
745 graph->edge = isl_calloc_array(ctx,
746 struct isl_sched_edge, graph->n_edge);
748 graph->intra_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
749 graph->inter_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
751 if (!graph->node || !graph->region || (graph->n_edge && !graph->edge) ||
752 !graph->sorted)
753 return -1;
755 for(i = 0; i < graph->n; ++i)
756 graph->sorted[i] = i;
758 return 0;
761 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
763 int i;
765 isl_map_to_basic_set_free(graph->intra_hmap);
766 isl_map_to_basic_set_free(graph->inter_hmap);
768 if (graph->node)
769 for (i = 0; i < graph->n; ++i) {
770 isl_space_free(graph->node[i].space);
771 isl_set_free(graph->node[i].hull);
772 isl_multi_aff_free(graph->node[i].compress);
773 isl_multi_aff_free(graph->node[i].decompress);
774 isl_mat_free(graph->node[i].sched);
775 isl_map_free(graph->node[i].sched_map);
776 isl_mat_free(graph->node[i].cmap);
777 isl_mat_free(graph->node[i].cinv);
778 if (graph->root) {
779 free(graph->node[i].band);
780 free(graph->node[i].band_id);
781 free(graph->node[i].coincident);
784 free(graph->node);
785 free(graph->sorted);
786 if (graph->edge)
787 for (i = 0; i < graph->n_edge; ++i) {
788 isl_map_free(graph->edge[i].map);
789 isl_union_map_free(graph->edge[i].tagged_condition);
790 isl_union_map_free(graph->edge[i].tagged_validity);
792 free(graph->edge);
793 free(graph->region);
794 for (i = 0; i <= isl_edge_last; ++i)
795 isl_hash_table_free(ctx, graph->edge_table[i]);
796 isl_hash_table_free(ctx, graph->node_table);
797 isl_basic_set_free(graph->lp);
800 /* For each "set" on which this function is called, increment
801 * graph->n by one and update graph->maxvar.
803 static int init_n_maxvar(__isl_take isl_set *set, void *user)
805 struct isl_sched_graph *graph = user;
806 int nvar = isl_set_dim(set, isl_dim_set);
808 graph->n++;
809 if (nvar > graph->maxvar)
810 graph->maxvar = nvar;
812 isl_set_free(set);
814 return 0;
817 /* Add the number of basic maps in "map" to *n.
819 static int add_n_basic_map(__isl_take isl_map *map, void *user)
821 int *n = user;
823 *n += isl_map_n_basic_map(map);
824 isl_map_free(map);
826 return 0;
829 /* Compute the number of rows that should be allocated for the schedule.
830 * The graph can be split at most "n - 1" times, there can be at most
831 * one row for each dimension in the iteration domains plus two rows
832 * for each basic map in the dependences (in particular,
833 * we usually have one row, but it may be split by split_scaled),
834 * and there can be one extra row for ordering the statements.
835 * Note that if we have actually split "n - 1" times, then no ordering
836 * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
837 * It is also practically impossible to exhaust both the number of dependences
838 * and the number of variables.
840 static int compute_max_row(struct isl_sched_graph *graph,
841 __isl_keep isl_schedule_constraints *sc)
843 enum isl_edge_type i;
844 int n_edge;
846 graph->n = 0;
847 graph->maxvar = 0;
848 if (isl_union_set_foreach_set(sc->domain, &init_n_maxvar, graph) < 0)
849 return -1;
850 n_edge = 0;
851 for (i = isl_edge_first; i <= isl_edge_last; ++i)
852 if (isl_union_map_foreach_map(sc->constraint[i],
853 &add_n_basic_map, &n_edge) < 0)
854 return -1;
855 graph->max_row = graph->n + 2 * n_edge + graph->maxvar;
857 return 0;
860 /* Does "bset" have any defining equalities for its set variables?
862 static int has_any_defining_equality(__isl_keep isl_basic_set *bset)
864 int i, n;
866 if (!bset)
867 return -1;
869 n = isl_basic_set_dim(bset, isl_dim_set);
870 for (i = 0; i < n; ++i) {
871 int has;
873 has = isl_basic_set_has_defining_equality(bset, isl_dim_set, i,
874 NULL);
875 if (has < 0 || has)
876 return has;
879 return 0;
882 /* Add a new node to the graph representing the given space.
883 * "nvar" is the (possibly compressed) number of variables and
884 * may be smaller than then number of set variables in "space"
885 * if "compressed" is set.
886 * If "compressed" is set, then "hull" represents the constraints
887 * that were used to derive the compression, while "compress" and
888 * "decompress" map the original space to the compressed space and
889 * vice versa.
890 * If "compressed" is not set, then "hull", "compress" and "decompress"
891 * should be NULL.
893 static int add_node(struct isl_sched_graph *graph, __isl_take isl_space *space,
894 int nvar, int compressed, __isl_take isl_set *hull,
895 __isl_take isl_multi_aff *compress,
896 __isl_take isl_multi_aff *decompress)
898 int nparam;
899 isl_ctx *ctx;
900 isl_mat *sched;
901 int *band, *band_id, *coincident;
903 if (!space)
904 return -1;
906 ctx = isl_space_get_ctx(space);
907 nparam = isl_space_dim(space, isl_dim_param);
908 if (!ctx->opt->schedule_parametric)
909 nparam = 0;
910 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
911 graph->node[graph->n].space = space;
912 graph->node[graph->n].nvar = nvar;
913 graph->node[graph->n].nparam = nparam;
914 graph->node[graph->n].sched = sched;
915 graph->node[graph->n].sched_map = NULL;
916 band = isl_alloc_array(ctx, int, graph->max_row);
917 graph->node[graph->n].band = band;
918 band_id = isl_calloc_array(ctx, int, graph->max_row);
919 graph->node[graph->n].band_id = band_id;
920 coincident = isl_calloc_array(ctx, int, graph->max_row);
921 graph->node[graph->n].coincident = coincident;
922 graph->node[graph->n].compressed = compressed;
923 graph->node[graph->n].hull = hull;
924 graph->node[graph->n].compress = compress;
925 graph->node[graph->n].decompress = decompress;
926 graph->n++;
928 if (!space || !sched ||
929 (graph->max_row && (!band || !band_id || !coincident)))
930 return -1;
931 if (compressed && (!hull || !compress || !decompress))
932 return -1;
934 return 0;
937 /* Add a new node to the graph representing the given set.
939 * If any of the set variables is defined by an equality, then
940 * we perform variable compression such that we can perform
941 * the scheduling on the compressed domain.
943 static int extract_node(__isl_take isl_set *set, void *user)
945 int nvar;
946 int has_equality;
947 isl_space *space;
948 isl_basic_set *hull;
949 isl_set *hull_set;
950 isl_morph *morph;
951 isl_multi_aff *compress, *decompress;
952 struct isl_sched_graph *graph = user;
954 space = isl_set_get_space(set);
955 hull = isl_set_affine_hull(set);
956 hull = isl_basic_set_remove_divs(hull);
957 nvar = isl_space_dim(space, isl_dim_set);
958 has_equality = has_any_defining_equality(hull);
960 if (has_equality < 0)
961 goto error;
962 if (!has_equality) {
963 isl_basic_set_free(hull);
964 return add_node(graph, space, nvar, 0, NULL, NULL, NULL);
967 morph = isl_basic_set_variable_compression(hull, isl_dim_set);
968 nvar = isl_morph_ran_dim(morph, isl_dim_set);
969 compress = isl_morph_get_var_multi_aff(morph);
970 morph = isl_morph_inverse(morph);
971 decompress = isl_morph_get_var_multi_aff(morph);
972 isl_morph_free(morph);
974 hull_set = isl_set_from_basic_set(hull);
975 return add_node(graph, space, nvar, 1, hull_set, compress, decompress);
976 error:
977 isl_basic_set_free(hull);
978 isl_space_free(space);
979 return -1;
982 struct isl_extract_edge_data {
983 enum isl_edge_type type;
984 struct isl_sched_graph *graph;
987 /* Merge edge2 into edge1, freeing the contents of edge2.
988 * "type" is the type of the schedule constraint from which edge2 was
989 * extracted.
990 * Return 0 on success and -1 on failure.
992 * edge1 and edge2 are assumed to have the same value for the map field.
994 static int merge_edge(enum isl_edge_type type, struct isl_sched_edge *edge1,
995 struct isl_sched_edge *edge2)
997 edge1->validity |= edge2->validity;
998 edge1->coincidence |= edge2->coincidence;
999 edge1->proximity |= edge2->proximity;
1000 edge1->condition |= edge2->condition;
1001 edge1->conditional_validity |= edge2->conditional_validity;
1002 isl_map_free(edge2->map);
1004 if (type == isl_edge_condition) {
1005 if (!edge1->tagged_condition)
1006 edge1->tagged_condition = edge2->tagged_condition;
1007 else
1008 edge1->tagged_condition =
1009 isl_union_map_union(edge1->tagged_condition,
1010 edge2->tagged_condition);
1013 if (type == isl_edge_conditional_validity) {
1014 if (!edge1->tagged_validity)
1015 edge1->tagged_validity = edge2->tagged_validity;
1016 else
1017 edge1->tagged_validity =
1018 isl_union_map_union(edge1->tagged_validity,
1019 edge2->tagged_validity);
1022 if (type == isl_edge_condition && !edge1->tagged_condition)
1023 return -1;
1024 if (type == isl_edge_conditional_validity && !edge1->tagged_validity)
1025 return -1;
1027 return 0;
1030 /* Insert dummy tags in domain and range of "map".
1032 * In particular, if "map" is of the form
1034 * A -> B
1036 * then return
1038 * [A -> dummy_tag] -> [B -> dummy_tag]
1040 * where the dummy_tags are identical and equal to any dummy tags
1041 * introduced by any other call to this function.
1043 static __isl_give isl_map *insert_dummy_tags(__isl_take isl_map *map)
1045 static char dummy;
1046 isl_ctx *ctx;
1047 isl_id *id;
1048 isl_space *space;
1049 isl_set *domain, *range;
1051 ctx = isl_map_get_ctx(map);
1053 id = isl_id_alloc(ctx, NULL, &dummy);
1054 space = isl_space_params(isl_map_get_space(map));
1055 space = isl_space_set_from_params(space);
1056 space = isl_space_set_tuple_id(space, isl_dim_set, id);
1057 space = isl_space_map_from_set(space);
1059 domain = isl_map_wrap(map);
1060 range = isl_map_wrap(isl_map_universe(space));
1061 map = isl_map_from_domain_and_range(domain, range);
1062 map = isl_map_zip(map);
1064 return map;
1067 /* Given that at least one of "src" or "dst" is compressed, return
1068 * a map between the spaces of these nodes restricted to the affine
1069 * hull that was used in the compression.
1071 static __isl_give isl_map *extract_hull(struct isl_sched_node *src,
1072 struct isl_sched_node *dst)
1074 isl_set *dom, *ran;
1076 if (src->compressed)
1077 dom = isl_set_copy(src->hull);
1078 else
1079 dom = isl_set_universe(isl_space_copy(src->space));
1080 if (dst->compressed)
1081 ran = isl_set_copy(dst->hull);
1082 else
1083 ran = isl_set_universe(isl_space_copy(dst->space));
1085 return isl_map_from_domain_and_range(dom, ran);
1088 /* Intersect the domains of the nested relations in domain and range
1089 * of "tagged" with "map".
1091 static __isl_give isl_map *map_intersect_domains(__isl_take isl_map *tagged,
1092 __isl_keep isl_map *map)
1094 isl_set *set;
1096 tagged = isl_map_zip(tagged);
1097 set = isl_map_wrap(isl_map_copy(map));
1098 tagged = isl_map_intersect_domain(tagged, set);
1099 tagged = isl_map_zip(tagged);
1100 return tagged;
1103 /* Add a new edge to the graph based on the given map
1104 * and add it to data->graph->edge_table[data->type].
1105 * If a dependence relation of a given type happens to be identical
1106 * to one of the dependence relations of a type that was added before,
1107 * then we don't create a new edge, but instead mark the original edge
1108 * as also representing a dependence of the current type.
1110 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1111 * may be specified as "tagged" dependence relations. That is, "map"
1112 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1113 * the dependence on iterations and a and b are tags.
1114 * edge->map is set to the relation containing the elements i -> j,
1115 * while edge->tagged_condition and edge->tagged_validity contain
1116 * the union of all the "map" relations
1117 * for which extract_edge is called that result in the same edge->map.
1119 * If the source or the destination node is compressed, then
1120 * intersect both "map" and "tagged" with the constraints that
1121 * were used to construct the compression.
1122 * This ensures that there are no schedule constraints defined
1123 * outside of these domains, while the scheduler no longer has
1124 * any control over those outside parts.
1126 static int extract_edge(__isl_take isl_map *map, void *user)
1128 isl_ctx *ctx = isl_map_get_ctx(map);
1129 struct isl_extract_edge_data *data = user;
1130 struct isl_sched_graph *graph = data->graph;
1131 struct isl_sched_node *src, *dst;
1132 isl_space *dim;
1133 struct isl_sched_edge *edge;
1134 isl_map *tagged = NULL;
1136 if (data->type == isl_edge_condition ||
1137 data->type == isl_edge_conditional_validity) {
1138 if (isl_map_can_zip(map)) {
1139 tagged = isl_map_copy(map);
1140 map = isl_set_unwrap(isl_map_domain(isl_map_zip(map)));
1141 } else {
1142 tagged = insert_dummy_tags(isl_map_copy(map));
1146 dim = isl_space_domain(isl_map_get_space(map));
1147 src = graph_find_node(ctx, graph, dim);
1148 isl_space_free(dim);
1149 dim = isl_space_range(isl_map_get_space(map));
1150 dst = graph_find_node(ctx, graph, dim);
1151 isl_space_free(dim);
1153 if (!src || !dst) {
1154 isl_map_free(map);
1155 isl_map_free(tagged);
1156 return 0;
1159 if (src->compressed || dst->compressed) {
1160 isl_map *hull;
1161 hull = extract_hull(src, dst);
1162 if (tagged)
1163 tagged = map_intersect_domains(tagged, hull);
1164 map = isl_map_intersect(map, hull);
1167 graph->edge[graph->n_edge].src = src;
1168 graph->edge[graph->n_edge].dst = dst;
1169 graph->edge[graph->n_edge].map = map;
1170 graph->edge[graph->n_edge].validity = 0;
1171 graph->edge[graph->n_edge].coincidence = 0;
1172 graph->edge[graph->n_edge].proximity = 0;
1173 graph->edge[graph->n_edge].condition = 0;
1174 graph->edge[graph->n_edge].local = 0;
1175 graph->edge[graph->n_edge].conditional_validity = 0;
1176 graph->edge[graph->n_edge].tagged_condition = NULL;
1177 graph->edge[graph->n_edge].tagged_validity = NULL;
1178 if (data->type == isl_edge_validity)
1179 graph->edge[graph->n_edge].validity = 1;
1180 if (data->type == isl_edge_coincidence)
1181 graph->edge[graph->n_edge].coincidence = 1;
1182 if (data->type == isl_edge_proximity)
1183 graph->edge[graph->n_edge].proximity = 1;
1184 if (data->type == isl_edge_condition) {
1185 graph->edge[graph->n_edge].condition = 1;
1186 graph->edge[graph->n_edge].tagged_condition =
1187 isl_union_map_from_map(tagged);
1189 if (data->type == isl_edge_conditional_validity) {
1190 graph->edge[graph->n_edge].conditional_validity = 1;
1191 graph->edge[graph->n_edge].tagged_validity =
1192 isl_union_map_from_map(tagged);
1195 edge = graph_find_matching_edge(graph, &graph->edge[graph->n_edge]);
1196 if (!edge) {
1197 graph->n_edge++;
1198 return -1;
1200 if (edge == &graph->edge[graph->n_edge])
1201 return graph_edge_table_add(ctx, graph, data->type,
1202 &graph->edge[graph->n_edge++]);
1204 if (merge_edge(data->type, edge, &graph->edge[graph->n_edge]) < 0)
1205 return -1;
1207 return graph_edge_table_add(ctx, graph, data->type, edge);
1210 /* Check whether there is any dependence from node[j] to node[i]
1211 * or from node[i] to node[j].
1213 static int node_follows_weak(int i, int j, void *user)
1215 int f;
1216 struct isl_sched_graph *graph = user;
1218 f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]);
1219 if (f < 0 || f)
1220 return f;
1221 return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]);
1224 /* Check whether there is a (conditional) validity dependence from node[j]
1225 * to node[i], forcing node[i] to follow node[j].
1227 static int node_follows_strong(int i, int j, void *user)
1229 struct isl_sched_graph *graph = user;
1231 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
1234 /* Use Tarjan's algorithm for computing the strongly connected components
1235 * in the dependence graph (only validity edges).
1236 * If weak is set, we consider the graph to be undirected and
1237 * we effectively compute the (weakly) connected components.
1238 * Additionally, we also consider other edges when weak is set.
1240 static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, int weak)
1242 int i, n;
1243 struct isl_tarjan_graph *g = NULL;
1245 g = isl_tarjan_graph_init(ctx, graph->n,
1246 weak ? &node_follows_weak : &node_follows_strong, graph);
1247 if (!g)
1248 return -1;
1250 graph->scc = 0;
1251 i = 0;
1252 n = graph->n;
1253 while (n) {
1254 while (g->order[i] != -1) {
1255 graph->node[g->order[i]].scc = graph->scc;
1256 --n;
1257 ++i;
1259 ++i;
1260 graph->scc++;
1263 isl_tarjan_graph_free(g);
1265 return 0;
1268 /* Apply Tarjan's algorithm to detect the strongly connected components
1269 * in the dependence graph.
1271 static int detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1273 return detect_ccs(ctx, graph, 0);
1276 /* Apply Tarjan's algorithm to detect the (weakly) connected components
1277 * in the dependence graph.
1279 static int detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1281 return detect_ccs(ctx, graph, 1);
1284 static int cmp_scc(const void *a, const void *b, void *data)
1286 struct isl_sched_graph *graph = data;
1287 const int *i1 = a;
1288 const int *i2 = b;
1290 return graph->node[*i1].scc - graph->node[*i2].scc;
1293 /* Sort the elements of graph->sorted according to the corresponding SCCs.
1295 static int sort_sccs(struct isl_sched_graph *graph)
1297 return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
1300 /* Given a dependence relation R from "node" to itself,
1301 * construct the set of coefficients of valid constraints for elements
1302 * in that dependence relation.
1303 * In particular, the result contains tuples of coefficients
1304 * c_0, c_n, c_x such that
1306 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1308 * or, equivalently,
1310 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1312 * We choose here to compute the dual of delta R.
1313 * Alternatively, we could have computed the dual of R, resulting
1314 * in a set of tuples c_0, c_n, c_x, c_y, and then
1315 * plugged in (c_0, c_n, c_x, -c_x).
1317 * If "node" has been compressed, then the dependence relation
1318 * is also compressed before the set of coefficients is computed.
1320 static __isl_give isl_basic_set *intra_coefficients(
1321 struct isl_sched_graph *graph, struct isl_sched_node *node,
1322 __isl_take isl_map *map)
1324 isl_set *delta;
1325 isl_map *key;
1326 isl_basic_set *coef;
1328 if (isl_map_to_basic_set_has(graph->intra_hmap, map))
1329 return isl_map_to_basic_set_get(graph->intra_hmap, map);
1331 key = isl_map_copy(map);
1332 if (node->compressed) {
1333 map = isl_map_preimage_domain_multi_aff(map,
1334 isl_multi_aff_copy(node->decompress));
1335 map = isl_map_preimage_range_multi_aff(map,
1336 isl_multi_aff_copy(node->decompress));
1338 delta = isl_set_remove_divs(isl_map_deltas(map));
1339 coef = isl_set_coefficients(delta);
1340 graph->intra_hmap = isl_map_to_basic_set_set(graph->intra_hmap, key,
1341 isl_basic_set_copy(coef));
1343 return coef;
1346 /* Given a dependence relation R, construct the set of coefficients
1347 * of valid constraints for elements in that dependence relation.
1348 * In particular, the result contains tuples of coefficients
1349 * c_0, c_n, c_x, c_y such that
1351 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1353 * If the source or destination nodes of "edge" have been compressed,
1354 * then the dependence relation is also compressed before
1355 * the set of coefficients is computed.
1357 static __isl_give isl_basic_set *inter_coefficients(
1358 struct isl_sched_graph *graph, struct isl_sched_edge *edge,
1359 __isl_take isl_map *map)
1361 isl_set *set;
1362 isl_map *key;
1363 isl_basic_set *coef;
1365 if (isl_map_to_basic_set_has(graph->inter_hmap, map))
1366 return isl_map_to_basic_set_get(graph->inter_hmap, map);
1368 key = isl_map_copy(map);
1369 if (edge->src->compressed)
1370 map = isl_map_preimage_domain_multi_aff(map,
1371 isl_multi_aff_copy(edge->src->decompress));
1372 if (edge->dst->compressed)
1373 map = isl_map_preimage_range_multi_aff(map,
1374 isl_multi_aff_copy(edge->dst->decompress));
1375 set = isl_map_wrap(isl_map_remove_divs(map));
1376 coef = isl_set_coefficients(set);
1377 graph->inter_hmap = isl_map_to_basic_set_set(graph->inter_hmap, key,
1378 isl_basic_set_copy(coef));
1380 return coef;
1383 /* Add constraints to graph->lp that force validity for the given
1384 * dependence from a node i to itself.
1385 * That is, add constraints that enforce
1387 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1388 * = c_i_x (y - x) >= 0
1390 * for each (x,y) in R.
1391 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1392 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1393 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1394 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1396 * Actually, we do not construct constraints for the c_i_x themselves,
1397 * but for the coefficients of c_i_x written as a linear combination
1398 * of the columns in node->cmap.
1400 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
1401 struct isl_sched_edge *edge)
1403 unsigned total;
1404 isl_map *map = isl_map_copy(edge->map);
1405 isl_ctx *ctx = isl_map_get_ctx(map);
1406 isl_space *dim;
1407 isl_dim_map *dim_map;
1408 isl_basic_set *coef;
1409 struct isl_sched_node *node = edge->src;
1411 coef = intra_coefficients(graph, node, map);
1413 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1415 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1416 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
1417 if (!coef)
1418 goto error;
1420 total = isl_basic_set_total_dim(graph->lp);
1421 dim_map = isl_dim_map_alloc(ctx, total);
1422 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1423 isl_space_dim(dim, isl_dim_set), 1,
1424 node->nvar, -1);
1425 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1426 isl_space_dim(dim, isl_dim_set), 1,
1427 node->nvar, 1);
1428 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1429 coef->n_eq, coef->n_ineq);
1430 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1431 coef, dim_map);
1432 isl_space_free(dim);
1434 return 0;
1435 error:
1436 isl_space_free(dim);
1437 return -1;
1440 /* Add constraints to graph->lp that force validity for the given
1441 * dependence from node i to node j.
1442 * That is, add constraints that enforce
1444 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1446 * for each (x,y) in R.
1447 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1448 * of valid constraints for R and then plug in
1449 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1450 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1451 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1452 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1454 * Actually, we do not construct constraints for the c_*_x themselves,
1455 * but for the coefficients of c_*_x written as a linear combination
1456 * of the columns in node->cmap.
1458 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
1459 struct isl_sched_edge *edge)
1461 unsigned total;
1462 isl_map *map = isl_map_copy(edge->map);
1463 isl_ctx *ctx = isl_map_get_ctx(map);
1464 isl_space *dim;
1465 isl_dim_map *dim_map;
1466 isl_basic_set *coef;
1467 struct isl_sched_node *src = edge->src;
1468 struct isl_sched_node *dst = edge->dst;
1470 coef = inter_coefficients(graph, edge, map);
1472 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1474 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1475 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1476 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1477 isl_space_dim(dim, isl_dim_set) + src->nvar,
1478 isl_mat_copy(dst->cmap));
1479 if (!coef)
1480 goto error;
1482 total = isl_basic_set_total_dim(graph->lp);
1483 dim_map = isl_dim_map_alloc(ctx, total);
1485 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
1486 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
1487 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
1488 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1489 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1490 dst->nvar, -1);
1491 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1492 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1493 dst->nvar, 1);
1495 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
1496 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
1497 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
1498 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1499 isl_space_dim(dim, isl_dim_set), 1,
1500 src->nvar, 1);
1501 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1502 isl_space_dim(dim, isl_dim_set), 1,
1503 src->nvar, -1);
1505 edge->start = graph->lp->n_ineq;
1506 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1507 coef->n_eq, coef->n_ineq);
1508 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1509 coef, dim_map);
1510 if (!graph->lp)
1511 goto error;
1512 isl_space_free(dim);
1513 edge->end = graph->lp->n_ineq;
1515 return 0;
1516 error:
1517 isl_space_free(dim);
1518 return -1;
1521 /* Add constraints to graph->lp that bound the dependence distance for the given
1522 * dependence from a node i to itself.
1523 * If s = 1, we add the constraint
1525 * c_i_x (y - x) <= m_0 + m_n n
1527 * or
1529 * -c_i_x (y - x) + m_0 + m_n n >= 0
1531 * for each (x,y) in R.
1532 * If s = -1, we add the constraint
1534 * -c_i_x (y - x) <= m_0 + m_n n
1536 * or
1538 * c_i_x (y - x) + m_0 + m_n n >= 0
1540 * for each (x,y) in R.
1541 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1542 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1543 * with each coefficient (except m_0) represented as a pair of non-negative
1544 * coefficients.
1546 * Actually, we do not construct constraints for the c_i_x themselves,
1547 * but for the coefficients of c_i_x written as a linear combination
1548 * of the columns in node->cmap.
1551 * If "local" is set, then we add constraints
1553 * c_i_x (y - x) <= 0
1555 * or
1557 * -c_i_x (y - x) <= 0
1559 * instead, forcing the dependence distance to be (less than or) equal to 0.
1560 * That is, we plug in (0, 0, -s * c_i_x),
1561 * Note that dependences marked local are treated as validity constraints
1562 * by add_all_validity_constraints and therefore also have
1563 * their distances bounded by 0 from below.
1565 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
1566 struct isl_sched_edge *edge, int s, int local)
1568 unsigned total;
1569 unsigned nparam;
1570 isl_map *map = isl_map_copy(edge->map);
1571 isl_ctx *ctx = isl_map_get_ctx(map);
1572 isl_space *dim;
1573 isl_dim_map *dim_map;
1574 isl_basic_set *coef;
1575 struct isl_sched_node *node = edge->src;
1577 coef = intra_coefficients(graph, node, map);
1579 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1581 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1582 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
1583 if (!coef)
1584 goto error;
1586 nparam = isl_space_dim(node->space, isl_dim_param);
1587 total = isl_basic_set_total_dim(graph->lp);
1588 dim_map = isl_dim_map_alloc(ctx, total);
1590 if (!local) {
1591 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1592 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1593 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1595 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1596 isl_space_dim(dim, isl_dim_set), 1,
1597 node->nvar, s);
1598 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1599 isl_space_dim(dim, isl_dim_set), 1,
1600 node->nvar, -s);
1601 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1602 coef->n_eq, coef->n_ineq);
1603 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1604 coef, dim_map);
1605 isl_space_free(dim);
1607 return 0;
1608 error:
1609 isl_space_free(dim);
1610 return -1;
1613 /* Add constraints to graph->lp that bound the dependence distance for the given
1614 * dependence from node i to node j.
1615 * If s = 1, we add the constraint
1617 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1618 * <= m_0 + m_n n
1620 * or
1622 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1623 * m_0 + m_n n >= 0
1625 * for each (x,y) in R.
1626 * If s = -1, we add the constraint
1628 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1629 * <= m_0 + m_n n
1631 * or
1633 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1634 * m_0 + m_n n >= 0
1636 * for each (x,y) in R.
1637 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1638 * of valid constraints for R and then plug in
1639 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1640 * -s*c_j_x+s*c_i_x)
1641 * with each coefficient (except m_0, c_j_0 and c_i_0)
1642 * represented as a pair of non-negative coefficients.
1644 * Actually, we do not construct constraints for the c_*_x themselves,
1645 * but for the coefficients of c_*_x written as a linear combination
1646 * of the columns in node->cmap.
1649 * If "local" is set, then we add constraints
1651 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1653 * or
1655 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1657 * instead, forcing the dependence distance to be (less than or) equal to 0.
1658 * That is, we plug in
1659 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1660 * Note that dependences marked local are treated as validity constraints
1661 * by add_all_validity_constraints and therefore also have
1662 * their distances bounded by 0 from below.
1664 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
1665 struct isl_sched_edge *edge, int s, int local)
1667 unsigned total;
1668 unsigned nparam;
1669 isl_map *map = isl_map_copy(edge->map);
1670 isl_ctx *ctx = isl_map_get_ctx(map);
1671 isl_space *dim;
1672 isl_dim_map *dim_map;
1673 isl_basic_set *coef;
1674 struct isl_sched_node *src = edge->src;
1675 struct isl_sched_node *dst = edge->dst;
1677 coef = inter_coefficients(graph, edge, map);
1679 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1681 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1682 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1683 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1684 isl_space_dim(dim, isl_dim_set) + src->nvar,
1685 isl_mat_copy(dst->cmap));
1686 if (!coef)
1687 goto error;
1689 nparam = isl_space_dim(src->space, isl_dim_param);
1690 total = isl_basic_set_total_dim(graph->lp);
1691 dim_map = isl_dim_map_alloc(ctx, total);
1693 if (!local) {
1694 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1695 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1696 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1699 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
1700 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
1701 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
1702 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1703 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1704 dst->nvar, s);
1705 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1706 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1707 dst->nvar, -s);
1709 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
1710 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
1711 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
1712 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1713 isl_space_dim(dim, isl_dim_set), 1,
1714 src->nvar, -s);
1715 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1716 isl_space_dim(dim, isl_dim_set), 1,
1717 src->nvar, s);
1719 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1720 coef->n_eq, coef->n_ineq);
1721 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1722 coef, dim_map);
1723 isl_space_free(dim);
1725 return 0;
1726 error:
1727 isl_space_free(dim);
1728 return -1;
1731 /* Add all validity constraints to graph->lp.
1733 * An edge that is forced to be local needs to have its dependence
1734 * distances equal to zero. We take care of bounding them by 0 from below
1735 * here. add_all_proximity_constraints takes care of bounding them by 0
1736 * from above.
1738 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1739 * Otherwise, we ignore them.
1741 static int add_all_validity_constraints(struct isl_sched_graph *graph,
1742 int use_coincidence)
1744 int i;
1746 for (i = 0; i < graph->n_edge; ++i) {
1747 struct isl_sched_edge *edge= &graph->edge[i];
1748 int local;
1750 local = edge->local || (edge->coincidence && use_coincidence);
1751 if (!edge->validity && !local)
1752 continue;
1753 if (edge->src != edge->dst)
1754 continue;
1755 if (add_intra_validity_constraints(graph, edge) < 0)
1756 return -1;
1759 for (i = 0; i < graph->n_edge; ++i) {
1760 struct isl_sched_edge *edge = &graph->edge[i];
1761 int local;
1763 local = edge->local || (edge->coincidence && use_coincidence);
1764 if (!edge->validity && !local)
1765 continue;
1766 if (edge->src == edge->dst)
1767 continue;
1768 if (add_inter_validity_constraints(graph, edge) < 0)
1769 return -1;
1772 return 0;
1775 /* Add constraints to graph->lp that bound the dependence distance
1776 * for all dependence relations.
1777 * If a given proximity dependence is identical to a validity
1778 * dependence, then the dependence distance is already bounded
1779 * from below (by zero), so we only need to bound the distance
1780 * from above. (This includes the case of "local" dependences
1781 * which are treated as validity dependence by add_all_validity_constraints.)
1782 * Otherwise, we need to bound the distance both from above and from below.
1784 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1785 * Otherwise, we ignore them.
1787 static int add_all_proximity_constraints(struct isl_sched_graph *graph,
1788 int use_coincidence)
1790 int i;
1792 for (i = 0; i < graph->n_edge; ++i) {
1793 struct isl_sched_edge *edge= &graph->edge[i];
1794 int local;
1796 local = edge->local || (edge->coincidence && use_coincidence);
1797 if (!edge->proximity && !local)
1798 continue;
1799 if (edge->src == edge->dst &&
1800 add_intra_proximity_constraints(graph, edge, 1, local) < 0)
1801 return -1;
1802 if (edge->src != edge->dst &&
1803 add_inter_proximity_constraints(graph, edge, 1, local) < 0)
1804 return -1;
1805 if (edge->validity || local)
1806 continue;
1807 if (edge->src == edge->dst &&
1808 add_intra_proximity_constraints(graph, edge, -1, 0) < 0)
1809 return -1;
1810 if (edge->src != edge->dst &&
1811 add_inter_proximity_constraints(graph, edge, -1, 0) < 0)
1812 return -1;
1815 return 0;
1818 /* Compute a basis for the rows in the linear part of the schedule
1819 * and extend this basis to a full basis. The remaining rows
1820 * can then be used to force linear independence from the rows
1821 * in the schedule.
1823 * In particular, given the schedule rows S, we compute
1825 * S = H Q
1826 * S U = H
1828 * with H the Hermite normal form of S. That is, all but the
1829 * first rank columns of H are zero and so each row in S is
1830 * a linear combination of the first rank rows of Q.
1831 * The matrix Q is then transposed because we will write the
1832 * coefficients of the next schedule row as a column vector s
1833 * and express this s as a linear combination s = Q c of the
1834 * computed basis.
1835 * Similarly, the matrix U is transposed such that we can
1836 * compute the coefficients c = U s from a schedule row s.
1838 static int node_update_cmap(struct isl_sched_node *node)
1840 isl_mat *H, *U, *Q;
1841 int n_row = isl_mat_rows(node->sched);
1843 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1844 1 + node->nparam, node->nvar);
1846 H = isl_mat_left_hermite(H, 0, &U, &Q);
1847 isl_mat_free(node->cmap);
1848 isl_mat_free(node->cinv);
1849 node->cmap = isl_mat_transpose(Q);
1850 node->cinv = isl_mat_transpose(U);
1851 node->rank = isl_mat_initial_non_zero_cols(H);
1852 isl_mat_free(H);
1854 if (!node->cmap || !node->cinv || node->rank < 0)
1855 return -1;
1856 return 0;
1859 /* How many times should we count the constraints in "edge"?
1861 * If carry is set, then we are counting the number of
1862 * (validity or conditional validity) constraints that will be added
1863 * in setup_carry_lp and we count each edge exactly once.
1865 * Otherwise, we count as follows
1866 * validity -> 1 (>= 0)
1867 * validity+proximity -> 2 (>= 0 and upper bound)
1868 * proximity -> 2 (lower and upper bound)
1869 * local(+any) -> 2 (>= 0 and <= 0)
1871 * If an edge is only marked conditional_validity then it counts
1872 * as zero since it is only checked afterwards.
1874 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1875 * Otherwise, we ignore them.
1877 static int edge_multiplicity(struct isl_sched_edge *edge, int carry,
1878 int use_coincidence)
1880 if (carry && !edge->validity && !edge->conditional_validity)
1881 return 0;
1882 if (carry)
1883 return 1;
1884 if (edge->proximity || edge->local)
1885 return 2;
1886 if (use_coincidence && edge->coincidence)
1887 return 2;
1888 if (edge->validity)
1889 return 1;
1890 return 0;
1893 /* Count the number of equality and inequality constraints
1894 * that will be added for the given map.
1896 * "use_coincidence" is set if we should take into account coincidence edges.
1898 static int count_map_constraints(struct isl_sched_graph *graph,
1899 struct isl_sched_edge *edge, __isl_take isl_map *map,
1900 int *n_eq, int *n_ineq, int carry, int use_coincidence)
1902 isl_basic_set *coef;
1903 int f = edge_multiplicity(edge, carry, use_coincidence);
1905 if (f == 0) {
1906 isl_map_free(map);
1907 return 0;
1910 if (edge->src == edge->dst)
1911 coef = intra_coefficients(graph, edge->src, map);
1912 else
1913 coef = inter_coefficients(graph, edge, map);
1914 if (!coef)
1915 return -1;
1916 *n_eq += f * coef->n_eq;
1917 *n_ineq += f * coef->n_ineq;
1918 isl_basic_set_free(coef);
1920 return 0;
1923 /* Count the number of equality and inequality constraints
1924 * that will be added to the main lp problem.
1925 * We count as follows
1926 * validity -> 1 (>= 0)
1927 * validity+proximity -> 2 (>= 0 and upper bound)
1928 * proximity -> 2 (lower and upper bound)
1929 * local(+any) -> 2 (>= 0 and <= 0)
1931 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1932 * Otherwise, we ignore them.
1934 static int count_constraints(struct isl_sched_graph *graph,
1935 int *n_eq, int *n_ineq, int use_coincidence)
1937 int i;
1939 *n_eq = *n_ineq = 0;
1940 for (i = 0; i < graph->n_edge; ++i) {
1941 struct isl_sched_edge *edge= &graph->edge[i];
1942 isl_map *map = isl_map_copy(edge->map);
1944 if (count_map_constraints(graph, edge, map, n_eq, n_ineq,
1945 0, use_coincidence) < 0)
1946 return -1;
1949 return 0;
1952 /* Count the number of constraints that will be added by
1953 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
1954 * accordingly.
1956 * In practice, add_bound_coefficient_constraints only adds inequalities.
1958 static int count_bound_coefficient_constraints(isl_ctx *ctx,
1959 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
1961 int i;
1963 if (ctx->opt->schedule_max_coefficient == -1)
1964 return 0;
1966 for (i = 0; i < graph->n; ++i)
1967 *n_ineq += 2 * graph->node[i].nparam + 2 * graph->node[i].nvar;
1969 return 0;
1972 /* Add constraints that bound the values of the variable and parameter
1973 * coefficients of the schedule.
1975 * The maximal value of the coefficients is defined by the option
1976 * 'schedule_max_coefficient'.
1978 static int add_bound_coefficient_constraints(isl_ctx *ctx,
1979 struct isl_sched_graph *graph)
1981 int i, j, k;
1982 int max_coefficient;
1983 int total;
1985 max_coefficient = ctx->opt->schedule_max_coefficient;
1987 if (max_coefficient == -1)
1988 return 0;
1990 total = isl_basic_set_total_dim(graph->lp);
1992 for (i = 0; i < graph->n; ++i) {
1993 struct isl_sched_node *node = &graph->node[i];
1994 for (j = 0; j < 2 * node->nparam + 2 * node->nvar; ++j) {
1995 int dim;
1996 k = isl_basic_set_alloc_inequality(graph->lp);
1997 if (k < 0)
1998 return -1;
1999 dim = 1 + node->start + 1 + j;
2000 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2001 isl_int_set_si(graph->lp->ineq[k][dim], -1);
2002 isl_int_set_si(graph->lp->ineq[k][0], max_coefficient);
2006 return 0;
2009 /* Construct an ILP problem for finding schedule coefficients
2010 * that result in non-negative, but small dependence distances
2011 * over all dependences.
2012 * In particular, the dependence distances over proximity edges
2013 * are bounded by m_0 + m_n n and we compute schedule coefficients
2014 * with small values (preferably zero) of m_n and m_0.
2016 * All variables of the ILP are non-negative. The actual coefficients
2017 * may be negative, so each coefficient is represented as the difference
2018 * of two non-negative variables. The negative part always appears
2019 * immediately before the positive part.
2020 * Other than that, the variables have the following order
2022 * - sum of positive and negative parts of m_n coefficients
2023 * - m_0
2024 * - sum of positive and negative parts of all c_n coefficients
2025 * (unconstrained when computing non-parametric schedules)
2026 * - sum of positive and negative parts of all c_x coefficients
2027 * - positive and negative parts of m_n coefficients
2028 * - for each node
2029 * - c_i_0
2030 * - positive and negative parts of c_i_n (if parametric)
2031 * - positive and negative parts of c_i_x
2033 * The c_i_x are not represented directly, but through the columns of
2034 * node->cmap. That is, the computed values are for variable t_i_x
2035 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2037 * The constraints are those from the edges plus two or three equalities
2038 * to express the sums.
2040 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2041 * Otherwise, we ignore them.
2043 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
2044 int use_coincidence)
2046 int i, j;
2047 int k;
2048 unsigned nparam;
2049 unsigned total;
2050 isl_space *dim;
2051 int parametric;
2052 int param_pos;
2053 int n_eq, n_ineq;
2054 int max_constant_term;
2056 max_constant_term = ctx->opt->schedule_max_constant_term;
2058 parametric = ctx->opt->schedule_parametric;
2059 nparam = isl_space_dim(graph->node[0].space, isl_dim_param);
2060 param_pos = 4;
2061 total = param_pos + 2 * nparam;
2062 for (i = 0; i < graph->n; ++i) {
2063 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2064 if (node_update_cmap(node) < 0)
2065 return -1;
2066 node->start = total;
2067 total += 1 + 2 * (node->nparam + node->nvar);
2070 if (count_constraints(graph, &n_eq, &n_ineq, use_coincidence) < 0)
2071 return -1;
2072 if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2073 return -1;
2075 dim = isl_space_set_alloc(ctx, 0, total);
2076 isl_basic_set_free(graph->lp);
2077 n_eq += 2 + parametric;
2078 if (max_constant_term != -1)
2079 n_ineq += graph->n;
2081 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2083 k = isl_basic_set_alloc_equality(graph->lp);
2084 if (k < 0)
2085 return -1;
2086 isl_seq_clr(graph->lp->eq[k], 1 + total);
2087 isl_int_set_si(graph->lp->eq[k][1], -1);
2088 for (i = 0; i < 2 * nparam; ++i)
2089 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
2091 if (parametric) {
2092 k = isl_basic_set_alloc_equality(graph->lp);
2093 if (k < 0)
2094 return -1;
2095 isl_seq_clr(graph->lp->eq[k], 1 + total);
2096 isl_int_set_si(graph->lp->eq[k][3], -1);
2097 for (i = 0; i < graph->n; ++i) {
2098 int pos = 1 + graph->node[i].start + 1;
2100 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2101 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2105 k = isl_basic_set_alloc_equality(graph->lp);
2106 if (k < 0)
2107 return -1;
2108 isl_seq_clr(graph->lp->eq[k], 1 + total);
2109 isl_int_set_si(graph->lp->eq[k][4], -1);
2110 for (i = 0; i < graph->n; ++i) {
2111 struct isl_sched_node *node = &graph->node[i];
2112 int pos = 1 + node->start + 1 + 2 * node->nparam;
2114 for (j = 0; j < 2 * node->nvar; ++j)
2115 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2118 if (max_constant_term != -1)
2119 for (i = 0; i < graph->n; ++i) {
2120 struct isl_sched_node *node = &graph->node[i];
2121 k = isl_basic_set_alloc_inequality(graph->lp);
2122 if (k < 0)
2123 return -1;
2124 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2125 isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1);
2126 isl_int_set_si(graph->lp->ineq[k][0], max_constant_term);
2129 if (add_bound_coefficient_constraints(ctx, graph) < 0)
2130 return -1;
2131 if (add_all_validity_constraints(graph, use_coincidence) < 0)
2132 return -1;
2133 if (add_all_proximity_constraints(graph, use_coincidence) < 0)
2134 return -1;
2136 return 0;
2139 /* Analyze the conflicting constraint found by
2140 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2141 * constraint of one of the edges between distinct nodes, living, moreover
2142 * in distinct SCCs, then record the source and sink SCC as this may
2143 * be a good place to cut between SCCs.
2145 static int check_conflict(int con, void *user)
2147 int i;
2148 struct isl_sched_graph *graph = user;
2150 if (graph->src_scc >= 0)
2151 return 0;
2153 con -= graph->lp->n_eq;
2155 if (con >= graph->lp->n_ineq)
2156 return 0;
2158 for (i = 0; i < graph->n_edge; ++i) {
2159 if (!graph->edge[i].validity)
2160 continue;
2161 if (graph->edge[i].src == graph->edge[i].dst)
2162 continue;
2163 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
2164 continue;
2165 if (graph->edge[i].start > con)
2166 continue;
2167 if (graph->edge[i].end <= con)
2168 continue;
2169 graph->src_scc = graph->edge[i].src->scc;
2170 graph->dst_scc = graph->edge[i].dst->scc;
2173 return 0;
2176 /* Check whether the next schedule row of the given node needs to be
2177 * non-trivial. Lower-dimensional domains may have some trivial rows,
2178 * but as soon as the number of remaining required non-trivial rows
2179 * is as large as the number or remaining rows to be computed,
2180 * all remaining rows need to be non-trivial.
2182 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
2184 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
2187 /* Solve the ILP problem constructed in setup_lp.
2188 * For each node such that all the remaining rows of its schedule
2189 * need to be non-trivial, we construct a non-triviality region.
2190 * This region imposes that the next row is independent of previous rows.
2191 * In particular the coefficients c_i_x are represented by t_i_x
2192 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2193 * its first columns span the rows of the previously computed part
2194 * of the schedule. The non-triviality region enforces that at least
2195 * one of the remaining components of t_i_x is non-zero, i.e.,
2196 * that the new schedule row depends on at least one of the remaining
2197 * columns of Q.
2199 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
2201 int i;
2202 isl_vec *sol;
2203 isl_basic_set *lp;
2205 for (i = 0; i < graph->n; ++i) {
2206 struct isl_sched_node *node = &graph->node[i];
2207 int skip = node->rank;
2208 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
2209 if (needs_row(graph, node))
2210 graph->region[i].len = 2 * (node->nvar - skip);
2211 else
2212 graph->region[i].len = 0;
2214 lp = isl_basic_set_copy(graph->lp);
2215 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
2216 graph->region, &check_conflict, graph);
2217 return sol;
2220 /* Update the schedules of all nodes based on the given solution
2221 * of the LP problem.
2222 * The new row is added to the current band.
2223 * All possibly negative coefficients are encoded as a difference
2224 * of two non-negative variables, so we need to perform the subtraction
2225 * here. Moreover, if use_cmap is set, then the solution does
2226 * not refer to the actual coefficients c_i_x, but instead to variables
2227 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2228 * In this case, we then also need to perform this multiplication
2229 * to obtain the values of c_i_x.
2231 * If coincident is set, then the caller guarantees that the new
2232 * row satisfies the coincidence constraints.
2234 static int update_schedule(struct isl_sched_graph *graph,
2235 __isl_take isl_vec *sol, int use_cmap, int coincident)
2237 int i, j;
2238 isl_vec *csol = NULL;
2240 if (!sol)
2241 goto error;
2242 if (sol->size == 0)
2243 isl_die(sol->ctx, isl_error_internal,
2244 "no solution found", goto error);
2245 if (graph->n_total_row >= graph->max_row)
2246 isl_die(sol->ctx, isl_error_internal,
2247 "too many schedule rows", goto error);
2249 for (i = 0; i < graph->n; ++i) {
2250 struct isl_sched_node *node = &graph->node[i];
2251 int pos = node->start;
2252 int row = isl_mat_rows(node->sched);
2254 isl_vec_free(csol);
2255 csol = isl_vec_alloc(sol->ctx, node->nvar);
2256 if (!csol)
2257 goto error;
2259 isl_map_free(node->sched_map);
2260 node->sched_map = NULL;
2261 node->sched = isl_mat_add_rows(node->sched, 1);
2262 if (!node->sched)
2263 goto error;
2264 node->sched = isl_mat_set_element(node->sched, row, 0,
2265 sol->el[1 + pos]);
2266 for (j = 0; j < node->nparam + node->nvar; ++j)
2267 isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
2268 sol->el[1 + pos + 1 + 2 * j + 1],
2269 sol->el[1 + pos + 1 + 2 * j]);
2270 for (j = 0; j < node->nparam; ++j)
2271 node->sched = isl_mat_set_element(node->sched,
2272 row, 1 + j, sol->el[1+pos+1+2*j+1]);
2273 for (j = 0; j < node->nvar; ++j)
2274 isl_int_set(csol->el[j],
2275 sol->el[1+pos+1+2*(node->nparam+j)+1]);
2276 if (use_cmap)
2277 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
2278 csol);
2279 if (!csol)
2280 goto error;
2281 for (j = 0; j < node->nvar; ++j)
2282 node->sched = isl_mat_set_element(node->sched,
2283 row, 1 + node->nparam + j, csol->el[j]);
2284 node->band[graph->n_total_row] = graph->n_band;
2285 node->coincident[graph->n_total_row] = coincident;
2287 isl_vec_free(sol);
2288 isl_vec_free(csol);
2290 graph->n_row++;
2291 graph->n_total_row++;
2293 return 0;
2294 error:
2295 isl_vec_free(sol);
2296 isl_vec_free(csol);
2297 return -1;
2300 /* Convert row "row" of node->sched into an isl_aff living in "ls"
2301 * and return this isl_aff.
2303 static __isl_give isl_aff *extract_schedule_row(__isl_take isl_local_space *ls,
2304 struct isl_sched_node *node, int row)
2306 int j;
2307 isl_int v;
2308 isl_aff *aff;
2310 isl_int_init(v);
2312 aff = isl_aff_zero_on_domain(ls);
2313 isl_mat_get_element(node->sched, row, 0, &v);
2314 aff = isl_aff_set_constant(aff, v);
2315 for (j = 0; j < node->nparam; ++j) {
2316 isl_mat_get_element(node->sched, row, 1 + j, &v);
2317 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
2319 for (j = 0; j < node->nvar; ++j) {
2320 isl_mat_get_element(node->sched, row, 1 + node->nparam + j, &v);
2321 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
2324 isl_int_clear(v);
2326 return aff;
2329 /* Convert node->sched into a multi_aff and return this multi_aff.
2331 * The result is defined over the uncompressed node domain.
2333 static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
2334 struct isl_sched_node *node)
2336 int i;
2337 isl_space *space;
2338 isl_local_space *ls;
2339 isl_aff *aff;
2340 isl_multi_aff *ma;
2341 int nrow, ncol;
2343 nrow = isl_mat_rows(node->sched);
2344 ncol = isl_mat_cols(node->sched) - 1;
2345 if (node->compressed)
2346 space = isl_multi_aff_get_domain_space(node->decompress);
2347 else
2348 space = isl_space_copy(node->space);
2349 ls = isl_local_space_from_space(isl_space_copy(space));
2350 space = isl_space_from_domain(space);
2351 space = isl_space_add_dims(space, isl_dim_out, nrow);
2352 ma = isl_multi_aff_zero(space);
2354 for (i = 0; i < nrow; ++i) {
2355 aff = extract_schedule_row(isl_local_space_copy(ls), node, i);
2356 ma = isl_multi_aff_set_aff(ma, i, aff);
2359 isl_local_space_free(ls);
2361 if (node->compressed)
2362 ma = isl_multi_aff_pullback_multi_aff(ma,
2363 isl_multi_aff_copy(node->compress));
2365 return ma;
2368 /* Convert node->sched into a map and return this map.
2370 * The result is cached in node->sched_map, which needs to be released
2371 * whenever node->sched is updated.
2372 * It is defined over the uncompressed node domain.
2374 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
2376 if (!node->sched_map) {
2377 isl_multi_aff *ma;
2379 ma = node_extract_schedule_multi_aff(node);
2380 node->sched_map = isl_map_from_multi_aff(ma);
2383 return isl_map_copy(node->sched_map);
2386 /* Construct a map that can be used to update a dependence relation
2387 * based on the current schedule.
2388 * That is, construct a map expressing that source and sink
2389 * are executed within the same iteration of the current schedule.
2390 * This map can then be intersected with the dependence relation.
2391 * This is not the most efficient way, but this shouldn't be a critical
2392 * operation.
2394 static __isl_give isl_map *specializer(struct isl_sched_node *src,
2395 struct isl_sched_node *dst)
2397 isl_map *src_sched, *dst_sched;
2399 src_sched = node_extract_schedule(src);
2400 dst_sched = node_extract_schedule(dst);
2401 return isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
2404 /* Intersect the domains of the nested relations in domain and range
2405 * of "umap" with "map".
2407 static __isl_give isl_union_map *intersect_domains(
2408 __isl_take isl_union_map *umap, __isl_keep isl_map *map)
2410 isl_union_set *uset;
2412 umap = isl_union_map_zip(umap);
2413 uset = isl_union_set_from_set(isl_map_wrap(isl_map_copy(map)));
2414 umap = isl_union_map_intersect_domain(umap, uset);
2415 umap = isl_union_map_zip(umap);
2416 return umap;
2419 /* Update the dependence relation of the given edge based
2420 * on the current schedule.
2421 * If the dependence is carried completely by the current schedule, then
2422 * it is removed from the edge_tables. It is kept in the list of edges
2423 * as otherwise all edge_tables would have to be recomputed.
2425 static int update_edge(struct isl_sched_graph *graph,
2426 struct isl_sched_edge *edge)
2428 isl_map *id;
2430 id = specializer(edge->src, edge->dst);
2431 edge->map = isl_map_intersect(edge->map, isl_map_copy(id));
2432 if (!edge->map)
2433 goto error;
2435 if (edge->tagged_condition) {
2436 edge->tagged_condition =
2437 intersect_domains(edge->tagged_condition, id);
2438 if (!edge->tagged_condition)
2439 goto error;
2441 if (edge->tagged_validity) {
2442 edge->tagged_validity =
2443 intersect_domains(edge->tagged_validity, id);
2444 if (!edge->tagged_validity)
2445 goto error;
2448 isl_map_free(id);
2449 if (isl_map_plain_is_empty(edge->map))
2450 graph_remove_edge(graph, edge);
2452 return 0;
2453 error:
2454 isl_map_free(id);
2455 return -1;
2458 /* Update the dependence relations of all edges based on the current schedule.
2460 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
2462 int i;
2464 for (i = graph->n_edge - 1; i >= 0; --i) {
2465 if (update_edge(graph, &graph->edge[i]) < 0)
2466 return -1;
2469 return 0;
2472 static void next_band(struct isl_sched_graph *graph)
2474 graph->band_start = graph->n_total_row;
2475 graph->n_band++;
2478 /* Topologically sort statements mapped to the same schedule iteration
2479 * and add a row to the schedule corresponding to this order.
2481 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
2483 int i, j;
2485 if (graph->n <= 1)
2486 return 0;
2488 if (update_edges(ctx, graph) < 0)
2489 return -1;
2491 if (graph->n_edge == 0)
2492 return 0;
2494 if (detect_sccs(ctx, graph) < 0)
2495 return -1;
2497 if (graph->n_total_row >= graph->max_row)
2498 isl_die(ctx, isl_error_internal,
2499 "too many schedule rows", return -1);
2501 for (i = 0; i < graph->n; ++i) {
2502 struct isl_sched_node *node = &graph->node[i];
2503 int row = isl_mat_rows(node->sched);
2504 int cols = isl_mat_cols(node->sched);
2506 isl_map_free(node->sched_map);
2507 node->sched_map = NULL;
2508 node->sched = isl_mat_add_rows(node->sched, 1);
2509 if (!node->sched)
2510 return -1;
2511 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2512 node->scc);
2513 for (j = 1; j < cols; ++j)
2514 node->sched = isl_mat_set_element_si(node->sched,
2515 row, j, 0);
2516 node->band[graph->n_total_row] = graph->n_band;
2519 graph->n_total_row++;
2520 next_band(graph);
2522 return 0;
2525 /* Construct an isl_schedule based on the computed schedule stored
2526 * in graph and with parameters specified by dim.
2528 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
2529 __isl_take isl_space *dim)
2531 int i;
2532 isl_ctx *ctx;
2533 isl_schedule *sched = NULL;
2535 if (!dim)
2536 return NULL;
2538 ctx = isl_space_get_ctx(dim);
2539 sched = isl_calloc(ctx, struct isl_schedule,
2540 sizeof(struct isl_schedule) +
2541 (graph->n - 1) * sizeof(struct isl_schedule_node));
2542 if (!sched)
2543 goto error;
2545 sched->ref = 1;
2546 sched->n = graph->n;
2547 sched->n_band = graph->n_band;
2548 sched->n_total_row = graph->n_total_row;
2550 for (i = 0; i < sched->n; ++i) {
2551 int r, b;
2552 int *band_end, *band_id, *coincident;
2554 sched->node[i].sched =
2555 node_extract_schedule_multi_aff(&graph->node[i]);
2556 if (!sched->node[i].sched)
2557 goto error;
2559 sched->node[i].n_band = graph->n_band;
2560 if (graph->n_band == 0)
2561 continue;
2563 band_end = isl_alloc_array(ctx, int, graph->n_band);
2564 band_id = isl_alloc_array(ctx, int, graph->n_band);
2565 coincident = isl_alloc_array(ctx, int, graph->n_total_row);
2566 sched->node[i].band_end = band_end;
2567 sched->node[i].band_id = band_id;
2568 sched->node[i].coincident = coincident;
2569 if (!band_end || !band_id || !coincident)
2570 goto error;
2572 for (r = 0; r < graph->n_total_row; ++r)
2573 coincident[r] = graph->node[i].coincident[r];
2574 for (r = b = 0; r < graph->n_total_row; ++r) {
2575 if (graph->node[i].band[r] == b)
2576 continue;
2577 band_end[b++] = r;
2578 if (graph->node[i].band[r] == -1)
2579 break;
2581 if (r == graph->n_total_row)
2582 band_end[b++] = r;
2583 sched->node[i].n_band = b;
2584 for (--b; b >= 0; --b)
2585 band_id[b] = graph->node[i].band_id[b];
2588 sched->dim = dim;
2590 return sched;
2591 error:
2592 isl_space_free(dim);
2593 isl_schedule_free(sched);
2594 return NULL;
2597 /* Copy nodes that satisfy node_pred from the src dependence graph
2598 * to the dst dependence graph.
2600 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
2601 int (*node_pred)(struct isl_sched_node *node, int data), int data)
2603 int i;
2605 dst->n = 0;
2606 for (i = 0; i < src->n; ++i) {
2607 int j;
2609 if (!node_pred(&src->node[i], data))
2610 continue;
2612 j = dst->n;
2613 dst->node[j].space = isl_space_copy(src->node[i].space);
2614 dst->node[j].compressed = src->node[i].compressed;
2615 dst->node[j].hull = isl_set_copy(src->node[i].hull);
2616 dst->node[j].compress =
2617 isl_multi_aff_copy(src->node[i].compress);
2618 dst->node[j].decompress =
2619 isl_multi_aff_copy(src->node[i].decompress);
2620 dst->node[j].nvar = src->node[i].nvar;
2621 dst->node[j].nparam = src->node[i].nparam;
2622 dst->node[j].sched = isl_mat_copy(src->node[i].sched);
2623 dst->node[j].sched_map = isl_map_copy(src->node[i].sched_map);
2624 dst->node[j].band = src->node[i].band;
2625 dst->node[j].band_id = src->node[i].band_id;
2626 dst->node[j].coincident = src->node[i].coincident;
2627 dst->n++;
2629 if (!dst->node[j].space || !dst->node[j].sched)
2630 return -1;
2631 if (dst->node[j].compressed &&
2632 (!dst->node[j].hull || !dst->node[j].compress ||
2633 !dst->node[j].decompress))
2634 return -1;
2637 return 0;
2640 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2641 * to the dst dependence graph.
2642 * If the source or destination node of the edge is not in the destination
2643 * graph, then it must be a backward proximity edge and it should simply
2644 * be ignored.
2646 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
2647 struct isl_sched_graph *src,
2648 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
2650 int i;
2651 enum isl_edge_type t;
2653 dst->n_edge = 0;
2654 for (i = 0; i < src->n_edge; ++i) {
2655 struct isl_sched_edge *edge = &src->edge[i];
2656 isl_map *map;
2657 isl_union_map *tagged_condition;
2658 isl_union_map *tagged_validity;
2659 struct isl_sched_node *dst_src, *dst_dst;
2661 if (!edge_pred(edge, data))
2662 continue;
2664 if (isl_map_plain_is_empty(edge->map))
2665 continue;
2667 dst_src = graph_find_node(ctx, dst, edge->src->space);
2668 dst_dst = graph_find_node(ctx, dst, edge->dst->space);
2669 if (!dst_src || !dst_dst) {
2670 if (edge->validity || edge->conditional_validity)
2671 isl_die(ctx, isl_error_internal,
2672 "backward (conditional) validity edge",
2673 return -1);
2674 continue;
2677 map = isl_map_copy(edge->map);
2678 tagged_condition = isl_union_map_copy(edge->tagged_condition);
2679 tagged_validity = isl_union_map_copy(edge->tagged_validity);
2681 dst->edge[dst->n_edge].src = dst_src;
2682 dst->edge[dst->n_edge].dst = dst_dst;
2683 dst->edge[dst->n_edge].map = map;
2684 dst->edge[dst->n_edge].tagged_condition = tagged_condition;
2685 dst->edge[dst->n_edge].tagged_validity = tagged_validity;
2686 dst->edge[dst->n_edge].validity = edge->validity;
2687 dst->edge[dst->n_edge].proximity = edge->proximity;
2688 dst->edge[dst->n_edge].coincidence = edge->coincidence;
2689 dst->edge[dst->n_edge].condition = edge->condition;
2690 dst->edge[dst->n_edge].conditional_validity =
2691 edge->conditional_validity;
2692 dst->n_edge++;
2694 if (edge->tagged_condition && !tagged_condition)
2695 return -1;
2696 if (edge->tagged_validity && !tagged_validity)
2697 return -1;
2699 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
2700 if (edge !=
2701 graph_find_edge(src, t, edge->src, edge->dst))
2702 continue;
2703 if (graph_edge_table_add(ctx, dst, t,
2704 &dst->edge[dst->n_edge - 1]) < 0)
2705 return -1;
2709 return 0;
2712 /* Given a "src" dependence graph that contains the nodes from "dst"
2713 * that satisfy node_pred, copy the schedule computed in "src"
2714 * for those nodes back to "dst".
2716 static int copy_schedule(struct isl_sched_graph *dst,
2717 struct isl_sched_graph *src,
2718 int (*node_pred)(struct isl_sched_node *node, int data), int data)
2720 int i;
2722 src->n = 0;
2723 for (i = 0; i < dst->n; ++i) {
2724 if (!node_pred(&dst->node[i], data))
2725 continue;
2726 isl_mat_free(dst->node[i].sched);
2727 isl_map_free(dst->node[i].sched_map);
2728 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
2729 dst->node[i].sched_map =
2730 isl_map_copy(src->node[src->n].sched_map);
2731 src->n++;
2734 dst->max_row = src->max_row;
2735 dst->n_total_row = src->n_total_row;
2736 dst->n_band = src->n_band;
2738 return 0;
2741 /* Compute the maximal number of variables over all nodes.
2742 * This is the maximal number of linearly independent schedule
2743 * rows that we need to compute.
2744 * Just in case we end up in a part of the dependence graph
2745 * with only lower-dimensional domains, we make sure we will
2746 * compute the required amount of extra linearly independent rows.
2748 static int compute_maxvar(struct isl_sched_graph *graph)
2750 int i;
2752 graph->maxvar = 0;
2753 for (i = 0; i < graph->n; ++i) {
2754 struct isl_sched_node *node = &graph->node[i];
2755 int nvar;
2757 if (node_update_cmap(node) < 0)
2758 return -1;
2759 nvar = node->nvar + graph->n_row - node->rank;
2760 if (nvar > graph->maxvar)
2761 graph->maxvar = nvar;
2764 return 0;
2767 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
2768 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
2770 /* Compute a schedule for a subgraph of "graph". In particular, for
2771 * the graph composed of nodes that satisfy node_pred and edges that
2772 * that satisfy edge_pred. The caller should precompute the number
2773 * of nodes and edges that satisfy these predicates and pass them along
2774 * as "n" and "n_edge".
2775 * If the subgraph is known to consist of a single component, then wcc should
2776 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2777 * Otherwise, we call compute_schedule, which will check whether the subgraph
2778 * is connected.
2780 static int compute_sub_schedule(isl_ctx *ctx,
2781 struct isl_sched_graph *graph, int n, int n_edge,
2782 int (*node_pred)(struct isl_sched_node *node, int data),
2783 int (*edge_pred)(struct isl_sched_edge *edge, int data),
2784 int data, int wcc)
2786 struct isl_sched_graph split = { 0 };
2787 int t;
2789 if (graph_alloc(ctx, &split, n, n_edge) < 0)
2790 goto error;
2791 if (copy_nodes(&split, graph, node_pred, data) < 0)
2792 goto error;
2793 if (graph_init_table(ctx, &split) < 0)
2794 goto error;
2795 for (t = 0; t <= isl_edge_last; ++t)
2796 split.max_edge[t] = graph->max_edge[t];
2797 if (graph_init_edge_tables(ctx, &split) < 0)
2798 goto error;
2799 if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
2800 goto error;
2801 split.n_row = graph->n_row;
2802 split.max_row = graph->max_row;
2803 split.n_total_row = graph->n_total_row;
2804 split.n_band = graph->n_band;
2805 split.band_start = graph->band_start;
2807 if (wcc && compute_schedule_wcc(ctx, &split) < 0)
2808 goto error;
2809 if (!wcc && compute_schedule(ctx, &split) < 0)
2810 goto error;
2812 copy_schedule(graph, &split, node_pred, data);
2814 graph_free(ctx, &split);
2815 return 0;
2816 error:
2817 graph_free(ctx, &split);
2818 return -1;
2821 static int node_scc_exactly(struct isl_sched_node *node, int scc)
2823 return node->scc == scc;
2826 static int node_scc_at_most(struct isl_sched_node *node, int scc)
2828 return node->scc <= scc;
2831 static int node_scc_at_least(struct isl_sched_node *node, int scc)
2833 return node->scc >= scc;
2836 static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
2838 return edge->src->scc == scc && edge->dst->scc == scc;
2841 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
2843 return edge->dst->scc <= scc;
2846 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
2848 return edge->src->scc >= scc;
2851 /* Pad the schedules of all nodes with zero rows such that in the end
2852 * they all have graph->n_total_row rows.
2853 * The extra rows don't belong to any band, so they get assigned band number -1.
2855 static int pad_schedule(struct isl_sched_graph *graph)
2857 int i, j;
2859 for (i = 0; i < graph->n; ++i) {
2860 struct isl_sched_node *node = &graph->node[i];
2861 int row = isl_mat_rows(node->sched);
2862 if (graph->n_total_row > row) {
2863 isl_map_free(node->sched_map);
2864 node->sched_map = NULL;
2866 node->sched = isl_mat_add_zero_rows(node->sched,
2867 graph->n_total_row - row);
2868 if (!node->sched)
2869 return -1;
2870 for (j = row; j < graph->n_total_row; ++j)
2871 node->band[j] = -1;
2874 return 0;
2877 /* Reset the current band by dropping all its schedule rows.
2879 static int reset_band(struct isl_sched_graph *graph)
2881 int i;
2882 int drop;
2884 drop = graph->n_total_row - graph->band_start;
2885 graph->n_total_row -= drop;
2886 graph->n_row -= drop;
2888 for (i = 0; i < graph->n; ++i) {
2889 struct isl_sched_node *node = &graph->node[i];
2891 isl_map_free(node->sched_map);
2892 node->sched_map = NULL;
2894 node->sched = isl_mat_drop_rows(node->sched,
2895 graph->band_start, drop);
2897 if (!node->sched)
2898 return -1;
2901 return 0;
2904 /* Split the current graph into two parts and compute a schedule for each
2905 * part individually. In particular, one part consists of all SCCs up
2906 * to and including graph->src_scc, while the other part contains the other
2907 * SCCS.
2909 * The split is enforced in the schedule by constant rows with two different
2910 * values (0 and 1). These constant rows replace the previously computed rows
2911 * in the current band.
2912 * It would be possible to reuse them as the first rows in the next
2913 * band, but recomputing them may result in better rows as we are looking
2914 * at a smaller part of the dependence graph.
2916 * Since we do not enforce coincidence, we conservatively mark the
2917 * splitting row as not coincident.
2919 * The band_id of the second group is set to n, where n is the number
2920 * of nodes in the first group. This ensures that the band_ids over
2921 * the two groups remain disjoint, even if either or both of the two
2922 * groups contain independent components.
2924 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2926 int i, j, n, e1, e2;
2927 int n_total_row, orig_total_row;
2928 int n_band, orig_band;
2930 if (graph->n_total_row >= graph->max_row)
2931 isl_die(ctx, isl_error_internal,
2932 "too many schedule rows", return -1);
2934 if (reset_band(graph) < 0)
2935 return -1;
2937 n = 0;
2938 for (i = 0; i < graph->n; ++i) {
2939 struct isl_sched_node *node = &graph->node[i];
2940 int row = isl_mat_rows(node->sched);
2941 int cols = isl_mat_cols(node->sched);
2942 int before = node->scc <= graph->src_scc;
2944 if (before)
2945 n++;
2947 isl_map_free(node->sched_map);
2948 node->sched_map = NULL;
2949 node->sched = isl_mat_add_rows(node->sched, 1);
2950 if (!node->sched)
2951 return -1;
2952 node->sched = isl_mat_set_element_si(node->sched, row, 0,
2953 !before);
2954 for (j = 1; j < cols; ++j)
2955 node->sched = isl_mat_set_element_si(node->sched,
2956 row, j, 0);
2957 node->band[graph->n_total_row] = graph->n_band;
2958 node->coincident[graph->n_total_row] = 0;
2961 e1 = e2 = 0;
2962 for (i = 0; i < graph->n_edge; ++i) {
2963 if (graph->edge[i].dst->scc <= graph->src_scc)
2964 e1++;
2965 if (graph->edge[i].src->scc > graph->src_scc)
2966 e2++;
2969 graph->n_total_row++;
2970 next_band(graph);
2972 for (i = 0; i < graph->n; ++i) {
2973 struct isl_sched_node *node = &graph->node[i];
2974 if (node->scc > graph->src_scc)
2975 node->band_id[graph->n_band] = n;
2978 orig_total_row = graph->n_total_row;
2979 orig_band = graph->n_band;
2980 if (compute_sub_schedule(ctx, graph, n, e1,
2981 &node_scc_at_most, &edge_dst_scc_at_most,
2982 graph->src_scc, 0) < 0)
2983 return -1;
2984 n_total_row = graph->n_total_row;
2985 graph->n_total_row = orig_total_row;
2986 n_band = graph->n_band;
2987 graph->n_band = orig_band;
2988 if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
2989 &node_scc_at_least, &edge_src_scc_at_least,
2990 graph->src_scc + 1, 0) < 0)
2991 return -1;
2992 if (n_total_row > graph->n_total_row)
2993 graph->n_total_row = n_total_row;
2994 if (n_band > graph->n_band)
2995 graph->n_band = n_band;
2997 return pad_schedule(graph);
3000 /* Compute the next band of the schedule after updating the dependence
3001 * relations based on the the current schedule.
3003 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
3005 if (update_edges(ctx, graph) < 0)
3006 return -1;
3007 next_band(graph);
3009 return compute_schedule(ctx, graph);
3012 /* Add constraints to graph->lp that force the dependence "map" (which
3013 * is part of the dependence relation of "edge")
3014 * to be respected and attempt to carry it, where the edge is one from
3015 * a node j to itself. "pos" is the sequence number of the given map.
3016 * That is, add constraints that enforce
3018 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3019 * = c_j_x (y - x) >= e_i
3021 * for each (x,y) in R.
3022 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3023 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3024 * with each coefficient in c_j_x represented as a pair of non-negative
3025 * coefficients.
3027 static int add_intra_constraints(struct isl_sched_graph *graph,
3028 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
3030 unsigned total;
3031 isl_ctx *ctx = isl_map_get_ctx(map);
3032 isl_space *dim;
3033 isl_dim_map *dim_map;
3034 isl_basic_set *coef;
3035 struct isl_sched_node *node = edge->src;
3037 coef = intra_coefficients(graph, node, map);
3038 if (!coef)
3039 return -1;
3041 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
3043 total = isl_basic_set_total_dim(graph->lp);
3044 dim_map = isl_dim_map_alloc(ctx, total);
3045 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3046 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
3047 isl_space_dim(dim, isl_dim_set), 1,
3048 node->nvar, -1);
3049 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
3050 isl_space_dim(dim, isl_dim_set), 1,
3051 node->nvar, 1);
3052 graph->lp = isl_basic_set_extend_constraints(graph->lp,
3053 coef->n_eq, coef->n_ineq);
3054 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
3055 coef, dim_map);
3056 isl_space_free(dim);
3058 return 0;
3061 /* Add constraints to graph->lp that force the dependence "map" (which
3062 * is part of the dependence relation of "edge")
3063 * to be respected and attempt to carry it, where the edge is one from
3064 * node j to node k. "pos" is the sequence number of the given map.
3065 * That is, add constraints that enforce
3067 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3069 * for each (x,y) in R.
3070 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3071 * of valid constraints for R and then plug in
3072 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3073 * with each coefficient (except e_i, c_k_0 and c_j_0)
3074 * represented as a pair of non-negative coefficients.
3076 static int add_inter_constraints(struct isl_sched_graph *graph,
3077 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
3079 unsigned total;
3080 isl_ctx *ctx = isl_map_get_ctx(map);
3081 isl_space *dim;
3082 isl_dim_map *dim_map;
3083 isl_basic_set *coef;
3084 struct isl_sched_node *src = edge->src;
3085 struct isl_sched_node *dst = edge->dst;
3087 coef = inter_coefficients(graph, edge, map);
3088 if (!coef)
3089 return -1;
3091 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
3093 total = isl_basic_set_total_dim(graph->lp);
3094 dim_map = isl_dim_map_alloc(ctx, total);
3096 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3098 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
3099 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
3100 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
3101 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
3102 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
3103 dst->nvar, -1);
3104 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
3105 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
3106 dst->nvar, 1);
3108 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
3109 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
3110 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
3111 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
3112 isl_space_dim(dim, isl_dim_set), 1,
3113 src->nvar, 1);
3114 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
3115 isl_space_dim(dim, isl_dim_set), 1,
3116 src->nvar, -1);
3118 graph->lp = isl_basic_set_extend_constraints(graph->lp,
3119 coef->n_eq, coef->n_ineq);
3120 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
3121 coef, dim_map);
3122 isl_space_free(dim);
3124 return 0;
3127 /* Add constraints to graph->lp that force all (conditional) validity
3128 * dependences to be respected and attempt to carry them.
3130 static int add_all_constraints(struct isl_sched_graph *graph)
3132 int i, j;
3133 int pos;
3135 pos = 0;
3136 for (i = 0; i < graph->n_edge; ++i) {
3137 struct isl_sched_edge *edge= &graph->edge[i];
3139 if (!edge->validity && !edge->conditional_validity)
3140 continue;
3142 for (j = 0; j < edge->map->n; ++j) {
3143 isl_basic_map *bmap;
3144 isl_map *map;
3146 bmap = isl_basic_map_copy(edge->map->p[j]);
3147 map = isl_map_from_basic_map(bmap);
3149 if (edge->src == edge->dst &&
3150 add_intra_constraints(graph, edge, map, pos) < 0)
3151 return -1;
3152 if (edge->src != edge->dst &&
3153 add_inter_constraints(graph, edge, map, pos) < 0)
3154 return -1;
3155 ++pos;
3159 return 0;
3162 /* Count the number of equality and inequality constraints
3163 * that will be added to the carry_lp problem.
3164 * We count each edge exactly once.
3166 static int count_all_constraints(struct isl_sched_graph *graph,
3167 int *n_eq, int *n_ineq)
3169 int i, j;
3171 *n_eq = *n_ineq = 0;
3172 for (i = 0; i < graph->n_edge; ++i) {
3173 struct isl_sched_edge *edge= &graph->edge[i];
3174 for (j = 0; j < edge->map->n; ++j) {
3175 isl_basic_map *bmap;
3176 isl_map *map;
3178 bmap = isl_basic_map_copy(edge->map->p[j]);
3179 map = isl_map_from_basic_map(bmap);
3181 if (count_map_constraints(graph, edge, map,
3182 n_eq, n_ineq, 1, 0) < 0)
3183 return -1;
3187 return 0;
3190 /* Construct an LP problem for finding schedule coefficients
3191 * such that the schedule carries as many dependences as possible.
3192 * In particular, for each dependence i, we bound the dependence distance
3193 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3194 * of all e_i's. Dependence with e_i = 0 in the solution are simply
3195 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3196 * Note that if the dependence relation is a union of basic maps,
3197 * then we have to consider each basic map individually as it may only
3198 * be possible to carry the dependences expressed by some of those
3199 * basic maps and not all off them.
3200 * Below, we consider each of those basic maps as a separate "edge".
3202 * All variables of the LP are non-negative. The actual coefficients
3203 * may be negative, so each coefficient is represented as the difference
3204 * of two non-negative variables. The negative part always appears
3205 * immediately before the positive part.
3206 * Other than that, the variables have the following order
3208 * - sum of (1 - e_i) over all edges
3209 * - sum of positive and negative parts of all c_n coefficients
3210 * (unconstrained when computing non-parametric schedules)
3211 * - sum of positive and negative parts of all c_x coefficients
3212 * - for each edge
3213 * - e_i
3214 * - for each node
3215 * - c_i_0
3216 * - positive and negative parts of c_i_n (if parametric)
3217 * - positive and negative parts of c_i_x
3219 * The constraints are those from the (validity) edges plus three equalities
3220 * to express the sums and n_edge inequalities to express e_i <= 1.
3222 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
3224 int i, j;
3225 int k;
3226 isl_space *dim;
3227 unsigned total;
3228 int n_eq, n_ineq;
3229 int n_edge;
3231 n_edge = 0;
3232 for (i = 0; i < graph->n_edge; ++i)
3233 n_edge += graph->edge[i].map->n;
3235 total = 3 + n_edge;
3236 for (i = 0; i < graph->n; ++i) {
3237 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
3238 node->start = total;
3239 total += 1 + 2 * (node->nparam + node->nvar);
3242 if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
3243 return -1;
3244 if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
3245 return -1;
3247 dim = isl_space_set_alloc(ctx, 0, total);
3248 isl_basic_set_free(graph->lp);
3249 n_eq += 3;
3250 n_ineq += n_edge;
3251 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
3252 graph->lp = isl_basic_set_set_rational(graph->lp);
3254 k = isl_basic_set_alloc_equality(graph->lp);
3255 if (k < 0)
3256 return -1;
3257 isl_seq_clr(graph->lp->eq[k], 1 + total);
3258 isl_int_set_si(graph->lp->eq[k][0], -n_edge);
3259 isl_int_set_si(graph->lp->eq[k][1], 1);
3260 for (i = 0; i < n_edge; ++i)
3261 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
3263 k = isl_basic_set_alloc_equality(graph->lp);
3264 if (k < 0)
3265 return -1;
3266 isl_seq_clr(graph->lp->eq[k], 1 + total);
3267 isl_int_set_si(graph->lp->eq[k][2], -1);
3268 for (i = 0; i < graph->n; ++i) {
3269 int pos = 1 + graph->node[i].start + 1;
3271 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
3272 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
3275 k = isl_basic_set_alloc_equality(graph->lp);
3276 if (k < 0)
3277 return -1;
3278 isl_seq_clr(graph->lp->eq[k], 1 + total);
3279 isl_int_set_si(graph->lp->eq[k][3], -1);
3280 for (i = 0; i < graph->n; ++i) {
3281 struct isl_sched_node *node = &graph->node[i];
3282 int pos = 1 + node->start + 1 + 2 * node->nparam;
3284 for (j = 0; j < 2 * node->nvar; ++j)
3285 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
3288 for (i = 0; i < n_edge; ++i) {
3289 k = isl_basic_set_alloc_inequality(graph->lp);
3290 if (k < 0)
3291 return -1;
3292 isl_seq_clr(graph->lp->ineq[k], 1 + total);
3293 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
3294 isl_int_set_si(graph->lp->ineq[k][0], 1);
3297 if (add_bound_coefficient_constraints(ctx, graph) < 0)
3298 return -1;
3299 if (add_all_constraints(graph) < 0)
3300 return -1;
3302 return 0;
3305 /* If the schedule_split_scaled option is set and if the linear
3306 * parts of the scheduling rows for all nodes in the graphs have
3307 * non-trivial common divisor, then split off the constant term
3308 * from the linear part.
3309 * The constant term is then placed in a separate band and
3310 * the linear part is reduced.
3312 static int split_scaled(isl_ctx *ctx, struct isl_sched_graph *graph)
3314 int i;
3315 int row;
3316 isl_int gcd, gcd_i;
3318 if (!ctx->opt->schedule_split_scaled)
3319 return 0;
3320 if (graph->n <= 1)
3321 return 0;
3323 if (graph->n_total_row >= graph->max_row)
3324 isl_die(ctx, isl_error_internal,
3325 "too many schedule rows", return -1);
3327 isl_int_init(gcd);
3328 isl_int_init(gcd_i);
3330 isl_int_set_si(gcd, 0);
3332 row = isl_mat_rows(graph->node[0].sched) - 1;
3334 for (i = 0; i < graph->n; ++i) {
3335 struct isl_sched_node *node = &graph->node[i];
3336 int cols = isl_mat_cols(node->sched);
3338 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
3339 isl_int_gcd(gcd, gcd, gcd_i);
3342 isl_int_clear(gcd_i);
3344 if (isl_int_cmp_si(gcd, 1) <= 0) {
3345 isl_int_clear(gcd);
3346 return 0;
3349 next_band(graph);
3351 for (i = 0; i < graph->n; ++i) {
3352 struct isl_sched_node *node = &graph->node[i];
3354 isl_map_free(node->sched_map);
3355 node->sched_map = NULL;
3356 node->sched = isl_mat_add_zero_rows(node->sched, 1);
3357 if (!node->sched)
3358 goto error;
3359 isl_int_fdiv_r(node->sched->row[row + 1][0],
3360 node->sched->row[row][0], gcd);
3361 isl_int_fdiv_q(node->sched->row[row][0],
3362 node->sched->row[row][0], gcd);
3363 isl_int_mul(node->sched->row[row][0],
3364 node->sched->row[row][0], gcd);
3365 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
3366 if (!node->sched)
3367 goto error;
3368 node->band[graph->n_total_row] = graph->n_band;
3371 graph->n_total_row++;
3373 isl_int_clear(gcd);
3374 return 0;
3375 error:
3376 isl_int_clear(gcd);
3377 return -1;
3380 static int compute_component_schedule(isl_ctx *ctx,
3381 struct isl_sched_graph *graph);
3383 /* Is the schedule row "sol" trivial on node "node"?
3384 * That is, is the solution zero on the dimensions orthogonal to
3385 * the previously found solutions?
3386 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3388 * Each coefficient is represented as the difference between
3389 * two non-negative values in "sol". "sol" has been computed
3390 * in terms of the original iterators (i.e., without use of cmap).
3391 * We construct the schedule row s and write it as a linear
3392 * combination of (linear combinations of) previously computed schedule rows.
3393 * s = Q c or c = U s.
3394 * If the final entries of c are all zero, then the solution is trivial.
3396 static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
3398 int i;
3399 int pos;
3400 int trivial;
3401 isl_ctx *ctx;
3402 isl_vec *node_sol;
3404 if (!sol)
3405 return -1;
3406 if (node->nvar == node->rank)
3407 return 0;
3409 ctx = isl_vec_get_ctx(sol);
3410 node_sol = isl_vec_alloc(ctx, node->nvar);
3411 if (!node_sol)
3412 return -1;
3414 pos = 1 + node->start + 1 + 2 * node->nparam;
3416 for (i = 0; i < node->nvar; ++i)
3417 isl_int_sub(node_sol->el[i],
3418 sol->el[pos + 2 * i + 1], sol->el[pos + 2 * i]);
3420 node_sol = isl_mat_vec_product(isl_mat_copy(node->cinv), node_sol);
3422 if (!node_sol)
3423 return -1;
3425 trivial = isl_seq_first_non_zero(node_sol->el + node->rank,
3426 node->nvar - node->rank) == -1;
3428 isl_vec_free(node_sol);
3430 return trivial;
3433 /* Is the schedule row "sol" trivial on any node where it should
3434 * not be trivial?
3435 * "sol" has been computed in terms of the original iterators
3436 * (i.e., without use of cmap).
3437 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3439 static int is_any_trivial(struct isl_sched_graph *graph,
3440 __isl_keep isl_vec *sol)
3442 int i;
3444 for (i = 0; i < graph->n; ++i) {
3445 struct isl_sched_node *node = &graph->node[i];
3446 int trivial;
3448 if (!needs_row(graph, node))
3449 continue;
3450 trivial = is_trivial(node, sol);
3451 if (trivial < 0 || trivial)
3452 return trivial;
3455 return 0;
3458 /* Construct a schedule row for each node such that as many dependences
3459 * as possible are carried and then continue with the next band.
3461 * If the computed schedule row turns out to be trivial on one or
3462 * more nodes where it should not be trivial, then we throw it away
3463 * and try again on each component separately.
3465 * If there is only one component, then we accept the schedule row anyway,
3466 * but we do not consider it as a complete row and therefore do not
3467 * increment graph->n_row. Note that the ranks of the nodes that
3468 * do get a non-trivial schedule part will get updated regardless and
3469 * graph->maxvar is computed based on these ranks. The test for
3470 * whether more schedule rows are required in compute_schedule_wcc
3471 * is therefore not affected.
3473 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
3475 int i;
3476 int n_edge;
3477 int trivial;
3478 isl_vec *sol;
3479 isl_basic_set *lp;
3481 n_edge = 0;
3482 for (i = 0; i < graph->n_edge; ++i)
3483 n_edge += graph->edge[i].map->n;
3485 if (setup_carry_lp(ctx, graph) < 0)
3486 return -1;
3488 lp = isl_basic_set_copy(graph->lp);
3489 sol = isl_tab_basic_set_non_neg_lexmin(lp);
3490 if (!sol)
3491 return -1;
3493 if (sol->size == 0) {
3494 isl_vec_free(sol);
3495 isl_die(ctx, isl_error_internal,
3496 "error in schedule construction", return -1);
3499 isl_int_divexact(sol->el[1], sol->el[1], sol->el[0]);
3500 if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
3501 isl_vec_free(sol);
3502 isl_die(ctx, isl_error_unknown,
3503 "unable to carry dependences", return -1);
3506 trivial = is_any_trivial(graph, sol);
3507 if (trivial < 0) {
3508 sol = isl_vec_free(sol);
3509 } else if (trivial && graph->scc > 1) {
3510 isl_vec_free(sol);
3511 return compute_component_schedule(ctx, graph);
3514 if (update_schedule(graph, sol, 0, 0) < 0)
3515 return -1;
3516 if (trivial)
3517 graph->n_row--;
3519 if (split_scaled(ctx, graph) < 0)
3520 return -1;
3522 return compute_next_band(ctx, graph);
3525 /* Are there any (non-empty) (conditional) validity edges in the graph?
3527 static int has_validity_edges(struct isl_sched_graph *graph)
3529 int i;
3531 for (i = 0; i < graph->n_edge; ++i) {
3532 int empty;
3534 empty = isl_map_plain_is_empty(graph->edge[i].map);
3535 if (empty < 0)
3536 return -1;
3537 if (empty)
3538 continue;
3539 if (graph->edge[i].validity ||
3540 graph->edge[i].conditional_validity)
3541 return 1;
3544 return 0;
3547 /* Should we apply a Feautrier step?
3548 * That is, did the user request the Feautrier algorithm and are
3549 * there any validity dependences (left)?
3551 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
3553 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
3554 return 0;
3556 return has_validity_edges(graph);
3559 /* Compute a schedule for a connected dependence graph using Feautrier's
3560 * multi-dimensional scheduling algorithm.
3561 * The original algorithm is described in [1].
3562 * The main idea is to minimize the number of scheduling dimensions, by
3563 * trying to satisfy as many dependences as possible per scheduling dimension.
3565 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3566 * Problem, Part II: Multi-Dimensional Time.
3567 * In Intl. Journal of Parallel Programming, 1992.
3569 static int compute_schedule_wcc_feautrier(isl_ctx *ctx,
3570 struct isl_sched_graph *graph)
3572 return carry_dependences(ctx, graph);
3575 /* Turn off the "local" bit on all (condition) edges.
3577 static void clear_local_edges(struct isl_sched_graph *graph)
3579 int i;
3581 for (i = 0; i < graph->n_edge; ++i)
3582 if (graph->edge[i].condition)
3583 graph->edge[i].local = 0;
3586 /* Does "graph" have both condition and conditional validity edges?
3588 static int need_condition_check(struct isl_sched_graph *graph)
3590 int i;
3591 int any_condition = 0;
3592 int any_conditional_validity = 0;
3594 for (i = 0; i < graph->n_edge; ++i) {
3595 if (graph->edge[i].condition)
3596 any_condition = 1;
3597 if (graph->edge[i].conditional_validity)
3598 any_conditional_validity = 1;
3601 return any_condition && any_conditional_validity;
3604 /* Does "graph" contain any coincidence edge?
3606 static int has_any_coincidence(struct isl_sched_graph *graph)
3608 int i;
3610 for (i = 0; i < graph->n_edge; ++i)
3611 if (graph->edge[i].coincidence)
3612 return 1;
3614 return 0;
3617 /* Extract the final schedule row as a map with the iteration domain
3618 * of "node" as domain.
3620 static __isl_give isl_map *final_row(struct isl_sched_node *node)
3622 isl_local_space *ls;
3623 isl_aff *aff;
3624 int row;
3626 row = isl_mat_rows(node->sched) - 1;
3627 ls = isl_local_space_from_space(isl_space_copy(node->space));
3628 aff = extract_schedule_row(ls, node, row);
3629 return isl_map_from_aff(aff);
3632 /* Is the conditional validity dependence in the edge with index "edge_index"
3633 * violated by the latest (i.e., final) row of the schedule?
3634 * That is, is i scheduled after j
3635 * for any conditional validity dependence i -> j?
3637 static int is_violated(struct isl_sched_graph *graph, int edge_index)
3639 isl_map *src_sched, *dst_sched, *map;
3640 struct isl_sched_edge *edge = &graph->edge[edge_index];
3641 int empty;
3643 src_sched = final_row(edge->src);
3644 dst_sched = final_row(edge->dst);
3645 map = isl_map_copy(edge->map);
3646 map = isl_map_apply_domain(map, src_sched);
3647 map = isl_map_apply_range(map, dst_sched);
3648 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);
3649 empty = isl_map_is_empty(map);
3650 isl_map_free(map);
3652 if (empty < 0)
3653 return -1;
3655 return !empty;
3658 /* Does the domain of "umap" intersect "uset"?
3660 static int domain_intersects(__isl_keep isl_union_map *umap,
3661 __isl_keep isl_union_set *uset)
3663 int empty;
3665 umap = isl_union_map_copy(umap);
3666 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(uset));
3667 empty = isl_union_map_is_empty(umap);
3668 isl_union_map_free(umap);
3670 return empty < 0 ? -1 : !empty;
3673 /* Does the range of "umap" intersect "uset"?
3675 static int range_intersects(__isl_keep isl_union_map *umap,
3676 __isl_keep isl_union_set *uset)
3678 int empty;
3680 umap = isl_union_map_copy(umap);
3681 umap = isl_union_map_intersect_range(umap, isl_union_set_copy(uset));
3682 empty = isl_union_map_is_empty(umap);
3683 isl_union_map_free(umap);
3685 return empty < 0 ? -1 : !empty;
3688 /* Are the condition dependences of "edge" local with respect to
3689 * the current schedule?
3691 * That is, are domain and range of the condition dependences mapped
3692 * to the same point?
3694 * In other words, is the condition false?
3696 static int is_condition_false(struct isl_sched_edge *edge)
3698 isl_union_map *umap;
3699 isl_map *map, *sched, *test;
3700 int local;
3702 umap = isl_union_map_copy(edge->tagged_condition);
3703 umap = isl_union_map_zip(umap);
3704 umap = isl_union_set_unwrap(isl_union_map_domain(umap));
3705 map = isl_map_from_union_map(umap);
3707 sched = node_extract_schedule(edge->src);
3708 map = isl_map_apply_domain(map, sched);
3709 sched = node_extract_schedule(edge->dst);
3710 map = isl_map_apply_range(map, sched);
3712 test = isl_map_identity(isl_map_get_space(map));
3713 local = isl_map_is_subset(map, test);
3714 isl_map_free(map);
3715 isl_map_free(test);
3717 return local;
3720 /* Does "graph" have any satisfied condition edges that
3721 * are adjacent to the conditional validity constraint with
3722 * domain "conditional_source" and range "conditional_sink"?
3724 * A satisfied condition is one that is not local.
3725 * If a condition was forced to be local already (i.e., marked as local)
3726 * then there is no need to check if it is in fact local.
3728 * Additionally, mark all adjacent condition edges found as local.
3730 static int has_adjacent_true_conditions(struct isl_sched_graph *graph,
3731 __isl_keep isl_union_set *conditional_source,
3732 __isl_keep isl_union_set *conditional_sink)
3734 int i;
3735 int any = 0;
3737 for (i = 0; i < graph->n_edge; ++i) {
3738 int adjacent, local;
3739 isl_union_map *condition;
3741 if (!graph->edge[i].condition)
3742 continue;
3743 if (graph->edge[i].local)
3744 continue;
3746 condition = graph->edge[i].tagged_condition;
3747 adjacent = domain_intersects(condition, conditional_sink);
3748 if (adjacent >= 0 && !adjacent)
3749 adjacent = range_intersects(condition,
3750 conditional_source);
3751 if (adjacent < 0)
3752 return -1;
3753 if (!adjacent)
3754 continue;
3756 graph->edge[i].local = 1;
3758 local = is_condition_false(&graph->edge[i]);
3759 if (local < 0)
3760 return -1;
3761 if (!local)
3762 any = 1;
3765 return any;
3768 /* Are there any violated conditional validity dependences with
3769 * adjacent condition dependences that are not local with respect
3770 * to the current schedule?
3771 * That is, is the conditional validity constraint violated?
3773 * Additionally, mark all those adjacent condition dependences as local.
3774 * We also mark those adjacent condition dependences that were not marked
3775 * as local before, but just happened to be local already. This ensures
3776 * that they remain local if the schedule is recomputed.
3778 * We first collect domain and range of all violated conditional validity
3779 * dependences and then check if there are any adjacent non-local
3780 * condition dependences.
3782 static int has_violated_conditional_constraint(isl_ctx *ctx,
3783 struct isl_sched_graph *graph)
3785 int i;
3786 int any = 0;
3787 isl_union_set *source, *sink;
3789 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3790 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3791 for (i = 0; i < graph->n_edge; ++i) {
3792 isl_union_set *uset;
3793 isl_union_map *umap;
3794 int violated;
3796 if (!graph->edge[i].conditional_validity)
3797 continue;
3799 violated = is_violated(graph, i);
3800 if (violated < 0)
3801 goto error;
3802 if (!violated)
3803 continue;
3805 any = 1;
3807 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
3808 uset = isl_union_map_domain(umap);
3809 source = isl_union_set_union(source, uset);
3810 source = isl_union_set_coalesce(source);
3812 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
3813 uset = isl_union_map_range(umap);
3814 sink = isl_union_set_union(sink, uset);
3815 sink = isl_union_set_coalesce(sink);
3818 if (any)
3819 any = has_adjacent_true_conditions(graph, source, sink);
3821 isl_union_set_free(source);
3822 isl_union_set_free(sink);
3823 return any;
3824 error:
3825 isl_union_set_free(source);
3826 isl_union_set_free(sink);
3827 return -1;
3830 /* Compute a schedule for a connected dependence graph.
3831 * We try to find a sequence of as many schedule rows as possible that result
3832 * in non-negative dependence distances (independent of the previous rows
3833 * in the sequence, i.e., such that the sequence is tilable), with as
3834 * many of the initial rows as possible satisfying the coincidence constraints.
3835 * If we can't find any more rows we either
3836 * - split between SCCs and start over (assuming we found an interesting
3837 * pair of SCCs between which to split)
3838 * - continue with the next band (assuming the current band has at least
3839 * one row)
3840 * - try to carry as many dependences as possible and continue with the next
3841 * band
3843 * If Feautrier's algorithm is selected, we first recursively try to satisfy
3844 * as many validity dependences as possible. When all validity dependences
3845 * are satisfied we extend the schedule to a full-dimensional schedule.
3847 * If we manage to complete the schedule, we finish off by topologically
3848 * sorting the statements based on the remaining dependences.
3850 * If ctx->opt->schedule_outer_coincidence is set, then we force the
3851 * outermost dimension to satisfy the coincidence constraints. If this
3852 * turns out to be impossible, we fall back on the general scheme above
3853 * and try to carry as many dependences as possible.
3855 * If "graph" contains both condition and conditional validity dependences,
3856 * then we need to check that that the conditional schedule constraint
3857 * is satisfied, i.e., there are no violated conditional validity dependences
3858 * that are adjacent to any non-local condition dependences.
3859 * If there are, then we mark all those adjacent condition dependences
3860 * as local and recompute the current band. Those dependences that
3861 * are marked local will then be forced to be local.
3862 * The initial computation is performed with no dependences marked as local.
3863 * If we are lucky, then there will be no violated conditional validity
3864 * dependences adjacent to any non-local condition dependences.
3865 * Otherwise, we mark some additional condition dependences as local and
3866 * recompute. We continue this process until there are no violations left or
3867 * until we are no longer able to compute a schedule.
3868 * Since there are only a finite number of dependences,
3869 * there will only be a finite number of iterations.
3871 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
3873 int has_coincidence;
3874 int use_coincidence;
3875 int force_coincidence = 0;
3876 int check_conditional;
3878 if (detect_sccs(ctx, graph) < 0)
3879 return -1;
3880 if (sort_sccs(graph) < 0)
3881 return -1;
3883 if (compute_maxvar(graph) < 0)
3884 return -1;
3886 if (need_feautrier_step(ctx, graph))
3887 return compute_schedule_wcc_feautrier(ctx, graph);
3889 clear_local_edges(graph);
3890 check_conditional = need_condition_check(graph);
3891 has_coincidence = has_any_coincidence(graph);
3893 if (ctx->opt->schedule_outer_coincidence)
3894 force_coincidence = 1;
3896 use_coincidence = has_coincidence;
3897 while (graph->n_row < graph->maxvar) {
3898 isl_vec *sol;
3899 int violated;
3900 int coincident;
3902 graph->src_scc = -1;
3903 graph->dst_scc = -1;
3905 if (setup_lp(ctx, graph, use_coincidence) < 0)
3906 return -1;
3907 sol = solve_lp(graph);
3908 if (!sol)
3909 return -1;
3910 if (sol->size == 0) {
3911 int empty = graph->n_total_row == graph->band_start;
3913 isl_vec_free(sol);
3914 if (use_coincidence && (!force_coincidence || !empty)) {
3915 use_coincidence = 0;
3916 continue;
3918 if (!ctx->opt->schedule_maximize_band_depth && !empty)
3919 return compute_next_band(ctx, graph);
3920 if (graph->src_scc >= 0)
3921 return compute_split_schedule(ctx, graph);
3922 if (!empty)
3923 return compute_next_band(ctx, graph);
3924 return carry_dependences(ctx, graph);
3926 coincident = !has_coincidence || use_coincidence;
3927 if (update_schedule(graph, sol, 1, coincident) < 0)
3928 return -1;
3930 if (!check_conditional)
3931 continue;
3932 violated = has_violated_conditional_constraint(ctx, graph);
3933 if (violated < 0)
3934 return -1;
3935 if (!violated)
3936 continue;
3937 if (reset_band(graph) < 0)
3938 return -1;
3939 use_coincidence = has_coincidence;
3942 if (graph->n_total_row > graph->band_start)
3943 next_band(graph);
3944 return sort_statements(ctx, graph);
3947 /* Add a row to the schedules that separates the SCCs and move
3948 * to the next band.
3950 static int split_on_scc(isl_ctx *ctx, struct isl_sched_graph *graph)
3952 int i;
3954 if (graph->n_total_row >= graph->max_row)
3955 isl_die(ctx, isl_error_internal,
3956 "too many schedule rows", return -1);
3958 for (i = 0; i < graph->n; ++i) {
3959 struct isl_sched_node *node = &graph->node[i];
3960 int row = isl_mat_rows(node->sched);
3962 isl_map_free(node->sched_map);
3963 node->sched_map = NULL;
3964 node->sched = isl_mat_add_zero_rows(node->sched, 1);
3965 node->sched = isl_mat_set_element_si(node->sched, row, 0,
3966 node->scc);
3967 if (!node->sched)
3968 return -1;
3969 node->band[graph->n_total_row] = graph->n_band;
3972 graph->n_total_row++;
3973 next_band(graph);
3975 return 0;
3978 /* Compute a schedule for each component (identified by node->scc)
3979 * of the dependence graph separately and then combine the results.
3980 * Depending on the setting of schedule_fuse, a component may be
3981 * either weakly or strongly connected.
3983 * The band_id is adjusted such that each component has a separate id.
3984 * Note that the band_id may have already been set to a value different
3985 * from zero by compute_split_schedule.
3987 static int compute_component_schedule(isl_ctx *ctx,
3988 struct isl_sched_graph *graph)
3990 int wcc, i;
3991 int n, n_edge;
3992 int n_total_row, orig_total_row;
3993 int n_band, orig_band;
3995 if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN ||
3996 ctx->opt->schedule_separate_components)
3997 if (split_on_scc(ctx, graph) < 0)
3998 return -1;
4000 n_total_row = 0;
4001 orig_total_row = graph->n_total_row;
4002 n_band = 0;
4003 orig_band = graph->n_band;
4004 for (i = 0; i < graph->n; ++i)
4005 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
4006 for (wcc = 0; wcc < graph->scc; ++wcc) {
4007 n = 0;
4008 for (i = 0; i < graph->n; ++i)
4009 if (graph->node[i].scc == wcc)
4010 n++;
4011 n_edge = 0;
4012 for (i = 0; i < graph->n_edge; ++i)
4013 if (graph->edge[i].src->scc == wcc &&
4014 graph->edge[i].dst->scc == wcc)
4015 n_edge++;
4017 if (compute_sub_schedule(ctx, graph, n, n_edge,
4018 &node_scc_exactly,
4019 &edge_scc_exactly, wcc, 1) < 0)
4020 return -1;
4021 if (graph->n_total_row > n_total_row)
4022 n_total_row = graph->n_total_row;
4023 graph->n_total_row = orig_total_row;
4024 if (graph->n_band > n_band)
4025 n_band = graph->n_band;
4026 graph->n_band = orig_band;
4029 graph->n_total_row = n_total_row;
4030 graph->n_band = n_band;
4032 return pad_schedule(graph);
4035 /* Compute a schedule for the given dependence graph.
4036 * We first check if the graph is connected (through validity and conditional
4037 * validity dependences) and, if not, compute a schedule
4038 * for each component separately.
4039 * If schedule_fuse is set to minimal fusion, then we check for strongly
4040 * connected components instead and compute a separate schedule for
4041 * each such strongly connected component.
4043 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
4045 if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) {
4046 if (detect_sccs(ctx, graph) < 0)
4047 return -1;
4048 } else {
4049 if (detect_wccs(ctx, graph) < 0)
4050 return -1;
4053 if (graph->scc > 1)
4054 return compute_component_schedule(ctx, graph);
4056 return compute_schedule_wcc(ctx, graph);
4059 /* Compute a schedule on sc->domain that respects the given schedule
4060 * constraints.
4062 * In particular, the schedule respects all the validity dependences.
4063 * If the default isl scheduling algorithm is used, it tries to minimize
4064 * the dependence distances over the proximity dependences.
4065 * If Feautrier's scheduling algorithm is used, the proximity dependence
4066 * distances are only minimized during the extension to a full-dimensional
4067 * schedule.
4069 * If there are any condition and conditional validity dependences,
4070 * then the conditional validity dependences may be violated inside
4071 * a tilable band, provided they have no adjacent non-local
4072 * condition dependences.
4074 __isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
4075 __isl_take isl_schedule_constraints *sc)
4077 isl_ctx *ctx = isl_schedule_constraints_get_ctx(sc);
4078 struct isl_sched_graph graph = { 0 };
4079 isl_schedule *sched;
4080 struct isl_extract_edge_data data;
4081 enum isl_edge_type i;
4083 sc = isl_schedule_constraints_align_params(sc);
4084 if (!sc)
4085 return NULL;
4087 graph.n = isl_union_set_n_set(sc->domain);
4088 if (graph.n == 0)
4089 goto empty;
4090 if (graph_alloc(ctx, &graph, graph.n,
4091 isl_schedule_constraints_n_map(sc)) < 0)
4092 goto error;
4093 if (compute_max_row(&graph, sc) < 0)
4094 goto error;
4095 graph.root = 1;
4096 graph.n = 0;
4097 if (isl_union_set_foreach_set(sc->domain, &extract_node, &graph) < 0)
4098 goto error;
4099 if (graph_init_table(ctx, &graph) < 0)
4100 goto error;
4101 for (i = isl_edge_first; i <= isl_edge_last; ++i)
4102 graph.max_edge[i] = isl_union_map_n_map(sc->constraint[i]);
4103 if (graph_init_edge_tables(ctx, &graph) < 0)
4104 goto error;
4105 graph.n_edge = 0;
4106 data.graph = &graph;
4107 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
4108 data.type = i;
4109 if (isl_union_map_foreach_map(sc->constraint[i],
4110 &extract_edge, &data) < 0)
4111 goto error;
4114 if (compute_schedule(ctx, &graph) < 0)
4115 goto error;
4117 empty:
4118 sched = extract_schedule(&graph, isl_union_set_get_space(sc->domain));
4120 graph_free(ctx, &graph);
4121 isl_schedule_constraints_free(sc);
4123 return sched;
4124 error:
4125 graph_free(ctx, &graph);
4126 isl_schedule_constraints_free(sc);
4127 return NULL;
4130 /* Compute a schedule for the given union of domains that respects
4131 * all the validity dependences and minimizes
4132 * the dependence distances over the proximity dependences.
4134 * This function is kept for backward compatibility.
4136 __isl_give isl_schedule *isl_union_set_compute_schedule(
4137 __isl_take isl_union_set *domain,
4138 __isl_take isl_union_map *validity,
4139 __isl_take isl_union_map *proximity)
4141 isl_schedule_constraints *sc;
4143 sc = isl_schedule_constraints_on_domain(domain);
4144 sc = isl_schedule_constraints_set_validity(sc, validity);
4145 sc = isl_schedule_constraints_set_proximity(sc, proximity);
4147 return isl_schedule_constraints_compute_schedule(sc);