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