Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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