isl_schedule.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_ctx_private.h>
  12 #include <isl_map_private.h>
  13 #include <isl_space_private.h>
  14 #include <isl/hash.h>
  15 #include <isl/constraint.h>
  16 #include <isl/schedule.h>
  17 #include <isl_mat_private.h>
  18 #include <isl/set.h>
  19 #include <isl/seq.h>
  20 #include <isl_tab.h>
  21 #include <isl_dim_map.h>
  22 #include <isl_hmap_map_basic_set.h>
  23 #include <isl_qsort.h>
  24 #include <isl_schedule_private.h>
  25 #include <isl_band_private.h>
  26 #include <isl_list_private.h>
  27 #include <isl_options_private.h>
  28
  29 /*
  30  * The scheduling algorithm implemented in this file was inspired by
  31  * Bondhugula et al., "Automatic Transformations for Communication-Minimized
  32  * Parallelization and Locality Optimization in the Polyhedral Model".
  33  */
  34
  35
  36 /* Internal information about a node that is used during the construction
  37  * of a schedule.
  38  * dim represents the space in which the domain lives
  39  * sched is a matrix representation of the schedule being constructed
  40  *      for this node
  41  * sched_map is an isl_map representation of the same (partial) schedule
  42  *      sched_map may be NULL
  43  * rank is the number of linearly independent rows in the linear part
  44  *      of sched
  45  * the columns of cmap represent a change of basis for the schedule
  46  *      coefficients; the first rank columns span the linear part of
  47  *      the schedule rows
  48  * start is the first variable in the LP problem in the sequences that
  49  *      represents the schedule coefficients of this node
  50  * nvar is the dimension of the domain
  51  * nparam is the number of parameters or 0 if we are not constructing
  52  *      a parametric schedule
  53  *
  54  * scc is the index of SCC (or WCC) this node belongs to
  55  *
  56  * band contains the band index for each of the rows of the schedule.
  57  * band_id is used to differentiate between separate bands at the same
  58  * level within the same parent band, i.e., bands that are separated
  59  * by the parent band or bands that are independent of each other.
  60  * zero contains a boolean for each of the rows of the schedule,
  61  * indicating whether the corresponding scheduling dimension results
  62  * in zero dependence distances within its band and with respect
  63  * to the proximity edges.
  64  *
  65  * index, min_index and on_stack are used during the SCC detection
  66  * index represents the order in which nodes are visited.
  67  * min_index is the index of the root of a (sub)component.
  68  * on_stack indicates whether the node is currently on the stack.
  69  */
  70 struct isl_sched_node {
  71         isl_space *dim;
  72         isl_mat *sched;
  73         isl_map *sched_map;
  74         int      rank;
  75         isl_mat *cmap;
  76         int      start;
  77         int      nvar;
  78         int      nparam;
  79
  80         int      scc;
  81
  82         int     *band;
  83         int     *band_id;
  84         int     *zero;
  85
  86         /* scc detection */
  87         int      index;
  88         int      min_index;
  89         int      on_stack;
  90 };
  91
  92 static int node_has_dim(const void *entry, const void *val)
  93 {
  94         struct isl_sched_node *node = (struct isl_sched_node *)entry;
  95         isl_space *dim = (isl_space *)val;
  96
  97         return isl_space_is_equal(node->dim, dim);
  98 }
  99
 100 /* An edge in the dependence graph.  An edge may be used to
 101  * ensure validity of the generated schedule, to minimize the dependence
 102  * distance or both
 103  *
 104  * map is the dependence relation
 105  * src is the source node
 106  * dst is the sink node
 107  * validity is set if the edge is used to ensure correctness
 108  * proximity is set if the edge is used to minimize dependence distances
 109  *
 110  * For validity edges, start and end mark the sequence of inequality
 111  * constraints in the LP problem that encode the validity constraint
 112  * corresponding to this edge.
 113  */
 114 struct isl_sched_edge {
 115         isl_map *map;
 116
 117         struct isl_sched_node *src;
 118         struct isl_sched_node *dst;
 119
 120         int validity;
 121         int proximity;
 122
 123         int start;
 124         int end;
 125 };
 126
 127 /* Internal information about the dependence graph used during
 128  * the construction of the schedule.
 129  *
 130  * intra_hmap is a cache, mapping dependence relations to their dual,
 131  *      for dependences from a node to itself
 132  * inter_hmap is a cache, mapping dependence relations to their dual,
 133  *      for dependences between distinct nodes
 134  *
 135  * n is the number of nodes
 136  * node is the list of nodes
 137  * maxvar is the maximal number of variables over all nodes
 138  * n_row is the current (maximal) number of linearly independent
 139  *      rows in the node schedules
 140  * n_total_row is the current number of rows in the node schedules
 141  * n_band is the current number of completed bands
 142  * band_start is the starting row in the node schedules of the current band
 143  * root is set if this graph is the original dependence graph,
 144  *      without any splitting
 145  *
 146  * sorted contains a list of node indices sorted according to the
 147  *      SCC to which a node belongs
 148  *
 149  * n_edge is the number of edges
 150  * edge is the list of edges
 151  * edge_table contains pointers into the edge array, hashed on the source
 152  *      and sink spaces; the table only contains edges that represent
 153  *      validity constraints (and that may or may not also represent proximity
 154  *      constraints)
 155  *
 156  * node_table contains pointers into the node array, hashed on the space
 157  *
 158  * region contains a list of variable sequences that should be non-trivial
 159  *
 160  * lp contains the (I)LP problem used to obtain new schedule rows
 161  *
 162  * src_scc and dst_scc are the source and sink SCCs of an edge with
 163  *      conflicting constraints
 164  *
 165  * scc, sp, index and stack are used during the detection of SCCs
 166  * scc is the number of the next SCC
 167  * stack contains the nodes on the path from the root to the current node
 168  * sp is the stack pointer
 169  * index is the index of the last node visited
 170  */
 171 struct isl_sched_graph {
 172         isl_hmap_map_basic_set *intra_hmap;
 173         isl_hmap_map_basic_set *inter_hmap;
 174
 175         struct isl_sched_node *node;
 176         int n;
 177         int maxvar;
 178         int n_row;
 179
 180         int *sorted;
 181
 182         int n_band;
 183         int n_total_row;
 184         int band_start;
 185
 186         int root;
 187
 188         struct isl_sched_edge *edge;
 189         int n_edge;
 190         struct isl_hash_table *edge_table;
 191
 192         struct isl_hash_table *node_table;
 193         struct isl_region *region;
 194
 195         isl_basic_set *lp;
 196
 197         int src_scc;
 198         int dst_scc;
 199
 200         /* scc detection */
 201         int scc;
 202         int sp;
 203         int index;
 204         int *stack;
 205 };
 206
 207 /* Initialize node_table based on the list of nodes.
 208  */
 209 static int graph_init_table(isl_ctx *ctx, struct isl_sched_graph *graph)
 210 {
 211         int i;
 212
 213         graph->node_table = isl_hash_table_alloc(ctx, graph->n);
 214         if (!graph->node_table)
 215                 return -1;
 216
 217         for (i = 0; i < graph->n; ++i) {
 218                 struct isl_hash_table_entry *entry;
 219                 uint32_t hash;
 220
 221                 hash = isl_space_get_hash(graph->node[i].dim);
 222                 entry = isl_hash_table_find(ctx, graph->node_table, hash,
 223                                             &node_has_dim,
 224                                             graph->node[i].dim, 1);
 225                 if (!entry)
 226                         return -1;
 227                 entry->data = &graph->node[i];
 228         }
 229
 230         return 0;
 231 }
 232
 233 /* Return a pointer to the node that lives within the given space,
 234  * or NULL if there is no such node.
 235  */
 236 static struct isl_sched_node *graph_find_node(isl_ctx *ctx,
 237         struct isl_sched_graph *graph, __isl_keep isl_space *dim)
 238 {
 239         struct isl_hash_table_entry *entry;
 240         uint32_t hash;
 241
 242         hash = isl_space_get_hash(dim);
 243         entry = isl_hash_table_find(ctx, graph->node_table, hash,
 244                                     &node_has_dim, dim, 0);
 245
 246         return entry ? entry->data : NULL;
 247 }
 248
 249 static int edge_has_src_and_dst(const void *entry, const void *val)
 250 {
 251         const struct isl_sched_edge *edge = entry;
 252         const struct isl_sched_edge *temp = val;
 253
 254         return edge->src == temp->src && edge->dst == temp->dst;
 255 }
 256
 257 /* Initialize edge_table based on the list of edges.
 258  * Only edges with validity set are added to the table.
 259  */
 260 static int graph_init_edge_table(isl_ctx *ctx, struct isl_sched_graph *graph)
 261 {
 262         int i;
 263
 264         graph->edge_table = isl_hash_table_alloc(ctx, graph->n_edge);
 265         if (!graph->edge_table)
 266                 return -1;
 267
 268         for (i = 0; i < graph->n_edge; ++i) {
 269                 struct isl_hash_table_entry *entry;
 270                 uint32_t hash;
 271
 272                 if (!graph->edge[i].validity)
 273                         continue;
 274
 275                 hash = isl_hash_init();
 276                 hash = isl_hash_builtin(hash, graph->edge[i].src);
 277                 hash = isl_hash_builtin(hash, graph->edge[i].dst);
 278                 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
 279                                             &edge_has_src_and_dst,
 280                                             &graph->edge[i], 1);
 281                 if (!entry)
 282                         return -1;
 283                 entry->data = &graph->edge[i];
 284         }
 285
 286         return 0;
 287 }
 288
 289 /* Check whether the dependence graph has a (validity) edge
 290  * between the given two nodes.
 291  */
 292 static int graph_has_edge(struct isl_sched_graph *graph,
 293         struct isl_sched_node *src, struct isl_sched_node *dst)
 294 {
 295         isl_ctx *ctx = isl_space_get_ctx(src->dim);
 296         struct isl_hash_table_entry *entry;
 297         uint32_t hash;
 298         struct isl_sched_edge temp = { .src = src, .dst = dst };
 299         struct isl_sched_edge *edge;
 300         int empty;
 301
 302         hash = isl_hash_init();
 303         hash = isl_hash_builtin(hash, temp.src);
 304         hash = isl_hash_builtin(hash, temp.dst);
 305         entry = isl_hash_table_find(ctx, graph->edge_table, hash,
 306                                     &edge_has_src_and_dst, &temp, 0);
 307         if (!entry)
 308                 return 0;
 309
 310         edge = entry->data;
 311         empty = isl_map_plain_is_empty(edge->map);
 312         if (empty < 0)
 313                 return -1;
 314
 315         return !empty;
 316 }
 317
 318 static int graph_alloc(isl_ctx *ctx, struct isl_sched_graph *graph,
 319         int n_node, int n_edge)
 320 {
 321         int i;
 322
 323         graph->n = n_node;
 324         graph->n_edge = n_edge;
 325         graph->node = isl_calloc_array(ctx, struct isl_sched_node, graph->n);
 326         graph->sorted = isl_calloc_array(ctx, int, graph->n);
 327         graph->region = isl_alloc_array(ctx, struct isl_region, graph->n);
 328         graph->stack = isl_alloc_array(ctx, int, graph->n);
 329         graph->edge = isl_calloc_array(ctx,
 330                                         struct isl_sched_edge, graph->n_edge);
 331
 332         graph->intra_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
 333         graph->inter_hmap = isl_hmap_map_basic_set_alloc(ctx, 2 * n_edge);
 334
 335         if (!graph->node || !graph->region || !graph->stack || !graph->edge ||
 336             !graph->sorted)
 337                 return -1;
 338
 339         for(i = 0; i < graph->n; ++i)
 340                 graph->sorted[i] = i;
 341
 342         return 0;
 343 }
 344
 345 static void graph_free(isl_ctx *ctx, struct isl_sched_graph *graph)
 346 {
 347         int i;
 348
 349         isl_hmap_map_basic_set_free(ctx, graph->intra_hmap);
 350         isl_hmap_map_basic_set_free(ctx, graph->inter_hmap);
 351
 352         for (i = 0; i < graph->n; ++i) {
 353                 isl_space_free(graph->node[i].dim);
 354                 isl_mat_free(graph->node[i].sched);
 355                 isl_map_free(graph->node[i].sched_map);
 356                 isl_mat_free(graph->node[i].cmap);
 357                 if (graph->root) {
 358                         free(graph->node[i].band);
 359                         free(graph->node[i].band_id);
 360                         free(graph->node[i].zero);
 361                 }
 362         }
 363         free(graph->node);
 364         free(graph->sorted);
 365         for (i = 0; i < graph->n_edge; ++i)
 366                 isl_map_free(graph->edge[i].map);
 367         free(graph->edge);
 368         free(graph->region);
 369         free(graph->stack);
 370         isl_hash_table_free(ctx, graph->edge_table);
 371         isl_hash_table_free(ctx, graph->node_table);
 372         isl_basic_set_free(graph->lp);
 373 }
 374
 375 /* Add a new node to the graph representing the given set.
 376  */
 377 static int extract_node(__isl_take isl_set *set, void *user)
 378 {
 379         int nvar, nparam;
 380         isl_ctx *ctx;
 381         isl_space *dim;
 382         isl_mat *sched;
 383         struct isl_sched_graph *graph = user;
 384         int *band, *band_id, *zero;
 385
 386         ctx = isl_set_get_ctx(set);
 387         dim = isl_set_get_space(set);
 388         isl_set_free(set);
 389         nvar = isl_space_dim(dim, isl_dim_set);
 390         nparam = isl_space_dim(dim, isl_dim_param);
 391         if (!ctx->opt->schedule_parametric)
 392                 nparam = 0;
 393         sched = isl_mat_alloc(ctx, 0, 1 + nparam + nvar);
 394         graph->node[graph->n].dim = dim;
 395         graph->node[graph->n].nvar = nvar;
 396         graph->node[graph->n].nparam = nparam;
 397         graph->node[graph->n].sched = sched;
 398         graph->node[graph->n].sched_map = NULL;
 399         band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
 400         graph->node[graph->n].band = band;
 401         band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
 402         graph->node[graph->n].band_id = band_id;
 403         zero = isl_calloc_array(ctx, int, graph->n_edge + nvar);
 404         graph->node[graph->n].zero = zero;
 405         graph->n++;
 406
 407         if (!sched || !band || !band_id || !zero)
 408                 return -1;
 409
 410         return 0;
 411 }
 412
 413 /* Add a new edge to the graph based on the given map.
 414  * Edges are first extracted from the validity dependences,
 415  * from which the edge_table is constructed.
 416  * Afterwards, the proximity dependences are added.  If a proximity
 417  * dependence relation happens to be identical to one of the
 418  * validity dependence relations added before, then we don't create
 419  * a new edge, but instead mark the original edge as also representing
 420  * a proximity dependence.
 421  */
 422 static int extract_edge(__isl_take isl_map *map, void *user)
 423 {
 424         isl_ctx *ctx = isl_map_get_ctx(map);
 425         struct isl_sched_graph *graph = user;
 426         struct isl_sched_node *src, *dst;
 427         isl_space *dim;
 428
 429         dim = isl_space_domain(isl_map_get_space(map));
 430         src = graph_find_node(ctx, graph, dim);
 431         isl_space_free(dim);
 432         dim = isl_space_range(isl_map_get_space(map));
 433         dst = graph_find_node(ctx, graph, dim);
 434         isl_space_free(dim);
 435
 436         if (!src || !dst) {
 437                 isl_map_free(map);
 438                 return 0;
 439         }
 440
 441         graph->edge[graph->n_edge].src = src;
 442         graph->edge[graph->n_edge].dst = dst;
 443         graph->edge[graph->n_edge].map = map;
 444         graph->edge[graph->n_edge].validity = !graph->edge_table;
 445         graph->edge[graph->n_edge].proximity = !!graph->edge_table;
 446         graph->n_edge++;
 447
 448         if (graph->edge_table) {
 449                 uint32_t hash;
 450                 struct isl_hash_table_entry *entry;
 451                 struct isl_sched_edge *edge;
 452                 int is_equal;
 453
 454                 hash = isl_hash_init();
 455                 hash = isl_hash_builtin(hash, src);
 456                 hash = isl_hash_builtin(hash, dst);
 457                 entry = isl_hash_table_find(ctx, graph->edge_table, hash,
 458                                             &edge_has_src_and_dst,
 459                                             &graph->edge[graph->n_edge - 1], 0);
 460                 if (!entry)
 461                         return 0;
 462                 edge = entry->data;
 463                 is_equal = isl_map_plain_is_equal(map, edge->map);
 464                 if (is_equal < 0)
 465                         return -1;
 466                 if (!is_equal)
 467                         return 0;
 468
 469                 graph->n_edge--;
 470                 edge->proximity = 1;
 471                 isl_map_free(map);
 472         }
 473
 474         return 0;
 475 }
 476
 477 /* Check whether there is a validity dependence from src to dst,
 478  * forcing dst to follow src.
 479  */
 480 static int node_follows(struct isl_sched_graph *graph,
 481         struct isl_sched_node *dst, struct isl_sched_node *src)
 482 {
 483         return graph_has_edge(graph, src, dst);
 484 }
 485
 486 /* Perform Tarjan's algorithm for computing the strongly connected components
 487  * in the dependence graph (only validity edges).
 488  * If directed is not set, we consider the graph to be undirected and
 489  * we effectively compute the (weakly) connected components.
 490  */
 491 static int detect_sccs_tarjan(struct isl_sched_graph *g, int i, int directed)
 492 {
 493         int j;
 494
 495         g->node[i].index = g->index;
 496         g->node[i].min_index = g->index;
 497         g->node[i].on_stack = 1;
 498         g->index++;
 499         g->stack[g->sp++] = i;
 500
 501         for (j = g->n - 1; j >= 0; --j) {
 502                 int f;
 503
 504                 if (j == i)
 505                         continue;
 506                 if (g->node[j].index >= 0 &&
 507                         (!g->node[j].on_stack ||
 508                          g->node[j].index > g->node[i].min_index))
 509                         continue;
 510
 511                 f = node_follows(g, &g->node[i], &g->node[j]);
 512                 if (f < 0)
 513                         return -1;
 514                 if (!f && !directed) {
 515                         f = node_follows(g, &g->node[j], &g->node[i]);
 516                         if (f < 0)
 517                                 return -1;
 518                 }
 519                 if (!f)
 520                         continue;
 521                 if (g->node[j].index < 0) {
 522                         detect_sccs_tarjan(g, j, directed);
 523                         if (g->node[j].min_index < g->node[i].min_index)
 524                                 g->node[i].min_index = g->node[j].min_index;
 525                 } else if (g->node[j].index < g->node[i].min_index)
 526                         g->node[i].min_index = g->node[j].index;
 527         }
 528
 529         if (g->node[i].index != g->node[i].min_index)
 530                 return 0;
 531
 532         do {
 533                 j = g->stack[--g->sp];
 534                 g->node[j].on_stack = 0;
 535                 g->node[j].scc = g->scc;
 536         } while (j != i);
 537         g->scc++;
 538
 539         return 0;
 540 }
 541
 542 static int detect_ccs(struct isl_sched_graph *graph, int directed)
 543 {
 544         int i;
 545
 546         graph->index = 0;
 547         graph->sp = 0;
 548         graph->scc = 0;
 549         for (i = graph->n - 1; i >= 0; --i)
 550                 graph->node[i].index = -1;
 551
 552         for (i = graph->n - 1; i >= 0; --i) {
 553                 if (graph->node[i].index >= 0)
 554                         continue;
 555                 if (detect_sccs_tarjan(graph, i, directed) < 0)
 556                         return -1;
 557         }
 558
 559         return 0;
 560 }
 561
 562 /* Apply Tarjan's algorithm to detect the strongly connected components
 563  * in the dependence graph.
 564  */
 565 static int detect_sccs(struct isl_sched_graph *graph)
 566 {
 567         return detect_ccs(graph, 1);
 568 }
 569
 570 /* Apply Tarjan's algorithm to detect the (weakly) connected components
 571  * in the dependence graph.
 572  */
 573 static int detect_wccs(struct isl_sched_graph *graph)
 574 {
 575         return detect_ccs(graph, 0);
 576 }
 577
 578 static int cmp_scc(const void *a, const void *b, void *data)
 579 {
 580         struct isl_sched_graph *graph = data;
 581         const int *i1 = a;
 582         const int *i2 = b;
 583
 584         return graph->node[*i1].scc - graph->node[*i2].scc;
 585 }
 586
 587 /* Sort the elements of graph->sorted according to the corresponding SCCs.
 588  */
 589 static void sort_sccs(struct isl_sched_graph *graph)
 590 {
 591         isl_quicksort(graph->sorted, graph->n, sizeof(int), &cmp_scc, graph);
 592 }
 593
 594 /* Given a dependence relation R from a node to itself,
 595  * construct the set of coefficients of valid constraints for elements
 596  * in that dependence relation.
 597  * In particular, the result contains tuples of coefficients
 598  * c_0, c_n, c_x such that
 599  *
 600  *      c_0 + c_n n + c_x y - c_x x >= 0 for each (x,y) in R
 601  *
 602  * or, equivalently,
 603  *
 604  *      c_0 + c_n n + c_x d >= 0 for each d in delta R = { y - x | (x,y) in R }
 605  *
 606  * We choose here to compute the dual of delta R.
 607  * Alternatively, we could have computed the dual of R, resulting
 608  * in a set of tuples c_0, c_n, c_x, c_y, and then
 609  * plugged in (c_0, c_n, c_x, -c_x).
 610  */
 611 static __isl_give isl_basic_set *intra_coefficients(
 612         struct isl_sched_graph *graph, __isl_take isl_map *map)
 613 {
 614         isl_ctx *ctx = isl_map_get_ctx(map);
 615         isl_set *delta;
 616         isl_basic_set *coef;
 617
 618         if (isl_hmap_map_basic_set_has(ctx, graph->intra_hmap, map))
 619                 return isl_hmap_map_basic_set_get(ctx, graph->intra_hmap, map);
 620
 621         delta = isl_set_remove_divs(isl_map_deltas(isl_map_copy(map)));
 622         coef = isl_set_coefficients(delta);
 623         isl_hmap_map_basic_set_set(ctx, graph->intra_hmap, map,
 624                                         isl_basic_set_copy(coef));
 625
 626         return coef;
 627 }
 628
 629 /* Given a dependence relation R, * construct the set of coefficients
 630  * of valid constraints for elements in that dependence relation.
 631  * In particular, the result contains tuples of coefficients
 632  * c_0, c_n, c_x, c_y such that
 633  *
 634  *      c_0 + c_n n + c_x x + c_y y >= 0 for each (x,y) in R
 635  *
 636  */
 637 static __isl_give isl_basic_set *inter_coefficients(
 638         struct isl_sched_graph *graph, __isl_take isl_map *map)
 639 {
 640         isl_ctx *ctx = isl_map_get_ctx(map);
 641         isl_set *set;
 642         isl_basic_set *coef;
 643
 644         if (isl_hmap_map_basic_set_has(ctx, graph->inter_hmap, map))
 645                 return isl_hmap_map_basic_set_get(ctx, graph->inter_hmap, map);
 646
 647         set = isl_map_wrap(isl_map_remove_divs(isl_map_copy(map)));
 648         coef = isl_set_coefficients(set);
 649         isl_hmap_map_basic_set_set(ctx, graph->inter_hmap, map,
 650                                         isl_basic_set_copy(coef));
 651
 652         return coef;
 653 }
 654
 655 /* Add constraints to graph->lp that force validity for the given
 656  * dependence from a node i to itself.
 657  * That is, add constraints that enforce
 658  *
 659  *      (c_i_0 + c_i_n n + c_i_x y) - (c_i_0 + c_i_n n + c_i_x x)
 660  *      = c_i_x (y - x) >= 0
 661  *
 662  * for each (x,y) in R.
 663  * We obtain general constraints on coefficients (c_0, c_n, c_x)
 664  * of valid constraints for (y - x) and then plug in (0, 0, c_i_x^+ - c_i_x^-),
 665  * where c_i_x = c_i_x^+ - c_i_x^-, with c_i_x^+ and c_i_x^- non-negative.
 666  * In graph->lp, the c_i_x^- appear before their c_i_x^+ counterpart.
 667  *
 668  * Actually, we do not construct constraints for the c_i_x themselves,
 669  * but for the coefficients of c_i_x written as a linear combination
 670  * of the columns in node->cmap.
 671  */
 672 static int add_intra_validity_constraints(struct isl_sched_graph *graph,
 673         struct isl_sched_edge *edge)
 674 {
 675         unsigned total;
 676         isl_map *map = isl_map_copy(edge->map);
 677         isl_ctx *ctx = isl_map_get_ctx(map);
 678         isl_space *dim;
 679         isl_dim_map *dim_map;
 680         isl_basic_set *coef;
 681         struct isl_sched_node *node = edge->src;
 682
 683         coef = intra_coefficients(graph, map);
 684
 685         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 686
 687         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 688                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
 689
 690         total = isl_basic_set_total_dim(graph->lp);
 691         dim_map = isl_dim_map_alloc(ctx, total);
 692         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
 693                           isl_space_dim(dim, isl_dim_set), 1,
 694                           node->nvar, -1);
 695         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
 696                           isl_space_dim(dim, isl_dim_set), 1,
 697                           node->nvar, 1);
 698         graph->lp = isl_basic_set_extend_constraints(graph->lp,
 699                         coef->n_eq, coef->n_ineq);
 700         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
 701                                                            coef, dim_map);
 702         isl_space_free(dim);
 703
 704         return 0;
 705 }
 706
 707 /* Add constraints to graph->lp that force validity for the given
 708  * dependence from node i to node j.
 709  * That is, add constraints that enforce
 710  *
 711  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) >= 0
 712  *
 713  * for each (x,y) in R.
 714  * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
 715  * of valid constraints for R and then plug in
 716  * (c_j_0 - c_i_0, c_j_n^+ - c_j_n^- - (c_i_n^+ - c_i_n^-),
 717  *  c_j_x^+ - c_j_x^- - (c_i_x^+ - c_i_x^-)),
 718  * where c_* = c_*^+ - c_*^-, with c_*^+ and c_*^- non-negative.
 719  * In graph->lp, the c_*^- appear before their c_*^+ counterpart.
 720  *
 721  * Actually, we do not construct constraints for the c_*_x themselves,
 722  * but for the coefficients of c_*_x written as a linear combination
 723  * of the columns in node->cmap.
 724  */
 725 static int add_inter_validity_constraints(struct isl_sched_graph *graph,
 726         struct isl_sched_edge *edge)
 727 {
 728         unsigned total;
 729         isl_map *map = isl_map_copy(edge->map);
 730         isl_ctx *ctx = isl_map_get_ctx(map);
 731         isl_space *dim;
 732         isl_dim_map *dim_map;
 733         isl_basic_set *coef;
 734         struct isl_sched_node *src = edge->src;
 735         struct isl_sched_node *dst = edge->dst;
 736
 737         coef = inter_coefficients(graph, map);
 738
 739         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 740
 741         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 742                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
 743         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 744                     isl_space_dim(dim, isl_dim_set) + src->nvar,
 745                     isl_mat_copy(dst->cmap));
 746
 747         total = isl_basic_set_total_dim(graph->lp);
 748         dim_map = isl_dim_map_alloc(ctx, total);
 749
 750         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
 751         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
 752         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
 753         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
 754                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
 755                           dst->nvar, -1);
 756         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
 757                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
 758                           dst->nvar, 1);
 759
 760         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
 761         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
 762         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
 763         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
 764                           isl_space_dim(dim, isl_dim_set), 1,
 765                           src->nvar, 1);
 766         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
 767                           isl_space_dim(dim, isl_dim_set), 1,
 768                           src->nvar, -1);
 769
 770         edge->start = graph->lp->n_ineq;
 771         graph->lp = isl_basic_set_extend_constraints(graph->lp,
 772                         coef->n_eq, coef->n_ineq);
 773         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
 774                                                            coef, dim_map);
 775         isl_space_free(dim);
 776         edge->end = graph->lp->n_ineq;
 777
 778         return 0;
 779 }
 780
 781 /* Add constraints to graph->lp that bound the dependence distance for the given
 782  * dependence from a node i to itself.
 783  * If s = 1, we add the constraint
 784  *
 785  *      c_i_x (y - x) <= m_0 + m_n n
 786  *
 787  * or
 788  *
 789  *      -c_i_x (y - x) + m_0 + m_n n >= 0
 790  *
 791  * for each (x,y) in R.
 792  * If s = -1, we add the constraint
 793  *
 794  *      -c_i_x (y - x) <= m_0 + m_n n
 795  *
 796  * or
 797  *
 798  *      c_i_x (y - x) + m_0 + m_n n >= 0
 799  *
 800  * for each (x,y) in R.
 801  * We obtain general constraints on coefficients (c_0, c_n, c_x)
 802  * of valid constraints for (y - x) and then plug in (m_0, m_n, -s * c_i_x),
 803  * with each coefficient (except m_0) represented as a pair of non-negative
 804  * coefficients.
 805  *
 806  * Actually, we do not construct constraints for the c_i_x themselves,
 807  * but for the coefficients of c_i_x written as a linear combination
 808  * of the columns in node->cmap.
 809  */
 810 static int add_intra_proximity_constraints(struct isl_sched_graph *graph,
 811         struct isl_sched_edge *edge, int s)
 812 {
 813         unsigned total;
 814         unsigned nparam;
 815         isl_map *map = isl_map_copy(edge->map);
 816         isl_ctx *ctx = isl_map_get_ctx(map);
 817         isl_space *dim;
 818         isl_dim_map *dim_map;
 819         isl_basic_set *coef;
 820         struct isl_sched_node *node = edge->src;
 821
 822         coef = intra_coefficients(graph, map);
 823
 824         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 825
 826         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 827                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(node->cmap));
 828
 829         nparam = isl_space_dim(node->dim, isl_dim_param);
 830         total = isl_basic_set_total_dim(graph->lp);
 831         dim_map = isl_dim_map_alloc(ctx, total);
 832         isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
 833         isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
 834         isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
 835         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
 836                           isl_space_dim(dim, isl_dim_set), 1,
 837                           node->nvar, s);
 838         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
 839                           isl_space_dim(dim, isl_dim_set), 1,
 840                           node->nvar, -s);
 841         graph->lp = isl_basic_set_extend_constraints(graph->lp,
 842                         coef->n_eq, coef->n_ineq);
 843         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
 844                                                            coef, dim_map);
 845         isl_space_free(dim);
 846
 847         return 0;
 848 }
 849
 850 /* Add constraints to graph->lp that bound the dependence distance for the given
 851  * dependence from node i to node j.
 852  * If s = 1, we add the constraint
 853  *
 854  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x)
 855  *              <= m_0 + m_n n
 856  *
 857  * or
 858  *
 859  *      -(c_j_0 + c_j_n n + c_j_x y) + (c_i_0 + c_i_n n + c_i_x x) +
 860  *              m_0 + m_n n >= 0
 861  *
 862  * for each (x,y) in R.
 863  * If s = -1, we add the constraint
 864  *
 865  *      -((c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x))
 866  *              <= m_0 + m_n n
 867  *
 868  * or
 869  *
 870  *      (c_j_0 + c_j_n n + c_j_x y) - (c_i_0 + c_i_n n + c_i_x x) +
 871  *              m_0 + m_n n >= 0
 872  *
 873  * for each (x,y) in R.
 874  * We obtain general constraints on coefficients (c_0, c_n, c_x, c_y)
 875  * of valid constraints for R and then plug in
 876  * (m_0 - s*c_j_0 + s*c_i_0, m_n - s*c_j_n + s*c_i_n,
 877  *  -s*c_j_x+s*c_i_x)
 878  * with each coefficient (except m_0, c_j_0 and c_i_0)
 879  * represented as a pair of non-negative coefficients.
 880  *
 881  * Actually, we do not construct constraints for the c_*_x themselves,
 882  * but for the coefficients of c_*_x written as a linear combination
 883  * of the columns in node->cmap.
 884  */
 885 static int add_inter_proximity_constraints(struct isl_sched_graph *graph,
 886         struct isl_sched_edge *edge, int s)
 887 {
 888         unsigned total;
 889         unsigned nparam;
 890         isl_map *map = isl_map_copy(edge->map);
 891         isl_ctx *ctx = isl_map_get_ctx(map);
 892         isl_space *dim;
 893         isl_dim_map *dim_map;
 894         isl_basic_set *coef;
 895         struct isl_sched_node *src = edge->src;
 896         struct isl_sched_node *dst = edge->dst;
 897
 898         coef = inter_coefficients(graph, map);
 899
 900         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
 901
 902         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 903                     isl_space_dim(dim, isl_dim_set), isl_mat_copy(src->cmap));
 904         coef = isl_basic_set_transform_dims(coef, isl_dim_set,
 905                     isl_space_dim(dim, isl_dim_set) + src->nvar,
 906                     isl_mat_copy(dst->cmap));
 907
 908         nparam = isl_space_dim(src->dim, isl_dim_param);
 909         total = isl_basic_set_total_dim(graph->lp);
 910         dim_map = isl_dim_map_alloc(ctx, total);
 911
 912         isl_dim_map_range(dim_map, 1, 0, 0, 0, 1, 1);
 913         isl_dim_map_range(dim_map, 4, 2, 1, 1, nparam, -1);
 914         isl_dim_map_range(dim_map, 5, 2, 1, 1, nparam, 1);
 915
 916         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, -s);
 917         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, s);
 918         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, -s);
 919         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
 920                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
 921                           dst->nvar, s);
 922         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
 923                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
 924                           dst->nvar, -s);
 925
 926         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, s);
 927         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, -s);
 928         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, s);
 929         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
 930                           isl_space_dim(dim, isl_dim_set), 1,
 931                           src->nvar, -s);
 932         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
 933                           isl_space_dim(dim, isl_dim_set), 1,
 934                           src->nvar, s);
 935
 936         graph->lp = isl_basic_set_extend_constraints(graph->lp,
 937                         coef->n_eq, coef->n_ineq);
 938         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
 939                                                            coef, dim_map);
 940         isl_space_free(dim);
 941
 942         return 0;
 943 }
 944
 945 static int add_all_validity_constraints(struct isl_sched_graph *graph)
 946 {
 947         int i;
 948
 949         for (i = 0; i < graph->n_edge; ++i) {
 950                 struct isl_sched_edge *edge= &graph->edge[i];
 951                 if (!edge->validity)
 952                         continue;
 953                 if (edge->src != edge->dst)
 954                         continue;
 955                 if (add_intra_validity_constraints(graph, edge) < 0)
 956                         return -1;
 957         }
 958
 959         for (i = 0; i < graph->n_edge; ++i) {
 960                 struct isl_sched_edge *edge = &graph->edge[i];
 961                 if (!edge->validity)
 962                         continue;
 963                 if (edge->src == edge->dst)
 964                         continue;
 965                 if (add_inter_validity_constraints(graph, edge) < 0)
 966                         return -1;
 967         }
 968
 969         return 0;
 970 }
 971
 972 /* Add constraints to graph->lp that bound the dependence distance
 973  * for all dependence relations.
 974  * If a given proximity dependence is identical to a validity
 975  * dependence, then the dependence distance is already bounded
 976  * from below (by zero), so we only need to bound the distance
 977  * from above.
 978  * Otherwise, we need to bound the distance both from above and from below.
 979  */
 980 static int add_all_proximity_constraints(struct isl_sched_graph *graph)
 981 {
 982         int i;
 983
 984         for (i = 0; i < graph->n_edge; ++i) {
 985                 struct isl_sched_edge *edge= &graph->edge[i];
 986                 if (!edge->proximity)
 987                         continue;
 988                 if (edge->src == edge->dst &&
 989                     add_intra_proximity_constraints(graph, edge, 1) < 0)
 990                         return -1;
 991                 if (edge->src != edge->dst &&
 992                     add_inter_proximity_constraints(graph, edge, 1) < 0)
 993                         return -1;
 994                 if (edge->validity)
 995                         continue;
 996                 if (edge->src == edge->dst &&
 997                     add_intra_proximity_constraints(graph, edge, -1) < 0)
 998                         return -1;
 999                 if (edge->src != edge->dst &&
1000                     add_inter_proximity_constraints(graph, edge, -1) < 0)
1001                         return -1;
1002         }
1003
1004         return 0;
1005 }
1006
1007 /* Compute a basis for the rows in the linear part of the schedule
1008  * and extend this basis to a full basis.  The remaining rows
1009  * can then be used to force linear independence from the rows
1010  * in the schedule.
1011  *
1012  * In particular, given the schedule rows S, we compute
1013  *
1014  *      S = H Q
1015  *
1016  * with H the Hermite normal form of S.  That is, all but the
1017  * first rank columns of Q are zero and so each row in S is
1018  * a linear combination of the first rank rows of Q.
1019  * The matrix Q is then transposed because we will write the
1020  * coefficients of the next schedule row as a column vector s
1021  * and express this s as a linear combination s = Q c of the
1022  * computed basis.
1023  */
1024 static int node_update_cmap(struct isl_sched_node *node)
1025 {
1026         isl_mat *H, *Q;
1027         int n_row = isl_mat_rows(node->sched);
1028
1029         H = isl_mat_sub_alloc(node->sched, 0, n_row,
1030                               1 + node->nparam, node->nvar);
1031
1032         H = isl_mat_left_hermite(H, 0, NULL, &Q);
1033         isl_mat_free(node->cmap);
1034         node->cmap = isl_mat_transpose(Q);
1035         node->rank = isl_mat_initial_non_zero_cols(H);
1036         isl_mat_free(H);
1037
1038         if (!node->cmap || node->rank < 0)
1039                 return -1;
1040         return 0;
1041 }
1042
1043 /* Count the number of equality and inequality constraints
1044  * that will be added for the given map.
1045  * If once is set, then we count
1046  * each edge exactly once.  Otherwise, we count as follows
1047  * validity             -> 1 (>= 0)
1048  * validity+proximity   -> 2 (>= 0 and upper bound)
1049  * proximity            -> 2 (lower and upper bound)
1050  */
1051 static int count_map_constraints(struct isl_sched_graph *graph,
1052         struct isl_sched_edge *edge, __isl_take isl_map *map,
1053         int *n_eq, int *n_ineq, int once)
1054 {
1055         isl_basic_set *coef;
1056         int f = once ? 1 : edge->proximity ? 2 : 1;
1057
1058         if (edge->src == edge->dst)
1059                 coef = intra_coefficients(graph, map);
1060         else
1061                 coef = inter_coefficients(graph, map);
1062         if (!coef)
1063                 return -1;
1064         *n_eq += f * coef->n_eq;
1065         *n_ineq += f * coef->n_ineq;
1066         isl_basic_set_free(coef);
1067
1068         return 0;
1069 }
1070
1071 /* Count the number of equality and inequality constraints
1072  * that will be added to the main lp problem.
1073  * If once is set, then we count
1074  * each edge exactly once.  Otherwise, we count as follows
1075  * validity             -> 1 (>= 0)
1076  * validity+proximity   -> 2 (>= 0 and upper bound)
1077  * proximity            -> 2 (lower and upper bound)
1078  */
1079 static int count_constraints(struct isl_sched_graph *graph,
1080         int *n_eq, int *n_ineq, int once)
1081 {
1082         int i;
1083
1084         *n_eq = *n_ineq = 0;
1085         for (i = 0; i < graph->n_edge; ++i) {
1086                 struct isl_sched_edge *edge= &graph->edge[i];
1087                 isl_map *map = isl_map_copy(edge->map);
1088
1089                 if (count_map_constraints(graph, edge, map,
1090                                           n_eq, n_ineq, once) < 0)
1091                         return -1;
1092         }
1093
1094         return 0;
1095 }
1096
1097 /* Construct an ILP problem for finding schedule coefficients
1098  * that result in non-negative, but small dependence distances
1099  * over all dependences.
1100  * In particular, the dependence distances over proximity edges
1101  * are bounded by m_0 + m_n n and we compute schedule coefficients
1102  * with small values (preferably zero) of m_n and m_0.
1103  *
1104  * All variables of the ILP are non-negative.  The actual coefficients
1105  * may be negative, so each coefficient is represented as the difference
1106  * of two non-negative variables.  The negative part always appears
1107  * immediately before the positive part.
1108  * Other than that, the variables have the following order
1109  *
1110  *      - sum of positive and negative parts of m_n coefficients
1111  *      - m_0
1112  *      - sum of positive and negative parts of all c_n coefficients
1113  *              (unconstrained when computing non-parametric schedules)
1114  *      - sum of positive and negative parts of all c_x coefficients
1115  *      - positive and negative parts of m_n coefficients
1116  *      - for each node
1117  *              - c_i_0
1118  *              - positive and negative parts of c_i_n (if parametric)
1119  *              - positive and negative parts of c_i_x
1120  *
1121  * The c_i_x are not represented directly, but through the columns of
1122  * node->cmap.  That is, the computed values are for variable t_i_x
1123  * such that c_i_x = Q t_i_x with Q equal to node->cmap.
1124  *
1125  * The constraints are those from the edges plus two or three equalities
1126  * to express the sums.
1127  *
1128  * If force_zero is set, then we add equalities to ensure that
1129  * the sum of the m_n coefficients and m_0 are both zero.
1130  */
1131 static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph,
1132         int force_zero)
1133 {
1134         int i, j;
1135         int k;
1136         unsigned nparam;
1137         unsigned total;
1138         isl_space *dim;
1139         int parametric;
1140         int param_pos;
1141         int n_eq, n_ineq;
1142
1143         parametric = ctx->opt->schedule_parametric;
1144         nparam = isl_space_dim(graph->node[0].dim, isl_dim_param);
1145         param_pos = 4;
1146         total = param_pos + 2 * nparam;
1147         for (i = 0; i < graph->n; ++i) {
1148                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1149                 if (node_update_cmap(node) < 0)
1150                         return -1;
1151                 node->start = total;
1152                 total += 1 + 2 * (node->nparam + node->nvar);
1153         }
1154
1155         if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0)
1156                 return -1;
1157
1158         dim = isl_space_set_alloc(ctx, 0, total);
1159         isl_basic_set_free(graph->lp);
1160         n_eq += 2 + parametric + force_zero;
1161         graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
1162
1163         k = isl_basic_set_alloc_equality(graph->lp);
1164         if (k < 0)
1165                 return -1;
1166         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1167         if (!force_zero)
1168                 isl_int_set_si(graph->lp->eq[k][1], -1);
1169         for (i = 0; i < 2 * nparam; ++i)
1170                 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1171
1172         if (force_zero) {
1173                 k = isl_basic_set_alloc_equality(graph->lp);
1174                 if (k < 0)
1175                         return -1;
1176                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1177                 isl_int_set_si(graph->lp->eq[k][2], -1);
1178         }
1179
1180         if (parametric) {
1181                 k = isl_basic_set_alloc_equality(graph->lp);
1182                 if (k < 0)
1183                         return -1;
1184                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1185                 isl_int_set_si(graph->lp->eq[k][3], -1);
1186                 for (i = 0; i < graph->n; ++i) {
1187                         int pos = 1 + graph->node[i].start + 1;
1188
1189                         for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1190                                 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1191                 }
1192         }
1193
1194         k = isl_basic_set_alloc_equality(graph->lp);
1195         if (k < 0)
1196                 return -1;
1197         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1198         isl_int_set_si(graph->lp->eq[k][4], -1);
1199         for (i = 0; i < graph->n; ++i) {
1200                 struct isl_sched_node *node = &graph->node[i];
1201                 int pos = 1 + node->start + 1 + 2 * node->nparam;
1202
1203                 for (j = 0; j < 2 * node->nvar; ++j)
1204                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1205         }
1206
1207         if (add_all_validity_constraints(graph) < 0)
1208                 return -1;
1209         if (add_all_proximity_constraints(graph) < 0)
1210                 return -1;
1211
1212         return 0;
1213 }
1214
1215 /* Analyze the conflicting constraint found by
1216  * isl_tab_basic_set_non_trivial_lexmin.  If it corresponds to the validity
1217  * constraint of one of the edges between distinct nodes, living, moreover
1218  * in distinct SCCs, then record the source and sink SCC as this may
1219  * be a good place to cut between SCCs.
1220  */
1221 static int check_conflict(int con, void *user)
1222 {
1223         int i;
1224         struct isl_sched_graph *graph = user;
1225
1226         if (graph->src_scc >= 0)
1227                 return 0;
1228
1229         con -= graph->lp->n_eq;
1230
1231         if (con >= graph->lp->n_ineq)
1232                 return 0;
1233
1234         for (i = 0; i < graph->n_edge; ++i) {
1235                 if (!graph->edge[i].validity)
1236                         continue;
1237                 if (graph->edge[i].src == graph->edge[i].dst)
1238                         continue;
1239                 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1240                         continue;
1241                 if (graph->edge[i].start > con)
1242                         continue;
1243                 if (graph->edge[i].end <= con)
1244                         continue;
1245                 graph->src_scc = graph->edge[i].src->scc;
1246                 graph->dst_scc = graph->edge[i].dst->scc;
1247         }
1248
1249         return 0;
1250 }
1251
1252 /* Check whether the next schedule row of the given node needs to be
1253  * non-trivial.  Lower-dimensional domains may have some trivial rows,
1254  * but as soon as the number of remaining required non-trivial rows
1255  * is as large as the number or remaining rows to be computed,
1256  * all remaining rows need to be non-trivial.
1257  */
1258 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1259 {
1260         return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1261 }
1262
1263 /* Solve the ILP problem constructed in setup_lp.
1264  * For each node such that all the remaining rows of its schedule
1265  * need to be non-trivial, we construct a non-triviality region.
1266  * This region imposes that the next row is independent of previous rows.
1267  * In particular the coefficients c_i_x are represented by t_i_x
1268  * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1269  * its first columns span the rows of the previously computed part
1270  * of the schedule.  The non-triviality region enforces that at least
1271  * one of the remaining components of t_i_x is non-zero, i.e.,
1272  * that the new schedule row depends on at least one of the remaining
1273  * columns of Q.
1274  */
1275 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1276 {
1277         int i;
1278         isl_vec *sol;
1279         isl_basic_set *lp;
1280
1281         for (i = 0; i < graph->n; ++i) {
1282                 struct isl_sched_node *node = &graph->node[i];
1283                 int skip = node->rank;
1284                 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1285                 if (needs_row(graph, node))
1286                         graph->region[i].len = 2 * (node->nvar - skip);
1287                 else
1288                         graph->region[i].len = 0;
1289         }
1290         lp = isl_basic_set_copy(graph->lp);
1291         sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1292                                        graph->region, &check_conflict, graph);
1293         return sol;
1294 }
1295
1296 /* Update the schedules of all nodes based on the given solution
1297  * of the LP problem.
1298  * The new row is added to the current band.
1299  * All possibly negative coefficients are encoded as a difference
1300  * of two non-negative variables, so we need to perform the subtraction
1301  * here.  Moreover, if use_cmap is set, then the solution does
1302  * not refer to the actual coefficients c_i_x, but instead to variables
1303  * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1304  * In this case, we then also need to perform this multiplication
1305  * to obtain the values of c_i_x.
1306  *
1307  * If check_zero is set, then the first two coordinates of sol are
1308  * assumed to correspond to the dependence distance.  If these two
1309  * coordinates are zero, then the corresponding scheduling dimension
1310  * is marked as being zero distance.
1311  */
1312 static int update_schedule(struct isl_sched_graph *graph,
1313         __isl_take isl_vec *sol, int use_cmap, int check_zero)
1314 {
1315         int i, j;
1316         int zero = 0;
1317         isl_vec *csol = NULL;
1318
1319         if (!sol)
1320                 goto error;
1321         if (sol->size == 0)
1322                 isl_die(sol->ctx, isl_error_internal,
1323                         "no solution found", goto error);
1324
1325         if (check_zero)
1326                 zero = isl_int_is_zero(sol->el[1]) &&
1327                            isl_int_is_zero(sol->el[2]);
1328
1329         for (i = 0; i < graph->n; ++i) {
1330                 struct isl_sched_node *node = &graph->node[i];
1331                 int pos = node->start;
1332                 int row = isl_mat_rows(node->sched);
1333
1334                 isl_vec_free(csol);
1335                 csol = isl_vec_alloc(sol->ctx, node->nvar);
1336                 if (!csol)
1337                         goto error;
1338
1339                 isl_map_free(node->sched_map);
1340                 node->sched_map = NULL;
1341                 node->sched = isl_mat_add_rows(node->sched, 1);
1342                 if (!node->sched)
1343                         goto error;
1344                 node->sched = isl_mat_set_element(node->sched, row, 0,
1345                                                   sol->el[1 + pos]);
1346                 for (j = 0; j < node->nparam + node->nvar; ++j)
1347                         isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1348                                     sol->el[1 + pos + 1 + 2 * j + 1],
1349                                     sol->el[1 + pos + 1 + 2 * j]);
1350                 for (j = 0; j < node->nparam; ++j)
1351                         node->sched = isl_mat_set_element(node->sched,
1352                                         row, 1 + j, sol->el[1+pos+1+2*j+1]);
1353                 for (j = 0; j < node->nvar; ++j)
1354                         isl_int_set(csol->el[j],
1355                                     sol->el[1+pos+1+2*(node->nparam+j)+1]);
1356                 if (use_cmap)
1357                         csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1358                                                    csol);
1359                 if (!csol)
1360                         goto error;
1361                 for (j = 0; j < node->nvar; ++j)
1362                         node->sched = isl_mat_set_element(node->sched,
1363                                         row, 1 + node->nparam + j, csol->el[j]);
1364                 node->band[graph->n_total_row] = graph->n_band;
1365                 node->zero[graph->n_total_row] = zero;
1366         }
1367         isl_vec_free(sol);
1368         isl_vec_free(csol);
1369
1370         graph->n_row++;
1371         graph->n_total_row++;
1372
1373         return 0;
1374 error:
1375         isl_vec_free(sol);
1376         isl_vec_free(csol);
1377         return -1;
1378 }
1379
1380 /* Convert node->sched into a map and return this map.
1381  * We simply add equality constraints that express each output variable
1382  * as the affine combination of parameters and input variables specified
1383  * by the schedule matrix.
1384  *
1385  * The result is cached in node->sched_map, which needs to be released
1386  * whenever node->sched is updated.
1387  */
1388 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1389 {
1390         int i, j;
1391         isl_space *dim;
1392         isl_local_space *ls;
1393         isl_basic_map *bmap;
1394         isl_constraint *c;
1395         int nrow, ncol;
1396         isl_int v;
1397
1398         if (node->sched_map)
1399                 return isl_map_copy(node->sched_map);
1400
1401         nrow = isl_mat_rows(node->sched);
1402         ncol = isl_mat_cols(node->sched) - 1;
1403         dim = isl_space_from_domain(isl_space_copy(node->dim));
1404         dim = isl_space_add_dims(dim, isl_dim_out, nrow);
1405         bmap = isl_basic_map_universe(isl_space_copy(dim));
1406         ls = isl_local_space_from_space(dim);
1407
1408         isl_int_init(v);
1409
1410         for (i = 0; i < nrow; ++i) {
1411                 c = isl_equality_alloc(isl_local_space_copy(ls));
1412                 isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
1413                 isl_mat_get_element(node->sched, i, 0, &v);
1414                 isl_constraint_set_constant(c, v);
1415                 for (j = 0; j < node->nparam; ++j) {
1416                         isl_mat_get_element(node->sched, i, 1 + j, &v);
1417                         isl_constraint_set_coefficient(c, isl_dim_param, j, v);
1418                 }
1419                 for (j = 0; j < node->nvar; ++j) {
1420                         isl_mat_get_element(node->sched,
1421                                             i, 1 + node->nparam + j, &v);
1422                         isl_constraint_set_coefficient(c, isl_dim_in, j, v);
1423                 }
1424                 bmap = isl_basic_map_add_constraint(bmap, c);
1425         }
1426
1427         isl_int_clear(v);
1428
1429         isl_local_space_free(ls);
1430
1431         node->sched_map = isl_map_from_basic_map(bmap);
1432         return isl_map_copy(node->sched_map);
1433 }
1434
1435 /* Update the given dependence relation based on the current schedule.
1436  * That is, intersect the dependence relation with a map expressing
1437  * that source and sink are executed within the same iteration of
1438  * the current schedule.
1439  * This is not the most efficient way, but this shouldn't be a critical
1440  * operation.
1441  */
1442 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1443         struct isl_sched_node *src, struct isl_sched_node *dst)
1444 {
1445         isl_map *src_sched, *dst_sched, *id;
1446
1447         src_sched = node_extract_schedule(src);
1448         dst_sched = node_extract_schedule(dst);
1449         id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1450         return isl_map_intersect(map, id);
1451 }
1452
1453 /* Update the dependence relations of all edges based on the current schedule.
1454  * If a dependence is carried completely by the current schedule, then
1455  * it is removed and edge_table is updated accordingly.
1456  */
1457 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1458 {
1459         int i;
1460         int reset_table = 0;
1461
1462         for (i = graph->n_edge - 1; i >= 0; --i) {
1463                 struct isl_sched_edge *edge = &graph->edge[i];
1464                 edge->map = specialize(edge->map, edge->src, edge->dst);
1465                 if (!edge->map)
1466                         return -1;
1467
1468                 if (isl_map_plain_is_empty(edge->map)) {
1469                         reset_table = 1;
1470                         isl_map_free(edge->map);
1471                         if (i != graph->n_edge - 1)
1472                                 graph->edge[i] = graph->edge[graph->n_edge - 1];
1473                         graph->n_edge--;
1474                 }
1475         }
1476
1477         if (reset_table) {
1478                 isl_hash_table_free(ctx, graph->edge_table);
1479                 graph->edge_table = NULL;
1480                 return graph_init_edge_table(ctx, graph);
1481         }
1482
1483         return 0;
1484 }
1485
1486 static void next_band(struct isl_sched_graph *graph)
1487 {
1488         graph->band_start = graph->n_total_row;
1489         graph->n_band++;
1490 }
1491
1492 /* Topologically sort statements mapped to same schedule iteration
1493  * and add a row to the schedule corresponding to this order.
1494  */
1495 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1496 {
1497         int i, j;
1498
1499         if (graph->n <= 1)
1500                 return 0;
1501
1502         if (update_edges(ctx, graph) < 0)
1503                 return -1;
1504
1505         if (graph->n_edge == 0)
1506                 return 0;
1507
1508         if (detect_sccs(graph) < 0)
1509                 return -1;
1510
1511         for (i = 0; i < graph->n; ++i) {
1512                 struct isl_sched_node *node = &graph->node[i];
1513                 int row = isl_mat_rows(node->sched);
1514                 int cols = isl_mat_cols(node->sched);
1515
1516                 isl_map_free(node->sched_map);
1517                 node->sched_map = NULL;
1518                 node->sched = isl_mat_add_rows(node->sched, 1);
1519                 if (!node->sched)
1520                         return -1;
1521                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1522                                                      node->scc);
1523                 for (j = 1; j < cols; ++j)
1524                         node->sched = isl_mat_set_element_si(node->sched,
1525                                                              row, j, 0);
1526                 node->band[graph->n_total_row] = graph->n_band;
1527         }
1528
1529         graph->n_total_row++;
1530         next_band(graph);
1531
1532         return 0;
1533 }
1534
1535 /* Construct an isl_schedule based on the computed schedule stored
1536  * in graph and with parameters specified by dim.
1537  */
1538 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1539         __isl_take isl_space *dim)
1540 {
1541         int i;
1542         isl_ctx *ctx;
1543         isl_schedule *sched = NULL;
1544
1545         if (!dim)
1546                 return NULL;
1547
1548         ctx = isl_space_get_ctx(dim);
1549         sched = isl_calloc(ctx, struct isl_schedule,
1550                            sizeof(struct isl_schedule) +
1551                            (graph->n - 1) * sizeof(struct isl_schedule_node));
1552         if (!sched)
1553                 goto error;
1554
1555         sched->ref = 1;
1556         sched->n = graph->n;
1557         sched->n_band = graph->n_band;
1558         sched->n_total_row = graph->n_total_row;
1559
1560         for (i = 0; i < sched->n; ++i) {
1561                 int r, b;
1562                 int *band_end, *band_id, *zero;
1563
1564                 band_end = isl_alloc_array(ctx, int, graph->n_band);
1565                 band_id = isl_alloc_array(ctx, int, graph->n_band);
1566                 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1567                 sched->node[i].sched = node_extract_schedule(&graph->node[i]);
1568                 sched->node[i].band_end = band_end;
1569                 sched->node[i].band_id = band_id;
1570                 sched->node[i].zero = zero;
1571                 if (!band_end || !band_id || !zero)
1572                         goto error;
1573
1574                 for (r = 0; r < graph->n_total_row; ++r)
1575                         zero[r] = graph->node[i].zero[r];
1576                 for (r = b = 0; r < graph->n_total_row; ++r) {
1577                         if (graph->node[i].band[r] == b)
1578                                 continue;
1579                         band_end[b++] = r;
1580                         if (graph->node[i].band[r] == -1)
1581                                 break;
1582                 }
1583                 if (r == graph->n_total_row)
1584                         band_end[b++] = r;
1585                 sched->node[i].n_band = b;
1586                 for (--b; b >= 0; --b)
1587                         band_id[b] = graph->node[i].band_id[b];
1588         }
1589
1590         sched->dim = dim;
1591
1592         return sched;
1593 error:
1594         isl_space_free(dim);
1595         isl_schedule_free(sched);
1596         return NULL;
1597 }
1598
1599 /* Copy nodes that satisfy node_pred from the src dependence graph
1600  * to the dst dependence graph.
1601  */
1602 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1603         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1604 {
1605         int i;
1606
1607         dst->n = 0;
1608         for (i = 0; i < src->n; ++i) {
1609                 if (!node_pred(&src->node[i], data))
1610                         continue;
1611                 dst->node[dst->n].dim = isl_space_copy(src->node[i].dim);
1612                 dst->node[dst->n].nvar = src->node[i].nvar;
1613                 dst->node[dst->n].nparam = src->node[i].nparam;
1614                 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1615                 dst->node[dst->n].sched_map =
1616                         isl_map_copy(src->node[i].sched_map);
1617                 dst->node[dst->n].band = src->node[i].band;
1618                 dst->node[dst->n].band_id = src->node[i].band_id;
1619                 dst->node[dst->n].zero = src->node[i].zero;
1620                 dst->n++;
1621         }
1622
1623         return 0;
1624 }
1625
1626 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1627  * to the dst dependence graph.
1628  */
1629 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1630         struct isl_sched_graph *src,
1631         int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1632 {
1633         int i;
1634
1635         dst->n_edge = 0;
1636         for (i = 0; i < src->n_edge; ++i) {
1637                 struct isl_sched_edge *edge = &src->edge[i];
1638                 isl_map *map;
1639
1640                 if (!edge_pred(edge, data))
1641                         continue;
1642
1643                 if (isl_map_plain_is_empty(edge->map))
1644                         continue;
1645
1646                 map = isl_map_copy(edge->map);
1647
1648                 dst->edge[dst->n_edge].src =
1649                         graph_find_node(ctx, dst, edge->src->dim);
1650                 dst->edge[dst->n_edge].dst =
1651                         graph_find_node(ctx, dst, edge->dst->dim);
1652                 dst->edge[dst->n_edge].map = map;
1653                 dst->edge[dst->n_edge].validity = edge->validity;
1654                 dst->edge[dst->n_edge].proximity = edge->proximity;
1655                 dst->n_edge++;
1656         }
1657
1658         return 0;
1659 }
1660
1661 /* Given a "src" dependence graph that contains the nodes from "dst"
1662  * that satisfy node_pred, copy the schedule computed in "src"
1663  * for those nodes back to "dst".
1664  */
1665 static int copy_schedule(struct isl_sched_graph *dst,
1666         struct isl_sched_graph *src,
1667         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1668 {
1669         int i;
1670
1671         src->n = 0;
1672         for (i = 0; i < dst->n; ++i) {
1673                 if (!node_pred(&dst->node[i], data))
1674                         continue;
1675                 isl_mat_free(dst->node[i].sched);
1676                 isl_map_free(dst->node[i].sched_map);
1677                 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1678                 dst->node[i].sched_map =
1679                         isl_map_copy(src->node[src->n].sched_map);
1680                 src->n++;
1681         }
1682
1683         dst->n_total_row = src->n_total_row;
1684         dst->n_band = src->n_band;
1685
1686         return 0;
1687 }
1688
1689 /* Compute the maximal number of variables over all nodes.
1690  * This is the maximal number of linearly independent schedule
1691  * rows that we need to compute.
1692  * Just in case we end up in a part of the dependence graph
1693  * with only lower-dimensional domains, we make sure we will
1694  * compute the required amount of extra linearly independent rows.
1695  */
1696 static int compute_maxvar(struct isl_sched_graph *graph)
1697 {
1698         int i;
1699
1700         graph->maxvar = 0;
1701         for (i = 0; i < graph->n; ++i) {
1702                 struct isl_sched_node *node = &graph->node[i];
1703                 int nvar;
1704
1705                 if (node_update_cmap(node) < 0)
1706                         return -1;
1707                 nvar = node->nvar + graph->n_row - node->rank;
1708                 if (nvar > graph->maxvar)
1709                         graph->maxvar = nvar;
1710         }
1711
1712         return 0;
1713 }
1714
1715 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1716 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1717
1718 /* Compute a schedule for a subgraph of "graph".  In particular, for
1719  * the graph composed of nodes that satisfy node_pred and edges that
1720  * that satisfy edge_pred.  The caller should precompute the number
1721  * of nodes and edges that satisfy these predicates and pass them along
1722  * as "n" and "n_edge".
1723  * If the subgraph is known to consist of a single component, then wcc should
1724  * be set and then we call compute_schedule_wcc on the constructed subgraph.
1725  * Otherwise, we call compute_schedule, which will check whether the subgraph
1726  * is connected.
1727  */
1728 static int compute_sub_schedule(isl_ctx *ctx,
1729         struct isl_sched_graph *graph, int n, int n_edge,
1730         int (*node_pred)(struct isl_sched_node *node, int data),
1731         int (*edge_pred)(struct isl_sched_edge *edge, int data),
1732         int data, int wcc)
1733 {
1734         struct isl_sched_graph split = { 0 };
1735
1736         if (graph_alloc(ctx, &split, n, n_edge) < 0)
1737                 goto error;
1738         if (copy_nodes(&split, graph, node_pred, data) < 0)
1739                 goto error;
1740         if (graph_init_table(ctx, &split) < 0)
1741                 goto error;
1742         if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1743                 goto error;
1744         if (graph_init_edge_table(ctx, &split) < 0)
1745                 goto error;
1746         split.n_row = graph->n_row;
1747         split.n_total_row = graph->n_total_row;
1748         split.n_band = graph->n_band;
1749         split.band_start = graph->band_start;
1750
1751         if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1752                 goto error;
1753         if (!wcc && compute_schedule(ctx, &split) < 0)
1754                 goto error;
1755
1756         copy_schedule(graph, &split, node_pred, data);
1757
1758         graph_free(ctx, &split);
1759         return 0;
1760 error:
1761         graph_free(ctx, &split);
1762         return -1;
1763 }
1764
1765 static int node_scc_exactly(struct isl_sched_node *node, int scc)
1766 {
1767         return node->scc == scc;
1768 }
1769
1770 static int node_scc_at_most(struct isl_sched_node *node, int scc)
1771 {
1772         return node->scc <= scc;
1773 }
1774
1775 static int node_scc_at_least(struct isl_sched_node *node, int scc)
1776 {
1777         return node->scc >= scc;
1778 }
1779
1780 static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc)
1781 {
1782         return edge->src->scc == scc;
1783 }
1784
1785 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
1786 {
1787         return edge->dst->scc <= scc;
1788 }
1789
1790 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
1791 {
1792         return edge->src->scc >= scc;
1793 }
1794
1795 /* Pad the schedules of all nodes with zero rows such that in the end
1796  * they all have graph->n_total_row rows.
1797  * The extra rows don't belong to any band, so they get assigned band number -1.
1798  */
1799 static int pad_schedule(struct isl_sched_graph *graph)
1800 {
1801         int i, j;
1802
1803         for (i = 0; i < graph->n; ++i) {
1804                 struct isl_sched_node *node = &graph->node[i];
1805                 int row = isl_mat_rows(node->sched);
1806                 if (graph->n_total_row > row) {
1807                         isl_map_free(node->sched_map);
1808                         node->sched_map = NULL;
1809                 }
1810                 node->sched = isl_mat_add_zero_rows(node->sched,
1811                                                     graph->n_total_row - row);
1812                 if (!node->sched)
1813                         return -1;
1814                 for (j = row; j < graph->n_total_row; ++j)
1815                         node->band[j] = -1;
1816         }
1817
1818         return 0;
1819 }
1820
1821 /* Split the current graph into two parts and compute a schedule for each
1822  * part individually.  In particular, one part consists of all SCCs up
1823  * to and including graph->src_scc, while the other part contains the other
1824  * SCCS.
1825  *
1826  * The split is enforced in the schedule by constant rows with two different
1827  * values (0 and 1).  These constant rows replace the previously computed rows
1828  * in the current band.
1829  * It would be possible to reuse them as the first rows in the next
1830  * band, but recomputing them may result in better rows as we are looking
1831  * at a smaller part of the dependence graph.
1832  *
1833  * The band_id of the second group is set to n, where n is the number
1834  * of nodes in the first group.  This ensures that the band_ids over
1835  * the two groups remain disjoint, even if either or both of the two
1836  * groups contain independent components.
1837  */
1838 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
1839 {
1840         int i, j, n, e1, e2;
1841         int n_total_row, orig_total_row;
1842         int n_band, orig_band;
1843         int drop;
1844
1845         drop = graph->n_total_row - graph->band_start;
1846         graph->n_total_row -= drop;
1847         graph->n_row -= drop;
1848
1849         n = 0;
1850         for (i = 0; i < graph->n; ++i) {
1851                 struct isl_sched_node *node = &graph->node[i];
1852                 int row = isl_mat_rows(node->sched) - drop;
1853                 int cols = isl_mat_cols(node->sched);
1854                 int before = node->scc <= graph->src_scc;
1855
1856                 if (before)
1857                         n++;
1858
1859                 isl_map_free(node->sched_map);
1860                 node->sched_map = NULL;
1861                 node->sched = isl_mat_drop_rows(node->sched,
1862                                                 graph->band_start, drop);
1863                 node->sched = isl_mat_add_rows(node->sched, 1);
1864                 if (!node->sched)
1865                         return -1;
1866                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1867                                                      !before);
1868                 for (j = 1; j < cols; ++j)
1869                         node->sched = isl_mat_set_element_si(node->sched,
1870                                                              row, j, 0);
1871                 node->band[graph->n_total_row] = graph->n_band;
1872         }
1873
1874         e1 = e2 = 0;
1875         for (i = 0; i < graph->n_edge; ++i) {
1876                 if (graph->edge[i].dst->scc <= graph->src_scc)
1877                         e1++;
1878                 if (graph->edge[i].src->scc > graph->src_scc)
1879                         e2++;
1880         }
1881
1882         graph->n_total_row++;
1883         next_band(graph);
1884
1885         for (i = 0; i < graph->n; ++i) {
1886                 struct isl_sched_node *node = &graph->node[i];
1887                 if (node->scc > graph->src_scc)
1888                         node->band_id[graph->n_band] = n;
1889         }
1890
1891         orig_total_row = graph->n_total_row;
1892         orig_band = graph->n_band;
1893         if (compute_sub_schedule(ctx, graph, n, e1,
1894                                 &node_scc_at_most, &edge_dst_scc_at_most,
1895                                 graph->src_scc, 0) < 0)
1896                 return -1;
1897         n_total_row = graph->n_total_row;
1898         graph->n_total_row = orig_total_row;
1899         n_band = graph->n_band;
1900         graph->n_band = orig_band;
1901         if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
1902                                 &node_scc_at_least, &edge_src_scc_at_least,
1903                                 graph->src_scc + 1, 0) < 0)
1904                 return -1;
1905         if (n_total_row > graph->n_total_row)
1906                 graph->n_total_row = n_total_row;
1907         if (n_band > graph->n_band)
1908                 graph->n_band = n_band;
1909
1910         return pad_schedule(graph);
1911 }
1912
1913 /* Compute the next band of the schedule after updating the dependence
1914  * relations based on the the current schedule.
1915  */
1916 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
1917 {
1918         if (update_edges(ctx, graph) < 0)
1919                 return -1;
1920         next_band(graph);
1921
1922         return compute_schedule(ctx, graph);
1923 }
1924
1925 /* Add constraints to graph->lp that force the dependence "map" (which
1926  * is part of the dependence relation of "edge")
1927  * to be respected and attempt to carry it, where the edge is one from
1928  * a node j to itself.  "pos" is the sequence number of the given map.
1929  * That is, add constraints that enforce
1930  *
1931  *      (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
1932  *      = c_j_x (y - x) >= e_i
1933  *
1934  * for each (x,y) in R.
1935  * We obtain general constraints on coefficients (c_0, c_n, c_x)
1936  * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
1937  * with each coefficient in c_j_x represented as a pair of non-negative
1938  * coefficients.
1939  */
1940 static int add_intra_constraints(struct isl_sched_graph *graph,
1941         struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
1942 {
1943         unsigned total;
1944         isl_ctx *ctx = isl_map_get_ctx(map);
1945         isl_space *dim;
1946         isl_dim_map *dim_map;
1947         isl_basic_set *coef;
1948         struct isl_sched_node *node = edge->src;
1949
1950         coef = intra_coefficients(graph, map);
1951
1952         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1953
1954         total = isl_basic_set_total_dim(graph->lp);
1955         dim_map = isl_dim_map_alloc(ctx, total);
1956         isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
1957         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1958                           isl_space_dim(dim, isl_dim_set), 1,
1959                           node->nvar, -1);
1960         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1961                           isl_space_dim(dim, isl_dim_set), 1,
1962                           node->nvar, 1);
1963         graph->lp = isl_basic_set_extend_constraints(graph->lp,
1964                         coef->n_eq, coef->n_ineq);
1965         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1966                                                            coef, dim_map);
1967         isl_space_free(dim);
1968
1969         return 0;
1970 }
1971
1972 /* Add constraints to graph->lp that force the dependence "map" (which
1973  * is part of the dependence relation of "edge")
1974  * to be respected and attempt to carry it, where the edge is one from
1975  * node j to node k.  "pos" is the sequence number of the given map.
1976  * That is, add constraints that enforce
1977  *
1978  *      (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
1979  *
1980  * for each (x,y) in R.
1981  * We obtain general constraints on coefficients (c_0, c_n, c_x)
1982  * of valid constraints for R and then plug in
1983  * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
1984  * with each coefficient (except e_i, c_k_0 and c_j_0)
1985  * represented as a pair of non-negative coefficients.
1986  */
1987 static int add_inter_constraints(struct isl_sched_graph *graph,
1988         struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
1989 {
1990         unsigned total;
1991         isl_ctx *ctx = isl_map_get_ctx(map);
1992         isl_space *dim;
1993         isl_dim_map *dim_map;
1994         isl_basic_set *coef;
1995         struct isl_sched_node *src = edge->src;
1996         struct isl_sched_node *dst = edge->dst;
1997
1998         coef = inter_coefficients(graph, map);
1999
2000         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2001
2002         total = isl_basic_set_total_dim(graph->lp);
2003         dim_map = isl_dim_map_alloc(ctx, total);
2004
2005         isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2006
2007         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
2008         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
2009         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
2010         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
2011                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2012                           dst->nvar, -1);
2013         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
2014                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2015                           dst->nvar, 1);
2016
2017         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
2018         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
2019         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
2020         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
2021                           isl_space_dim(dim, isl_dim_set), 1,
2022                           src->nvar, 1);
2023         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
2024                           isl_space_dim(dim, isl_dim_set), 1,
2025                           src->nvar, -1);
2026
2027         graph->lp = isl_basic_set_extend_constraints(graph->lp,
2028                         coef->n_eq, coef->n_ineq);
2029         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2030                                                            coef, dim_map);
2031         isl_space_free(dim);
2032
2033         return 0;
2034 }
2035
2036 /* Add constraints to graph->lp that force all dependence
2037  * to be respected and attempt to carry it.
2038  */
2039 static int add_all_constraints(struct isl_sched_graph *graph)
2040 {
2041         int i, j;
2042         int pos;
2043
2044         pos = 0;
2045         for (i = 0; i < graph->n_edge; ++i) {
2046                 struct isl_sched_edge *edge= &graph->edge[i];
2047                 for (j = 0; j < edge->map->n; ++j) {
2048                         isl_basic_map *bmap;
2049                         isl_map *map;
2050
2051                         bmap = isl_basic_map_copy(edge->map->p[j]);
2052                         map = isl_map_from_basic_map(bmap);
2053
2054                         if (edge->src == edge->dst &&
2055                             add_intra_constraints(graph, edge, map, pos) < 0)
2056                                 return -1;
2057                         if (edge->src != edge->dst &&
2058                             add_inter_constraints(graph, edge, map, pos) < 0)
2059                                 return -1;
2060                         ++pos;
2061                 }
2062         }
2063
2064         return 0;
2065 }
2066
2067 /* Count the number of equality and inequality constraints
2068  * that will be added to the carry_lp problem.
2069  * If once is set, then we count
2070  * each edge exactly once.  Otherwise, we count as follows
2071  * validity             -> 1 (>= 0)
2072  * validity+proximity   -> 2 (>= 0 and upper bound)
2073  * proximity            -> 2 (lower and upper bound)
2074  */
2075 static int count_all_constraints(struct isl_sched_graph *graph,
2076         int *n_eq, int *n_ineq, int once)
2077 {
2078         int i, j;
2079
2080         *n_eq = *n_ineq = 0;
2081         for (i = 0; i < graph->n_edge; ++i) {
2082                 struct isl_sched_edge *edge= &graph->edge[i];
2083                 for (j = 0; j < edge->map->n; ++j) {
2084                         isl_basic_map *bmap;
2085                         isl_map *map;
2086
2087                         bmap = isl_basic_map_copy(edge->map->p[j]);
2088                         map = isl_map_from_basic_map(bmap);
2089
2090                         if (count_map_constraints(graph, edge, map,
2091                                                   n_eq, n_ineq, once) < 0)
2092                                     return -1;
2093                 }
2094         }
2095
2096         return 0;
2097 }
2098
2099 /* Construct an LP problem for finding schedule coefficients
2100  * such that the schedule carries as many dependences as possible.
2101  * In particular, for each dependence i, we bound the dependence distance
2102  * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2103  * of all e_i's.  Dependence with e_i = 0 in the solution are simply
2104  * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2105  * Note that if the dependence relation is a union of basic maps,
2106  * then we have to consider each basic map individually as it may only
2107  * be possible to carry the dependences expressed by some of those
2108  * basic maps and not all off them.
2109  * Below, we consider each of those basic maps as a separate "edge".
2110  *
2111  * All variables of the LP are non-negative.  The actual coefficients
2112  * may be negative, so each coefficient is represented as the difference
2113  * of two non-negative variables.  The negative part always appears
2114  * immediately before the positive part.
2115  * Other than that, the variables have the following order
2116  *
2117  *      - sum of (1 - e_i) over all edges
2118  *      - sum of positive and negative parts of all c_n coefficients
2119  *              (unconstrained when computing non-parametric schedules)
2120  *      - sum of positive and negative parts of all c_x coefficients
2121  *      - for each edge
2122  *              - e_i
2123  *      - for each node
2124  *              - c_i_0
2125  *              - positive and negative parts of c_i_n (if parametric)
2126  *              - positive and negative parts of c_i_x
2127  *
2128  * The constraints are those from the edges plus three equalities
2129  * to express the sums and n_edge inequalities to express e_i <= 1.
2130  */
2131 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2132 {
2133         int i, j;
2134         int k;
2135         isl_space *dim;
2136         unsigned total;
2137         int n_eq, n_ineq;
2138         int n_edge;
2139
2140         n_edge = 0;
2141         for (i = 0; i < graph->n_edge; ++i)
2142                 n_edge += graph->edge[i].map->n;
2143
2144         total = 3 + n_edge;
2145         for (i = 0; i < graph->n; ++i) {
2146                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2147                 node->start = total;
2148                 total += 1 + 2 * (node->nparam + node->nvar);
2149         }
2150
2151         if (count_all_constraints(graph, &n_eq, &n_ineq, 1) < 0)
2152                 return -1;
2153
2154         dim = isl_space_set_alloc(ctx, 0, total);
2155         isl_basic_set_free(graph->lp);
2156         n_eq += 3;
2157         n_ineq += n_edge;
2158         graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2159         graph->lp = isl_basic_set_set_rational(graph->lp);
2160
2161         k = isl_basic_set_alloc_equality(graph->lp);
2162         if (k < 0)
2163                 return -1;
2164         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2165         isl_int_set_si(graph->lp->eq[k][0], -n_edge);
2166         isl_int_set_si(graph->lp->eq[k][1], 1);
2167         for (i = 0; i < n_edge; ++i)
2168                 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2169
2170         k = isl_basic_set_alloc_equality(graph->lp);
2171         if (k < 0)
2172                 return -1;
2173         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2174         isl_int_set_si(graph->lp->eq[k][2], -1);
2175         for (i = 0; i < graph->n; ++i) {
2176                 int pos = 1 + graph->node[i].start + 1;
2177
2178                 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2179                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2180         }
2181
2182         k = isl_basic_set_alloc_equality(graph->lp);
2183         if (k < 0)
2184                 return -1;
2185         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2186         isl_int_set_si(graph->lp->eq[k][3], -1);
2187         for (i = 0; i < graph->n; ++i) {
2188                 struct isl_sched_node *node = &graph->node[i];
2189                 int pos = 1 + node->start + 1 + 2 * node->nparam;
2190
2191                 for (j = 0; j < 2 * node->nvar; ++j)
2192                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2193         }
2194
2195         for (i = 0; i < n_edge; ++i) {
2196                 k = isl_basic_set_alloc_inequality(graph->lp);
2197                 if (k < 0)
2198                         return -1;
2199                 isl_seq_clr(graph->lp->ineq[k], 1 +  total);
2200                 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2201                 isl_int_set_si(graph->lp->ineq[k][0], 1);
2202         }
2203
2204         if (add_all_constraints(graph) < 0)
2205                 return -1;
2206
2207         return 0;
2208 }
2209
2210 /* If the schedule_split_parallel option is set and if the linear
2211  * parts of the scheduling rows for all nodes in the graphs are the same,
2212  * then split off the constant term from the linear part.
2213  * The constant term is then placed in a separate band and
2214  * the linear part is simplified.
2215  */
2216 static int split_parallel(isl_ctx *ctx, struct isl_sched_graph *graph)
2217 {
2218         int i;
2219         int equal = 1;
2220         int row, cols;
2221         struct isl_sched_node *node0;
2222
2223         if (!ctx->opt->schedule_split_parallel)
2224                 return 0;
2225         if (graph->n <= 1)
2226                 return 0;
2227
2228         node0 = &graph->node[0];
2229         row = isl_mat_rows(node0->sched) - 1;
2230         cols = isl_mat_cols(node0->sched);
2231         for (i = 1; i < graph->n; ++i) {
2232                 struct isl_sched_node *node = &graph->node[i];
2233
2234                 if (!isl_seq_eq(node0->sched->row[row] + 1,
2235                                 node->sched->row[row] + 1, cols - 1))
2236                         return 0;
2237                 if (equal &&
2238                     isl_int_ne(node0->sched->row[row][0],
2239                                node->sched->row[row][0]))
2240                         equal = 0;
2241         }
2242         if (equal)
2243                 return 0;
2244
2245         next_band(graph);
2246
2247         for (i = 0; i < graph->n; ++i) {
2248                 struct isl_sched_node *node = &graph->node[i];
2249
2250                 isl_map_free(node->sched_map);
2251                 node->sched_map = NULL;
2252                 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2253                 if (!node->sched)
2254                         return -1;
2255                 isl_int_set(node->sched->row[row + 1][0],
2256                             node->sched->row[row][0]);
2257                 isl_int_set_si(node->sched->row[row][0], 0);
2258                 node->sched = isl_mat_normalize_row(node->sched, row);
2259                 if (!node->sched)
2260                         return -1;
2261                 node->band[graph->n_total_row] = graph->n_band;
2262         }
2263
2264         graph->n_total_row++;
2265
2266         return 0;
2267 }
2268
2269 /* Construct a schedule row for each node such that as many dependences
2270  * as possible are carried and then continue with the next band.
2271  */
2272 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2273 {
2274         int i;
2275         int n_edge;
2276         isl_vec *sol;
2277         isl_basic_set *lp;
2278
2279         n_edge = 0;
2280         for (i = 0; i < graph->n_edge; ++i)
2281                 n_edge += graph->edge[i].map->n;
2282
2283         if (setup_carry_lp(ctx, graph) < 0)
2284                 return -1;
2285
2286         lp = isl_basic_set_copy(graph->lp);
2287         sol = isl_tab_basic_set_non_neg_lexmin(lp);
2288         if (!sol)
2289                 return -1;
2290
2291         if (sol->size == 0) {
2292                 isl_vec_free(sol);
2293                 isl_die(ctx, isl_error_internal,
2294                         "error in schedule construction", return -1);
2295         }
2296
2297         if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
2298                 isl_vec_free(sol);
2299                 isl_die(ctx, isl_error_unknown,
2300                         "unable to carry dependences", return -1);
2301         }
2302
2303         if (update_schedule(graph, sol, 0, 0) < 0)
2304                 return -1;
2305
2306         if (split_parallel(ctx, graph) < 0)
2307                 return -1;
2308
2309         return compute_next_band(ctx, graph);
2310 }
2311
2312 /* Compute a schedule for a connected dependence graph.
2313  * We try to find a sequence of as many schedule rows as possible that result
2314  * in non-negative dependence distances (independent of the previous rows
2315  * in the sequence, i.e., such that the sequence is tilable).
2316  * If we can't find any more rows we either
2317  * - split between SCCs and start over (assuming we found an interesting
2318  *      pair of SCCs between which to split)
2319  * - continue with the next band (assuming the current band has at least
2320  *      one row)
2321  * - try to carry as many dependences as possible and continue with the next
2322  *      band
2323  *
2324  * If we manage to complete the schedule, we finish off by topologically
2325  * sorting the statements based on the remaining dependences.
2326  *
2327  * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2328  * outermost dimension in the current band to be zero distance.  If this
2329  * turns out to be impossible, we fall back on the general scheme above
2330  * and try to carry as many dependences as possible.
2331  */
2332 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2333 {
2334         int force_zero = 0;
2335
2336         if (detect_sccs(graph) < 0)
2337                 return -1;
2338         sort_sccs(graph);
2339
2340         if (compute_maxvar(graph) < 0)
2341                 return -1;
2342
2343         if (ctx->opt->schedule_outer_zero_distance)
2344                 force_zero = 1;
2345
2346         while (graph->n_row < graph->maxvar) {
2347                 isl_vec *sol;
2348
2349                 graph->src_scc = -1;
2350                 graph->dst_scc = -1;
2351
2352                 if (setup_lp(ctx, graph, force_zero) < 0)
2353                         return -1;
2354                 sol = solve_lp(graph);
2355                 if (!sol)
2356                         return -1;
2357                 if (sol->size == 0) {
2358                         isl_vec_free(sol);
2359                         if (!ctx->opt->schedule_maximize_band_depth &&
2360                             graph->n_total_row > graph->band_start)
2361                                 return compute_next_band(ctx, graph);
2362                         if (graph->src_scc >= 0)
2363                                 return compute_split_schedule(ctx, graph);
2364                         if (graph->n_total_row > graph->band_start)
2365                                 return compute_next_band(ctx, graph);
2366                         return carry_dependences(ctx, graph);
2367                 }
2368                 if (update_schedule(graph, sol, 1, 1) < 0)
2369                         return -1;
2370                 force_zero = 0;
2371         }
2372
2373         if (graph->n_total_row > graph->band_start)
2374                 next_band(graph);
2375         return sort_statements(ctx, graph);
2376 }
2377
2378 /* Compute a schedule for each component (identified by node->scc)
2379  * of the dependence graph separately and then combine the results.
2380  *
2381  * The band_id is adjusted such that each component has a separate id.
2382  * Note that the band_id may have already been set to a value different
2383  * from zero by compute_split_schedule.
2384  */
2385 static int compute_component_schedule(isl_ctx *ctx,
2386         struct isl_sched_graph *graph)
2387 {
2388         int wcc, i;
2389         int n, n_edge;
2390         int n_total_row, orig_total_row;
2391         int n_band, orig_band;
2392
2393         n_total_row = 0;
2394         orig_total_row = graph->n_total_row;
2395         n_band = 0;
2396         orig_band = graph->n_band;
2397         for (i = 0; i < graph->n; ++i)
2398                 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2399         for (wcc = 0; wcc < graph->scc; ++wcc) {
2400                 n = 0;
2401                 for (i = 0; i < graph->n; ++i)
2402                         if (graph->node[i].scc == wcc)
2403                                 n++;
2404                 n_edge = 0;
2405                 for (i = 0; i < graph->n_edge; ++i)
2406                         if (graph->edge[i].src->scc == wcc)
2407                                 n_edge++;
2408
2409                 if (compute_sub_schedule(ctx, graph, n, n_edge,
2410                                     &node_scc_exactly,
2411                                     &edge_src_scc_exactly, wcc, 1) < 0)
2412                         return -1;
2413                 if (graph->n_total_row > n_total_row)
2414                         n_total_row = graph->n_total_row;
2415                 graph->n_total_row = orig_total_row;
2416                 if (graph->n_band > n_band)
2417                         n_band = graph->n_band;
2418                 graph->n_band = orig_band;
2419         }
2420
2421         graph->n_total_row = n_total_row;
2422         graph->n_band = n_band;
2423
2424         return pad_schedule(graph);
2425 }
2426
2427 /* Compute a schedule for the given dependence graph.
2428  * We first check if the graph is connected (through validity dependences)
2429  * and, if not, compute a schedule for each component separately.
2430  */
2431 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2432 {
2433         if (detect_wccs(graph) < 0)
2434                 return -1;
2435
2436         if (graph->scc > 1)
2437                 return compute_component_schedule(ctx, graph);
2438
2439         return compute_schedule_wcc(ctx, graph);
2440 }
2441
2442 /* Compute a schedule for the given union of domains that respects
2443  * all the validity dependences and tries to minimize the dependence
2444  * distances over the proximity dependences.
2445  */
2446 __isl_give isl_schedule *isl_union_set_compute_schedule(
2447         __isl_take isl_union_set *domain,
2448         __isl_take isl_union_map *validity,
2449         __isl_take isl_union_map *proximity)
2450 {
2451         isl_ctx *ctx = isl_union_set_get_ctx(domain);
2452         isl_space *dim;
2453         struct isl_sched_graph graph = { 0 };
2454         isl_schedule *sched;
2455
2456         domain = isl_union_set_align_params(domain,
2457                                             isl_union_map_get_space(validity));
2458         domain = isl_union_set_align_params(domain,
2459                                             isl_union_map_get_space(proximity));
2460         dim = isl_union_set_get_space(domain);
2461         validity = isl_union_map_align_params(validity, isl_space_copy(dim));
2462         proximity = isl_union_map_align_params(proximity, dim);
2463
2464         if (!domain)
2465                 goto error;
2466
2467         graph.n = isl_union_set_n_set(domain);
2468         if (graph.n == 0)
2469                 goto empty;
2470         if (graph_alloc(ctx, &graph, graph.n,
2471             isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2472                 goto error;
2473         graph.root = 1;
2474         graph.n = 0;
2475         if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2476                 goto error;
2477         if (graph_init_table(ctx, &graph) < 0)
2478                 goto error;
2479         graph.n_edge = 0;
2480         if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0)
2481                 goto error;
2482         if (graph_init_edge_table(ctx, &graph) < 0)
2483                 goto error;
2484         if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0)
2485                 goto error;
2486
2487         if (compute_schedule(ctx, &graph) < 0)
2488                 goto error;
2489
2490 empty:
2491         sched = extract_schedule(&graph, isl_union_set_get_space(domain));
2492
2493         graph_free(ctx, &graph);
2494         isl_union_set_free(domain);
2495         isl_union_map_free(validity);
2496         isl_union_map_free(proximity);
2497
2498         return sched;
2499 error:
2500         graph_free(ctx, &graph);
2501         isl_union_set_free(domain);
2502         isl_union_map_free(validity);
2503         isl_union_map_free(proximity);
2504         return NULL;
2505 }
2506
2507 void *isl_schedule_free(__isl_take isl_schedule *sched)
2508 {
2509         int i;
2510         if (!sched)
2511                 return NULL;
2512
2513         if (--sched->ref > 0)
2514                 return NULL;
2515
2516         for (i = 0; i < sched->n; ++i) {
2517                 isl_map_free(sched->node[i].sched);
2518                 free(sched->node[i].band_end);
2519                 free(sched->node[i].band_id);
2520                 free(sched->node[i].zero);
2521         }
2522         isl_space_free(sched->dim);
2523         isl_band_list_free(sched->band_forest);
2524         free(sched);
2525         return NULL;
2526 }
2527
2528 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2529 {
2530         return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
2531 }
2532
2533 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2534 {
2535         int i;
2536         isl_union_map *umap;
2537
2538         if (!sched)
2539                 return NULL;
2540
2541         umap = isl_union_map_empty(isl_space_copy(sched->dim));
2542         for (i = 0; i < sched->n; ++i)
2543                 umap = isl_union_map_add_map(umap,
2544                                             isl_map_copy(sched->node[i].sched));
2545
2546         return umap;
2547 }
2548
2549 static __isl_give isl_band_list *construct_band_list(
2550         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2551         int band_nr, int *parent_active, int n_active);
2552
2553 /* Construct an isl_band structure for the band in the given schedule
2554  * with sequence number band_nr for the n_active nodes marked by active.
2555  * If the nodes don't have a band with the given sequence number,
2556  * then a band without members is created.
2557  *
2558  * Because of the way the schedule is constructed, we know that
2559  * the position of the band inside the schedule of a node is the same
2560  * for all active nodes.
2561  */
2562 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2563         __isl_keep isl_band *parent,
2564         int band_nr, int *active, int n_active)
2565 {
2566         int i, j;
2567         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2568         isl_band *band;
2569         unsigned start, end;
2570
2571         band = isl_calloc_type(ctx, isl_band);
2572         if (!band)
2573                 return NULL;
2574
2575         band->ref = 1;
2576         band->schedule = schedule;
2577         band->parent = parent;
2578
2579         for (i = 0; i < schedule->n; ++i)
2580                 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2581                         break;
2582
2583         if (i < schedule->n) {
2584                 band->children = construct_band_list(schedule, band,
2585                                                 band_nr + 1, active, n_active);
2586                 if (!band->children)
2587                         goto error;
2588         }
2589
2590         for (i = 0; i < schedule->n; ++i)
2591                 if (active[i])
2592                         break;
2593
2594         if (i >= schedule->n)
2595                 isl_die(ctx, isl_error_internal,
2596                         "band without active statements", goto error);
2597
2598         start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2599         end = band_nr < schedule->node[i].n_band ?
2600                 schedule->node[i].band_end[band_nr] : start;
2601         band->n = end - start;
2602
2603         band->zero = isl_alloc_array(ctx, int, band->n);
2604         if (!band->zero)
2605                 goto error;
2606
2607         for (j = 0; j < band->n; ++j)
2608                 band->zero[j] = schedule->node[i].zero[start + j];
2609
2610         band->map = isl_union_map_empty(isl_space_copy(schedule->dim));
2611         for (i = 0; i < schedule->n; ++i) {
2612                 isl_map *map;
2613                 unsigned n_out;
2614
2615                 if (!active[i])
2616                         continue;
2617
2618                 map = isl_map_copy(schedule->node[i].sched);
2619                 n_out = isl_map_dim(map, isl_dim_out);
2620                 map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
2621                 map = isl_map_project_out(map, isl_dim_out, 0, start);
2622                 band->map = isl_union_map_union(band->map,
2623                                                 isl_union_map_from_map(map));
2624         }
2625         if (!band->map)
2626                 goto error;
2627
2628         return band;
2629 error:
2630         isl_band_free(band);
2631         return NULL;
2632 }
2633
2634 /* Construct a list of bands that start at the same position (with
2635  * sequence number band_nr) in the schedules of the nodes that
2636  * were active in the parent band.
2637  *
2638  * A separate isl_band structure is created for each band_id
2639  * and for each node that does not have a band with sequence
2640  * number band_nr.  In the latter case, a band without members
2641  * is created.
2642  * This ensures that if a band has any children, then each node
2643  * that was active in the band is active in exactly one of the children.
2644  */
2645 static __isl_give isl_band_list *construct_band_list(
2646         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2647         int band_nr, int *parent_active, int n_active)
2648 {
2649         int i, j;
2650         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2651         int *active;
2652         int n_band;
2653         isl_band_list *list;
2654
2655         n_band = 0;
2656         for (i = 0; i < n_active; ++i) {
2657                 for (j = 0; j < schedule->n; ++j) {
2658                         if (!parent_active[j])
2659                                 continue;
2660                         if (schedule->node[j].n_band <= band_nr)
2661                                 continue;
2662                         if (schedule->node[j].band_id[band_nr] == i) {
2663                                 n_band++;
2664                                 break;
2665                         }
2666                 }
2667         }
2668         for (j = 0; j < schedule->n; ++j)
2669                 if (schedule->node[j].n_band <= band_nr)
2670                         n_band++;
2671
2672         if (n_band == 1) {
2673                 isl_band *band;
2674                 list = isl_band_list_alloc(ctx, n_band);
2675                 band = construct_band(schedule, parent, band_nr,
2676                                         parent_active, n_active);
2677                 return isl_band_list_add(list, band);
2678         }
2679
2680         active = isl_alloc_array(ctx, int, schedule->n);
2681         if (!active)
2682                 return NULL;
2683
2684         list = isl_band_list_alloc(ctx, n_band);
2685
2686         for (i = 0; i < n_active; ++i) {
2687                 int n = 0;
2688                 isl_band *band;
2689
2690                 for (j = 0; j < schedule->n; ++j) {
2691                         active[j] = parent_active[j] &&
2692                                         schedule->node[j].n_band > band_nr &&
2693                                         schedule->node[j].band_id[band_nr] == i;
2694                         if (active[j])
2695                                 n++;
2696                 }
2697                 if (n == 0)
2698                         continue;
2699
2700                 band = construct_band(schedule, parent, band_nr, active, n);
2701
2702                 list = isl_band_list_add(list, band);
2703         }
2704         for (i = 0; i < schedule->n; ++i) {
2705                 isl_band *band;
2706                 if (!parent_active[i])
2707                         continue;
2708                 if (schedule->node[i].n_band > band_nr)
2709                         continue;
2710                 for (j = 0; j < schedule->n; ++j)
2711                         active[j] = j == i;
2712                 band = construct_band(schedule, parent, band_nr, active, 1);
2713                 list = isl_band_list_add(list, band);
2714         }
2715
2716         free(active);
2717
2718         return list;
2719 }
2720
2721 /* Construct a band forest representation of the schedule and
2722  * return the list of roots.
2723  */
2724 static __isl_give isl_band_list *construct_forest(
2725         __isl_keep isl_schedule *schedule)
2726 {
2727         int i;
2728         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2729         isl_band_list *forest;
2730         int *active;
2731
2732         active = isl_alloc_array(ctx, int, schedule->n);
2733         if (!active)
2734                 return NULL;
2735
2736         for (i = 0; i < schedule->n; ++i)
2737                 active[i] = 1;
2738
2739         forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
2740
2741         free(active);
2742
2743         return forest;
2744 }
2745
2746 /* Return the roots of a band forest representation of the schedule.
2747  */
2748 __isl_give isl_band_list *isl_schedule_get_band_forest(
2749         __isl_keep isl_schedule *schedule)
2750 {
2751         if (!schedule)
2752                 return NULL;
2753         if (!schedule->band_forest)
2754                 schedule->band_forest = construct_forest(schedule);
2755         return isl_band_list_dup(schedule->band_forest);
2756 }
2757
2758 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2759         __isl_keep isl_band_list *list);
2760
2761 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
2762         __isl_keep isl_band *band)
2763 {
2764         isl_band_list *children;
2765
2766         p = isl_printer_start_line(p);
2767         p = isl_printer_print_union_map(p, band->map);
2768         p = isl_printer_end_line(p);
2769
2770         if (!isl_band_has_children(band))
2771                 return p;
2772
2773         children = isl_band_get_children(band);
2774
2775         p = isl_printer_indent(p, 4);
2776         p = print_band_list(p, children);
2777         p = isl_printer_indent(p, -4);
2778
2779         isl_band_list_free(children);
2780
2781         return p;
2782 }
2783
2784 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2785         __isl_keep isl_band_list *list)
2786 {
2787         int i, n;
2788
2789         n = isl_band_list_n_band(list);
2790         for (i = 0; i < n; ++i) {
2791                 isl_band *band;
2792                 band = isl_band_list_get_band(list, i);
2793                 p = print_band(p, band);
2794                 isl_band_free(band);
2795         }
2796
2797         return p;
2798 }
2799
2800 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
2801         __isl_keep isl_schedule *schedule)
2802 {
2803         isl_band_list *forest;
2804
2805         forest = isl_schedule_get_band_forest(schedule);
2806
2807         p = print_band_list(p, forest);
2808
2809         isl_band_list_free(forest);
2810
2811         return p;
2812 }
2813
2814 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
2815 {
2816         isl_printer *printer;
2817
2818         if (!schedule)
2819                 return;
2820
2821         printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
2822         printer = isl_printer_print_schedule(printer, schedule);
2823
2824         isl_printer_free(printer);
2825 }