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