Bug Summary

File:polly/lib/External/isl/isl_scheduler.c
Location:line 2417, column 2
Description:Value stored to 'nrow' is never read

Annotated Source Code

1/*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015 Sven Verdoolaege
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12 */
13
14#include <isl_ctx_private.h>
15#include <isl_map_private.h>
16#include <isl_space_private.h>
17#include <isl_aff_private.h>
18#include <isl/hash.h>
19#include <isl/constraint.h>
20#include <isl/schedule.h>
21#include <isl/schedule_node.h>
22#include <isl_mat_private.h>
23#include <isl_vec_private.h>
24#include <isl/set.h>
25#include <isl/union_set.h>
26#include <isl_seq.h>
27#include <isl_tab.h>
28#include <isl_dim_map.h>
29#include <isl/map_to_basic_set.h>
30#include <isl_sort.h>
31#include <isl_options_private.h>
32#include <isl_tarjan.h>
33#include <isl_morph.h>
34
35/*
36 * The scheduling algorithm implemented in this file was inspired by
37 * Bondhugula et al., "Automatic Transformations for Communication-Minimized
38 * Parallelization and Locality Optimization in the Polyhedral Model".
39 */
40
41enum isl_edge_type {
42 isl_edge_validity = 0,
43 isl_edge_first = isl_edge_validity,
44 isl_edge_coincidence,
45 isl_edge_condition,
46 isl_edge_conditional_validity,
47 isl_edge_proximity,
48 isl_edge_last = isl_edge_proximity
49};
50
51/* The constraints that need to be satisfied by a schedule on "domain".
52 *
53 * "context" specifies extra constraints on the parameters.
54 *
55 * "validity" constraints map domain elements i to domain elements
56 * that should be scheduled after i. (Hard constraint)
57 * "proximity" constraints map domain elements i to domains elements
58 * that should be scheduled as early as possible after i (or before i).
59 * (Soft constraint)
60 *
61 * "condition" and "conditional_validity" constraints map possibly "tagged"
62 * domain elements i -> s to "tagged" domain elements j -> t.
63 * The elements of the "conditional_validity" constraints, but without the
64 * tags (i.e., the elements i -> j) are treated as validity constraints,
65 * except that during the construction of a tilable band,
66 * the elements of the "conditional_validity" constraints may be violated
67 * provided that all adjacent elements of the "condition" constraints
68 * are local within the band.
69 * A dependence is local within a band if domain and range are mapped
70 * to the same schedule point by the band.
71 */
72struct isl_schedule_constraints {
73 isl_union_set *domain;
74 isl_setisl_map *context;
75
76 isl_union_map *constraint[isl_edge_last + 1];
77};
78
79__isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
80 __isl_keep isl_schedule_constraints *sc)
81{
82 isl_ctx *ctx;
83 isl_schedule_constraints *sc_copy;
84 enum isl_edge_type i;
85
86 ctx = isl_union_set_get_ctx(sc->domain);
87 sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints)((struct isl_schedule_constraints *)isl_calloc_or_die(ctx, 1,
sizeof(struct isl_schedule_constraints)));
88 if (!sc_copy)
89 return NULL((void*)0);
90
91 sc_copy->domain = isl_union_set_copy(sc->domain);
92 sc_copy->context = isl_set_copy(sc->context);
93 if (!sc_copy->domain || !sc_copy->context)
94 return isl_schedule_constraints_free(sc_copy);
95
96 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
97 sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);
98 if (!sc_copy->constraint[i])
99 return isl_schedule_constraints_free(sc_copy);
100 }
101
102 return sc_copy;
103}
104
105
106/* Construct an isl_schedule_constraints object for computing a schedule
107 * on "domain". The initial object does not impose any constraints.
108 */
109__isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
110 __isl_take isl_union_set *domain)
111{
112 isl_ctx *ctx;
113 isl_space *space;
114 isl_schedule_constraints *sc;
115 isl_union_map *empty;
116 enum isl_edge_type i;
117
118 if (!domain)
119 return NULL((void*)0);
120
121 ctx = isl_union_set_get_ctx(domain);
122 sc = isl_calloc_type(ctx, struct isl_schedule_constraints)((struct isl_schedule_constraints *)isl_calloc_or_die(ctx, 1,
sizeof(struct isl_schedule_constraints)));
123 if (!sc)
124 goto error;
125
126 space = isl_union_set_get_space(domain);
127 sc->domain = domain;
128 sc->context = isl_set_universe(isl_space_copy(space));
129 empty = isl_union_map_empty(space);
130 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
131 sc->constraint[i] = isl_union_map_copy(empty);
132 if (!sc->constraint[i])
133 sc->domain = isl_union_set_free(sc->domain);
134 }
135 isl_union_map_free(empty);
136
137 if (!sc->domain || !sc->context)
138 return isl_schedule_constraints_free(sc);
139
140 return sc;
141error:
142 isl_union_set_free(domain);
143 return NULL((void*)0);
144}
145
146/* Replace the context of "sc" by "context".
147 */
148__isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
149 __isl_take isl_schedule_constraints *sc, __isl_take isl_setisl_map *context)
150{
151 if (!sc || !context)
152 goto error;
153
154 isl_set_free(sc->context);
155 sc->context = context;
156
157 return sc;
158error:
159 isl_schedule_constraints_free(sc);
160 isl_set_free(context);
161 return NULL((void*)0);
162}
163
164/* Replace the validity constraints of "sc" by "validity".
165 */
166__isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
167 __isl_take isl_schedule_constraints *sc,
168 __isl_take isl_union_map *validity)
169{
170 if (!sc || !validity)
171 goto error;
172
173 isl_union_map_free(sc->constraint[isl_edge_validity]);
174 sc->constraint[isl_edge_validity] = validity;
175
176 return sc;
177error:
178 isl_schedule_constraints_free(sc);
179 isl_union_map_free(validity);
180 return NULL((void*)0);
181}
182
183/* Replace the coincidence constraints of "sc" by "coincidence".
184 */
185__isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
186 __isl_take isl_schedule_constraints *sc,
187 __isl_take isl_union_map *coincidence)
188{
189 if (!sc || !coincidence)
190 goto error;
191
192 isl_union_map_free(sc->constraint[isl_edge_coincidence]);
193 sc->constraint[isl_edge_coincidence] = coincidence;
194
195 return sc;
196error:
197 isl_schedule_constraints_free(sc);
198 isl_union_map_free(coincidence);
199 return NULL((void*)0);
200}
201
202/* Replace the proximity constraints of "sc" by "proximity".
203 */
204__isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
205 __isl_take isl_schedule_constraints *sc,
206 __isl_take isl_union_map *proximity)
207{
208 if (!sc || !proximity)
209 goto error;
210
211 isl_union_map_free(sc->constraint[isl_edge_proximity]);
212 sc->constraint[isl_edge_proximity] = proximity;
213
214 return sc;
215error:
216 isl_schedule_constraints_free(sc);
217 isl_union_map_free(proximity);
218 return NULL((void*)0);
219}
220
221/* Replace the conditional validity constraints of "sc" by "condition"
222 * and "validity".
223 */
224__isl_give isl_schedule_constraints *
225isl_schedule_constraints_set_conditional_validity(
226 __isl_take isl_schedule_constraints *sc,
227 __isl_take isl_union_map *condition,
228 __isl_take isl_union_map *validity)
229{
230 if (!sc || !condition || !validity)
231 goto error;
232
233 isl_union_map_free(sc->constraint[isl_edge_condition]);
234 sc->constraint[isl_edge_condition] = condition;
235 isl_union_map_free(sc->constraint[isl_edge_conditional_validity]);
236 sc->constraint[isl_edge_conditional_validity] = validity;
237
238 return sc;
239error:
240 isl_schedule_constraints_free(sc);
241 isl_union_map_free(condition);
242 isl_union_map_free(validity);
243 return NULL((void*)0);
244}
245
246__isl_null isl_schedule_constraints *isl_schedule_constraints_free(
247 __isl_take isl_schedule_constraints *sc)
248{
249 enum isl_edge_type i;
250
251 if (!sc)
252 return NULL((void*)0);
253
254 isl_union_set_free(sc->domain);
255 isl_set_free(sc->context);
256 for (i = isl_edge_first; i <= isl_edge_last; ++i)
257 isl_union_map_free(sc->constraint[i]);
258
259 free(sc);
260
261 return NULL((void*)0);
262}
263
264isl_ctx *isl_schedule_constraints_get_ctx(
265 __isl_keep isl_schedule_constraints *sc)
266{
267 return sc ? isl_union_set_get_ctx(sc->domain) : NULL((void*)0);
268}
269
270/* Return the validity constraints of "sc".
271 */
272__isl_give isl_union_map *isl_schedule_constraints_get_validity(
273 __isl_keep isl_schedule_constraints *sc)
274{
275 if (!sc)
276 return NULL((void*)0);
277
278 return isl_union_map_copy(sc->constraint[isl_edge_validity]);
279}
280
281/* Return the coincidence constraints of "sc".
282 */
283__isl_give isl_union_map *isl_schedule_constraints_get_coincidence(
284 __isl_keep isl_schedule_constraints *sc)
285{
286 if (!sc)
287 return NULL((void*)0);
288
289 return isl_union_map_copy(sc->constraint[isl_edge_coincidence]);
290}
291
292/* Return the conditional validity constraints of "sc".
293 */
294__isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(
295 __isl_keep isl_schedule_constraints *sc)
296{
297 if (!sc)
298 return NULL((void*)0);
299
300 return
301 isl_union_map_copy(sc->constraint[isl_edge_conditional_validity]);
302}
303
304/* Return the conditions for the conditional validity constraints of "sc".
305 */
306__isl_give isl_union_map *
307isl_schedule_constraints_get_conditional_validity_condition(
308 __isl_keep isl_schedule_constraints *sc)
309{
310 if (!sc)
311 return NULL((void*)0);
312
313 return isl_union_map_copy(sc->constraint[isl_edge_condition]);
314}
315
316void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc)
317{
318 if (!sc)
319 return;
320
321 fprintf(stderr, "domain: ")__fprintf_chk (stderr, 2 - 1, "domain: ");
322 isl_union_set_dump(sc->domain);
323 fprintf(stderr, "context: ")__fprintf_chk (stderr, 2 - 1, "context: ");
324 isl_set_dump(sc->context);
325 fprintf(stderr, "validity: ")__fprintf_chk (stderr, 2 - 1, "validity: ");
326 isl_union_map_dump(sc->constraint[isl_edge_validity]);
327 fprintf(stderr, "proximity: ")__fprintf_chk (stderr, 2 - 1, "proximity: ");
328 isl_union_map_dump(sc->constraint[isl_edge_proximity]);
329 fprintf(stderr, "coincidence: ")__fprintf_chk (stderr, 2 - 1, "coincidence: ");
330 isl_union_map_dump(sc->constraint[isl_edge_coincidence]);
331 fprintf(stderr, "condition: ")__fprintf_chk (stderr, 2 - 1, "condition: ");
332 isl_union_map_dump(sc->constraint[isl_edge_condition]);
333 fprintf(stderr, "conditional_validity: ")__fprintf_chk (stderr, 2 - 1, "conditional_validity: ");
334 isl_union_map_dump(sc->constraint[isl_edge_conditional_validity]);
335}
336
337/* Align the parameters of the fields of "sc".
338 */
339static __isl_give isl_schedule_constraints *
340isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)
341{
342 isl_space *space;
343 enum isl_edge_type i;
344
345 if (!sc)
346 return NULL((void*)0);
347
348 space = isl_union_set_get_space(sc->domain);
349 space = isl_space_align_params(space, isl_set_get_space(sc->context));
350 for (i = isl_edge_first; i <= isl_edge_last; ++i)
351 space = isl_space_align_params(space,
352 isl_union_map_get_space(sc->constraint[i]));
353
354 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
355 sc->constraint[i] = isl_union_map_align_params(
356 sc->constraint[i], isl_space_copy(space));
357 if (!sc->constraint[i])
358 space = isl_space_free(space);
359 }
360 sc->context = isl_set_align_params(sc->context, isl_space_copy(space));
361 sc->domain = isl_union_set_align_params(sc->domain, space);
362 if (!sc->context || !sc->domain)
363 return isl_schedule_constraints_free(sc);
364
365 return sc;
366}
367
368/* Return the total number of isl_maps in the constraints of "sc".
369 */
370static __isl_give int isl_schedule_constraints_n_map(
371 __isl_keep isl_schedule_constraints *sc)
372{
373 enum isl_edge_type i;
374 int n = 0;
375
376 for (i = isl_edge_first; i <= isl_edge_last; ++i)
377 n += isl_union_map_n_map(sc->constraint[i]);
378
379 return n;
380}
381
382/* Internal information about a node that is used during the construction
383 * of a schedule.
384 * space represents the space in which the domain lives
385 * sched is a matrix representation of the schedule being constructed
386 * for this node; if compressed is set, then this schedule is
387 * defined over the compressed domain space
388 * sched_map is an isl_map representation of the same (partial) schedule
389 * sched_map may be NULL; if compressed is set, then this map
390 * is defined over the uncompressed domain space
391 * rank is the number of linearly independent rows in the linear part
392 * of sched
393 * the columns of cmap represent a change of basis for the schedule
394 * coefficients; the first rank columns span the linear part of
395 * the schedule rows
396 * cinv is the inverse of cmap.
397 * start is the first variable in the LP problem in the sequences that
398 * represents the schedule coefficients of this node
399 * nvar is the dimension of the domain
400 * nparam is the number of parameters or 0 if we are not constructing
401 * a parametric schedule
402 *
403 * If compressed is set, then hull represents the constraints
404 * that were used to derive the compression, while compress and
405 * decompress map the original space to the compressed space and
406 * vice versa.
407 *
408 * scc is the index of SCC (or WCC) this node belongs to
409 *
410 * coincident contains a boolean for each of the rows of the schedule,
411 * indicating whether the corresponding scheduling dimension satisfies
412 * the coincidence constraints in the sense that the corresponding
413 * dependence distances are zero.
414 */
415struct isl_sched_node {
416 isl_space *space;
417 int compressed;
418 isl_setisl_map *hull;
419 isl_multi_aff *compress;
420 isl_multi_aff *decompress;
421 isl_mat *sched;
422 isl_map *sched_map;
423 int rank;
424 isl_mat *cmap;
425 isl_mat *cinv;
426 int start;
427 int nvar;
428 int nparam;
429
430 int scc;
431
432 int *coincident;
433};
434
435static int node_has_space(const void *entry, const void *val)
436{
437 struct isl_sched_node *node = (struct isl_sched_node *)entry;
438 isl_space *dim = (isl_space *)val;
439
440 return isl_space_is_equal(node->space, dim);
441}
442
443static int node_scc_exactly(struct isl_sched_node *node, int scc)
444{
445 return node->scc == scc;
446}
447
448static int node_scc_at_most(struct isl_sched_node *node, int scc)
449{
450 return node->scc <= scc;
451}
452
453static int node_scc_at_least(struct isl_sched_node *node, int scc)
454{
455 return node->scc >= scc;
456}
457
458/* An edge in the dependence graph. An edge may be used to
459 * ensure validity of the generated schedule, to minimize the dependence
460 * distance or both
461 *
462 * map is the dependence relation, with i -> j in the map if j depends on i
463 * tagged_condition and tagged_validity contain the union of all tagged
464 * condition or conditional validity dependence relations that
465 * specialize the dependence relation "map"; that is,
466 * if (i -> a) -> (j -> b) is an element of "tagged_condition"
467 * or "tagged_validity", then i -> j is an element of "map".
468 * If these fields are NULL, then they represent the empty relation.
469 * src is the source node
470 * dst is the sink node
471 * validity is set if the edge is used to ensure correctness
472 * coincidence is used to enforce zero dependence distances
473 * proximity is set if the edge is used to minimize dependence distances
474 * condition is set if the edge represents a condition
475 * for a conditional validity schedule constraint
476 * local can only be set for condition edges and indicates that
477 * the dependence distance over the edge should be zero
478 * conditional_validity is set if the edge is used to conditionally
479 * ensure correctness
480 *
481 * For validity edges, start and end mark the sequence of inequality
482 * constraints in the LP problem that encode the validity constraint
483 * corresponding to this edge.
484 */
485struct isl_sched_edge {
486 isl_map *map;
487 isl_union_map *tagged_condition;
488 isl_union_map *tagged_validity;
489
490 struct isl_sched_node *src;
491 struct isl_sched_node *dst;
492
493 unsigned validity : 1;
494 unsigned coincidence : 1;
495 unsigned proximity : 1;
496 unsigned local : 1;
497 unsigned condition : 1;
498 unsigned conditional_validity : 1;
499
500 int start;
501 int end;
502};
503
504/* Internal information about the dependence graph used during
505 * the construction of the schedule.
506 *
507 * intra_hmap is a cache, mapping dependence relations to their dual,
508 * for dependences from a node to itself
509 * inter_hmap is a cache, mapping dependence relations to their dual,
510 * for dependences between distinct nodes
511 * if compression is involved then the key for these maps
512 * it the original, uncompressed dependence relation, while
513 * the value is the dual of the compressed dependence relation.
514 *
515 * n is the number of nodes
516 * node is the list of nodes
517 * maxvar is the maximal number of variables over all nodes
518 * max_row is the allocated number of rows in the schedule
519 * n_row is the current (maximal) number of linearly independent
520 * rows in the node schedules
521 * n_total_row is the current number of rows in the node schedules
522 * band_start is the starting row in the node schedules of the current band
523 * root is set if this graph is the original dependence graph,
524 * without any splitting
525 *
526 * sorted contains a list of node indices sorted according to the
527 * SCC to which a node belongs
528 *
529 * n_edge is the number of edges
530 * edge is the list of edges
531 * max_edge contains the maximal number of edges of each type;
532 * in particular, it contains the number of edges in the inital graph.
533 * edge_table contains pointers into the edge array, hashed on the source
534 * and sink spaces; there is one such table for each type;
535 * a given edge may be referenced from more than one table
536 * if the corresponding relation appears in more than one of the
537 * sets of dependences
538 *
539 * node_table contains pointers into the node array, hashed on the space
540 *
541 * region contains a list of variable sequences that should be non-trivial
542 *
543 * lp contains the (I)LP problem used to obtain new schedule rows
544 *
545 * src_scc and dst_scc are the source and sink SCCs of an edge with
546 * conflicting constraints
547 *
548 * scc represents the number of components
549 * weak is set if the components are weakly connected
550 */
551struct isl_sched_graph {
552 isl_map_to_basic_set *intra_hmap;
553 isl_map_to_basic_set *inter_hmap;
554
555 struct isl_sched_node *node;
556 int n;
557 int maxvar;
558 int max_row;
559 int n_row;
560
561 int *sorted;
562
563 int n_total_row;
564 int band_start;
565
566 int root;
567
568 struct isl_sched_edge *edge;
569 int n_edge;
570 int max_edge[isl_edge_last + 1];
571 struct isl_hash_table *edge_table[isl_edge_last + 1];
572
573 struct isl_hash_table *node_table;
574 struct isl_region *region;
575
576 isl_basic_setisl_basic_map *lp;
577
578 int src_scc;
579 int dst_scc;
580
581 int scc;
582 int weak;
583};
584
585/* Initialize node_table based on the list of nodes.
586 */
587static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
588{
589 int i;
590
591 graph->node_table = isl_hash_table_alloc(ctx, graph->n);
592 if (!graph->node_table)
593 return -1;
594
595 for (i = 0; i < graph->n; ++i) {
596 struct isl_hash_table_entry *entry;
597 uint32_t hash;
598
599 hash = isl_space_get_hash(graph->node[i].space);
600 entry = isl_hash_table_find(ctx, graph->node_table, hash,
601 &node_has_space,
602 graph->node[i].space, 1);
603 if (!entry)
604 return -1;
605 entry->data = &graph->node[i];
606 }
607
608 return 0;
609}
610
611/* Return a pointer to the node that lives within the given space,
612 * or NULL if there is no such node.
613 */
614static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
615 struct isl_sched_graph *graph, __isl_keep isl_space *dim)
616{
617 struct isl_hash_table_entry *entry;
618 uint32_t hash;
619
620 hash = isl_space_get_hash(dim);
621 entry = isl_hash_table_find(ctx, graph->node_table, hash,
622 &node_has_space, dim, 0);
623
624 return entry ? entry->data : NULL((void*)0);
625}
626
627static int edge_has_src_and_dst(const void *entry, const void *val)
628{
629 const struct isl_sched_edge *edge = entry;
630 const struct isl_sched_edge *temp = val;
631
632 return edge->src == temp->src && edge->dst == temp->dst;
633}
634
635/* Add the given edge to graph->edge_table[type].
636 */
637static isl_stat graph_edge_table_add(isl_ctx *ctx,
638 struct isl_sched_graph *graph, enum isl_edge_type type,
639 struct isl_sched_edge *edge)
640{
641 struct isl_hash_table_entry *entry;
642 uint32_t hash;
643
644 hash = isl_hash_init()(2166136261u);
645 hash = isl_hash_builtin(hash, edge->src)isl_hash_mem(hash, &edge->src, sizeof(edge->src));
646 hash = isl_hash_builtin(hash, edge->dst)isl_hash_mem(hash, &edge->dst, sizeof(edge->dst));
647 entry = isl_hash_table_find(ctx, graph->edge_table[type], hash,
648 &edge_has_src_and_dst, edge, 1);
649 if (!entry)
650 return isl_stat_error;
651 entry->data = edge;
652
653 return isl_stat_ok;
654}
655
656/* Allocate the edge_tables based on the maximal number of edges of
657 * each type.
658 */
659static int graph_init_edge_tables(isl_ctx *ctx, struct isl_sched_graph *graph)
660{
661 int i;
662
663 for (i = 0; i <= isl_edge_last; ++i) {
664 graph->edge_table[i] = isl_hash_table_alloc(ctx,
665 graph->max_edge[i]);
666 if (!graph->edge_table[i])
667 return -1;
668 }
669
670 return 0;
671}
672
673/* If graph->edge_table[type] contains an edge from the given source
674 * to the given destination, then return the hash table entry of this edge.
675 * Otherwise, return NULL.
676 */
677static struct isl_hash_table_entry *graph_find_edge_entry(
678 struct isl_sched_graph *graph,
679 enum isl_edge_type type,
680 struct isl_sched_node *src, struct isl_sched_node *dst)
681{
682 isl_ctx *ctx = isl_space_get_ctx(src->space);
683 uint32_t hash;
684 struct isl_sched_edge temp = { .src = src, .dst = dst };
685
686 hash = isl_hash_init()(2166136261u);
687 hash = isl_hash_builtin(hash, temp.src)isl_hash_mem(hash, &temp.src, sizeof(temp.src));
688 hash = isl_hash_builtin(hash, temp.dst)isl_hash_mem(hash, &temp.dst, sizeof(temp.dst));
689 return isl_hash_table_find(ctx, graph->edge_table[type], hash,
690 &edge_has_src_and_dst, &temp, 0);
691}
692
693
694/* If graph->edge_table[type] contains an edge from the given source
695 * to the given destination, then return this edge.
696 * Otherwise, return NULL.
697 */
698static struct isl_sched_edge *graph_find_edge(struct isl_sched_graph *graph,
699 enum isl_edge_type type,
700 struct isl_sched_node *src, struct isl_sched_node *dst)
701{
702 struct isl_hash_table_entry *entry;
703
704 entry = graph_find_edge_entry(graph, type, src, dst);
705 if (!entry)
706 return NULL((void*)0);
707
708 return entry->data;
709}
710
711/* Check whether the dependence graph has an edge of the given type
712 * between the given two nodes.
713 */
714static isl_bool graph_has_edge(struct isl_sched_graph *graph,
715 enum isl_edge_type type,
716 struct isl_sched_node *src, struct isl_sched_node *dst)
717{
718 struct isl_sched_edge *edge;
719 isl_bool empty;
720
721 edge = graph_find_edge(graph, type, src, dst);
722 if (!edge)
723 return 0;
724
725 empty = isl_map_plain_is_empty(edge->map);
726 if (empty < 0)
727 return isl_bool_error;
728
729 return !empty;
730}
731
732/* Look for any edge with the same src, dst and map fields as "model".
733 *
734 * Return the matching edge if one can be found.
735 * Return "model" if no matching edge is found.
736 * Return NULL on error.
737 */
738static struct isl_sched_edge *graph_find_matching_edge(
739 struct isl_sched_graph *graph, struct isl_sched_edge *model)
740{
741 enum isl_edge_type i;
742 struct isl_sched_edge *edge;
743
744 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
745 int is_equal;
746
747 edge = graph_find_edge(graph, i, model->src, model->dst);
748 if (!edge)
749 continue;
750 is_equal = isl_map_plain_is_equal(model->map, edge->map);
751 if (is_equal < 0)
752 return NULL((void*)0);
753 if (is_equal)
754 return edge;
755 }
756
757 return model;
758}
759
760/* Remove the given edge from all the edge_tables that refer to it.
761 */
762static void graph_remove_edge(struct isl_sched_graph *graph,
763 struct isl_sched_edge *edge)
764{
765 isl_ctx *ctx = isl_map_get_ctx(edge->map);
766 enum isl_edge_type i;
767
768 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
769 struct isl_hash_table_entry *entry;
770
771 entry = graph_find_edge_entry(graph, i, edge->src, edge->dst);
772 if (!entry)
773 continue;
774 if (entry->data != edge)
775 continue;
776 isl_hash_table_remove(ctx, graph->edge_table[i], entry);
777 }
778}
779
780/* Check whether the dependence graph has any edge
781 * between the given two nodes.
782 */
783static isl_bool graph_has_any_edge(struct isl_sched_graph *graph,
784 struct isl_sched_node *src, struct isl_sched_node *dst)
785{
786 enum isl_edge_type i;
787 isl_bool r;
788
789 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
790 r = graph_has_edge(graph, i, src, dst);
791 if (r < 0 || r)
792 return r;
793 }
794
795 return r;
796}
797
798/* Check whether the dependence graph has a validity edge
799 * between the given two nodes.
800 *
801 * Conditional validity edges are essentially validity edges that
802 * can be ignored if the corresponding condition edges are iteration private.
803 * Here, we are only checking for the presence of validity
804 * edges, so we need to consider the conditional validity edges too.
805 * In particular, this function is used during the detection
806 * of strongly connected components and we cannot ignore
807 * conditional validity edges during this detection.
808 */
809static isl_bool graph_has_validity_edge(struct isl_sched_graph *graph,
810 struct isl_sched_node *src, struct isl_sched_node *dst)
811{
812 isl_bool r;
813
814 r = graph_has_edge(graph, isl_edge_validity, src, dst);
815 if (r < 0 || r)
816 return r;
817
818 return graph_has_edge(graph, isl_edge_conditional_validity, src, dst);
819}
820
821static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
822 int n_node, int n_edge)
823{
824 int i;
825
826 graph->n = n_node;
827 graph->n_edge = n_edge;
828 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)));
829 graph->sorted = isl_calloc_array(ctx, int, graph->n)((int *)isl_calloc_or_die(ctx, graph->n, sizeof(int)));
830 graph->region = isl_alloc_array(ctx, struct isl_region, graph->n)((struct isl_region *)isl_malloc_or_die(ctx, (graph->n)*sizeof
(struct isl_region)));
831 graph->edge = isl_calloc_array(ctx,((struct isl_sched_edge *)isl_calloc_or_die(ctx, graph->n_edge
, sizeof(struct isl_sched_edge)))
832 struct isl_sched_edge, graph->n_edge)((struct isl_sched_edge *)isl_calloc_or_die(ctx, graph->n_edge
, sizeof(struct isl_sched_edge)));
833
834 graph->intra_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
835 graph->inter_hmap = isl_map_to_basic_set_alloc(ctx, 2 * n_edge);
836
837 if (!graph->node || !graph->region || (graph->n_edge && !graph->edge) ||
838 !graph->sorted)
839 return -1;
840
841 for(i = 0; i < graph->n; ++i)
842 graph->sorted[i] = i;
843
844 return 0;
845}
846
847static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
848{
849 int i;
850
851 isl_map_to_basic_set_free(graph->intra_hmap);
852 isl_map_to_basic_set_free(graph->inter_hmap);
853
854 if (graph->node)
855 for (i = 0; i < graph->n; ++i) {
856 isl_space_free(graph->node[i].space);
857 isl_set_free(graph->node[i].hull);
858 isl_multi_aff_free(graph->node[i].compress);
859 isl_multi_aff_free(graph->node[i].decompress);
860 isl_mat_free(graph->node[i].sched);
861 isl_map_free(graph->node[i].sched_map);
862 isl_mat_free(graph->node[i].cmap);
863 isl_mat_free(graph->node[i].cinv);
864 if (graph->root)
865 free(graph->node[i].coincident);
866 }
867 free(graph->node);
868 free(graph->sorted);
869 if (graph->edge)
870 for (i = 0; i < graph->n_edge; ++i) {
871 isl_map_free(graph->edge[i].map);
872 isl_union_map_free(graph->edge[i].tagged_condition);
873 isl_union_map_free(graph->edge[i].tagged_validity);
874 }
875 free(graph->edge);
876 free(graph->region);
877 for (i = 0; i <= isl_edge_last; ++i)
878 isl_hash_table_free(ctx, graph->edge_table[i]);
879 isl_hash_table_free(ctx, graph->node_table);
880 isl_basic_set_free(graph->lp);
881}
882
883/* For each "set" on which this function is called, increment
884 * graph->n by one and update graph->maxvar.
885 */
886static isl_stat init_n_maxvar(__isl_take isl_setisl_map *set, void *user)
887{
888 struct isl_sched_graph *graph = user;
889 int nvar = isl_set_dim(set, isl_dim_set);
890
891 graph->n++;
892 if (nvar > graph->maxvar)
893 graph->maxvar = nvar;
894
895 isl_set_free(set);
896
897 return isl_stat_ok;
898}
899
900/* Add the number of basic maps in "map" to *n.
901 */
902static isl_stat add_n_basic_map(__isl_take isl_map *map, void *user)
903{
904 int *n = user;
905
906 *n += isl_map_n_basic_map(map);
907 isl_map_free(map);
908
909 return isl_stat_ok;
910}
911
912/* Compute the number of rows that should be allocated for the schedule.
913 * In particular, we need one row for each variable or one row
914 * for each basic map in the dependences.
915 * Note that it is practically impossible to exhaust both
916 * the number of dependences and the number of variables.
917 */
918static int compute_max_row(struct isl_sched_graph *graph,
919 __isl_keep isl_schedule_constraints *sc)
920{
921 enum isl_edge_type i;
922 int n_edge;
923
924 graph->n = 0;
925 graph->maxvar = 0;
926 if (isl_union_set_foreach_set(sc->domain, &init_n_maxvar, graph) < 0)
927 return -1;
928 n_edge = 0;
929 for (i = isl_edge_first; i <= isl_edge_last; ++i)
930 if (isl_union_map_foreach_map(sc->constraint[i],
931 &add_n_basic_map, &n_edge) < 0)
932 return -1;
933 graph->max_row = n_edge + graph->maxvar;
934
935 return 0;
936}
937
938/* Does "bset" have any defining equalities for its set variables?
939 */
940static int has_any_defining_equality(__isl_keep isl_basic_setisl_basic_map *bset)
941{
942 int i, n;
943
944 if (!bset)
945 return -1;
946
947 n = isl_basic_set_dim(bset, isl_dim_set);
948 for (i = 0; i < n; ++i) {
949 int has;
950
951 has = isl_basic_set_has_defining_equality(bset, isl_dim_set, i,
952 NULL((void*)0));
953 if (has < 0 || has)
954 return has;
955 }
956
957 return 0;
958}
959
960/* Add a new node to the graph representing the given space.
961 * "nvar" is the (possibly compressed) number of variables and
962 * may be smaller than then number of set variables in "space"
963 * if "compressed" is set.
964 * If "compressed" is set, then "hull" represents the constraints
965 * that were used to derive the compression, while "compress" and
966 * "decompress" map the original space to the compressed space and
967 * vice versa.
968 * If "compressed" is not set, then "hull", "compress" and "decompress"
969 * should be NULL.
970 */
971static isl_stat add_node(struct isl_sched_graph *graph,
972 __isl_take isl_space *space, int nvar, int compressed,
973 __isl_take isl_setisl_map *hull, __isl_take isl_multi_aff *compress,
974 __isl_take isl_multi_aff *decompress)
975{
976 int nparam;
977 isl_ctx *ctx;
978 isl_mat *sched;
979 int *coincident;
980
981 if (!space)
982 return isl_stat_error;
983
984 ctx = isl_space_get_ctx(space);
985 nparam = isl_space_dim(space, isl_dim_param);
986 if (!ctx->opt->schedule_parametric)
987 nparam = 0;
988 sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
989 graph->node[graph->n].space = space;
990 graph->node[graph->n].nvar = nvar;
991 graph->node[graph->n].nparam = nparam;
992 graph->node[graph->n].sched = sched;
993 graph->node[graph->n].sched_map = NULL((void*)0);
994 coincident = isl_calloc_array(ctx, int, graph->max_row)((int *)isl_calloc_or_die(ctx, graph->max_row, sizeof(int)
));
995 graph->node[graph->n].coincident = coincident;
996 graph->node[graph->n].compressed = compressed;
997 graph->node[graph->n].hull = hull;
998 graph->node[graph->n].compress = compress;
999 graph->node[graph->n].decompress = decompress;
1000 graph->n++;
1001
1002 if (!space || !sched || (graph->max_row && !coincident))
1003 return isl_stat_error;
1004 if (compressed && (!hull || !compress || !decompress))
1005 return isl_stat_error;
1006
1007 return isl_stat_ok;
1008}
1009
1010/* Add a new node to the graph representing the given set.
1011 *
1012 * If any of the set variables is defined by an equality, then
1013 * we perform variable compression such that we can perform
1014 * the scheduling on the compressed domain.
1015 */
1016static isl_stat extract_node(__isl_take isl_setisl_map *set, void *user)
1017{
1018 int nvar;
1019 int has_equality;
1020 isl_space *space;
1021 isl_basic_setisl_basic_map *hull;
1022 isl_setisl_map *hull_set;
1023 isl_morph *morph;
1024 isl_multi_aff *compress, *decompress;
1025 struct isl_sched_graph *graph = user;
1026
1027 space = isl_set_get_space(set);
1028 hull = isl_set_affine_hull(set);
1029 hull = isl_basic_set_remove_divs(hull);
1030 nvar = isl_space_dim(space, isl_dim_set);
1031 has_equality = has_any_defining_equality(hull);
1032
1033 if (has_equality < 0)
1034 goto error;
1035 if (!has_equality) {
1036 isl_basic_set_free(hull);
1037 return add_node(graph, space, nvar, 0, NULL((void*)0), NULL((void*)0), NULL((void*)0));
1038 }
1039
1040 morph = isl_basic_set_variable_compression(hull, isl_dim_set);
1041 nvar = isl_morph_ran_dim(morph, isl_dim_set);
1042 compress = isl_morph_get_var_multi_aff(morph);
1043 morph = isl_morph_inverse(morph);
1044 decompress = isl_morph_get_var_multi_aff(morph);
1045 isl_morph_free(morph);
1046
1047 hull_set = isl_set_from_basic_set(hull);
1048 return add_node(graph, space, nvar, 1, hull_set, compress, decompress);
1049error:
1050 isl_basic_set_free(hull);
1051 isl_space_free(space);
1052 return isl_stat_error;
1053}
1054
1055struct isl_extract_edge_data {
1056 enum isl_edge_type type;
1057 struct isl_sched_graph *graph;
1058};
1059
1060/* Merge edge2 into edge1, freeing the contents of edge2.
1061 * "type" is the type of the schedule constraint from which edge2 was
1062 * extracted.
1063 * Return 0 on success and -1 on failure.
1064 *
1065 * edge1 and edge2 are assumed to have the same value for the map field.
1066 */
1067static int merge_edge(enum isl_edge_type type, struct isl_sched_edge *edge1,
1068 struct isl_sched_edge *edge2)
1069{
1070 edge1->validity |= edge2->validity;
1071 edge1->coincidence |= edge2->coincidence;
1072 edge1->proximity |= edge2->proximity;
1073 edge1->condition |= edge2->condition;
1074 edge1->conditional_validity |= edge2->conditional_validity;
1075 isl_map_free(edge2->map);
1076
1077 if (type == isl_edge_condition) {
1078 if (!edge1->tagged_condition)
1079 edge1->tagged_condition = edge2->tagged_condition;
1080 else
1081 edge1->tagged_condition =
1082 isl_union_map_union(edge1->tagged_condition,
1083 edge2->tagged_condition);
1084 }
1085
1086 if (type == isl_edge_conditional_validity) {
1087 if (!edge1->tagged_validity)
1088 edge1->tagged_validity = edge2->tagged_validity;
1089 else
1090 edge1->tagged_validity =
1091 isl_union_map_union(edge1->tagged_validity,
1092 edge2->tagged_validity);
1093 }
1094
1095 if (type == isl_edge_condition && !edge1->tagged_condition)
1096 return -1;
1097 if (type == isl_edge_conditional_validity && !edge1->tagged_validity)
1098 return -1;
1099
1100 return 0;
1101}
1102
1103/* Insert dummy tags in domain and range of "map".
1104 *
1105 * In particular, if "map" is of the form
1106 *
1107 * A -> B
1108 *
1109 * then return
1110 *
1111 * [A -> dummy_tag] -> [B -> dummy_tag]
1112 *
1113 * where the dummy_tags are identical and equal to any dummy tags
1114 * introduced by any other call to this function.
1115 */
1116static __isl_give isl_map *insert_dummy_tags(__isl_take isl_map *map)
1117{
1118 static char dummy;
1119 isl_ctx *ctx;
1120 isl_id *id;
1121 isl_space *space;
1122 isl_setisl_map *domain, *range;
1123
1124 ctx = isl_map_get_ctx(map);
1125
1126 id = isl_id_alloc(ctx, NULL((void*)0), &dummy);
1127 space = isl_space_params(isl_map_get_space(map));
1128 space = isl_space_set_from_params(space);
1129 space = isl_space_set_tuple_id(space, isl_dim_set, id);
1130 space = isl_space_map_from_set(space);
1131
1132 domain = isl_map_wrap(map);
1133 range = isl_map_wrap(isl_map_universe(space));
1134 map = isl_map_from_domain_and_range(domain, range);
1135 map = isl_map_zip(map);
1136
1137 return map;
1138}
1139
1140/* Given that at least one of "src" or "dst" is compressed, return
1141 * a map between the spaces of these nodes restricted to the affine
1142 * hull that was used in the compression.
1143 */
1144static __isl_give isl_map *extract_hull(struct isl_sched_node *src,
1145 struct isl_sched_node *dst)
1146{
1147 isl_setisl_map *dom, *ran;
1148
1149 if (src->compressed)
1150 dom = isl_set_copy(src->hull);
1151 else
1152 dom = isl_set_universe(isl_space_copy(src->space));
1153 if (dst->compressed)
1154 ran = isl_set_copy(dst->hull);
1155 else
1156 ran = isl_set_universe(isl_space_copy(dst->space));
1157
1158 return isl_map_from_domain_and_range(dom, ran);
1159}
1160
1161/* Intersect the domains of the nested relations in domain and range
1162 * of "tagged" with "map".
1163 */
1164static __isl_give isl_map *map_intersect_domains(__isl_take isl_map *tagged,
1165 __isl_keep isl_map *map)
1166{
1167 isl_setisl_map *set;
1168
1169 tagged = isl_map_zip(tagged);
1170 set = isl_map_wrap(isl_map_copy(map));
1171 tagged = isl_map_intersect_domain(tagged, set);
1172 tagged = isl_map_zip(tagged);
1173 return tagged;
1174}
1175
1176/* Add a new edge to the graph based on the given map
1177 * and add it to data->graph->edge_table[data->type].
1178 * If a dependence relation of a given type happens to be identical
1179 * to one of the dependence relations of a type that was added before,
1180 * then we don't create a new edge, but instead mark the original edge
1181 * as also representing a dependence of the current type.
1182 *
1183 * Edges of type isl_edge_condition or isl_edge_conditional_validity
1184 * may be specified as "tagged" dependence relations. That is, "map"
1185 * may contain elements (i -> a) -> (j -> b), where i -> j denotes
1186 * the dependence on iterations and a and b are tags.
1187 * edge->map is set to the relation containing the elements i -> j,
1188 * while edge->tagged_condition and edge->tagged_validity contain
1189 * the union of all the "map" relations
1190 * for which extract_edge is called that result in the same edge->map.
1191 *
1192 * If the source or the destination node is compressed, then
1193 * intersect both "map" and "tagged" with the constraints that
1194 * were used to construct the compression.
1195 * This ensures that there are no schedule constraints defined
1196 * outside of these domains, while the scheduler no longer has
1197 * any control over those outside parts.
1198 */
1199static isl_stat extract_edge(__isl_take isl_map *map, void *user)
1200{
1201 isl_ctx *ctx = isl_map_get_ctx(map);
1202 struct isl_extract_edge_data *data = user;
1203 struct isl_sched_graph *graph = data->graph;
1204 struct isl_sched_node *src, *dst;
1205 isl_space *dim;
1206 struct isl_sched_edge *edge;
1207 isl_map *tagged = NULL((void*)0);
1208
1209 if (data->type == isl_edge_condition ||
1210 data->type == isl_edge_conditional_validity) {
1211 if (isl_map_can_zip(map)) {
1212 tagged = isl_map_copy(map);
1213 map = isl_set_unwrap(isl_map_domain(isl_map_zip(map)));
1214 } else {
1215 tagged = insert_dummy_tags(isl_map_copy(map));
1216 }
1217 }
1218
1219 dim = isl_space_domain(isl_map_get_space(map));
1220 src = graph_find_node(ctx, graph, dim);
1221 isl_space_free(dim);
1222 dim = isl_space_range(isl_map_get_space(map));
1223 dst = graph_find_node(ctx, graph, dim);
1224 isl_space_free(dim);
1225
1226 if (!src || !dst) {
1227 isl_map_free(map);
1228 isl_map_free(tagged);
1229 return isl_stat_ok;
1230 }
1231
1232 if (src->compressed || dst->compressed) {
1233 isl_map *hull;
1234 hull = extract_hull(src, dst);
1235 if (tagged)
1236 tagged = map_intersect_domains(tagged, hull);
1237 map = isl_map_intersect(map, hull);
1238 }
1239
1240 graph->edge[graph->n_edge].src = src;
1241 graph->edge[graph->n_edge].dst = dst;
1242 graph->edge[graph->n_edge].map = map;
1243 graph->edge[graph->n_edge].validity = 0;
1244 graph->edge[graph->n_edge].coincidence = 0;
1245 graph->edge[graph->n_edge].proximity = 0;
1246 graph->edge[graph->n_edge].condition = 0;
1247 graph->edge[graph->n_edge].local = 0;
1248 graph->edge[graph->n_edge].conditional_validity = 0;
1249 graph->edge[graph->n_edge].tagged_condition = NULL((void*)0);
1250 graph->edge[graph->n_edge].tagged_validity = NULL((void*)0);
1251 if (data->type == isl_edge_validity)
1252 graph->edge[graph->n_edge].validity = 1;
1253 if (data->type == isl_edge_coincidence)
1254 graph->edge[graph->n_edge].coincidence = 1;
1255 if (data->type == isl_edge_proximity)
1256 graph->edge[graph->n_edge].proximity = 1;
1257 if (data->type == isl_edge_condition) {
1258 graph->edge[graph->n_edge].condition = 1;
1259 graph->edge[graph->n_edge].tagged_condition =
1260 isl_union_map_from_map(tagged);
1261 }
1262 if (data->type == isl_edge_conditional_validity) {
1263 graph->edge[graph->n_edge].conditional_validity = 1;
1264 graph->edge[graph->n_edge].tagged_validity =
1265 isl_union_map_from_map(tagged);
1266 }
1267
1268 edge = graph_find_matching_edge(graph, &graph->edge[graph->n_edge]);
1269 if (!edge) {
1270 graph->n_edge++;
1271 return isl_stat_error;
1272 }
1273 if (edge == &graph->edge[graph->n_edge])
1274 return graph_edge_table_add(ctx, graph, data->type,
1275 &graph->edge[graph->n_edge++]);
1276
1277 if (merge_edge(data->type, edge, &graph->edge[graph->n_edge]) < 0)
1278 return -1;
1279
1280 return graph_edge_table_add(ctx, graph, data->type, edge);
1281}
1282
1283/* Check whether there is any dependence from node[j] to node[i]
1284 * or from node[i] to node[j].
1285 */
1286static isl_bool node_follows_weak(int i, int j, void *user)
1287{
1288 isl_bool f;
1289 struct isl_sched_graph *graph = user;
1290
1291 f = graph_has_any_edge(graph, &graph->node[j], &graph->node[i]);
1292 if (f < 0 || f)
1293 return f;
1294 return graph_has_any_edge(graph, &graph->node[i], &graph->node[j]);
1295}
1296
1297/* Check whether there is a (conditional) validity dependence from node[j]
1298 * to node[i], forcing node[i] to follow node[j].
1299 */
1300static isl_bool node_follows_strong(int i, int j, void *user)
1301{
1302 struct isl_sched_graph *graph = user;
1303
1304 return graph_has_validity_edge(graph, &graph->node[j], &graph->node[i]);
1305}
1306
1307/* Use Tarjan's algorithm for computing the strongly connected components
1308 * in the dependence graph (only validity edges).
1309 * If weak is set, we consider the graph to be undirected and
1310 * we effectively compute the (weakly) connected components.
1311 * Additionally, we also consider other edges when weak is set.
1312 */
1313static int detect_ccs(isl_ctx *ctx, struct isl_sched_graph *graph, int weak)
1314{
1315 int i, n;
1316 struct isl_tarjan_graph *g = NULL((void*)0);
1317
1318 g = isl_tarjan_graph_init(ctx, graph->n,
1319 weak ? &node_follows_weak : &node_follows_strong, graph);
1320 if (!g)
1321 return -1;
1322
1323 graph->weak = weak;
1324 graph->scc = 0;
1325 i = 0;
1326 n = graph->n;
1327 while (n) {
1328 while (g->order[i] != -1) {
1329 graph->node[g->order[i]].scc = graph->scc;
1330 --n;
1331 ++i;
1332 }
1333 ++i;
1334 graph->scc++;
1335 }
1336
1337 isl_tarjan_graph_free(g);
1338
1339 return 0;
1340}
1341
1342/* Apply Tarjan's algorithm to detect the strongly connected components
1343 * in the dependence graph.
1344 */
1345static int detect_sccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1346{
1347 return detect_ccs(ctx, graph, 0);
1348}
1349
1350/* Apply Tarjan's algorithm to detect the (weakly) connected components
1351 * in the dependence graph.
1352 */
1353static int detect_wccs(isl_ctx *ctx, struct isl_sched_graph *graph)
1354{
1355 return detect_ccs(ctx, graph, 1);
1356}
1357
1358static int cmp_scc(const void *a, const void *b, void *data)
1359{
1360 struct isl_sched_graph *graph = data;
1361 const int *i1 = a;
1362 const int *i2 = b;
1363
1364 return graph->node[*i1].scc - graph->node[*i2].scc;
1365}
1366
1367/* Sort the elements of graph->sorted according to the corresponding SCCs.
1368 */
1369static int sort_sccs(struct isl_sched_graph *graph)
1370{
1371 return isl_sort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
1372}
1373
1374/* Given a dependence relation R from "node" to itself,
1375 * construct the set of coefficients of valid constraints for elements
1376 * in that dependence relation.
1377 * In particular, the result contains tuples of coefficients
1378 * c_0, c_n, c_x such that
1379 *
1380 * c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
1381 *
1382 * or, equivalently,
1383 *
1384 * c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
1385 *
1386 * We choose here to compute the dual of delta R.
1387 * Alternatively, we could have computed the dual of R, resulting
1388 * in a set of tuples c_0, c_n, c_x, c_y, and then
1389 * plugged in (c_0, c_n, c_x, -c_x).
1390 *
1391 * If "node" has been compressed, then the dependence relation
1392 * is also compressed before the set of coefficients is computed.
1393 */
1394static __isl_give isl_basic_setisl_basic_map *intra_coefficients(
1395 struct isl_sched_graph *graph, struct isl_sched_node *node,
1396 __isl_take isl_map *map)
1397{
1398 isl_setisl_map *delta;
1399 isl_map *key;
1400 isl_basic_setisl_basic_map *coef;
1401
1402 if (isl_map_to_basic_set_has(graph->intra_hmap, map))
1403 return isl_map_to_basic_set_get(graph->intra_hmap, map);
1404
1405 key = isl_map_copy(map);
1406 if (node->compressed) {
1407 map = isl_map_preimage_domain_multi_aff(map,
1408 isl_multi_aff_copy(node->decompress));
1409 map = isl_map_preimage_range_multi_aff(map,
1410 isl_multi_aff_copy(node->decompress));
1411 }
1412 delta = isl_set_remove_divs(isl_map_deltas(map));
1413 coef = isl_set_coefficients(delta);
1414 graph->intra_hmap = isl_map_to_basic_set_set(graph->intra_hmap, key,
1415 isl_basic_set_copy(coef));
1416
1417 return coef;
1418}
1419
1420/* Given a dependence relation R, construct the set of coefficients
1421 * of valid constraints for elements in that dependence relation.
1422 * In particular, the result contains tuples of coefficients
1423 * c_0, c_n, c_x, c_y such that
1424 *
1425 * c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
1426 *
1427 * If the source or destination nodes of "edge" have been compressed,
1428 * then the dependence relation is also compressed before
1429 * the set of coefficients is computed.
1430 */
1431static __isl_give isl_basic_setisl_basic_map *inter_coefficients(
1432 struct isl_sched_graph *graph, struct isl_sched_edge *edge,
1433 __isl_take isl_map *map)
1434{
1435 isl_setisl_map *set;
1436 isl_map *key;
1437 isl_basic_setisl_basic_map *coef;
1438
1439 if (isl_map_to_basic_set_has(graph->inter_hmap, map))
1440 return isl_map_to_basic_set_get(graph->inter_hmap, map);
1441
1442 key = isl_map_copy(map);
1443 if (edge->src->compressed)
1444 map = isl_map_preimage_domain_multi_aff(map,
1445 isl_multi_aff_copy(edge->src->decompress));
1446 if (edge->dst->compressed)
1447 map = isl_map_preimage_range_multi_aff(map,
1448 isl_multi_aff_copy(edge->dst->decompress));
1449 set = isl_map_wrap(isl_map_remove_divs(map));
1450 coef = isl_set_coefficients(set);
1451 graph->inter_hmap = isl_map_to_basic_set_set(graph->inter_hmap, key,
1452 isl_basic_set_copy(coef));
1453
1454 return coef;
1455}
1456
1457/* Add constraints to graph->lp that force validity for the given
1458 * dependence from a node i to itself.
1459 * That is, add constraints that enforce
1460 *
1461 * (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
1462 * = c_i_x (y - x) >= 0
1463 *
1464 * for each (x,y) in R.
1465 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1466 * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
1467 * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
1468 * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
1469 *
1470 * Actually, we do not construct constraints for the c_i_x themselves,
1471 * but for the coefficients of c_i_x written as a linear combination
1472 * of the columns in node->cmap.
1473 */
1474static int add_intra_validity_constraints(struct isl_sched_graph *graph,
1475 struct isl_sched_edge *edge)
1476{
1477 unsigned total;
1478 isl_map *map = isl_map_copy(edge->map);
1479 isl_ctx *ctx = isl_map_get_ctx(map);
1480 isl_space *dim;
1481 isl_dim_map *dim_map;
1482 isl_basic_setisl_basic_map *coef;
1483 struct isl_sched_node *node = edge->src;
1484
1485 coef = intra_coefficients(graph, node, map);
1486
1487 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1488
1489 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1490 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
1491 if (!coef)
1492 goto error;
1493
1494 total = isl_basic_set_total_dim(graph->lp);
1495 dim_map = isl_dim_map_alloc(ctx, total);
1496 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1497 isl_space_dim(dim, isl_dim_set), 1,
1498 node->nvar, -1);
1499 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1500 isl_space_dim(dim, isl_dim_set), 1,
1501 node->nvar, 1);
1502 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1503 coef->n_eq, coef->n_ineq);
1504 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1505 coef, dim_map);
1506 isl_space_free(dim);
1507
1508 return 0;
1509error:
1510 isl_space_free(dim);
1511 return -1;
1512}
1513
1514/* Add constraints to graph->lp that force validity for the given
1515 * dependence from node i to node j.
1516 * That is, add constraints that enforce
1517 *
1518 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
1519 *
1520 * for each (x,y) in R.
1521 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1522 * of valid constraints for R and then plug in
1523 * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
1524 * c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
1525 * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
1526 * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
1527 *
1528 * Actually, we do not construct constraints for the c_*_x themselves,
1529 * but for the coefficients of c_*_x written as a linear combination
1530 * of the columns in node->cmap.
1531 */
1532static int add_inter_validity_constraints(struct isl_sched_graph *graph,
1533 struct isl_sched_edge *edge)
1534{
1535 unsigned total;
1536 isl_map *map = isl_map_copy(edge->map);
1537 isl_ctx *ctx = isl_map_get_ctx(map);
1538 isl_space *dim;
1539 isl_dim_map *dim_map;
1540 isl_basic_setisl_basic_map *coef;
1541 struct isl_sched_node *src = edge->src;
1542 struct isl_sched_node *dst = edge->dst;
1543
1544 coef = inter_coefficients(graph, edge, map);
1545
1546 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1547
1548 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1549 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1550 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1551 isl_space_dim(dim, isl_dim_set) + src->nvar,
1552 isl_mat_copy(dst->cmap));
1553 if (!coef)
1554 goto error;
1555
1556 total = isl_basic_set_total_dim(graph->lp);
1557 dim_map = isl_dim_map_alloc(ctx, total);
1558
1559 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
1560 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
1561 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
1562 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1563 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1564 dst->nvar, -1);
1565 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1566 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1567 dst->nvar, 1);
1568
1569 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
1570 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
1571 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
1572 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1573 isl_space_dim(dim, isl_dim_set), 1,
1574 src->nvar, 1);
1575 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1576 isl_space_dim(dim, isl_dim_set), 1,
1577 src->nvar, -1);
1578
1579 edge->start = graph->lp->n_ineq;
1580 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1581 coef->n_eq, coef->n_ineq);
1582 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1583 coef, dim_map);
1584 if (!graph->lp)
1585 goto error;
1586 isl_space_free(dim);
1587 edge->end = graph->lp->n_ineq;
1588
1589 return 0;
1590error:
1591 isl_space_free(dim);
1592 return -1;
1593}
1594
1595/* Add constraints to graph->lp that bound the dependence distance for the given
1596 * dependence from a node i to itself.
1597 * If s = 1, we add the constraint
1598 *
1599 * c_i_x (y - x) <= m_0 + m_n n
1600 *
1601 * or
1602 *
1603 * -c_i_x (y - x) + m_0 + m_n n >= 0
1604 *
1605 * for each (x,y) in R.
1606 * If s = -1, we add the constraint
1607 *
1608 * -c_i_x (y - x) <= m_0 + m_n n
1609 *
1610 * or
1611 *
1612 * c_i_x (y - x) + m_0 + m_n n >= 0
1613 *
1614 * for each (x,y) in R.
1615 * We obtain general constraints on coefficients (c_0, c_n, c_x)
1616 * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
1617 * with each coefficient (except m_0) represented as a pair of non-negative
1618 * coefficients.
1619 *
1620 * Actually, we do not construct constraints for the c_i_x themselves,
1621 * but for the coefficients of c_i_x written as a linear combination
1622 * of the columns in node->cmap.
1623 *
1624 *
1625 * If "local" is set, then we add constraints
1626 *
1627 * c_i_x (y - x) <= 0
1628 *
1629 * or
1630 *
1631 * -c_i_x (y - x) <= 0
1632 *
1633 * instead, forcing the dependence distance to be (less than or) equal to 0.
1634 * That is, we plug in (0, 0, -s * c_i_x),
1635 * Note that dependences marked local are treated as validity constraints
1636 * by add_all_validity_constraints and therefore also have
1637 * their distances bounded by 0 from below.
1638 */
1639static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
1640 struct isl_sched_edge *edge, int s, int local)
1641{
1642 unsigned total;
1643 unsigned nparam;
1644 isl_map *map = isl_map_copy(edge->map);
1645 isl_ctx *ctx = isl_map_get_ctx(map);
1646 isl_space *dim;
1647 isl_dim_map *dim_map;
1648 isl_basic_setisl_basic_map *coef;
1649 struct isl_sched_node *node = edge->src;
1650
1651 coef = intra_coefficients(graph, node, map);
1652
1653 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1654
1655 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1656 isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
1657 if (!coef)
1658 goto error;
1659
1660 nparam = isl_space_dim(node->space, isl_dim_param);
1661 total = isl_basic_set_total_dim(graph->lp);
1662 dim_map = isl_dim_map_alloc(ctx, total);
1663
1664 if (!local) {
1665 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1666 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1667 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1668 }
1669 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1670 isl_space_dim(dim, isl_dim_set), 1,
1671 node->nvar, s);
1672 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1673 isl_space_dim(dim, isl_dim_set), 1,
1674 node->nvar, -s);
1675 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1676 coef->n_eq, coef->n_ineq);
1677 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1678 coef, dim_map);
1679 isl_space_free(dim);
1680
1681 return 0;
1682error:
1683 isl_space_free(dim);
1684 return -1;
1685}
1686
1687/* Add constraints to graph->lp that bound the dependence distance for the given
1688 * dependence from node i to node j.
1689 * If s = 1, we add the constraint
1690 *
1691 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
1692 * <= m_0 + m_n n
1693 *
1694 * or
1695 *
1696 * -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
1697 * m_0 + m_n n >= 0
1698 *
1699 * for each (x,y) in R.
1700 * If s = -1, we add the constraint
1701 *
1702 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
1703 * <= m_0 + m_n n
1704 *
1705 * or
1706 *
1707 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
1708 * m_0 + m_n n >= 0
1709 *
1710 * for each (x,y) in R.
1711 * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
1712 * of valid constraints for R and then plug in
1713 * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
1714 * -s*c_j_x+s*c_i_x)
1715 * with each coefficient (except m_0, c_j_0 and c_i_0)
1716 * represented as a pair of non-negative coefficients.
1717 *
1718 * Actually, we do not construct constraints for the c_*_x themselves,
1719 * but for the coefficients of c_*_x written as a linear combination
1720 * of the columns in node->cmap.
1721 *
1722 *
1723 * If "local" is set, then we add constraints
1724 *
1725 * (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) <= 0
1726 *
1727 * or
1728 *
1729 * -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)) <= 0
1730 *
1731 * instead, forcing the dependence distance to be (less than or) equal to 0.
1732 * That is, we plug in
1733 * (-s*c_j_0 + s*c_i_0, -s*c_j_n + s*c_i_n, -s*c_j_x+s*c_i_x).
1734 * Note that dependences marked local are treated as validity constraints
1735 * by add_all_validity_constraints and therefore also have
1736 * their distances bounded by 0 from below.
1737 */
1738static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
1739 struct isl_sched_edge *edge, int s, int local)
1740{
1741 unsigned total;
1742 unsigned nparam;
1743 isl_map *map = isl_map_copy(edge->map);
1744 isl_ctx *ctx = isl_map_get_ctx(map);
1745 isl_space *dim;
1746 isl_dim_map *dim_map;
1747 isl_basic_setisl_basic_map *coef;
1748 struct isl_sched_node *src = edge->src;
1749 struct isl_sched_node *dst = edge->dst;
1750
1751 coef = inter_coefficients(graph, edge, map);
1752
1753 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1754
1755 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1756 isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
1757 coef = isl_basic_set_transform_dims(coef, isl_dim_set,
1758 isl_space_dim(dim, isl_dim_set) + src->nvar,
1759 isl_mat_copy(dst->cmap));
1760 if (!coef)
1761 goto error;
1762
1763 nparam = isl_space_dim(src->space, isl_dim_param);
1764 total = isl_basic_set_total_dim(graph->lp);
1765 dim_map = isl_dim_map_alloc(ctx, total);
1766
1767 if (!local) {
1768 isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
1769 isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
1770 isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
1771 }
1772
1773 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
1774 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
1775 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
1776 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
1777 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1778 dst->nvar, s);
1779 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
1780 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
1781 dst->nvar, -s);
1782
1783 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
1784 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
1785 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
1786 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
1787 isl_space_dim(dim, isl_dim_set), 1,
1788 src->nvar, -s);
1789 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
1790 isl_space_dim(dim, isl_dim_set), 1,
1791 src->nvar, s);
1792
1793 graph->lp = isl_basic_set_extend_constraints(graph->lp,
1794 coef->n_eq, coef->n_ineq);
1795 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1796 coef, dim_map);
1797 isl_space_free(dim);
1798
1799 return 0;
1800error:
1801 isl_space_free(dim);
1802 return -1;
1803}
1804
1805/* Add all validity constraints to graph->lp.
1806 *
1807 * An edge that is forced to be local needs to have its dependence
1808 * distances equal to zero. We take care of bounding them by 0 from below
1809 * here. add_all_proximity_constraints takes care of bounding them by 0
1810 * from above.
1811 *
1812 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1813 * Otherwise, we ignore them.
1814 */
1815static int add_all_validity_constraints(struct isl_sched_graph *graph,
1816 int use_coincidence)
1817{
1818 int i;
1819
1820 for (i = 0; i < graph->n_edge; ++i) {
1821 struct isl_sched_edge *edge= &graph->edge[i];
1822 int local;
1823
1824 local = edge->local || (edge->coincidence && use_coincidence);
1825 if (!edge->validity && !local)
1826 continue;
1827 if (edge->src != edge->dst)
1828 continue;
1829 if (add_intra_validity_constraints(graph, edge) < 0)
1830 return -1;
1831 }
1832
1833 for (i = 0; i < graph->n_edge; ++i) {
1834 struct isl_sched_edge *edge = &graph->edge[i];
1835 int local;
1836
1837 local = edge->local || (edge->coincidence && use_coincidence);
1838 if (!edge->validity && !local)
1839 continue;
1840 if (edge->src == edge->dst)
1841 continue;
1842 if (add_inter_validity_constraints(graph, edge) < 0)
1843 return -1;
1844 }
1845
1846 return 0;
1847}
1848
1849/* Add constraints to graph->lp that bound the dependence distance
1850 * for all dependence relations.
1851 * If a given proximity dependence is identical to a validity
1852 * dependence, then the dependence distance is already bounded
1853 * from below (by zero), so we only need to bound the distance
1854 * from above. (This includes the case of "local" dependences
1855 * which are treated as validity dependence by add_all_validity_constraints.)
1856 * Otherwise, we need to bound the distance both from above and from below.
1857 *
1858 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1859 * Otherwise, we ignore them.
1860 */
1861static int add_all_proximity_constraints(struct isl_sched_graph *graph,
1862 int use_coincidence)
1863{
1864 int i;
1865
1866 for (i = 0; i < graph->n_edge; ++i) {
1867 struct isl_sched_edge *edge= &graph->edge[i];
1868 int local;
1869
1870 local = edge->local || (edge->coincidence && use_coincidence);
1871 if (!edge->proximity && !local)
1872 continue;
1873 if (edge->src == edge->dst &&
1874 add_intra_proximity_constraints(graph, edge, 1, local) < 0)
1875 return -1;
1876 if (edge->src != edge->dst &&
1877 add_inter_proximity_constraints(graph, edge, 1, local) < 0)
1878 return -1;
1879 if (edge->validity || local)
1880 continue;
1881 if (edge->src == edge->dst &&
1882 add_intra_proximity_constraints(graph, edge, -1, 0) < 0)
1883 return -1;
1884 if (edge->src != edge->dst &&
1885 add_inter_proximity_constraints(graph, edge, -1, 0) < 0)
1886 return -1;
1887 }
1888
1889 return 0;
1890}
1891
1892/* Compute a basis for the rows in the linear part of the schedule
1893 * and extend this basis to a full basis. The remaining rows
1894 * can then be used to force linear independence from the rows
1895 * in the schedule.
1896 *
1897 * In particular, given the schedule rows S, we compute
1898 *
1899 * S = H Q
1900 * S U = H
1901 *
1902 * with H the Hermite normal form of S. That is, all but the
1903 * first rank columns of H are zero and so each row in S is
1904 * a linear combination of the first rank rows of Q.
1905 * The matrix Q is then transposed because we will write the
1906 * coefficients of the next schedule row as a column vector s
1907 * and express this s as a linear combination s = Q c of the
1908 * computed basis.
1909 * Similarly, the matrix U is transposed such that we can
1910 * compute the coefficients c = U s from a schedule row s.
1911 */
1912static int node_update_cmap(struct isl_sched_node *node)
1913{
1914 isl_mat *H, *U, *Q;
1915 int n_row = isl_mat_rows(node->sched);
1916
1917 H = isl_mat_sub_alloc(node->sched, 0, n_row,
1918 1 + node->nparam, node->nvar);
1919
1920 H = isl_mat_left_hermite(H, 0, &U, &Q);
1921 isl_mat_free(node->cmap);
1922 isl_mat_free(node->cinv);
1923 node->cmap = isl_mat_transpose(Q);
1924 node->cinv = isl_mat_transpose(U);
1925 node->rank = isl_mat_initial_non_zero_cols(H);
1926 isl_mat_free(H);
1927
1928 if (!node->cmap || !node->cinv || node->rank < 0)
1929 return -1;
1930 return 0;
1931}
1932
1933/* How many times should we count the constraints in "edge"?
1934 *
1935 * If carry is set, then we are counting the number of
1936 * (validity or conditional validity) constraints that will be added
1937 * in setup_carry_lp and we count each edge exactly once.
1938 *
1939 * Otherwise, we count as follows
1940 * validity -> 1 (>= 0)
1941 * validity+proximity -> 2 (>= 0 and upper bound)
1942 * proximity -> 2 (lower and upper bound)
1943 * local(+any) -> 2 (>= 0 and <= 0)
1944 *
1945 * If an edge is only marked conditional_validity then it counts
1946 * as zero since it is only checked afterwards.
1947 *
1948 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
1949 * Otherwise, we ignore them.
1950 */
1951static int edge_multiplicity(struct isl_sched_edge *edge, int carry,
1952 int use_coincidence)
1953{
1954 if (carry && !edge->validity && !edge->conditional_validity)
1955 return 0;
1956 if (carry)
1957 return 1;
1958 if (edge->proximity || edge->local)
1959 return 2;
1960 if (use_coincidence && edge->coincidence)
1961 return 2;
1962 if (edge->validity)
1963 return 1;
1964 return 0;
1965}
1966
1967/* Count the number of equality and inequality constraints
1968 * that will be added for the given map.
1969 *
1970 * "use_coincidence" is set if we should take into account coincidence edges.
1971 */
1972static int count_map_constraints(struct isl_sched_graph *graph,
1973 struct isl_sched_edge *edge, __isl_take isl_map *map,
1974 int *n_eq, int *n_ineq, int carry, int use_coincidence)
1975{
1976 isl_basic_setisl_basic_map *coef;
1977 int f = edge_multiplicity(edge, carry, use_coincidence);
1978
1979 if (f == 0) {
1980 isl_map_free(map);
1981 return 0;
1982 }
1983
1984 if (edge->src == edge->dst)
1985 coef = intra_coefficients(graph, edge->src, map);
1986 else
1987 coef = inter_coefficients(graph, edge, map);
1988 if (!coef)
1989 return -1;
1990 *n_eq += f * coef->n_eq;
1991 *n_ineq += f * coef->n_ineq;
1992 isl_basic_set_free(coef);
1993
1994 return 0;
1995}
1996
1997/* Count the number of equality and inequality constraints
1998 * that will be added to the main lp problem.
1999 * We count as follows
2000 * validity -> 1 (>= 0)
2001 * validity+proximity -> 2 (>= 0 and upper bound)
2002 * proximity -> 2 (lower and upper bound)
2003 * local(+any) -> 2 (>= 0 and <= 0)
2004 *
2005 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2006 * Otherwise, we ignore them.
2007 */
2008static int count_constraints(struct isl_sched_graph *graph,
2009 int *n_eq, int *n_ineq, int use_coincidence)
2010{
2011 int i;
2012
2013 *n_eq = *n_ineq = 0;
2014 for (i = 0; i < graph->n_edge; ++i) {
2015 struct isl_sched_edge *edge= &graph->edge[i];
2016 isl_map *map = isl_map_copy(edge->map);
2017
2018 if (count_map_constraints(graph, edge, map, n_eq, n_ineq,
2019 0, use_coincidence) < 0)
2020 return -1;
2021 }
2022
2023 return 0;
2024}
2025
2026/* Count the number of constraints that will be added by
2027 * add_bound_coefficient_constraints and increment *n_eq and *n_ineq
2028 * accordingly.
2029 *
2030 * In practice, add_bound_coefficient_constraints only adds inequalities.
2031 */
2032static int count_bound_coefficient_constraints(isl_ctx *ctx,
2033 struct isl_sched_graph *graph, int *n_eq, int *n_ineq)
2034{
2035 int i;
2036
2037 if (ctx->opt->schedule_max_coefficient == -1)
2038 return 0;
2039
2040 for (i = 0; i < graph->n; ++i)
2041 *n_ineq += 2 * graph->node[i].nparam + 2 * graph->node[i].nvar;
2042
2043 return 0;
2044}
2045
2046/* Add constraints that bound the values of the variable and parameter
2047 * coefficients of the schedule.
2048 *
2049 * The maximal value of the coefficients is defined by the option
2050 * 'schedule_max_coefficient'.
2051 */
2052static int add_bound_coefficient_constraints(isl_ctx *ctx,
2053 struct isl_sched_graph *graph)
2054{
2055 int i, j, k;
2056 int max_coefficient;
2057 int total;
2058
2059 max_coefficient = ctx->opt->schedule_max_coefficient;
2060
2061 if (max_coefficient == -1)
2062 return 0;
2063
2064 total = isl_basic_set_total_dim(graph->lp);
2065
2066 for (i = 0; i < graph->n; ++i) {
2067 struct isl_sched_node *node = &graph->node[i];
2068 for (j = 0; j < 2 * node->nparam + 2 * node->nvar; ++j) {
2069 int dim;
2070 k = isl_basic_set_alloc_inequality(graph->lp);
2071 if (k < 0)
2072 return -1;
2073 dim = 1 + node->start + 1 + j;
2074 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2075 isl_int_set_si(graph->lp->ineq[k][dim], -1)isl_sioimath_set_si((graph->lp->ineq[k][dim]), -1);
2076 isl_int_set_si(graph->lp->ineq[k][0], max_coefficient)isl_sioimath_set_si((graph->lp->ineq[k][0]), max_coefficient
);
2077 }
2078 }
2079
2080 return 0;
2081}
2082
2083/* Construct an ILP problem for finding schedule coefficients
2084 * that result in non-negative, but small dependence distances
2085 * over all dependences.
2086 * In particular, the dependence distances over proximity edges
2087 * are bounded by m_0 + m_n n and we compute schedule coefficients
2088 * with small values (preferably zero) of m_n and m_0.
2089 *
2090 * All variables of the ILP are non-negative. The actual coefficients
2091 * may be negative, so each coefficient is represented as the difference
2092 * of two non-negative variables. The negative part always appears
2093 * immediately before the positive part.
2094 * Other than that, the variables have the following order
2095 *
2096 * - sum of positive and negative parts of m_n coefficients
2097 * - m_0
2098 * - sum of positive and negative parts of all c_n coefficients
2099 * (unconstrained when computing non-parametric schedules)
2100 * - sum of positive and negative parts of all c_x coefficients
2101 * - positive and negative parts of m_n coefficients
2102 * - for each node
2103 * - c_i_0
2104 * - positive and negative parts of c_i_n (if parametric)
2105 * - positive and negative parts of c_i_x
2106 *
2107 * The c_i_x are not represented directly, but through the columns of
2108 * node->cmap. That is, the computed values are for variable t_i_x
2109 * such that c_i_x = Q t_i_x with Q equal to node->cmap.
2110 *
2111 * The constraints are those from the edges plus two or three equalities
2112 * to express the sums.
2113 *
2114 * If "use_coincidence" is set, then we treat coincidence edges as local edges.
2115 * Otherwise, we ignore them.
2116 */
2117static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
2118 int use_coincidence)
2119{
2120 int i, j;
2121 int k;
2122 unsigned nparam;
2123 unsigned total;
2124 isl_space *dim;
2125 int parametric;
2126 int param_pos;
2127 int n_eq, n_ineq;
2128 int max_constant_term;
2129
2130 max_constant_term = ctx->opt->schedule_max_constant_term;
2131
2132 parametric = ctx->opt->schedule_parametric;
2133 nparam = isl_space_dim(graph->node[0].space, isl_dim_param);
2134 param_pos = 4;
2135 total = param_pos + 2 * nparam;
2136 for (i = 0; i < graph->n; ++i) {
2137 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2138 if (node_update_cmap(node) < 0)
2139 return -1;
2140 node->start = total;
2141 total += 1 + 2 * (node->nparam + node->nvar);
2142 }
2143
2144 if (count_constraints(graph, &n_eq, &n_ineq, use_coincidence) < 0)
2145 return -1;
2146 if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0)
2147 return -1;
2148
2149 dim = isl_space_set_alloc(ctx, 0, total);
2150 isl_basic_set_free(graph->lp);
2151 n_eq += 2 + parametric;
2152 if (max_constant_term != -1)
2153 n_ineq += graph->n;
2154
2155 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2156
2157 k = isl_basic_set_alloc_equality(graph->lp);
2158 if (k < 0)
2159 return -1;
2160 isl_seq_clr(graph->lp->eq[k], 1 + total);
2161 isl_int_set_si(graph->lp->eq[k][1], -1)isl_sioimath_set_si((graph->lp->eq[k][1]), -1);
2162 for (i = 0; i < 2 * nparam; ++i)
2163 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1)isl_sioimath_set_si((graph->lp->eq[k][1 + param_pos + i
]), 1);
2164
2165 if (parametric) {
2166 k = isl_basic_set_alloc_equality(graph->lp);
2167 if (k < 0)
2168 return -1;
2169 isl_seq_clr(graph->lp->eq[k], 1 + total);
2170 isl_int_set_si(graph->lp->eq[k][3], -1)isl_sioimath_set_si((graph->lp->eq[k][3]), -1);
2171 for (i = 0; i < graph->n; ++i) {
2172 int pos = 1 + graph->node[i].start + 1;
2173
2174 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2175 isl_int_set_si(graph->lp->eq[k][pos + j], 1)isl_sioimath_set_si((graph->lp->eq[k][pos + j]), 1);
2176 }
2177 }
2178
2179 k = isl_basic_set_alloc_equality(graph->lp);
2180 if (k < 0)
2181 return -1;
2182 isl_seq_clr(graph->lp->eq[k], 1 + total);
2183 isl_int_set_si(graph->lp->eq[k][4], -1)isl_sioimath_set_si((graph->lp->eq[k][4]), -1);
2184 for (i = 0; i < graph->n; ++i) {
2185 struct isl_sched_node *node = &graph->node[i];
2186 int pos = 1 + node->start + 1 + 2 * node->nparam;
2187
2188 for (j = 0; j < 2 * node->nvar; ++j)
2189 isl_int_set_si(graph->lp->eq[k][pos + j], 1)isl_sioimath_set_si((graph->lp->eq[k][pos + j]), 1);
2190 }
2191
2192 if (max_constant_term != -1)
2193 for (i = 0; i < graph->n; ++i) {
2194 struct isl_sched_node *node = &graph->node[i];
2195 k = isl_basic_set_alloc_inequality(graph->lp);
2196 if (k < 0)
2197 return -1;
2198 isl_seq_clr(graph->lp->ineq[k], 1 + total);
2199 isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1)isl_sioimath_set_si((graph->lp->ineq[k][1 + node->start
]), -1);
2200 isl_int_set_si(graph->lp->ineq[k][0], max_constant_term)isl_sioimath_set_si((graph->lp->ineq[k][0]), max_constant_term
);
2201 }
2202
2203 if (add_bound_coefficient_constraints(ctx, graph) < 0)
2204 return -1;
2205 if (add_all_validity_constraints(graph, use_coincidence) < 0)
2206 return -1;
2207 if (add_all_proximity_constraints(graph, use_coincidence) < 0)
2208 return -1;
2209
2210 return 0;
2211}
2212
2213/* Analyze the conflicting constraint found by
2214 * isl_tab_basic_set_non_trivial_lexmin. If it corresponds to the validity
2215 * constraint of one of the edges between distinct nodes, living, moreover
2216 * in distinct SCCs, then record the source and sink SCC as this may
2217 * be a good place to cut between SCCs.
2218 */
2219static int check_conflict(int con, void *user)
2220{
2221 int i;
2222 struct isl_sched_graph *graph = user;
2223
2224 if (graph->src_scc >= 0)
2225 return 0;
2226
2227 con -= graph->lp->n_eq;
2228
2229 if (con >= graph->lp->n_ineq)
2230 return 0;
2231
2232 for (i = 0; i < graph->n_edge; ++i) {
2233 if (!graph->edge[i].validity)
2234 continue;
2235 if (graph->edge[i].src == graph->edge[i].dst)
2236 continue;
2237 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
2238 continue;
2239 if (graph->edge[i].start > con)
2240 continue;
2241 if (graph->edge[i].end <= con)
2242 continue;
2243 graph->src_scc = graph->edge[i].src->scc;
2244 graph->dst_scc = graph->edge[i].dst->scc;
2245 }
2246
2247 return 0;
2248}
2249
2250/* Check whether the next schedule row of the given node needs to be
2251 * non-trivial. Lower-dimensional domains may have some trivial rows,
2252 * but as soon as the number of remaining required non-trivial rows
2253 * is as large as the number or remaining rows to be computed,
2254 * all remaining rows need to be non-trivial.
2255 */
2256static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
2257{
2258 return node->nvar - node->rank >= graph->maxvar - graph->n_row;
2259}
2260
2261/* Solve the ILP problem constructed in setup_lp.
2262 * For each node such that all the remaining rows of its schedule
2263 * need to be non-trivial, we construct a non-triviality region.
2264 * This region imposes that the next row is independent of previous rows.
2265 * In particular the coefficients c_i_x are represented by t_i_x
2266 * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
2267 * its first columns span the rows of the previously computed part
2268 * of the schedule. The non-triviality region enforces that at least
2269 * one of the remaining components of t_i_x is non-zero, i.e.,
2270 * that the new schedule row depends on at least one of the remaining
2271 * columns of Q.
2272 */
2273static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
2274{
2275 int i;
2276 isl_vec *sol;
2277 isl_basic_setisl_basic_map *lp;
2278
2279 for (i = 0; i < graph->n; ++i) {
2280 struct isl_sched_node *node = &graph->node[i];
2281 int skip = node->rank;
2282 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
2283 if (needs_row(graph, node))
2284 graph->region[i].len = 2 * (node->nvar - skip);
2285 else
2286 graph->region[i].len = 0;
2287 }
2288 lp = isl_basic_set_copy(graph->lp);
2289 sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
2290 graph->region, &check_conflict, graph);
2291 return sol;
2292}
2293
2294/* Update the schedules of all nodes based on the given solution
2295 * of the LP problem.
2296 * The new row is added to the current band.
2297 * All possibly negative coefficients are encoded as a difference
2298 * of two non-negative variables, so we need to perform the subtraction
2299 * here. Moreover, if use_cmap is set, then the solution does
2300 * not refer to the actual coefficients c_i_x, but instead to variables
2301 * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
2302 * In this case, we then also need to perform this multiplication
2303 * to obtain the values of c_i_x.
2304 *
2305 * If coincident is set, then the caller guarantees that the new
2306 * row satisfies the coincidence constraints.
2307 */
2308static int update_schedule(struct isl_sched_graph *graph,
2309 __isl_take isl_vec *sol, int use_cmap, int coincident)
2310{
2311 int i, j;
2312 isl_vec *csol = NULL((void*)0);
2313
2314 if (!sol)
2315 goto error;
2316 if (sol->size == 0)
2317 isl_die(sol->ctx, isl_error_internal,do { isl_handle_error(sol->ctx, isl_error_internal, "no solution found"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2318); goto error; } while (0)
2318 "no solution found", goto error)do { isl_handle_error(sol->ctx, isl_error_internal, "no solution found"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2318); goto error; } while (0);
2319 if (graph->n_total_row >= graph->max_row)
2320 isl_die(sol->ctx, isl_error_internal,do { isl_handle_error(sol->ctx, isl_error_internal, "too many schedule rows"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2321); goto error; } while (0)
2321 "too many schedule rows", goto error)do { isl_handle_error(sol->ctx, isl_error_internal, "too many schedule rows"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2321); goto error; } while (0);
2322
2323 for (i = 0; i < graph->n; ++i) {
2324 struct isl_sched_node *node = &graph->node[i];
2325 int pos = node->start;
2326 int row = isl_mat_rows(node->sched);
2327
2328 isl_vec_free(csol);
2329 csol = isl_vec_alloc(sol->ctx, node->nvar);
2330 if (!csol)
2331 goto error;
2332
2333 isl_map_free(node->sched_map);
2334 node->sched_map = NULL((void*)0);
2335 node->sched = isl_mat_add_rows(node->sched, 1);
2336 if (!node->sched)
2337 goto error;
2338 node->sched = isl_mat_set_element(node->sched, row, 0,
2339 sol->el[1 + pos]);
2340 for (j = 0; j < node->nparam + node->nvar; ++j)
2341 isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],isl_sioimath_sub((sol->el[1 + pos + 1 + 2 * j + 1]), *(sol
->el[1 + pos + 1 + 2 * j + 1]), *(sol->el[1 + pos + 1 +
2 * j]))
2342 sol->el[1 + pos + 1 + 2 * j + 1],isl_sioimath_sub((sol->el[1 + pos + 1 + 2 * j + 1]), *(sol
->el[1 + pos + 1 + 2 * j + 1]), *(sol->el[1 + pos + 1 +
2 * j]))
2343 sol->el[1 + pos + 1 + 2 * j])isl_sioimath_sub((sol->el[1 + pos + 1 + 2 * j + 1]), *(sol
->el[1 + pos + 1 + 2 * j + 1]), *(sol->el[1 + pos + 1 +
2 * j]));
2344 for (j = 0; j < node->nparam; ++j)
2345 node->sched = isl_mat_set_element(node->sched,
2346 row, 1 + j, sol->el[1+pos+1+2*j+1]);
2347 for (j = 0; j < node->nvar; ++j)
2348 isl_int_set(csol->el[j],isl_sioimath_set((csol->el[j]), *(sol->el[1+pos+1+2*(node
->nparam+j)+1]))
2349 sol->el[1+pos+1+2*(node->nparam+j)+1])isl_sioimath_set((csol->el[j]), *(sol->el[1+pos+1+2*(node
->nparam+j)+1]));
2350 if (use_cmap)
2351 csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
2352 csol);
2353 if (!csol)
2354 goto error;
2355 for (j = 0; j < node->nvar; ++j)
2356 node->sched = isl_mat_set_element(node->sched,
2357 row, 1 + node->nparam + j, csol->el[j]);
2358 node->coincident[graph->n_total_row] = coincident;
2359 }
2360 isl_vec_free(sol);
2361 isl_vec_free(csol);
2362
2363 graph->n_row++;
2364 graph->n_total_row++;
2365
2366 return 0;
2367error:
2368 isl_vec_free(sol);
2369 isl_vec_free(csol);
2370 return -1;
2371}
2372
2373/* Convert row "row" of node->sched into an isl_aff living in "ls"
2374 * and return this isl_aff.
2375 */
2376static __isl_give isl_aff *extract_schedule_row(__isl_take isl_local_space *ls,
2377 struct isl_sched_node *node, int row)
2378{
2379 int j;
2380 isl_int v;
2381 isl_aff *aff;
2382
2383 isl_int_init(v)isl_sioimath_init((v));
2384
2385 aff = isl_aff_zero_on_domain(ls);
2386 isl_mat_get_element(node->sched, row, 0, &v);
2387 aff = isl_aff_set_constant(aff, v);
2388 for (j = 0; j < node->nparam; ++j) {
2389 isl_mat_get_element(node->sched, row, 1 + j, &v);
2390 aff = isl_aff_set_coefficient(aff, isl_dim_param, j, v);
2391 }
2392 for (j = 0; j < node->nvar; ++j) {
2393 isl_mat_get_element(node->sched, row, 1 + node->nparam + j, &v);
2394 aff = isl_aff_set_coefficient(aff, isl_dim_in, j, v);
2395 }
2396
2397 isl_int_clear(v)isl_sioimath_clear((v));
2398
2399 return aff;
2400}
2401
2402/* Convert the "n" rows starting at "first" of node->sched into a multi_aff
2403 * and return this multi_aff.
2404 *
2405 * The result is defined over the uncompressed node domain.
2406 */
2407static __isl_give isl_multi_aff *node_extract_partial_schedule_multi_aff(
2408 struct isl_sched_node *node, int first, int n)
2409{
2410 int i;
2411 isl_space *space;
2412 isl_local_space *ls;
2413 isl_aff *aff;
2414 isl_multi_aff *ma;
2415 int nrow;
2416
2417 nrow = isl_mat_rows(node->sched);
Value stored to 'nrow' is never read
2418 if (node->compressed)
2419 space = isl_multi_aff_get_domain_space(node->decompress);
2420 else
2421 space = isl_space_copy(node->space);
2422 ls = isl_local_space_from_space(isl_space_copy(space));
2423 space = isl_space_from_domain(space);
2424 space = isl_space_add_dims(space, isl_dim_out, n);
2425 ma = isl_multi_aff_zero(space);
2426
2427 for (i = first; i < first + n; ++i) {
2428 aff = extract_schedule_row(isl_local_space_copy(ls), node, i);
2429 ma = isl_multi_aff_set_aff(ma, i - first, aff);
2430 }
2431
2432 isl_local_space_free(ls);
2433
2434 if (node->compressed)
2435 ma = isl_multi_aff_pullback_multi_aff(ma,
2436 isl_multi_aff_copy(node->compress));
2437
2438 return ma;
2439}
2440
2441/* Convert node->sched into a multi_aff and return this multi_aff.
2442 *
2443 * The result is defined over the uncompressed node domain.
2444 */
2445static __isl_give isl_multi_aff *node_extract_schedule_multi_aff(
2446 struct isl_sched_node *node)
2447{
2448 int nrow;
2449
2450 nrow = isl_mat_rows(node->sched);
2451 return node_extract_partial_schedule_multi_aff(node, 0, nrow);
2452}
2453
2454/* Convert node->sched into a map and return this map.
2455 *
2456 * The result is cached in node->sched_map, which needs to be released
2457 * whenever node->sched is updated.
2458 * It is defined over the uncompressed node domain.
2459 */
2460static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
2461{
2462 if (!node->sched_map) {
2463 isl_multi_aff *ma;
2464
2465 ma = node_extract_schedule_multi_aff(node);
2466 node->sched_map = isl_map_from_multi_aff(ma);
2467 }
2468
2469 return isl_map_copy(node->sched_map);
2470}
2471
2472/* Construct a map that can be used to update a dependence relation
2473 * based on the current schedule.
2474 * That is, construct a map expressing that source and sink
2475 * are executed within the same iteration of the current schedule.
2476 * This map can then be intersected with the dependence relation.
2477 * This is not the most efficient way, but this shouldn't be a critical
2478 * operation.
2479 */
2480static __isl_give isl_map *specializer(struct isl_sched_node *src,
2481 struct isl_sched_node *dst)
2482{
2483 isl_map *src_sched, *dst_sched;
2484
2485 src_sched = node_extract_schedule(src);
2486 dst_sched = node_extract_schedule(dst);
2487 return isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
2488}
2489
2490/* Intersect the domains of the nested relations in domain and range
2491 * of "umap" with "map".
2492 */
2493static __isl_give isl_union_map *intersect_domains(
2494 __isl_take isl_union_map *umap, __isl_keep isl_map *map)
2495{
2496 isl_union_set *uset;
2497
2498 umap = isl_union_map_zip(umap);
2499 uset = isl_union_set_from_set(isl_map_wrap(isl_map_copy(map)));
2500 umap = isl_union_map_intersect_domain(umap, uset);
2501 umap = isl_union_map_zip(umap);
2502 return umap;
2503}
2504
2505/* Update the dependence relation of the given edge based
2506 * on the current schedule.
2507 * If the dependence is carried completely by the current schedule, then
2508 * it is removed from the edge_tables. It is kept in the list of edges
2509 * as otherwise all edge_tables would have to be recomputed.
2510 */
2511static int update_edge(struct isl_sched_graph *graph,
2512 struct isl_sched_edge *edge)
2513{
2514 int empty;
2515 isl_map *id;
2516
2517 id = specializer(edge->src, edge->dst);
2518 edge->map = isl_map_intersect(edge->map, isl_map_copy(id));
2519 if (!edge->map)
2520 goto error;
2521
2522 if (edge->tagged_condition) {
2523 edge->tagged_condition =
2524 intersect_domains(edge->tagged_condition, id);
2525 if (!edge->tagged_condition)
2526 goto error;
2527 }
2528 if (edge->tagged_validity) {
2529 edge->tagged_validity =
2530 intersect_domains(edge->tagged_validity, id);
2531 if (!edge->tagged_validity)
2532 goto error;
2533 }
2534
2535 empty = isl_map_plain_is_empty(edge->map);
2536 if (empty < 0)
2537 goto error;
2538 if (empty)
2539 graph_remove_edge(graph, edge);
2540
2541 isl_map_free(id);
2542 return 0;
2543error:
2544 isl_map_free(id);
2545 return -1;
2546}
2547
2548/* Does the domain of "umap" intersect "uset"?
2549 */
2550static int domain_intersects(__isl_keep isl_union_map *umap,
2551 __isl_keep isl_union_set *uset)
2552{
2553 int empty;
2554
2555 umap = isl_union_map_copy(umap);
2556 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(uset));
2557 empty = isl_union_map_is_empty(umap);
2558 isl_union_map_free(umap);
2559
2560 return empty < 0 ? -1 : !empty;
2561}
2562
2563/* Does the range of "umap" intersect "uset"?
2564 */
2565static int range_intersects(__isl_keep isl_union_map *umap,
2566 __isl_keep isl_union_set *uset)
2567{
2568 int empty;
2569
2570 umap = isl_union_map_copy(umap);
2571 umap = isl_union_map_intersect_range(umap, isl_union_set_copy(uset));
2572 empty = isl_union_map_is_empty(umap);
2573 isl_union_map_free(umap);
2574
2575 return empty < 0 ? -1 : !empty;
2576}
2577
2578/* Are the condition dependences of "edge" local with respect to
2579 * the current schedule?
2580 *
2581 * That is, are domain and range of the condition dependences mapped
2582 * to the same point?
2583 *
2584 * In other words, is the condition false?
2585 */
2586static int is_condition_false(struct isl_sched_edge *edge)
2587{
2588 isl_union_map *umap;
2589 isl_map *map, *sched, *test;
2590 int empty, local;
2591
2592 empty = isl_union_map_is_empty(edge->tagged_condition);
2593 if (empty < 0 || empty)
2594 return empty;
2595
2596 umap = isl_union_map_copy(edge->tagged_condition);
2597 umap = isl_union_map_zip(umap);
2598 umap = isl_union_set_unwrap(isl_union_map_domain(umap));
2599 map = isl_map_from_union_map(umap);
2600
2601 sched = node_extract_schedule(edge->src);
2602 map = isl_map_apply_domain(map, sched);
2603 sched = node_extract_schedule(edge->dst);
2604 map = isl_map_apply_range(map, sched);
2605
2606 test = isl_map_identity(isl_map_get_space(map));
2607 local = isl_map_is_subset(map, test);
2608 isl_map_free(map);
2609 isl_map_free(test);
2610
2611 return local;
2612}
2613
2614/* For each conditional validity constraint that is adjacent
2615 * to a condition with domain in condition_source or range in condition_sink,
2616 * turn it into an unconditional validity constraint.
2617 */
2618static int unconditionalize_adjacent_validity(struct isl_sched_graph *graph,
2619 __isl_take isl_union_set *condition_source,
2620 __isl_take isl_union_set *condition_sink)
2621{
2622 int i;
2623
2624 condition_source = isl_union_set_coalesce(condition_source);
2625 condition_sink = isl_union_set_coalesce(condition_sink);
2626
2627 for (i = 0; i < graph->n_edge; ++i) {
2628 int adjacent;
2629 isl_union_map *validity;
2630
2631 if (!graph->edge[i].conditional_validity)
2632 continue;
2633 if (graph->edge[i].validity)
2634 continue;
2635
2636 validity = graph->edge[i].tagged_validity;
2637 adjacent = domain_intersects(validity, condition_sink);
2638 if (adjacent >= 0 && !adjacent)
2639 adjacent = range_intersects(validity, condition_source);
2640 if (adjacent < 0)
2641 goto error;
2642 if (!adjacent)
2643 continue;
2644
2645 graph->edge[i].validity = 1;
2646 }
2647
2648 isl_union_set_free(condition_source);
2649 isl_union_set_free(condition_sink);
2650 return 0;
2651error:
2652 isl_union_set_free(condition_source);
2653 isl_union_set_free(condition_sink);
2654 return -1;
2655}
2656
2657/* Update the dependence relations of all edges based on the current schedule
2658 * and enforce conditional validity constraints that are adjacent
2659 * to satisfied condition constraints.
2660 *
2661 * First check if any of the condition constraints are satisfied
2662 * (i.e., not local to the outer schedule) and keep track of
2663 * their domain and range.
2664 * Then update all dependence relations (which removes the non-local
2665 * constraints).
2666 * Finally, if any condition constraints turned out to be satisfied,
2667 * then turn all adjacent conditional validity constraints into
2668 * unconditional validity constraints.
2669 */
2670static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
2671{
2672 int i;
2673 int any = 0;
2674 isl_union_set *source, *sink;
2675
2676 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
2677 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
2678 for (i = 0; i < graph->n_edge; ++i) {
2679 int local;
2680 isl_union_set *uset;
2681 isl_union_map *umap;
2682
2683 if (!graph->edge[i].condition)
2684 continue;
2685 if (graph->edge[i].local)
2686 continue;
2687 local = is_condition_false(&graph->edge[i]);
2688 if (local < 0)
2689 goto error;
2690 if (local)
2691 continue;
2692
2693 any = 1;
2694
2695 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
2696 uset = isl_union_map_domain(umap);
2697 source = isl_union_set_union(source, uset);
2698
2699 umap = isl_union_map_copy(graph->edge[i].tagged_condition);
2700 uset = isl_union_map_range(umap);
2701 sink = isl_union_set_union(sink, uset);
2702 }
2703
2704 for (i = graph->n_edge - 1; i >= 0; --i) {
2705 if (update_edge(graph, &graph->edge[i]) < 0)
2706 goto error;
2707 }
2708
2709 if (any)
2710 return unconditionalize_adjacent_validity(graph, source, sink);
2711
2712 isl_union_set_free(source);
2713 isl_union_set_free(sink);
2714 return 0;
2715error:
2716 isl_union_set_free(source);
2717 isl_union_set_free(sink);
2718 return -1;
2719}
2720
2721static void next_band(struct isl_sched_graph *graph)
2722{
2723 graph->band_start = graph->n_total_row;
2724}
2725
2726/* Return the union of the universe domains of the nodes in "graph"
2727 * that satisfy "pred".
2728 */
2729static __isl_give isl_union_set *isl_sched_graph_domain(isl_ctx *ctx,
2730 struct isl_sched_graph *graph,
2731 int (*pred)(struct isl_sched_node *node, int data), int data)
2732{
2733 int i;
2734 isl_setisl_map *set;
2735 isl_union_set *dom;
2736
2737 for (i = 0; i < graph->n; ++i)
2738 if (pred(&graph->node[i], data))
2739 break;
2740
2741 if (i >= graph->n)
2742 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "empty component"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2743); return ((void*)0); } while (0)
2743 "empty component", return NULL)do { isl_handle_error(ctx, isl_error_internal, "empty component"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2743); return ((void*)0); } while (0);
2744
2745 set = isl_set_universe(isl_space_copy(graph->node[i].space));
2746 dom = isl_union_set_from_set(set);
2747
2748 for (i = i + 1; i < graph->n; ++i) {
2749 if (!pred(&graph->node[i], data))
2750 continue;
2751 set = isl_set_universe(isl_space_copy(graph->node[i].space));
2752 dom = isl_union_set_union(dom, isl_union_set_from_set(set));
2753 }
2754
2755 return dom;
2756}
2757
2758/* Return a list of unions of universe domains, where each element
2759 * in the list corresponds to an SCC (or WCC) indexed by node->scc.
2760 */
2761static __isl_give isl_union_set_list *extract_sccs(isl_ctx *ctx,
2762 struct isl_sched_graph *graph)
2763{
2764 int i;
2765 isl_union_set_list *filters;
2766
2767 filters = isl_union_set_list_alloc(ctx, graph->scc);
2768 for (i = 0; i < graph->scc; ++i) {
2769 isl_union_set *dom;
2770
2771 dom = isl_sched_graph_domain(ctx, graph, &node_scc_exactly, i);
2772 filters = isl_union_set_list_add(filters, dom);
2773 }
2774
2775 return filters;
2776}
2777
2778/* Return a list of two unions of universe domains, one for the SCCs up
2779 * to and including graph->src_scc and another for the other SCCS.
2780 */
2781static __isl_give isl_union_set_list *extract_split(isl_ctx *ctx,
2782 struct isl_sched_graph *graph)
2783{
2784 isl_union_set *dom;
2785 isl_union_set_list *filters;
2786
2787 filters = isl_union_set_list_alloc(ctx, 2);
2788 dom = isl_sched_graph_domain(ctx, graph,
2789 &node_scc_at_most, graph->src_scc);
2790 filters = isl_union_set_list_add(filters, dom);
2791 dom = isl_sched_graph_domain(ctx, graph,
2792 &node_scc_at_least, graph->src_scc + 1);
2793 filters = isl_union_set_list_add(filters, dom);
2794
2795 return filters;
2796}
2797
2798/* Copy nodes that satisfy node_pred from the src dependence graph
2799 * to the dst dependence graph.
2800 */
2801static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
2802 int (*node_pred)(struct isl_sched_node *node, int data), int data)
2803{
2804 int i;
2805
2806 dst->n = 0;
2807 for (i = 0; i < src->n; ++i) {
2808 int j;
2809
2810 if (!node_pred(&src->node[i], data))
2811 continue;
2812
2813 j = dst->n;
2814 dst->node[j].space = isl_space_copy(src->node[i].space);
2815 dst->node[j].compressed = src->node[i].compressed;
2816 dst->node[j].hull = isl_set_copy(src->node[i].hull);
2817 dst->node[j].compress =
2818 isl_multi_aff_copy(src->node[i].compress);
2819 dst->node[j].decompress =
2820 isl_multi_aff_copy(src->node[i].decompress);
2821 dst->node[j].nvar = src->node[i].nvar;
2822 dst->node[j].nparam = src->node[i].nparam;
2823 dst->node[j].sched = isl_mat_copy(src->node[i].sched);
2824 dst->node[j].sched_map = isl_map_copy(src->node[i].sched_map);
2825 dst->node[j].coincident = src->node[i].coincident;
2826 dst->n++;
2827
2828 if (!dst->node[j].space || !dst->node[j].sched)
2829 return -1;
2830 if (dst->node[j].compressed &&
2831 (!dst->node[j].hull || !dst->node[j].compress ||
2832 !dst->node[j].decompress))
2833 return -1;
2834 }
2835
2836 return 0;
2837}
2838
2839/* Copy non-empty edges that satisfy edge_pred from the src dependence graph
2840 * to the dst dependence graph.
2841 * If the source or destination node of the edge is not in the destination
2842 * graph, then it must be a backward proximity edge and it should simply
2843 * be ignored.
2844 */
2845static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
2846 struct isl_sched_graph *src,
2847 int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
2848{
2849 int i;
2850 enum isl_edge_type t;
2851
2852 dst->n_edge = 0;
2853 for (i = 0; i < src->n_edge; ++i) {
2854 struct isl_sched_edge *edge = &src->edge[i];
2855 isl_map *map;
2856 isl_union_map *tagged_condition;
2857 isl_union_map *tagged_validity;
2858 struct isl_sched_node *dst_src, *dst_dst;
2859
2860 if (!edge_pred(edge, data))
2861 continue;
2862
2863 if (isl_map_plain_is_empty(edge->map))
2864 continue;
2865
2866 dst_src = graph_find_node(ctx, dst, edge->src->space);
2867 dst_dst = graph_find_node(ctx, dst, edge->dst->space);
2868 if (!dst_src || !dst_dst) {
2869 if (edge->validity || edge->conditional_validity)
2870 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "backward (conditional) validity edge"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2872); return -1; } while (0)
2871 "backward (conditional) validity edge",do { isl_handle_error(ctx, isl_error_internal, "backward (conditional) validity edge"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2872); return -1; } while (0)
2872 return -1)do { isl_handle_error(ctx, isl_error_internal, "backward (conditional) validity edge"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 2872); return -1; } while (0);
2873 continue;
2874 }
2875
2876 map = isl_map_copy(edge->map);
2877 tagged_condition = isl_union_map_copy(edge->tagged_condition);
2878 tagged_validity = isl_union_map_copy(edge->tagged_validity);
2879
2880 dst->edge[dst->n_edge].src = dst_src;
2881 dst->edge[dst->n_edge].dst = dst_dst;
2882 dst->edge[dst->n_edge].map = map;
2883 dst->edge[dst->n_edge].tagged_condition = tagged_condition;
2884 dst->edge[dst->n_edge].tagged_validity = tagged_validity;
2885 dst->edge[dst->n_edge].validity = edge->validity;
2886 dst->edge[dst->n_edge].proximity = edge->proximity;
2887 dst->edge[dst->n_edge].coincidence = edge->coincidence;
2888 dst->edge[dst->n_edge].condition = edge->condition;
2889 dst->edge[dst->n_edge].conditional_validity =
2890 edge->conditional_validity;
2891 dst->n_edge++;
2892
2893 if (edge->tagged_condition && !tagged_condition)
2894 return -1;
2895 if (edge->tagged_validity && !tagged_validity)
2896 return -1;
2897
2898 for (t = isl_edge_first; t <= isl_edge_last; ++t) {
2899 if (edge !=
2900 graph_find_edge(src, t, edge->src, edge->dst))
2901 continue;
2902 if (graph_edge_table_add(ctx, dst, t,
2903 &dst->edge[dst->n_edge - 1]) < 0)
2904 return -1;
2905 }
2906 }
2907
2908 return 0;
2909}
2910
2911/* Compute the maximal number of variables over all nodes.
2912 * This is the maximal number of linearly independent schedule
2913 * rows that we need to compute.
2914 * Just in case we end up in a part of the dependence graph
2915 * with only lower-dimensional domains, we make sure we will
2916 * compute the required amount of extra linearly independent rows.
2917 */
2918static int compute_maxvar(struct isl_sched_graph *graph)
2919{
2920 int i;
2921
2922 graph->maxvar = 0;
2923 for (i = 0; i < graph->n; ++i) {
2924 struct isl_sched_node *node = &graph->node[i];
2925 int nvar;
2926
2927 if (node_update_cmap(node) < 0)
2928 return -1;
2929 nvar = node->nvar + graph->n_row - node->rank;
2930 if (nvar > graph->maxvar)
2931 graph->maxvar = nvar;
2932 }
2933
2934 return 0;
2935}
2936
2937static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
2938 struct isl_sched_graph *graph);
2939static __isl_give isl_schedule_node *compute_schedule_wcc(
2940 isl_schedule_node *node, struct isl_sched_graph *graph);
2941
2942/* Compute a schedule for a subgraph of "graph". In particular, for
2943 * the graph composed of nodes that satisfy node_pred and edges that
2944 * that satisfy edge_pred. The caller should precompute the number
2945 * of nodes and edges that satisfy these predicates and pass them along
2946 * as "n" and "n_edge".
2947 * If the subgraph is known to consist of a single component, then wcc should
2948 * be set and then we call compute_schedule_wcc on the constructed subgraph.
2949 * Otherwise, we call compute_schedule, which will check whether the subgraph
2950 * is connected.
2951 *
2952 * The schedule is inserted at "node" and the updated schedule node
2953 * is returned.
2954 */
2955static __isl_give isl_schedule_node *compute_sub_schedule(
2956 __isl_take isl_schedule_node *node, isl_ctx *ctx,
2957 struct isl_sched_graph *graph, int n, int n_edge,
2958 int (*node_pred)(struct isl_sched_node *node, int data),
2959 int (*edge_pred)(struct isl_sched_edge *edge, int data),
2960 int data, int wcc)
2961{
2962 struct isl_sched_graph split = { 0 };
2963 int t;
2964
2965 if (graph_alloc(ctx, &split, n, n_edge) < 0)
2966 goto error;
2967 if (copy_nodes(&split, graph, node_pred, data) < 0)
2968 goto error;
2969 if (graph_init_table(ctx, &split) < 0)
2970 goto error;
2971 for (t = 0; t <= isl_edge_last; ++t)
2972 split.max_edge[t] = graph->max_edge[t];
2973 if (graph_init_edge_tables(ctx, &split) < 0)
2974 goto error;
2975 if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
2976 goto error;
2977 split.n_row = graph->n_row;
2978 split.max_row = graph->max_row;
2979 split.n_total_row = graph->n_total_row;
2980 split.band_start = graph->band_start;
2981
2982 if (wcc)
2983 node = compute_schedule_wcc(node, &split);
2984 else
2985 node = compute_schedule(node, &split);
2986
2987 graph_free(ctx, &split);
2988 return node;
2989error:
2990 graph_free(ctx, &split);
2991 return isl_schedule_node_free(node);
2992}
2993
2994static int edge_scc_exactly(struct isl_sched_edge *edge, int scc)
2995{
2996 return edge->src->scc == scc && edge->dst->scc == scc;
2997}
2998
2999static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
3000{
3001 return edge->dst->scc <= scc;
3002}
3003
3004static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
3005{
3006 return edge->src->scc >= scc;
3007}
3008
3009/* Reset the current band by dropping all its schedule rows.
3010 */
3011static int reset_band(struct isl_sched_graph *graph)
3012{
3013 int i;
3014 int drop;
3015
3016 drop = graph->n_total_row - graph->band_start;
3017 graph->n_total_row -= drop;
3018 graph->n_row -= drop;
3019
3020 for (i = 0; i < graph->n; ++i) {
3021 struct isl_sched_node *node = &graph->node[i];
3022
3023 isl_map_free(node->sched_map);
3024 node->sched_map = NULL((void*)0);
3025
3026 node->sched = isl_mat_drop_rows(node->sched,
3027 graph->band_start, drop);
3028
3029 if (!node->sched)
3030 return -1;
3031 }
3032
3033 return 0;
3034}
3035
3036/* Split the current graph into two parts and compute a schedule for each
3037 * part individually. In particular, one part consists of all SCCs up
3038 * to and including graph->src_scc, while the other part contains the other
3039 * SCCS. The split is enforced by a sequence node inserted at position "node"
3040 * in the schedule tree. Return the updated schedule node.
3041 *
3042 * The current band is reset. It would be possible to reuse
3043 * the previously computed rows as the first rows in the next
3044 * band, but recomputing them may result in better rows as we are looking
3045 * at a smaller part of the dependence graph.
3046 */
3047static __isl_give isl_schedule_node *compute_split_schedule(
3048 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3049{
3050 int i, n, e1, e2;
3051 isl_ctx *ctx;
3052 isl_union_set_list *filters;
3053
3054 if (!node)
3055 return NULL((void*)0);
3056
3057 if (reset_band(graph) < 0)
3058 return isl_schedule_node_free(node);
3059
3060 n = 0;
3061 for (i = 0; i < graph->n; ++i) {
3062 struct isl_sched_node *node = &graph->node[i];
3063 int before = node->scc <= graph->src_scc;
3064
3065 if (before)
3066 n++;
3067 }
3068
3069 e1 = e2 = 0;
3070 for (i = 0; i < graph->n_edge; ++i) {
3071 if (graph->edge[i].dst->scc <= graph->src_scc)
3072 e1++;
3073 if (graph->edge[i].src->scc > graph->src_scc)
3074 e2++;
3075 }
3076
3077 next_band(graph);
3078
3079 ctx = isl_schedule_node_get_ctx(node);
3080 filters = extract_split(ctx, graph);
3081 node = isl_schedule_node_insert_sequence(node, filters);
3082 node = isl_schedule_node_child(node, 0);
3083 node = isl_schedule_node_child(node, 0);
3084
3085 node = compute_sub_schedule(node, ctx, graph, n, e1,
3086 &node_scc_at_most, &edge_dst_scc_at_most,
3087 graph->src_scc, 0);
3088 node = isl_schedule_node_parent(node);
3089 node = isl_schedule_node_next_sibling(node);
3090 node = isl_schedule_node_child(node, 0);
3091 node = compute_sub_schedule(node, ctx, graph, graph->n - n, e2,
3092 &node_scc_at_least, &edge_src_scc_at_least,
3093 graph->src_scc + 1, 0);
3094 node = isl_schedule_node_parent(node);
3095 node = isl_schedule_node_parent(node);
3096
3097 return node;
3098}
3099
3100/* Insert a band node at position "node" in the schedule tree corresponding
3101 * to the current band in "graph". Mark the band node permutable
3102 * if "permutable" is set.
3103 * The partial schedules and the coincidence property are extracted
3104 * from the graph nodes.
3105 * Return the updated schedule node.
3106 */
3107static __isl_give isl_schedule_node *insert_current_band(
3108 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
3109 int permutable)
3110{
3111 int i;
3112 int start, end, n;
3113 isl_multi_aff *ma;
3114 isl_multi_pw_aff *mpa;
3115 isl_multi_union_pw_aff *mupa;
3116
3117 if (!node)
3118 return NULL((void*)0);
3119
3120 if (graph->n < 1)
3121 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_internal
, "graph should have at least one node", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3123); return isl_schedule_node_free(node); } while (0)
3122 "graph should have at least one node",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_internal
, "graph should have at least one node", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3123); return isl_schedule_node_free(node); } while (0)
3123 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_internal
, "graph should have at least one node", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3123); return isl_schedule_node_free(node); } while (0);
3124
3125 start = graph->band_start;
3126 end = graph->n_total_row;
3127 n = end - start;
3128
3129 ma = node_extract_partial_schedule_multi_aff(&graph->node[0], start, n);
3130 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3131 mupa = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3132
3133 for (i = 1; i < graph->n; ++i) {
3134 isl_multi_union_pw_aff *mupa_i;
3135
3136 ma = node_extract_partial_schedule_multi_aff(&graph->node[i],
3137 start, n);
3138 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3139 mupa_i = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3140 mupa = isl_multi_union_pw_aff_union_add(mupa, mupa_i);
3141 }
3142 node = isl_schedule_node_insert_partial_schedule(node, mupa);
3143
3144 for (i = 0; i < n; ++i)
3145 node = isl_schedule_node_band_member_set_coincident(node, i,
3146 graph->node[0].coincident[start + i]);
3147 node = isl_schedule_node_band_set_permutable(node, permutable);
3148
3149 return node;
3150}
3151
3152/* Update the dependence relations based on the current schedule,
3153 * add the current band to "node" and then continue with the computation
3154 * of the next band.
3155 * Return the updated schedule node.
3156 */
3157static __isl_give isl_schedule_node *compute_next_band(
3158 __isl_take isl_schedule_node *node,
3159 struct isl_sched_graph *graph, int permutable)
3160{
3161 isl_ctx *ctx;
3162
3163 if (!node)
3164 return NULL((void*)0);
3165
3166 ctx = isl_schedule_node_get_ctx(node);
3167 if (update_edges(ctx, graph) < 0)
3168 return isl_schedule_node_free(node);
3169 node = insert_current_band(node, graph, permutable);
3170 next_band(graph);
3171
3172 node = isl_schedule_node_child(node, 0);
3173 node = compute_schedule(node, graph);
3174 node = isl_schedule_node_parent(node);
3175
3176 return node;
3177}
3178
3179/* Add constraints to graph->lp that force the dependence "map" (which
3180 * is part of the dependence relation of "edge")
3181 * to be respected and attempt to carry it, where the edge is one from
3182 * a node j to itself. "pos" is the sequence number of the given map.
3183 * That is, add constraints that enforce
3184 *
3185 * (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
3186 * = c_j_x (y - x) >= e_i
3187 *
3188 * for each (x,y) in R.
3189 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3190 * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
3191 * with each coefficient in c_j_x represented as a pair of non-negative
3192 * coefficients.
3193 */
3194static int add_intra_constraints(struct isl_sched_graph *graph,
3195 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
3196{
3197 unsigned total;
3198 isl_ctx *ctx = isl_map_get_ctx(map);
3199 isl_space *dim;
3200 isl_dim_map *dim_map;
3201 isl_basic_setisl_basic_map *coef;
3202 struct isl_sched_node *node = edge->src;
3203
3204 coef = intra_coefficients(graph, node, map);
3205 if (!coef)
3206 return -1;
3207
3208 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
3209
3210 total = isl_basic_set_total_dim(graph->lp);
3211 dim_map = isl_dim_map_alloc(ctx, total);
3212 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3213 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
3214 isl_space_dim(dim, isl_dim_set), 1,
3215 node->nvar, -1);
3216 isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
3217 isl_space_dim(dim, isl_dim_set), 1,
3218 node->nvar, 1);
3219 graph->lp = isl_basic_set_extend_constraints(graph->lp,
3220 coef->n_eq, coef->n_ineq);
3221 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
3222 coef, dim_map);
3223 isl_space_free(dim);
3224
3225 return 0;
3226}
3227
3228/* Add constraints to graph->lp that force the dependence "map" (which
3229 * is part of the dependence relation of "edge")
3230 * to be respected and attempt to carry it, where the edge is one from
3231 * node j to node k. "pos" is the sequence number of the given map.
3232 * That is, add constraints that enforce
3233 *
3234 * (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
3235 *
3236 * for each (x,y) in R.
3237 * We obtain general constraints on coefficients (c_0, c_n, c_x)
3238 * of valid constraints for R and then plug in
3239 * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
3240 * with each coefficient (except e_i, c_k_0 and c_j_0)
3241 * represented as a pair of non-negative coefficients.
3242 */
3243static int add_inter_constraints(struct isl_sched_graph *graph,
3244 struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
3245{
3246 unsigned total;
3247 isl_ctx *ctx = isl_map_get_ctx(map);
3248 isl_space *dim;
3249 isl_dim_map *dim_map;
3250 isl_basic_setisl_basic_map *coef;
3251 struct isl_sched_node *src = edge->src;
3252 struct isl_sched_node *dst = edge->dst;
3253
3254 coef = inter_coefficients(graph, edge, map);
3255 if (!coef)
3256 return -1;
3257
3258 dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
3259
3260 total = isl_basic_set_total_dim(graph->lp);
3261 dim_map = isl_dim_map_alloc(ctx, total);
3262
3263 isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
3264
3265 isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
3266 isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
3267 isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
3268 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
3269 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
3270 dst->nvar, -1);
3271 isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
3272 isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
3273 dst->nvar, 1);
3274
3275 isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
3276 isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
3277 isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
3278 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
3279 isl_space_dim(dim, isl_dim_set), 1,
3280 src->nvar, 1);
3281 isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
3282 isl_space_dim(dim, isl_dim_set), 1,
3283 src->nvar, -1);
3284
3285 graph->lp = isl_basic_set_extend_constraints(graph->lp,
3286 coef->n_eq, coef->n_ineq);
3287 graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
3288 coef, dim_map);
3289 isl_space_free(dim);
3290
3291 return 0;
3292}
3293
3294/* Add constraints to graph->lp that force all (conditional) validity
3295 * dependences to be respected and attempt to carry them.
3296 */
3297static int add_all_constraints(struct isl_sched_graph *graph)
3298{
3299 int i, j;
3300 int pos;
3301
3302 pos = 0;
3303 for (i = 0; i < graph->n_edge; ++i) {
3304 struct isl_sched_edge *edge= &graph->edge[i];
3305
3306 if (!edge->validity && !edge->conditional_validity)
3307 continue;
3308
3309 for (j = 0; j < edge->map->n; ++j) {
3310 isl_basic_map *bmap;
3311 isl_map *map;
3312
3313 bmap = isl_basic_map_copy(edge->map->p[j]);
3314 map = isl_map_from_basic_map(bmap);
3315
3316 if (edge->src == edge->dst &&
3317 add_intra_constraints(graph, edge, map, pos) < 0)
3318 return -1;
3319 if (edge->src != edge->dst &&
3320 add_inter_constraints(graph, edge, map, pos) < 0)
3321 return -1;
3322 ++pos;
3323 }
3324 }
3325
3326 return 0;
3327}
3328
3329/* Count the number of equality and inequality constraints
3330 * that will be added to the carry_lp problem.
3331 * We count each edge exactly once.
3332 */
3333static int count_all_constraints(struct isl_sched_graph *graph,
3334 int *n_eq, int *n_ineq)
3335{
3336 int i, j;
3337
3338 *n_eq = *n_ineq = 0;
3339 for (i = 0; i < graph->n_edge; ++i) {
3340 struct isl_sched_edge *edge= &graph->edge[i];
3341 for (j = 0; j < edge->map->n; ++j) {
3342 isl_basic_map *bmap;
3343 isl_map *map;
3344
3345 bmap = isl_basic_map_copy(edge->map->p[j]);
3346 map = isl_map_from_basic_map(bmap);
3347
3348 if (count_map_constraints(graph, edge, map,
3349 n_eq, n_ineq, 1, 0) < 0)
3350 return -1;
3351 }
3352 }
3353
3354 return 0;
3355}
3356
3357/* Construct an LP problem for finding schedule coefficients
3358 * such that the schedule carries as many dependences as possible.
3359 * In particular, for each dependence i, we bound the dependence distance
3360 * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
3361 * of all e_i's. Dependences with e_i = 0 in the solution are simply
3362 * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
3363 * Note that if the dependence relation is a union of basic maps,
3364 * then we have to consider each basic map individually as it may only
3365 * be possible to carry the dependences expressed by some of those
3366 * basic maps and not all of them.
3367 * Below, we consider each of those basic maps as a separate "edge".
3368 *
3369 * All variables of the LP are non-negative. The actual coefficients
3370 * may be negative, so each coefficient is represented as the difference
3371 * of two non-negative variables. The negative part always appears
3372 * immediately before the positive part.
3373 * Other than that, the variables have the following order
3374 *
3375 * - sum of (1 - e_i) over all edges
3376 * - sum of positive and negative parts of all c_n coefficients
3377 * (unconstrained when computing non-parametric schedules)
3378 * - sum of positive and negative parts of all c_x coefficients
3379 * - for each edge
3380 * - e_i
3381 * - for each node
3382 * - c_i_0
3383 * - positive and negative parts of c_i_n (if parametric)
3384 * - positive and negative parts of c_i_x
3385 *
3386 * The constraints are those from the (validity) edges plus three equalities
3387 * to express the sums and n_edge inequalities to express e_i <= 1.
3388 */
3389static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
3390{
3391 int i, j;
3392 int k;
3393 isl_space *dim;
3394 unsigned total;
3395 int n_eq, n_ineq;
3396 int n_edge;
3397
3398 n_edge = 0;
3399 for (i = 0; i < graph->n_edge; ++i)
3400 n_edge += graph->edge[i].map->n;
3401
3402 total = 3 + n_edge;
3403 for (i = 0; i < graph->n; ++i) {
3404 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
3405 node->start = total;
3406 total += 1 + 2 * (node->nparam + node->nvar);
3407 }
3408
3409 if (count_all_constraints(graph, &n_eq, &n_ineq) < 0)
3410 return -1;
3411
3412 dim = isl_space_set_alloc(ctx, 0, total);
3413 isl_basic_set_free(graph->lp);
3414 n_eq += 3;
3415 n_ineq += n_edge;
3416 graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
3417 graph->lp = isl_basic_set_set_rational(graph->lp);
3418
3419 k = isl_basic_set_alloc_equality(graph->lp);
3420 if (k < 0)
3421 return -1;
3422 isl_seq_clr(graph->lp->eq[k], 1 + total);
3423 isl_int_set_si(graph->lp->eq[k][0], -n_edge)isl_sioimath_set_si((graph->lp->eq[k][0]), -n_edge);
3424 isl_int_set_si(graph->lp->eq[k][1], 1)isl_sioimath_set_si((graph->lp->eq[k][1]), 1);
3425 for (i = 0; i < n_edge; ++i)
3426 isl_int_set_si(graph->lp->eq[k][4 + i], 1)isl_sioimath_set_si((graph->lp->eq[k][4 + i]), 1);
3427
3428 k = isl_basic_set_alloc_equality(graph->lp);
3429 if (k < 0)
3430 return -1;
3431 isl_seq_clr(graph->lp->eq[k], 1 + total);
3432 isl_int_set_si(graph->lp->eq[k][2], -1)isl_sioimath_set_si((graph->lp->eq[k][2]), -1);
3433 for (i = 0; i < graph->n; ++i) {
3434 int pos = 1 + graph->node[i].start + 1;
3435
3436 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
3437 isl_int_set_si(graph->lp->eq[k][pos + j], 1)isl_sioimath_set_si((graph->lp->eq[k][pos + j]), 1);
3438 }
3439
3440 k = isl_basic_set_alloc_equality(graph->lp);
3441 if (k < 0)
3442 return -1;
3443 isl_seq_clr(graph->lp->eq[k], 1 + total);
3444 isl_int_set_si(graph->lp->eq[k][3], -1)isl_sioimath_set_si((graph->lp->eq[k][3]), -1);
3445 for (i = 0; i < graph->n; ++i) {
3446 struct isl_sched_node *node = &graph->node[i];
3447 int pos = 1 + node->start + 1 + 2 * node->nparam;
3448
3449 for (j = 0; j < 2 * node->nvar; ++j)
3450 isl_int_set_si(graph->lp->eq[k][pos + j], 1)isl_sioimath_set_si((graph->lp->eq[k][pos + j]), 1);
3451 }
3452
3453 for (i = 0; i < n_edge; ++i) {
3454 k = isl_basic_set_alloc_inequality(graph->lp);
3455 if (k < 0)
3456 return -1;
3457 isl_seq_clr(graph->lp->ineq[k], 1 + total);
3458 isl_int_set_si(graph->lp->ineq[k][4 + i], -1)isl_sioimath_set_si((graph->lp->ineq[k][4 + i]), -1);
3459 isl_int_set_si(graph->lp->ineq[k][0], 1)isl_sioimath_set_si((graph->lp->ineq[k][0]), 1);
3460 }
3461
3462 if (add_all_constraints(graph) < 0)
3463 return -1;
3464
3465 return 0;
3466}
3467
3468static __isl_give isl_schedule_node *compute_component_schedule(
3469 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
3470 int wcc);
3471
3472/* Comparison function for sorting the statements based on
3473 * the corresponding value in "r".
3474 */
3475static int smaller_value(const void *a, const void *b, void *data)
3476{
3477 isl_vec *r = data;
3478 const int *i1 = a;
3479 const int *i2 = b;
3480
3481 return isl_int_cmp(r->el[*i1], r->el[*i2])isl_sioimath_cmp(*(r->el[*i1]), *(r->el[*i2]));
3482}
3483
3484/* If the schedule_split_scaled option is set and if the linear
3485 * parts of the scheduling rows for all nodes in the graphs have
3486 * a non-trivial common divisor, then split off the remainder of the
3487 * constant term modulo this common divisor from the linear part.
3488 * Otherwise, insert a band node directly and continue with
3489 * the construction of the schedule.
3490 *
3491 * If a non-trivial common divisor is found, then
3492 * the linear part is reduced and the remainder is enforced
3493 * by a sequence node with the children placed in the order
3494 * of this remainder.
3495 * In particular, we assign an scc index based on the remainder and
3496 * then rely on compute_component_schedule to insert the sequence and
3497 * to continue the schedule construction on each part.
3498 */
3499static __isl_give isl_schedule_node *split_scaled(
3500 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3501{
3502 int i;
3503 int row;
3504 int scc;
3505 isl_ctx *ctx;
3506 isl_int gcd, gcd_i;
3507 isl_vec *r;
3508 int *order;
3509
3510 if (!node)
3511 return NULL((void*)0);
3512
3513 ctx = isl_schedule_node_get_ctx(node);
3514 if (!ctx->opt->schedule_split_scaled)
3515 return compute_next_band(node, graph, 0);
3516 if (graph->n <= 1)
3517 return compute_next_band(node, graph, 0);
3518
3519 isl_int_init(gcd)isl_sioimath_init((gcd));
3520 isl_int_init(gcd_i)isl_sioimath_init((gcd_i));
3521
3522 isl_int_set_si(gcd, 0)isl_sioimath_set_si((gcd), 0);
3523
3524 row = isl_mat_rows(graph->node[0].sched) - 1;
3525
3526 for (i = 0; i < graph->n; ++i) {
3527 struct isl_sched_node *node = &graph->node[i];
3528 int cols = isl_mat_cols(node->sched);
3529
3530 isl_seq_gcd(node->sched->row[row] + 1, cols - 1, &gcd_i);
3531 isl_int_gcd(gcd, gcd, gcd_i)isl_sioimath_gcd((gcd), *(gcd), *(gcd_i));
3532 }
3533
3534 isl_int_clear(gcd_i)isl_sioimath_clear((gcd_i));
3535
3536 if (isl_int_cmp_si(gcd, 1)isl_sioimath_cmp_si(*(gcd), 1) <= 0) {
3537 isl_int_clear(gcd)isl_sioimath_clear((gcd));
3538 return compute_next_band(node, graph, 0);
3539 }
3540
3541 r = isl_vec_alloc(ctx, graph->n);
3542 order = isl_calloc_array(ctx, int, graph->n)((int *)isl_calloc_or_die(ctx, graph->n, sizeof(int)));
3543 if (!r || !order)
3544 goto error;
3545
3546 for (i = 0; i < graph->n; ++i) {
3547 struct isl_sched_node *node = &graph->node[i];
3548
3549 order[i] = i;
3550 isl_int_fdiv_r(r->el[i], node->sched->row[row][0], gcd)isl_sioimath_fdiv_r((r->el[i]), *(node->sched->row[row
][0]), *(gcd));
3551 isl_int_fdiv_q(node->sched->row[row][0],isl_sioimath_fdiv_q((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd))
3552 node->sched->row[row][0], gcd)isl_sioimath_fdiv_q((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd));
3553 isl_int_mul(node->sched->row[row][0],isl_sioimath_mul((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd))
3554 node->sched->row[row][0], gcd)isl_sioimath_mul((node->sched->row[row][0]), *(node->
sched->row[row][0]), *(gcd));
3555 node->sched = isl_mat_scale_down_row(node->sched, row, gcd);
3556 if (!node->sched)
3557 goto error;
3558 }
3559
3560 if (isl_sort(order, graph->n, sizeof(order[0]), &smaller_value, r) < 0)
3561 goto error;
3562
3563 scc = 0;
3564 for (i = 0; i < graph->n; ++i) {
3565 if (i > 0 && isl_int_ne(r->el[order[i - 1]], r->el[order[i]])(isl_sioimath_cmp(*(r->el[order[i - 1]]), *(r->el[order
[i]])) != 0))
3566 ++scc;
3567 graph->node[order[i]].scc = scc;
3568 }
3569 graph->scc = ++scc;
3570 graph->weak = 0;
3571
3572 isl_int_clear(gcd)isl_sioimath_clear((gcd));
3573 isl_vec_free(r);
3574 free(order);
3575
3576 if (update_edges(ctx, graph) < 0)
3577 return isl_schedule_node_free(node);
3578 node = insert_current_band(node, graph, 0);
3579 next_band(graph);
3580
3581 node = isl_schedule_node_child(node, 0);
3582 node = compute_component_schedule(node, graph, 0);
3583 node = isl_schedule_node_parent(node);
3584
3585 return node;
3586error:
3587 isl_vec_free(r);
3588 free(order);
3589 isl_int_clear(gcd)isl_sioimath_clear((gcd));
3590 return isl_schedule_node_free(node);
3591}
3592
3593/* Is the schedule row "sol" trivial on node "node"?
3594 * That is, is the solution zero on the dimensions orthogonal to
3595 * the previously found solutions?
3596 * Return 1 if the solution is trivial, 0 if it is not and -1 on error.
3597 *
3598 * Each coefficient is represented as the difference between
3599 * two non-negative values in "sol". "sol" has been computed
3600 * in terms of the original iterators (i.e., without use of cmap).
3601 * We construct the schedule row s and write it as a linear
3602 * combination of (linear combinations of) previously computed schedule rows.
3603 * s = Q c or c = U s.
3604 * If the final entries of c are all zero, then the solution is trivial.
3605 */
3606static int is_trivial(struct isl_sched_node *node, __isl_keep isl_vec *sol)
3607{
3608 int i;
3609 int pos;
3610 int trivial;
3611 isl_ctx *ctx;
3612 isl_vec *node_sol;
3613
3614 if (!sol)
3615 return -1;
3616 if (node->nvar == node->rank)
3617 return 0;
3618
3619 ctx = isl_vec_get_ctx(sol);
3620 node_sol = isl_vec_alloc(ctx, node->nvar);
3621 if (!node_sol)
3622 return -1;
3623
3624 pos = 1 + node->start + 1 + 2 * node->nparam;
3625
3626 for (i = 0; i < node->nvar; ++i)
3627 isl_int_sub(node_sol->el[i],isl_sioimath_sub((node_sol->el[i]), *(sol->el[pos + 2 *
i + 1]), *(sol->el[pos + 2 * i]))
3628 sol->el[pos + 2 * i + 1], sol->el[pos + 2 * i])isl_sioimath_sub((node_sol->el[i]), *(sol->el[pos + 2 *
i + 1]), *(sol->el[pos + 2 * i]));
3629
3630 node_sol = isl_mat_vec_product(isl_mat_copy(node->cinv), node_sol);
3631
3632 if (!node_sol)
3633 return -1;
3634
3635 trivial = isl_seq_first_non_zero(node_sol->el + node->rank,
3636 node->nvar - node->rank) == -1;
3637
3638 isl_vec_free(node_sol);
3639
3640 return trivial;
3641}
3642
3643/* Is the schedule row "sol" trivial on any node where it should
3644 * not be trivial?
3645 * "sol" has been computed in terms of the original iterators
3646 * (i.e., without use of cmap).
3647 * Return 1 if any solution is trivial, 0 if they are not and -1 on error.
3648 */
3649static int is_any_trivial(struct isl_sched_graph *graph,
3650 __isl_keep isl_vec *sol)
3651{
3652 int i;
3653
3654 for (i = 0; i < graph->n; ++i) {
3655 struct isl_sched_node *node = &graph->node[i];
3656 int trivial;
3657
3658 if (!needs_row(graph, node))
3659 continue;
3660 trivial = is_trivial(node, sol);
3661 if (trivial < 0 || trivial)
3662 return trivial;
3663 }
3664
3665 return 0;
3666}
3667
3668/* Construct a schedule row for each node such that as many dependences
3669 * as possible are carried and then continue with the next band.
3670 *
3671 * If the computed schedule row turns out to be trivial on one or
3672 * more nodes where it should not be trivial, then we throw it away
3673 * and try again on each component separately.
3674 *
3675 * If there is only one component, then we accept the schedule row anyway,
3676 * but we do not consider it as a complete row and therefore do not
3677 * increment graph->n_row. Note that the ranks of the nodes that
3678 * do get a non-trivial schedule part will get updated regardless and
3679 * graph->maxvar is computed based on these ranks. The test for
3680 * whether more schedule rows are required in compute_schedule_wcc
3681 * is therefore not affected.
3682 *
3683 * Insert a band corresponding to the schedule row at position "node"
3684 * of the schedule tree and continue with the construction of the schedule.
3685 * This insertion and the continued construction is performed by split_scaled
3686 * after optionally checking for non-trivial common divisors.
3687 */
3688static __isl_give isl_schedule_node *carry_dependences(
3689 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3690{
3691 int i;
3692 int n_edge;
3693 int trivial;
3694 isl_ctx *ctx;
3695 isl_vec *sol;
3696 isl_basic_setisl_basic_map *lp;
3697
3698 if (!node)
3699 return NULL((void*)0);
3700
3701 n_edge = 0;
3702 for (i = 0; i < graph->n_edge; ++i)
3703 n_edge += graph->edge[i].map->n;
3704
3705 ctx = isl_schedule_node_get_ctx(node);
3706 if (setup_carry_lp(ctx, graph) < 0)
3707 return isl_schedule_node_free(node);
3708
3709 lp = isl_basic_set_copy(graph->lp);
3710 sol = isl_tab_basic_set_non_neg_lexmin(lp);
3711 if (!sol)
3712 return isl_schedule_node_free(node);
3713
3714 if (sol->size == 0) {
3715 isl_vec_free(sol);
3716 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "error in schedule construction"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3718); return isl_schedule_node_free(node); } while (0)
3717 "error in schedule construction",do { isl_handle_error(ctx, isl_error_internal, "error in schedule construction"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3718); return isl_schedule_node_free(node); } while (0)
3718 return isl_schedule_node_free(node))do { isl_handle_error(ctx, isl_error_internal, "error in schedule construction"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3718); return isl_schedule_node_free(node); } while (0);
3719 }
3720
3721 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]));
3722 if (isl_int_cmp_si(sol->el[1], n_edge)isl_sioimath_cmp_si(*(sol->el[1]), n_edge) >= 0) {
3723 isl_vec_free(sol);
3724 isl_die(ctx, isl_error_unknown,do { isl_handle_error(ctx, isl_error_unknown, "unable to carry dependences"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3726); return isl_schedule_node_free(node); } while (0)
3725 "unable to carry dependences",do { isl_handle_error(ctx, isl_error_unknown, "unable to carry dependences"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3726); return isl_schedule_node_free(node); } while (0)
3726 return isl_schedule_node_free(node))do { isl_handle_error(ctx, isl_error_unknown, "unable to carry dependences"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3726); return isl_schedule_node_free(node); } while (0);
3727 }
3728
3729 trivial = is_any_trivial(graph, sol);
3730 if (trivial < 0) {
3731 sol = isl_vec_free(sol);
3732 } else if (trivial && graph->scc > 1) {
3733 isl_vec_free(sol);
3734 return compute_component_schedule(node, graph, 1);
3735 }
3736
3737 if (update_schedule(graph, sol, 0, 0) < 0)
3738 return isl_schedule_node_free(node);
3739 if (trivial)
3740 graph->n_row--;
3741
3742 return split_scaled(node, graph);
3743}
3744
3745/* Topologically sort statements mapped to the same schedule iteration
3746 * and add insert a sequence node in front of "node"
3747 * corresponding to this order.
3748 *
3749 * If it turns out to be impossible to sort the statements apart,
3750 * because different dependences impose different orderings
3751 * on the statements, then we extend the schedule such that
3752 * it carries at least one more dependence.
3753 */
3754static __isl_give isl_schedule_node *sort_statements(
3755 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
3756{
3757 isl_ctx *ctx;
3758 isl_union_set_list *filters;
3759
3760 if (!node)
3761 return NULL((void*)0);
3762
3763 ctx = isl_schedule_node_get_ctx(node);
3764 if (graph->n < 1)
3765 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "graph should have at least one node"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3767); return isl_schedule_node_free(node); } while (0)
3766 "graph should have at least one node",do { isl_handle_error(ctx, isl_error_internal, "graph should have at least one node"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3767); return isl_schedule_node_free(node); } while (0)
3767 return isl_schedule_node_free(node))do { isl_handle_error(ctx, isl_error_internal, "graph should have at least one node"
, "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_scheduler.c"
, 3767); return isl_schedule_node_free(node); } while (0);
3768
3769 if (graph->n == 1)
3770 return node;
3771
3772 if (update_edges(ctx, graph) < 0)
3773 return isl_schedule_node_free(node);
3774
3775 if (graph->n_edge == 0)
3776 return node;
3777
3778 if (detect_sccs(ctx, graph) < 0)
3779 return isl_schedule_node_free(node);
3780
3781 next_band(graph);
3782 if (graph->scc < graph->n)
3783 return carry_dependences(node, graph);
3784
3785 filters = extract_sccs(ctx, graph);
3786 node = isl_schedule_node_insert_sequence(node, filters);
3787
3788 return node;
3789}
3790
3791/* Are there any (non-empty) (conditional) validity edges in the graph?
3792 */
3793static int has_validity_edges(struct isl_sched_graph *graph)
3794{
3795 int i;
3796
3797 for (i = 0; i < graph->n_edge; ++i) {
3798 int empty;
3799
3800 empty = isl_map_plain_is_empty(graph->edge[i].map);
3801 if (empty < 0)
3802 return -1;
3803 if (empty)
3804 continue;
3805 if (graph->edge[i].validity ||
3806 graph->edge[i].conditional_validity)
3807 return 1;
3808 }
3809
3810 return 0;
3811}
3812
3813/* Should we apply a Feautrier step?
3814 * That is, did the user request the Feautrier algorithm and are
3815 * there any validity dependences (left)?
3816 */
3817static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
3818{
3819 if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER1)
3820 return 0;
3821
3822 return has_validity_edges(graph);
3823}
3824
3825/* Compute a schedule for a connected dependence graph using Feautrier's
3826 * multi-dimensional scheduling algorithm and return the updated schedule node.
3827 *
3828 * The original algorithm is described in [1].
3829 * The main idea is to minimize the number of scheduling dimensions, by
3830 * trying to satisfy as many dependences as possible per scheduling dimension.
3831 *
3832 * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
3833 * Problem, Part II: Multi-Dimensional Time.
3834 * In Intl. Journal of Parallel Programming, 1992.
3835 */
3836static __isl_give isl_schedule_node *compute_schedule_wcc_feautrier(
3837 isl_schedule_node *node, struct isl_sched_graph *graph)
3838{
3839 return carry_dependences(node, graph);
3840}
3841
3842/* Turn off the "local" bit on all (condition) edges.
3843 */
3844static void clear_local_edges(struct isl_sched_graph *graph)
3845{
3846 int i;
3847
3848 for (i = 0; i < graph->n_edge; ++i)
3849 if (graph->edge[i].condition)
3850 graph->edge[i].local = 0;
3851}
3852
3853/* Does "graph" have both condition and conditional validity edges?
3854 */
3855static int need_condition_check(struct isl_sched_graph *graph)
3856{
3857 int i;
3858 int any_condition = 0;
3859 int any_conditional_validity = 0;
3860
3861 for (i = 0; i < graph->n_edge; ++i) {
3862 if (graph->edge[i].condition)
3863 any_condition = 1;
3864 if (graph->edge[i].conditional_validity)
3865 any_conditional_validity = 1;
3866 }
3867
3868 return any_condition && any_conditional_validity;
3869}
3870
3871/* Does "graph" contain any coincidence edge?
3872 */
3873static int has_any_coincidence(struct isl_sched_graph *graph)
3874{
3875 int i;
3876
3877 for (i = 0; i < graph->n_edge; ++i)
3878 if (graph->edge[i].coincidence)
3879 return 1;
3880
3881 return 0;
3882}
3883
3884/* Extract the final schedule row as a map with the iteration domain
3885 * of "node" as domain.
3886 */
3887static __isl_give isl_map *final_row(struct isl_sched_node *node)
3888{
3889 isl_local_space *ls;
3890 isl_aff *aff;
3891 int row;
3892
3893 row = isl_mat_rows(node->sched) - 1;
3894 ls = isl_local_space_from_space(isl_space_copy(node->space));
3895 aff = extract_schedule_row(ls, node, row);
3896 return isl_map_from_aff(aff);
3897}
3898
3899/* Is the conditional validity dependence in the edge with index "edge_index"
3900 * violated by the latest (i.e., final) row of the schedule?
3901 * That is, is i scheduled after j
3902 * for any conditional validity dependence i -> j?
3903 */
3904static int is_violated(struct isl_sched_graph *graph, int edge_index)
3905{
3906 isl_map *src_sched, *dst_sched, *map;
3907 struct isl_sched_edge *edge = &graph->edge[edge_index];
3908 int empty;
3909
3910 src_sched = final_row(edge->src);
3911 dst_sched = final_row(edge->dst);
3912 map = isl_map_copy(edge->map);
3913 map = isl_map_apply_domain(map, src_sched);
3914 map = isl_map_apply_range(map, dst_sched);
3915 map = isl_map_order_gt(map, isl_dim_in, 0, isl_dim_out, 0);
3916 empty = isl_map_is_empty(map);
3917 isl_map_free(map);
3918
3919 if (empty < 0)
3920 return -1;
3921
3922 return !empty;
3923}
3924
3925/* Does "graph" have any satisfied condition edges that
3926 * are adjacent to the conditional validity constraint with
3927 * domain "conditional_source" and range "conditional_sink"?
3928 *
3929 * A satisfied condition is one that is not local.
3930 * If a condition was forced to be local already (i.e., marked as local)
3931 * then there is no need to check if it is in fact local.
3932 *
3933 * Additionally, mark all adjacent condition edges found as local.
3934 */
3935static int has_adjacent_true_conditions(struct isl_sched_graph *graph,
3936 __isl_keep isl_union_set *conditional_source,
3937 __isl_keep isl_union_set *conditional_sink)
3938{
3939 int i;
3940 int any = 0;
3941
3942 for (i = 0; i < graph->n_edge; ++i) {
3943 int adjacent, local;
3944 isl_union_map *condition;
3945
3946 if (!graph->edge[i].condition)
3947 continue;
3948 if (graph->edge[i].local)
3949 continue;
3950
3951 condition = graph->edge[i].tagged_condition;
3952 adjacent = domain_intersects(condition, conditional_sink);
3953 if (adjacent >= 0 && !adjacent)
3954 adjacent = range_intersects(condition,
3955 conditional_source);
3956 if (adjacent < 0)
3957 return -1;
3958 if (!adjacent)
3959 continue;
3960
3961 graph->edge[i].local = 1;
3962
3963 local = is_condition_false(&graph->edge[i]);
3964 if (local < 0)
3965 return -1;
3966 if (!local)
3967 any = 1;
3968 }
3969
3970 return any;
3971}
3972
3973/* Are there any violated conditional validity dependences with
3974 * adjacent condition dependences that are not local with respect
3975 * to the current schedule?
3976 * That is, is the conditional validity constraint violated?
3977 *
3978 * Additionally, mark all those adjacent condition dependences as local.
3979 * We also mark those adjacent condition dependences that were not marked
3980 * as local before, but just happened to be local already. This ensures
3981 * that they remain local if the schedule is recomputed.
3982 *
3983 * We first collect domain and range of all violated conditional validity
3984 * dependences and then check if there are any adjacent non-local
3985 * condition dependences.
3986 */
3987static int has_violated_conditional_constraint(isl_ctx *ctx,
3988 struct isl_sched_graph *graph)
3989{
3990 int i;
3991 int any = 0;
3992 isl_union_set *source, *sink;
3993
3994 source = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3995 sink = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
3996 for (i = 0; i < graph->n_edge; ++i) {
3997 isl_union_set *uset;
3998 isl_union_map *umap;
3999 int violated;
4000
4001 if (!graph->edge[i].conditional_validity)
4002 continue;
4003
4004 violated = is_violated(graph, i);
4005 if (violated < 0)
4006 goto error;
4007 if (!violated)
4008 continue;
4009
4010 any = 1;
4011
4012 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
4013 uset = isl_union_map_domain(umap);
4014 source = isl_union_set_union(source, uset);
4015 source = isl_union_set_coalesce(source);
4016
4017 umap = isl_union_map_copy(graph->edge[i].tagged_validity);
4018 uset = isl_union_map_range(umap);
4019 sink = isl_union_set_union(sink, uset);
4020 sink = isl_union_set_coalesce(sink);
4021 }
4022
4023 if (any)
4024 any = has_adjacent_true_conditions(graph, source, sink);
4025
4026 isl_union_set_free(source);
4027 isl_union_set_free(sink);
4028 return any;
4029error:
4030 isl_union_set_free(source);
4031 isl_union_set_free(sink);
4032 return -1;
4033}
4034
4035/* Compute a schedule for a connected dependence graph and return
4036 * the updated schedule node.
4037 *
4038 * We try to find a sequence of as many schedule rows as possible that result
4039 * in non-negative dependence distances (independent of the previous rows
4040 * in the sequence, i.e., such that the sequence is tilable), with as
4041 * many of the initial rows as possible satisfying the coincidence constraints.
4042 * If we can't find any more rows we either
4043 * - split between SCCs and start over (assuming we found an interesting
4044 * pair of SCCs between which to split)
4045 * - continue with the next band (assuming the current band has at least
4046 * one row)
4047 * - try to carry as many dependences as possible and continue with the next
4048 * band
4049 * In each case, we first insert a band node in the schedule tree
4050 * if any rows have been computed.
4051 *
4052 * If Feautrier's algorithm is selected, we first recursively try to satisfy
4053 * as many validity dependences as possible. When all validity dependences
4054 * are satisfied we extend the schedule to a full-dimensional schedule.
4055 *
4056 * If we manage to complete the schedule, we insert a band node
4057 * (if any schedule rows were computed) and we finish off by topologically
4058 * sorting the statements based on the remaining dependences.
4059 *
4060 * If ctx->opt->schedule_outer_coincidence is set, then we force the
4061 * outermost dimension to satisfy the coincidence constraints. If this
4062 * turns out to be impossible, we fall back on the general scheme above
4063 * and try to carry as many dependences as possible.
4064 *
4065 * If "graph" contains both condition and conditional validity dependences,
4066 * then we need to check that that the conditional schedule constraint
4067 * is satisfied, i.e., there are no violated conditional validity dependences
4068 * that are adjacent to any non-local condition dependences.
4069 * If there are, then we mark all those adjacent condition dependences
4070 * as local and recompute the current band. Those dependences that
4071 * are marked local will then be forced to be local.
4072 * The initial computation is performed with no dependences marked as local.
4073 * If we are lucky, then there will be no violated conditional validity
4074 * dependences adjacent to any non-local condition dependences.
4075 * Otherwise, we mark some additional condition dependences as local and
4076 * recompute. We continue this process until there are no violations left or
4077 * until we are no longer able to compute a schedule.
4078 * Since there are only a finite number of dependences,
4079 * there will only be a finite number of iterations.
4080 */
4081static __isl_give isl_schedule_node *compute_schedule_wcc(
4082 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph)
4083{
4084 int has_coincidence;
4085 int use_coincidence;
4086 int force_coincidence = 0;
4087 int check_conditional;
4088 int insert;
4089 isl_ctx *ctx;
4090
4091 if (!node)
4092 return NULL((void*)0);
4093
4094 ctx = isl_schedule_node_get_ctx(node);
4095 if (detect_sccs(ctx, graph) < 0)
4096 return isl_schedule_node_free(node);
4097 if (sort_sccs(graph) < 0)
4098 return isl_schedule_node_free(node);
4099
4100 if (compute_maxvar(graph) < 0)
4101 return isl_schedule_node_free(node);
4102
4103 if (need_feautrier_step(ctx, graph))
4104 return compute_schedule_wcc_feautrier(node, graph);
4105
4106 clear_local_edges(graph);
4107 check_conditional = need_condition_check(graph);
4108 has_coincidence = has_any_coincidence(graph);
4109
4110 if (ctx->opt->schedule_outer_coincidence)
4111 force_coincidence = 1;
4112
4113 use_coincidence = has_coincidence;
4114 while (graph->n_row < graph->maxvar) {
4115 isl_vec *sol;
4116 int violated;
4117 int coincident;
4118
4119 graph->src_scc = -1;
4120 graph->dst_scc = -1;
4121
4122 if (setup_lp(ctx, graph, use_coincidence) < 0)
4123 return isl_schedule_node_free(node);
4124 sol = solve_lp(graph);
4125 if (!sol)
4126 return isl_schedule_node_free(node);
4127 if (sol->size == 0) {
4128 int empty = graph->n_total_row == graph->band_start;
4129
4130 isl_vec_free(sol);
4131 if (use_coincidence && (!force_coincidence || !empty)) {
4132 use_coincidence = 0;
4133 continue;
4134 }
4135 if (!ctx->opt->schedule_maximize_band_depth && !empty)
4136 return compute_next_band(node, graph, 1);
4137 if (graph->src_scc >= 0)
4138 return compute_split_schedule(node, graph);
4139 if (!empty)
4140 return compute_next_band(node, graph, 1);
4141 return carry_dependences(node, graph);
4142 }
4143 coincident = !has_coincidence || use_coincidence;
4144 if (update_schedule(graph, sol, 1, coincident) < 0)
4145 return isl_schedule_node_free(node);
4146
4147 if (!check_conditional)
4148 continue;
4149 violated = has_violated_conditional_constraint(ctx, graph);
4150 if (violated < 0)
4151 return isl_schedule_node_free(node);
4152 if (!violated)
4153 continue;
4154 if (reset_band(graph) < 0)
4155 return isl_schedule_node_free(node);
4156 use_coincidence = has_coincidence;
4157 }
4158
4159 insert = graph->n_total_row > graph->band_start;
4160 if (insert) {
4161 node = insert_current_band(node, graph, 1);
4162 node = isl_schedule_node_child(node, 0);
4163 }
4164 node = sort_statements(node, graph);
4165 if (insert)
4166 node = isl_schedule_node_parent(node);
4167
4168 return node;
4169}
4170
4171/* Compute a schedule for each group of nodes identified by node->scc
4172 * separately and then combine them in a sequence node (or as set node
4173 * if graph->weak is set) inserted at position "node" of the schedule tree.
4174 * Return the updated schedule node.
4175 *
4176 * If "wcc" is set then each of the groups belongs to a single
4177 * weakly connected component in the dependence graph so that
4178 * there is no need for compute_sub_schedule to look for weakly
4179 * connected components.
4180 */
4181static __isl_give isl_schedule_node *compute_component_schedule(
4182 __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,
4183 int wcc)
4184{
4185 int component, i;
4186 int n, n_edge;
4187 isl_ctx *ctx;
4188 isl_union_set_list *filters;
4189
4190 if (!node)
4191 return NULL((void*)0);
4192 ctx = isl_schedule_node_get_ctx(node);
4193
4194 filters = extract_sccs(ctx, graph);
4195 if (graph->weak)
4196 node = isl_schedule_node_insert_set(node, filters);
4197 else
4198 node = isl_schedule_node_insert_sequence(node, filters);
4199
4200 for (component = 0; component < graph->scc; ++component) {
4201 n = 0;
4202 for (i = 0; i < graph->n; ++i)
4203 if (graph->node[i].scc == component)
4204 n++;
4205 n_edge = 0;
4206 for (i = 0; i < graph->n_edge; ++i)
4207 if (graph->edge[i].src->scc == component &&
4208 graph->edge[i].dst->scc == component)
4209 n_edge++;
4210
4211 node = isl_schedule_node_child(node, component);
4212 node = isl_schedule_node_child(node, 0);
4213 node = compute_sub_schedule(node, ctx, graph, n, n_edge,
4214 &node_scc_exactly,
4215 &edge_scc_exactly, component, wcc);
4216 node = isl_schedule_node_parent(node);
4217 node = isl_schedule_node_parent(node);
4218 }
4219
4220 return node;
4221}
4222
4223/* Compute a schedule for the given dependence graph and insert it at "node".
4224 * Return the updated schedule node.
4225 *
4226 * We first check if the graph is connected (through validity and conditional
4227 * validity dependences) and, if not, compute a schedule
4228 * for each component separately.
4229 * If the schedule_serialize_sccs option is set, then we check for strongly
4230 * connected components instead and compute a separate schedule for
4231 * each such strongly connected component.
4232 */
4233static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
4234 struct isl_sched_graph *graph)
4235{
4236 isl_ctx *ctx;
4237
4238 if (!node)
4239 return NULL((void*)0);
4240
4241 ctx = isl_schedule_node_get_ctx(node);
4242 if (isl_options_get_schedule_serialize_sccs(ctx)) {
4243 if (detect_sccs(ctx, graph) < 0)
4244 return isl_schedule_node_free(node);
4245 } else {
4246 if (detect_wccs(ctx, graph) < 0)
4247 return isl_schedule_node_free(node);
4248 }
4249
4250 if (graph->scc > 1)
4251 return compute_component_schedule(node, graph, 1);
4252
4253 return compute_schedule_wcc(node, graph);
4254}
4255
4256/* Compute a schedule on sc->domain that respects the given schedule
4257 * constraints.
4258 *
4259 * In particular, the schedule respects all the validity dependences.
4260 * If the default isl scheduling algorithm is used, it tries to minimize
4261 * the dependence distances over the proximity dependences.
4262 * If Feautrier's scheduling algorithm is used, the proximity dependence
4263 * distances are only minimized during the extension to a full-dimensional
4264 * schedule.
4265 *
4266 * If there are any condition and conditional validity dependences,
4267 * then the conditional validity dependences may be violated inside
4268 * a tilable band, provided they have no adjacent non-local
4269 * condition dependences.
4270 *
4271 * The context is included in the domain before the nodes of
4272 * the graphs are extracted in order to be able to exploit
4273 * any possible additional equalities.
4274 * However, the returned schedule contains the original domain
4275 * (before this intersection).
4276 */
4277__isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
4278 __isl_take isl_schedule_constraints *sc)
4279{
4280 isl_ctx *ctx = isl_schedule_constraints_get_ctx(sc);
4281 struct isl_sched_graph graph = { 0 };
4282 isl_schedule *sched;
4283 isl_schedule_node *node;
4284 isl_union_set *domain;
4285 struct isl_extract_edge_data data;
4286 enum isl_edge_type i;
4287 int r;
4288
4289 sc = isl_schedule_constraints_align_params(sc);
4290 if (!sc)
4291 return NULL((void*)0);
4292
4293 graph.n = isl_union_set_n_set(sc->domain);
4294 if (graph.n == 0) {
4295 isl_union_set *domain = isl_union_set_copy(sc->domain);
4296 sched = isl_schedule_from_domain(domain);
4297 goto done;
4298 }
4299 if (graph_alloc(ctx, &graph, graph.n,
4300 isl_schedule_constraints_n_map(sc)) < 0)
4301 goto error;
4302 if (compute_max_row(&graph, sc) < 0)
4303 goto error;
4304 graph.root = 1;
4305 graph.n = 0;
4306 domain = isl_union_set_copy(sc->domain);
4307 domain = isl_union_set_intersect_params(domain,
4308 isl_set_copy(sc->context));
4309 r = isl_union_set_foreach_set(domain, &extract_node, &graph);
4310 isl_union_set_free(domain);
4311 if (r < 0)
4312 goto error;
4313 if (graph_init_table(ctx, &graph) < 0)
4314 goto error;
4315 for (i = isl_edge_first; i <= isl_edge_last; ++i)
4316 graph.max_edge[i] = isl_union_map_n_map(sc->constraint[i]);
4317 if (graph_init_edge_tables(ctx, &graph) < 0)
4318 goto error;
4319 graph.n_edge = 0;
4320 data.graph = &graph;
4321 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
4322 data.type = i;
4323 if (isl_union_map_foreach_map(sc->constraint[i],
4324 &extract_edge, &data) < 0)
4325 goto error;
4326 }
4327
4328 node = isl_schedule_node_from_domain(isl_union_set_copy(sc->domain));
4329 node = isl_schedule_node_child(node, 0);
4330 if (graph.n > 0)
4331 node = compute_schedule(node, &graph);
4332 sched = isl_schedule_node_get_schedule(node);
4333 isl_schedule_node_free(node);
4334
4335done:
4336 graph_free(ctx, &graph);
4337 isl_schedule_constraints_free(sc);
4338
4339 return sched;
4340error:
4341 graph_free(ctx, &graph);
4342 isl_schedule_constraints_free(sc);
4343 return NULL((void*)0);
4344}
4345
4346/* Compute a schedule for the given union of domains that respects
4347 * all the validity dependences and minimizes
4348 * the dependence distances over the proximity dependences.
4349 *
4350 * This function is kept for backward compatibility.
4351 */
4352__isl_give isl_schedule *isl_union_set_compute_schedule(
4353 __isl_take isl_union_set *domain,
4354 __isl_take isl_union_map *validity,
4355 __isl_take isl_union_map *proximity)
4356{
4357 isl_schedule_constraints *sc;
4358
4359 sc = isl_schedule_constraints_on_domain(domain);
4360 sc = isl_schedule_constraints_set_validity(sc, validity);
4361 sc = isl_schedule_constraints_set_proximity(sc, proximity);
4362
4363 return isl_schedule_constraints_compute_schedule(sc);
4364}