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