Bug Summary

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