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         int max_constant_term;
1143
1144         max_constant_term = ctx->opt->schedule_max_constant_term;
1145
1146         parametric = ctx->opt->schedule_parametric;
1147         nparam = isl_space_dim(graph->node[0].dim, isl_dim_param);
1148         param_pos = 4;
1149         total = param_pos + 2 * nparam;
1150         for (i = 0; i < graph->n; ++i) {
1151                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
1152                 if (node_update_cmap(node) < 0)
1153                         return -1;
1154                 node->start = total;
1155                 total += 1 + 2 * (node->nparam + node->nvar);
1156         }
1157
1158         if (count_constraints(graph, &n_eq, &n_ineq, 0) < 0)
1159                 return -1;
1160
1161         dim = isl_space_set_alloc(ctx, 0, total);
1162         isl_basic_set_free(graph->lp);
1163         n_eq += 2 + parametric + force_zero;
1164         if (max_constant_term != -1)
1165                 n_ineq += graph->n;
1166
1167         graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
1168
1169         k = isl_basic_set_alloc_equality(graph->lp);
1170         if (k < 0)
1171                 return -1;
1172         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1173         if (!force_zero)
1174                 isl_int_set_si(graph->lp->eq[k][1], -1);
1175         for (i = 0; i < 2 * nparam; ++i)
1176                 isl_int_set_si(graph->lp->eq[k][1 + param_pos + i], 1);
1177
1178         if (force_zero) {
1179                 k = isl_basic_set_alloc_equality(graph->lp);
1180                 if (k < 0)
1181                         return -1;
1182                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1183                 isl_int_set_si(graph->lp->eq[k][2], -1);
1184         }
1185
1186         if (parametric) {
1187                 k = isl_basic_set_alloc_equality(graph->lp);
1188                 if (k < 0)
1189                         return -1;
1190                 isl_seq_clr(graph->lp->eq[k], 1 +  total);
1191                 isl_int_set_si(graph->lp->eq[k][3], -1);
1192                 for (i = 0; i < graph->n; ++i) {
1193                         int pos = 1 + graph->node[i].start + 1;
1194
1195                         for (j = 0; j < 2 * graph->node[i].nparam; ++j)
1196                                 isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1197                 }
1198         }
1199
1200         k = isl_basic_set_alloc_equality(graph->lp);
1201         if (k < 0)
1202                 return -1;
1203         isl_seq_clr(graph->lp->eq[k], 1 +  total);
1204         isl_int_set_si(graph->lp->eq[k][4], -1);
1205         for (i = 0; i < graph->n; ++i) {
1206                 struct isl_sched_node *node = &graph->node[i];
1207                 int pos = 1 + node->start + 1 + 2 * node->nparam;
1208
1209                 for (j = 0; j < 2 * node->nvar; ++j)
1210                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
1211         }
1212
1213         if (max_constant_term != -1)
1214                 for (i = 0; i < graph->n; ++i) {
1215                         struct isl_sched_node *node = &graph->node[i];
1216                         k = isl_basic_set_alloc_inequality(graph->lp);
1217                         if (k < 0)
1218                                 return -1;
1219                         isl_seq_clr(graph->lp->ineq[k], 1 +  total);
1220                         isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1);
1221                         isl_int_set_si(graph->lp->ineq[k][0], max_constant_term);
1222                 }
1223
1224         if (add_all_validity_constraints(graph) < 0)
1225                 return -1;
1226         if (add_all_proximity_constraints(graph) < 0)
1227                 return -1;
1228
1229         return 0;
1230 }
1231
1232 /* Analyze the conflicting constraint found by
1233  * isl_tab_basic_set_non_trivial_lexmin.  If it corresponds to the validity
1234  * constraint of one of the edges between distinct nodes, living, moreover
1235  * in distinct SCCs, then record the source and sink SCC as this may
1236  * be a good place to cut between SCCs.
1237  */
1238 static int check_conflict(int con, void *user)
1239 {
1240         int i;
1241         struct isl_sched_graph *graph = user;
1242
1243         if (graph->src_scc >= 0)
1244                 return 0;
1245
1246         con -= graph->lp->n_eq;
1247
1248         if (con >= graph->lp->n_ineq)
1249                 return 0;
1250
1251         for (i = 0; i < graph->n_edge; ++i) {
1252                 if (!graph->edge[i].validity)
1253                         continue;
1254                 if (graph->edge[i].src == graph->edge[i].dst)
1255                         continue;
1256                 if (graph->edge[i].src->scc == graph->edge[i].dst->scc)
1257                         continue;
1258                 if (graph->edge[i].start > con)
1259                         continue;
1260                 if (graph->edge[i].end <= con)
1261                         continue;
1262                 graph->src_scc = graph->edge[i].src->scc;
1263                 graph->dst_scc = graph->edge[i].dst->scc;
1264         }
1265
1266         return 0;
1267 }
1268
1269 /* Check whether the next schedule row of the given node needs to be
1270  * non-trivial.  Lower-dimensional domains may have some trivial rows,
1271  * but as soon as the number of remaining required non-trivial rows
1272  * is as large as the number or remaining rows to be computed,
1273  * all remaining rows need to be non-trivial.
1274  */
1275 static int needs_row(struct isl_sched_graph *graph, struct isl_sched_node *node)
1276 {
1277         return node->nvar - node->rank >= graph->maxvar - graph->n_row;
1278 }
1279
1280 /* Solve the ILP problem constructed in setup_lp.
1281  * For each node such that all the remaining rows of its schedule
1282  * need to be non-trivial, we construct a non-triviality region.
1283  * This region imposes that the next row is independent of previous rows.
1284  * In particular the coefficients c_i_x are represented by t_i_x
1285  * variables with c_i_x = Q t_i_x and Q a unimodular matrix such that
1286  * its first columns span the rows of the previously computed part
1287  * of the schedule.  The non-triviality region enforces that at least
1288  * one of the remaining components of t_i_x is non-zero, i.e.,
1289  * that the new schedule row depends on at least one of the remaining
1290  * columns of Q.
1291  */
1292 static __isl_give isl_vec *solve_lp(struct isl_sched_graph *graph)
1293 {
1294         int i;
1295         isl_vec *sol;
1296         isl_basic_set *lp;
1297
1298         for (i = 0; i < graph->n; ++i) {
1299                 struct isl_sched_node *node = &graph->node[i];
1300                 int skip = node->rank;
1301                 graph->region[i].pos = node->start + 1 + 2*(node->nparam+skip);
1302                 if (needs_row(graph, node))
1303                         graph->region[i].len = 2 * (node->nvar - skip);
1304                 else
1305                         graph->region[i].len = 0;
1306         }
1307         lp = isl_basic_set_copy(graph->lp);
1308         sol = isl_tab_basic_set_non_trivial_lexmin(lp, 2, graph->n,
1309                                        graph->region, &check_conflict, graph);
1310         return sol;
1311 }
1312
1313 /* Update the schedules of all nodes based on the given solution
1314  * of the LP problem.
1315  * The new row is added to the current band.
1316  * All possibly negative coefficients are encoded as a difference
1317  * of two non-negative variables, so we need to perform the subtraction
1318  * here.  Moreover, if use_cmap is set, then the solution does
1319  * not refer to the actual coefficients c_i_x, but instead to variables
1320  * t_i_x such that c_i_x = Q t_i_x and Q is equal to node->cmap.
1321  * In this case, we then also need to perform this multiplication
1322  * to obtain the values of c_i_x.
1323  *
1324  * If check_zero is set, then the first two coordinates of sol are
1325  * assumed to correspond to the dependence distance.  If these two
1326  * coordinates are zero, then the corresponding scheduling dimension
1327  * is marked as being zero distance.
1328  */
1329 static int update_schedule(struct isl_sched_graph *graph,
1330         __isl_take isl_vec *sol, int use_cmap, int check_zero)
1331 {
1332         int i, j;
1333         int zero = 0;
1334         isl_vec *csol = NULL;
1335
1336         if (!sol)
1337                 goto error;
1338         if (sol->size == 0)
1339                 isl_die(sol->ctx, isl_error_internal,
1340                         "no solution found", goto error);
1341
1342         if (check_zero)
1343                 zero = isl_int_is_zero(sol->el[1]) &&
1344                            isl_int_is_zero(sol->el[2]);
1345
1346         for (i = 0; i < graph->n; ++i) {
1347                 struct isl_sched_node *node = &graph->node[i];
1348                 int pos = node->start;
1349                 int row = isl_mat_rows(node->sched);
1350
1351                 isl_vec_free(csol);
1352                 csol = isl_vec_alloc(sol->ctx, node->nvar);
1353                 if (!csol)
1354                         goto error;
1355
1356                 isl_map_free(node->sched_map);
1357                 node->sched_map = NULL;
1358                 node->sched = isl_mat_add_rows(node->sched, 1);
1359                 if (!node->sched)
1360                         goto error;
1361                 node->sched = isl_mat_set_element(node->sched, row, 0,
1362                                                   sol->el[1 + pos]);
1363                 for (j = 0; j < node->nparam + node->nvar; ++j)
1364                         isl_int_sub(sol->el[1 + pos + 1 + 2 * j + 1],
1365                                     sol->el[1 + pos + 1 + 2 * j + 1],
1366                                     sol->el[1 + pos + 1 + 2 * j]);
1367                 for (j = 0; j < node->nparam; ++j)
1368                         node->sched = isl_mat_set_element(node->sched,
1369                                         row, 1 + j, sol->el[1+pos+1+2*j+1]);
1370                 for (j = 0; j < node->nvar; ++j)
1371                         isl_int_set(csol->el[j],
1372                                     sol->el[1+pos+1+2*(node->nparam+j)+1]);
1373                 if (use_cmap)
1374                         csol = isl_mat_vec_product(isl_mat_copy(node->cmap),
1375                                                    csol);
1376                 if (!csol)
1377                         goto error;
1378                 for (j = 0; j < node->nvar; ++j)
1379                         node->sched = isl_mat_set_element(node->sched,
1380                                         row, 1 + node->nparam + j, csol->el[j]);
1381                 node->band[graph->n_total_row] = graph->n_band;
1382                 node->zero[graph->n_total_row] = zero;
1383         }
1384         isl_vec_free(sol);
1385         isl_vec_free(csol);
1386
1387         graph->n_row++;
1388         graph->n_total_row++;
1389
1390         return 0;
1391 error:
1392         isl_vec_free(sol);
1393         isl_vec_free(csol);
1394         return -1;
1395 }
1396
1397 /* Convert node->sched into a map and return this map.
1398  * We simply add equality constraints that express each output variable
1399  * as the affine combination of parameters and input variables specified
1400  * by the schedule matrix.
1401  *
1402  * The result is cached in node->sched_map, which needs to be released
1403  * whenever node->sched is updated.
1404  */
1405 static __isl_give isl_map *node_extract_schedule(struct isl_sched_node *node)
1406 {
1407         int i, j;
1408         isl_space *dim;
1409         isl_local_space *ls;
1410         isl_basic_map *bmap;
1411         isl_constraint *c;
1412         int nrow, ncol;
1413         isl_int v;
1414
1415         if (node->sched_map)
1416                 return isl_map_copy(node->sched_map);
1417
1418         nrow = isl_mat_rows(node->sched);
1419         ncol = isl_mat_cols(node->sched) - 1;
1420         dim = isl_space_from_domain(isl_space_copy(node->dim));
1421         dim = isl_space_add_dims(dim, isl_dim_out, nrow);
1422         bmap = isl_basic_map_universe(isl_space_copy(dim));
1423         ls = isl_local_space_from_space(dim);
1424
1425         isl_int_init(v);
1426
1427         for (i = 0; i < nrow; ++i) {
1428                 c = isl_equality_alloc(isl_local_space_copy(ls));
1429                 isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
1430                 isl_mat_get_element(node->sched, i, 0, &v);
1431                 isl_constraint_set_constant(c, v);
1432                 for (j = 0; j < node->nparam; ++j) {
1433                         isl_mat_get_element(node->sched, i, 1 + j, &v);
1434                         isl_constraint_set_coefficient(c, isl_dim_param, j, v);
1435                 }
1436                 for (j = 0; j < node->nvar; ++j) {
1437                         isl_mat_get_element(node->sched,
1438                                             i, 1 + node->nparam + j, &v);
1439                         isl_constraint_set_coefficient(c, isl_dim_in, j, v);
1440                 }
1441                 bmap = isl_basic_map_add_constraint(bmap, c);
1442         }
1443
1444         isl_int_clear(v);
1445
1446         isl_local_space_free(ls);
1447
1448         node->sched_map = isl_map_from_basic_map(bmap);
1449         return isl_map_copy(node->sched_map);
1450 }
1451
1452 /* Update the given dependence relation based on the current schedule.
1453  * That is, intersect the dependence relation with a map expressing
1454  * that source and sink are executed within the same iteration of
1455  * the current schedule.
1456  * This is not the most efficient way, but this shouldn't be a critical
1457  * operation.
1458  */
1459 static __isl_give isl_map *specialize(__isl_take isl_map *map,
1460         struct isl_sched_node *src, struct isl_sched_node *dst)
1461 {
1462         isl_map *src_sched, *dst_sched, *id;
1463
1464         src_sched = node_extract_schedule(src);
1465         dst_sched = node_extract_schedule(dst);
1466         id = isl_map_apply_range(src_sched, isl_map_reverse(dst_sched));
1467         return isl_map_intersect(map, id);
1468 }
1469
1470 /* Update the dependence relations of all edges based on the current schedule.
1471  * If a dependence is carried completely by the current schedule, then
1472  * it is removed and edge_table is updated accordingly.
1473  */
1474 static int update_edges(isl_ctx *ctx, struct isl_sched_graph *graph)
1475 {
1476         int i;
1477         int reset_table = 0;
1478
1479         for (i = graph->n_edge - 1; i >= 0; --i) {
1480                 struct isl_sched_edge *edge = &graph->edge[i];
1481                 edge->map = specialize(edge->map, edge->src, edge->dst);
1482                 if (!edge->map)
1483                         return -1;
1484
1485                 if (isl_map_plain_is_empty(edge->map)) {
1486                         reset_table = 1;
1487                         isl_map_free(edge->map);
1488                         if (i != graph->n_edge - 1)
1489                                 graph->edge[i] = graph->edge[graph->n_edge - 1];
1490                         graph->n_edge--;
1491                 }
1492         }
1493
1494         if (reset_table) {
1495                 isl_hash_table_free(ctx, graph->edge_table);
1496                 graph->edge_table = NULL;
1497                 return graph_init_edge_table(ctx, graph);
1498         }
1499
1500         return 0;
1501 }
1502
1503 static void next_band(struct isl_sched_graph *graph)
1504 {
1505         graph->band_start = graph->n_total_row;
1506         graph->n_band++;
1507 }
1508
1509 /* Topologically sort statements mapped to same schedule iteration
1510  * and add a row to the schedule corresponding to this order.
1511  */
1512 static int sort_statements(isl_ctx *ctx, struct isl_sched_graph *graph)
1513 {
1514         int i, j;
1515
1516         if (graph->n <= 1)
1517                 return 0;
1518
1519         if (update_edges(ctx, graph) < 0)
1520                 return -1;
1521
1522         if (graph->n_edge == 0)
1523                 return 0;
1524
1525         if (detect_sccs(graph) < 0)
1526                 return -1;
1527
1528         for (i = 0; i < graph->n; ++i) {
1529                 struct isl_sched_node *node = &graph->node[i];
1530                 int row = isl_mat_rows(node->sched);
1531                 int cols = isl_mat_cols(node->sched);
1532
1533                 isl_map_free(node->sched_map);
1534                 node->sched_map = NULL;
1535                 node->sched = isl_mat_add_rows(node->sched, 1);
1536                 if (!node->sched)
1537                         return -1;
1538                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1539                                                      node->scc);
1540                 for (j = 1; j < cols; ++j)
1541                         node->sched = isl_mat_set_element_si(node->sched,
1542                                                              row, j, 0);
1543                 node->band[graph->n_total_row] = graph->n_band;
1544         }
1545
1546         graph->n_total_row++;
1547         next_band(graph);
1548
1549         return 0;
1550 }
1551
1552 /* Construct an isl_schedule based on the computed schedule stored
1553  * in graph and with parameters specified by dim.
1554  */
1555 static __isl_give isl_schedule *extract_schedule(struct isl_sched_graph *graph,
1556         __isl_take isl_space *dim)
1557 {
1558         int i;
1559         isl_ctx *ctx;
1560         isl_schedule *sched = NULL;
1561
1562         if (!dim)
1563                 return NULL;
1564
1565         ctx = isl_space_get_ctx(dim);
1566         sched = isl_calloc(ctx, struct isl_schedule,
1567                            sizeof(struct isl_schedule) +
1568                            (graph->n - 1) * sizeof(struct isl_schedule_node));
1569         if (!sched)
1570                 goto error;
1571
1572         sched->ref = 1;
1573         sched->n = graph->n;
1574         sched->n_band = graph->n_band;
1575         sched->n_total_row = graph->n_total_row;
1576
1577         for (i = 0; i < sched->n; ++i) {
1578                 int r, b;
1579                 int *band_end, *band_id, *zero;
1580
1581                 band_end = isl_alloc_array(ctx, int, graph->n_band);
1582                 band_id = isl_alloc_array(ctx, int, graph->n_band);
1583                 zero = isl_alloc_array(ctx, int, graph->n_total_row);
1584                 sched->node[i].sched = node_extract_schedule(&graph->node[i]);
1585                 sched->node[i].band_end = band_end;
1586                 sched->node[i].band_id = band_id;
1587                 sched->node[i].zero = zero;
1588                 if (!band_end || !band_id || !zero)
1589                         goto error;
1590
1591                 for (r = 0; r < graph->n_total_row; ++r)
1592                         zero[r] = graph->node[i].zero[r];
1593                 for (r = b = 0; r < graph->n_total_row; ++r) {
1594                         if (graph->node[i].band[r] == b)
1595                                 continue;
1596                         band_end[b++] = r;
1597                         if (graph->node[i].band[r] == -1)
1598                                 break;
1599                 }
1600                 if (r == graph->n_total_row)
1601                         band_end[b++] = r;
1602                 sched->node[i].n_band = b;
1603                 for (--b; b >= 0; --b)
1604                         band_id[b] = graph->node[i].band_id[b];
1605         }
1606
1607         sched->dim = dim;
1608
1609         return sched;
1610 error:
1611         isl_space_free(dim);
1612         isl_schedule_free(sched);
1613         return NULL;
1614 }
1615
1616 /* Copy nodes that satisfy node_pred from the src dependence graph
1617  * to the dst dependence graph.
1618  */
1619 static int copy_nodes(struct isl_sched_graph *dst, struct isl_sched_graph *src,
1620         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1621 {
1622         int i;
1623
1624         dst->n = 0;
1625         for (i = 0; i < src->n; ++i) {
1626                 if (!node_pred(&src->node[i], data))
1627                         continue;
1628                 dst->node[dst->n].dim = isl_space_copy(src->node[i].dim);
1629                 dst->node[dst->n].nvar = src->node[i].nvar;
1630                 dst->node[dst->n].nparam = src->node[i].nparam;
1631                 dst->node[dst->n].sched = isl_mat_copy(src->node[i].sched);
1632                 dst->node[dst->n].sched_map =
1633                         isl_map_copy(src->node[i].sched_map);
1634                 dst->node[dst->n].band = src->node[i].band;
1635                 dst->node[dst->n].band_id = src->node[i].band_id;
1636                 dst->node[dst->n].zero = src->node[i].zero;
1637                 dst->n++;
1638         }
1639
1640         return 0;
1641 }
1642
1643 /* Copy non-empty edges that satisfy edge_pred from the src dependence graph
1644  * to the dst dependence graph.
1645  * If the source or destination node of the edge is not in the destination
1646  * graph, then it must be a backward proximity edge and it should simply
1647  * be ignored.
1648  */
1649 static int copy_edges(isl_ctx *ctx, struct isl_sched_graph *dst,
1650         struct isl_sched_graph *src,
1651         int (*edge_pred)(struct isl_sched_edge *edge, int data), int data)
1652 {
1653         int i;
1654
1655         dst->n_edge = 0;
1656         for (i = 0; i < src->n_edge; ++i) {
1657                 struct isl_sched_edge *edge = &src->edge[i];
1658                 isl_map *map;
1659                 struct isl_sched_node *dst_src, *dst_dst;
1660
1661                 if (!edge_pred(edge, data))
1662                         continue;
1663
1664                 if (isl_map_plain_is_empty(edge->map))
1665                         continue;
1666
1667                 dst_src = graph_find_node(ctx, dst, edge->src->dim);
1668                 dst_dst = graph_find_node(ctx, dst, edge->dst->dim);
1669                 if (!dst_src || !dst_dst) {
1670                         if (edge->validity)
1671                                 isl_die(ctx, isl_error_internal,
1672                                         "backward validity edge", return -1);
1673                         continue;
1674                 }
1675
1676                 map = isl_map_copy(edge->map);
1677
1678                 dst->edge[dst->n_edge].src = dst_src;
1679                 dst->edge[dst->n_edge].dst = dst_dst;
1680                 dst->edge[dst->n_edge].map = map;
1681                 dst->edge[dst->n_edge].validity = edge->validity;
1682                 dst->edge[dst->n_edge].proximity = edge->proximity;
1683                 dst->n_edge++;
1684         }
1685
1686         return 0;
1687 }
1688
1689 /* Given a "src" dependence graph that contains the nodes from "dst"
1690  * that satisfy node_pred, copy the schedule computed in "src"
1691  * for those nodes back to "dst".
1692  */
1693 static int copy_schedule(struct isl_sched_graph *dst,
1694         struct isl_sched_graph *src,
1695         int (*node_pred)(struct isl_sched_node *node, int data), int data)
1696 {
1697         int i;
1698
1699         src->n = 0;
1700         for (i = 0; i < dst->n; ++i) {
1701                 if (!node_pred(&dst->node[i], data))
1702                         continue;
1703                 isl_mat_free(dst->node[i].sched);
1704                 isl_map_free(dst->node[i].sched_map);
1705                 dst->node[i].sched = isl_mat_copy(src->node[src->n].sched);
1706                 dst->node[i].sched_map =
1707                         isl_map_copy(src->node[src->n].sched_map);
1708                 src->n++;
1709         }
1710
1711         dst->n_total_row = src->n_total_row;
1712         dst->n_band = src->n_band;
1713
1714         return 0;
1715 }
1716
1717 /* Compute the maximal number of variables over all nodes.
1718  * This is the maximal number of linearly independent schedule
1719  * rows that we need to compute.
1720  * Just in case we end up in a part of the dependence graph
1721  * with only lower-dimensional domains, we make sure we will
1722  * compute the required amount of extra linearly independent rows.
1723  */
1724 static int compute_maxvar(struct isl_sched_graph *graph)
1725 {
1726         int i;
1727
1728         graph->maxvar = 0;
1729         for (i = 0; i < graph->n; ++i) {
1730                 struct isl_sched_node *node = &graph->node[i];
1731                 int nvar;
1732
1733                 if (node_update_cmap(node) < 0)
1734                         return -1;
1735                 nvar = node->nvar + graph->n_row - node->rank;
1736                 if (nvar > graph->maxvar)
1737                         graph->maxvar = nvar;
1738         }
1739
1740         return 0;
1741 }
1742
1743 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph);
1744 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph);
1745
1746 /* Compute a schedule for a subgraph of "graph".  In particular, for
1747  * the graph composed of nodes that satisfy node_pred and edges that
1748  * that satisfy edge_pred.  The caller should precompute the number
1749  * of nodes and edges that satisfy these predicates and pass them along
1750  * as "n" and "n_edge".
1751  * If the subgraph is known to consist of a single component, then wcc should
1752  * be set and then we call compute_schedule_wcc on the constructed subgraph.
1753  * Otherwise, we call compute_schedule, which will check whether the subgraph
1754  * is connected.
1755  */
1756 static int compute_sub_schedule(isl_ctx *ctx,
1757         struct isl_sched_graph *graph, int n, int n_edge,
1758         int (*node_pred)(struct isl_sched_node *node, int data),
1759         int (*edge_pred)(struct isl_sched_edge *edge, int data),
1760         int data, int wcc)
1761 {
1762         struct isl_sched_graph split = { 0 };
1763
1764         if (graph_alloc(ctx, &split, n, n_edge) < 0)
1765                 goto error;
1766         if (copy_nodes(&split, graph, node_pred, data) < 0)
1767                 goto error;
1768         if (graph_init_table(ctx, &split) < 0)
1769                 goto error;
1770         if (copy_edges(ctx, &split, graph, edge_pred, data) < 0)
1771                 goto error;
1772         if (graph_init_edge_table(ctx, &split) < 0)
1773                 goto error;
1774         split.n_row = graph->n_row;
1775         split.n_total_row = graph->n_total_row;
1776         split.n_band = graph->n_band;
1777         split.band_start = graph->band_start;
1778
1779         if (wcc && compute_schedule_wcc(ctx, &split) < 0)
1780                 goto error;
1781         if (!wcc && compute_schedule(ctx, &split) < 0)
1782                 goto error;
1783
1784         copy_schedule(graph, &split, node_pred, data);
1785
1786         graph_free(ctx, &split);
1787         return 0;
1788 error:
1789         graph_free(ctx, &split);
1790         return -1;
1791 }
1792
1793 static int node_scc_exactly(struct isl_sched_node *node, int scc)
1794 {
1795         return node->scc == scc;
1796 }
1797
1798 static int node_scc_at_most(struct isl_sched_node *node, int scc)
1799 {
1800         return node->scc <= scc;
1801 }
1802
1803 static int node_scc_at_least(struct isl_sched_node *node, int scc)
1804 {
1805         return node->scc >= scc;
1806 }
1807
1808 static int edge_src_scc_exactly(struct isl_sched_edge *edge, int scc)
1809 {
1810         return edge->src->scc == scc;
1811 }
1812
1813 static int edge_dst_scc_at_most(struct isl_sched_edge *edge, int scc)
1814 {
1815         return edge->dst->scc <= scc;
1816 }
1817
1818 static int edge_src_scc_at_least(struct isl_sched_edge *edge, int scc)
1819 {
1820         return edge->src->scc >= scc;
1821 }
1822
1823 /* Pad the schedules of all nodes with zero rows such that in the end
1824  * they all have graph->n_total_row rows.
1825  * The extra rows don't belong to any band, so they get assigned band number -1.
1826  */
1827 static int pad_schedule(struct isl_sched_graph *graph)
1828 {
1829         int i, j;
1830
1831         for (i = 0; i < graph->n; ++i) {
1832                 struct isl_sched_node *node = &graph->node[i];
1833                 int row = isl_mat_rows(node->sched);
1834                 if (graph->n_total_row > row) {
1835                         isl_map_free(node->sched_map);
1836                         node->sched_map = NULL;
1837                 }
1838                 node->sched = isl_mat_add_zero_rows(node->sched,
1839                                                     graph->n_total_row - row);
1840                 if (!node->sched)
1841                         return -1;
1842                 for (j = row; j < graph->n_total_row; ++j)
1843                         node->band[j] = -1;
1844         }
1845
1846         return 0;
1847 }
1848
1849 /* Split the current graph into two parts and compute a schedule for each
1850  * part individually.  In particular, one part consists of all SCCs up
1851  * to and including graph->src_scc, while the other part contains the other
1852  * SCCS.
1853  *
1854  * The split is enforced in the schedule by constant rows with two different
1855  * values (0 and 1).  These constant rows replace the previously computed rows
1856  * in the current band.
1857  * It would be possible to reuse them as the first rows in the next
1858  * band, but recomputing them may result in better rows as we are looking
1859  * at a smaller part of the dependence graph.
1860  * compute_split_schedule is only called when no zero-distance schedule row
1861  * could be found on the entire graph, so we wark the splitting row as
1862  * non zero-distance.
1863  *
1864  * The band_id of the second group is set to n, where n is the number
1865  * of nodes in the first group.  This ensures that the band_ids over
1866  * the two groups remain disjoint, even if either or both of the two
1867  * groups contain independent components.
1868  */
1869 static int compute_split_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
1870 {
1871         int i, j, n, e1, e2;
1872         int n_total_row, orig_total_row;
1873         int n_band, orig_band;
1874         int drop;
1875
1876         drop = graph->n_total_row - graph->band_start;
1877         graph->n_total_row -= drop;
1878         graph->n_row -= drop;
1879
1880         n = 0;
1881         for (i = 0; i < graph->n; ++i) {
1882                 struct isl_sched_node *node = &graph->node[i];
1883                 int row = isl_mat_rows(node->sched) - drop;
1884                 int cols = isl_mat_cols(node->sched);
1885                 int before = node->scc <= graph->src_scc;
1886
1887                 if (before)
1888                         n++;
1889
1890                 isl_map_free(node->sched_map);
1891                 node->sched_map = NULL;
1892                 node->sched = isl_mat_drop_rows(node->sched,
1893                                                 graph->band_start, drop);
1894                 node->sched = isl_mat_add_rows(node->sched, 1);
1895                 if (!node->sched)
1896                         return -1;
1897                 node->sched = isl_mat_set_element_si(node->sched, row, 0,
1898                                                      !before);
1899                 for (j = 1; j < cols; ++j)
1900                         node->sched = isl_mat_set_element_si(node->sched,
1901                                                              row, j, 0);
1902                 node->band[graph->n_total_row] = graph->n_band;
1903                 node->zero[graph->n_total_row] = 0;
1904         }
1905
1906         e1 = e2 = 0;
1907         for (i = 0; i < graph->n_edge; ++i) {
1908                 if (graph->edge[i].dst->scc <= graph->src_scc)
1909                         e1++;
1910                 if (graph->edge[i].src->scc > graph->src_scc)
1911                         e2++;
1912         }
1913
1914         graph->n_total_row++;
1915         next_band(graph);
1916
1917         for (i = 0; i < graph->n; ++i) {
1918                 struct isl_sched_node *node = &graph->node[i];
1919                 if (node->scc > graph->src_scc)
1920                         node->band_id[graph->n_band] = n;
1921         }
1922
1923         orig_total_row = graph->n_total_row;
1924         orig_band = graph->n_band;
1925         if (compute_sub_schedule(ctx, graph, n, e1,
1926                                 &node_scc_at_most, &edge_dst_scc_at_most,
1927                                 graph->src_scc, 0) < 0)
1928                 return -1;
1929         n_total_row = graph->n_total_row;
1930         graph->n_total_row = orig_total_row;
1931         n_band = graph->n_band;
1932         graph->n_band = orig_band;
1933         if (compute_sub_schedule(ctx, graph, graph->n - n, e2,
1934                                 &node_scc_at_least, &edge_src_scc_at_least,
1935                                 graph->src_scc + 1, 0) < 0)
1936                 return -1;
1937         if (n_total_row > graph->n_total_row)
1938                 graph->n_total_row = n_total_row;
1939         if (n_band > graph->n_band)
1940                 graph->n_band = n_band;
1941
1942         return pad_schedule(graph);
1943 }
1944
1945 /* Compute the next band of the schedule after updating the dependence
1946  * relations based on the the current schedule.
1947  */
1948 static int compute_next_band(isl_ctx *ctx, struct isl_sched_graph *graph)
1949 {
1950         if (update_edges(ctx, graph) < 0)
1951                 return -1;
1952         next_band(graph);
1953
1954         return compute_schedule(ctx, graph);
1955 }
1956
1957 /* Add constraints to graph->lp that force the dependence "map" (which
1958  * is part of the dependence relation of "edge")
1959  * to be respected and attempt to carry it, where the edge is one from
1960  * a node j to itself.  "pos" is the sequence number of the given map.
1961  * That is, add constraints that enforce
1962  *
1963  *      (c_j_0 + c_j_n n + c_j_x y) - (c_j_0 + c_j_n n + c_j_x x)
1964  *      = c_j_x (y - x) >= e_i
1965  *
1966  * for each (x,y) in R.
1967  * We obtain general constraints on coefficients (c_0, c_n, c_x)
1968  * of valid constraints for (y - x) and then plug in (-e_i, 0, c_j_x),
1969  * with each coefficient in c_j_x represented as a pair of non-negative
1970  * coefficients.
1971  */
1972 static int add_intra_constraints(struct isl_sched_graph *graph,
1973         struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
1974 {
1975         unsigned total;
1976         isl_ctx *ctx = isl_map_get_ctx(map);
1977         isl_space *dim;
1978         isl_dim_map *dim_map;
1979         isl_basic_set *coef;
1980         struct isl_sched_node *node = edge->src;
1981
1982         coef = intra_coefficients(graph, map);
1983
1984         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
1985
1986         total = isl_basic_set_total_dim(graph->lp);
1987         dim_map = isl_dim_map_alloc(ctx, total);
1988         isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
1989         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 1, 2,
1990                           isl_space_dim(dim, isl_dim_set), 1,
1991                           node->nvar, -1);
1992         isl_dim_map_range(dim_map, node->start + 2 * node->nparam + 2, 2,
1993                           isl_space_dim(dim, isl_dim_set), 1,
1994                           node->nvar, 1);
1995         graph->lp = isl_basic_set_extend_constraints(graph->lp,
1996                         coef->n_eq, coef->n_ineq);
1997         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
1998                                                            coef, dim_map);
1999         isl_space_free(dim);
2000
2001         return 0;
2002 }
2003
2004 /* Add constraints to graph->lp that force the dependence "map" (which
2005  * is part of the dependence relation of "edge")
2006  * to be respected and attempt to carry it, where the edge is one from
2007  * node j to node k.  "pos" is the sequence number of the given map.
2008  * That is, add constraints that enforce
2009  *
2010  *      (c_k_0 + c_k_n n + c_k_x y) - (c_j_0 + c_j_n n + c_j_x x) >= e_i
2011  *
2012  * for each (x,y) in R.
2013  * We obtain general constraints on coefficients (c_0, c_n, c_x)
2014  * of valid constraints for R and then plug in
2015  * (-e_i + c_k_0 - c_j_0, c_k_n - c_j_n, c_k_x - c_j_x)
2016  * with each coefficient (except e_i, c_k_0 and c_j_0)
2017  * represented as a pair of non-negative coefficients.
2018  */
2019 static int add_inter_constraints(struct isl_sched_graph *graph,
2020         struct isl_sched_edge *edge, __isl_take isl_map *map, int pos)
2021 {
2022         unsigned total;
2023         isl_ctx *ctx = isl_map_get_ctx(map);
2024         isl_space *dim;
2025         isl_dim_map *dim_map;
2026         isl_basic_set *coef;
2027         struct isl_sched_node *src = edge->src;
2028         struct isl_sched_node *dst = edge->dst;
2029
2030         coef = inter_coefficients(graph, map);
2031
2032         dim = isl_space_domain(isl_space_unwrap(isl_basic_set_get_space(coef)));
2033
2034         total = isl_basic_set_total_dim(graph->lp);
2035         dim_map = isl_dim_map_alloc(ctx, total);
2036
2037         isl_dim_map_range(dim_map, 3 + pos, 0, 0, 0, 1, -1);
2038
2039         isl_dim_map_range(dim_map, dst->start, 0, 0, 0, 1, 1);
2040         isl_dim_map_range(dim_map, dst->start + 1, 2, 1, 1, dst->nparam, -1);
2041         isl_dim_map_range(dim_map, dst->start + 2, 2, 1, 1, dst->nparam, 1);
2042         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 1, 2,
2043                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2044                           dst->nvar, -1);
2045         isl_dim_map_range(dim_map, dst->start + 2 * dst->nparam + 2, 2,
2046                           isl_space_dim(dim, isl_dim_set) + src->nvar, 1,
2047                           dst->nvar, 1);
2048
2049         isl_dim_map_range(dim_map, src->start, 0, 0, 0, 1, -1);
2050         isl_dim_map_range(dim_map, src->start + 1, 2, 1, 1, src->nparam, 1);
2051         isl_dim_map_range(dim_map, src->start + 2, 2, 1, 1, src->nparam, -1);
2052         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 1, 2,
2053                           isl_space_dim(dim, isl_dim_set), 1,
2054                           src->nvar, 1);
2055         isl_dim_map_range(dim_map, src->start + 2 * src->nparam + 2, 2,
2056                           isl_space_dim(dim, isl_dim_set), 1,
2057                           src->nvar, -1);
2058
2059         graph->lp = isl_basic_set_extend_constraints(graph->lp,
2060                         coef->n_eq, coef->n_ineq);
2061         graph->lp = isl_basic_set_add_constraints_dim_map(graph->lp,
2062                                                            coef, dim_map);
2063         isl_space_free(dim);
2064
2065         return 0;
2066 }
2067
2068 /* Add constraints to graph->lp that force all dependence
2069  * to be respected and attempt to carry it.
2070  */
2071 static int add_all_constraints(struct isl_sched_graph *graph)
2072 {
2073         int i, j;
2074         int pos;
2075
2076         pos = 0;
2077         for (i = 0; i < graph->n_edge; ++i) {
2078                 struct isl_sched_edge *edge= &graph->edge[i];
2079                 for (j = 0; j < edge->map->n; ++j) {
2080                         isl_basic_map *bmap;
2081                         isl_map *map;
2082
2083                         bmap = isl_basic_map_copy(edge->map->p[j]);
2084                         map = isl_map_from_basic_map(bmap);
2085
2086                         if (edge->src == edge->dst &&
2087                             add_intra_constraints(graph, edge, map, pos) < 0)
2088                                 return -1;
2089                         if (edge->src != edge->dst &&
2090                             add_inter_constraints(graph, edge, map, pos) < 0)
2091                                 return -1;
2092                         ++pos;
2093                 }
2094         }
2095
2096         return 0;
2097 }
2098
2099 /* Count the number of equality and inequality constraints
2100  * that will be added to the carry_lp problem.
2101  * If once is set, then we count
2102  * each edge exactly once.  Otherwise, we count as follows
2103  * validity             -> 1 (>= 0)
2104  * validity+proximity   -> 2 (>= 0 and upper bound)
2105  * proximity            -> 2 (lower and upper bound)
2106  */
2107 static int count_all_constraints(struct isl_sched_graph *graph,
2108         int *n_eq, int *n_ineq, int once)
2109 {
2110         int i, j;
2111
2112         *n_eq = *n_ineq = 0;
2113         for (i = 0; i < graph->n_edge; ++i) {
2114                 struct isl_sched_edge *edge= &graph->edge[i];
2115                 for (j = 0; j < edge->map->n; ++j) {
2116                         isl_basic_map *bmap;
2117                         isl_map *map;
2118
2119                         bmap = isl_basic_map_copy(edge->map->p[j]);
2120                         map = isl_map_from_basic_map(bmap);
2121
2122                         if (count_map_constraints(graph, edge, map,
2123                                                   n_eq, n_ineq, once) < 0)
2124                                     return -1;
2125                 }
2126         }
2127
2128         return 0;
2129 }
2130
2131 /* Construct an LP problem for finding schedule coefficients
2132  * such that the schedule carries as many dependences as possible.
2133  * In particular, for each dependence i, we bound the dependence distance
2134  * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum
2135  * of all e_i's.  Dependence with e_i = 0 in the solution are simply
2136  * respected, while those with e_i > 0 (in practice e_i = 1) are carried.
2137  * Note that if the dependence relation is a union of basic maps,
2138  * then we have to consider each basic map individually as it may only
2139  * be possible to carry the dependences expressed by some of those
2140  * basic maps and not all off them.
2141  * Below, we consider each of those basic maps as a separate "edge".
2142  *
2143  * All variables of the LP are non-negative.  The actual coefficients
2144  * may be negative, so each coefficient is represented as the difference
2145  * of two non-negative variables.  The negative part always appears
2146  * immediately before the positive part.
2147  * Other than that, the variables have the following order
2148  *
2149  *      - sum of (1 - e_i) over all edges
2150  *      - sum of positive and negative parts of all c_n coefficients
2151  *              (unconstrained when computing non-parametric schedules)
2152  *      - sum of positive and negative parts of all c_x coefficients
2153  *      - for each edge
2154  *              - e_i
2155  *      - for each node
2156  *              - c_i_0
2157  *              - positive and negative parts of c_i_n (if parametric)
2158  *              - positive and negative parts of c_i_x
2159  *
2160  * The constraints are those from the edges plus three equalities
2161  * to express the sums and n_edge inequalities to express e_i <= 1.
2162  */
2163 static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
2164 {
2165         int i, j;
2166         int k;
2167         isl_space *dim;
2168         unsigned total;
2169         int n_eq, n_ineq;
2170         int n_edge;
2171
2172         n_edge = 0;
2173         for (i = 0; i < graph->n_edge; ++i)
2174                 n_edge += graph->edge[i].map->n;
2175
2176         total = 3 + n_edge;
2177         for (i = 0; i < graph->n; ++i) {
2178                 struct isl_sched_node *node = &graph->node[graph->sorted[i]];
2179                 node->start = total;
2180                 total += 1 + 2 * (node->nparam + node->nvar);
2181         }
2182
2183         if (count_all_constraints(graph, &n_eq, &n_ineq, 1) < 0)
2184                 return -1;
2185
2186         dim = isl_space_set_alloc(ctx, 0, total);
2187         isl_basic_set_free(graph->lp);
2188         n_eq += 3;
2189         n_ineq += n_edge;
2190         graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
2191         graph->lp = isl_basic_set_set_rational(graph->lp);
2192
2193         k = isl_basic_set_alloc_equality(graph->lp);
2194         if (k < 0)
2195                 return -1;
2196         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2197         isl_int_set_si(graph->lp->eq[k][0], -n_edge);
2198         isl_int_set_si(graph->lp->eq[k][1], 1);
2199         for (i = 0; i < n_edge; ++i)
2200                 isl_int_set_si(graph->lp->eq[k][4 + i], 1);
2201
2202         k = isl_basic_set_alloc_equality(graph->lp);
2203         if (k < 0)
2204                 return -1;
2205         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2206         isl_int_set_si(graph->lp->eq[k][2], -1);
2207         for (i = 0; i < graph->n; ++i) {
2208                 int pos = 1 + graph->node[i].start + 1;
2209
2210                 for (j = 0; j < 2 * graph->node[i].nparam; ++j)
2211                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2212         }
2213
2214         k = isl_basic_set_alloc_equality(graph->lp);
2215         if (k < 0)
2216                 return -1;
2217         isl_seq_clr(graph->lp->eq[k], 1 +  total);
2218         isl_int_set_si(graph->lp->eq[k][3], -1);
2219         for (i = 0; i < graph->n; ++i) {
2220                 struct isl_sched_node *node = &graph->node[i];
2221                 int pos = 1 + node->start + 1 + 2 * node->nparam;
2222
2223                 for (j = 0; j < 2 * node->nvar; ++j)
2224                         isl_int_set_si(graph->lp->eq[k][pos + j], 1);
2225         }
2226
2227         for (i = 0; i < n_edge; ++i) {
2228                 k = isl_basic_set_alloc_inequality(graph->lp);
2229                 if (k < 0)
2230                         return -1;
2231                 isl_seq_clr(graph->lp->ineq[k], 1 +  total);
2232                 isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
2233                 isl_int_set_si(graph->lp->ineq[k][0], 1);
2234         }
2235
2236         if (add_all_constraints(graph) < 0)
2237                 return -1;
2238
2239         return 0;
2240 }
2241
2242 /* If the schedule_split_parallel option is set and if the linear
2243  * parts of the scheduling rows for all nodes in the graphs are the same,
2244  * then split off the constant term from the linear part.
2245  * The constant term is then placed in a separate band and
2246  * the linear part is simplified.
2247  */
2248 static int split_parallel(isl_ctx *ctx, struct isl_sched_graph *graph)
2249 {
2250         int i;
2251         int equal = 1;
2252         int row, cols;
2253         struct isl_sched_node *node0;
2254
2255         if (!ctx->opt->schedule_split_parallel)
2256                 return 0;
2257         if (graph->n <= 1)
2258                 return 0;
2259
2260         node0 = &graph->node[0];
2261         row = isl_mat_rows(node0->sched) - 1;
2262         cols = isl_mat_cols(node0->sched);
2263         for (i = 1; i < graph->n; ++i) {
2264                 struct isl_sched_node *node = &graph->node[i];
2265
2266                 if (isl_mat_cols(node->sched) != cols)
2267                         return 0;
2268                 if (!isl_seq_eq(node0->sched->row[row] + 1,
2269                                 node->sched->row[row] + 1, cols - 1))
2270                         return 0;
2271                 if (equal &&
2272                     isl_int_ne(node0->sched->row[row][0],
2273                                node->sched->row[row][0]))
2274                         equal = 0;
2275         }
2276         if (equal)
2277                 return 0;
2278
2279         next_band(graph);
2280
2281         for (i = 0; i < graph->n; ++i) {
2282                 struct isl_sched_node *node = &graph->node[i];
2283
2284                 isl_map_free(node->sched_map);
2285                 node->sched_map = NULL;
2286                 node->sched = isl_mat_add_zero_rows(node->sched, 1);
2287                 if (!node->sched)
2288                         return -1;
2289                 isl_int_set(node->sched->row[row + 1][0],
2290                             node->sched->row[row][0]);
2291                 isl_int_set_si(node->sched->row[row][0], 0);
2292                 node->sched = isl_mat_normalize_row(node->sched, row);
2293                 if (!node->sched)
2294                         return -1;
2295                 node->band[graph->n_total_row] = graph->n_band;
2296         }
2297
2298         graph->n_total_row++;
2299
2300         return 0;
2301 }
2302
2303 /* Construct a schedule row for each node such that as many dependences
2304  * as possible are carried and then continue with the next band.
2305  */
2306 static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph)
2307 {
2308         int i;
2309         int n_edge;
2310         isl_vec *sol;
2311         isl_basic_set *lp;
2312
2313         n_edge = 0;
2314         for (i = 0; i < graph->n_edge; ++i)
2315                 n_edge += graph->edge[i].map->n;
2316
2317         if (setup_carry_lp(ctx, graph) < 0)
2318                 return -1;
2319
2320         lp = isl_basic_set_copy(graph->lp);
2321         sol = isl_tab_basic_set_non_neg_lexmin(lp);
2322         if (!sol)
2323                 return -1;
2324
2325         if (sol->size == 0) {
2326                 isl_vec_free(sol);
2327                 isl_die(ctx, isl_error_internal,
2328                         "error in schedule construction", return -1);
2329         }
2330
2331         if (isl_int_cmp_si(sol->el[1], n_edge) >= 0) {
2332                 isl_vec_free(sol);
2333                 isl_die(ctx, isl_error_unknown,
2334                         "unable to carry dependences", return -1);
2335         }
2336
2337         if (update_schedule(graph, sol, 0, 0) < 0)
2338                 return -1;
2339
2340         if (split_parallel(ctx, graph) < 0)
2341                 return -1;
2342
2343         return compute_next_band(ctx, graph);
2344 }
2345
2346 /* Are there any validity edges in the graph?
2347  */
2348 static int has_validity_edges(struct isl_sched_graph *graph)
2349 {
2350         int i;
2351
2352         for (i = 0; i < graph->n_edge; ++i)
2353                 if (graph->edge[i].validity)
2354                         return 1;
2355
2356         return 0;
2357 }
2358
2359 /* Should we apply a Feautrier step?
2360  * That is, did the user request the Feautrier algorithm and are
2361  * there any validity dependences (left)?
2362  */
2363 static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph)
2364 {
2365         if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER)
2366                 return 0;
2367
2368         return has_validity_edges(graph);
2369 }
2370
2371 /* Compute a schedule for a connected dependence graph using Feautrier's
2372  * multi-dimensional scheduling algorithm.
2373  * The original algorithm is described in [1].
2374  * The main idea is to minimize the number of scheduling dimensions, by
2375  * trying to satisfy as many dependences as possible per scheduling dimension.
2376  *
2377  * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling
2378  *     Problem, Part II: Multi-Dimensional Time.
2379  *     In Intl. Journal of Parallel Programming, 1992.
2380  */
2381 static int compute_schedule_wcc_feautrier(isl_ctx *ctx,
2382         struct isl_sched_graph *graph)
2383 {
2384         return carry_dependences(ctx, graph);
2385 }
2386
2387 /* Compute a schedule for a connected dependence graph.
2388  * We try to find a sequence of as many schedule rows as possible that result
2389  * in non-negative dependence distances (independent of the previous rows
2390  * in the sequence, i.e., such that the sequence is tilable).
2391  * If we can't find any more rows we either
2392  * - split between SCCs and start over (assuming we found an interesting
2393  *      pair of SCCs between which to split)
2394  * - continue with the next band (assuming the current band has at least
2395  *      one row)
2396  * - try to carry as many dependences as possible and continue with the next
2397  *      band
2398  *
2399  * If Feautrier's algorithm is selected, we first recursively try to satisfy
2400  * as many validity dependences as possible. When all validity dependences
2401  * are satisfied we extend the schedule to a full-dimensional schedule.
2402  *
2403  * If we manage to complete the schedule, we finish off by topologically
2404  * sorting the statements based on the remaining dependences.
2405  *
2406  * If ctx->opt->schedule_outer_zero_distance is set, then we force the
2407  * outermost dimension in the current band to be zero distance.  If this
2408  * turns out to be impossible, we fall back on the general scheme above
2409  * and try to carry as many dependences as possible.
2410  */
2411 static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph)
2412 {
2413         int force_zero = 0;
2414
2415         if (detect_sccs(graph) < 0)
2416                 return -1;
2417         sort_sccs(graph);
2418
2419         if (compute_maxvar(graph) < 0)
2420                 return -1;
2421
2422         if (need_feautrier_step(ctx, graph))
2423                 return compute_schedule_wcc_feautrier(ctx, graph);
2424
2425         if (ctx->opt->schedule_outer_zero_distance)
2426                 force_zero = 1;
2427
2428         while (graph->n_row < graph->maxvar) {
2429                 isl_vec *sol;
2430
2431                 graph->src_scc = -1;
2432                 graph->dst_scc = -1;
2433
2434                 if (setup_lp(ctx, graph, force_zero) < 0)
2435                         return -1;
2436                 sol = solve_lp(graph);
2437                 if (!sol)
2438                         return -1;
2439                 if (sol->size == 0) {
2440                         isl_vec_free(sol);
2441                         if (!ctx->opt->schedule_maximize_band_depth &&
2442                             graph->n_total_row > graph->band_start)
2443                                 return compute_next_band(ctx, graph);
2444                         if (graph->src_scc >= 0)
2445                                 return compute_split_schedule(ctx, graph);
2446                         if (graph->n_total_row > graph->band_start)
2447                                 return compute_next_band(ctx, graph);
2448                         return carry_dependences(ctx, graph);
2449                 }
2450                 if (update_schedule(graph, sol, 1, 1) < 0)
2451                         return -1;
2452                 force_zero = 0;
2453         }
2454
2455         if (graph->n_total_row > graph->band_start)
2456                 next_band(graph);
2457         return sort_statements(ctx, graph);
2458 }
2459
2460 /* Compute a schedule for each component (identified by node->scc)
2461  * of the dependence graph separately and then combine the results.
2462  *
2463  * The band_id is adjusted such that each component has a separate id.
2464  * Note that the band_id may have already been set to a value different
2465  * from zero by compute_split_schedule.
2466  */
2467 static int compute_component_schedule(isl_ctx *ctx,
2468         struct isl_sched_graph *graph)
2469 {
2470         int wcc, i;
2471         int n, n_edge;
2472         int n_total_row, orig_total_row;
2473         int n_band, orig_band;
2474
2475         n_total_row = 0;
2476         orig_total_row = graph->n_total_row;
2477         n_band = 0;
2478         orig_band = graph->n_band;
2479         for (i = 0; i < graph->n; ++i)
2480                 graph->node[i].band_id[graph->n_band] += graph->node[i].scc;
2481         for (wcc = 0; wcc < graph->scc; ++wcc) {
2482                 n = 0;
2483                 for (i = 0; i < graph->n; ++i)
2484                         if (graph->node[i].scc == wcc)
2485                                 n++;
2486                 n_edge = 0;
2487                 for (i = 0; i < graph->n_edge; ++i)
2488                         if (graph->edge[i].src->scc == wcc)
2489                                 n_edge++;
2490
2491                 if (compute_sub_schedule(ctx, graph, n, n_edge,
2492                                     &node_scc_exactly,
2493                                     &edge_src_scc_exactly, wcc, 1) < 0)
2494                         return -1;
2495                 if (graph->n_total_row > n_total_row)
2496                         n_total_row = graph->n_total_row;
2497                 graph->n_total_row = orig_total_row;
2498                 if (graph->n_band > n_band)
2499                         n_band = graph->n_band;
2500                 graph->n_band = orig_band;
2501         }
2502
2503         graph->n_total_row = n_total_row;
2504         graph->n_band = n_band;
2505
2506         return pad_schedule(graph);
2507 }
2508
2509 /* Compute a schedule for the given dependence graph.
2510  * We first check if the graph is connected (through validity dependences)
2511  * and, if not, compute a schedule for each component separately.
2512  */
2513 static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph)
2514 {
2515         if (detect_wccs(graph) < 0)
2516                 return -1;
2517
2518         if (graph->scc > 1)
2519                 return compute_component_schedule(ctx, graph);
2520
2521         return compute_schedule_wcc(ctx, graph);
2522 }
2523
2524 /* Compute a schedule for the given union of domains that respects
2525  * all the validity dependences.
2526  * If the default isl scheduling algorithm is used, it tries to minimize
2527  * the dependence distances over the proximity dependences.
2528  * If Feautrier's scheduling algorithm is used, the proximity dependence
2529  * distances are only minimized during the extension to a full-dimensional
2530  * schedule.
2531  */
2532 __isl_give isl_schedule *isl_union_set_compute_schedule(
2533         __isl_take isl_union_set *domain,
2534         __isl_take isl_union_map *validity,
2535         __isl_take isl_union_map *proximity)
2536 {
2537         isl_ctx *ctx = isl_union_set_get_ctx(domain);
2538         isl_space *dim;
2539         struct isl_sched_graph graph = { 0 };
2540         isl_schedule *sched;
2541
2542         domain = isl_union_set_align_params(domain,
2543                                             isl_union_map_get_space(validity));
2544         domain = isl_union_set_align_params(domain,
2545                                             isl_union_map_get_space(proximity));
2546         dim = isl_union_set_get_space(domain);
2547         validity = isl_union_map_align_params(validity, isl_space_copy(dim));
2548         proximity = isl_union_map_align_params(proximity, dim);
2549
2550         if (!domain)
2551                 goto error;
2552
2553         graph.n = isl_union_set_n_set(domain);
2554         if (graph.n == 0)
2555                 goto empty;
2556         if (graph_alloc(ctx, &graph, graph.n,
2557             isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
2558                 goto error;
2559         graph.root = 1;
2560         graph.n = 0;
2561         if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
2562                 goto error;
2563         if (graph_init_table(ctx, &graph) < 0)
2564                 goto error;
2565         graph.n_edge = 0;
2566         if (isl_union_map_foreach_map(validity, &extract_edge, &graph) < 0)
2567                 goto error;
2568         if (graph_init_edge_table(ctx, &graph) < 0)
2569                 goto error;
2570         if (isl_union_map_foreach_map(proximity, &extract_edge, &graph) < 0)
2571                 goto error;
2572
2573         if (compute_schedule(ctx, &graph) < 0)
2574                 goto error;
2575
2576 empty:
2577         sched = extract_schedule(&graph, isl_union_set_get_space(domain));
2578
2579         graph_free(ctx, &graph);
2580         isl_union_set_free(domain);
2581         isl_union_map_free(validity);
2582         isl_union_map_free(proximity);
2583
2584         return sched;
2585 error:
2586         graph_free(ctx, &graph);
2587         isl_union_set_free(domain);
2588         isl_union_map_free(validity);
2589         isl_union_map_free(proximity);
2590         return NULL;
2591 }
2592
2593 void *isl_schedule_free(__isl_take isl_schedule *sched)
2594 {
2595         int i;
2596         if (!sched)
2597                 return NULL;
2598
2599         if (--sched->ref > 0)
2600                 return NULL;
2601
2602         for (i = 0; i < sched->n; ++i) {
2603                 isl_map_free(sched->node[i].sched);
2604                 free(sched->node[i].band_end);
2605                 free(sched->node[i].band_id);
2606                 free(sched->node[i].zero);
2607         }
2608         isl_space_free(sched->dim);
2609         isl_band_list_free(sched->band_forest);
2610         free(sched);
2611         return NULL;
2612 }
2613
2614 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
2615 {
2616         return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
2617 }
2618
2619 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
2620 {
2621         int i;
2622         isl_union_map *umap;
2623
2624         if (!sched)
2625                 return NULL;
2626
2627         umap = isl_union_map_empty(isl_space_copy(sched->dim));
2628         for (i = 0; i < sched->n; ++i)
2629                 umap = isl_union_map_add_map(umap,
2630                                             isl_map_copy(sched->node[i].sched));
2631
2632         return umap;
2633 }
2634
2635 static __isl_give isl_band_list *construct_band_list(
2636         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2637         int band_nr, int *parent_active, int n_active);
2638
2639 /* Construct an isl_band structure for the band in the given schedule
2640  * with sequence number band_nr for the n_active nodes marked by active.
2641  * If the nodes don't have a band with the given sequence number,
2642  * then a band without members is created.
2643  *
2644  * Because of the way the schedule is constructed, we know that
2645  * the position of the band inside the schedule of a node is the same
2646  * for all active nodes.
2647  */
2648 static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
2649         __isl_keep isl_band *parent,
2650         int band_nr, int *active, int n_active)
2651 {
2652         int i, j;
2653         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2654         isl_band *band;
2655         unsigned start, end;
2656
2657         band = isl_calloc_type(ctx, isl_band);
2658         if (!band)
2659                 return NULL;
2660
2661         band->ref = 1;
2662         band->schedule = schedule;
2663         band->parent = parent;
2664
2665         for (i = 0; i < schedule->n; ++i)
2666                 if (active[i] && schedule->node[i].n_band > band_nr + 1)
2667                         break;
2668
2669         if (i < schedule->n) {
2670                 band->children = construct_band_list(schedule, band,
2671                                                 band_nr + 1, active, n_active);
2672                 if (!band->children)
2673                         goto error;
2674         }
2675
2676         for (i = 0; i < schedule->n; ++i)
2677                 if (active[i])
2678                         break;
2679
2680         if (i >= schedule->n)
2681                 isl_die(ctx, isl_error_internal,
2682                         "band without active statements", goto error);
2683
2684         start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
2685         end = band_nr < schedule->node[i].n_band ?
2686                 schedule->node[i].band_end[band_nr] : start;
2687         band->n = end - start;
2688
2689         band->zero = isl_alloc_array(ctx, int, band->n);
2690         if (!band->zero)
2691                 goto error;
2692
2693         for (j = 0; j < band->n; ++j)
2694                 band->zero[j] = schedule->node[i].zero[start + j];
2695
2696         band->map = isl_union_map_empty(isl_space_copy(schedule->dim));
2697         for (i = 0; i < schedule->n; ++i) {
2698                 isl_map *map;
2699                 unsigned n_out;
2700
2701                 if (!active[i])
2702                         continue;
2703
2704                 map = isl_map_copy(schedule->node[i].sched);
2705                 n_out = isl_map_dim(map, isl_dim_out);
2706                 map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
2707                 map = isl_map_project_out(map, isl_dim_out, 0, start);
2708                 band->map = isl_union_map_union(band->map,
2709                                                 isl_union_map_from_map(map));
2710         }
2711         if (!band->map)
2712                 goto error;
2713
2714         return band;
2715 error:
2716         isl_band_free(band);
2717         return NULL;
2718 }
2719
2720 /* Construct a list of bands that start at the same position (with
2721  * sequence number band_nr) in the schedules of the nodes that
2722  * were active in the parent band.
2723  *
2724  * A separate isl_band structure is created for each band_id
2725  * and for each node that does not have a band with sequence
2726  * number band_nr.  In the latter case, a band without members
2727  * is created.
2728  * This ensures that if a band has any children, then each node
2729  * that was active in the band is active in exactly one of the children.
2730  */
2731 static __isl_give isl_band_list *construct_band_list(
2732         __isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
2733         int band_nr, int *parent_active, int n_active)
2734 {
2735         int i, j;
2736         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2737         int *active;
2738         int n_band;
2739         isl_band_list *list;
2740
2741         n_band = 0;
2742         for (i = 0; i < n_active; ++i) {
2743                 for (j = 0; j < schedule->n; ++j) {
2744                         if (!parent_active[j])
2745                                 continue;
2746                         if (schedule->node[j].n_band <= band_nr)
2747                                 continue;
2748                         if (schedule->node[j].band_id[band_nr] == i) {
2749                                 n_band++;
2750                                 break;
2751                         }
2752                 }
2753         }
2754         for (j = 0; j < schedule->n; ++j)
2755                 if (schedule->node[j].n_band <= band_nr)
2756                         n_band++;
2757
2758         if (n_band == 1) {
2759                 isl_band *band;
2760                 list = isl_band_list_alloc(ctx, n_band);
2761                 band = construct_band(schedule, parent, band_nr,
2762                                         parent_active, n_active);
2763                 return isl_band_list_add(list, band);
2764         }
2765
2766         active = isl_alloc_array(ctx, int, schedule->n);
2767         if (!active)
2768                 return NULL;
2769
2770         list = isl_band_list_alloc(ctx, n_band);
2771
2772         for (i = 0; i < n_active; ++i) {
2773                 int n = 0;
2774                 isl_band *band;
2775
2776                 for (j = 0; j < schedule->n; ++j) {
2777                         active[j] = parent_active[j] &&
2778                                         schedule->node[j].n_band > band_nr &&
2779                                         schedule->node[j].band_id[band_nr] == i;
2780                         if (active[j])
2781                                 n++;
2782                 }
2783                 if (n == 0)
2784                         continue;
2785
2786                 band = construct_band(schedule, parent, band_nr, active, n);
2787
2788                 list = isl_band_list_add(list, band);
2789         }
2790         for (i = 0; i < schedule->n; ++i) {
2791                 isl_band *band;
2792                 if (!parent_active[i])
2793                         continue;
2794                 if (schedule->node[i].n_band > band_nr)
2795                         continue;
2796                 for (j = 0; j < schedule->n; ++j)
2797                         active[j] = j == i;
2798                 band = construct_band(schedule, parent, band_nr, active, 1);
2799                 list = isl_band_list_add(list, band);
2800         }
2801
2802         free(active);
2803
2804         return list;
2805 }
2806
2807 /* Construct a band forest representation of the schedule and
2808  * return the list of roots.
2809  */
2810 static __isl_give isl_band_list *construct_forest(
2811         __isl_keep isl_schedule *schedule)
2812 {
2813         int i;
2814         isl_ctx *ctx = isl_schedule_get_ctx(schedule);
2815         isl_band_list *forest;
2816         int *active;
2817
2818         active = isl_alloc_array(ctx, int, schedule->n);
2819         if (!active)
2820                 return NULL;
2821
2822         for (i = 0; i < schedule->n; ++i)
2823                 active[i] = 1;
2824
2825         forest = construct_band_list(schedule, NULL, 0, active, schedule->n);
2826
2827         free(active);
2828
2829         return forest;
2830 }
2831
2832 /* Return the roots of a band forest representation of the schedule.
2833  */
2834 __isl_give isl_band_list *isl_schedule_get_band_forest(
2835         __isl_keep isl_schedule *schedule)
2836 {
2837         if (!schedule)
2838                 return NULL;
2839         if (!schedule->band_forest)
2840                 schedule->band_forest = construct_forest(schedule);
2841         return isl_band_list_dup(schedule->band_forest);
2842 }
2843
2844 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2845         __isl_keep isl_band_list *list);
2846
2847 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
2848         __isl_keep isl_band *band)
2849 {
2850         isl_band_list *children;
2851
2852         p = isl_printer_start_line(p);
2853         p = isl_printer_print_union_map(p, band->map);
2854         p = isl_printer_end_line(p);
2855
2856         if (!isl_band_has_children(band))
2857                 return p;
2858
2859         children = isl_band_get_children(band);
2860
2861         p = isl_printer_indent(p, 4);
2862         p = print_band_list(p, children);
2863         p = isl_printer_indent(p, -4);
2864
2865         isl_band_list_free(children);
2866
2867         return p;
2868 }
2869
2870 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
2871         __isl_keep isl_band_list *list)
2872 {
2873         int i, n;
2874
2875         n = isl_band_list_n_band(list);
2876         for (i = 0; i < n; ++i) {
2877                 isl_band *band;
2878                 band = isl_band_list_get_band(list, i);
2879                 p = print_band(p, band);
2880                 isl_band_free(band);
2881         }
2882
2883         return p;
2884 }
2885
2886 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
2887         __isl_keep isl_schedule *schedule)
2888 {
2889         isl_band_list *forest;
2890
2891         forest = isl_schedule_get_band_forest(schedule);
2892
2893         p = print_band_list(p, forest);
2894
2895         isl_band_list_free(forest);
2896
2897         return p;
2898 }
2899
2900 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
2901 {
2902         isl_printer *printer;
2903
2904         if (!schedule)
2905                 return;
2906
2907         printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
2908         printer = isl_printer_print_schedule(printer, schedule);
2909
2910         isl_printer_free(printer);
2911 }