Bug Summary

File:tools/polly/lib/External/isl/isl_scheduler.c
Warning:line 2698, column 2
Value stored to 'nrow' is never read

Annotated Source Code

1/*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015-2016 Sven Verdoolaege
5 * Copyright 2016 INRIA Paris
6 *
7 * Use of this software is governed by the MIT license
8 *
9 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
14 * CS 42112, 75589 Paris Cedex 12, France
15 */
16
17#include <isl_ctx_private.h>
18#include <isl_map_private.h>
19#include <isl_space_private.h>
20#include <isl_aff_private.h>
21#include <isl/hash.h>
22#include <isl/constraint.h>
23#include <isl/schedule.h>
24#include <isl_schedule_constraints.h>
25#include <isl/schedule_node.h>
26#include <isl_mat_private.h>
27#include <isl_vec_private.h>
28#include <isl/set.h>
29#include <isl/union_set.h>
30#include <isl_seq.h>
31#include <isl_tab.h>
32#include <isl_dim_map.h>
33#include <isl/map_to_basic_set.h>
34#include <isl_sort.h>
35#include <isl_options_private.h>
36#include <isl_tarjan.h>
37#include <isl_morph.h>
38#include <isl/ilp.h>
39#include <isl_val_private.h>
40
41/*
42 * The scheduling algorithm implemented in this file was inspired by
43 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
44 * Parallelization and Locality Optimization in the Polyhedral Model".
45 */
46
47
48/* Internal information about a node that is used during the construction
49 * of a schedule.
50 * space represents the space in which the domain lives
51 * sched is a matrix representation of the schedule being constructed
52 * for this node; if compressed is set, then this schedule is
53 * defined over the compressed domain space
54 * sched_map is an isl_map representation of the same (partial) schedule
55 * sched_map may be NULL; if compressed is set, then this map
56 * is defined over the uncompressed domain space
57 * rank is the number of linearly independent rows in the linear part
58 * of sched
59 * the columns of cmap represent a change of basis for the schedule
60 * coefficients; the first rank columns span the linear part of
61 * the schedule rows
62 * cinv is the inverse of cmap.
63 * ctrans is the transpose of cmap.
64 * start is the first variable in the LP problem in the sequences that
65 * represents the schedule coefficients of this node
66 * nvar is the dimension of the domain
67 * nparam is the number of parameters or 0 if we are not constructing
68 * a parametric schedule
69 *
70 * If compressed is set, then hull represents the constraints
71 * that were used to derive the compression, while compress and
72 * decompress map the original space to the compressed space and
73 * vice versa.
74 *
75 * scc is the index of SCC (or WCC) this node belongs to
76 *
77 * "cluster" is only used inside extract_clusters and identifies
78 * the cluster of SCCs that the node belongs to.
79 *
80 * coincident contains a boolean for each of the rows of the schedule,
81 * indicating whether the corresponding scheduling dimension satisfies
82 * the coincidence constraints in the sense that the corresponding
83 * dependence distances are zero.
84 *
85 * If the schedule_treat_coalescing option is set, then
86 * "sizes" contains the sizes of the (compressed) instance set
87 * in each direction. If there is no fixed size in a given direction,
88 * then the corresponding size value is set to infinity.
89 * If the schedule_treat_coalescing option or the schedule_max_coefficient
90 * option is set, then "max" contains the maximal values for
91 * schedule coefficients of the (compressed) variables. If no bound
92 * needs to be imposed on a particular variable, then the corresponding
93 * value is negative.
94 */
95struct isl_sched_node {
96 isl_space *space;
97 int compressed;
98 isl_setisl_map *hull;
99 isl_multi_aff *compress;
100 isl_multi_aff *decompress;
101 isl_mat *sched;
102 isl_map *sched_map;
103 int rank;
104 isl_mat *cmap;
105 isl_mat *cinv;
106 isl_mat *ctrans;
107 int start;
108 int nvar;
109 int nparam;
110
111 int scc;
112 int cluster;
113
114 int *coincident;
115
116 isl_multi_val *sizes;
117 isl_vec *max;
118};
119
120static int node_has_space(const void *entry, const void *val)
121{
122 struct isl_sched_node *node = (struct isl_sched_node *)entry;
123 isl_space *dim = (isl_space *)val;
124
125 return isl_space_is_equal(node->space, dim);
126}
127
128static int node_scc_exactly(struct isl_sched_node *node, int scc)
129{
130 return node->scc == scc;
131}
132
133static int node_scc_at_most(struct isl_sched_node *node, int scc)
134{
135 return node->scc <= scc;
136}
137
138static int node_scc_at_least(struct isl_sched_node *node, int scc)
139{
140 return node->scc >= scc;
141}
142
143/* An edge in the dependence graph. An edge may be used to
144 * ensure validity of the generated schedule, to minimize the dependence
145 * distance or both
146 *
147 * map is the dependence relation, with i -> j in the map if j depends on i
148 * tagged_condition and tagged_validity contain the union of all tagged
149 * condition or conditional validity dependence relations that
150 * specialize the dependence relation "map"; that is,
151 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
152 * or "tagged_validity", then i -> j is an element of "map".
153 * If these fields are NULL, then they represent the empty relation.
154 * src is the source node
155 * dst is the sink node
156 *
157 * types is a bit vector containing the types of this edge.
158 * validity is set if the edge is used to ensure correctness
159 * coincidence is used to enforce zero dependence distances
160 * proximity is set if the edge is used to minimize dependence distances
161 * condition is set if the edge represents a condition
162 * for a conditional validity schedule constraint
163 * local can only be set for condition edges and indicates that
164 * the dependence distance over the edge should be zero
165 * conditional_validity is set if the edge is used to conditionally
166 * ensure correctness
167 *
168 * For validity edges, start and end mark the sequence of inequality
169 * constraints in the LP problem that encode the validity constraint
170 * corresponding to this edge.
171 *
172 * During clustering, an edge may be marked "no_merge" if it should
173 * not be used to merge clusters.
174 * The weight is also only used during clustering and it is
175 * an indication of how many schedule dimensions on either side
176 * of the schedule constraints can be aligned.
177 * If the weight is negative, then this means that this edge was postponed
178 * by has_bounded_distances or any_no_merge. The original weight can
179 * be retrieved by adding 1 + graph->max_weight, with "graph"
180 * the graph containing this edge.
181 */
182struct isl_sched_edge {
183 isl_map *map;
184 isl_union_map *tagged_condition;
185 isl_union_map *tagged_validity;
186
187 struct isl_sched_node *src;
188 struct isl_sched_node *dst;
189
190 unsigned types;
191
192 int start;
193 int end;
194
195 int no_merge;
196 int weight;
197};
198
199/* Is "edge" marked as being of type "type"?
200 */
201static int is_type(struct isl_sched_edge *edge, enum isl_edge_type type)
202{
203 return ISL_FL_ISSET(edge->types, 1 << type)(!!((edge->types) & (1 << type)));
204}
205
206/* Mark "edge" as being of type "type".
207 */
208static void set_type(struct isl_sched_edge *edge, enum isl_edge_type type)
209{
210 ISL_FL_SET(edge->types, 1 << type)((edge->types) |= (1 << type));
211}
212
213/* No longer mark "edge" as being of type "type"?
214 */
215static void clear_type(struct isl_sched_edge *edge, enum isl_edge_type type)
216{
217 ISL_FL_CLR(edge->types, 1 << type)((edge->types) &= ~(1 << type));
218}
219
220/* Is "edge" marked as a validity edge?
221 */
222static int is_validity(struct isl_sched_edge *edge)
223{
224 return is_type(edge, isl_edge_validity);
225}
226
227/* Mark "edge" as a validity edge.
228 */
229static void set_validity(struct isl_sched_edge *edge)
230{
231 set_type(edge, isl_edge_validity);
232}
233
234/* Is "edge" marked as a proximity edge?
235 */
236static int is_proximity(struct isl_sched_edge *edge)
237{
238 return is_type(edge, isl_edge_proximity);
239}
240
241/* Is "edge" marked as a local edge?
242 */
243static int is_local(struct isl_sched_edge *edge)
244{
245 return is_type(edge, isl_edge_local);
246}
247
248/* Mark "edge" as a local edge.
249 */
250static void set_local(struct isl_sched_edge *edge)
251{
252 set_type(edge, isl_edge_local);
253}
254
255/* No longer mark "edge" as a local edge.
256 */
257static void clear_local(struct isl_sched_edge *edge)
258{
259 clear_type(edge, isl_edge_local);
260}
261
262/* Is "edge" marked as a coincidence edge?
263 */
264static int is_coincidence(struct isl_sched_edge *edge)
265{
266 return is_type(edge, isl_edge_coincidence);
267}
268
269/* Is "edge" marked as a condition edge?
270 */
271static int is_condition(struct isl_sched_edge *edge)
272{
273 return is_type(edge, isl_edge_condition);
274}
275
276/* Is "edge" marked as a conditional validity edge?
277 */
278static int is_conditional_validity(struct isl_sched_edge *edge)
279{
280 return is_type(edge, isl_edge_conditional_validity);
281}
282
283/* Internal information about the dependence graph used during
284 * the construction of the schedule.
285 *
286 * intra_hmap is a cache, mapping dependence relations to their dual,
287 * for dependences from a node to itself
288 * inter_hmap is a cache, mapping dependence relations to their dual,
289 * for dependences between distinct nodes
290 * if compression is involved then the key for these maps
291 * is the original, uncompressed dependence relation, while
292 * the value is the dual of the compressed dependence relation.
293 *
294 * n is the number of nodes
295 * node is the list of nodes
296 * maxvar is the maximal number of variables over all nodes
297 * max_row is the allocated number of rows in the schedule
298 * n_row is the current (maximal) number of linearly independent
299 * rows in the node schedules
300 * n_total_row is the current number of rows in the node schedules
301 * band_start is the starting row in the node schedules of the current band
302 * root is set if this graph is the original dependence graph,
303 * without any splitting
304 *
305 * sorted contains a list of node indices sorted according to the
306 * SCC to which a node belongs
307 *
308 * n_edge is the number of edges
309 * edge is the list of edges
310 * max_edge contains the maximal number of edges of each type;
311 * in particular, it contains the number of edges in the inital graph.
312 * edge_table contains pointers into the edge array, hashed on the source
313 * and sink spaces; there is one such table for each type;
314 * a given edge may be referenced from more than one table
315 * if the corresponding relation appears in more than one of the
316 * sets of dependences; however, for each type there is only
317 * a single edge between a given pair of source and sink space
318 * in the entire graph
319 *
320 * node_table contains pointers into the node array, hashed on the space
321 *
322 * region contains a list of variable sequences that should be non-trivial
323 *
324 * lp contains the (I)LP problem used to obtain new schedule rows
325 *
326 * src_scc and dst_scc are the source and sink SCCs of an edge with
327 * conflicting constraints
328 *
329 * scc represents the number of components
330 * weak is set if the components are weakly connected
331 *
332 * max_weight is used during clustering and represents the maximal
333 * weight of the relevant proximity edges.
334 */
335struct isl_sched_graph {
336 isl_map_to_basic_set *intra_hmap;
337 isl_map_to_basic_set *inter_hmap;
338
339 struct isl_sched_node *node;
340 int n;
341 int maxvar;
342 int max_row;
343 int n_row;
344
345 int *sorted;
346
347 int n_total_row;
348 int band_start;
349
350 int root;
351
352 struct isl_sched_edge *edge;
353 int n_edge;
354 int max_edge[isl_edge_last + 1];
355 struct isl_hash_table *edge_table[isl_edge_last + 1];
356
357 struct isl_hash_table *node_table;
358 struct isl_region *region;
359
360 isl_basic_setisl_basic_map *lp;
361
362 int src_scc;
363 int dst_scc;
364
365 int scc;
366 int weak;
367
368 int max_weight;
369};
370
371/* Initialize node_table based on the list of nodes.
372 */
373static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
374{
375 int i;
376
377 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
378 if (!graph->node_table)
379 return -1;
380
381 for (i = 0; i < graph->n; ++i) {
382 struct isl_hash_table_entry *entry;
383 uint32_t hash;
384
385 hash = isl_space_get_hash(graph->node[i].space);
386 entry = isl_hash_table_find(ctx, graph->node_table, hash,
387 &node_has_space,
388 graph->node[i].space, 1);
389 if (!entry)
390 return -1;
391 entry->data = &graph->node[i];
392 }
393
394 return 0;
395}
396
397/* Return a pointer to the node that lives within the given space,
398 * or NULL if there is no such node.
399 */
400static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
401 struct isl_sched_graph *graph, __isl_keep isl_space *dim)
402{
403 struct isl_hash_table_entry *entry;
404 uint32_t hash;
405
406 hash = isl_space_get_hash(dim);
407 entry = isl_hash_table_find(ctx, graph->node_table, hash,
408 &node_has_space, dim, 0);
409
410 return entry ? entry->data : NULL((void*)0);
411}
412
413static int edge_has_src_and_dst(const void *entry, const void *val)
414{
415 const struct isl_sched_edge *edge = entry;
416 const struct isl_sched_edge *temp = val;
417
418 return edge->src == temp->src && edge->dst == temp->dst;
419}
420
421/* Add the given edge to graph->edge_table[type].
422 */
423static isl_stat graph_edge_table_add(isl_ctx *ctx,
424 struct isl_sched_graph *graph, enum isl_edge_type type,
425 struct isl_sched_edge *edge)
426{
427 struct isl_hash_table_entry *entry;
428 uint32_t hash;
429
430 hash = isl_hash_init()(2166136261u);
431 hash = isl_hash_builtin(hash, edge->src)isl_hash_mem(hash, &edge->src, sizeof(edge->src));
432 hash = isl_hash_builtin(hash, edge->dst)isl_hash_mem(hash, &edge->dst, sizeof(edge->dst));
433 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
434 &edge_has_src_and_dst, edge, 1);
435 if (!entry)
436 return isl_stat_error;
437 entry->data = edge;
438
439 return isl_stat_ok;
440}
441
442/* Allocate the edge_tables based on the maximal number of edges of
443 * each type.
444 */
445static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
446{
447 int i;
448
449 for (i = 0; i <= isl_edge_last; ++i) {
450 graph->edge_table[i] = isl_hash_table_alloc(ctx,
451 graph->max_edge[i]);
452 if (!graph->edge_table[i])
453 return -1;
454 }
455
456 return 0;
457}
458
459/* If graph->edge_table[type] contains an edge from the given source
460 * to the given destination, then return the hash table entry of this edge.
461 * Otherwise, return NULL.
462 */
463static struct isl_hash_table_entry *graph_find_edge_entry(
464 struct isl_sched_graph *graph,
465 enum isl_edge_type type,
466 struct isl_sched_node *src, struct isl_sched_node *dst)
467{
468 isl_ctx *ctx = isl_space_get_ctx(src->space);
469 uint32_t hash;
470 struct isl_sched_edge temp = { .src = src, .dst = dst };
471
472 hash = isl_hash_init()(2166136261u);
473 hash = isl_hash_builtin(hash, temp.src)isl_hash_mem(hash, &temp.src, sizeof(temp.src));
474 hash = isl_hash_builtin(hash, temp.dst)isl_hash_mem(hash, &temp.dst, sizeof(temp.dst));
475 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
476 &edge_has_src_and_dst, &temp, 0);
477}
478
479
480/* If graph->edge_table[type] contains an edge from the given source
481 * to the given destination, then return this edge.
482 * Otherwise, return NULL.
483 */
484static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
485 enum isl_edge_type type,
486 struct isl_sched_node *src, struct isl_sched_node *dst)
487{
488 struct isl_hash_table_entry *entry;
489
490 entry = graph_find_edge_entry(graph, type, src, dst);
491 if (!entry)
492 return NULL((void*)0);
493
494 return entry->data;
495}
496
497/* Check whether the dependence graph has an edge of the given type
498 * between the given two nodes.
499 */
500static isl_bool graph_has_edge(struct isl_sched_graph *graph,
501 enum isl_edge_type type,
502 struct isl_sched_node *src, struct isl_sched_node *dst)
503{
504 struct isl_sched_edge *edge;
505 isl_bool empty;
506
507 edge = graph_find_edge(graph, type, src, dst);
508 if (!edge)
509 return 0;
510
511 empty = isl_map_plain_is_empty(edge->map);
512 if (empty < 0)
513 return isl_bool_error;
514
515 return !empty;
516}
517
518/* Look for any edge with the same src, dst and map fields as "model".
519 *
520 * Return the matching edge if one can be found.
521 * Return "model" if no matching edge is found.
522 * Return NULL on error.
523 */
524static struct isl_sched_edge *graph_find_matching_edge(
525 struct isl_sched_graph *graph, struct isl_sched_edge *model)
526{
527 enum isl_edge_type i;
528 struct isl_sched_edge *edge;
529
530 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
531 int is_equal;
532
533 edge = graph_find_edge(graph, i, model->src, model->dst);
534 if (!edge)
535 continue;
536 is_equal = isl_map_plain_is_equal(model->map, edge->map);
537 if (is_equal < 0)
538 return NULL((void*)0);
539 if (is_equal)
540 return edge;
541 }
542
543 return model;
544}
545
546/* Remove the given edge from all the edge_tables that refer to it.
547 */
548static void graph_remove_edge(struct isl_sched_graph *graph,
549 struct isl_sched_edge *edge)
550{
551 isl_ctx *ctx = isl_map_get_ctx(edge->map);
552 enum isl_edge_type i;
553
554 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
555 struct isl_hash_table_entry *entry;
556
557 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
558 if (!entry)
559 continue;
560 if (entry->data != edge)
561 continue;
562 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
563 }
564}
565
566/* Check whether the dependence graph has any edge
567 * between the given two nodes.
568 */
569static isl_bool graph_has_any_edge(struct isl_sched_graph *graph,
570 struct isl_sched_node *src, struct isl_sched_node *dst)
571{
572 enum isl_edge_type i;
573 isl_bool r;
574
575 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
576 r = graph_has_edge(graph, i, src, dst);
577 if (r < 0 || r)
578 return r;
579 }
580
581 return r;
582}
583
584/* Check whether the dependence graph has a validity edge
585 * between the given two nodes.
586 *
587 * Conditional validity edges are essentially validity edges that
588 * can be ignored if the corresponding condition edges are iteration private.
589 * Here, we are only checking for the presence of validity
590 * edges, so we need to consider the conditional validity edges too.
591 * In particular, this function is used during the detection
592 * of strongly connected components and we cannot ignore
593 * conditional validity edges during this detection.
594 */
595static isl_bool graph_has_validity_edge(struct isl_sched_graph *graph,
596 struct isl_sched_node *src, struct isl_sched_node *dst)
597{
598 isl_bool r;
599
600 r = graph_has_edge(graph, isl_edge_validity, src, dst);
601 if (r < 0 || r)
602 return r;
603
604 return graph_has_edge(graph, isl_edge_conditional_validity, src, dst);
605}
606
607static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
608 int n_node, int n_edge)
609{
610 int i;
611
612 graph->n = n_node;
613 graph->n_edge = n_edge;
614 graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n)((struct isl_sched_node *)isl_calloc_or_die(ctx, graph->n,
sizeof(struct isl_sched_node)))
;
615 graph->sorted = isl_calloc_array(ctx, int, graph->n)((int *)isl_calloc_or_die(ctx, graph->n, sizeof(int)));
616 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n)((struct isl_region *)isl_malloc_or_die(ctx, (graph->n)*sizeof
(struct isl_region)))
;
617 graph->edge = isl_calloc_array(ctx,((struct isl_sched_edge *)isl_calloc_or_die(ctx, graph->n_edge
, sizeof(struct isl_sched_edge)))
618 struct isl_sched_edge, graph->n_edge)((struct isl_sched_edge *)isl_calloc_or_die(ctx, graph->n_edge
, sizeof(struct isl_sched_edge)))
;
619
620 graph->intra_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
621 graph->inter_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
622
623 if (!graph->node || !graph->region || (graph->n_edge && !graph->edge) ||
624 !graph->sorted)
625 return -1;
626
627 for(i = 0; i < graph->n; ++i)
628 graph->sorted[i] = i;
629
630 return 0;
631}
632
633static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
634{
635 int i;
636
637 isl_map_to_basic_set_free(graph->intra_hmap);
638 isl_map_to_basic_set_free(graph->inter_hmap);
639
640 if (graph->node)
641 for (i = 0; i < graph->n; ++i) {
642 isl_space_free(graph->node[i].space);
643 isl_set_free(graph->node[i].hull);
644 isl_multi_aff_free(graph->node[i].compress);
645 isl_multi_aff_free(graph->node[i].decompress);
646 isl_mat_free(graph->node[i].sched);
647 isl_map_free(graph->node[i].sched_map);
648 isl_mat_free(graph->node[i].cmap);
649 isl_mat_free(graph->node[i].cinv);
650 isl_mat_free(graph->node[i].ctrans);
651 if (graph->root)
652 free(graph->node[i].coincident);
653 isl_multi_val_free(graph->node[i].sizes);
654 isl_vec_free(graph->node[i].max);
655 }
656 free(graph->node);
657 free(graph->sorted);
658 if (graph->edge)
659 for (i = 0; i < graph->n_edge; ++i) {
660 isl_map_free(graph->edge[i].map);
661 isl_union_map_free(graph->edge[i].tagged_condition);
662 isl_union_map_free(graph->edge[i].tagged_validity);
663 }
664 free(graph->edge);
665 free(graph->region);
666 for (i = 0; i <= isl_edge_last; ++i)
667 isl_hash_table_free(ctx, graph->edge_table[i]);
668 isl_hash_table_free(ctx, graph->node_table);
669 isl_basic_set_free(graph->lp);
670}
671
672/* For each "set" on which this function is called, increment
673 * graph->n by one and update graph->maxvar.
674 */
675static isl_stat init_n_maxvar(__isl_take isl_setisl_map *set, void *user)
676{
677 struct isl_sched_graph *graph = user;
678 int nvar = isl_set_dim(set, isl_dim_set);
679
680 graph->n++;
681 if (nvar > graph->maxvar)
682 graph->maxvar = nvar;
683
684 isl_set_free(set);
685
686 return isl_stat_ok;
687}
688
689/* Compute the number of rows that should be allocated for the schedule.
690 * In particular, we need one row for each variable or one row
691 * for each basic map in the dependences.
692 * Note that it is practically impossible to exhaust both
693 * the number of dependences and the number of variables.
694 */
695static isl_stat compute_max_row(struct isl_sched_graph *graph,
696 __isl_keep isl_schedule_constraints *sc)
697{
698 int n_edge;
699 isl_stat r;
700 isl_union_set *domain;
701
702 graph->n = 0;
703 graph->maxvar = 0;
704 domain = isl_schedule_constraints_get_domain(sc);
705 r = isl_union_set_foreach_set(domain, &init_n_maxvar, graph);
706 isl_union_set_free(domain);
707 if (r < 0)
708 return isl_stat_error;
709 n_edge = isl_schedule_constraints_n_basic_map(sc);
710 if (n_edge < 0)
711 return isl_stat_error;
712 graph->max_row = n_edge + graph->maxvar;
713
714 return isl_stat_ok;
715}
716
717/* Does "bset" have any defining equalities for its set variables?
718 */
719static isl_bool has_any_defining_equality(__isl_keep isl_basic_setisl_basic_map *bset)
720{
721 int i, n;
722
723 if (!bset)
724 return isl_bool_error;
725
726 n = isl_basic_set_dim(bset, isl_dim_set);
727 for (i = 0; i < n; ++i) {
728 isl_bool has;
729
730 has = isl_basic_set_has_defining_equality(bset, isl_dim_set, i,
731 NULL((void*)0));
732 if (has < 0 || has)
733 return has;
734 }
735
736 return isl_bool_false;
737}
738
739/* Set the entries of node->max to the value of the schedule_max_coefficient
740 * option, if set.
741 */
742static isl_stat set_max_coefficient(isl_ctx *ctx, struct isl_sched_node *node)
743{
744 int max;
745
746 max = isl_options_get_schedule_max_coefficient(ctx);
747 if (max == -1)
748 return isl_stat_ok;
749
750 node->max = isl_vec_alloc(ctx, node->nvar);
751 node->max = isl_vec_set_si(node->max, max);
752 if (!node->max)
753 return isl_stat_error;
754
755 return isl_stat_ok;
756}
757
758/* Set the entries of node->max to the minimum of the schedule_max_coefficient
759 * option (if set) and half of the minimum of the sizes in the other
760 * dimensions. If the minimum of the sizes is one, half of the size
761 * is zero and this value is reset to one.
762 * If the global minimum is unbounded (i.e., if both
763 * the schedule_max_coefficient is not set and the sizes in the other
764 * dimensions are unbounded), then store a negative value.
765 * If the schedule coefficient is close to the size of the instance set
766 * in another dimension, then the schedule may represent a loop
767 * coalescing transformation (especially if the coefficient
768 * in that other dimension is one). Forcing the coefficient to be
769 * smaller than or equal to half the minimal size should avoid this
770 * situation.
771 */
772static isl_stat compute_max_coefficient(isl_ctx *ctx,
773 struct isl_sched_node *node)
774{
775 int max;
776 int i, j;
777 isl_vec *v;
778
779 max = isl_options_get_schedule_max_coefficient(ctx);
780 v = isl_vec_alloc(ctx, node->nvar);
781 if (!v)
782 return isl_stat_error;
783
784 for (i = 0; i < node->nvar; ++i) {
785 isl_int_set_si(v->el[i], max)isl_sioimath_set_si((v->el[i]), max);
786 isl_int_mul_si(v->el[i], v->el[i], 2)isl_sioimath_mul_si((v->el[i]), *(v->el[i]), 2);
787 }
788
789 for (i = 0; i < node->nvar; ++i) {
790 isl_val *size;
791
792 size = isl_multi_val_get_val(node->sizes, i);
793 if (!size)
794 goto error;
795 if (!isl_val_is_int(size)) {
796 isl_val_free(size);
797 continue;
798 }
799 for (j = 0; j < node->nvar; ++j) {
800 if (j == i)
801 continue;
802 if (isl_int_is_neg(v->el[j])(isl_sioimath_sgn(*(v->el[j])) < 0) ||
803 isl_int_gt(v->el[j], size->n)(isl_sioimath_cmp(*(v->el[j]), *(size->n)) > 0))
804 isl_int_set(v->el[j], size->n)isl_sioimath_set((v->el[j]), *(size->n));
805 }
806 isl_val_free(size);
807 }
808
809 for (i = 0; i < node->nvar; ++i) {
810 isl_int_fdiv_q_ui(v->el[i], v->el[i], 2)isl_sioimath_fdiv_q_ui((v->el[i]), *(v->el[i]), 2);
811 if (isl_int_is_zero(v->el[i])(isl_sioimath_sgn(*(v->el[i])) == 0))
812 isl_int_set_si(v->el[i], 1)isl_sioimath_set_si((v->el[i]), 1);
813 }
814
815 node->max = v;
816 return isl_stat_ok;
817error:
818 isl_vec_free(v);
819 return isl_stat_error;
820}
821
822/* Compute and return the size of "set" in dimension "dim".
823 * The size is taken to be the difference in values for that variable
824 * for fixed values of the other variables.
825 * In particular, the variable is first isolated from the other variables
826 * in the range of a map
827 *
828 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [i_dim]
829 *
830 * and then duplicated
831 *
832 * [i_0, ..., i_dim-1, i_dim+1, ...] -> [[i_dim] -> [i_dim']]
833 *
834 * The shared variables are then projected out and the maximal value
835 * of i_dim' - i_dim is computed.
836 */
837static __isl_give isl_val *compute_size(__isl_take isl_setisl_map *set, int dim)
838{
839 isl_map *map;
840 isl_local_space *ls;
841 isl_aff *obj;
842 isl_val *v;
843
844 map = isl_set_project_onto_map(set, isl_dim_set, dim, 1);
845 map = isl_map_project_out(map, isl_dim_in, dim, 1);
846 map = isl_map_range_product(map, isl_map_copy(map));
847 map = isl_set_unwrap(isl_map_range(map));
848 set = isl_map_deltas(map);
849 ls = isl_local_space_from_space(isl_set_get_space(set));
850 obj = isl_aff_var_on_domain(ls, isl_dim_set, 0);
851 v = isl_set_max_val(set, obj);
852 isl_aff_free(obj);
853 isl_set_free(set);
854
855 return v;
856}
857
858/* Compute the size of the instance set "set" of "node", after compression,
859 * as well as bounds on the corresponding coefficients, if needed.
860 *
861 * The sizes are needed when the schedule_treat_coalescing option is set.
862 * The bounds are needed when the schedule_treat_coalescing option or
863 * the schedule_max_coefficient option is set.
864 *
865 * If the schedule_treat_coalescing option is not set, then at most
866 * the bounds need to be set and this is done in set_max_coefficient.
867 * Otherwise, compress the domain if needed, compute the size
868 * in each direction and store the results in node->size.
869 * Finally, set the bounds on the coefficients based on the sizes
870 * and the schedule_max_coefficient option in compute_max_coefficient.
871 */
872static isl_stat compute_sizes_and_max(isl_ctx *ctx, struct isl_sched_node *node,
873 __isl_take isl_setisl_map *set)
874{
875 int j, n;
876 isl_multi_val *mv;
877
878 if (!isl_options_get_schedule_treat_coalescing(ctx)) {
879 isl_set_free(set);
880 return set_max_coefficient(ctx, node);
881 }
882
883 if (node->compressed)
884 set = isl_set_preimage_multi_aff(set,
885 isl_multi_aff_copy(node->decompress));
886 mv = isl_multi_val_zero(isl_set_get_space(set));
887 n = isl_set_dim(set, isl_dim_set);
888 for (j = 0; j < n; ++j) {
889 isl_val *v;
890
891 v = compute_size(isl_set_copy(set), j);
892 mv = isl_multi_val_set_val(mv, j, v);
893 }
894 node->sizes = mv;
895 isl_set_free(set);
896 if (!node->sizes)
897 return isl_stat_error;
898 return compute_max_coefficient(ctx, node);
899}
900
901/* Add a new node to the graph representing the given instance set.
902 * "nvar" is the (possibly compressed) number of variables and
903 * may be smaller than then number of set variables in "set"
904 * if "compressed" is set.
905 * If "compressed" is set, then "hull" represents the constraints
906 * that were used to derive the compression, while "compress" and
907 * "decompress" map the original space to the compressed space and
908 * vice versa.
909 * If "compressed" is not set, then "hull", "compress" and "decompress"
910 * should be NULL.
911 *
912 * Compute the size of the instance set and bounds on the coefficients,
913 * if needed.
914 */
915static isl_stat add_node(struct isl_sched_graph *graph,
916 __isl_take isl_setisl_map *set, int nvar, int compressed,
917 __isl_take isl_setisl_map *hull, __isl_take isl_multi_aff *compress,
918 __isl_take isl_multi_aff *decompress)
919{
920 int nparam;
921 isl_ctx *ctx;
922 isl_mat *sched;
923 isl_space *space;
924 int *coincident;
925 struct isl_sched_node *node;
926
927 if (!set)
928 return isl_stat_error;
929
930 ctx = isl_set_get_ctx(set);
931 nparam = isl_set_dim(set, isl_dim_param);
932 if (!ctx->opt->schedule_parametric)
933 nparam = 0;
934 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
935 node = &graph->node[graph->n];
936 graph->n++;
937 space = isl_set_get_space(set);
938 node->space = space;
939 node->nvar = nvar;
940 node->nparam = nparam;
941 node->sched = sched;
942 node->sched_map = NULL((void*)0);
943 coincident = isl_calloc_array(ctx, int, graph->max_row)((int *)isl_calloc_or_die(ctx, graph->max_row, sizeof(int)
))
;
944 node->coincident = coincident;
945 node->compressed = compressed;
946 node->hull = hull;
947 node->compress = compress;
948 node->decompress = decompress;
949 if (compute_sizes_and_max(ctx, node, set) < 0)
950 return isl_stat_error;
951
952 if (!space || !sched || (graph->max_row && !coincident))
953 return isl_stat_error;
954 if (compressed && (!hull || !compress || !decompress))
955 return isl_stat_error;
956
957 return isl_stat_ok;
958}
959
960/* Add a new node to the graph representing the given set.
961 *
962 * If any of the set variables is defined by an equality, then
963 * we perform variable compression such that we can perform
964 * the scheduling on the compressed domain.
965 */
966static isl_stat extract_node(__isl_take isl_setisl_map *set, void *user)
967{
968 int nvar;
969 isl_bool has_equality;
970 isl_basic_setisl_basic_map *hull;
971 isl_setisl_map *hull_set;
972 isl_morph *morph;
973 isl_multi_aff *compress, *decompress;
974 struct isl_sched_graph *graph = user;
975
976 hull = isl_set_affine_hull(isl_set_copy(set));
977 hull = isl_basic_set_remove_divs(hull);
978 nvar = isl_set_dim(set, isl_dim_set);
979 has_equality = has_any_defining_equality(hull);
980
981 if (has_equality < 0)
982 goto error;
983 if (!has_equality) {
984 isl_basic_set_free(hull);
985 return add_node(graph, set, nvar, 0, NULL((void*)0), NULL((void*)0), NULL((void*)0));
986 }
987
988 morph = isl_basic_set_variable_compression(hull, isl_dim_set);
989 nvar = isl_morph_ran_dim(morph, isl_dim_set);
990 compress = isl_morph_get_var_multi_aff(morph);
991 morph = isl_morph_inverse(morph);
992 decompress = isl_morph_get_var_multi_aff(morph);
993 isl_morph_free(morph);
994
995 hull_set = isl_set_from_basic_set(hull);
996 return add_node(graph, set, nvar, 1, hull_set, compress, decompress);
997error:
998 isl_basic_set_free(hull);
999 isl_set_free(set);
1000 return isl_stat_error;
1001}
1002
1003struct isl_extract_edge_data {
1004 enum isl_edge_type type;
1005 struct isl_sched_graph *graph;
1006};
1007
1008/* Merge edge2 into edge1, freeing the contents of edge2.
1009 * Return 0 on success and -1 on failure.
1010 *
1011 * edge1 and edge2 are assumed to have the same value for the map field.
1012 */
1013static int merge_edge(struct isl_sched_edge *edge1,
1014 struct isl_sched_edge *edge2)
1015{
1016 edge1->types |= edge2->types;
1017 isl_map_free(edge2->map);
1018
1019 if (is_condition(edge2)) {
1020 if (!edge1->tagged_condition)
1021 edge1->tagged_condition = edge2->tagged_condition;
1022 else
1023 edge1->tagged_condition =
1024 isl_union_map_union(edge1->tagged_condition,
1025 edge2->tagged_condition);
1026 }
1027
1028 if (is_conditional_validity(edge2)) {
1029 if (!edge1->tagged_validity)
1030 edge1->tagged_validity = edge2->tagged_validity;
1031 else
1032 edge1->tagged_validity =
1033 isl_union_map_union(edge1->tagged_validity,
1034 edge2->tagged_validity);
1035 }
1036
1037 if (is_condition(edge2) && !edge1->tagged_condition)
1038 return -1;
1039 if (is_conditional_validity(edge2) && !edge1->tagged_validity)
1040 return -1;
1041
1042 return 0;
1043}
1044
1045/* Insert dummy tags in domain and range of "map".
1046 *
1047 * In particular, if "map" is of the form
1048 *
1049 * A -> B
1050 *
1051 * then return
1052 *
1053 * [A -> dummy_tag] -> [B -> dummy_tag]
1054 *
1055 * where the dummy_tags are identical and equal to any dummy tags
1056 * introduced by any other call to this function.
1057 */
1058static __isl_give isl_map *insert_dummy_tags(__isl_take isl_map *map)
1059{
1060 static char dummy;
1061 isl_ctx *ctx;
1062 isl_id *id;
1063 isl_space *space;
1064 isl_setisl_map *domain, *range;
1065
1066 ctx = isl_map_get_ctx(map);
1067
1068 id = isl_id_alloc(ctx, NULL((void*)0), &dummy);
1069 space = isl_space_params(isl_map_get_space(map));
1070 space = isl_space_set_from_params(space);
1071 space = isl_space_set_tuple_id(space, isl_dim_set, id);
1072 space = isl_space_map_from_set(space);
1073
1074 domain = isl_map_wrap(map);
1075 range = isl_map_wrap(isl_map_universe(space));
1076 map = isl_map_from_domain_and_range(domain, range);
1077 map = isl_map_zip(map);
1078
1079 return map;
1080}
1081
1082/* Given that at least one of "src" or "dst" is compressed, return
1083 * a map between the spaces of these nodes restricted to the affine
1084 * hull that was used in the compression.
1085 */
1086static __isl_give isl_map *extract_hull(struct isl_sched_node *src,
1087 struct isl_sched_node *dst)
1088{
1089 isl_setisl_map *dom, *ran;
1090
1091 if (src->compressed)
1092 dom = isl_set_copy(src->hull);
1093 else
1094 dom = isl_set_universe(isl_space_copy(src->space));
1095 if (dst->compressed)
1096 ran = isl_set_copy(dst->hull);
1097 else
1098 ran = isl_set_universe(isl_space_copy(dst->space));
1099
1100 return isl_map_from_domain_and_range(dom, ran);
1101}
1102
1103/* Intersect the domains of the nested relations in domain and range
1104 * of "tagged" with "map".
1105 */
1106static __isl_give isl_map *map_intersect_domains(__isl_take isl_map *tagged,
1107 __isl_keep isl_map *map)
1108{
1109 isl_setisl_map *set;
1110
1111 tagged = isl_map_zip(tagged);
1112 set = isl_map_wrap(isl_map_copy(map));
1113 tagged = isl_map_intersect_domain(tagged, set);
1114 tagged = isl_map_zip(tagged);
1115 return tagged;
1116}
1117
1118/* Return a pointer to the node that lives in the domain space of "map"
1119 * or NULL if there is no such node.
1120 */
1121static struct isl_sched_node *find_domain_node(isl_ctx *ctx,
1122 struct isl_sched_graph *graph, __isl_keep isl_map *map)
1123{
1124 struct isl_sched_node *node;
1125 isl_space *space;
1126
1127 space = isl_space_domain(isl_map_get_space(map));
1128 node = graph_find_node(ctx, graph, space);
1129 isl_space_free(space);
1130
1131 return node;
1132}
1133
1134/* Return a pointer to the node that lives in the range space of "map"
1135 * or NULL if there is no such node.
1136 */
1137static struct isl_sched_node *find_range_node(isl_ctx *ctx,
1138 struct isl_sched_graph *graph, __isl_keep isl_map *map)
1139{
1140 struct isl_sched_node *node;
1141 isl_space *space;
1142
1143 space = isl_space_range(isl_map_get_space(map));
1144 node = graph_find_node(ctx, graph, space);
1145 isl_space_free(space);
1146
1147 return node;
1148}
1149
1150/* Add a new edge to the graph based on the given map
1151 * and add it to data->graph->edge_table[data->type].
1152 * If a dependence relation of a given type happens to be identical
1153 * to one of the dependence relations of a type that was added before,
1154 * then we don't create a new edge, but instead mark the original edge
1155 * as also representing a dependence of the current type.
1156 *
1157 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1158 * may be specified as "tagged" dependence relations. That is, "map"
1159 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1160 * the dependence on iterations and a and b are tags.
1161 * edge->map is set to the relation containing the elements i -> j,
1162 * while edge->tagged_condition and edge->tagged_validity contain
1163 * the union of all the "map" relations
1164 * for which extract_edge is called that result in the same edge->map.
1165 *
1166 * If the source or the destination node is compressed, then
1167 * intersect both "map" and "tagged" with the constraints that
1168 * were used to construct the compression.
1169 * This ensures that there are no schedule constraints defined
1170 * outside of these domains, while the scheduler no longer has
1171 * any control over those outside parts.
1172 */
1173static isl_stat extract_edge(__isl_take isl_map *map, void *user)
1174{
1175 isl_ctx *ctx = isl_map_get_ctx(map);
1176 struct isl_extract_edge_data *data = user;
1177 struct isl_sched_graph *graph = data->graph;
1178 struct isl_sched_node *src, *dst;
1179 struct isl_sched_edge *edge;
1180 isl_map *tagged = NULL((void*)0);
1181
1182 if (data->type == isl_edge_condition ||
1183 data->type == isl_edge_conditional_validity) {
1184 if (isl_map_can_zip(map)) {
1185 tagged = isl_map_copy(map);
1186 map = isl_set_unwrap(isl_map_domain(isl_map_zip(map)));
1187 } else {
1188 tagged = insert_dummy_tags(isl_map_copy(map));
1189 }
1190 }
1191
1192 src = find_domain_node(ctx, graph, map);
1193 dst = find_range_node(ctx, graph, map);
1194
1195 if (!src || !dst) {
1196 isl_map_free(map);
1197 isl_map_free(tagged);
1198 return isl_stat_ok;
1199 }
1200
1201 if (src->compressed || dst->compressed) {
1202 isl_map *hull;
1203 hull = extract_hull(src, dst);
1204 if (tagged)
1205 tagged = map_intersect_domains(tagged, hull);
1206 map = isl_map_intersect(map, hull);
1207 }
1208
1209 graph->edge[graph->n_edge].src = src;
1210 graph->edge[graph->n_edge].dst = dst;
1211 graph->edge[graph->n_edge].map = map;
1212 graph->edge[graph->n_edge].types = 0;
1213 graph->edge[graph->n_edge].tagged_condition = NULL((void*)0);
1214 graph->edge[graph->n_edge].tagged_validity = NULL((void*)0);
1215 set_type(&graph->edge[graph->n_edge], data->type);
1216 if (data->type == isl_edge_condition)
1217 graph->edge[graph->n_edge].tagged_condition =
1218 isl_union_map_from_map(tagged);
1219 if (data->type == isl_edge_conditional_validity)
1220 graph->edge[graph->n_edge].tagged_validity =
1221 isl_union_map_from_map(tagged);
1222
1223 edge = graph_find_matching_edge(graph, &graph->edge[graph->n_edge]);
1224 if (!edge) {
1225 graph->n_edge++;
1226 return isl_stat_error;
1227 }
1228 if (edge == &graph->edge[graph->n_edge])
1229 return graph_edge_table_add(ctx, graph, data->type,
1230 &graph->edge[graph->n_edge++]);
1231
1232 if (merge_edge(edge, &graph->edge[graph->n_edge]) < 0)
1233 return -1;
1234
1235 return graph_edge_table_add(ctx, graph, data->type, edge);
1236}
1237
1238/* Initialize the schedule graph "graph" from the schedule constraints "sc".
1239 *
1240 * The context is included in the domain before the nodes of
1241 * the graphs are extracted in order to be able to exploit
1242 * any possible additional equalities.
1243 * Note that this intersection is only performed locally here.
1244 */
1245static isl_stat graph_init(struct isl_sched_graph *graph,
1246 __isl_keep isl_schedule_constraints *sc)
1247{
1248 isl_ctx *ctx;
1249 isl_union_set *domain;
1250 isl_union_map *c;
1251 struct isl_extract_edge_data data;
1252 enum isl_edge_type i;
1253 isl_stat r;
1254
1255 if (!sc)
1256 return isl_stat_error;
1257
1258 ctx = isl_schedule_constraints_get_ctx(sc);
1259
1260 domain = isl_schedule_constraints_get_domain(sc);
1261 graph->n = isl_union_set_n_set(domain);
1262 isl_union_set_free(domain);
1263
1264 if (graph_alloc(ctx, graph, graph->n,
1265 isl_schedule_constraints_n_map(sc)) < 0)
1266 return isl_stat_error;
1267
1268 if (compute_max_row(graph, sc) < 0)
1269 return isl_stat_error;
1270 graph->root = 1;
1271 graph->n = 0;
1272 domain = isl_schedule_constraints_get_domain(sc);
1273 domain = isl_union_set_intersect_params(domain,
1274 isl_schedule_constraints_get_context(sc));
1275 r = isl_union_set_foreach_set(domain, &extract_node, graph);
1276 isl_union_set_free(domain);
1277 if (r < 0)
1278 return isl_stat_error;
1279 if (graph_init_table(ctx, graph) < 0)
1280 return isl_stat_error;
1281 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
1282 c = isl_schedule_constraints_get(sc, i);
1283 graph->max_edge[i] = isl_union_map_n_map(c);
1284 isl_union_map_free(c);
1285 if (!c)
1286 return isl_stat_error;
1287 }
1288 if (graph_init_edge_tables(ctx, graph) < 0)
1289 return isl_stat_error;
1290 graph->n_edge = 0;
1291 data.graph = graph;
1292 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
1293 isl_stat r;
1294
1295 data.type = i;
1296 c = isl_schedule_constraints_get(sc, i);
1297 r = isl_union_map_foreach_map(c, &extract_edge, &data);
1298 isl_union_map_free(c);
1299 if (r < 0)
1300 return isl_stat_error;
1301 }
1302
1303 return isl_stat_ok;
1304}
1305
1306/* Check whether there is any dependence from node[j] to node[i]
1307 * or from node[i] to node[j].
1308 */
1309static isl_bool node_follows_weak(int i, int j, void *user)
1310{
1311 isl_bool f;
1312 struct isl_sched_graph *graph = user;
1313
1314 f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]);
1315 if (f < 0 || f)
1316 return f;
1317 return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]);
1318}
1319
1320/* Check whether there is a (conditional) validity dependence from node[j]
1321 * to node[i], forcing node[i] to follow node[j].
1322 */
1323static isl_bool node_follows_strong(int i, int j, void *user)
1324{
1325 struct isl_sched_graph *graph = user;
1326
1327 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
1328}
1329
1330/* Use Tarjan's algorithm for computing the strongly connected components
1331 * in the dependence graph only considering those edges defined by "follows".
1332 */
1333static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph,
1334 isl_bool (*follows)(int i, int j, void *user))
1335{
1336 int i, n;
1337 struct isl_tarjan_graph *g = NULL((void*)0);
1338
1339 g = isl_tarjan_graph_init(ctx, graph->n, follows, graph);
1340 if (!g)
1341 return -1;
1342
1343 graph->scc = 0;
1344 i = 0;
1345 n = graph->n;
1346 while (n) {
1347 while (g->order[i] != -1) {
1348 graph->node[g->order[i]].scc = graph->scc;
1349 --n;
1350 ++i;
1351 }
1352 ++i;
1353 graph->scc++;
1354 }
1355
1356 isl_tarjan_graph_free(g);
1357
1358 return 0;
1359}
1360
1361/* Apply Tarjan's algorithm to detect the strongly connected components
1362 * in the dependence graph.
1363 * Only consider the (conditional) validity dependences and clear "weak".
1364 */
1365static int detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1366{
1367 graph->weak = 0;
1368 return detect_ccs(ctx, graph, &node_follows_strong);
1369}
1370
1371/* Apply Tarjan's algorithm to detect the (weakly) connected components
1372 * in the dependence graph.
1373 * Consider all dependences and set "weak".
1374 */
1375static int detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1376{
1377 graph->weak = 1;
1378 return detect_ccs(ctx, graph, &node_follows_weak);
1379}
1380
1381static int cmp_scc(const void *a, const void *b, void *data)
1382{
1383 struct isl_sched_graph *graph = data;
1384 const int *i1 = a;
1385 const int *i2 = b;
1386
1387 return graph->node[*i1].scc - graph->node[*i2].scc;
1388}
1389
1390/* Sort the elements of graph->sorted according to the corresponding SCCs.
1391 */
1392static int sort_sccs(struct isl_sched_graph *graph)
1393{
1394 return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
1395}
1396
1397/* Given a dependence relation R from "node" to itself,
1398 * construct the set of coefficients of valid constraints for elements
1399 * in that dependence relation.
1400 * In particular, the result contains tuples of coefficients
1401 * c_0, c_n, c_x such that
1402 *
1403 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1404 *
1405 * or, equivalently,
1406 *
1407 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1408 *
1409 * We choose here to compute the dual of delta R.
1410 * Alternatively, we could have computed the dual of R, resulting
1411 * in a set of tuples c_0, c_n, c_x, c_y, and then
1412 * plugged in (c_0, c_n, c_x, -c_x).
1413 *
1414 * If "node" has been compressed, then the dependence relation
1415 * is also compressed before the set of coefficients is computed.
1416 */
1417static __isl_give isl_basic_setisl_basic_map *intra_coefficients(
1418 struct isl_sched_graph *graph, struct isl_sched_node *node,
1419 __isl_take isl_map *map)
1420{
1421 isl_setisl_map *delta;
1422 isl_map *key;
1423 isl_basic_setisl_basic_map *coef;
1424 isl_maybe_isl_basic_setisl_maybe_isl_basic_map m;
1425
1426 m = isl_map_to_basic_set_try_get(graph->intra_hmap, map);
1427 if (m.valid < 0 || m.valid) {
1428 isl_map_free(map);
1429 return m.value;
1430 }
1431
1432 key = isl_map_copy(map);
1433 if (node->compressed) {
1434 map = isl_map_preimage_domain_multi_aff(map,
1435 isl_multi_aff_copy(node->decompress));
1436 map = isl_map_preimage_range_multi_aff(map,
1437 isl_multi_aff_copy(node->decompress));
1438 }
1439 delta = isl_set_remove_divs(isl_map_deltas(map));
1440 coef = isl_set_coefficients(delta);
1441 graph->intra_hmap = isl_map_to_basic_set_set(graph->intra_hmap, key,
1442 isl_basic_set_copy(coef));
1443
1444 return coef;
1445}
1446
1447/* Given a dependence relation R, construct the set of coefficients
1448 * of valid constraints for elements in that dependence relation.
1449 * In particular, the result contains tuples of coefficients
1450 * c_0, c_n, c_x, c_y such that
1451 *
1452 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1453 *
1454 * If the source or destination nodes of "edge" have been compressed,
1455 * then the dependence relation is also compressed before
1456 * the set of coefficients is computed.
1457 */
1458static __isl_give isl_basic_setisl_basic_map *inter_coefficients(
1459 struct isl_sched_graph *graph, struct isl_sched_edge *edge,
1460 __isl_take isl_map *map)
1461{
1462 isl_setisl_map *set;
1463 isl_map *key;
1464 isl_basic_setisl_basic_map *coef;
1465 isl_maybe_isl_basic_setisl_maybe_isl_basic_map m;
1466
1467 m = isl_map_to_basic_set_try_get(graph->inter_hmap, map);
1468 if (m.valid < 0 || m.valid) {
1469 isl_map_free(map);
1470 return m.value;
1471 }
1472
1473 key = isl_map_copy(map);
1474 if (edge->src->compressed)
1475 map = isl_map_preimage_domain_multi_aff(map,
1476 isl_multi_aff_copy(edge->src->decompress));
1477 if (edge->dst->compressed)
1478 map = isl_map_preimage_range_multi_aff(map,
1479 isl_multi_aff_copy(edge->dst->decompress));
1480 set = isl_map_wrap(isl_map_remove_divs(map));
1481 coef = isl_set_coefficients(set);
1482 graph->inter_hmap = isl_map_to_basic_set_set(graph->inter_hmap, key,
1483 isl_basic_set_copy(coef));
1484
1485 return coef;
1486}
1487
1488/* Return the position of the coefficients of the variables in
1489 * the coefficients constraints "coef".
1490 *
1491 * The space of "coef" is of the form
1492 *
1493 * { coefficients[[cst, params] -> S] }
1494 *
1495 * Return the position of S.
1496 */
1497static int coef_var_offset(__isl_keep isl_basic_setisl_basic_map *coef)
1498{
1499 int offset;
1500 isl_space *space;
1501
1502 space = isl_space_unwrap(isl_basic_set_get_space(coef));
1503 offset = isl_space_dim(space, isl_dim_in);
1504 isl_space_free(space);
1505
1506 return offset;
1507}
1508
1509/* Return the offset of the coefficients of the variables of "node"
1510 * within the (I)LP.
1511 *
1512 * Within each node, the coefficients have the following order:
1513 * - c_i_0
1514 * - c_i_n (if parametric)
1515 * - positive and negative parts of c_i_x
1516 */
1517static int node_var_coef_offset(struct isl_sched_node *node)
1518{
1519 return node->start + 1 + node->nparam;
1520}
1521
1522/* Construct an isl_dim_map for mapping constraints on coefficients
1523 * for "node" to the corresponding positions in graph->lp.
1524 * "offset" is the offset of the coefficients for the variables
1525 * in the input constraints.
1526 * "s" is the sign of the mapping.
1527 *
1528 * The input constraints are given in terms of the coefficients (c_0, c_n, c_x).
1529 * The mapping produced by this function essentially plugs in
1530 * (0, 0, c_i_x^+ - c_i_x^-) if s = 1 and
1531 * (0, 0, -c_i_x^+ + c_i_x^-) if s = -1.
1532 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1533 *
1534 * The caller can extend the mapping to also map the other coefficients
1535 * (and therefore not plug in 0).
1536 */
1537static __isl_give isl_dim_map *intra_dim_map(isl_ctx *ctx,
1538 struct isl_sched_graph *graph, struct isl_sched_node *node,
1539 int offset, int s)
1540{
1541 int pos;
1542 unsigned total;
1543 isl_dim_map *dim_map;
1544
1545 total = isl_basic_set_total_dim(graph->lp);
1546 pos = node_var_coef_offset(node);
1547 dim_map = isl_dim_map_alloc(ctx, total);
1548 isl_dim_map_range(dim_map, pos, 2, offset, 1, node->nvar, -s);
1549 isl_dim_map_range(dim_map, pos + 1, 2, offset, 1, node->nvar, s);
1550
1551 return dim_map;
1552}
1553
1554/* Construct an isl_dim_map for mapping constraints on coefficients
1555 * for "src" (node i) and "dst" (node j) to the corresponding positions
1556 * in graph->lp.
1557 * "offset" is the offset of the coefficients for the variables of "src"
1558 * in the input constraints.
1559 * "s" is the sign of the mapping.
1560 *
1561 * The input constraints are given in terms of the coefficients
1562 * (c_0, c_n, c_x, c_y).
1563 * The mapping produced by this function essentially plugs in
1564 * (c_j_0 - c_i_0, c_j_n - c_i_n,
1565 * c_j_x^+ - c_j_x^-, -(c_i_x^+ - c_i_x^-)) if s = 1 and
1566 * (-c_j_0 + c_i_0, -c_j_n + c_i_n,
1567 * - (c_j_x^+ - c_j_x^-), c_i_x^+ - c_i_x^-) if s = -1.
1568 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1569 *
1570 * The caller can further extend the mapping.
1571 */
1572static __isl_give isl_dim_map *inter_dim_map(isl_ctx *ctx,
1573 struct isl_sched_graph *graph, struct isl_sched_node *src,
1574 struct isl_sched_node *dst, int offset, int s)
1575{
1576 int pos;
1577 unsigned total;
1578 isl_dim_map *dim_map;
1579
1580 total = isl_basic_set_total_dim(graph->lp);
1581 dim_map = isl_dim_map_alloc(ctx, total);
1582
1583 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, s);
1584 isl_dim_map_range(dim_map, dst->start + 1, 1, 1, 1, dst->nparam, s);
1585 pos = node_var_coef_offset(dst);
1586 isl_dim_map_range(dim_map, pos, 2, offset + src->nvar, 1,
1587 dst->nvar, -s);
1588 isl_dim_map_range(dim_map, pos + 1, 2, offset + src->nvar, 1,
1589 dst->nvar, s);
1590
1591 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -s);
1592 isl_dim_map_range(dim_map, src->start + 1, 1, 1, 1, src->nparam, -s);
1593 pos = node_var_coef_offset(src);
1594 isl_dim_map_range(dim_map, pos, 2, offset, 1, src->nvar, s);
1595 isl_dim_map_range(dim_map, pos + 1, 2, offset, 1, src->nvar, -s);
1596
1597 return dim_map;
1598}
1599
1600/* Add constraints to graph->lp that force validity for the given
1601 * dependence from a node i to itself.
1602 * That is, add constraints that enforce
1603 *
1604 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1605 * = c_i_x (y - x) >= 0
1606 *
1607 * for each (x,y) in R.
1608 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1609 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1610 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1611 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1612 *
1613 * Actually, we do not construct constraints for the c_i_x themselves,
1614 * but for the coefficients of c_i_x written as a linear combination
1615 * of the columns in node->cmap.
1616 */
1617static isl_stat add_intra_validity_constraints(struct isl_sched_graph *graph,
1618 struct isl_sched_edge *edge)
1619{
1620 int offset;
1621 isl_map *map = isl_map_copy(edge->map);
1622 isl_ctx *ctx = isl_map_get_ctx(map);
1623 isl_dim_map *dim_map;
1624 isl_basic_setisl_basic_map *coef;
1625 struct isl_sched_node *node = edge->src;
1626
1627 coef = intra_coefficients(graph, node, map);
1628
1629 offset = coef_var_offset(coef);
1630
1631 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1632 offset, isl_mat_copy(node->cmap));
1633 if (!coef)
1634 return isl_stat_error;
1635
1636 dim_map = intra_dim_map(ctx, graph, node, offset, 1);
1637 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1638 coef->n_eq, coef->n_ineq);
1639 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1640 coef, dim_map);
1641
1642 return isl_stat_ok;
1643}
1644
1645/* Add constraints to graph->lp that force validity for the given
1646 * dependence from node i to node j.
1647 * That is, add constraints that enforce
1648 *
1649 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1650 *
1651 * for each (x,y) in R.
1652 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1653 * of valid constraints for R and then plug in
1654 * (c_j_0 - c_i_0, c_j_n - c_i_n, c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1655 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1656 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1657 *
1658 * Actually, we do not construct constraints for the c_*_x themselves,
1659 * but for the coefficients of c_*_x written as a linear combination
1660 * of the columns in node->cmap.
1661 */
1662static isl_stat add_inter_validity_constraints(struct isl_sched_graph *graph,
1663 struct isl_sched_edge *edge)
1664{
1665 int offset;
1666 isl_map *map = isl_map_copy(edge->map);
1667 isl_ctx *ctx = isl_map_get_ctx(map);
1668 isl_dim_map *dim_map;
1669 isl_basic_setisl_basic_map *coef;
1670 struct isl_sched_node *src = edge->src;
1671 struct isl_sched_node *dst = edge->dst;
1672
1673 coef = inter_coefficients(graph, edge, map);
1674
1675 offset = coef_var_offset(coef);
1676
1677 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1678 offset, isl_mat_copy(src->cmap));
1679 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1680 offset + src->nvar, isl_mat_copy(dst->cmap));
1681 if (!coef)
1682 return isl_stat_error;
1683
1684 dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1);
1685
1686 edge->start = graph->lp->n_ineq;
1687 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1688 coef->n_eq, coef->n_ineq);
1689 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1690 coef, dim_map);
1691 if (!graph->lp)
1692 return isl_stat_error;
1693 edge->end = graph->lp->n_ineq;
1694
1695 return isl_stat_ok;
1696}
1697
1698/* Add constraints to graph->lp that bound the dependence distance for the given
1699 * dependence from a node i to itself.
1700 * If s = 1, we add the constraint
1701 *
1702 * c_i_x (y - x) <= m_0 + m_n n
1703 *
1704 * or
1705 *
1706 * -c_i_x (y - x) + m_0 + m_n n >= 0
1707 *
1708 * for each (x,y) in R.
1709 * If s = -1, we add the constraint
1710 *
1711 * -c_i_x (y - x) <= m_0 + m_n n
1712 *
1713 * or
1714 *
1715 * c_i_x (y - x) + m_0 + m_n n >= 0
1716 *
1717 * for each (x,y) in R.
1718 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1719 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1720 * with each coefficient (except m_0) represented as a pair of non-negative
1721 * coefficients.
1722 *
1723 * Actually, we do not construct constraints for the c_i_x themselves,
1724 * but for the coefficients of c_i_x written as a linear combination
1725 * of the columns in node->cmap.
1726 *
1727 *
1728 * If "local" is set, then we add constraints
1729 *
1730 * c_i_x (y - x) <= 0
1731 *
1732 * or
1733 *
1734 * -c_i_x (y - x) <= 0
1735 *
1736 * instead, forcing the dependence distance to be (less than or) equal to 0.
1737 * That is, we plug in (0, 0, -s * c_i_x),
1738 * Note that dependences marked local are treated as validity constraints
1739 * by add_all_validity_constraints and therefore also have
1740 * their distances bounded by 0 from below.
1741 */
1742static isl_stat add_intra_proximity_constraints(struct isl_sched_graph *graph,
1743 struct isl_sched_edge *edge, int s, int local)
1744{
1745 int offset;
1746 unsigned nparam;
1747 isl_map *map = isl_map_copy(edge->map);
1748 isl_ctx *ctx = isl_map_get_ctx(map);
1749 isl_dim_map *dim_map;
1750 isl_basic_setisl_basic_map *coef;
1751 struct isl_sched_node *node = edge->src;
1752
1753 coef = intra_coefficients(graph, node, map);
1754
1755 offset = coef_var_offset(coef);
1756
1757 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1758 offset, isl_mat_copy(node->cmap));
1759 if (!coef)
1760 return isl_stat_error;
1761
1762 nparam = isl_space_dim(node->space, isl_dim_param);
1763 dim_map = intra_dim_map(ctx, graph, node, offset, -s);
1764
1765 if (!local) {
1766 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1767 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1768 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1769 }
1770 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1771 coef->n_eq, coef->n_ineq);
1772 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1773 coef, dim_map);
1774
1775 return isl_stat_ok;
1776}
1777
1778/* Add constraints to graph->lp that bound the dependence distance for the given
1779 * dependence from node i to node j.
1780 * If s = 1, we add the constraint
1781 *
1782 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1783 * <= m_0 + m_n n
1784 *
1785 * or
1786 *
1787 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1788 * m_0 + m_n n >= 0
1789 *
1790 * for each (x,y) in R.
1791 * If s = -1, we add the constraint
1792 *
1793 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1794 * <= m_0 + m_n n
1795 *
1796 * or
1797 *
1798 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1799 * m_0 + m_n n >= 0
1800 *
1801 * for each (x,y) in R.
1802 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1803 * of valid constraints for R and then plug in
1804 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1805 * -s*c_j_x+s*c_i_x)
1806 * with each coefficient (except m_0, c_*_0 and c_*_n)
1807 * represented as a pair of non-negative coefficients.
1808 *
1809 * Actually, we do not construct constraints for the c_*_x themselves,
1810 * but for the coefficients of c_*_x written as a linear combination
1811 * of the columns in node->cmap.
1812 *
1813 *
1814 * If "local" is set, then we add constraints
1815 *
1816 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1817 *
1818 * or
1819 *
1820 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1821 *
1822 * instead, forcing the dependence distance to be (less than or) equal to 0.
1823 * That is, we plug in
1824 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1825 * Note that dependences marked local are treated as validity constraints
1826 * by add_all_validity_constraints and therefore also have
1827 * their distances bounded by 0 from below.
1828 */
1829static isl_stat add_inter_proximity_constraints(struct isl_sched_graph *graph,
1830 struct isl_sched_edge *edge, int s, int local)
1831{
1832 int offset;
1833 unsigned nparam;
1834 isl_map *map = isl_map_copy(edge->map);
1835 isl_ctx *ctx = isl_map_get_ctx(map);
1836 isl_dim_map *dim_map;
1837 isl_basic_setisl_basic_map *coef;
1838 struct isl_sched_node *src = edge->src;
1839 struct isl_sched_node *dst = edge->dst;
1840
1841 coef = inter_coefficients(graph, edge, map);
1842
1843 offset = coef_var_offset(coef);
1844
1845 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1846 offset, isl_mat_copy(src->cmap));
1847 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1848 offset + src->nvar, isl_mat_copy(dst->cmap));
1849 if (!coef)
1850 return isl_stat_error;
1851
1852 nparam = isl_space_dim(src->space, isl_dim_param);
1853 dim_map = inter_dim_map(ctx, graph, src, dst, offset, -s);
1854
1855 if (!local) {
1856 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1857 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1858 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1859 }
1860
1861 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1862 coef->n_eq, coef->n_ineq);
1863 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1864 coef, dim_map);
1865
1866 return isl_stat_ok;
1867}
1868
1869/* Add all validity constraints to graph->lp.
1870 *
1871 * An edge that is forced to be local needs to have its dependence
1872 * distances equal to zero. We take care of bounding them by 0 from below
1873 * here. add_all_proximity_constraints takes care of bounding them by 0
1874 * from above.
1875 *
1876 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1877 * Otherwise, we ignore them.
1878 */
1879static int add_all_validity_constraints(struct isl_sched_graph *graph,
1880 int use_coincidence)
1881{
1882 int i;
1883
1884 for (i = 0; i < graph->n_edge; ++i) {
1885 struct isl_sched_edge *edge= &graph->edge[i];
1886 int local;
1887
1888 local = is_local(edge) ||
1889 (is_coincidence(edge) && use_coincidence);
1890 if (!is_validity(edge) && !local)
1891 continue;
1892 if (edge->src != edge->dst)
1893 continue;
1894 if (add_intra_validity_constraints(graph, edge) < 0)
1895 return -1;
1896 }
1897
1898 for (i = 0; i < graph->n_edge; ++i) {
1899 struct isl_sched_edge *edge = &graph->edge[i];
1900 int local;
1901
1902 local = is_local(edge) ||
1903 (is_coincidence(edge) && use_coincidence);
1904 if (!is_validity(edge) && !local)
1905 continue;
1906 if (edge->src == edge->dst)
1907 continue;
1908 if (add_inter_validity_constraints(graph, edge) < 0)
1909 return -1;
1910 }
1911
1912 return 0;
1913}
1914
1915/* Add constraints to graph->lp that bound the dependence distance
1916 * for all dependence relations.
1917 * If a given proximity dependence is identical to a validity
1918 * dependence, then the dependence distance is already bounded
1919 * from below (by zero), so we only need to bound the distance
1920 * from above. (This includes the case of "local" dependences
1921 * which are treated as validity dependence by add_all_validity_constraints.)
1922 * Otherwise, we need to bound the distance both from above and from below.
1923 *
1924 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1925 * Otherwise, we ignore them.
1926 */
1927static int add_all_proximity_constraints(struct isl_sched_graph *graph,
1928 int use_coincidence)
1929{
1930 int i;
1931
1932 for (i = 0; i < graph->n_edge; ++i) {
1933 struct isl_sched_edge *edge= &graph->edge[i];
1934 int local;
1935
1936 local = is_local(edge) ||
1937 (is_coincidence(edge) && use_coincidence);
1938 if (!is_proximity(edge) && !local)
1939 continue;
1940 if (edge->src == edge->dst &&
1941 add_intra_proximity_constraints(graph, edge, 1, local) < 0)
1942 return -1;
1943 if (edge->src != edge->dst &&
1944 add_inter_proximity_constraints(graph, edge, 1, local) < 0)
1945 return -1;
1946 if (is_validity(edge) || local)
1947 continue;
1948 if (edge->src == edge->dst &&
1949 add_intra_proximity_constraints(graph, edge, -1, 0) < 0)
1950 return -1;
1951 if (edge->src != edge->dst &&
1952 add_inter_proximity_constraints(graph, edge, -1, 0) < 0)
1953 return -1;
1954 }
1955
1956 return 0;
1957}
1958
1959/* Compute a basis for the rows in the linear part of the schedule
1960 * and extend this basis to a full basis. The remaining rows
1961 * can then be used to force linear independence from the rows
1962 * in the schedule.
1963 *
1964 * In particular, given the schedule rows S, we compute
1965 *
1966 * S = H Q
1967 * S U = H
1968 *
1969 * with H the Hermite normal form of S. That is, all but the
1970 * first rank columns of H are zero and so each row in S is
1971 * a linear combination of the first rank rows of Q.
1972 * The matrix Q is then transposed because we will write the
1973 * coefficients of the next schedule row as a column vector s
1974 * and express this s as a linear combination s = Q c of the
1975 * computed basis.
1976 * Similarly, the matrix U is transposed such that we can
1977 * compute the coefficients c = U s from a schedule row s.
1978 */
1979static int node_update_cmap(struct isl_sched_node *node)
1980{
1981 isl_mat *H, *U, *Q;
1982 int n_row = isl_mat_rows(node->sched);
1983
1984 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1985 1 + node->nparam, node->nvar);
1986
1987 H = isl_mat_left_hermite(H, 0, &U, &Q);
1988 isl_mat_free(node->cmap);
1989 isl_mat_free(node->cinv);
1990 isl_mat_free(node->ctrans);
1991 node->ctrans = isl_mat_copy(Q);
1992 node->cmap = isl_mat_transpose(Q);
1993 node->cinv = isl_mat_transpose(U);
1994 node->rank = isl_mat_initial_non_zero_cols(H);
1995 isl_mat_free(H);
1996
1997 if (!node->cmap || !node->cinv || !node->ctrans || node->rank < 0)
1998 return -1;
1999 return 0;
2000}
2001
2002/* Is "edge" marked as a validity or a conditional validity edge?
2003 */
2004static int is_any_validity(struct isl_sched_edge *edge)
2005{
2006 return is_validity(edge) || is_conditional_validity(edge);
2007}
2008
2009/* How many times should we count the constraints in "edge"?
2010 *
2011 * If carry is set, then we are counting the number of
2012 * (validity or conditional validity) constraints that will be added
2013 * in setup_carry_lp and we count each edge exactly once.
2014 *
2015 * Otherwise, we count as follows
2016 * validity -> 1 (>= 0)
2017 * validity+proximity -> 2 (>= 0 and upper bound)
2018 * proximity -> 2 (lower and upper bound)
2019 * local(+any) -> 2 (>= 0 and <= 0)
2020 *
2021 * If an edge is only marked conditional_validity then it counts
2022 * as zero since it is only checked afterwards.
2023 *
2024 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2025 * Otherwise, we ignore them.
2026 */
2027static int edge_multiplicity(struct isl_sched_edge *edge, int carry,
2028 int use_coincidence)
2029{
2030 if (carry)
2031 return 1;
2032 if (is_proximity(edge) || is_local(edge))
2033 return 2;
2034 if (use_coincidence && is_coincidence(edge))
2035 return 2;
2036 if (is_validity(edge))
2037 return 1;
2038 return 0;
2039}
2040
2041/* Count the number of equality and inequality constraints
2042 * that will be added for the given map.
2043 *
2044 * "use_coincidence" is set if we should take into account coincidence edges.
2045 */
2046static isl_stat count_map_constraints(struct isl_sched_graph *graph,
2047 struct isl_sched_edge *edge, __isl_take isl_map *map,
2048 int *n_eq, int *n_ineq, int carry, int use_coincidence)
2049{
2050 isl_basic_setisl_basic_map *coef;
2051 int f = edge_multiplicity(edge, carry, use_coincidence);
2052
2053 if (f == 0) {
2054 isl_map_free(map);
2055 return isl_stat_ok;
2056 }
2057
2058 if (edge->src == edge->dst)
2059 coef = intra_coefficients(graph, edge->src, map);
2060 else
2061 coef = inter_coefficients(graph, edge, map);
2062 if (!coef)
2063 return isl_stat_error;
2064 *n_eq += f * coef->n_eq;
2065 *n_ineq += f * coef->n_ineq;
2066 isl_basic_set_free(coef);
2067
2068 return isl_stat_ok;
2069}
2070
2071/* Count the number of equality and inequality constraints
2072 * that will be added to the main lp problem.
2073 * We count as follows
2074 * validity -> 1 (>= 0)
2075 * validity+proximity -> 2 (>= 0 and upper bound)
2076 * proximity -> 2 (lower and upper bound)
2077 * local(+any) -> 2 (>= 0 and <= 0)
2078 *
2079 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2080 * Otherwise, we ignore them.
2081 */
2082static int count_constraints(struct isl_sched_graph *graph,
2083 int *n_eq, int *n_ineq, int use_coincidence)
2084{
2085 int i;
2086
2087 *n_eq = *n_ineq = 0;
2088 for (i = 0; i < graph->n_edge; ++i) {
2089 struct isl_sched_edge *edge= &graph->edge[i];
2090 isl_map *map = isl_map_copy(edge->map);
2091
2092 if (count_map_constraints(graph, edge, map, n_eq, n_ineq,
2093 0, use_coincidence) < 0)
2094 return -1;
2095 }
2096
2097 return 0;
2098}
2099
2100/* Count the number of constraints that will be added by
2101 * add_bound_constant_constraints to bound the values of the constant terms
2102 * and increment *n_eq and *n_ineq accordingly.
2103 *
2104 * In practice, add_bound_constant_constraints only adds inequalities.
2105 */
2106static isl_stat count_bound_constant_constraints(isl_ctx *ctx,
2107 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2108{
2109 if (isl_options_get_schedule_max_constant_term(ctx) == -1)
2110 return isl_stat_ok;
2111
2112 *n_ineq += graph->n;
2113
2114 return isl_stat_ok;
2115}
2116
2117/* Add constraints to bound the values of the constant terms in the schedule,
2118 * if requested by the user.
2119 *
2120 * The maximal value of the constant terms is defined by the option
2121 * "schedule_max_constant_term".
2122 *
2123 * Within each node, the coefficients have the following order:
2124 * - c_i_0
2125 * - c_i_n (if parametric)
2126 * - positive and negative parts of c_i_x
2127 */
2128static isl_stat add_bound_constant_constraints(isl_ctx *ctx,
2129 struct isl_sched_graph *graph)
2130{
2131 int i, k;
2132 int max;
2133 int total;
2134
2135 max = isl_options_get_schedule_max_constant_term(ctx);
2136 if (max == -1)
2137 return isl_stat_ok;
2138
2139 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2140
2141 for (i = 0; i < graph->n; ++i) {
2142 struct isl_sched_node *node = &graph->node[i];
2143 k = isl_basic_set_alloc_inequality(graph->lp);
2144 if (k < 0)
2145 return isl_stat_error;
2146 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2147 isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1)isl_sioimath_set_si((graph->lp->ineq[k][1 + node->start
]), -1)
;
2148 isl_int_set_si(graph->lp->ineq[k][0], max)isl_sioimath_set_si((graph->lp->ineq[k][0]), max);
2149 }
2150
2151 return isl_stat_ok;
2152}
2153
2154/* Count the number of constraints that will be added by
2155 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2156 * accordingly.
2157 *
2158 * In practice, add_bound_coefficient_constraints only adds inequalities.
2159 */
2160static int count_bound_coefficient_constraints(isl_ctx *ctx,
2161 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2162{
2163 int i;
2164
2165 if (isl_options_get_schedule_max_coefficient(ctx) == -1 &&
2166 !isl_options_get_schedule_treat_coalescing(ctx))
2167 return 0;
2168
2169 for (i = 0; i < graph->n; ++i)
2170 *n_ineq += graph->node[i].nparam + 2 * graph->node[i].nvar;
2171
2172 return 0;
2173}
2174
2175/* Add constraints to graph->lp that bound the values of
2176 * the parameter schedule coefficients of "node" to "max" and
2177 * the variable schedule coefficients to the corresponding entry
2178 * in node->max.
2179 * In either case, a negative value means that no bound needs to be imposed.
2180 *
2181 * For parameter coefficients, this amounts to adding a constraint
2182 *
2183 * c_n <= max
2184 *
2185 * i.e.,
2186 *
2187 * -c_n + max >= 0
2188 *
2189 * The variables coefficients are, however, not represented directly.
2190 * Instead, the variables coefficients c_x are written as a linear
2191 * combination c_x = cmap c_z of some other coefficients c_z,
2192 * which are in turn encoded as c_z = c_z^+ - c_z^-.
2193 * Let a_j be the elements of row i of node->cmap, then
2194 *
2195 * -max_i <= c_x_i <= max_i
2196 *
2197 * is encoded as
2198 *
2199 * -max_i <= \sum_j a_j (c_z_j^+ - c_z_j^-) <= max_i
2200 *
2201 * or
2202 *
2203 * -\sum_j a_j (c_z_j^+ - c_z_j^-) + max_i >= 0
2204 * \sum_j a_j (c_z_j^+ - c_z_j^-) + max_i >= 0
2205 */
2206static isl_stat node_add_coefficient_constraints(isl_ctx *ctx,
2207 struct isl_sched_graph *graph, struct isl_sched_node *node, int max)
2208{
2209 int i, j, k;
2210 int total;
2211 isl_vec *ineq;
2212
2213 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2214
2215 for (j = 0; j < node->nparam; ++j) {
2216 int dim;
2217
2218 if (max < 0)
2219 continue;
2220
2221 k = isl_basic_set_alloc_inequality(graph->lp);
2222 if (k < 0)
2223 return isl_stat_error;
2224 dim = 1 + node->start + 1 + j;
2225 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2226 isl_int_set_si(graph->lp->ineq[k][dim], -1)isl_sioimath_set_si((graph->lp->ineq[k][dim]), -1);
2227 isl_int_set_si(graph->lp->ineq[k][0], max)isl_sioimath_set_si((graph->lp->ineq[k][0]), max);
2228 }
2229
2230 ineq = isl_vec_alloc(ctx, 1 + total);
2231 ineq = isl_vec_clr(ineq);
2232 if (!ineq)
2233 return isl_stat_error;
2234 for (i = 0; i < node->nvar; ++i) {
2235 int pos = 1 + node_var_coef_offset(node);
2236
2237 if (isl_int_is_neg(node->max->el[i])(isl_sioimath_sgn(*(node->max->el[i])) < 0))
2238 continue;
2239
2240 for (j = 0; j < node->nvar; ++j) {
2241 isl_int_set(ineq->el[pos + 2 * j],isl_sioimath_set((ineq->el[pos + 2 * j]), *(node->cmap->
row[i][j]))
2242 node->cmap->row[i][j])isl_sioimath_set((ineq->el[pos + 2 * j]), *(node->cmap->
row[i][j]))
;
2243 isl_int_neg(ineq->el[pos + 2 * j + 1],isl_sioimath_neg((ineq->el[pos + 2 * j + 1]), *(node->cmap
->row[i][j]))
2244 node->cmap->row[i][j])isl_sioimath_neg((ineq->el[pos + 2 * j + 1]), *(node->cmap
->row[i][j]))
;
2245 }
2246 isl_int_set(ineq->el[0], node->max->el[i])isl_sioimath_set((ineq->el[0]), *(node->max->el[i]));
2247
2248 k = isl_basic_set_alloc_inequality(graph->lp);
2249 if (k < 0)
2250 goto error;
2251 isl_seq_cpy(graph->lp->ineq[k], ineq->el, 1 + total);
2252
2253 isl_seq_neg(ineq->el + pos, ineq->el + pos, 2 * node->nvar);
2254 k = isl_basic_set_alloc_inequality(graph->lp);
2255 if (k < 0)
2256 goto error;
2257 isl_seq_cpy(graph->lp->ineq[k], ineq->el, 1 + total);
2258 }
2259 isl_vec_free(ineq);
2260
2261 return isl_stat_ok;
2262error:
2263 isl_vec_free(ineq);
2264 return isl_stat_error;
2265}
2266
2267/* Add constraints that bound the values of the variable and parameter
2268 * coefficients of the schedule.
2269 *
2270 * The maximal value of the coefficients is defined by the option
2271 * 'schedule_max_coefficient' and the entries in node->max.
2272 * These latter entries are only set if either the schedule_max_coefficient
2273 * option or the schedule_treat_coalescing option is set.
2274 */
2275static isl_stat add_bound_coefficient_constraints(isl_ctx *ctx,
2276 struct isl_sched_graph *graph)
2277{
2278 int i;
2279 int max;
2280
2281 max = isl_options_get_schedule_max_coefficient(ctx);
2282
2283 if (max == -1 && !isl_options_get_schedule_treat_coalescing(ctx))
2284 return isl_stat_ok;
2285
2286 for (i = 0; i < graph->n; ++i) {
2287 struct isl_sched_node *node = &graph->node[i];
2288
2289 if (node_add_coefficient_constraints(ctx, graph, node, max) < 0)
2290 return isl_stat_error;
2291 }
2292
2293 return isl_stat_ok;
2294}
2295
2296/* Add a constraint to graph->lp that equates the value at position
2297 * "sum_pos" to the sum of the "n" values starting at "first".
2298 */
2299static isl_stat add_sum_constraint(struct isl_sched_graph *graph,
2300 int sum_pos, int first, int n)
2301{
2302 int i, k;
2303 int total;
2304
2305 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2306
2307 k = isl_basic_set_alloc_equality(graph->lp);
2308 if (k < 0)
2309 return isl_stat_error;
2310 isl_seq_clr(graph->lp->eq[k], 1 + total);
2311 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1)isl_sioimath_set_si((graph->lp->eq[k][1 + sum_pos]), -1
)
;
2312 for (i = 0; i < n; ++i)
2313 isl_int_set_si(graph->lp->eq[k][1 + first + i], 1)isl_sioimath_set_si((graph->lp->eq[k][1 + first + i]), 1
)
;
2314
2315 return isl_stat_ok;
2316}
2317
2318/* Add a constraint to graph->lp that equates the value at position
2319 * "sum_pos" to the sum of the parameter coefficients of all nodes.
2320 *
2321 * Within each node, the coefficients have the following order:
2322 * - c_i_0
2323 * - c_i_n (if parametric)
2324 * - positive and negative parts of c_i_x
2325 */
2326static isl_stat add_param_sum_constraint(struct isl_sched_graph *graph,
2327 int sum_pos)
2328{
2329 int i, j, k;
2330 int total;
2331
2332 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2333
2334 k = isl_basic_set_alloc_equality(graph->lp);
2335 if (k < 0)
2336 return isl_stat_error;
2337 isl_seq_clr(graph->lp->eq[k], 1 + total);
2338 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1)isl_sioimath_set_si((graph->lp->eq[k][1 + sum_pos]), -1
)
;
2339 for (i = 0; i < graph->n; ++i) {
2340 int pos = 1 + graph->node[i].start + 1;
2341
2342 for (j = 0; j < graph->node[i].nparam; ++j)
2343 isl_int_set_si(graph->lp->eq[k][pos + j], 1)isl_sioimath_set_si((graph->lp->eq[k][pos + j]), 1);
2344 }
2345
2346 return isl_stat_ok;
2347}
2348
2349/* Add a constraint to graph->lp that equates the value at position
2350 * "sum_pos" to the sum of the variable coefficients of all nodes.
2351 *
2352 * Within each node, the coefficients have the following order:
2353 * - c_i_0
2354 * - c_i_n (if parametric)
2355 * - positive and negative parts of c_i_x
2356 */
2357static isl_stat add_var_sum_constraint(struct isl_sched_graph *graph,
2358 int sum_pos)
2359{
2360 int i, j, k;
2361 int total;
2362
2363 total = isl_basic_set_dim(graph->lp, isl_dim_set);
2364
2365 k = isl_basic_set_alloc_equality(graph->lp);
2366 if (k < 0)
2367 return isl_stat_error;
2368 isl_seq_clr(graph->lp->eq[k], 1 + total);
2369 isl_int_set_si(graph->lp->eq[k][1 + sum_pos], -1)isl_sioimath_set_si((graph->lp->eq[k][1 + sum_pos]), -1
)
;
2370 for (i = 0; i < graph->n; ++i) {
2371 struct isl_sched_node *node = &graph->node[i];
2372 int pos = 1 + node_var_coef_offset(node);
2373
2374 for (j = 0; j < 2 * node->nvar; ++j)
2375 isl_int_set_si(graph->lp->eq[k][pos + j], 1)isl_sioimath_set_si((graph->lp->eq[k][pos + j]), 1);
2376 }
2377
2378 return isl_stat_ok;
2379}
2380
2381/* Construct an ILP problem for finding schedule coefficients
2382 * that result in non-negative, but small dependence distances
2383 * over all dependences.
2384 * In particular, the dependence distances over proximity edges
2385 * are bounded by m_0 + m_n n and we compute schedule coefficients
2386 * with small values (preferably zero) of m_n and m_0.
2387 *
2388 * All variables of the ILP are non-negative. The actual coefficients
2389 * may be negative, so each coefficient is represented as the difference
2390 * of two non-negative variables. The negative part always appears
2391 * immediately before the positive part.
2392 * Other than that, the variables have the following order
2393 *
2394 * - sum of positive and negative parts of m_n coefficients
2395 * - m_0
2396 * - sum of all c_n coefficients
2397 * (unconstrained when computing non-parametric schedules)
2398 * - sum of positive and negative parts of all c_x coefficients
2399 * - positive and negative parts of m_n coefficients
2400 * - for each node
2401 * - c_i_0
2402 * - c_i_n (if parametric)
2403 * - positive and negative parts of c_i_x
2404 *
2405 * The c_i_x are not represented directly, but through the columns of
2406 * node->cmap. That is, the computed values are for variable t_i_x
2407 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2408 *
2409 * The constraints are those from the edges plus two or three equalities
2410 * to express the sums.
2411 *
2412 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2413 * Otherwise, we ignore them.
2414 */
2415static isl_stat setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
2416 int use_coincidence)
2417{
2418 int i;
2419 unsigned nparam;
2420 unsigned total;
2421 isl_space *space;
2422 int parametric;
2423 int param_pos;
2424 int n_eq, n_ineq;
2425
2426 parametric = ctx->opt->schedule_parametric;
2427 nparam = isl_space_dim(graph->node[0].space, isl_dim_param);
2428 param_pos = 4;
2429 total = param_pos + 2 * nparam;
2430 for (i = 0; i < graph->n; ++i) {
2431 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2432 if (node_update_cmap(node) < 0)
2433 return isl_stat_error;
2434 node->start = total;
2435 total += 1 + node->nparam + 2 * node->nvar;
2436 }
2437
2438 if (count_constraints(graph, &n_eq, &n_ineq, use_coincidence) < 0)
2439 return isl_stat_error;
2440 if (count_bound_constant_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2441 return isl_stat_error;
2442 if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2443 return isl_stat_error;
2444
2445 space = isl_space_set_alloc(ctx, 0, total);
2446 isl_basic_set_free(graph->lp);
2447 n_eq += 2 + parametric;
2448
2449 graph->lp = isl_basic_set_alloc_space(space, 0, n_eq, n_ineq);
2450
2451 if (add_sum_constraint(graph, 0, param_pos, 2 * nparam) < 0)
2452 return isl_stat_error;
2453 if (parametric && add_param_sum_constraint(graph, 2) < 0)
2454 return isl_stat_error;
2455 if (add_var_sum_constraint(graph, 3) < 0)
2456 return isl_stat_error;
2457 if (add_bound_constant_constraints(ctx, graph) < 0)
2458 return isl_stat_error;
2459 if (add_bound_coefficient_constraints(ctx, graph) < 0)
2460 return isl_stat_error;
2461 if (add_all_validity_constraints(graph, use_coincidence) < 0)
2462 return isl_stat_error;
2463 if (add_all_proximity_constraints(graph, use_coincidence) < 0)
2464 return isl_stat_error;
2465
2466 return isl_stat_ok;
2467}
2468
2469/* Analyze the conflicting constraint found by
2470 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2471 * constraint of one of the edges between distinct nodes, living, moreover
2472 * in distinct SCCs, then record the source and sink SCC as this may
2473 * be a good place to cut between SCCs.
2474 */
2475static int check_conflict(int con, void *user)
2476{
2477 int i;
2478 struct isl_sched_graph *graph = user;
2479
2480 if (graph->src_scc >= 0)
2481 return 0;
2482
2483 con -= graph->lp->n_eq;
2484
2485 if (con >= graph->lp->n_ineq)
2486 return 0;
2487
2488 for (i = 0; i < graph->n_edge; ++i) {
2489 if (!is_validity(&graph->edge[i]))
2490 continue;
2491 if (graph->edge[i].src == graph->edge[i].dst)
2492 continue;
2493 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
2494 continue;
2495 if (graph->edge[i].start > con)
2496 continue;
2497 if (graph->edge[i].end <= con)
2498 continue;
2499 graph->src_scc = graph->edge[i].src->scc;
2500 graph->dst_scc = graph->edge[i].dst->scc;
2501 }
2502
2503 return 0;
2504}
2505
2506/* Check whether the next schedule row of the given node needs to be
2507 * non-trivial. Lower-dimensional domains may have some trivial rows,
2508 * but as soon as the number of remaining required non-trivial rows
2509 * is as large as the number or remaining rows to be computed,
2510 * all remaining rows need to be non-trivial.
2511 */
2512static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
2513{
2514 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
2515}
2516
2517/* Solve the ILP problem constructed in setup_lp.
2518 * For each node such that all the remaining rows of its schedule
2519 * need to be non-trivial, we construct a non-triviality region.
2520 * This region imposes that the next row is independent of previous rows.
2521 * In particular the coefficients c_i_x are represented by t_i_x
2522 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2523 * its first columns span the rows of the previously computed part
2524 * of the schedule. The non-triviality region enforces that at least
2525 * one of the remaining components of t_i_x is non-zero, i.e.,
2526 * that the new schedule row depends on at least one of the remaining
2527 * columns of Q.
2528 */
2529static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
2530{
2531 int i;
2532 isl_vec *sol;
2533 isl_basic_setisl_basic_map *lp;
2534
2535 for (i = 0; i < graph->n; ++i) {
2536 struct isl_sched_node *node = &graph->node[i];
2537 int skip = node->rank;
2538 graph->region[i].pos = node_var_coef_offset(node) + 2 * skip;
2539 if (needs_row(graph, node))
2540 graph->region[i].len = 2 * (node->nvar - skip);
2541 else
2542 graph->region[i].len = 0;
2543 }
2544 lp = isl_basic_set_copy(graph->lp);
2545 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
2546 graph->region, &check_conflict, graph);
2547 return sol;
2548}
2549
2550/* Extract the coefficients for the variables of "node" from "sol".
2551 *
2552 * Within each node, the coefficients have the following order:
2553 * - c_i_0
2554 * - c_i_n (if parametric)
2555 * - positive and negative parts of c_i_x
2556 *
2557 * The c_i_x^- appear before their c_i_x^+ counterpart.
2558 *
2559 * Return c_i_x = c_i_x^+ - c_i_x^-
2560 */
2561static __isl_give isl_vec *extract_var_coef(struct isl_sched_node *node,
2562 __isl_keep isl_vec *sol)
2563{
2564 int i;
2565 int pos;
2566 isl_vec *csol;
2567
2568 if (!sol)
2569 return NULL((void*)0);
2570 csol = isl_vec_alloc(isl_vec_get_ctx(sol), node->nvar);
2571 if (!csol)
2572 return NULL((void*)0);
2573
2574 pos = 1 + node_var_coef_offset(node);
2575 for (i = 0; i < node->nvar; ++i)
2576 isl_int_sub(csol->el[i],isl_sioimath_sub((csol->el[i]), *(sol->el[pos + 2 * i +
1]), *(sol->el[pos + 2 * i]))
2577 sol->el[pos + 2 * i + 1], sol->el[pos + 2 * i])isl_sioimath_sub((csol->el[i]), *(sol->el[pos + 2 * i +
1]), *(sol->el[pos + 2 * i]))
;
2578
2579 return csol;
2580}
2581
2582/* Update the schedules of all nodes based on the given solution
2583 * of the LP problem.
2584 * The new row is added to the current band.
2585 * All possibly negative coefficients are encoded as a difference
2586 * of two non-negative variables, so we need to perform the subtraction
2587 * here. Moreover, if use_cmap is set, then the solution does
2588 * not refer to the actual coefficients c_i_x, but instead to variables
2589 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2590 * In this case, we then also need to perform this multiplication
2591 * to obtain the values of c_i_x.
2592 *
2593 * If coincident is set, then the caller guarantees that the new
2594 * row satisfies the coincidence constraints.
2595 */
2596static int update_schedule(struct isl_sched_graph *graph,
2597 __isl_take isl_vec *sol, int use_cmap, int coincident)
2598{
2599 int i, j;
2600 isl_vec *csol = NULL((void*)0);
2601
2602 if (!sol)
2603 goto error;
2604 if (sol->size == 0)
2605 isl_die(sol->ctx, isl_error_internal,do { isl_handle_error(sol->ctx, isl_error_internal, "no solution found"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 2606); goto error; } while (0)
2606 "no solution found", goto error)do { isl_handle_error(sol->ctx, isl_error_internal, "no solution found"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 2606); goto error; } while (0)
;
2607 if (graph->n_total_row >= graph->max_row)
2608 isl_die(sol->ctx, isl_error_internal,do { isl_handle_error(sol->ctx, isl_error_internal, "too many schedule rows"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 2609); goto error; } while (0)
2609 "too many schedule rows", goto error)do { isl_handle_error(sol->ctx, isl_error_internal, "too many schedule rows"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 2609); goto error; } while (0)
;
2610
2611 for (i = 0; i < graph->n; ++i) {
2612 struct isl_sched_node *node = &graph->node[i];
2613 int pos = node->start;
2614 int row = isl_mat_rows(node->sched);
2615
2616 isl_vec_free(csol);
2617 csol = extract_var_coef(node, sol);
2618 if (!csol)
2619 goto error;
2620
2621 isl_map_free(node->sched_map);
2622 node->sched_map = NULL((void*)0);
2623 node->sched = isl_mat_add_rows(node->sched, 1);
2624 if (!node->sched)
2625 goto error;
2626 for (j = 0; j < 1 + node->nparam; ++j)
2627 node->sched = isl_mat_set_element(node->sched,
2628 row, j, sol->el[1 + pos + j]);
2629 if (use_cmap)
2630 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
2631 csol);
2632 if (!csol)
2633 goto error;
2634 for (j = 0; j < node->nvar; ++j)
2635 node->sched = isl_mat_set_element(node->sched,
2636 row, 1 + node->nparam + j, csol->el[j]);
2637 node->coincident[graph->n_total_row] = coincident;
2638 }
2639 isl_vec_free(sol);
2640 isl_vec_free(csol);
2641
2642 graph->n_row++;
2643 graph->n_total_row++;
2644
2645 return 0;
2646error:
2647 isl_vec_free(sol);
2648 isl_vec_free(csol);
2649 return -1;
2650}
2651
2652/* Convert row "row" of node->sched into an isl_aff living in "ls"
2653 * and return this isl_aff.
2654 */
2655static __isl_give isl_aff *extract_schedule_row(__isl_take isl_local_space *ls,
2656 struct isl_sched_node *node, int row)
2657{
2658 int j;
2659 isl_int v;
2660 isl_aff *aff;
2661
2662 isl_int_init(v)isl_sioimath_init((v));
2663
2664 aff = isl_aff_zero_on_domain(ls);
2665 isl_mat_get_element(node->sched, row, 0, &v);
2666 aff = isl_aff_set_constant(aff, v);
2667 for (j = 0; j < node->nparam; ++j) {
2668 isl_mat_get_element(node->sched, row, 1 + j, &v);
2669 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
2670 }
2671 for (j = 0; j < node->nvar; ++j) {
2672 isl_mat_get_element(node->sched, row, 1 + node->nparam + j, &v);
2673 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
2674 }
2675
2676 isl_int_clear(v)isl_sioimath_clear((v));
2677
2678 return aff;
2679}
2680
2681/* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2682 * and return this multi_aff.
2683 *
2684 * The result is defined over the uncompressed node domain.
2685 */
2686static __isl_give isl_multi_aff *node_extract_partial_schedule_multi_aff(
2687 struct isl_sched_node *node, int first, int n)
2688{
2689 int i;
2690 isl_space *space;
2691 isl_local_space *ls;
2692 isl_aff *aff;
2693 isl_multi_aff *ma;
2694 int nrow;
2695
2696 if (!node)
2697 return NULL((void*)0);
2698 nrow = isl_mat_rows(node->sched);
Value stored to 'nrow' is never read
2699 if (node->compressed)
2700 space = isl_multi_aff_get_domain_space(node->decompress);
2701 else
2702 space = isl_space_copy(node->space);
2703 ls = isl_local_space_from_space(isl_space_copy(space));
2704 space = isl_space_from_domain(space);
2705 space = isl_space_add_dims(space, isl_dim_out, n);
2706 ma = isl_multi_aff_zero(space);
2707
2708 for (i = first; i < first + n; ++i) {
2709 aff = extract_schedule_row(isl_local_space_copy(ls), node, i);
2710 ma = isl_multi_aff_set_aff(ma, i - first, aff);
2711 }
2712
2713 isl_local_space_free(ls);
2714
2715 if (node->compressed)
2716 ma = isl_multi_aff_pullback_multi_aff(ma,
2717 isl_multi_aff_copy(node->compress));
2718
2719 return ma;
2720}
2721
2722/* Convert node->sched into a multi_aff and return this multi_aff.
2723 *
2724 * The result is defined over the uncompressed node domain.
2725 */
2726static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
2727 struct isl_sched_node *node)
2728{
2729 int nrow;
2730
2731 nrow = isl_mat_rows(node->sched);
2732 return node_extract_partial_schedule_multi_aff(node, 0, nrow);
2733}
2734
2735/* Convert node->sched into a map and return this map.
2736 *
2737 * The result is cached in node->sched_map, which needs to be released
2738 * whenever node->sched is updated.
2739 * It is defined over the uncompressed node domain.
2740 */
2741static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
2742{
2743 if (!node->sched_map) {
2744 isl_multi_aff *ma;
2745
2746 ma = node_extract_schedule_multi_aff(node);
2747 node->sched_map = isl_map_from_multi_aff(ma);
2748 }
2749
2750 return isl_map_copy(node->sched_map);
2751}
2752
2753/* Construct a map that can be used to update a dependence relation
2754 * based on the current schedule.
2755 * That is, construct a map expressing that source and sink
2756 * are executed within the same iteration of the current schedule.
2757 * This map can then be intersected with the dependence relation.
2758 * This is not the most efficient way, but this shouldn't be a critical
2759 * operation.
2760 */
2761static __isl_give isl_map *specializer(struct isl_sched_node *src,
2762 struct isl_sched_node *dst)
2763{
2764 isl_map *src_sched, *dst_sched;
2765
2766 src_sched = node_extract_schedule(src);
2767 dst_sched = node_extract_schedule(dst);
2768 return isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
2769}
2770
2771/* Intersect the domains of the nested relations in domain and range
2772 * of "umap" with "map".
2773 */
2774static __isl_give isl_union_map *intersect_domains(
2775 __isl_take isl_union_map *umap, __isl_keep isl_map *map)
2776{
2777 isl_union_set *uset;
2778
2779 umap = isl_union_map_zip(umap);
2780 uset = isl_union_set_from_set(isl_map_wrap(isl_map_copy(map)));
2781 umap = isl_union_map_intersect_domain(umap, uset);
2782 umap = isl_union_map_zip(umap);
2783 return umap;
2784}
2785
2786/* Update the dependence relation of the given edge based
2787 * on the current schedule.
2788 * If the dependence is carried completely by the current schedule, then
2789 * it is removed from the edge_tables. It is kept in the list of edges
2790 * as otherwise all edge_tables would have to be recomputed.
2791 */
2792static int update_edge(struct isl_sched_graph *graph,
2793 struct isl_sched_edge *edge)
2794{
2795 int empty;
2796 isl_map *id;
2797
2798 id = specializer(edge->src, edge->dst);
2799 edge->map = isl_map_intersect(edge->map, isl_map_copy(id));
2800 if (!edge->map)
2801 goto error;
2802
2803 if (edge->tagged_condition) {
2804 edge->tagged_condition =
2805 intersect_domains(edge->tagged_condition, id);
2806 if (!edge->tagged_condition)
2807 goto error;
2808 }
2809 if (edge->tagged_validity) {
2810 edge->tagged_validity =
2811 intersect_domains(edge->tagged_validity, id);
2812 if (!edge->tagged_validity)
2813 goto error;
2814 }
2815
2816 empty = isl_map_plain_is_empty(edge->map);
2817 if (empty < 0)
2818 goto error;
2819 if (empty)
2820 graph_remove_edge(graph, edge);
2821
2822 isl_map_free(id);
2823 return 0;
2824error:
2825 isl_map_free(id);
2826 return -1;
2827}
2828
2829/* Does the domain of "umap" intersect "uset"?
2830 */
2831static int domain_intersects(__isl_keep isl_union_map *umap,
2832 __isl_keep isl_union_set *uset)
2833{
2834 int empty;
2835
2836 umap = isl_union_map_copy(umap);
2837 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(uset));
2838 empty = isl_union_map_is_empty(umap);
2839 isl_union_map_free(umap);
2840
2841 return empty < 0 ? -1 : !empty;
2842}
2843
2844/* Does the range of "umap" intersect "uset"?
2845 */
2846static int range_intersects(__isl_keep isl_union_map *umap,
2847 __isl_keep isl_union_set *uset)
2848{
2849 int empty;
2850
2851 umap = isl_union_map_copy(umap);
2852 umap = isl_union_map_intersect_range(umap, isl_union_set_copy(uset));
2853 empty = isl_union_map_is_empty(umap);
2854 isl_union_map_free(umap);
2855
2856 return empty < 0 ? -1 : !empty;
2857}
2858
2859/* Are the condition dependences of "edge" local with respect to
2860 * the current schedule?
2861 *
2862 * That is, are domain and range of the condition dependences mapped
2863 * to the same point?
2864 *
2865 * In other words, is the condition false?
2866 */
2867static int is_condition_false(struct isl_sched_edge *edge)
2868{
2869 isl_union_map *umap;
2870 isl_map *map, *sched, *test;
2871 int empty, local;
2872
2873 empty = isl_union_map_is_empty(edge->tagged_condition);
2874 if (empty < 0 || empty)
2875 return empty;
2876
2877 umap = isl_union_map_copy(edge->tagged_condition);
2878 umap = isl_union_map_zip(umap);
2879 umap = isl_union_set_unwrap(isl_union_map_domain(umap));
2880 map = isl_map_from_union_map(umap);
2881
2882 sched = node_extract_schedule(edge->src);
2883 map = isl_map_apply_domain(map, sched);
2884 sched = node_extract_schedule(edge->dst);
2885 map = isl_map_apply_range(map, sched);
2886
2887 test = isl_map_identity(isl_map_get_space(map));
2888 local = isl_map_is_subset(map, test);
2889 isl_map_free(map);
2890 isl_map_free(test);
2891
2892 return local;
2893}
2894
2895/* For each conditional validity constraint that is adjacent
2896 * to a condition with domain in condition_source or range in condition_sink,
2897 * turn it into an unconditional validity constraint.
2898 */
2899static int unconditionalize_adjacent_validity(struct isl_sched_graph *graph,
2900 __isl_take isl_union_set *condition_source,
2901 __isl_take isl_union_set *condition_sink)
2902{
2903 int i;
2904
2905 condition_source = isl_union_set_coalesce(condition_source);
2906 condition_sink = isl_union_set_coalesce(condition_sink);
2907
2908 for (i = 0; i < graph->n_edge; ++i) {
2909 int adjacent;
2910 isl_union_map *validity;
2911
2912 if (!is_conditional_validity(&graph->edge[i]))
2913 continue;
2914 if (is_validity(&graph->edge[i]))
2915 continue;
2916
2917 validity = graph->edge[i].tagged_validity;
2918 adjacent = domain_intersects(validity, condition_sink);
2919 if (adjacent >= 0 && !adjacent)
2920 adjacent = range_intersects(validity, condition_source);
2921 if (adjacent < 0)
2922 goto error;
2923 if (!adjacent)
2924 continue;
2925
2926 set_validity(&graph->edge[i]);
2927 }
2928
2929 isl_union_set_free(condition_source);
2930 isl_union_set_free(condition_sink);
2931 return 0;
2932error:
2933 isl_union_set_free(condition_source);
2934 isl_union_set_free(condition_sink);
2935 return -1;
2936}
2937
2938/* Update the dependence relations of all edges based on the current schedule
2939 * and enforce conditional validity constraints that are adjacent
2940 * to satisfied condition constraints.
2941 *
2942 * First check if any of the condition constraints are satisfied
2943 * (i.e., not local to the outer schedule) and keep track of
2944 * their domain and range.
2945 * Then update all dependence relations (which removes the non-local
2946 * constraints).
2947 * Finally, if any condition constraints turned out to be satisfied,
2948 * then turn all adjacent conditional validity constraints into
2949 * unconditional validity constraints.
2950 */
2951static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
2952{
2953 int i;
2954 int any = 0;
2955 isl_union_set *source, *sink;
2956
2957 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
2958 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
2959 for (i = 0; i < graph->n_edge; ++i) {
2960 int local;
2961 isl_union_set *uset;
2962 isl_union_map *umap;
2963
2964 if (!is_condition(&graph->edge[i]))
2965 continue;
2966 if (is_local(&graph->edge[i]))
2967 continue;
2968 local = is_condition_false(&graph->edge[i]);
2969 if (local < 0)
2970 goto error;
2971 if (local)
2972 continue;
2973
2974 any = 1;
2975
2976 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
2977 uset = isl_union_map_domain(umap);
2978 source = isl_union_set_union(source, uset);
2979
2980 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
2981 uset = isl_union_map_range(umap);
2982 sink = isl_union_set_union(sink, uset);
2983 }
2984
2985 for (i = graph->n_edge - 1; i >= 0; --i) {
2986 if (update_edge(graph, &graph->edge[i]) < 0)
2987 goto error;
2988 }
2989
2990 if (any)
2991 return unconditionalize_adjacent_validity(graph, source, sink);
2992
2993 isl_union_set_free(source);
2994 isl_union_set_free(sink);
2995 return 0;
2996error:
2997 isl_union_set_free(source);
2998 isl_union_set_free(sink);
2999 return -1;
3000}
3001
3002static void next_band(struct isl_sched_graph *graph)
3003{
3004 graph->band_start = graph->n_total_row;
3005}
3006
3007/* Return the union of the universe domains of the nodes in "graph"
3008 * that satisfy "pred".
3009 */
3010static __isl_give isl_union_set *isl_sched_graph_domain(isl_ctx *ctx,
3011 struct isl_sched_graph *graph,
3012 int (*pred)(struct isl_sched_node *node, int data), int data)
3013{
3014 int i;
3015 isl_setisl_map *set;
3016 isl_union_set *dom;
3017
3018 for (i = 0; i < graph->n; ++i)
3019 if (pred(&graph->node[i], data))
3020 break;
3021
3022 if (i >= graph->n)
3023 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "empty component"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3024); return ((void*)0); } while (0)
3024 "empty component", return NULL)do { isl_handle_error(ctx, isl_error_internal, "empty component"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3024); return ((void*)0); } while (0)
;
3025
3026 set = isl_set_universe(isl_space_copy(graph->node[i].space));
3027 dom = isl_union_set_from_set(set);
3028
3029 for (i = i + 1; i < graph->n; ++i) {
3030 if (!pred(&graph->node[i], data))
3031 continue;
3032 set = isl_set_universe(isl_space_copy(graph->node[i].space));
3033 dom = isl_union_set_union(dom, isl_union_set_from_set(set));
3034 }
3035
3036 return dom;
3037}
3038
3039/* Return a list of unions of universe domains, where each element
3040 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
3041 */
3042static __isl_give isl_union_set_list *extract_sccs(isl_ctx *ctx,
3043 struct isl_sched_graph *graph)
3044{
3045 int i;
3046 isl_union_set_list *filters;
3047
3048 filters = isl_union_set_list_alloc(ctx, graph->scc);
3049 for (i = 0; i < graph->scc; ++i) {
3050 isl_union_set *dom;
3051
3052 dom = isl_sched_graph_domain(ctx, graph, &node_scc_exactly, i);
3053 filters = isl_union_set_list_add(filters, dom);
3054 }
3055
3056 return filters;
3057}
3058
3059/* Return a list of two unions of universe domains, one for the SCCs up
3060 * to and including graph->src_scc and another for the other SCCs.
3061 */
3062static __isl_give isl_union_set_list *extract_split(isl_ctx *ctx,
3063 struct isl_sched_graph *graph)
3064{
3065 isl_union_set *dom;
3066 isl_union_set_list *filters;
3067
3068 filters = isl_union_set_list_alloc(ctx, 2);
3069 dom = isl_sched_graph_domain(ctx, graph,
3070 &node_scc_at_most, graph->src_scc);
3071 filters = isl_union_set_list_add(filters, dom);
3072 dom = isl_sched_graph_domain(ctx, graph,
3073 &node_scc_at_least, graph->src_scc + 1);
3074 filters = isl_union_set_list_add(filters, dom);
3075
3076 return filters;
3077}
3078
3079/* Copy nodes that satisfy node_pred from the src dependence graph
3080 * to the dst dependence graph.
3081 */
3082static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
3083 int (*node_pred)(struct isl_sched_node *node, int data), int data)
3084{
3085 int i;
3086
3087 dst->n = 0;
3088 for (i = 0; i < src->n; ++i) {
3089 int j;
3090
3091 if (!node_pred(&src->node[i], data))
3092 continue;
3093
3094 j = dst->n;
3095 dst->node[j].space = isl_space_copy(src->node[i].space);
3096 dst->node[j].compressed = src->node[i].compressed;
3097 dst->node[j].hull = isl_set_copy(src->node[i].hull);
3098 dst->node[j].compress =
3099 isl_multi_aff_copy(src->node[i].compress);
3100 dst->node[j].decompress =
3101 isl_multi_aff_copy(src->node[i].decompress);
3102 dst->node[j].nvar = src->node[i].nvar;
3103 dst->node[j].nparam = src->node[i].nparam;
3104 dst->node[j].sched = isl_mat_copy(src->node[i].sched);
3105 dst->node[j].sched_map = isl_map_copy(src->node[i].sched_map);
3106 dst->node[j].coincident = src->node[i].coincident;
3107 dst->node[j].sizes = isl_multi_val_copy(src->node[i].sizes);
3108 dst->node[j].max = isl_vec_copy(src->node[i].max);
3109 dst->n++;
3110
3111 if (!dst->node[j].space || !dst->node[j].sched)
3112 return -1;
3113 if (dst->node[j].compressed &&
3114 (!dst->node[j].hull || !dst->node[j].compress ||
3115 !dst->node[j].decompress))
3116 return -1;
3117 }
3118
3119 return 0;
3120}
3121
3122/* Copy non-empty edges that satisfy edge_pred from the src dependence graph
3123 * to the dst dependence graph.
3124 * If the source or destination node of the edge is not in the destination
3125 * graph, then it must be a backward proximity edge and it should simply
3126 * be ignored.
3127 */
3128static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
3129 struct isl_sched_graph *src,
3130 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
3131{
3132 int i;
3133 enum isl_edge_type t;
3134
3135 dst->n_edge = 0;
3136 for (i = 0; i < src->n_edge; ++i) {
3137 struct isl_sched_edge *edge = &src->edge[i];
3138 isl_map *map;
3139 isl_union_map *tagged_condition;
3140 isl_union_map *tagged_validity;
3141 struct isl_sched_node *dst_src, *dst_dst;
3142
3143 if (!edge_pred(edge, data))
3144 continue;
3145
3146 if (isl_map_plain_is_empty(edge->map))
3147 continue;
3148
3149 dst_src = graph_find_node(ctx, dst, edge->src->space);
3150 dst_dst = graph_find_node(ctx, dst, edge->dst->space);
3151 if (!dst_src || !dst_dst) {
3152 if (is_validity(edge) || is_conditional_validity(edge))
3153 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "backward (conditional) validity edge"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3155); return -1; } while (0)
3154 "backward (conditional) validity edge",do { isl_handle_error(ctx, isl_error_internal, "backward (conditional) validity edge"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3155); return -1; } while (0)
3155 return -1)do { isl_handle_error(ctx, isl_error_internal, "backward (conditional) validity edge"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3155); return -1; } while (0)
;
3156 continue;
3157 }
3158
3159 map = isl_map_copy(edge->map);
3160 tagged_condition = isl_union_map_copy(edge->tagged_condition);
3161 tagged_validity = isl_union_map_copy(edge->tagged_validity);
3162
3163 dst->edge[dst->n_edge].src = dst_src;
3164 dst->edge[dst->n_edge].dst = dst_dst;
3165 dst->edge[dst->n_edge].map = map;
3166 dst->edge[dst->n_edge].tagged_condition = tagged_condition;
3167 dst->edge[dst->n_edge].tagged_validity = tagged_validity;
3168 dst->edge[dst->n_edge].types = edge->types;
3169 dst->n_edge++;
3170
3171 if (edge->tagged_condition && !tagged_condition)
3172 return -1;
3173 if (edge->tagged_validity && !tagged_validity)
3174 return -1;
3175
3176 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
3177 if (edge !=
3178 graph_find_edge(src, t, edge->src, edge->dst))
3179 continue;
3180 if (graph_edge_table_add(ctx, dst, t,
3181 &dst->edge[dst->n_edge - 1]) < 0)
3182 return -1;
3183 }
3184 }
3185
3186 return 0;
3187}
3188
3189/* Compute the maximal number of variables over all nodes.
3190 * This is the maximal number of linearly independent schedule
3191 * rows that we need to compute.
3192 * Just in case we end up in a part of the dependence graph
3193 * with only lower-dimensional domains, we make sure we will
3194 * compute the required amount of extra linearly independent rows.
3195 */
3196static int compute_maxvar(struct isl_sched_graph *graph)
3197{
3198 int i;
3199
3200 graph->maxvar = 0;
3201 for (i = 0; i < graph->n; ++i) {
3202 struct isl_sched_node *node = &graph->node[i];
3203 int nvar;
3204
3205 if (node_update_cmap(node) < 0)
3206 return -1;
3207 nvar = node->nvar + graph->n_row - node->rank;
3208 if (nvar > graph->maxvar)
3209 graph->maxvar = nvar;
3210 }
3211
3212 return 0;
3213}
3214
3215/* Extract the subgraph of "graph" that consists of the node satisfying
3216 * "node_pred" and the edges satisfying "edge_pred" and store
3217 * the result in "sub".
3218 */
3219static int extract_sub_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
3220 int (*node_pred)(struct isl_sched_node *node, int data),
3221 int (*edge_pred)(struct isl_sched_edge *edge, int data),
3222 int data, struct isl_sched_graph *sub)
3223{
3224 int i, n = 0, n_edge = 0;
3225 int t;
3226
3227 for (i = 0; i < graph->n; ++i)
3228 if (node_pred(&graph->node[i], data))
3229 ++n;
3230 for (i = 0; i < graph->n_edge; ++i)
3231 if (edge_pred(&graph->edge[i], data))
3232 ++n_edge;
3233 if (graph_alloc(ctx, sub, n, n_edge) < 0)
3234 return -1;
3235 if (copy_nodes(sub, graph, node_pred, data) < 0)
3236 return -1;
3237 if (graph_init_table(ctx, sub) < 0)
3238 return -1;
3239 for (t = 0; t <= isl_edge_last; ++t)
3240 sub->max_edge[t] = graph->max_edge[t];
3241 if (graph_init_edge_tables(ctx, sub) < 0)
3242 return -1;
3243 if (copy_edges(ctx, sub, graph, edge_pred, data) < 0)
3244 return -1;
3245 sub->n_row = graph->n_row;
3246 sub->max_row = graph->max_row;
3247 sub->n_total_row = graph->n_total_row;
3248 sub->band_start = graph->band_start;
3249
3250 return 0;
3251}
3252
3253static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
3254 struct isl_sched_graph *graph);
3255static __isl_give isl_schedule_node *compute_schedule_wcc(
3256 isl_schedule_node *node, struct isl_sched_graph *graph);
3257
3258/* Compute a schedule for a subgraph of "graph". In particular, for
3259 * the graph composed of nodes that satisfy node_pred and edges that
3260 * that satisfy edge_pred.
3261 * If the subgraph is known to consist of a single component, then wcc should
3262 * be set and then we call compute_schedule_wcc on the constructed subgraph.
3263 * Otherwise, we call compute_schedule, which will check whether the subgraph
3264 * is connected.
3265 *
3266 * The schedule is inserted at "node" and the updated schedule node
3267 * is returned.
3268 */
3269static __isl_give isl_schedule_node *compute_sub_schedule(
3270 __isl_take isl_schedule_node *node, isl_ctx *ctx,
3271 struct isl_sched_graph *graph,
3272 int (*node_pred)(struct isl_sched_node *node, int data),
3273 int (*edge_pred)(struct isl_sched_edge *edge, int data),
3274 int data, int wcc)
3275{
3276 struct isl_sched_graph split = { 0 };
3277
3278 if (extract_sub_graph(ctx, graph, node_pred, edge_pred, data,
3279 &split) < 0)
3280 goto error;
3281
3282 if (wcc)
3283 node = compute_schedule_wcc(node, &split);
3284 else
3285 node = compute_schedule(node, &split);
3286
3287 graph_free(ctx, &split);
3288 return node;
3289error:
3290 graph_free(ctx, &split);
3291 return isl_schedule_node_free(node);
3292}
3293
3294static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
3295{
3296 return edge->src->scc == scc && edge->dst->scc == scc;
3297}
3298
3299static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
3300{
3301 return edge->dst->scc <= scc;
3302}
3303
3304static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
3305{
3306 return edge->src->scc >= scc;
3307}
3308
3309/* Reset the current band by dropping all its schedule rows.
3310 */
3311static int reset_band(struct isl_sched_graph *graph)
3312{
3313 int i;
3314 int drop;
3315
3316 drop = graph->n_total_row - graph->band_start;
3317 graph->n_total_row -= drop;
3318 graph->n_row -= drop;
3319
3320 for (i = 0; i < graph->n; ++i) {
3321 struct isl_sched_node *node = &graph->node[i];
3322
3323 isl_map_free(node->sched_map);
3324 node->sched_map = NULL((void*)0);
3325
3326 node->sched = isl_mat_drop_rows(node->sched,
3327 graph->band_start, drop);
3328
3329 if (!node->sched)
3330 return -1;
3331 }
3332
3333 return 0;
3334}
3335
3336/* Split the current graph into two parts and compute a schedule for each
3337 * part individually. In particular, one part consists of all SCCs up
3338 * to and including graph->src_scc, while the other part contains the other
3339 * SCCs. The split is enforced by a sequence node inserted at position "node"
3340 * in the schedule tree. Return the updated schedule node.
3341 * If either of these two parts consists of a sequence, then it is spliced
3342 * into the sequence containing the two parts.
3343 *
3344 * The current band is reset. It would be possible to reuse
3345 * the previously computed rows as the first rows in the next
3346 * band, but recomputing them may result in better rows as we are looking
3347 * at a smaller part of the dependence graph.
3348 */
3349static __isl_give isl_schedule_node *compute_split_schedule(
3350 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3351{
3352 int is_seq;
3353 isl_ctx *ctx;
3354 isl_union_set_list *filters;
3355
3356 if (!node)
3357 return NULL((void*)0);
3358
3359 if (reset_band(graph) < 0)
3360 return isl_schedule_node_free(node);
3361
3362 next_band(graph);
3363
3364 ctx = isl_schedule_node_get_ctx(node);
3365 filters = extract_split(ctx, graph);
3366 node = isl_schedule_node_insert_sequence(node, filters);
3367 node = isl_schedule_node_child(node, 1);
3368 node = isl_schedule_node_child(node, 0);
3369
3370 node = compute_sub_schedule(node, ctx, graph,
3371 &node_scc_at_least, &edge_src_scc_at_least,
3372 graph->src_scc + 1, 0);
3373 is_seq = isl_schedule_node_get_type(node) == isl_schedule_node_sequence;
3374 node = isl_schedule_node_parent(node);
3375 node = isl_schedule_node_parent(node);
3376 if (is_seq)
3377 node = isl_schedule_node_sequence_splice_child(node, 1);
3378 node = isl_schedule_node_child(node, 0);
3379 node = isl_schedule_node_child(node, 0);
3380 node = compute_sub_schedule(node, ctx, graph,
3381 &node_scc_at_most, &edge_dst_scc_at_most,
3382 graph->src_scc, 0);
3383 is_seq = isl_schedule_node_get_type(node) == isl_schedule_node_sequence;
3384 node = isl_schedule_node_parent(node);
3385 node = isl_schedule_node_parent(node);
3386 if (is_seq)
3387 node = isl_schedule_node_sequence_splice_child(node, 0);
3388
3389 return node;
3390}
3391
3392/* Insert a band node at position "node" in the schedule tree corresponding
3393 * to the current band in "graph". Mark the band node permutable
3394 * if "permutable" is set.
3395 * The partial schedules and the coincidence property are extracted
3396 * from the graph nodes.
3397 * Return the updated schedule node.
3398 */
3399static __isl_give isl_schedule_node *insert_current_band(
3400 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
3401 int permutable)
3402{
3403 int i;
3404 int start, end, n;
3405 isl_multi_aff *ma;
3406 isl_multi_pw_aff *mpa;
3407 isl_multi_union_pw_aff *mupa;
3408
3409 if (!node)
3410 return NULL((void*)0);
3411
3412 if (graph->n < 1)
3413 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_internal
, "graph should have at least one node", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3415); return isl_schedule_node_free(node); } while (0)
3414 "graph should have at least one node",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_internal
, "graph should have at least one node", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3415); return isl_schedule_node_free(node); } while (0)
3415 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_internal
, "graph should have at least one node", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 3415); return isl_schedule_node_free(node); } while (0)
;
3416
3417 start = graph->band_start;
3418 end = graph->n_total_row;
3419 n = end - start;
3420
3421 ma = node_extract_partial_schedule_multi_aff(&graph->node[0], start, n);
3422 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3423 mupa = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3424
3425 for (i = 1; i < graph->n; ++i) {
3426 isl_multi_union_pw_aff *mupa_i;
3427
3428 ma = node_extract_partial_schedule_multi_aff(&graph->node[i],
3429 start, n);
3430 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3431 mupa_i = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3432 mupa = isl_multi_union_pw_aff_union_add(mupa, mupa_i);
3433 }
3434 node = isl_schedule_node_insert_partial_schedule(node, mupa);
3435
3436 for (i = 0; i < n; ++i)
3437 node = isl_schedule_node_band_member_set_coincident(node, i,
3438 graph->node[0].coincident[start + i]);
3439 node = isl_schedule_node_band_set_permutable(node, permutable);
3440
3441 return node;
3442}
3443
3444/* Update the dependence relations based on the current schedule,
3445 * add the current band to "node" and then continue with the computation
3446 * of the next band.
3447 * Return the updated schedule node.
3448 */
3449static __isl_give isl_schedule_node *compute_next_band(
3450 __isl_take isl_schedule_node *node,
3451 struct isl_sched_graph *graph, int permutable)
3452{
3453 isl_ctx *ctx;
3454
3455 if (!node)
3456 return NULL((void*)0);
3457
3458 ctx = isl_schedule_node_get_ctx(node);
3459 if (update_edges(ctx, graph) < 0)
3460 return isl_schedule_node_free(node);
3461 node = insert_current_band(node, graph, permutable);
3462 next_band(graph);
3463
3464 node = isl_schedule_node_child(node, 0);
3465 node = compute_schedule(node, graph);
3466 node = isl_schedule_node_parent(node);
3467
3468 return node;
3469}
3470
3471/* Add constraints to graph->lp that force the dependence "map" (which
3472 * is part of the dependence relation of "edge")
3473 * to be respected and attempt to carry it, where the edge is one from
3474 * a node j to itself. "pos" is the sequence number of the given map.
3475 * That is, add constraints that enforce
3476 *
3477 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3478 * = c_j_x (y - x) >= e_i
3479 *
3480 * for each (x,y) in R.
3481 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3482 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3483 * with each coefficient in c_j_x represented as a pair of non-negative
3484 * coefficients.
3485 */
3486static int add_intra_constraints(struct isl_sched_graph *graph,
3487 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
3488{
3489 int offset;
3490 isl_ctx *ctx = isl_map_get_ctx(map);
3491 isl_dim_map *dim_map;
3492 isl_basic_setisl_basic_map *coef;
3493 struct isl_sched_node *node = edge->src;
3494
3495 coef = intra_coefficients(graph, node, map);
3496 if (!coef)
3497 return -1;
3498
3499 offset = coef_var_offset(coef);
3500 dim_map = intra_dim_map(ctx, graph, node, offset, 1);
3501 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3502 graph->lp = isl_basic_set_extend_constraints(graph->lp,
3503 coef->n_eq, coef->n_ineq);
3504 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
3505 coef, dim_map);
3506
3507 return 0;
3508}
3509
3510/* Add constraints to graph->lp that force the dependence "map" (which
3511 * is part of the dependence relation of "edge")
3512 * to be respected and attempt to carry it, where the edge is one from
3513 * node j to node k. "pos" is the sequence number of the given map.
3514 * That is, add constraints that enforce
3515 *
3516 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3517 *
3518 * for each (x,y) in R.
3519 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3520 * of valid constraints for R and then plug in
3521 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3522 * with each coefficient (except e_i, c_*_0 and c_*_n)
3523 * represented as a pair of non-negative coefficients.
3524 */
3525static int add_inter_constraints(struct isl_sched_graph *graph,
3526 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
3527{
3528 int offset;
3529 isl_ctx *ctx = isl_map_get_ctx(map);
3530 isl_dim_map *dim_map;
3531 isl_basic_setisl_basic_map *coef;
3532 struct isl_sched_node *src = edge->src;
3533 struct isl_sched_node *dst = edge->dst;
3534
3535 coef = inter_coefficients(graph, edge, map);
3536 if (!coef)
3537 return -1;
3538
3539 offset = coef_var_offset(coef);
3540 dim_map = inter_dim_map(ctx, graph, src, dst, offset, 1);
3541 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3542 graph->lp = isl_basic_set_extend_constraints(graph->lp,
3543 coef->n_eq, coef->n_ineq);
3544 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
3545 coef, dim_map);
3546
3547 return 0;
3548}
3549
3550/* Add constraints to graph->lp that force all (conditional) validity
3551 * dependences to be respected and attempt to carry them.
3552 */
3553static isl_stat add_all_constraints(struct isl_sched_graph *graph)
3554{
3555 int i, j;
3556 int pos;
3557
3558 pos = 0;
3559 for (i = 0; i < graph->n_edge; ++i) {
3560 struct isl_sched_edge *edge= &graph->edge[i];
3561
3562 if (!is_any_validity(edge))
3563 continue;
3564
3565 for (j = 0; j < edge->map->n; ++j) {
3566 isl_basic_map *bmap;
3567 isl_map *map;
3568
3569 bmap = isl_basic_map_copy(edge->map->p[j]);
3570 map = isl_map_from_basic_map(bmap);
3571
3572 if (edge->src == edge->dst &&
3573 add_intra_constraints(graph, edge, map, pos) < 0)
3574 return isl_stat_error;
3575 if (edge->src != edge->dst &&
3576 add_inter_constraints(graph, edge, map, pos) < 0)
3577 return isl_stat_error;
3578 ++pos;
3579 }
3580 }
3581
3582 return isl_stat_ok;
3583}
3584
3585/* Count the number of equality and inequality constraints
3586 * that will be added to the carry_lp problem.
3587 * We count each edge exactly once.
3588 */
3589static isl_stat count_all_constraints(struct isl_sched_graph *graph,
3590 int *n_eq, int *n_ineq)
3591{
3592 int i, j;
3593
3594 *n_eq = *n_ineq = 0;
3595 for (i = 0; i < graph->n_edge; ++i) {
3596 struct isl_sched_edge *edge= &graph->edge[i];
3597
3598 if (!is_any_validity(edge))
3599 continue;
3600
3601 for (j = 0; j < edge->map->n; ++j) {
3602 isl_basic_map *bmap;
3603 isl_map *map;
3604
3605 bmap = isl_basic_map_copy(edge->map->p[j]);
3606 map = isl_map_from_basic_map(bmap);
3607
3608 if (count_map_constraints(graph, edge, map,
3609 n_eq, n_ineq, 1, 0) < 0)
3610 return isl_stat_error;
3611 }
3612 }
3613
3614 return isl_stat_ok;
3615}
3616
3617/* Return the total number of (validity) edges that carry_dependences will
3618 * attempt to carry.
3619 */
3620static int count_carry_edges(struct isl_sched_graph *graph)
3621{
3622 int i;
3623 int n_edge;
3624
3625 n_edge = 0;
3626 for (i = 0; i < graph->n_edge; ++i) {
3627 struct isl_sched_edge *edge = &graph->edge[i];
3628
3629 if (!is_any_validity(edge))
3630 continue;
3631
3632 n_edge += isl_map_n_basic_map(edge->map);
3633 }
3634
3635 return n_edge;
3636}
3637
3638/* Construct an LP problem for finding schedule coefficients
3639 * such that the schedule carries as many validity dependences as possible.
3640 * In particular, for each dependence i, we bound the dependence distance
3641 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3642 * of all e_i's. Dependences with e_i = 0 in the solution are simply
3643 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3644 * Note that if the dependence relation is a union of basic maps,
3645 * then we have to consider each basic map individually as it may only
3646 * be possible to carry the dependences expressed by some of those
3647 * basic maps and not all of them.
3648 * Below, we consider each of those basic maps as a separate "edge".
3649 * "n_edge" is the number of these edges.
3650 *
3651 * All variables of the LP are non-negative. The actual coefficients
3652 * may be negative, so each coefficient is represented as the difference
3653 * of two non-negative variables. The negative part always appears
3654 * immediately before the positive part.
3655 * Other than that, the variables have the following order
3656 *
3657 * - sum of (1 - e_i) over all edges
3658 * - sum of all c_n coefficients
3659 * (unconstrained when computing non-parametric schedules)
3660 * - sum of positive and negative parts of all c_x coefficients
3661 * - for each edge
3662 * - e_i
3663 * - for each node
3664 * - c_i_0
3665 * - c_i_n (if parametric)
3666 * - positive and negative parts of c_i_x
3667 *
3668 * The constraints are those from the (validity) edges plus three equalities
3669 * to express the sums and n_edge inequalities to express e_i <= 1.
3670 */
3671static isl_stat setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
3672 int n_edge)
3673{
3674 int i;
3675 int k;
3676 isl_space *dim;
3677 unsigned total;
3678 int n_eq, n_ineq;
3679
3680 total = 3 + n_edge;
3681 for (i = 0; i < graph->n; ++i) {
3682 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
3683 node->start = total;
3684 total += 1 + node->nparam + 2 * node->nvar;
3685 }
3686
3687 if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
3688 return isl_stat_error;
3689
3690 dim = isl_space_set_alloc(ctx, 0, total);
3691 isl_basic_set_free(graph->lp);
3692 n_eq += 3;
3693 n_ineq += n_edge;
3694 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
3695 graph->lp = isl_basic_set_set_rational(graph->lp);
3696
3697 k = isl_basic_set_alloc_equality(graph->lp);
3698 if (k < 0)
3699 return isl_stat_error;
3700 isl_seq_clr(graph->lp->eq[k], 1 + total);
3701 isl_int_set_si(graph->lp->eq[k][0], -n_edge)isl_sioimath_set_si((graph->lp->eq[k][0]), -n_edge);
3702 isl_int_set_si(graph->lp->eq[k][1], 1)isl_sioimath_set_si((graph->lp->eq[k][1]), 1);
3703 for (i = 0; i < n_edge; ++i)
3704 isl_int_set_si(graph->lp->eq[k][4 + i], 1)isl_sioimath_set_si((graph->lp->eq[k][4 + i]), 1);
3705
3706 if (add_param_sum_constraint(graph, 1) < 0)
3707 return isl_stat_error;
3708 if (add_var_sum_constraint(graph, 2) < 0)
3709 return isl_stat_error;
3710
3711 for (i = 0; i < n_edge; ++i) {
3712 k = isl_basic_set_alloc_inequality(graph->lp);
3713 if (k < 0)
3714 return isl_stat_error;
3715 isl_seq_clr(graph->lp->ineq[k], 1 + total);
3716 isl_int_set_si(graph->lp->ineq[k][4 + i], -1)isl_sioimath_set_si((graph->lp->ineq[k][4 + i]), -1);
3717 isl_int_set_si(graph->lp->ineq[k][0], 1)isl_sioimath_set_si((graph->lp->ineq[k][0]), 1);
3718 }
3719
3720 if (add_all_constraints(graph) < 0)
3721 return isl_stat_error;
3722
3723 return isl_stat_ok;
3724}
3725
3726static __isl_give isl_schedule_node *compute_component_schedule(
3727 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
3728 int wcc);
3729
3730/* Comparison function for sorting the statements based on
3731 * the corresponding value in "r".
3732 */
3733static int smaller_value(const void *a, const void *b, void *data)
3734{
3735 isl_vec *r = data;
3736 const int *i1 = a;
3737 const int *i2 = b;
3738
3739 return isl_int_cmp(r->el[*i1], r->el[*i2])isl_sioimath_cmp(*(r->el[*i1]), *(r->el[*i2]));
3740}
3741
3742/* If the schedule_split_scaled option is set and if the linear
3743 * parts of the scheduling rows for all nodes in the graphs have
3744 * a non-trivial common divisor, then split off the remainder of the
3745 * constant term modulo this common divisor from the linear part.
3746 * Otherwise, insert a band node directly and continue with
3747 * the construction of the schedule.
3748 *
3749 * If a non-trivial common divisor is found, then
3750 * the linear part is reduced and the remainder is enforced
3751 * by a sequence node with the children placed in the order
3752 * of this remainder.
3753 * In particular, we assign an scc index based on the remainder and
3754 * then rely on compute_component_schedule to insert the sequence and
3755 * to continue the schedule construction on each part.
3756 */
3757static __isl_give isl_schedule_node *split_scaled(
3758 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3759{
3760 int i;
3761 int row;
3762 int scc;
3763 isl_ctx *ctx;
3764 isl_int gcd, gcd_i;
3765 isl_vec *r;
3766 int *order;
3767
3768 if (!node)
3769 return NULL((void*)0);
3770
3771 ctx = isl_schedule_node_get_ctx(node);
3772 if (!ctx->opt->schedule_split_scaled)
3773 return compute_next_band(node, graph, 0);
3774 if (graph->n <= 1)
3775 return compute_next_band(node, graph, 0);
3776
3777 isl_int_init(gcd)isl_sioimath_init((gcd));
3778 isl_int_init(gcd_i)isl_sioimath_init((gcd_i));
3779
3780 isl_int_set_si(gcd, 0)isl_sioimath_set_si((gcd), 0);
3781
3782 row = isl_mat_rows(graph->node[0].sched) - 1;
3783
3784 for (i = 0; i < graph->n; ++i) {
3785 struct isl_sched_node *node = &graph->node[i];
3786 int cols = isl_mat_cols(node->sched);
3787
3788 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
3789 isl_int_gcd(gcd, gcd, gcd_i)isl_sioimath_gcd((gcd), *(gcd), *(gcd_i));
3790 }
3791
3792 isl_int_clear(gcd_i)isl_sioimath_clear((gcd_i));
3793
3794 if (isl_int_cmp_si(gcd, 1)isl_sioimath_cmp_si(*(gcd), 1) <= 0) {
3795 isl_int_clear(gcd)isl_sioimath_clear((gcd));
3796 return compute_next_band(node, graph, 0);
3797 }
3798
3799 r = isl_vec_alloc(ctx, graph->n);
3800 order = isl_calloc_array(ctx, int, graph->n)((int *)isl_calloc_or_die(ctx, graph->n, sizeof(int)));
3801 if (!r || !order)
3802 goto error;
3803
3804 for (i = 0; i < graph->n; ++i) {
3805 struct isl_sched_node *node = &graph->node[i];
3806
3807 order[i] = i;
3808 isl_int_fdiv_r(r->el[i], node->sched->row[row][0], gcd)isl_sioimath_fdiv_r((r->el[i]), *(node->sched->row[row
][0]), *(gcd))
;
3809 isl_int_fdiv_q(node->sched->row[row][0],isl_sioimath_fdiv_q((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd))
3810 node->sched->row[row][0], gcd)isl_sioimath_fdiv_q((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd))
;
3811 isl_int_mul(node->sched->row[row][0],isl_sioimath_mul((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd))
3812 node->sched->row[row][0], gcd)isl_sioimath_mul((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd))
;
3813 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
3814 if (!node->sched)
3815 goto error;
3816 }
3817
3818 if (isl_sort(order, graph->n, sizeof(order[0]), &smaller_value, r) < 0)
3819 goto error;
3820
3821 scc = 0;
3822 for (i = 0; i < graph->n; ++i) {
3823 if (i > 0 && isl_int_ne(r->el[order[i - 1]], r->el[order[i]])(isl_sioimath_cmp(*(r->el[order[i - 1]]), *(r->el[order
[i]])) != 0)
)
3824 ++scc;
3825 graph->node[order[i]].scc = scc;
3826 }
3827 graph->scc = ++scc;
3828 graph->weak = 0;
3829
3830 isl_int_clear(gcd)isl_sioimath_clear((gcd));
3831 isl_vec_free(r);
3832 free(order);
3833
3834 if (update_edges(ctx, graph) < 0)
3835 return isl_schedule_node_free(node);
3836 node = insert_current_band(node, graph, 0);
3837 next_band(graph);
3838
3839 node = isl_schedule_node_child(node, 0);
3840 node = compute_component_schedule(node, graph, 0);
3841 node = isl_schedule_node_parent(node);
3842
3843 return node;
3844error:
3845 isl_vec_free(r);
3846 free(order);
3847 isl_int_clear(gcd)isl_sioimath_clear((gcd));
3848 return isl_schedule_node_free(node);
3849}
3850
3851/* Is the schedule row "sol" trivial on node "node"?
3852 * That is, is the solution zero on the dimensions orthogonal to
3853 * the previously found solutions?
3854 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3855 *
3856 * Each coefficient is represented as the difference between
3857 * two non-negative values in "sol". "sol" has been computed
3858 * in terms of the original iterators (i.e., without use of cmap).
3859 * We construct the schedule row s and write it as a linear
3860 * combination of (linear combinations of) previously computed schedule rows.
3861 * s = Q c or c = U s.
3862 * If the final entries of c are all zero, then the solution is trivial.
3863 */
3864static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
3865{
3866 int trivial;
3867 isl_vec *node_sol;
3868
3869 if (!sol)
3870 return -1;
3871 if (node->nvar == node->rank)
3872 return 0;
3873
3874 node_sol = extract_var_coef(node, sol);
3875 node_sol = isl_mat_vec_product(isl_mat_copy(node->cinv), node_sol);
3876 if (!node_sol)
3877 return -1;
3878
3879 trivial = isl_seq_first_non_zero(node_sol->el + node->rank,
3880 node->nvar - node->rank) == -1;
3881
3882 isl_vec_free(node_sol);
3883
3884 return trivial;
3885}
3886
3887/* Is the schedule row "sol" trivial on any node where it should
3888 * not be trivial?
3889 * "sol" has been computed in terms of the original iterators
3890 * (i.e., without use of cmap).
3891 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3892 */
3893static int is_any_trivial(struct isl_sched_graph *graph,
3894 __isl_keep isl_vec *sol)
3895{
3896 int i;
3897
3898 for (i = 0; i < graph->n; ++i) {
3899 struct isl_sched_node *node = &graph->node[i];
3900 int trivial;
3901
3902 if (!needs_row(graph, node))
3903 continue;
3904 trivial = is_trivial(node, sol);
3905 if (trivial < 0 || trivial)
3906 return trivial;
3907 }
3908
3909 return 0;
3910}
3911
3912/* Does the schedule represented by "sol" perform loop coalescing on "node"?
3913 * If so, return the position of the coalesced dimension.
3914 * Otherwise, return node->nvar or -1 on error.
3915 *
3916 * In particular, look for pairs of coefficients c_i and c_j such that
3917 * |c_j/c_i| >= size_i, i.e., |c_j| >= |c_i * size_i|.
3918 * If any such pair is found, then return i.
3919 * If size_i is infinity, then no check on c_i needs to be performed.
3920 */
3921static int find_node_coalescing(struct isl_sched_node *node,
3922 __isl_keep isl_vec *sol)
3923{
3924 int i, j;
3925 isl_int max;
3926 isl_vec *csol;
3927
3928 if (node->nvar <= 1)
3929 return node->nvar;
3930
3931 csol = extract_var_coef(node, sol);
3932 if (!csol)
3933 return -1;
3934 isl_int_init(max)isl_sioimath_init((max));
3935 for (i = 0; i < node->nvar; ++i) {
3936 isl_val *v;
3937
3938 if (isl_int_is_zero(csol->el[i])(isl_sioimath_sgn(*(csol->el[i])) == 0))
3939 continue;
3940 v = isl_multi_val_get_val(node->sizes, i);
3941 if (!v)
3942 goto error;
3943 if (!isl_val_is_int(v)) {
3944 isl_val_free(v);
3945 continue;
3946 }
3947 isl_int_mul(max, v->n, csol->el[i])isl_sioimath_mul((max), *(v->n), *(csol->el[i]));
3948 isl_val_free(v);
3949
3950 for (j = 0; j < node->nvar; ++j) {
3951 if (j == i)
3952 continue;
3953 if (isl_int_abs_ge(csol->el[j], max)(isl_sioimath_abs_cmp(*(csol->el[j]), *(max)) >= 0))
3954 break;
3955 }
3956 if (j < node->nvar)
3957 break;
3958 }
3959
3960 isl_int_clear(max)isl_sioimath_clear((max));
3961 isl_vec_free(csol);
3962 return i;
3963error:
3964 isl_int_clear(max)isl_sioimath_clear((max));
3965 isl_vec_free(csol);
3966 return -1;
3967}
3968
3969/* Force the schedule coefficient at position "pos" of "node" to be zero
3970 * in "tl".
3971 * The coefficient is encoded as the difference between two non-negative
3972 * variables. Force these two variables to have the same value.
3973 */
3974static __isl_give isl_tab_lexmin *zero_out_node_coef(
3975 __isl_take isl_tab_lexmin *tl, struct isl_sched_node *node, int pos)
3976{
3977 int dim;
3978 isl_ctx *ctx;
3979 isl_vec *eq;
3980
3981 ctx = isl_space_get_ctx(node->space);
3982 dim = isl_tab_lexmin_dim(tl);
3983 if (dim < 0)
3984 return isl_tab_lexmin_free(tl);
3985 eq = isl_vec_alloc(ctx, 1 + dim);
3986 eq = isl_vec_clr(eq);
3987 if (!eq)
3988 return isl_tab_lexmin_free(tl);
3989
3990 pos = 1 + node_var_coef_offset(node) + 2 * pos;
3991 isl_int_set_si(eq->el[pos], 1)isl_sioimath_set_si((eq->el[pos]), 1);
3992 isl_int_set_si(eq->el[pos + 1], -1)isl_sioimath_set_si((eq->el[pos + 1]), -1);
3993 tl = isl_tab_lexmin_add_eq(tl, eq->el);
3994 isl_vec_free(eq);
3995
3996 return tl;
3997}
3998
3999/* Return the lexicographically smallest rational point in the basic set
4000 * from which "tl" was constructed, double checking that this input set
4001 * was not empty.
4002 */
4003static __isl_give isl_vec *non_empty_solution(__isl_keep isl_tab_lexmin *tl)
4004{
4005 isl_vec *sol;
4006
4007 sol = isl_tab_lexmin_get_solution(tl);
4008 if (!sol)
4009 return NULL((void*)0);
4010 if (sol->size == 0)
4011 isl_die(isl_vec_get_ctx(sol), isl_error_internal,do { isl_handle_error(isl_vec_get_ctx(sol), isl_error_internal
, "error in schedule construction", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4013); return isl_vec_free(sol); } while (0)
4012 "error in schedule construction",do { isl_handle_error(isl_vec_get_ctx(sol), isl_error_internal
, "error in schedule construction", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4013); return isl_vec_free(sol); } while (0)
4013 return isl_vec_free(sol))do { isl_handle_error(isl_vec_get_ctx(sol), isl_error_internal
, "error in schedule construction", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4013); return isl_vec_free(sol); } while (0)
;
4014 return sol;
4015}
4016
4017/* Does the solution "sol" of the LP problem constructed by setup_carry_lp
4018 * carry any of the "n_edge" groups of dependences?
4019 * The value in the first position is the sum of (1 - e_i) over all "n_edge"
4020 * edges, with 0 <= e_i <= 1 equal to 1 when the dependences represented
4021 * by the edge are carried by the solution.
4022 * If the sum of the (1 - e_i) is smaller than "n_edge" then at least
4023 * one of those is carried.
4024 *
4025 * Note that despite the fact that the problem is solved using a rational
4026 * solver, the solution is guaranteed to be integral.
4027 * Specifically, the dependence distance lower bounds e_i (and therefore
4028 * also their sum) are integers. See Lemma 5 of [1].
4029 *
4030 * Any potential denominator of the sum is cleared by this function.
4031 * The denominator is not relevant for any of the other elements
4032 * in the solution.
4033 *
4034 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4035 * Problem, Part II: Multi-Dimensional Time.
4036 * In Intl. Journal of Parallel Programming, 1992.
4037 */
4038static int carries_dependences(__isl_keep isl_vec *sol, int n_edge)
4039{
4040 isl_int_divexact(sol->el[1], sol->el[1], sol->el[0])isl_sioimath_tdiv_q((sol->el[1]), *(sol->el[1]), *(sol->
el[0]))
;
4041 isl_int_set_si(sol->el[0], 1)isl_sioimath_set_si((sol->el[0]), 1);
4042 return isl_int_cmp_si(sol->el[1], n_edge)isl_sioimath_cmp_si(*(sol->el[1]), n_edge) < 0;
4043}
4044
4045/* Return the lexicographically smallest rational point in "lp",
4046 * assuming that all variables are non-negative and performing some
4047 * additional sanity checks.
4048 * In particular, "lp" should not be empty by construction.
4049 * Double check that this is the case.
4050 * Also, check that dependences are carried for at least one of
4051 * the "n_edge" edges.
4052 *
4053 * If the computed schedule performs loop coalescing on a given node,
4054 * i.e., if it is of the form
4055 *
4056 * c_i i + c_j j + ...
4057 *
4058 * with |c_j/c_i| >= size_i, then force the coefficient c_i to be zero
4059 * to cut out this solution. Repeat this process until no more loop
4060 * coalescing occurs or until no more dependences can be carried.
4061 * In the latter case, revert to the previously computed solution.
4062 */
4063static __isl_give isl_vec *non_neg_lexmin(struct isl_sched_graph *graph,
4064 __isl_take isl_basic_setisl_basic_map *lp, int n_edge)
4065{
4066 int i, pos;
4067 isl_ctx *ctx;
4068 isl_tab_lexmin *tl;
4069 isl_vec *sol, *prev = NULL((void*)0);
4070 int treat_coalescing;
4071
4072 if (!lp)
4073 return NULL((void*)0);
4074 ctx = isl_basic_set_get_ctx(lp);
4075 treat_coalescing = isl_options_get_schedule_treat_coalescing(ctx);
4076 tl = isl_tab_lexmin_from_basic_set(lp);
4077
4078 do {
4079 sol = non_empty_solution(tl);
4080 if (!sol)
4081 goto error;
4082
4083 if (!carries_dependences(sol, n_edge)) {
4084 if (!prev)
4085 isl_die(ctx, isl_error_unknown,do { isl_handle_error(ctx, isl_error_unknown, "unable to carry dependences"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4087); goto error; } while (0)
4086 "unable to carry dependences",do { isl_handle_error(ctx, isl_error_unknown, "unable to carry dependences"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4087); goto error; } while (0)
4087 goto error)do { isl_handle_error(ctx, isl_error_unknown, "unable to carry dependences"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4087); goto error; } while (0)
;
4088 isl_vec_free(sol);
4089 sol = prev;
4090 break;
4091 }
4092 prev = isl_vec_free(prev);
4093 if (!treat_coalescing)
4094 break;
4095 for (i = 0; i < graph->n; ++i) {
4096 struct isl_sched_node *node = &graph->node[i];
4097
4098 pos = find_node_coalescing(node, sol);
4099 if (pos < 0)
4100 goto error;
4101 if (pos < node->nvar)
4102 break;
4103 }
4104 if (i < graph->n) {
4105 prev = sol;
4106 tl = zero_out_node_coef(tl, &graph->node[i], pos);
4107 }
4108 } while (i < graph->n);
4109
4110 isl_tab_lexmin_free(tl);
4111
4112 return sol;
4113error:
4114 isl_tab_lexmin_free(tl);
4115 isl_vec_free(prev);
4116 isl_vec_free(sol);
4117 return NULL((void*)0);
4118}
4119
4120/* Construct a schedule row for each node such that as many validity dependences
4121 * as possible are carried and then continue with the next band.
4122 *
4123 * If there are no validity dependences, then no dependence can be carried and
4124 * the procedure is guaranteed to fail. If there is more than one component,
4125 * then try computing a schedule on each component separately
4126 * to prevent or at least postpone this failure.
4127 *
4128 * If the computed schedule row turns out to be trivial on one or
4129 * more nodes where it should not be trivial, then we throw it away
4130 * and try again on each component separately.
4131 *
4132 * If there is only one component, then we accept the schedule row anyway,
4133 * but we do not consider it as a complete row and therefore do not
4134 * increment graph->n_row. Note that the ranks of the nodes that
4135 * do get a non-trivial schedule part will get updated regardless and
4136 * graph->maxvar is computed based on these ranks. The test for
4137 * whether more schedule rows are required in compute_schedule_wcc
4138 * is therefore not affected.
4139 *
4140 * Insert a band corresponding to the schedule row at position "node"
4141 * of the schedule tree and continue with the construction of the schedule.
4142 * This insertion and the continued construction is performed by split_scaled
4143 * after optionally checking for non-trivial common divisors.
4144 */
4145static __isl_give isl_schedule_node *carry_dependences(
4146 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
4147{
4148 int n_edge;
4149 int trivial;
4150 isl_ctx *ctx;
4151 isl_vec *sol;
4152 isl_basic_setisl_basic_map *lp;
4153
4154 if (!node)
4155 return NULL((void*)0);
4156
4157 n_edge = count_carry_edges(graph);
4158 if (n_edge == 0 && graph->scc > 1)
4159 return compute_component_schedule(node, graph, 1);
4160
4161 ctx = isl_schedule_node_get_ctx(node);
4162 if (setup_carry_lp(ctx, graph, n_edge) < 0)
4163 return isl_schedule_node_free(node);
4164
4165 lp = isl_basic_set_copy(graph->lp);
4166 sol = non_neg_lexmin(graph, lp, n_edge);
4167 if (!sol)
4168 return isl_schedule_node_free(node);
4169
4170 trivial = is_any_trivial(graph, sol);
4171 if (trivial < 0) {
4172 sol = isl_vec_free(sol);
4173 } else if (trivial && graph->scc > 1) {
4174 isl_vec_free(sol);
4175 return compute_component_schedule(node, graph, 1);
4176 }
4177
4178 if (update_schedule(graph, sol, 0, 0) < 0)
4179 return isl_schedule_node_free(node);
4180 if (trivial)
4181 graph->n_row--;
4182
4183 return split_scaled(node, graph);
4184}
4185
4186/* Topologically sort statements mapped to the same schedule iteration
4187 * and add insert a sequence node in front of "node"
4188 * corresponding to this order.
4189 * If "initialized" is set, then it may be assumed that compute_maxvar
4190 * has been called on the current band. Otherwise, call
4191 * compute_maxvar if and before carry_dependences gets called.
4192 *
4193 * If it turns out to be impossible to sort the statements apart,
4194 * because different dependences impose different orderings
4195 * on the statements, then we extend the schedule such that
4196 * it carries at least one more dependence.
4197 */
4198static __isl_give isl_schedule_node *sort_statements(
4199 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
4200 int initialized)
4201{
4202 isl_ctx *ctx;
4203 isl_union_set_list *filters;
4204
4205 if (!node)
4206 return NULL((void*)0);
4207
4208 ctx = isl_schedule_node_get_ctx(node);
4209 if (graph->n < 1)
4210 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "graph should have at least one node"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4212); return isl_schedule_node_free(node); } while (0)
4211 "graph should have at least one node",do { isl_handle_error(ctx, isl_error_internal, "graph should have at least one node"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4212); return isl_schedule_node_free(node); } while (0)
4212 return isl_schedule_node_free(node))do { isl_handle_error(ctx, isl_error_internal, "graph should have at least one node"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4212); return isl_schedule_node_free(node); } while (0)
;
4213
4214 if (graph->n == 1)
4215 return node;
4216
4217 if (update_edges(ctx, graph) < 0)
4218 return isl_schedule_node_free(node);
4219
4220 if (graph->n_edge == 0)
4221 return node;
4222
4223 if (detect_sccs(ctx, graph) < 0)
4224 return isl_schedule_node_free(node);
4225
4226 next_band(graph);
4227 if (graph->scc < graph->n) {
4228 if (!initialized && compute_maxvar(graph) < 0)
4229 return isl_schedule_node_free(node);
4230 return carry_dependences(node, graph);
4231 }
4232
4233 filters = extract_sccs(ctx, graph);
4234 node = isl_schedule_node_insert_sequence(node, filters);
4235
4236 return node;
4237}
4238
4239/* Are there any (non-empty) (conditional) validity edges in the graph?
4240 */
4241static int has_validity_edges(struct isl_sched_graph *graph)
4242{
4243 int i;
4244
4245 for (i = 0; i < graph->n_edge; ++i) {
4246 int empty;
4247
4248 empty = isl_map_plain_is_empty(graph->edge[i].map);
4249 if (empty < 0)
4250 return -1;
4251 if (empty)
4252 continue;
4253 if (is_any_validity(&graph->edge[i]))
4254 return 1;
4255 }
4256
4257 return 0;
4258}
4259
4260/* Should we apply a Feautrier step?
4261 * That is, did the user request the Feautrier algorithm and are
4262 * there any validity dependences (left)?
4263 */
4264static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
4265{
4266 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER1)
4267 return 0;
4268
4269 return has_validity_edges(graph);
4270}
4271
4272/* Compute a schedule for a connected dependence graph using Feautrier's
4273 * multi-dimensional scheduling algorithm and return the updated schedule node.
4274 *
4275 * The original algorithm is described in [1].
4276 * The main idea is to minimize the number of scheduling dimensions, by
4277 * trying to satisfy as many dependences as possible per scheduling dimension.
4278 *
4279 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
4280 * Problem, Part II: Multi-Dimensional Time.
4281 * In Intl. Journal of Parallel Programming, 1992.
4282 */
4283static __isl_give isl_schedule_node *compute_schedule_wcc_feautrier(
4284 isl_schedule_node *node, struct isl_sched_graph *graph)
4285{
4286 return carry_dependences(node, graph);
4287}
4288
4289/* Turn off the "local" bit on all (condition) edges.
4290 */
4291static void clear_local_edges(struct isl_sched_graph *graph)
4292{
4293 int i;
4294
4295 for (i = 0; i < graph->n_edge; ++i)
4296 if (is_condition(&graph->edge[i]))
4297 clear_local(&graph->edge[i]);
4298}
4299
4300/* Does "graph" have both condition and conditional validity edges?
4301 */
4302static int need_condition_check(struct isl_sched_graph *graph)
4303{
4304 int i;
4305 int any_condition = 0;
4306 int any_conditional_validity = 0;
4307
4308 for (i = 0; i < graph->n_edge; ++i) {
4309 if (is_condition(&graph->edge[i]))
4310 any_condition = 1;
4311 if (is_conditional_validity(&graph->edge[i]))
4312 any_conditional_validity = 1;
4313 }
4314
4315 return any_condition && any_conditional_validity;
4316}
4317
4318/* Does "graph" contain any coincidence edge?
4319 */
4320static int has_any_coincidence(struct isl_sched_graph *graph)
4321{
4322 int i;
4323
4324 for (i = 0; i < graph->n_edge; ++i)
4325 if (is_coincidence(&graph->edge[i]))
4326 return 1;
4327
4328 return 0;
4329}
4330
4331/* Extract the final schedule row as a map with the iteration domain
4332 * of "node" as domain.
4333 */
4334static __isl_give isl_map *final_row(struct isl_sched_node *node)
4335{
4336 isl_multi_aff *ma;
4337 int row;
4338
4339 row = isl_mat_rows(node->sched) - 1;
4340 ma = node_extract_partial_schedule_multi_aff(node, row, 1);
4341 return isl_map_from_multi_aff(ma);
4342}
4343
4344/* Is the conditional validity dependence in the edge with index "edge_index"
4345 * violated by the latest (i.e., final) row of the schedule?
4346 * That is, is i scheduled after j
4347 * for any conditional validity dependence i -> j?
4348 */
4349static int is_violated(struct isl_sched_graph *graph, int edge_index)
4350{
4351 isl_map *src_sched, *dst_sched, *map;
4352 struct isl_sched_edge *edge = &graph->edge[edge_index];
4353 int empty;
4354
4355 src_sched = final_row(edge->src);
4356 dst_sched = final_row(edge->dst);
4357 map = isl_map_copy(edge->map);
4358 map = isl_map_apply_domain(map, src_sched);
4359 map = isl_map_apply_range(map, dst_sched);
4360 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);
4361 empty = isl_map_is_empty(map);
4362 isl_map_free(map);
4363
4364 if (empty < 0)
4365 return -1;
4366
4367 return !empty;
4368}
4369
4370/* Does "graph" have any satisfied condition edges that
4371 * are adjacent to the conditional validity constraint with
4372 * domain "conditional_source" and range "conditional_sink"?
4373 *
4374 * A satisfied condition is one that is not local.
4375 * If a condition was forced to be local already (i.e., marked as local)
4376 * then there is no need to check if it is in fact local.
4377 *
4378 * Additionally, mark all adjacent condition edges found as local.
4379 */
4380static int has_adjacent_true_conditions(struct isl_sched_graph *graph,
4381 __isl_keep isl_union_set *conditional_source,
4382 __isl_keep isl_union_set *conditional_sink)
4383{
4384 int i;
4385 int any = 0;
4386
4387 for (i = 0; i < graph->n_edge; ++i) {
4388 int adjacent, local;
4389 isl_union_map *condition;
4390
4391 if (!is_condition(&graph->edge[i]))
4392 continue;
4393 if (is_local(&graph->edge[i]))
4394 continue;
4395
4396 condition = graph->edge[i].tagged_condition;
4397 adjacent = domain_intersects(condition, conditional_sink);
4398 if (adjacent >= 0 && !adjacent)
4399 adjacent = range_intersects(condition,
4400 conditional_source);
4401 if (adjacent < 0)
4402 return -1;
4403 if (!adjacent)
4404 continue;
4405
4406 set_local(&graph->edge[i]);
4407
4408 local = is_condition_false(&graph->edge[i]);
4409 if (local < 0)
4410 return -1;
4411 if (!local)
4412 any = 1;
4413 }
4414
4415 return any;
4416}
4417
4418/* Are there any violated conditional validity dependences with
4419 * adjacent condition dependences that are not local with respect
4420 * to the current schedule?
4421 * That is, is the conditional validity constraint violated?
4422 *
4423 * Additionally, mark all those adjacent condition dependences as local.
4424 * We also mark those adjacent condition dependences that were not marked
4425 * as local before, but just happened to be local already. This ensures
4426 * that they remain local if the schedule is recomputed.
4427 *
4428 * We first collect domain and range of all violated conditional validity
4429 * dependences and then check if there are any adjacent non-local
4430 * condition dependences.
4431 */
4432static int has_violated_conditional_constraint(isl_ctx *ctx,
4433 struct isl_sched_graph *graph)
4434{
4435 int i;
4436 int any = 0;
4437 isl_union_set *source, *sink;
4438
4439 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
4440 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
4441 for (i = 0; i < graph->n_edge; ++i) {
4442 isl_union_set *uset;
4443 isl_union_map *umap;
4444 int violated;
4445
4446 if (!is_conditional_validity(&graph->edge[i]))
4447 continue;
4448
4449 violated = is_violated(graph, i);
4450 if (violated < 0)
4451 goto error;
4452 if (!violated)
4453 continue;
4454
4455 any = 1;
4456
4457 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
4458 uset = isl_union_map_domain(umap);
4459 source = isl_union_set_union(source, uset);
4460 source = isl_union_set_coalesce(source);
4461
4462 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
4463 uset = isl_union_map_range(umap);
4464 sink = isl_union_set_union(sink, uset);
4465 sink = isl_union_set_coalesce(sink);
4466 }
4467
4468 if (any)
4469 any = has_adjacent_true_conditions(graph, source, sink);
4470
4471 isl_union_set_free(source);
4472 isl_union_set_free(sink);
4473 return any;
4474error:
4475 isl_union_set_free(source);
4476 isl_union_set_free(sink);
4477 return -1;
4478}
4479
4480/* Examine the current band (the rows between graph->band_start and
4481 * graph->n_total_row), deciding whether to drop it or add it to "node"
4482 * and then continue with the computation of the next band, if any.
4483 * If "initialized" is set, then it may be assumed that compute_maxvar
4484 * has been called on the current band. Otherwise, call
4485 * compute_maxvar if and before carry_dependences gets called.
4486 *
4487 * The caller keeps looking for a new row as long as
4488 * graph->n_row < graph->maxvar. If the latest attempt to find
4489 * such a row failed (i.e., we still have graph->n_row < graph->maxvar),
4490 * then we either
4491 * - split between SCCs and start over (assuming we found an interesting
4492 * pair of SCCs between which to split)
4493 * - continue with the next band (assuming the current band has at least
4494 * one row)
4495 * - try to carry as many dependences as possible and continue with the next
4496 * band
4497 * In each case, we first insert a band node in the schedule tree
4498 * if any rows have been computed.
4499 *
4500 * If the caller managed to complete the schedule, we insert a band node
4501 * (if any schedule rows were computed) and we finish off by topologically
4502 * sorting the statements based on the remaining dependences.
4503 */
4504static __isl_give isl_schedule_node *compute_schedule_finish_band(
4505 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
4506 int initialized)
4507{
4508 int insert;
4509
4510 if (!node)
4511 return NULL((void*)0);
4512
4513 if (graph->n_row < graph->maxvar) {
4514 isl_ctx *ctx;
4515 int empty = graph->n_total_row == graph->band_start;
4516
4517 ctx = isl_schedule_node_get_ctx(node);
4518 if (!ctx->opt->schedule_maximize_band_depth && !empty)
4519 return compute_next_band(node, graph, 1);
4520 if (graph->src_scc >= 0)
4521 return compute_split_schedule(node, graph);
4522 if (!empty)
4523 return compute_next_band(node, graph, 1);
4524 if (!initialized && compute_maxvar(graph) < 0)
4525 return isl_schedule_node_free(node);
4526 return carry_dependences(node, graph);
4527 }
4528
4529 insert = graph->n_total_row > graph->band_start;
4530 if (insert) {
4531 node = insert_current_band(node, graph, 1);
4532 node = isl_schedule_node_child(node, 0);
4533 }
4534 node = sort_statements(node, graph, initialized);
4535 if (insert)
4536 node = isl_schedule_node_parent(node);
4537
4538 return node;
4539}
4540
4541/* Construct a band of schedule rows for a connected dependence graph.
4542 * The caller is responsible for determining the strongly connected
4543 * components and calling compute_maxvar first.
4544 *
4545 * We try to find a sequence of as many schedule rows as possible that result
4546 * in non-negative dependence distances (independent of the previous rows
4547 * in the sequence, i.e., such that the sequence is tilable), with as
4548 * many of the initial rows as possible satisfying the coincidence constraints.
4549 * The computation stops if we can't find any more rows or if we have found
4550 * all the rows we wanted to find.
4551 *
4552 * If ctx->opt->schedule_outer_coincidence is set, then we force the
4553 * outermost dimension to satisfy the coincidence constraints. If this
4554 * turns out to be impossible, we fall back on the general scheme above
4555 * and try to carry as many dependences as possible.
4556 *
4557 * If "graph" contains both condition and conditional validity dependences,
4558 * then we need to check that that the conditional schedule constraint
4559 * is satisfied, i.e., there are no violated conditional validity dependences
4560 * that are adjacent to any non-local condition dependences.
4561 * If there are, then we mark all those adjacent condition dependences
4562 * as local and recompute the current band. Those dependences that
4563 * are marked local will then be forced to be local.
4564 * The initial computation is performed with no dependences marked as local.
4565 * If we are lucky, then there will be no violated conditional validity
4566 * dependences adjacent to any non-local condition dependences.
4567 * Otherwise, we mark some additional condition dependences as local and
4568 * recompute. We continue this process until there are no violations left or
4569 * until we are no longer able to compute a schedule.
4570 * Since there are only a finite number of dependences,
4571 * there will only be a finite number of iterations.
4572 */
4573static isl_stat compute_schedule_wcc_band(isl_ctx *ctx,
4574 struct isl_sched_graph *graph)
4575{
4576 int has_coincidence;
4577 int use_coincidence;
4578 int force_coincidence = 0;
4579 int check_conditional;
4580
4581 if (sort_sccs(graph) < 0)
4582 return isl_stat_error;
4583
4584 clear_local_edges(graph);
4585 check_conditional = need_condition_check(graph);
4586 has_coincidence = has_any_coincidence(graph);
4587
4588 if (ctx->opt->schedule_outer_coincidence)
4589 force_coincidence = 1;
4590
4591 use_coincidence = has_coincidence;
4592 while (graph->n_row < graph->maxvar) {
4593 isl_vec *sol;
4594 int violated;
4595 int coincident;
4596
4597 graph->src_scc = -1;
4598 graph->dst_scc = -1;
4599
4600 if (setup_lp(ctx, graph, use_coincidence) < 0)
4601 return isl_stat_error;
4602 sol = solve_lp(graph);
4603 if (!sol)
4604 return isl_stat_error;
4605 if (sol->size == 0) {
4606 int empty = graph->n_total_row == graph->band_start;
4607
4608 isl_vec_free(sol);
4609 if (use_coincidence && (!force_coincidence || !empty)) {
4610 use_coincidence = 0;
4611 continue;
4612 }
4613 return isl_stat_ok;
4614 }
4615 coincident = !has_coincidence || use_coincidence;
4616 if (update_schedule(graph, sol, 1, coincident) < 0)
4617 return isl_stat_error;
4618
4619 if (!check_conditional)
4620 continue;
4621 violated = has_violated_conditional_constraint(ctx, graph);
4622 if (violated < 0)
4623 return isl_stat_error;
4624 if (!violated)
4625 continue;
4626 if (reset_band(graph) < 0)
4627 return isl_stat_error;
4628 use_coincidence = has_coincidence;
4629 }
4630
4631 return isl_stat_ok;
4632}
4633
4634/* Compute a schedule for a connected dependence graph by considering
4635 * the graph as a whole and return the updated schedule node.
4636 *
4637 * The actual schedule rows of the current band are computed by
4638 * compute_schedule_wcc_band. compute_schedule_finish_band takes
4639 * care of integrating the band into "node" and continuing
4640 * the computation.
4641 */
4642static __isl_give isl_schedule_node *compute_schedule_wcc_whole(
4643 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
4644{
4645 isl_ctx *ctx;
4646
4647 if (!node)
4648 return NULL((void*)0);
4649
4650 ctx = isl_schedule_node_get_ctx(node);
4651 if (compute_schedule_wcc_band(ctx, graph) < 0)
4652 return isl_schedule_node_free(node);
4653
4654 return compute_schedule_finish_band(node, graph, 1);
4655}
4656
4657/* Clustering information used by compute_schedule_wcc_clustering.
4658 *
4659 * "n" is the number of SCCs in the original dependence graph
4660 * "scc" is an array of "n" elements, each representing an SCC
4661 * of the original dependence graph. All entries in the same cluster
4662 * have the same number of schedule rows.
4663 * "scc_cluster" maps each SCC index to the cluster to which it belongs,
4664 * where each cluster is represented by the index of the first SCC
4665 * in the cluster. Initially, each SCC belongs to a cluster containing
4666 * only that SCC.
4667 *
4668 * "scc_in_merge" is used by merge_clusters_along_edge to keep
4669 * track of which SCCs need to be merged.
4670 *
4671 * "cluster" contains the merged clusters of SCCs after the clustering
4672 * has completed.
4673 *
4674 * "scc_node" is a temporary data structure used inside copy_partial.
4675 * For each SCC, it keeps track of the number of nodes in the SCC
4676 * that have already been copied.
4677 */
4678struct isl_clustering {
4679 int n;
4680 struct isl_sched_graph *scc;
4681 struct isl_sched_graph *cluster;
4682 int *scc_cluster;
4683 int *scc_node;
4684 int *scc_in_merge;
4685};
4686
4687/* Initialize the clustering data structure "c" from "graph".
4688 *
4689 * In particular, allocate memory, extract the SCCs from "graph"
4690 * into c->scc, initialize scc_cluster and construct
4691 * a band of schedule rows for each SCC.
4692 * Within each SCC, there is only one SCC by definition.
4693 * Each SCC initially belongs to a cluster containing only that SCC.
4694 */
4695static isl_stat clustering_init(isl_ctx *ctx, struct isl_clustering *c,
4696 struct isl_sched_graph *graph)
4697{
4698 int i;
4699
4700 c->n = graph->scc;
4701 c->scc = isl_calloc_array(ctx, struct isl_sched_graph, c->n)((struct isl_sched_graph *)isl_calloc_or_die(ctx, c->n, sizeof
(struct isl_sched_graph)))
;
4702 c->cluster = isl_calloc_array(ctx, struct isl_sched_graph, c->n)((struct isl_sched_graph *)isl_calloc_or_die(ctx, c->n, sizeof
(struct isl_sched_graph)))
;
4703 c->scc_cluster = isl_calloc_array(ctx, int, c->n)((int *)isl_calloc_or_die(ctx, c->n, sizeof(int)));
4704 c->scc_node = isl_calloc_array(ctx, int, c->n)((int *)isl_calloc_or_die(ctx, c->n, sizeof(int)));
4705 c->scc_in_merge = isl_calloc_array(ctx, int, c->n)((int *)isl_calloc_or_die(ctx, c->n, sizeof(int)));
4706 if (!c->scc || !c->cluster ||
4707 !c->scc_cluster || !c->scc_node || !c->scc_in_merge)
4708 return isl_stat_error;
4709
4710 for (i = 0; i < c->n; ++i) {
4711 if (extract_sub_graph(ctx, graph, &node_scc_exactly,
4712 &edge_scc_exactly, i, &c->scc[i]) < 0)
4713 return isl_stat_error;
4714 c->scc[i].scc = 1;
4715 if (compute_maxvar(&c->scc[i]) < 0)
4716 return isl_stat_error;
4717 if (compute_schedule_wcc_band(ctx, &c->scc[i]) < 0)
4718 return isl_stat_error;
4719 c->scc_cluster[i] = i;
4720 }
4721
4722 return isl_stat_ok;
4723}
4724
4725/* Free all memory allocated for "c".
4726 */
4727static void clustering_free(isl_ctx *ctx, struct isl_clustering *c)
4728{
4729 int i;
4730
4731 if (c->scc)
4732 for (i = 0; i < c->n; ++i)
4733 graph_free(ctx, &c->scc[i]);
4734 free(c->scc);
4735 if (c->cluster)
4736 for (i = 0; i < c->n; ++i)
4737 graph_free(ctx, &c->cluster[i]);
4738 free(c->cluster);
4739 free(c->scc_cluster);
4740 free(c->scc_node);
4741 free(c->scc_in_merge);
4742}
4743
4744/* Should we refrain from merging the cluster in "graph" with
4745 * any other cluster?
4746 * In particular, is its current schedule band empty and incomplete.
4747 */
4748static int bad_cluster(struct isl_sched_graph *graph)
4749{
4750 return graph->n_row < graph->maxvar &&
4751 graph->n_total_row == graph->band_start;
4752}
4753
4754/* Return the index of an edge in "graph" that can be used to merge
4755 * two clusters in "c".
4756 * Return graph->n_edge if no such edge can be found.
4757 * Return -1 on error.
4758 *
4759 * In particular, return a proximity edge between two clusters
4760 * that is not marked "no_merge" and such that neither of the
4761 * two clusters has an incomplete, empty band.
4762 *
4763 * If there are multiple such edges, then try and find the most
4764 * appropriate edge to use for merging. In particular, pick the edge
4765 * with the greatest weight. If there are multiple of those,
4766 * then pick one with the shortest distance between
4767 * the two cluster representatives.
4768 */
4769static int find_proximity(struct isl_sched_graph *graph,
4770 struct isl_clustering *c)
4771{
4772 int i, best = graph->n_edge, best_dist, best_weight;
4773
4774 for (i = 0; i < graph->n_edge; ++i) {
4775 struct isl_sched_edge *edge = &graph->edge[i];
4776 int dist, weight;
4777
4778 if (!is_proximity(edge))
4779 continue;
4780 if (edge->no_merge)
4781 continue;
4782 if (bad_cluster(&c->scc[edge->src->scc]) ||
4783 bad_cluster(&c->scc[edge->dst->scc]))
4784 continue;
4785 dist = c->scc_cluster[edge->dst->scc] -
4786 c->scc_cluster[edge->src->scc];
4787 if (dist == 0)
4788 continue;
4789 weight = edge->weight;
4790 if (best < graph->n_edge) {
4791 if (best_weight > weight)
4792 continue;
4793 if (best_weight == weight && best_dist <= dist)
4794 continue;
4795 }
4796 best = i;
4797 best_dist = dist;
4798 best_weight = weight;
4799 }
4800
4801 return best;
4802}
4803
4804/* Internal data structure used in mark_merge_sccs.
4805 *
4806 * "graph" is the dependence graph in which a strongly connected
4807 * component is constructed.
4808 * "scc_cluster" maps each SCC index to the cluster to which it belongs.
4809 * "src" and "dst" are the indices of the nodes that are being merged.
4810 */
4811struct isl_mark_merge_sccs_data {
4812 struct isl_sched_graph *graph;
4813 int *scc_cluster;
4814 int src;
4815 int dst;
4816};
4817
4818/* Check whether the cluster containing node "i" depends on the cluster
4819 * containing node "j". If "i" and "j" belong to the same cluster,
4820 * then they are taken to depend on each other to ensure that
4821 * the resulting strongly connected component consists of complete
4822 * clusters. Furthermore, if "i" and "j" are the two nodes that
4823 * are being merged, then they are taken to depend on each other as well.
4824 * Otherwise, check if there is a (conditional) validity dependence
4825 * from node[j] to node[i], forcing node[i] to follow node[j].
4826 */
4827static isl_bool cluster_follows(int i, int j, void *user)
4828{
4829 struct isl_mark_merge_sccs_data *data = user;
4830 struct isl_sched_graph *graph = data->graph;
4831 int *scc_cluster = data->scc_cluster;
4832
4833 if (data->src == i && data->dst == j)
4834 return isl_bool_true;
4835 if (data->src == j && data->dst == i)
4836 return isl_bool_true;
4837 if (scc_cluster[graph->node[i].scc] == scc_cluster[graph->node[j].scc])
4838 return isl_bool_true;
4839
4840 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
4841}
4842
4843/* Mark all SCCs that belong to either of the two clusters in "c"
4844 * connected by the edge in "graph" with index "edge", or to any
4845 * of the intermediate clusters.
4846 * The marking is recorded in c->scc_in_merge.
4847 *
4848 * The given edge has been selected for merging two clusters,
4849 * meaning that there is at least a proximity edge between the two nodes.
4850 * However, there may also be (indirect) validity dependences
4851 * between the two nodes. When merging the two clusters, all clusters
4852 * containing one or more of the intermediate nodes along the
4853 * indirect validity dependences need to be merged in as well.
4854 *
4855 * First collect all such nodes by computing the strongly connected
4856 * component (SCC) containing the two nodes connected by the edge, where
4857 * the two nodes are considered to depend on each other to make
4858 * sure they end up in the same SCC. Similarly, each node is considered
4859 * to depend on every other node in the same cluster to ensure
4860 * that the SCC consists of complete clusters.
4861 *
4862 * Then the original SCCs that contain any of these nodes are marked
4863 * in c->scc_in_merge.
4864 */
4865static isl_stat mark_merge_sccs(isl_ctx *ctx, struct isl_sched_graph *graph,
4866 int edge, struct isl_clustering *c)
4867{
4868 struct isl_mark_merge_sccs_data data;
4869 struct isl_tarjan_graph *g;
4870 int i;
4871
4872 for (i = 0; i < c->n; ++i)
4873 c->scc_in_merge[i] = 0;
4874
4875 data.graph = graph;
4876 data.scc_cluster = c->scc_cluster;
4877 data.src = graph->edge[edge].src - graph->node;
4878 data.dst = graph->edge[edge].dst - graph->node;
4879
4880 g = isl_tarjan_graph_component(ctx, graph->n, data.dst,
4881 &cluster_follows, &data);
4882 if (!g)
4883 goto error;
4884
4885 i = g->op;
4886 if (i < 3)
4887 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "expecting at least two nodes in component"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4889); goto error; } while (0)
4888 "expecting at least two nodes in component",do { isl_handle_error(ctx, isl_error_internal, "expecting at least two nodes in component"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4889); goto error; } while (0)
4889 goto error)do { isl_handle_error(ctx, isl_error_internal, "expecting at least two nodes in component"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4889); goto error; } while (0)
;
4890 if (g->order[--i] != -1)
4891 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "expecting end of component marker"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4892); goto error; } while (0)
4892 "expecting end of component marker", goto error)do { isl_handle_error(ctx, isl_error_internal, "expecting end of component marker"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 4892); goto error; } while (0)
;
4893
4894 for (--i; i >= 0 && g->order[i] != -1; --i) {
4895 int scc = graph->node[g->order[i]].scc;
4896 c->scc_in_merge[scc] = 1;
4897 }
4898
4899 isl_tarjan_graph_free(g);
4900 return isl_stat_ok;
4901error:
4902 isl_tarjan_graph_free(g);
4903 return isl_stat_error;
4904}
4905
4906/* Construct the identifier "cluster_i".
4907 */
4908static __isl_give isl_id *cluster_id(isl_ctx *ctx, int i)
4909{
4910 char name[40];
4911
4912 snprintf(name, sizeof(name), "cluster_%d", i);
4913 return isl_id_alloc(ctx, name, NULL((void*)0));
4914}
4915
4916/* Construct the space of the cluster with index "i" containing
4917 * the strongly connected component "scc".
4918 *
4919 * In particular, construct a space called cluster_i with dimension equal
4920 * to the number of schedule rows in the current band of "scc".
4921 */
4922static __isl_give isl_space *cluster_space(struct isl_sched_graph *scc, int i)
4923{
4924 int nvar;
4925 isl_space *space;
4926 isl_id *id;
4927
4928 nvar = scc->n_total_row - scc->band_start;
4929 space = isl_space_copy(scc->node[0].space);
4930 space = isl_space_params(space);
4931 space = isl_space_set_from_params(space);
4932 space = isl_space_add_dims(space, isl_dim_set, nvar);
4933 id = cluster_id(isl_space_get_ctx(space), i);
4934 space = isl_space_set_tuple_id(space, isl_dim_set, id);
4935
4936 return space;
4937}
4938
4939/* Collect the domain of the graph for merging clusters.
4940 *
4941 * In particular, for each cluster with first SCC "i", construct
4942 * a set in the space called cluster_i with dimension equal
4943 * to the number of schedule rows in the current band of the cluster.
4944 */
4945static __isl_give isl_union_set *collect_domain(isl_ctx *ctx,
4946 struct isl_sched_graph *graph, struct isl_clustering *c)
4947{
4948 int i;
4949 isl_space *space;
4950 isl_union_set *domain;
4951
4952 space = isl_space_params_alloc(ctx, 0);
4953 domain = isl_union_set_empty(space);
4954
4955 for (i = 0; i < graph->scc; ++i) {
4956 isl_space *space;
4957
4958 if (!c->scc_in_merge[i])
4959 continue;
4960 if (c->scc_cluster[i] != i)
4961 continue;
4962 space = cluster_space(&c->scc[i], i);
4963 domain = isl_union_set_add_set(domain, isl_set_universe(space));
4964 }
4965
4966 return domain;
4967}
4968
4969/* Construct a map from the original instances to the corresponding
4970 * cluster instance in the current bands of the clusters in "c".
4971 */
4972static __isl_give isl_union_map *collect_cluster_map(isl_ctx *ctx,
4973 struct isl_sched_graph *graph, struct isl_clustering *c)
4974{
4975 int i, j;
4976 isl_space *space;
4977 isl_union_map *cluster_map;
4978
4979 space = isl_space_params_alloc(ctx, 0);
4980 cluster_map = isl_union_map_empty(space);
4981 for (i = 0; i < graph->scc; ++i) {
4982 int start, n;
4983 isl_id *id;
4984
4985 if (!c->scc_in_merge[i])
4986 continue;
4987
4988 id = cluster_id(ctx, c->scc_cluster[i]);
4989 start = c->scc[i].band_start;
4990 n = c->scc[i].n_total_row - start;
4991 for (j = 0; j < c->scc[i].n; ++j) {
4992 isl_multi_aff *ma;
4993 isl_map *map;
4994 struct isl_sched_node *node = &c->scc[i].node[j];
4995
4996 ma = node_extract_partial_schedule_multi_aff(node,
4997 start, n);
4998 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out,
4999 isl_id_copy(id));
5000 map = isl_map_from_multi_aff(ma);
5001 cluster_map = isl_union_map_add_map(cluster_map, map);
5002 }
5003 isl_id_free(id);
5004 }
5005
5006 return cluster_map;
5007}
5008
5009/* Add "umap" to the schedule constraints "sc" of all types of "edge"
5010 * that are not isl_edge_condition or isl_edge_conditional_validity.
5011 */
5012static __isl_give isl_schedule_constraints *add_non_conditional_constraints(
5013 struct isl_sched_edge *edge, __isl_keep isl_union_map *umap,
5014 __isl_take isl_schedule_constraints *sc)
5015{
5016 enum isl_edge_type t;
5017
5018 if (!sc)
5019 return NULL((void*)0);
5020
5021 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
5022 if (t == isl_edge_condition ||
5023 t == isl_edge_conditional_validity)
5024 continue;
5025 if (!is_type(edge, t))
5026 continue;
5027 sc = isl_schedule_constraints_add(sc, t,
5028 isl_union_map_copy(umap));
5029 }
5030
5031 return sc;
5032}
5033
5034/* Add schedule constraints of types isl_edge_condition and
5035 * isl_edge_conditional_validity to "sc" by applying "umap" to
5036 * the domains of the wrapped relations in domain and range
5037 * of the corresponding tagged constraints of "edge".
5038 */
5039static __isl_give isl_schedule_constraints *add_conditional_constraints(
5040 struct isl_sched_edge *edge, __isl_keep isl_union_map *umap,
5041 __isl_take isl_schedule_constraints *sc)
5042{
5043 enum isl_edge_type t;
5044 isl_union_map *tagged;
5045
5046 for (t = isl_edge_condition; t <= isl_edge_conditional_validity; ++t) {
5047 if (!is_type(edge, t))
5048 continue;
5049 if (t == isl_edge_condition)
5050 tagged = isl_union_map_copy(edge->tagged_condition);
5051 else
5052 tagged = isl_union_map_copy(edge->tagged_validity);
5053 tagged = isl_union_map_zip(tagged);
5054 tagged = isl_union_map_apply_domain(tagged,
5055 isl_union_map_copy(umap));
5056 tagged = isl_union_map_zip(tagged);
5057 sc = isl_schedule_constraints_add(sc, t, tagged);
5058 if (!sc)
5059 return NULL((void*)0);
5060 }
5061
5062 return sc;
5063}
5064
5065/* Given a mapping "cluster_map" from the original instances to
5066 * the cluster instances, add schedule constraints on the clusters
5067 * to "sc" corresponding to the original constraints represented by "edge".
5068 *
5069 * For non-tagged dependence constraints, the cluster constraints
5070 * are obtained by applying "cluster_map" to the edge->map.
5071 *
5072 * For tagged dependence constraints, "cluster_map" needs to be applied
5073 * to the domains of the wrapped relations in domain and range
5074 * of the tagged dependence constraints. Pick out the mappings
5075 * from these domains from "cluster_map" and construct their product.
5076 * This mapping can then be applied to the pair of domains.
5077 */
5078static __isl_give isl_schedule_constraints *collect_edge_constraints(
5079 struct isl_sched_edge *edge, __isl_keep isl_union_map *cluster_map,
5080 __isl_take isl_schedule_constraints *sc)
5081{
5082 isl_union_map *umap;
5083 isl_space *space;
5084 isl_union_set *uset;
5085 isl_union_map *umap1, *umap2;
5086
5087 if (!sc)
5088 return NULL((void*)0);
5089
5090 umap = isl_union_map_from_map(isl_map_copy(edge->map));
5091 umap = isl_union_map_apply_domain(umap,
5092 isl_union_map_copy(cluster_map));
5093 umap = isl_union_map_apply_range(umap,
5094 isl_union_map_copy(cluster_map));
5095 sc = add_non_conditional_constraints(edge, umap, sc);
5096 isl_union_map_free(umap);
5097
5098 if (!sc || (!is_condition(edge) && !is_conditional_validity(edge)))
5099 return sc;
5100
5101 space = isl_space_domain(isl_map_get_space(edge->map));
5102 uset = isl_union_set_from_set(isl_set_universe(space));
5103 umap1 = isl_union_map_copy(cluster_map);
5104 umap1 = isl_union_map_intersect_domain(umap1, uset);
5105 space = isl_space_range(isl_map_get_space(edge->map));
5106 uset = isl_union_set_from_set(isl_set_universe(space));
5107 umap2 = isl_union_map_copy(cluster_map);
5108 umap2 = isl_union_map_intersect_domain(umap2, uset);
5109 umap = isl_union_map_product(umap1, umap2);
5110
5111 sc = add_conditional_constraints(edge, umap, sc);
5112
5113 isl_union_map_free(umap);
5114 return sc;
5115}
5116
5117/* Given a mapping "cluster_map" from the original instances to
5118 * the cluster instances, add schedule constraints on the clusters
5119 * to "sc" corresponding to all edges in "graph" between nodes that
5120 * belong to SCCs that are marked for merging in "scc_in_merge".
5121 */
5122static __isl_give isl_schedule_constraints *collect_constraints(
5123 struct isl_sched_graph *graph, int *scc_in_merge,
5124 __isl_keep isl_union_map *cluster_map,
5125 __isl_take isl_schedule_constraints *sc)
5126{
5127 int i;
5128
5129 for (i = 0; i < graph->n_edge; ++i) {
5130 struct isl_sched_edge *edge = &graph->edge[i];
5131
5132 if (!scc_in_merge[edge->src->scc])
5133 continue;
5134 if (!scc_in_merge[edge->dst->scc])
5135 continue;
5136 sc = collect_edge_constraints(edge, cluster_map, sc);
5137 }
5138
5139 return sc;
5140}
5141
5142/* Construct a dependence graph for scheduling clusters with respect
5143 * to each other and store the result in "merge_graph".
5144 * In particular, the nodes of the graph correspond to the schedule
5145 * dimensions of the current bands of those clusters that have been
5146 * marked for merging in "c".
5147 *
5148 * First construct an isl_schedule_constraints object for this domain
5149 * by transforming the edges in "graph" to the domain.
5150 * Then initialize a dependence graph for scheduling from these
5151 * constraints.
5152 */
5153static isl_stat init_merge_graph(isl_ctx *ctx, struct isl_sched_graph *graph,
5154 struct isl_clustering *c, struct isl_sched_graph *merge_graph)
5155{
5156 isl_union_set *domain;
5157 isl_union_map *cluster_map;
5158 isl_schedule_constraints *sc;
5159 isl_stat r;
5160
5161 domain = collect_domain(ctx, graph, c);
5162 sc = isl_schedule_constraints_on_domain(domain);
5163 if (!sc)
5164 return isl_stat_error;
5165 cluster_map = collect_cluster_map(ctx, graph, c);
5166 sc = collect_constraints(graph, c->scc_in_merge, cluster_map, sc);
5167 isl_union_map_free(cluster_map);
5168
5169 r = graph_init(merge_graph, sc);
5170
5171 isl_schedule_constraints_free(sc);
5172
5173 return r;
5174}
5175
5176/* Compute the maximal number of remaining schedule rows that still need
5177 * to be computed for the nodes that belong to clusters with the maximal
5178 * dimension for the current band (i.e., the band that is to be merged).
5179 * Only clusters that are about to be merged are considered.
5180 * "maxvar" is the maximal dimension for the current band.
5181 * "c" contains information about the clusters.
5182 *
5183 * Return the maximal number of remaining schedule rows or -1 on error.
5184 */
5185static int compute_maxvar_max_slack(int maxvar, struct isl_clustering *c)
5186{
5187 int i, j;
5188 int max_slack;
5189
5190 max_slack = 0;
5191 for (i = 0; i < c->n; ++i) {
5192 int nvar;
5193 struct isl_sched_graph *scc;
5194
5195 if (!c->scc_in_merge[i])
5196 continue;
5197 scc = &c->scc[i];
5198 nvar = scc->n_total_row - scc->band_start;
5199 if (nvar != maxvar)
5200 continue;
5201 for (j = 0; j < scc->n; ++j) {
5202 struct isl_sched_node *node = &scc->node[j];
5203 int slack;
5204
5205 if (node_update_cmap(node) < 0)
5206 return -1;
5207 slack = node->nvar - node->rank;
5208 if (slack > max_slack)
5209 max_slack = slack;
5210 }
5211 }
5212
5213 return max_slack;
5214}
5215
5216/* If there are any clusters where the dimension of the current band
5217 * (i.e., the band that is to be merged) is smaller than "maxvar" and
5218 * if there are any nodes in such a cluster where the number
5219 * of remaining schedule rows that still need to be computed
5220 * is greater than "max_slack", then return the smallest current band
5221 * dimension of all these clusters. Otherwise return the original value
5222 * of "maxvar". Return -1 in case of any error.
5223 * Only clusters that are about to be merged are considered.
5224 * "c" contains information about the clusters.
5225 */
5226static int limit_maxvar_to_slack(int maxvar, int max_slack,
5227 struct isl_clustering *c)
5228{
5229 int i, j;
5230
5231 for (i = 0; i < c->n; ++i) {
5232 int nvar;
5233 struct isl_sched_graph *scc;
5234
5235 if (!c->scc_in_merge[i])
5236 continue;
5237 scc = &c->scc[i];
5238 nvar = scc->n_total_row - scc->band_start;
5239 if (nvar >= maxvar)
5240 continue;
5241 for (j = 0; j < scc->n; ++j) {
5242 struct isl_sched_node *node = &scc->node[j];
5243 int slack;
5244
5245 if (node_update_cmap(node) < 0)
5246 return -1;
5247 slack = node->nvar - node->rank;
5248 if (slack > max_slack) {
5249 maxvar = nvar;
5250 break;
5251 }
5252 }
5253 }
5254
5255 return maxvar;
5256}
5257
5258/* Adjust merge_graph->maxvar based on the number of remaining schedule rows
5259 * that still need to be computed. In particular, if there is a node
5260 * in a cluster where the dimension of the current band is smaller
5261 * than merge_graph->maxvar, but the number of remaining schedule rows
5262 * is greater than that of any node in a cluster with the maximal
5263 * dimension for the current band (i.e., merge_graph->maxvar),
5264 * then adjust merge_graph->maxvar to the (smallest) current band dimension
5265 * of those clusters. Without this adjustment, the total number of
5266 * schedule dimensions would be increased, resulting in a skewed view
5267 * of the number of coincident dimensions.
5268 * "c" contains information about the clusters.
5269 *
5270 * If the maximize_band_depth option is set and merge_graph->maxvar is reduced,
5271 * then there is no point in attempting any merge since it will be rejected
5272 * anyway. Set merge_graph->maxvar to zero in such cases.
5273 */
5274static isl_stat adjust_maxvar_to_slack(isl_ctx *ctx,
5275 struct isl_sched_graph *merge_graph, struct isl_clustering *c)
5276{
5277 int max_slack, maxvar;
5278
5279 max_slack = compute_maxvar_max_slack(merge_graph->maxvar, c);
5280 if (max_slack < 0)
5281 return isl_stat_error;
5282 maxvar = limit_maxvar_to_slack(merge_graph->maxvar, max_slack, c);
5283 if (maxvar < 0)
5284 return isl_stat_error;
5285
5286 if (maxvar < merge_graph->maxvar) {
5287 if (isl_options_get_schedule_maximize_band_depth(ctx))
5288 merge_graph->maxvar = 0;
5289 else
5290 merge_graph->maxvar = maxvar;
5291 }
5292
5293 return isl_stat_ok;
5294}
5295
5296/* Return the number of coincident dimensions in the current band of "graph",
5297 * where the nodes of "graph" are assumed to be scheduled by a single band.
5298 */
5299static int get_n_coincident(struct isl_sched_graph *graph)
5300{
5301 int i;
5302
5303 for (i = graph->band_start; i < graph->n_total_row; ++i)
5304 if (!graph->node[0].coincident[i])
5305 break;
5306
5307 return i - graph->band_start;
5308}
5309
5310/* Should the clusters be merged based on the cluster schedule
5311 * in the current (and only) band of "merge_graph", given that
5312 * coincidence should be maximized?
5313 *
5314 * If the number of coincident schedule dimensions in the merged band
5315 * would be less than the maximal number of coincident schedule dimensions
5316 * in any of the merged clusters, then the clusters should not be merged.
5317 */
5318static isl_bool ok_to_merge_coincident(struct isl_clustering *c,
5319 struct isl_sched_graph *merge_graph)
5320{
5321 int i;
5322 int n_coincident;
5323 int max_coincident;
5324
5325 max_coincident = 0;
5326 for (i = 0; i < c->n; ++i) {
5327 if (!c->scc_in_merge[i])
5328 continue;
5329 n_coincident = get_n_coincident(&c->scc[i]);
5330 if (n_coincident > max_coincident)
5331 max_coincident = n_coincident;
5332 }
5333
5334 n_coincident = get_n_coincident(merge_graph);
5335
5336 return n_coincident >= max_coincident;
5337}
5338
5339/* Return the transformation on "node" expressed by the current (and only)
5340 * band of "merge_graph" applied to the clusters in "c".
5341 *
5342 * First find the representation of "node" in its SCC in "c" and
5343 * extract the transformation expressed by the current band.
5344 * Then extract the transformation applied by "merge_graph"
5345 * to the cluster to which this SCC belongs.
5346 * Combine the two to obtain the complete transformation on the node.
5347 *
5348 * Note that the range of the first transformation is an anonymous space,
5349 * while the domain of the second is named "cluster_X". The range
5350 * of the former therefore needs to be adjusted before the two
5351 * can be combined.
5352 */
5353static __isl_give isl_map *extract_node_transformation(isl_ctx *ctx,
5354 struct isl_sched_node *node, struct isl_clustering *c,
5355 struct isl_sched_graph *merge_graph)
5356{
5357 struct isl_sched_node *scc_node, *cluster_node;
5358 int start, n;
5359 isl_id *id;
5360 isl_space *space;
5361 isl_multi_aff *ma, *ma2;
5362
5363 scc_node = graph_find_node(ctx, &c->scc[node->scc], node->space);
5364 start = c->scc[node->scc].band_start;
5365 n = c->scc[node->scc].n_total_row - start;
5366 ma = node_extract_partial_schedule_multi_aff(scc_node, start, n);
5367 space = cluster_space(&c->scc[node->scc], c->scc_cluster[node->scc]);
5368 cluster_node = graph_find_node(ctx, merge_graph, space);
5369 if (space && !cluster_node)
5370 isl_die(ctx, isl_error_internal, "unable to find cluster",do { isl_handle_error(ctx, isl_error_internal, "unable to find cluster"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 5371); space = isl_space_free(space); } while (0)
5371 space = isl_space_free(space))do { isl_handle_error(ctx, isl_error_internal, "unable to find cluster"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 5371); space = isl_space_free(space); } while (0)
;
5372 id = isl_space_get_tuple_id(space, isl_dim_set);
5373 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out, id);
5374 isl_space_free(space);
5375 n = merge_graph->n_total_row;
5376 ma2 = node_extract_partial_schedule_multi_aff(cluster_node, 0, n);
5377 ma = isl_multi_aff_pullback_multi_aff(ma2, ma);
5378
5379 return isl_map_from_multi_aff(ma);
5380}
5381
5382/* Give a set of distances "set", are they bounded by a small constant
5383 * in direction "pos"?
5384 * In practice, check if they are bounded by 2 by checking that there
5385 * are no elements with a value greater than or equal to 3 or
5386 * smaller than or equal to -3.
5387 */
5388static isl_bool distance_is_bounded(__isl_keep isl_setisl_map *set, int pos)
5389{
5390 isl_bool bounded;
5391 isl_setisl_map *test;
5392
5393 if (!set)
5394 return isl_bool_error;
5395
5396 test = isl_set_copy(set);
5397 test = isl_set_lower_bound_si(test, isl_dim_set, pos, 3);
5398 bounded = isl_set_is_empty(test);
5399 isl_set_free(test);
5400
5401 if (bounded < 0 || !bounded)
5402 return bounded;
5403
5404 test = isl_set_copy(set);
5405 test = isl_set_upper_bound_si(test, isl_dim_set, pos, -3);
5406 bounded = isl_set_is_empty(test);
5407 isl_set_free(test);
5408
5409 return bounded;
5410}
5411
5412/* Does the set "set" have a fixed (but possible parametric) value
5413 * at dimension "pos"?
5414 */
5415static isl_bool has_single_value(__isl_keep isl_setisl_map *set, int pos)
5416{
5417 int n;
5418 isl_bool single;
5419
5420 if (!set)
5421 return isl_bool_error;
5422 set = isl_set_copy(set);
5423 n = isl_set_dim(set, isl_dim_set);
5424 set = isl_set_project_out(set, isl_dim_set, pos + 1, n - (pos + 1));
5425 set = isl_set_project_out(set, isl_dim_set, 0, pos);
5426 single = isl_set_is_singleton(set);
5427 isl_set_free(set);
5428
5429 return single;
5430}
5431
5432/* Does "map" have a fixed (but possible parametric) value
5433 * at dimension "pos" of either its domain or its range?
5434 */
5435static isl_bool has_singular_src_or_dst(__isl_keep isl_map *map, int pos)
5436{
5437 isl_setisl_map *set;
5438 isl_bool single;
5439
5440 set = isl_map_domain(isl_map_copy(map));
5441 single = has_single_value(set, pos);
5442 isl_set_free(set);
5443
5444 if (single < 0 || single)
5445 return single;
5446
5447 set = isl_map_range(isl_map_copy(map));
5448 single = has_single_value(set, pos);
5449 isl_set_free(set);
5450
5451 return single;
5452}
5453
5454/* Does the edge "edge" from "graph" have bounded dependence distances
5455 * in the merged graph "merge_graph" of a selection of clusters in "c"?
5456 *
5457 * Extract the complete transformations of the source and destination
5458 * nodes of the edge, apply them to the edge constraints and
5459 * compute the differences. Finally, check if these differences are bounded
5460 * in each direction.
5461 *
5462 * If the dimension of the band is greater than the number of
5463 * dimensions that can be expected to be optimized by the edge
5464 * (based on its weight), then also allow the differences to be unbounded
5465 * in the remaining dimensions, but only if either the source or
5466 * the destination has a fixed value in that direction.
5467 * This allows a statement that produces values that are used by
5468 * several instances of another statement to be merged with that
5469 * other statement.
5470 * However, merging such clusters will introduce an inherently
5471 * large proximity distance inside the merged cluster, meaning
5472 * that proximity distances will no longer be optimized in
5473 * subsequent merges. These merges are therefore only allowed
5474 * after all other possible merges have been tried.
5475 * The first time such a merge is encountered, the weight of the edge
5476 * is replaced by a negative weight. The second time (i.e., after
5477 * all merges over edges with a non-negative weight have been tried),
5478 * the merge is allowed.
5479 */
5480static isl_bool has_bounded_distances(isl_ctx *ctx, struct isl_sched_edge *edge,
5481 struct isl_sched_graph *graph, struct isl_clustering *c,
5482 struct isl_sched_graph *merge_graph)
5483{
5484 int i, n, n_slack;
5485 isl_bool bounded;
5486 isl_map *map, *t;
5487 isl_setisl_map *dist;
5488
5489 map = isl_map_copy(edge->map);
5490 t = extract_node_transformation(ctx, edge->src, c, merge_graph);
5491 map = isl_map_apply_domain(map, t);
5492 t = extract_node_transformation(ctx, edge->dst, c, merge_graph);
5493 map = isl_map_apply_range(map, t);
5494 dist = isl_map_deltas(isl_map_copy(map));
5495
5496 bounded = isl_bool_true;
5497 n = isl_set_dim(dist, isl_dim_set);
5498 n_slack = n - edge->weight;
5499 if (edge->weight < 0)
5500 n_slack -= graph->max_weight + 1;
5501 for (i = 0; i < n; ++i) {
5502 isl_bool bounded_i, singular_i;
5503
5504 bounded_i = distance_is_bounded(dist, i);
5505 if (bounded_i < 0)
5506 goto error;
5507 if (bounded_i)
5508 continue;
5509 if (edge->weight >= 0)
5510 bounded = isl_bool_false;
5511 n_slack--;
5512 if (n_slack < 0)
5513 break;
5514 singular_i = has_singular_src_or_dst(map, i);
5515 if (singular_i < 0)
5516 goto error;
5517 if (singular_i)
5518 continue;
5519 bounded = isl_bool_false;
5520 break;
5521 }
5522 if (!bounded && i >= n && edge->weight >= 0)
5523 edge->weight -= graph->max_weight + 1;
5524 isl_map_free(map);
5525 isl_set_free(dist);
5526
5527 return bounded;
5528error:
5529 isl_map_free(map);
5530 isl_set_free(dist);
5531 return isl_bool_error;
5532}
5533
5534/* Should the clusters be merged based on the cluster schedule
5535 * in the current (and only) band of "merge_graph"?
5536 * "graph" is the original dependence graph, while "c" records
5537 * which SCCs are involved in the latest merge.
5538 *
5539 * In particular, is there at least one proximity constraint
5540 * that is optimized by the merge?
5541 *
5542 * A proximity constraint is considered to be optimized
5543 * if the dependence distances are small.
5544 */
5545static isl_bool ok_to_merge_proximity(isl_ctx *ctx,
5546 struct isl_sched_graph *graph, struct isl_clustering *c,
5547 struct isl_sched_graph *merge_graph)
5548{
5549 int i;
5550
5551 for (i = 0; i < graph->n_edge; ++i) {
5552 struct isl_sched_edge *edge = &graph->edge[i];
5553 isl_bool bounded;
5554
5555 if (!is_proximity(edge))
5556 continue;
5557 if (!c->scc_in_merge[edge->src->scc])
5558 continue;
5559 if (!c->scc_in_merge[edge->dst->scc])
5560 continue;
5561 if (c->scc_cluster[edge->dst->scc] ==
5562 c->scc_cluster[edge->src->scc])
5563 continue;
5564 bounded = has_bounded_distances(ctx, edge, graph, c,
5565 merge_graph);
5566 if (bounded < 0 || bounded)
5567 return bounded;
5568 }
5569
5570 return isl_bool_false;
5571}
5572
5573/* Should the clusters be merged based on the cluster schedule
5574 * in the current (and only) band of "merge_graph"?
5575 * "graph" is the original dependence graph, while "c" records
5576 * which SCCs are involved in the latest merge.
5577 *
5578 * If the current band is empty, then the clusters should not be merged.
5579 *
5580 * If the band depth should be maximized and the merge schedule
5581 * is incomplete (meaning that the dimension of some of the schedule
5582 * bands in the original schedule will be reduced), then the clusters
5583 * should not be merged.
5584 *
5585 * If the schedule_maximize_coincidence option is set, then check that
5586 * the number of coincident schedule dimensions is not reduced.
5587 *
5588 * Finally, only allow the merge if at least one proximity
5589 * constraint is optimized.
5590 */
5591static isl_bool ok_to_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
5592 struct isl_clustering *c, struct isl_sched_graph *merge_graph)
5593{
5594 if (merge_graph->n_total_row == merge_graph->band_start)
5595 return isl_bool_false;
5596
5597 if (isl_options_get_schedule_maximize_band_depth(ctx) &&
5598 merge_graph->n_total_row < merge_graph->maxvar)
5599 return isl_bool_false;
5600
5601 if (isl_options_get_schedule_maximize_coincidence(ctx)) {
5602 isl_bool ok;
5603
5604 ok = ok_to_merge_coincident(c, merge_graph);
5605 if (ok < 0 || !ok)
5606 return ok;
5607 }
5608
5609 return ok_to_merge_proximity(ctx, graph, c, merge_graph);
5610}
5611
5612/* Apply the schedule in "t_node" to the "n" rows starting at "first"
5613 * of the schedule in "node" and return the result.
5614 *
5615 * That is, essentially compute
5616 *
5617 * T * N(first:first+n-1)
5618 *
5619 * taking into account the constant term and the parameter coefficients
5620 * in "t_node".
5621 */
5622static __isl_give isl_mat *node_transformation(isl_ctx *ctx,
5623 struct isl_sched_node *t_node, struct isl_sched_node *node,
5624 int first, int n)
5625{
5626 int i, j;
5627 isl_mat *t;
5628 int n_row, n_col, n_param, n_var;
5629
5630 n_param = node->nparam;
5631 n_var = node->nvar;
5632 n_row = isl_mat_rows(t_node->sched);
5633 n_col = isl_mat_cols(node->sched);
5634 t = isl_mat_alloc(ctx, n_row, n_col);
5635 if (!t)
5636 return NULL((void*)0);
5637 for (i = 0; i < n_row; ++i) {
5638 isl_seq_cpy(t->row[i], t_node->sched->row[i], 1 + n_param);
5639 isl_seq_clr(t->row[i] + 1 + n_param, n_var);
5640 for (j = 0; j < n; ++j)
5641 isl_seq_addmul(t->row[i],
5642 t_node->sched->row[i][1 + n_param + j],
5643 node->sched->row[first + j],
5644 1 + n_param + n_var);
5645 }
5646 return t;
5647}
5648
5649/* Apply the cluster schedule in "t_node" to the current band
5650 * schedule of the nodes in "graph".
5651 *
5652 * In particular, replace the rows starting at band_start
5653 * by the result of applying the cluster schedule in "t_node"
5654 * to the original rows.
5655 *
5656 * The coincidence of the schedule is determined by the coincidence
5657 * of the cluster schedule.
5658 */
5659static isl_stat transform(isl_ctx *ctx, struct isl_sched_graph *graph,
5660 struct isl_sched_node *t_node)
5661{
5662 int i, j;
5663 int n_new;
5664 int start, n;
5665
5666 start = graph->band_start;
5667 n = graph->n_total_row - start;
5668
5669 n_new = isl_mat_rows(t_node->sched);
5670 for (i = 0; i < graph->n; ++i) {
5671 struct isl_sched_node *node = &graph->node[i];
5672 isl_mat *t;
5673
5674 t = node_transformation(ctx, t_node, node, start, n);
5675 node->sched = isl_mat_drop_rows(node->sched, start, n);
5676 node->sched = isl_mat_concat(node->sched, t);
5677 node->sched_map = isl_map_free(node->sched_map);
5678 if (!node->sched)
5679 return isl_stat_error;
5680 for (j = 0; j < n_new; ++j)
5681 node->coincident[start + j] = t_node->coincident[j];
5682 }
5683 graph->n_total_row -= n;
5684 graph->n_row -= n;
5685 graph->n_total_row += n_new;
5686 graph->n_row += n_new;
5687
5688 return isl_stat_ok;
5689}
5690
5691/* Merge the clusters marked for merging in "c" into a single
5692 * cluster using the cluster schedule in the current band of "merge_graph".
5693 * The representative SCC for the new cluster is the SCC with
5694 * the smallest index.
5695 *
5696 * The current band schedule of each SCC in the new cluster is obtained
5697 * by applying the schedule of the corresponding original cluster
5698 * to the original band schedule.
5699 * All SCCs in the new cluster have the same number of schedule rows.
5700 */
5701static isl_stat merge(isl_ctx *ctx, struct isl_clustering *c,
5702 struct isl_sched_graph *merge_graph)
5703{
5704 int i;
5705 int cluster = -1;
5706 isl_space *space;
5707
5708 for (i = 0; i < c->n; ++i) {
5709 struct isl_sched_node *node;
5710
5711 if (!c->scc_in_merge[i])
5712 continue;
5713 if (cluster < 0)
5714 cluster = i;
5715 space = cluster_space(&c->scc[i], c->scc_cluster[i]);
5716 if (!space)
5717 return isl_stat_error;
5718 node = graph_find_node(ctx, merge_graph, space);
5719 isl_space_free(space);
5720 if (!node)
5721 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "unable to find cluster"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 5723); return isl_stat_error; } while (0)
5722 "unable to find cluster",do { isl_handle_error(ctx, isl_error_internal, "unable to find cluster"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 5723); return isl_stat_error; } while (0)
5723 return isl_stat_error)do { isl_handle_error(ctx, isl_error_internal, "unable to find cluster"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/External/isl/isl_scheduler.c"
, 5723); return isl_stat_error; } while (0)
;
5724 if (transform(ctx, &c->scc[i], node) < 0)
5725 return isl_stat_error;
5726 c->scc_cluster[i] = cluster;
5727 }
5728
5729 return isl_stat_ok;
5730}
5731
5732/* Try and merge the clusters of SCCs marked in c->scc_in_merge
5733 * by scheduling the current cluster bands with respect to each other.
5734 *
5735 * Construct a dependence graph with a space for each cluster and
5736 * with the coordinates of each space corresponding to the schedule
5737 * dimensions of the current band of that cluster.
5738 * Construct a cluster schedule in this cluster dependence graph and
5739 * apply it to the current cluster bands if it is applicable
5740 * according to ok_to_merge.
5741 *
5742 * If the number of remaining schedule dimensions in a cluster
5743 * with a non-maximal current schedule dimension is greater than
5744 * the number of remaining schedule dimensions in clusters
5745 * with a maximal current schedule dimension, then restrict
5746 * the number of rows to be computed in the cluster schedule
5747 * to the minimal such non-maximal current schedule dimension.
5748 * Do this by adjusting merge_graph.maxvar.
5749 *
5750 * Return isl_bool_true if the clusters have effectively been merged
5751 * into a single cluster.
5752 *
5753 * Note that since the standard scheduling algorithm minimizes the maximal
5754 * distance over proximity constraints, the proximity constraints between
5755 * the merged clusters may not be optimized any further than what is
5756 * sufficient to bring the distances within the limits of the internal
5757 * proximity constraints inside the individual clusters.
5758 * It may therefore make sense to perform an additional translation step
5759 * to bring the clusters closer to each other, while maintaining
5760 * the linear part of the merging schedule found using the standard
5761 * scheduling algorithm.
5762 */
5763static isl_bool try_merge(isl_ctx *ctx, struct isl_sched_graph *graph,
5764 struct isl_clustering *c)
5765{
5766 struct isl_sched_graph merge_graph = { 0 };
5767 isl_bool merged;
5768
5769 if (init_merge_graph(ctx, graph, c, &merge_graph) < 0)
5770 goto error;
5771
5772 if (compute_maxvar(&merge_graph) < 0)
5773 goto error;
5774 if (adjust_maxvar_to_slack(ctx, &merge_graph,c) < 0)
5775 goto error;
5776 if (compute_schedule_wcc_band(ctx, &merge_graph) < 0)
5777 goto error;
5778 merged = ok_to_merge(ctx, graph, c, &merge_graph);
5779 if (merged && merge(ctx, c, &merge_graph) < 0)
5780 goto error;
5781
5782 graph_free(ctx, &merge_graph);
5783 return merged;
5784error:
5785 graph_free(ctx, &merge_graph);
5786 return isl_bool_error;
5787}
5788
5789/* Is there any edge marked "no_merge" between two SCCs that are
5790 * about to be merged (i.e., that are set in "scc_in_merge")?
5791 * "merge_edge" is the proximity edge along which the clusters of SCCs
5792 * are going to be merged.
5793 *
5794 * If there is any edge between two SCCs with a negative weight,
5795 * while the weight of "merge_edge" is non-negative, then this
5796 * means that the edge was postponed. "merge_edge" should then
5797 * also be postponed since merging along the edge with negative weight should
5798 * be postponed until all edges with non-negative weight have been tried.
5799 * Replace the weight of "merge_edge" by a negative weight as well and
5800 * tell the caller not to attempt a merge.
5801 */
5802static int any_no_merge(struct isl_sched_graph *graph, int *scc_in_merge,
5803 struct isl_sched_edge *merge_edge)
5804{
5805 int i;
5806
5807 for (i = 0; i < graph->n_edge; ++i) {
5808 struct isl_sched_edge *edge = &graph->edge[i];
5809
5810 if (!scc_in_merge[edge->src->scc])
5811 continue;
5812 if (!scc_in_merge[edge->dst->scc])
5813 continue;
5814 if (edge->no_merge)
5815 return 1;
5816 if (merge_edge->weight >= 0 && edge->weight < 0) {
5817 merge_edge->weight -= graph->max_weight + 1;
5818 return 1;
5819 }
5820 }
5821
5822 return 0;
5823}
5824
5825/* Merge the two clusters in "c" connected by the edge in "graph"
5826 * with index "edge" into a single cluster.
5827 * If it turns out to be impossible to merge these two clusters,
5828 * then mark the edge as "no_merge" such that it will not be
5829 * considered again.
5830 *
5831 * First mark all SCCs that need to be merged. This includes the SCCs
5832 * in the two clusters, but it may also include the SCCs
5833 * of intermediate clusters.
5834 * If there is already a no_merge edge between any pair of such SCCs,
5835 * then simply mark the current edge as no_merge as well.
5836 * Likewise, if any of those edges was postponed by has_bounded_distances,
5837 * then postpone the current edge as well.
5838 * Otherwise, try and merge the clusters and mark "edge" as "no_merge"
5839 * if the clusters did not end up getting merged, unless the non-merge
5840 * is due to the fact that the edge was postponed. This postponement
5841 * can be recognized by a change in weight (from non-negative to negative).
5842 */
5843static isl_stat merge_clusters_along_edge(isl_ctx *ctx,
5844 struct isl_sched_graph *graph, int edge, struct isl_clustering *c)
5845{
5846 isl_bool merged;
5847 int edge_weight = graph->edge[edge].weight;
5848
5849 if (mark_merge_sccs(ctx, graph, edge, c) < 0)
5850 return isl_stat_error;
5851
5852 if (any_no_merge(graph, c->scc_in_merge, &graph->edge[edge]))
5853 merged = isl_bool_false;
5854 else
5855 merged = try_merge(ctx, graph, c);
5856 if (merged < 0)
5857 return isl_stat_error;
5858 if (!merged && edge_weight == graph->edge[edge].weight)
5859 graph->edge[edge].no_merge = 1;
5860
5861 return isl_stat_ok;
5862}
5863
5864/* Does "node" belong to the cluster identified by "cluster"?
5865 */
5866static int node_cluster_exactly(struct isl_sched_node *node, int cluster)
5867{
5868 return node->cluster == cluster;
5869}
5870
5871/* Does "edge" connect two nodes belonging to the cluster
5872 * identified by "cluster"?
5873 */
5874static int edge_cluster_exactly(struct isl_sched_edge *edge, int cluster)
5875{
5876 return edge->src->cluster == cluster && edge->dst->cluster == cluster;
5877}
5878
5879/* Swap the schedule of "node1" and "node2".
5880 * Both nodes have been derived from the same node in a common parent graph.
5881 * Since the "coincident" field is shared with that node
5882 * in the parent graph, there is no need to also swap this field.
5883 */
5884static void swap_sched(struct isl_sched_node *node1,
5885 struct isl_sched_node *node2)
5886{
5887 isl_mat *sched;
5888 isl_map *sched_map;
5889
5890 sched = node1->sched;
5891 node1->sched = node2->sched;
5892 node2->sched = sched;
5893
5894 sched_map = node1->sched_map;
5895 node1->sched_map = node2->sched_map;
5896 node2->sched_map = sched_map;
5897}
5898
5899/* Copy the current band schedule from the SCCs that form the cluster
5900 * with index "pos" to the actual cluster at position "pos".
5901 * By construction, the index of the first SCC that belongs to the cluster
5902 * is also "pos".
5903 *
5904 * The order of the nodes inside both the SCCs and the cluster
5905 * is assumed to be same as the order in the original "graph".
5906 *
5907 * Since the SCC graphs will no longer be used after this function,
5908 * the schedules are actually swapped rather than copied.
5909 */
5910static isl_stat copy_partial(struct isl_sched_graph *graph,
5911 struct isl_clustering *c, int pos)
5912{
5913 int i, j;
5914
5915 c->cluster[pos].n_total_row = c->scc[pos].n_total_row;
5916 c->cluster[pos].n_row = c->scc[pos].n_row;
5917 c->cluster[pos].maxvar = c->scc[pos].maxvar;
5918 j = 0;
5919 for (i = 0; i < graph->n; ++i) {
5920 int k;
5921 int s;
5922
5923 if (graph->node[i].cluster != pos)
5924 continue;
5925 s = graph->node[i].scc;
5926 k = c->scc_node[s]++;
5927 swap_sched(&c->cluster[pos].node[j], &c->scc[s].node[k]);
5928 if (c->scc[s].maxvar > c->cluster[pos].maxvar)
5929 c->cluster[pos].maxvar = c->scc[s].maxvar;
5930 ++j;
5931 }
5932
5933 return isl_stat_ok;
5934}
5935
5936/* Is there a (conditional) validity dependence from node[j] to node[i],
5937 * forcing node[i] to follow node[j] or do the nodes belong to the same
5938 * cluster?
5939 */
5940static isl_bool node_follows_strong_or_same_cluster(int i, int j, void *user)
5941{
5942 struct isl_sched_graph *graph = user;
5943
5944 if (graph->node[i].cluster == graph->node[j].cluster)
5945 return isl_bool_true;
5946 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
5947}
5948
5949/* Extract the merged clusters of SCCs in "graph", sort them, and
5950 * store them in c->clusters. Update c->scc_cluster accordingly.
5951 *
5952 * First keep track of the cluster containing the SCC to which a node
5953 * belongs in the node itself.
5954 * Then extract the clusters into c->clusters, copying the current
5955 * band schedule from the SCCs that belong to the cluster.
5956 * Do this only once per cluster.
5957 *
5958 * Finally, topologically sort the clusters and update c->scc_cluster
5959 * to match the new scc numbering. While the SCCs were originally
5960 * sorted already, some SCCs that depend on some other SCCs may
5961 * have been merged with SCCs that appear before these other SCCs.
5962 * A reordering may therefore be required.
5963 */
5964static isl_stat extract_clusters(isl_ctx *ctx, struct isl_sched_graph *graph,
5965 struct isl_clustering *c)
5966{
5967 int i;
5968
5969 for (i = 0; i < graph->n; ++i)
5970 graph->node[i].cluster = c->scc_cluster[graph->node[i].scc];
5971
5972 for (i = 0; i < graph->scc; ++i) {
5973 if (c->scc_cluster[i] != i)
5974 continue;
5975 if (extract_sub_graph(ctx, graph, &node_cluster_exactly,
5976 &edge_cluster_exactly, i, &c->cluster[i]) < 0)
5977 return isl_stat_error;
5978 c->cluster[i].src_scc = -1;
5979 c->cluster[i].dst_scc = -1;
5980 if (copy_partial(graph, c, i) < 0)
5981 return isl_stat_error;
5982 }
5983
5984 if (detect_ccs(ctx, graph, &node_follows_strong_or_same_cluster) < 0)
5985 return isl_stat_error;
5986 for (i = 0; i < graph->n; ++i)
5987 c->scc_cluster[graph->node[i].scc] = graph->node[i].cluster;
5988
5989 return isl_stat_ok;
5990}
5991
5992/* Compute weights on the proximity edges of "graph" that can
5993 * be used by find_proximity to find the most appropriate
5994 * proximity edge to use to merge two clusters in "c".
5995 * The weights are also used by has_bounded_distances to determine
5996 * whether the merge should be allowed.
5997 * Store the maximum of the computed weights in graph->max_weight.
5998 *
5999 * The computed weight is a measure for the number of remaining schedule
6000 * dimensions that can still be completely aligned.
6001 * In particular, compute the number of equalities between
6002 * input dimensions and output dimensions in the proximity constraints.
6003 * The directions that are already handled by outer schedule bands
6004 * are projected out prior to determining this number.
6005 *
6006 * Edges that will never be considered by find_proximity are ignored.
6007 */
6008static isl_stat compute_weights(struct isl_sched_graph *graph,
6009 struct isl_clustering *c)
6010{
6011 int i;
6012
6013 graph->max_weight = 0;
6014
6015 for (i = 0; i < graph->n_edge; ++i) {
6016 struct isl_sched_edge *edge = &graph->edge[i];
6017 struct isl_sched_node *src = edge->src;
6018 struct isl_sched_node *dst = edge->dst;
6019 isl_basic_map *hull;
6020 int n_in, n_out;
6021
6022 if (!is_proximity(edge))
6023 continue;
6024 if (bad_cluster(&c->scc[edge->src->scc]) ||
6025 bad_cluster(&c->scc[edge->dst->scc]))
6026 continue;
6027 if (c->scc_cluster[edge->dst->scc] ==
6028 c->scc_cluster[edge->src->scc])
6029 continue;
6030
6031 hull = isl_map_affine_hull(isl_map_copy(edge->map));
6032 hull = isl_basic_map_transform_dims(hull, isl_dim_in, 0,
6033 isl_mat_copy(src->ctrans));
6034 hull = isl_basic_map_transform_dims(hull, isl_dim_out, 0,
6035 isl_mat_copy(dst->ctrans));
6036 hull = isl_basic_map_project_out(hull,
6037 isl_dim_in, 0, src->rank);
6038 hull = isl_basic_map_project_out(hull,
6039 isl_dim_out, 0, dst->rank);
6040 hull = isl_basic_map_remove_divs(hull);
6041 n_in = isl_basic_map_dim(hull, isl_dim_in);
6042 n_out = isl_basic_map_dim(hull, isl_dim_out);
6043 hull = isl_basic_map_drop_constraints_not_involving_dims(hull,
6044 isl_dim_in, 0, n_in);
6045 hull = isl_basic_map_drop_constraints_not_involving_dims(hull,
6046 isl_dim_out, 0, n_out);
6047 if (!hull)
6048 return isl_stat_error;
6049 edge->weight = hull->n_eq;
6050 isl_basic_map_free(hull);
6051
6052 if (edge->weight > graph->max_weight)
6053 graph->max_weight = edge->weight;
6054 }
6055
6056 return isl_stat_ok;
6057}
6058
6059/* Call compute_schedule_finish_band on each of the clusters in "c"
6060 * in their topological order. This order is determined by the scc
6061 * fields of the nodes in "graph".
6062 * Combine the results in a sequence expressing the topological order.
6063 *
6064 * If there is only one cluster left, then there is no need to introduce
6065 * a sequence node. Also, in this case, the cluster necessarily contains
6066 * the SCC at position 0 in the original graph and is therefore also
6067 * stored in the first cluster of "c".
6068 */
6069static __isl_give isl_schedule_node *finish_bands_clustering(
6070 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
6071 struct isl_clustering *c)
6072{
6073 int i;
6074 isl_ctx *ctx;
6075 isl_union_set_list *filters;
6076
6077 if (graph->scc == 1)
6078 return compute_schedule_finish_band(node, &c->cluster[0], 0);
6079
6080 ctx = isl_schedule_node_get_ctx(node);
6081
6082 filters = extract_sccs(ctx, graph);
6083 node = isl_schedule_node_insert_sequence(node, filters);
6084
6085 for (i = 0; i < graph->scc; ++i) {
6086 int j = c->scc_cluster[i];
6087 node = isl_schedule_node_child(node, i);
6088 node = isl_schedule_node_child(node, 0);
6089 node = compute_schedule_finish_band(node, &c->cluster[j], 0);
6090 node = isl_schedule_node_parent(node);
6091 node = isl_schedule_node_parent(node);
6092 }
6093
6094 return node;
6095}
6096
6097/* Compute a schedule for a connected dependence graph by first considering
6098 * each strongly connected component (SCC) in the graph separately and then
6099 * incrementally combining them into clusters.
6100 * Return the updated schedule node.
6101 *
6102 * Initially, each cluster consists of a single SCC, each with its
6103 * own band schedule. The algorithm then tries to merge pairs
6104 * of clusters along a proximity edge until no more suitable
6105 * proximity edges can be found. During this merging, the schedule
6106 * is maintained in the individual SCCs.
6107 * After the merging is completed, the full resulting clusters
6108 * are extracted and in finish_bands_clustering,
6109 * compute_schedule_finish_band is called on each of them to integrate
6110 * the band into "node" and to continue the computation.
6111 *
6112 * compute_weights initializes the weights that are used by find_proximity.
6113 */
6114static __isl_give isl_schedule_node *compute_schedule_wcc_clustering(
6115 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
6116{
6117 isl_ctx *ctx;
6118 struct isl_clustering c;
6119 int i;
6120
6121 ctx = isl_schedule_node_get_ctx(node);
6122
6123 if (clustering_init(ctx, &c, graph) < 0)
6124 goto error;
6125
6126 if (compute_weights(graph, &c) < 0)
6127 goto error;
6128
6129 for (;;) {
6130 i = find_proximity(graph, &c);
6131 if (i < 0)
6132 goto error;
6133 if (i >= graph->n_edge)
6134 break;
6135 if (merge_clusters_along_edge(ctx, graph, i, &c) < 0)
6136 goto error;
6137 }
6138
6139 if (extract_clusters(ctx, graph, &c) < 0)
6140 goto error;
6141
6142 node = finish_bands_clustering(node, graph, &c);
6143
6144 clustering_free(ctx, &c);
6145 return node;
6146error:
6147 clustering_free(ctx, &c);
6148 return isl_schedule_node_free(node);
6149}
6150
6151/* Compute a schedule for a connected dependence graph and return
6152 * the updated schedule node.
6153 *
6154 * If Feautrier's algorithm is selected, we first recursively try to satisfy
6155 * as many validity dependences as possible. When all validity dependences
6156 * are satisfied we extend the schedule to a full-dimensional schedule.
6157 *
6158 * Call compute_schedule_wcc_whole or compute_schedule_wcc_clustering
6159 * depending on whether the user has selected the option to try and
6160 * compute a schedule for the entire (weakly connected) component first.
6161 * If there is only a single strongly connected component (SCC), then
6162 * there is no point in trying to combine SCCs
6163 * in compute_schedule_wcc_clustering, so compute_schedule_wcc_whole
6164 * is called instead.
6165 */
6166static __isl_give isl_schedule_node *compute_schedule_wcc(
6167 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
6168{
6169 isl_ctx *ctx;
6170
6171 if (!node)
6172 return NULL((void*)0);
6173
6174 ctx = isl_schedule_node_get_ctx(node);
6175 if (detect_sccs(ctx, graph) < 0)
6176 return isl_schedule_node_free(node);
6177
6178 if (compute_maxvar(graph) < 0)
6179 return isl_schedule_node_free(node);
6180
6181 if (need_feautrier_step(ctx, graph))
6182 return compute_schedule_wcc_feautrier(node, graph);
6183
6184 if (graph->scc <= 1 || isl_options_get_schedule_whole_component(ctx))
6185 return compute_schedule_wcc_whole(node, graph);
6186 else
6187 return compute_schedule_wcc_clustering(node, graph);
6188}
6189
6190/* Compute a schedule for each group of nodes identified by node->scc
6191 * separately and then combine them in a sequence node (or as set node
6192 * if graph->weak is set) inserted at position "node" of the schedule tree.
6193 * Return the updated schedule node.
6194 *
6195 * If "wcc" is set then each of the groups belongs to a single
6196 * weakly connected component in the dependence graph so that
6197 * there is no need for compute_sub_schedule to look for weakly
6198 * connected components.
6199 */
6200static __isl_give isl_schedule_node *compute_component_schedule(
6201 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
6202 int wcc)
6203{
6204 int component;
6205 isl_ctx *ctx;
6206 isl_union_set_list *filters;
6207
6208 if (!node)
6209 return NULL((void*)0);
6210 ctx = isl_schedule_node_get_ctx(node);
6211
6212 filters = extract_sccs(ctx, graph);
6213 if (graph->weak)
6214 node = isl_schedule_node_insert_set(node, filters);
6215 else
6216 node = isl_schedule_node_insert_sequence(node, filters);
6217
6218 for (component = 0; component < graph->scc; ++component) {
6219 node = isl_schedule_node_child(node, component);
6220 node = isl_schedule_node_child(node, 0);
6221 node = compute_sub_schedule(node, ctx, graph,
6222 &node_scc_exactly,
6223 &edge_scc_exactly, component, wcc);
6224 node = isl_schedule_node_parent(node);
6225 node = isl_schedule_node_parent(node);
6226 }
6227
6228 return node;
6229}
6230
6231/* Compute a schedule for the given dependence graph and insert it at "node".
6232 * Return the updated schedule node.
6233 *
6234 * We first check if the graph is connected (through validity and conditional
6235 * validity dependences) and, if not, compute a schedule
6236 * for each component separately.
6237 * If the schedule_serialize_sccs option is set, then we check for strongly
6238 * connected components instead and compute a separate schedule for
6239 * each such strongly connected component.
6240 */
6241static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
6242 struct isl_sched_graph *graph)
6243{
6244 isl_ctx *ctx;
6245
6246 if (!node)
6247 return NULL((void*)0);
6248
6249 ctx = isl_schedule_node_get_ctx(node);
6250 if (isl_options_get_schedule_serialize_sccs(ctx)) {
6251 if (detect_sccs(ctx, graph) < 0)
6252 return isl_schedule_node_free(node);
6253 } else {
6254 if (detect_wccs(ctx, graph) < 0)
6255 return isl_schedule_node_free(node);
6256 }
6257
6258 if (graph->scc > 1)
6259 return compute_component_schedule(node, graph, 1);
6260
6261 return compute_schedule_wcc(node, graph);
6262}
6263
6264/* Compute a schedule on sc->domain that respects the given schedule
6265 * constraints.
6266 *
6267 * In particular, the schedule respects all the validity dependences.
6268 * If the default isl scheduling algorithm is used, it tries to minimize
6269 * the dependence distances over the proximity dependences.
6270 * If Feautrier's scheduling algorithm is used, the proximity dependence
6271 * distances are only minimized during the extension to a full-dimensional
6272 * schedule.
6273 *
6274 * If there are any condition and conditional validity dependences,
6275 * then the conditional validity dependences may be violated inside
6276 * a tilable band, provided they have no adjacent non-local
6277 * condition dependences.
6278 */
6279__isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
6280 __isl_take isl_schedule_constraints *sc)
6281{
6282 isl_ctx *ctx = isl_schedule_constraints_get_ctx(sc);
6283 struct isl_sched_graph graph = { 0 };
6284 isl_schedule *sched;
6285 isl_schedule_node *node;
6286 isl_union_set *domain;
6287
6288 sc = isl_schedule_constraints_align_params(sc);
6289
6290 domain = isl_schedule_constraints_get_domain(sc);
6291 if (isl_union_set_n_set(domain) == 0) {
6292 isl_schedule_constraints_free(sc);
6293 return isl_schedule_from_domain(domain);
6294 }
6295
6296 if (graph_init(&graph, sc) < 0)
6297 domain = isl_union_set_free(domain);
6298
6299 node = isl_schedule_node_from_domain(domain);
6300 node = isl_schedule_node_child(node, 0);
6301 if (graph.n > 0)
6302 node = compute_schedule(node, &graph);
6303 sched = isl_schedule_node_get_schedule(node);
6304 isl_schedule_node_free(node);
6305
6306 graph_free(ctx, &graph);
6307 isl_schedule_constraints_free(sc);
6308
6309 return sched;
6310}
6311
6312/* Compute a schedule for the given union of domains that respects
6313 * all the validity dependences and minimizes
6314 * the dependence distances over the proximity dependences.
6315 *
6316 * This function is kept for backward compatibility.
6317 */
6318__isl_give isl_schedule *isl_union_set_compute_schedule(
6319 __isl_take isl_union_set *domain,
6320 __isl_take isl_union_map *validity,
6321 __isl_take isl_union_map *proximity)
6322{
6323 isl_schedule_constraints *sc;
6324
6325 sc = isl_schedule_constraints_on_domain(domain);
6326 sc = isl_schedule_constraints_set_validity(sc, validity);
6327 sc = isl_schedule_constraints_set_proximity(sc, proximity);
6328
6329 return isl_schedule_constraints_compute_schedule(sc);
6330}