isl_schedule.c

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