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