isl_ast_build.c

   1 /*
   2  * Copyright 2012      Ecole Normale Superieure
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege,
   7  * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
   8  */
   9
  10 #include <isl/map.h>
  11 #include <isl/aff.h>
  12 #include <isl/map.h>
  13 #include <isl_ast_build_private.h>
  14 #include <isl_ast_private.h>
  15
  16 /* Construct a map that isolates the current dimension.
  17  *
  18  * Essentially, the current dimension of "set" is moved to the single output
  19  * dimension in the result, with the current dimension in the domain replaced
  20  * by an unconstrained variable.
  21  */
  22 __isl_give isl_map *isl_ast_build_map_to_iterator(
  23         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
  24 {
  25         isl_map *map;
  26
  27         map = isl_map_from_domain(set);
  28         map = isl_map_add_dims(map, isl_dim_out, 1);
  29
  30         if (!build)
  31                 return isl_map_free(map);
  32
  33         map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
  34         map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
  35
  36         return map;
  37 }
  38
  39 /* Initialize the information derived during the AST generation to default
  40  * values for a schedule domain in "space".
  41  *
  42  * We also check that the remaining fields are not NULL so that
  43  * the calling functions don't have to perform this test.
  44  */
  45 static __isl_give isl_ast_build *isl_ast_build_init_derived(
  46         __isl_take isl_ast_build *build, __isl_take isl_space *space)
  47 {
  48         isl_ctx *ctx;
  49         isl_vec *strides;
  50
  51         build = isl_ast_build_cow(build);
  52         if (!build || !build->domain)
  53                 goto error;
  54
  55         ctx = isl_ast_build_get_ctx(build);
  56         strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
  57         strides = isl_vec_set_si(strides, 1);
  58
  59         isl_vec_free(build->strides);
  60         build->strides = strides;
  61
  62         space = isl_space_map_from_set(space);
  63         isl_multi_aff_free(build->offsets);
  64         build->offsets = isl_multi_aff_zero(isl_space_copy(space));
  65         isl_multi_aff_free(build->values);
  66         build->values = isl_multi_aff_identity(space);
  67
  68         if (!build->iterators || !build->domain || !build->generated ||
  69             !build->pending || !build->values ||
  70             !build->strides || !build->offsets || !build->options)
  71                 return isl_ast_build_free(build);
  72
  73         return build;
  74 error:
  75         isl_space_free(space);
  76         return isl_ast_build_free(build);
  77 }
  78
  79 /* Return an isl_id called "c%d", with "%d" set to "i".
  80  * If an isl_id with such a name already appears among the parameters
  81  * in build->domain, then adjust the name to "c%d_%d".
  82  */
  83 static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
  84         __isl_keep isl_ast_build *build)
  85 {
  86         int j;
  87         char name[16];
  88         isl_set *dom = build->domain;
  89
  90         snprintf(name, sizeof(name), "c%d", i);
  91         j = 0;
  92         while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
  93                 snprintf(name, sizeof(name), "c%d_%d", i, j++);
  94         return isl_id_alloc(ctx, name, NULL);
  95 }
  96
  97 /* Create an isl_ast_build with "set" as domain.
  98  *
  99  * The input set is usually a parameter domain, but we currently allow it to
 100  * be any kind of set.  We set the domain of the returned isl_ast_build
 101  * to "set" and initialize all the other field to default values.
 102  */
 103 __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
 104 {
 105         int i, n;
 106         isl_ctx *ctx;
 107         isl_space *space;
 108         isl_ast_build *build;
 109
 110         set = isl_set_compute_divs(set);
 111         if (!set)
 112                 return NULL;
 113
 114         ctx = isl_set_get_ctx(set);
 115
 116         build = isl_calloc_type(ctx, isl_ast_build);
 117         if (!build)
 118                 goto error;
 119
 120         build->ref = 1;
 121         build->domain = set;
 122         build->generated = isl_set_copy(build->domain);
 123         build->pending = isl_set_universe(isl_set_get_space(build->domain));
 124         build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
 125         n = isl_set_dim(set, isl_dim_set);
 126         build->depth = n;
 127         build->iterators = isl_id_list_alloc(ctx, n);
 128         for (i = 0; i < n; ++i) {
 129                 isl_id *id;
 130                 if (isl_set_has_dim_id(set, isl_dim_set, i))
 131                         id = isl_set_get_dim_id(set, isl_dim_set, i);
 132                 else
 133                         id = generate_name(ctx, i, build);
 134                 build->iterators = isl_id_list_add(build->iterators, id);
 135         }
 136         space = isl_set_get_space(set);
 137         if (isl_space_is_params(space))
 138                 space = isl_space_set_from_params(space);
 139
 140         return isl_ast_build_init_derived(build, space);
 141 error:
 142         isl_set_free(set);
 143         return NULL;
 144 }
 145
 146 __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
 147 {
 148         if (!build)
 149                 return NULL;
 150
 151         build->ref++;
 152         return build;
 153 }
 154
 155 __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
 156 {
 157         isl_ctx *ctx;
 158         isl_ast_build *dup;
 159
 160         if (!build)
 161                 return NULL;
 162
 163         ctx = isl_ast_build_get_ctx(build);
 164         dup = isl_calloc_type(ctx, isl_ast_build);
 165         if (!dup)
 166                 return NULL;
 167
 168         dup->ref = 1;
 169         dup->outer_pos = build->outer_pos;
 170         dup->depth = build->depth;
 171         dup->iterators = isl_id_list_copy(build->iterators);
 172         dup->domain = isl_set_copy(build->domain);
 173         dup->generated = isl_set_copy(build->generated);
 174         dup->pending = isl_set_copy(build->pending);
 175         dup->values = isl_multi_aff_copy(build->values);
 176         dup->value = isl_pw_aff_copy(build->value);
 177         dup->strides = isl_vec_copy(build->strides);
 178         dup->offsets = isl_multi_aff_copy(build->offsets);
 179         dup->executed = isl_union_map_copy(build->executed);
 180         dup->single_valued = build->single_valued;
 181         dup->options = isl_union_map_copy(build->options);
 182         dup->at_each_domain = build->at_each_domain;
 183         dup->at_each_domain_user = build->at_each_domain_user;
 184         dup->before_each_for = build->before_each_for;
 185         dup->before_each_for_user = build->before_each_for_user;
 186         dup->after_each_for = build->after_each_for;
 187         dup->after_each_for_user = build->after_each_for_user;
 188         dup->create_leaf = build->create_leaf;
 189         dup->create_leaf_user = build->create_leaf_user;
 190
 191         if (!dup->iterators || !dup->domain || !dup->generated ||
 192             !dup->pending || !dup->values ||
 193             !dup->strides || !dup->offsets || !dup->options ||
 194             (build->executed && !dup->executed) ||
 195             (build->value && !dup->value))
 196                 return isl_ast_build_free(dup);
 197
 198         return dup;
 199 }
 200
 201 /* Align the parameters of "build" to those of "model", introducing
 202  * additional parameters if needed.
 203  */
 204 __isl_give isl_ast_build *isl_ast_build_align_params(
 205         __isl_take isl_ast_build *build, __isl_take isl_space *model)
 206 {
 207         build = isl_ast_build_cow(build);
 208         if (!build)
 209                 goto error;
 210
 211         build->domain = isl_set_align_params(build->domain,
 212                                                 isl_space_copy(model));
 213         build->generated = isl_set_align_params(build->generated,
 214                                                 isl_space_copy(model));
 215         build->pending = isl_set_align_params(build->pending,
 216                                                 isl_space_copy(model));
 217         build->values = isl_multi_aff_align_params(build->values,
 218                                                 isl_space_copy(model));
 219         build->offsets = isl_multi_aff_align_params(build->offsets,
 220                                                 isl_space_copy(model));
 221         build->options = isl_union_map_align_params(build->options,
 222                                                 isl_space_copy(model));
 223         isl_space_free(model);
 224
 225         if (!build->domain || !build->values || !build->offsets ||
 226             !build->options)
 227                 return isl_ast_build_free(build);
 228
 229         return build;
 230 error:
 231         isl_space_free(model);
 232         return NULL;
 233 }
 234
 235 __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
 236 {
 237         if (!build)
 238                 return NULL;
 239
 240         if (build->ref == 1)
 241                 return build;
 242         build->ref--;
 243         return isl_ast_build_dup(build);
 244 }
 245
 246 void *isl_ast_build_free(__isl_take isl_ast_build *build)
 247 {
 248         if (!build)
 249                 return NULL;
 250
 251         if (--build->ref > 0)
 252                 return NULL;
 253
 254         isl_id_list_free(build->iterators);
 255         isl_set_free(build->domain);
 256         isl_set_free(build->generated);
 257         isl_set_free(build->pending);
 258         isl_multi_aff_free(build->values);
 259         isl_pw_aff_free(build->value);
 260         isl_vec_free(build->strides);
 261         isl_multi_aff_free(build->offsets);
 262         isl_multi_aff_free(build->schedule_map);
 263         isl_union_map_free(build->executed);
 264         isl_union_map_free(build->options);
 265
 266         free(build);
 267
 268         return NULL;
 269 }
 270
 271 isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
 272 {
 273         return build ? isl_set_get_ctx(build->domain) : NULL;
 274 }
 275
 276 /* Replace build->options by "options".
 277  */
 278 __isl_give isl_ast_build *isl_ast_build_set_options(
 279         __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
 280 {
 281         build = isl_ast_build_cow(build);
 282
 283         if (!build || !options)
 284                 goto error;
 285
 286         isl_union_map_free(build->options);
 287         build->options = options;
 288
 289         return build;
 290 error:
 291         isl_union_map_free(options);
 292         return isl_ast_build_free(build);
 293 }
 294
 295 /* Set the iterators for the next code generation.
 296  *
 297  * If we still have some iterators left from the previous code generation
 298  * (if any) or if iterators have already been set by a previous
 299  * call to this function, then we remove them first.
 300  */
 301 __isl_give isl_ast_build *isl_ast_build_set_iterators(
 302         __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
 303 {
 304         int dim, n_it;
 305
 306         build = isl_ast_build_cow(build);
 307         if (!build)
 308                 goto error;
 309
 310         dim = isl_set_dim(build->domain, isl_dim_set);
 311         n_it = isl_id_list_n_id(build->iterators);
 312         if (n_it < dim)
 313                 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
 314                         "isl_ast_build in inconsistent state", goto error);
 315         if (n_it > dim)
 316                 build->iterators = isl_id_list_drop(build->iterators,
 317                                                         dim, n_it - dim);
 318         build->iterators = isl_id_list_concat(build->iterators, iterators);
 319         if (!build->iterators)
 320                 return isl_ast_build_free(build);
 321
 322         return build;
 323 error:
 324         isl_id_list_free(iterators);
 325         return isl_ast_build_free(build);
 326 }
 327
 328 /* Set the "at_each_domain" callback of "build" to "fn".
 329  */
 330 __isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
 331         __isl_take isl_ast_build *build,
 332         __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
 333                 __isl_keep isl_ast_build *build, void *user), void *user)
 334 {
 335         build = isl_ast_build_cow(build);
 336
 337         if (!build)
 338                 return NULL;
 339
 340         build->at_each_domain = fn;
 341         build->at_each_domain_user = user;
 342
 343         return build;
 344 }
 345
 346 /* Set the "before_each_for" callback of "build" to "fn".
 347  */
 348 __isl_give isl_ast_build *isl_ast_build_set_before_each_for(
 349         __isl_take isl_ast_build *build,
 350         __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
 351                 void *user), void *user)
 352 {
 353         build = isl_ast_build_cow(build);
 354
 355         if (!build)
 356                 return NULL;
 357
 358         build->before_each_for = fn;
 359         build->before_each_for_user = user;
 360
 361         return build;
 362 }
 363
 364 /* Set the "after_each_for" callback of "build" to "fn".
 365  */
 366 __isl_give isl_ast_build *isl_ast_build_set_after_each_for(
 367         __isl_take isl_ast_build *build,
 368         __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
 369                 __isl_keep isl_ast_build *build, void *user), void *user)
 370 {
 371         build = isl_ast_build_cow(build);
 372
 373         if (!build)
 374                 return NULL;
 375
 376         build->after_each_for = fn;
 377         build->after_each_for_user = user;
 378
 379         return build;
 380 }
 381
 382 /* Set the "create_leaf" callback of "build" to "fn".
 383  */
 384 __isl_give isl_ast_build *isl_ast_build_set_create_leaf(
 385         __isl_take isl_ast_build *build,
 386         __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
 387                 void *user), void *user)
 388 {
 389         build = isl_ast_build_cow(build);
 390
 391         if (!build)
 392                 return NULL;
 393
 394         build->create_leaf = fn;
 395         build->create_leaf_user = user;
 396
 397         return build;
 398 }
 399
 400 /* Clear all information that is specific to this code generation
 401  * and that is (probably) not meaningful to any nested code generation.
 402  */
 403 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
 404         __isl_take isl_ast_build *build)
 405 {
 406         isl_space *space;
 407
 408         build = isl_ast_build_cow(build);
 409         if (!build)
 410                 return NULL;
 411
 412         space = isl_union_map_get_space(build->options);
 413         isl_union_map_free(build->options);
 414         build->options = isl_union_map_empty(space);
 415
 416         build->at_each_domain = NULL;
 417         build->at_each_domain_user = NULL;
 418         build->before_each_for = NULL;
 419         build->before_each_for_user = NULL;
 420         build->after_each_for = NULL;
 421         build->after_each_for_user = NULL;
 422         build->create_leaf = NULL;
 423         build->create_leaf_user = NULL;
 424
 425         if (!build->options)
 426                 return isl_ast_build_free(build);
 427
 428         return build;
 429 }
 430
 431 /* Have any loops been eliminated?
 432  * That is, do any of the original schedule dimensions have a fixed
 433  * value that has been substituted?
 434  */
 435 static int any_eliminated(isl_ast_build *build)
 436 {
 437         int i;
 438
 439         for (i = 0; i < build->depth; ++i)
 440                 if (isl_ast_build_has_affine_value(build, i))
 441                         return 1;
 442
 443         return 0;
 444 }
 445
 446 /* Clear build->schedule_map.
 447  * This function should be called whenever anything that might affect
 448  * the result of isl_ast_build_get_schedule_map_multi_aff changes.
 449  * In particular, it should be called when the depth is changed or
 450  * when an iterator is determined to have a fixed value.
 451  */
 452 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
 453 {
 454         if (!build)
 455                 return;
 456         isl_multi_aff_free(build->schedule_map);
 457         build->schedule_map = NULL;
 458 }
 459
 460 /* Do we need a (non-trivial) schedule map?
 461  * That is, is the internal schedule space different from
 462  * the external schedule space?
 463  *
 464  * The internal and external schedule spaces are only the same
 465  * if code has been generated for the entire schedule and if none
 466  * of the loops have been eliminated.
 467  */
 468 __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
 469 {
 470         int dim;
 471
 472         if (!build)
 473                 return -1;
 474
 475         dim = isl_set_dim(build->domain, isl_dim_set);
 476         return build->depth != dim || any_eliminated(build);
 477 }
 478
 479 /* Return a mapping from the internal schedule space to the external
 480  * schedule space in the form of an isl_multi_aff.
 481  * The internal schedule space originally corresponds to that of the
 482  * input schedule.  This may change during the code generation if
 483  * if isl_ast_build_insert_dim is ever called.
 484  * The external schedule space corresponds to the
 485  * loops that have been generated.
 486  *
 487  * Currently, the only difference between the internal schedule domain
 488  * and the external schedule domain is that some dimensions are projected
 489  * out in the external schedule domain.  In particular, the dimensions
 490  * for which no code has been generated yet and the dimensions that correspond
 491  * to eliminated loops.
 492  *
 493  * We cache a copy of the schedule_map in build->schedule_map.
 494  * The cache is cleared through isl_ast_build_reset_schedule_map
 495  * whenever anything changes that might affect the result of this function.
 496  */
 497 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
 498         __isl_keep isl_ast_build *build)
 499 {
 500         isl_space *space;
 501         isl_multi_aff *ma;
 502
 503         if (!build)
 504                 return NULL;
 505         if (build->schedule_map)
 506                 return isl_multi_aff_copy(build->schedule_map);
 507
 508         space = isl_ast_build_get_space(build, 1);
 509         space = isl_space_map_from_set(space);
 510         ma = isl_multi_aff_identity(space);
 511         if (isl_ast_build_need_schedule_map(build)) {
 512                 int i;
 513                 int dim = isl_set_dim(build->domain, isl_dim_set);
 514                 ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
 515                                         build->depth, dim - build->depth);
 516                 for (i = build->depth - 1; i >= 0; --i)
 517                         if (isl_ast_build_has_affine_value(build, i))
 518                                 ma = isl_multi_aff_drop_dims(ma,
 519                                                         isl_dim_out, i, 1);
 520         }
 521
 522         build->schedule_map = ma;
 523         return isl_multi_aff_copy(build->schedule_map);
 524 }
 525
 526 /* Return a mapping from the internal schedule space to the external
 527  * schedule space in the form of an isl_map.
 528  */
 529 __isl_give isl_map *isl_ast_build_get_schedule_map(
 530         __isl_keep isl_ast_build *build)
 531 {
 532         isl_multi_aff *ma;
 533
 534         ma = isl_ast_build_get_schedule_map_multi_aff(build);
 535         return isl_map_from_multi_aff(ma);
 536 }
 537
 538 /* Return the position of the dimension in build->domain for which
 539  * an AST node is currently being generated.
 540  */
 541 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
 542 {
 543         return build ? build->depth : -1;
 544 }
 545
 546 /* Prepare for generating code for the next level.
 547  * In particular, increase the depth and reset any information
 548  * that is local to the current depth.
 549  */
 550 __isl_give isl_ast_build *isl_ast_build_increase_depth(
 551         __isl_take isl_ast_build *build)
 552 {
 553         build = isl_ast_build_cow(build);
 554         if (!build)
 555                 return NULL;
 556         build->depth++;
 557         isl_ast_build_reset_schedule_map(build);
 558         build->value = isl_pw_aff_free(build->value);
 559         return build;
 560 }
 561
 562 void isl_ast_build_dump(__isl_keep isl_ast_build *build)
 563 {
 564         if (!build)
 565                 return;
 566
 567         fprintf(stderr, "domain: ");
 568         isl_set_dump(build->domain);
 569         fprintf(stderr, "generated: ");
 570         isl_set_dump(build->generated);
 571         fprintf(stderr, "pending: ");
 572         isl_set_dump(build->pending);
 573         fprintf(stderr, "iterators: ");
 574         isl_id_list_dump(build->iterators);
 575         fprintf(stderr, "values: ");
 576         isl_multi_aff_dump(build->values);
 577         if (build->value) {
 578                 fprintf(stderr, "value: ");
 579                 isl_pw_aff_dump(build->value);
 580         }
 581         fprintf(stderr, "strides: ");
 582         isl_vec_dump(build->strides);
 583         fprintf(stderr, "offsets: ");
 584         isl_multi_aff_dump(build->offsets);
 585 }
 586
 587 /* Initialize "build" for AST construction in schedule space "space"
 588  * in the case that build->domain is a parameter set.
 589  *
 590  * build->iterators is assumed to have been updated already.
 591  */
 592 static __isl_give isl_ast_build *isl_ast_build_init(
 593         __isl_take isl_ast_build *build, __isl_take isl_space *space)
 594 {
 595         isl_set *set;
 596
 597         build = isl_ast_build_cow(build);
 598         if (!build)
 599                 goto error;
 600
 601         set = isl_set_universe(isl_space_copy(space));
 602         build->domain = isl_set_intersect_params(isl_set_copy(set),
 603                                                     build->domain);
 604         build->pending = isl_set_intersect_params(isl_set_copy(set),
 605                                                     build->pending);
 606         build->generated = isl_set_intersect_params(set, build->generated);
 607
 608         return isl_ast_build_init_derived(build, space);
 609 error:
 610         isl_ast_build_free(build);
 611         isl_space_free(space);
 612         return NULL;
 613 }
 614
 615 /* Assign "aff" to *user and return -1, effectively extracting
 616  * the first (and presumably only) affine expression in the isl_pw_aff
 617  * on which this function is used.
 618  */
 619 static int extract_single_piece(__isl_take isl_set *set,
 620         __isl_take isl_aff *aff, void *user)
 621 {
 622         isl_aff **p = user;
 623
 624         *p = aff;
 625         isl_set_free(set);
 626
 627         return -1;
 628 }
 629
 630 /* Check if the given bounds on the current dimension imply that
 631  * this current dimension attains only a single value (in terms of
 632  * parameters and outer dimensions).
 633  * If so, we record it in build->value.
 634  * If, moreover, this value can be represented as a single affine expression,
 635  * then we also update build->values, effectively marking the current
 636  * dimension as "eliminated".
 637  *
 638  * When computing the gist of the fixed value that can be represented
 639  * as a single affine expression, it is important to only take into
 640  * account the domain constraints in the original AST build and
 641  * not the domain of the affine expression itself.
 642  * Otherwise, a [i/3] is changed into a i/3 because we know that i
 643  * is a multiple of 3, but then we end up not expressing anywhere
 644  * in the context that i is a multiple of 3.
 645  */
 646 static __isl_give isl_ast_build *update_values(
 647         __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
 648 {
 649         int sv;
 650         isl_pw_multi_aff *pma;
 651         isl_aff *aff = NULL;
 652         isl_map *it_map;
 653         isl_set *set;
 654
 655         set = isl_set_from_basic_set(bounds);
 656         set = isl_set_intersect(set, isl_set_copy(build->domain));
 657         it_map = isl_ast_build_map_to_iterator(build, set);
 658
 659         sv = isl_map_is_single_valued(it_map);
 660         if (sv < 0)
 661                 build = isl_ast_build_free(build);
 662         if (!build || !sv) {
 663                 isl_map_free(it_map);
 664                 return build;
 665         }
 666
 667         pma = isl_pw_multi_aff_from_map(it_map);
 668         build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
 669         build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
 670         build->value = isl_pw_aff_coalesce(build->value);
 671         isl_pw_multi_aff_free(pma);
 672
 673         if (!build->value)
 674                 return isl_ast_build_free(build);
 675
 676         if (isl_pw_aff_n_piece(build->value) != 1)
 677                 return build;
 678
 679         isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
 680
 681         build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
 682         if (!build->values)
 683                 return isl_ast_build_free(build);
 684         isl_ast_build_reset_schedule_map(build);
 685         return build;
 686 }
 687
 688 /* Update the AST build based on the given loop bounds for
 689  * the current dimension.
 690  *
 691  * We first make sure that the bounds do not refer to any iterators
 692  * that have already been eliminated.
 693  * Then, we check if the bounds imply that the current iterator
 694  * has a fixed value.
 695  * If they do and if this fixed value can be expressed as a single
 696  * affine expression, we eliminate the iterators from the bounds.
 697  * Note that we cannot simply plug in this single value using
 698  * isl_basic_set_preimage_multi_aff as the single value may only
 699  * be defined on a subset of the domain.  Plugging in the value
 700  * would restrict the build domain to this subset, while this
 701  * restriction may not be reflected in the generated code.
 702  * build->domain may, however, already refer to the current dimension
 703  * due an earlier call to isl_ast_build_include_stride.  If so, we need
 704  * to eliminate the dimension so that we do not introduce it in any other sets.
 705  * Finally, we intersect build->domain with the updated bounds.
 706  *
 707  * Note that the check for a fixed value in update_values requires
 708  * us to intersect the bounds with the current build domain.
 709  * When we intersect build->domain with the updated bounds in
 710  * the final step, we make sure that these updated bounds have
 711  * not been intersected with the old build->domain.
 712  * Otherwise, we would indirectly intersect the build domain with itself,
 713  * which can lead to inefficiencies, in particular if the build domain
 714  * contains any unknown divs.
 715  */
 716 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
 717         __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
 718 {
 719         isl_set *set;
 720
 721         build = isl_ast_build_cow(build);
 722         if (!build)
 723                 goto error;
 724
 725         bounds = isl_basic_set_preimage_multi_aff(bounds,
 726                                         isl_multi_aff_copy(build->values));
 727         build = update_values(build, isl_basic_set_copy(bounds));
 728         if (!build)
 729                 goto error;
 730         set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
 731         if (isl_ast_build_has_affine_value(build, build->depth)) {
 732                 set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
 733                 set = isl_set_compute_divs(set);
 734                 build->pending = isl_set_intersect(build->pending,
 735                                                         isl_set_copy(set));
 736                 if (isl_ast_build_has_stride(build, build->depth)) {
 737                         build->domain = isl_set_eliminate(build->domain,
 738                                                 isl_dim_set, build->depth, 1);
 739                         build->domain = isl_set_compute_divs(build->domain);
 740                 }
 741         } else {
 742                 isl_basic_set *generated, *pending;
 743
 744                 pending = isl_basic_set_copy(bounds);
 745                 pending = isl_basic_set_drop_constraints_involving_dims(pending,
 746                                         isl_dim_set, build->depth, 1);
 747                 build->pending = isl_set_intersect(build->pending,
 748                                         isl_set_from_basic_set(pending));
 749                 generated = isl_basic_set_copy(bounds);
 750                 generated = isl_basic_set_drop_constraints_not_involving_dims(
 751                                     generated, isl_dim_set, build->depth, 1);
 752                 build->generated = isl_set_intersect(build->generated,
 753                                         isl_set_from_basic_set(generated));
 754         }
 755         isl_basic_set_free(bounds);
 756
 757         build->domain = isl_set_intersect(build->domain, set);
 758         if (!build->domain || !build->pending || !build->generated)
 759                 return isl_ast_build_free(build);
 760
 761         return build;
 762 error:
 763         isl_ast_build_free(build);
 764         isl_basic_set_free(bounds);
 765         return NULL;
 766 }
 767
 768 /* Update build->domain based on the constraints enforced by inner loops.
 769  *
 770  * The constraints in build->pending may end up not getting generated
 771  * if they are implied by "enforced".  We therefore reconstruct
 772  * build->domain from build->generated and build->pending, dropping
 773  * those constraint in build->pending that may not get generated.
 774  */
 775 __isl_give isl_ast_build *isl_ast_build_set_enforced(
 776         __isl_take isl_ast_build *build, __isl_take isl_basic_set *enforced)
 777 {
 778         isl_set *set;
 779
 780         build = isl_ast_build_cow(build);
 781         if (!build)
 782                 goto error;
 783
 784         set = isl_set_from_basic_set(enforced);
 785         set = isl_set_gist(isl_set_copy(build->pending), set);
 786         set = isl_set_intersect(isl_set_copy(build->generated), set);
 787
 788         isl_set_free(build->domain);
 789         build->domain = set;
 790
 791         if (!build->domain)
 792                 return isl_ast_build_free(build);
 793
 794         return build;
 795 error:
 796         isl_basic_set_free(enforced);
 797         return isl_ast_build_free(build);
 798 }
 799
 800 /* Intersect build->domain with "set", where "set" is specified
 801  * in terms of the internal schedule domain.
 802  */
 803 static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
 804         __isl_take isl_ast_build *build, __isl_take isl_set *set)
 805 {
 806         build = isl_ast_build_cow(build);
 807         if (!build)
 808                 goto error;
 809
 810         set = isl_set_compute_divs(set);
 811         build->domain = isl_set_intersect(build->domain, set);
 812         build->domain = isl_set_coalesce(build->domain);
 813
 814         if (!build->domain)
 815                 return isl_ast_build_free(build);
 816
 817         return build;
 818 error:
 819         isl_ast_build_free(build);
 820         isl_set_free(set);
 821         return NULL;
 822 }
 823
 824 /* Intersect build->generated and build->domain with "set",
 825  * where "set" is specified in terms of the internal schedule domain.
 826  */
 827 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
 828         __isl_take isl_ast_build *build, __isl_take isl_set *set)
 829 {
 830         set = isl_set_compute_divs(set);
 831         build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
 832         build = isl_ast_build_cow(build);
 833         if (!build)
 834                 goto error;
 835
 836         build->generated = isl_set_intersect(build->generated, set);
 837         build->generated = isl_set_coalesce(build->generated);
 838
 839         if (!build->generated)
 840                 return isl_ast_build_free(build);
 841
 842         return build;
 843 error:
 844         isl_ast_build_free(build);
 845         isl_set_free(set);
 846         return NULL;
 847 }
 848
 849 /* Intersect build->pending and build->domain with "set",
 850  * where "set" is specified in terms of the internal schedule domain.
 851  */
 852 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
 853         __isl_take isl_ast_build *build, __isl_take isl_set *set)
 854 {
 855         set = isl_set_compute_divs(set);
 856         build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
 857         build = isl_ast_build_cow(build);
 858         if (!build)
 859                 goto error;
 860
 861         build->pending = isl_set_intersect(build->pending, set);
 862         build->pending = isl_set_coalesce(build->pending);
 863
 864         if (!build->pending)
 865                 return isl_ast_build_free(build);
 866
 867         return build;
 868 error:
 869         isl_ast_build_free(build);
 870         isl_set_free(set);
 871         return NULL;
 872 }
 873
 874 /* Intersect build->domain with "set", where "set" is specified
 875  * in terms of the external schedule domain.
 876  */
 877 __isl_give isl_ast_build *isl_ast_build_restrict(
 878         __isl_take isl_ast_build *build, __isl_take isl_set *set)
 879 {
 880         if (isl_set_is_params(set))
 881                 return isl_ast_build_restrict_generated(build, set);
 882
 883         if (isl_ast_build_need_schedule_map(build)) {
 884                 isl_multi_aff *ma;
 885                 ma = isl_ast_build_get_schedule_map_multi_aff(build);
 886                 set = isl_set_preimage_multi_aff(set, ma);
 887         }
 888         return isl_ast_build_restrict_generated(build, set);
 889 }
 890
 891 /* Replace build->executed by "executed".
 892  */
 893 __isl_give isl_ast_build *isl_ast_build_set_executed(
 894         __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
 895 {
 896         build = isl_ast_build_cow(build);
 897         if (!build)
 898                 goto error;
 899
 900         isl_union_map_free(build->executed);
 901         build->executed = executed;
 902
 903         return build;
 904 error:
 905         isl_ast_build_free(build);
 906         isl_union_map_free(executed);
 907         return NULL;
 908 }
 909
 910 /* Return a copy of the current schedule domain.
 911  */
 912 __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
 913 {
 914         return build ? isl_set_copy(build->domain) : NULL;
 915 }
 916
 917 /* Return the (schedule) space of "build".
 918  *
 919  * If "internal" is set, then this space is the space of the internal
 920  * representation of the entire schedule, including those parts for
 921  * which no code has been generated yet.
 922  *
 923  * If "internal" is not set, then this space is the external representation
 924  * of the loops generated so far.
 925  */
 926 __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
 927         int internal)
 928 {
 929         int i;
 930         int dim;
 931         isl_space *space;
 932
 933         if (!build)
 934                 return NULL;
 935
 936         space = isl_set_get_space(build->domain);
 937         if (internal)
 938                 return space;
 939
 940         if (!isl_ast_build_need_schedule_map(build))
 941                 return space;
 942
 943         dim = isl_set_dim(build->domain, isl_dim_set);
 944         space = isl_space_drop_dims(space, isl_dim_set,
 945                                     build->depth, dim - build->depth);
 946         for (i = build->depth - 1; i >= 0; --i)
 947                 if (isl_ast_build_has_affine_value(build, i))
 948                         space = isl_space_drop_dims(space, isl_dim_set, i, 1);
 949
 950         return space;
 951 }
 952
 953 /* Return the external representation of the schedule space of "build",
 954  * i.e., a space with a dimension for each loop generated so far,
 955  * with the names of the dimensions set to the loop iterators.
 956  */
 957 __isl_give isl_space *isl_ast_build_get_schedule_space(
 958         __isl_keep isl_ast_build *build)
 959 {
 960         isl_space *space;
 961         int i, skip;
 962
 963         if (!build)
 964                 return NULL;
 965
 966         space = isl_ast_build_get_space(build, 0);
 967
 968         skip = 0;
 969         for (i = 0; i < build->depth; ++i) {
 970                 isl_id *id;
 971
 972                 if (isl_ast_build_has_affine_value(build, i)) {
 973                         skip++;
 974                         continue;
 975                 }
 976
 977                 id = isl_ast_build_get_iterator_id(build, i);
 978                 space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
 979         }
 980
 981         return space;
 982 }
 983
 984 /* Return the current schedule, as stored in build->executed, in terms
 985  * of the external schedule domain.
 986  */
 987 __isl_give isl_union_map *isl_ast_build_get_schedule(
 988         __isl_keep isl_ast_build *build)
 989 {
 990         isl_union_map *executed;
 991         isl_union_map *schedule;
 992
 993         if (!build)
 994                 return NULL;
 995
 996         executed = isl_union_map_copy(build->executed);
 997         if (isl_ast_build_need_schedule_map(build)) {
 998                 isl_map *proj = isl_ast_build_get_schedule_map(build);
 999                 executed = isl_union_map_apply_domain(executed,
1000                                         isl_union_map_from_map(proj));
1001         }
1002         schedule = isl_union_map_reverse(executed);
1003
1004         return schedule;
1005 }
1006
1007 /* Return the iterator attached to the internal schedule dimension "pos".
1008  */
1009 __isl_give isl_id *isl_ast_build_get_iterator_id(
1010         __isl_keep isl_ast_build *build, int pos)
1011 {
1012         if (!build)
1013                 return NULL;
1014
1015         return isl_id_list_get_id(build->iterators, pos);
1016 }
1017
1018 /* Set the stride and offset of the current dimension to the given
1019  * value and expression.
1020  *
1021  * If we had already found a stride before, then the two strides
1022  * are combined into a single stride.
1023  *
1024  * In particular, if the new stride information is of the form
1025  *
1026  *      i = f + s (...)
1027  *
1028  * and the old stride information is of the form
1029  *
1030  *      i = f2 + s2 (...)
1031  *
1032  * then we compute the extended gcd of s and s2
1033  *
1034  *      a s + b s2 = g,
1035  *
1036  * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1037  * and the second with t2 = a s1/g.
1038  * This results in
1039  *
1040  *      i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1041  *
1042  * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1043  * is the combined stride.
1044  */
1045 static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1046         isl_int stride, __isl_take isl_aff *offset)
1047 {
1048         int pos;
1049
1050         build = isl_ast_build_cow(build);
1051         if (!build || !offset)
1052                 goto error;
1053
1054         pos = build->depth;
1055
1056         if (isl_ast_build_has_stride(build, pos)) {
1057                 isl_int stride2, a, b, g;
1058                 isl_aff *offset2;
1059
1060                 isl_int_init(stride2);
1061                 isl_int_init(a);
1062                 isl_int_init(b);
1063                 isl_int_init(g);
1064
1065                 isl_vec_get_element(build->strides, pos, &stride2);
1066                 isl_int_gcdext(g, a, b, stride, stride2);
1067                 isl_int_mul(a, a, stride);
1068                 isl_int_divexact(a, a, g);
1069                 isl_int_divexact(stride2, stride2, g);
1070                 isl_int_mul(b, b, stride2);
1071                 isl_int_mul(stride, stride, stride2);
1072
1073                 offset2 = isl_multi_aff_get_aff(build->offsets, pos);
1074                 offset2 = isl_aff_scale(offset2, a);
1075                 offset = isl_aff_scale(offset, b);
1076                 offset = isl_aff_add(offset, offset2);
1077
1078                 isl_int_clear(stride2);
1079                 isl_int_clear(a);
1080                 isl_int_clear(b);
1081                 isl_int_clear(g);
1082         }
1083
1084         build->strides = isl_vec_set_element(build->strides, pos, stride);
1085         build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1086         if (!build->strides || !build->offsets)
1087                 return isl_ast_build_free(build);
1088
1089         return build;
1090 error:
1091         isl_aff_free(offset);
1092         return isl_ast_build_free(build);
1093 }
1094
1095 /* Return a set expressing the stride constraint at the current depth.
1096  *
1097  * In particular, if the current iterator (i) is known to attain values
1098  *
1099  *      f + s a
1100  *
1101  * where f is the offset and s is the stride, then the returned set
1102  * expresses the constraint
1103  *
1104  *      (f - i) mod s = 0
1105  */
1106 __isl_give isl_set *isl_ast_build_get_stride_constraint(
1107         __isl_keep isl_ast_build *build)
1108 {
1109         isl_aff *aff;
1110         isl_set *set;
1111         isl_int stride;
1112         int pos;
1113
1114         if (!build)
1115                 return NULL;
1116
1117         pos = build->depth;
1118
1119         if (!isl_ast_build_has_stride(build, pos))
1120                 return isl_set_universe(isl_ast_build_get_space(build, 1));
1121
1122         isl_int_init(stride);
1123
1124         isl_ast_build_get_stride(build, pos, &stride);
1125         aff = isl_ast_build_get_offset(build, pos);
1126         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1127         aff = isl_aff_mod(aff, stride);
1128         set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1129
1130         isl_int_clear(stride);
1131
1132         return set;
1133 }
1134
1135 /* Return the expansion implied by the stride and offset at the current
1136  * depth.
1137  *
1138  * That is, return the mapping
1139  *
1140  *      [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1141  *              -> [i_0, ..., i_{d-1}, s * i_d + offset(i),  i_{d+1}, ...]
1142  *
1143  * where s is the stride at the current depth d and offset(i) is
1144  * the corresponding offset.
1145  */
1146 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1147         __isl_keep isl_ast_build *build)
1148 {
1149         isl_space *space;
1150         isl_multi_aff *ma;
1151         int pos;
1152         isl_aff *aff, *offset;
1153         isl_int stride;
1154
1155         if (!build)
1156                 return NULL;
1157
1158         pos = isl_ast_build_get_depth(build);
1159         space = isl_ast_build_get_space(build, 1);
1160         space = isl_space_map_from_set(space);
1161         ma = isl_multi_aff_identity(space);
1162
1163         if (!isl_ast_build_has_stride(build, pos))
1164                 return ma;
1165
1166         isl_int_init(stride);
1167         offset = isl_ast_build_get_offset(build, pos);
1168         isl_ast_build_get_stride(build, pos, &stride);
1169         aff = isl_multi_aff_get_aff(ma, pos);
1170         aff = isl_aff_scale(aff, stride);
1171         aff = isl_aff_add(aff, offset);
1172         ma = isl_multi_aff_set_aff(ma, pos, aff);
1173         isl_int_clear(stride);
1174
1175         return ma;
1176 }
1177
1178 /* Add constraints corresponding to any previously detected
1179  * stride on the current dimension to build->domain.
1180  */
1181 __isl_give isl_ast_build *isl_ast_build_include_stride(
1182         __isl_take isl_ast_build *build)
1183 {
1184         isl_set *set;
1185
1186         if (!build)
1187                 return NULL;
1188         if (!isl_ast_build_has_stride(build, build->depth))
1189                 return build;
1190         build = isl_ast_build_cow(build);
1191         if (!build)
1192                 return NULL;
1193
1194         set = isl_ast_build_get_stride_constraint(build);
1195
1196         build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1197         build->generated = isl_set_intersect(build->generated, set);
1198         if (!build->domain || !build->generated)
1199                 return isl_ast_build_free(build);
1200
1201         return build;
1202 }
1203
1204 /* Information used inside detect_stride.
1205  *
1206  * "build" may be updated by detect_stride to include stride information.
1207  * "pos" is equal to build->depth.
1208  */
1209 struct isl_detect_stride_data {
1210         isl_ast_build *build;
1211         int pos;
1212 };
1213
1214 /* Check if constraint "c" imposes any stride on dimension data->pos
1215  * and, if so, update the stride information in data->build.
1216  *
1217  * In order to impose a stride on the dimension, "c" needs to be an equality
1218  * and it needs to involve the dimension.  Note that "c" may also be
1219  * a div constraint and thus an inequality that we cannot use.
1220  *
1221  * Let c be of the form
1222  *
1223  *      h(p) + g * v * i + g * stride * f(alpha) = 0
1224  *
1225  * with h(p) an expression in terms of the parameters and outer dimensions
1226  * and f(alpha) an expression in terms of the existentially quantified
1227  * variables.  Note that the inner dimensions have been eliminated so
1228  * they do not appear in "c".
1229  *
1230  * If "stride" is not zero and not one, then it represents a non-trivial stride
1231  * on "i".  We compute a and b such that
1232  *
1233  *      a v + b stride = 1
1234  *
1235  * We have
1236  *
1237  *      g v i = -h(p) + g stride f(alpha)
1238  *
1239  *      a g v i = -a h(p) + g stride f(alpha)
1240  *
1241  *      a g v i + b g stride i = -a h(p) + g stride * (...)
1242  *
1243  *      g i = -a h(p) + g stride * (...)
1244  *
1245  *      i = -a h(p)/g + stride * (...)
1246  *
1247  * The expression "-a h(p)/g" can therefore be used as offset.
1248  */
1249 static int detect_stride(__isl_take isl_constraint *c, void *user)
1250 {
1251         struct isl_detect_stride_data *data = user;
1252         int i, n_div;
1253         isl_int v, gcd, stride, a, b, m;
1254
1255         if (!isl_constraint_is_equality(c) ||
1256             !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
1257                 isl_constraint_free(c);
1258                 return 0;
1259         }
1260
1261         isl_int_init(a);
1262         isl_int_init(b);
1263         isl_int_init(v);
1264         isl_int_init(m);
1265         isl_int_init(gcd);
1266         isl_int_init(stride);
1267
1268         isl_int_set_si(gcd, 0);
1269         n_div = isl_constraint_dim(c, isl_dim_div);
1270         for (i = 0; i < n_div; ++i) {
1271                 isl_constraint_get_coefficient(c, isl_dim_div, i, &v);
1272                 isl_int_gcd(gcd, gcd, v);
1273         }
1274
1275         isl_constraint_get_coefficient(c, isl_dim_set, data->pos, &v);
1276         isl_int_gcd(m, v, gcd);
1277         isl_int_divexact(stride, gcd, m);
1278         isl_int_divexact(v, v, m);
1279
1280         if (!isl_int_is_zero(stride) && !isl_int_is_one(stride)) {
1281                 isl_aff *aff;
1282
1283                 isl_int_gcdext(gcd, a, b, v, stride);
1284
1285                 aff = isl_constraint_get_aff(c);
1286                 for (i = 0; i < n_div; ++i)
1287                         aff = isl_aff_set_coefficient_si(aff,
1288                                                          isl_dim_div, i, 0);
1289                 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
1290                 isl_int_neg(a, a);
1291                 aff = isl_aff_scale(aff, a);
1292                 aff = isl_aff_scale_down(aff, m);
1293                 data->build = set_stride(data->build, stride, aff);
1294         }
1295
1296         isl_int_clear(stride);
1297         isl_int_clear(gcd);
1298         isl_int_clear(m);
1299         isl_int_clear(v);
1300         isl_int_clear(b);
1301         isl_int_clear(a);
1302
1303         isl_constraint_free(c);
1304         return 0;
1305 }
1306
1307 /* Check if the constraints in "set" imply any stride on the current
1308  * dimension and, if so, record the stride information in "build"
1309  * and return the updated "build".
1310  *
1311  * We compute the affine hull and then check if any of the constraints
1312  * in the hull imposes any stride on the current dimension.
1313  *
1314  * We assume that inner dimensions have been eliminated from "set"
1315  * by the caller.  This is needed because the common stride
1316  * may be imposed by different inner dimensions on different parts of
1317  * the domain.
1318  */
1319 __isl_give isl_ast_build *isl_ast_build_detect_strides(
1320         __isl_take isl_ast_build *build, __isl_take isl_set *set)
1321 {
1322         isl_basic_set *hull;
1323         struct isl_detect_stride_data data;
1324
1325         if (!build)
1326                 goto error;
1327
1328         data.build = build;
1329         data.pos = isl_ast_build_get_depth(build);
1330         hull = isl_set_affine_hull(set);
1331
1332         if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1333                 data.build = isl_ast_build_free(data.build);
1334
1335         isl_basic_set_free(hull);
1336         return data.build;
1337 error:
1338         isl_set_free(set);
1339         return NULL;
1340 }
1341
1342 struct isl_ast_build_involves_data {
1343         int depth;
1344         int involves;
1345 };
1346
1347 /* Check if "map" involves the input dimension data->depth.
1348  */
1349 static int involves_depth(__isl_take isl_map *map, void *user)
1350 {
1351         struct isl_ast_build_involves_data *data = user;
1352
1353         data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1354         isl_map_free(map);
1355
1356         if (data->involves < 0 || data->involves)
1357                 return -1;
1358         return 0;
1359 }
1360
1361 /* Do any options depend on the value of the dimension at the current depth?
1362  */
1363 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1364 {
1365         struct isl_ast_build_involves_data data;
1366
1367         if (!build)
1368                 return -1;
1369
1370         data.depth = build->depth;
1371         data.involves = 0;
1372
1373         if (isl_union_map_foreach_map(build->options,
1374                                         &involves_depth, &data) < 0) {
1375                 if (data.involves < 0 || !data.involves)
1376                         return -1;
1377         }
1378
1379         return data.involves;
1380 }
1381
1382 /* Construct the map
1383  *
1384  *      { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1385  *
1386  * with "space" the parameter space of the constructed map.
1387  */
1388 static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1389         int pos)
1390 {
1391         isl_constraint *c;
1392         isl_basic_map *bmap1, *bmap2;
1393
1394         space = isl_space_set_from_params(space);
1395         space = isl_space_add_dims(space, isl_dim_set, 1);
1396         space = isl_space_map_from_set(space);
1397         c = isl_equality_alloc(isl_local_space_from_space(space));
1398         c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1399         c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1400         bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1401         c = isl_constraint_set_constant_si(c, 1);
1402         bmap2 = isl_basic_map_from_constraint(c);
1403
1404         bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1405         bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1406
1407         return isl_basic_map_union(bmap1, bmap2);
1408 }
1409
1410 static const char *option_str[] = {
1411         [atomic] = "atomic",
1412         [unroll] = "unroll",
1413         [separate] = "separate"
1414 };
1415
1416 /* Update the "options" to reflect the insertion of a dimension
1417  * at position "pos" in the schedule domain space.
1418  * "space" is the original domain space before the insertion and
1419  * may be named and/or structured.
1420  *
1421  * The (relevant) input options all have "space" as domain, which
1422  * has to be mapped to the extended space.
1423  * The values of the ranges also refer to the schedule domain positions
1424  * and they therefore also need to be adjusted.  In particular, values
1425  * smaller than pos do not need to change, while values greater than or
1426  * equal to pos need to be incremented.
1427  * That is, we need to apply the following map.
1428  *
1429  *      { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1430  *        unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1431  *        separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1432  *        separation_class[[i] -> [c]]
1433  *              -> separation_class[[i] -> [c]] : i < pos;
1434  *        separation_class[[i] -> [c]]
1435  *              -> separation_class[[i + 1] -> [c]] : i >= pos }
1436  */
1437 static __isl_give isl_union_map *options_insert_dim(
1438         __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1439 {
1440         isl_map *map;
1441         isl_union_map *insertion;
1442         enum isl_ast_build_domain_type type;
1443         const char *name = "separation_class";
1444
1445         space = isl_space_map_from_set(space);
1446         map = isl_map_identity(space);
1447         map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1448         options = isl_union_map_apply_domain(options,
1449                                                 isl_union_map_from_map(map));
1450
1451         if (!options)
1452                 return NULL;
1453
1454         map = construct_insertion_map(isl_union_map_get_space(options), pos);
1455
1456         insertion = isl_union_map_empty(isl_union_map_get_space(options));
1457
1458         for (type = atomic; type <= separate; ++type) {
1459                 isl_map *map_type = isl_map_copy(map);
1460                 const char *name = option_str[type];
1461                 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1462                 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1463                 insertion = isl_union_map_add_map(insertion, map_type);
1464         }
1465
1466         map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1467         map = isl_map_set_tuple_name(map, isl_dim_in, name);
1468         map = isl_map_set_tuple_name(map, isl_dim_out, name);
1469         insertion = isl_union_map_add_map(insertion, map);
1470
1471         options = isl_union_map_apply_range(options, insertion);
1472
1473         return options;
1474 }
1475
1476 /* Insert a single dimension in the schedule domain at position "pos".
1477  * The new dimension is given an isl_id with the empty string as name.
1478  *
1479  * The main difficulty is updating build->options to reflect the
1480  * extra dimension.  This is handled in options_insert_dim.
1481  *
1482  * Note that because of the dimension manipulations, the resulting
1483  * schedule domain space will always be unnamed and unstructured.
1484  * However, the original schedule domain space may be named and/or
1485  * structured, so we have to take this possibility into account
1486  * while performing the transformations.
1487  */
1488 __isl_give isl_ast_build *isl_ast_build_insert_dim(
1489         __isl_take isl_ast_build *build, int pos)
1490 {
1491         isl_ctx *ctx;
1492         isl_space *space, *ma_space;
1493         isl_id *id;
1494         isl_multi_aff *ma;
1495
1496         build = isl_ast_build_cow(build);
1497         if (!build)
1498                 return NULL;
1499
1500         ctx = isl_ast_build_get_ctx(build);
1501         id = isl_id_alloc(ctx, "", NULL);
1502         space = isl_ast_build_get_space(build, 1);
1503         build->iterators = isl_id_list_insert(build->iterators, pos, id);
1504         build->domain = isl_set_insert_dims(build->domain,
1505                                                 isl_dim_set, pos, 1);
1506         build->generated = isl_set_insert_dims(build->generated,
1507                                                 isl_dim_set, pos, 1);
1508         build->pending = isl_set_insert_dims(build->pending,
1509                                                 isl_dim_set, pos, 1);
1510         build->strides = isl_vec_insert_els(build->strides, pos, 1);
1511         build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1512         ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1513         ma_space = isl_space_set_from_params(ma_space);
1514         ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1515         ma_space = isl_space_map_from_set(ma_space);
1516         ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1517         build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1518         ma = isl_multi_aff_identity(ma_space);
1519         build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1520         build->options = options_insert_dim(build->options, space, pos);
1521
1522         if (!build->iterators || !build->domain || !build->generated ||
1523             !build->pending || !build->values ||
1524             !build->strides || !build->offsets || !build->options)
1525                 return isl_ast_build_free(build);
1526
1527         return build;
1528 }
1529
1530 /* Scale down the current dimension by a factor of "m".
1531  * "umap" is an isl_union_map that implements the scaling down.
1532  * That is, it is of the form
1533  *
1534  *      { [.... i ....] -> [.... i' ....] : i = m i' }
1535  *
1536  * This function is called right after the strides have been
1537  * detected, but before any constraints on the current dimension
1538  * have been included in build->domain.
1539  * We therefore only need to update stride, offset and the options.
1540  */
1541 __isl_give isl_ast_build *isl_ast_build_scale_down(
1542         __isl_take isl_ast_build *build, isl_int m,
1543         __isl_take isl_union_map *umap)
1544 {
1545         isl_aff *aff;
1546         isl_int v;
1547         int depth;
1548
1549         build = isl_ast_build_cow(build);
1550         if (!build || !umap)
1551                 goto error;
1552
1553         depth = build->depth;
1554
1555         isl_int_init(v);
1556         if (isl_vec_get_element(build->strides, depth, &v) < 0)
1557                 build->strides = isl_vec_free(build->strides);
1558         isl_int_divexact(v, v, m);
1559         build->strides = isl_vec_set_element(build->strides, depth, v);
1560         isl_int_clear(v);
1561
1562         aff = isl_multi_aff_get_aff(build->offsets, depth);
1563         aff = isl_aff_scale_down(aff, m);
1564         build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1565         build->options = isl_union_map_apply_domain(build->options, umap);
1566         if (!build->strides || !build->offsets || !build->options)
1567                 return isl_ast_build_free(build);
1568
1569         return build;
1570 error:
1571         isl_union_map_free(umap);
1572         return isl_ast_build_free(build);
1573 }
1574
1575 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1576  * If an isl_id with such a name already appears among the parameters
1577  * in build->domain, then adjust the name to "c%d_%d".
1578  */
1579 static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1580         __isl_keep isl_ast_build *build)
1581 {
1582         int i;
1583         isl_id_list *names;
1584
1585         names = isl_id_list_alloc(ctx, n);
1586         for (i = 0; i < n; ++i) {
1587                 isl_id *id;
1588
1589                 id = generate_name(ctx, first + i, build);
1590                 names = isl_id_list_add(names, id);
1591         }
1592
1593         return names;
1594 }
1595
1596 /* Embed "options" into the given isl_ast_build space.
1597  *
1598  * This function is called from within a nested call to
1599  * isl_ast_build_ast_from_schedule.
1600  * "options" refers to the additional schedule,
1601  * while space refers to both the space of the outer isl_ast_build and
1602  * that of the additional schedule.
1603  * Specifically, space is of the form
1604  *
1605  *      [I -> S]
1606  *
1607  * while options lives in the space(s)
1608  *
1609  *      S -> *
1610  *
1611  * We compute
1612  *
1613  *      [I -> S] -> S
1614  *
1615  * and compose this with options, to obtain the new options
1616  * living in the space(s)
1617  *
1618  *      [I -> S] -> *
1619  */
1620 static __isl_give isl_union_map *embed_options(
1621         __isl_take isl_union_map *options, __isl_take isl_space *space)
1622 {
1623         isl_map *map;
1624
1625         map = isl_map_universe(isl_space_unwrap(space));
1626         map = isl_map_range_map(map);
1627
1628         options = isl_union_map_apply_range(
1629                                 isl_union_map_from_map(map), options);
1630
1631         return options;
1632 }
1633
1634 /* Update "build" for use in a (possibly nested) code generation.  That is,
1635  * extend "build" from an AST build on some domain O to an AST build
1636  * on domain [O -> S], with S corresponding to "space".
1637  * If the original domain is a parameter domain, then the new domain is
1638  * simply S.
1639  * "iterators" is a list of iterators for S, but the number of elements
1640  * may be smaller or greater than the number of set dimensions of S.
1641  * If "keep_iterators" is set, then any extra ids in build->iterators
1642  * are reused for S.  Otherwise, these extra ids are dropped.
1643  *
1644  * We first update build->outer_pos to the current depth.
1645  * This depth is zero in case this is the outermost code generation.
1646  *
1647  * We then add additional ids such that the number of iterators is at least
1648  * equal to the dimension of the new build domain.
1649  *
1650  * If the original domain is parametric, then we are constructing
1651  * an isl_ast_build for the outer code generation and we pass control
1652  * to isl_ast_build_init.
1653  *
1654  * Otherwise, we adjust the fields of "build" to include "space".
1655  */
1656 __isl_give isl_ast_build *isl_ast_build_product(
1657         __isl_take isl_ast_build *build, __isl_take isl_space *space)
1658 {
1659         isl_ctx *ctx;
1660         isl_vec *strides;
1661         isl_set *set;
1662         isl_multi_aff *embedding;
1663         int dim, n_it;
1664
1665         build = isl_ast_build_cow(build);
1666         if (!build)
1667                 goto error;
1668
1669         build->outer_pos = build->depth;
1670
1671         ctx = isl_ast_build_get_ctx(build);
1672         dim = isl_set_dim(build->domain, isl_dim_set);
1673         dim += isl_space_dim(space, isl_dim_set);
1674         n_it = isl_id_list_n_id(build->iterators);
1675         if (n_it < dim) {
1676                 isl_id_list *l;
1677                 l = generate_names(ctx, dim - n_it, n_it, build);
1678                 build->iterators = isl_id_list_concat(build->iterators, l);
1679         }
1680
1681         if (isl_set_is_params(build->domain))
1682                 return isl_ast_build_init(build, space);
1683
1684         set = isl_set_universe(isl_space_copy(space));
1685         build->domain = isl_set_product(build->domain, isl_set_copy(set));
1686         build->pending = isl_set_product(build->pending, isl_set_copy(set));
1687         build->generated = isl_set_product(build->generated, set);
1688
1689         strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1690         strides = isl_vec_set_si(strides, 1);
1691         build->strides = isl_vec_concat(build->strides, strides);
1692
1693         space = isl_space_map_from_set(space);
1694         build->offsets = isl_multi_aff_align_params(build->offsets,
1695                                                     isl_space_copy(space));
1696         build->offsets = isl_multi_aff_product(build->offsets,
1697                                 isl_multi_aff_zero(isl_space_copy(space)));
1698         build->values = isl_multi_aff_align_params(build->values,
1699                                                     isl_space_copy(space));
1700         embedding = isl_multi_aff_identity(space);
1701         build->values = isl_multi_aff_product(build->values, embedding);
1702
1703         space = isl_ast_build_get_space(build, 1);
1704         build->options = embed_options(build->options, space);
1705
1706         if (!build->iterators || !build->domain || !build->generated ||
1707             !build->pending || !build->values ||
1708             !build->strides || !build->offsets || !build->options)
1709                 return isl_ast_build_free(build);
1710
1711         return build;
1712 error:
1713         isl_ast_build_free(build);
1714         isl_space_free(space);
1715         return NULL;
1716 }
1717
1718 /* Does "aff" only attain non-negative values over build->domain?
1719  * That is, does it not attain any negative values?
1720  */
1721 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
1722         __isl_keep isl_aff *aff)
1723 {
1724         isl_set *test;
1725         int empty;
1726
1727         if (!build)
1728                 return -1;
1729
1730         aff = isl_aff_copy(aff);
1731         test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
1732         test = isl_set_intersect(test, isl_set_copy(build->domain));
1733         empty = isl_set_is_empty(test);
1734         isl_set_free(test);
1735
1736         return empty;
1737 }
1738
1739 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1740  */
1741 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
1742 {
1743         isl_int v;
1744         int has_stride;
1745
1746         if (!build)
1747                 return -1;
1748
1749         isl_int_init(v);
1750         isl_vec_get_element(build->strides, pos, &v);
1751         has_stride = !isl_int_is_one(v);
1752         isl_int_clear(v);
1753
1754         return has_stride;
1755 }
1756
1757 /* Given that the dimension at position "pos" takes on values
1758  *
1759  *      f + s a
1760  *
1761  * with a an integer, return s through *stride.
1762  */
1763 int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
1764         isl_int *stride)
1765 {
1766         if (!build)
1767                 return -1;
1768
1769         isl_vec_get_element(build->strides, pos, stride);
1770
1771         return 0;
1772 }
1773
1774 /* Given that the dimension at position "pos" takes on values
1775  *
1776  *      f + s a
1777  *
1778  * with a an integer, return f.
1779  */
1780 __isl_give isl_aff *isl_ast_build_get_offset(
1781         __isl_keep isl_ast_build *build, int pos)
1782 {
1783         if (!build)
1784                 return NULL;
1785
1786         return isl_multi_aff_get_aff(build->offsets, pos);
1787 }
1788
1789 /* Is the dimension at position "pos" known to attain only a single
1790  * value that, moreover, can be described by a single affine expression
1791  * in terms of the outer dimensions and parameters?
1792  *
1793  * If not, then the correponding affine expression in build->values
1794  * is set to be equal to the same input dimension.
1795  * Otherwise, it is set to the requested expression in terms of
1796  * outer dimensions and parameters.
1797  */
1798 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
1799         int pos)
1800 {
1801         isl_aff *aff;
1802         int involves;
1803
1804         if (!build)
1805                 return -1;
1806
1807         aff = isl_multi_aff_get_aff(build->values, pos);
1808         involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
1809         isl_aff_free(aff);
1810
1811         if (involves < 0)
1812                 return -1;
1813
1814         return !involves;
1815 }
1816
1817 /* Plug in the known values (fixed affine expressions in terms of
1818  * parameters and outer loop iterators) of all loop iterators
1819  * in the domain of "umap".
1820  *
1821  * We simply precompose "umap" with build->values.
1822  */
1823 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
1824         __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
1825 {
1826         isl_multi_aff *values;
1827
1828         if (!build)
1829                 return isl_union_map_free(umap);
1830
1831         values = isl_multi_aff_copy(build->values);
1832         umap = isl_union_map_preimage_domain_multi_aff(umap, values);
1833
1834         return umap;
1835 }
1836
1837 /* Is the current dimension known to attain only a single value?
1838  */
1839 int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
1840 {
1841         if (!build)
1842                 return -1;
1843
1844         return build->value != NULL;
1845 }
1846
1847 /* Simplify the basic set "bset" based on what we know about
1848  * the iterators of already generated loops.
1849  *
1850  * "bset" is assumed to live in the (internal) schedule domain.
1851  */
1852 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
1853         __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1854 {
1855         if (!build)
1856                 goto error;
1857
1858         bset = isl_basic_set_preimage_multi_aff(bset,
1859                                         isl_multi_aff_copy(build->values));
1860         bset = isl_basic_set_gist(bset,
1861                         isl_set_simple_hull(isl_set_copy(build->domain)));
1862
1863         return bset;
1864 error:
1865         isl_basic_set_free(bset);
1866         return NULL;
1867 }
1868
1869 /* Simplify the set "set" based on what we know about
1870  * the iterators of already generated loops.
1871  *
1872  * "set" is assumed to live in the (internal) schedule domain.
1873  */
1874 __isl_give isl_set *isl_ast_build_compute_gist(
1875         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1876 {
1877         if (!build)
1878                 goto error;
1879
1880         set = isl_set_preimage_multi_aff(set,
1881                                         isl_multi_aff_copy(build->values));
1882         set = isl_set_gist(set, isl_set_copy(build->domain));
1883
1884         return set;
1885 error:
1886         isl_set_free(set);
1887         return NULL;
1888 }
1889
1890 /* Simplify the map "map" based on what we know about
1891  * the iterators of already generated loops.
1892  *
1893  * The domain of "map" is assumed to live in the (internal) schedule domain.
1894  */
1895 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
1896         __isl_keep isl_ast_build *build, __isl_take isl_map *map)
1897 {
1898         if (!build)
1899                 goto error;
1900
1901         map = isl_map_gist_domain(map, isl_set_copy(build->domain));
1902
1903         return map;
1904 error:
1905         isl_map_free(map);
1906         return NULL;
1907 }
1908
1909 /* Simplify the affine expression "aff" based on what we know about
1910  * the iterators of already generated loops.
1911  *
1912  * The domain of "aff" is assumed to live in the (internal) schedule domain.
1913  */
1914 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
1915         __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
1916 {
1917         if (!build)
1918                 goto error;
1919
1920         aff = isl_aff_gist(aff, isl_set_copy(build->domain));
1921
1922         return aff;
1923 error:
1924         isl_aff_free(aff);
1925         return NULL;
1926 }
1927
1928 /* Simplify the piecewise affine expression "aff" based on what we know about
1929  * the iterators of already generated loops.
1930  *
1931  * The domain of "pa" is assumed to live in the (internal) schedule domain.
1932  */
1933 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
1934         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1935 {
1936         if (!build)
1937                 goto error;
1938
1939         pa = isl_pw_aff_pullback_multi_aff(pa,
1940                                         isl_multi_aff_copy(build->values));
1941         pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
1942
1943         return pa;
1944 error:
1945         isl_pw_aff_free(pa);
1946         return NULL;
1947 }
1948
1949 /* Simplify the piecewise multi-affine expression "aff" based on what
1950  * we know about the iterators of already generated loops.
1951  *
1952  * The domain of "pma" is assumed to live in the (internal) schedule domain.
1953  */
1954 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
1955         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1956 {
1957         if (!build)
1958                 goto error;
1959
1960         pma = isl_pw_multi_aff_pullback_multi_aff(pma,
1961                                         isl_multi_aff_copy(build->values));
1962         pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
1963
1964         return pma;
1965 error:
1966         isl_pw_multi_aff_free(pma);
1967         return NULL;
1968 }
1969
1970 /* Extract the schedule domain of the given type from build->options
1971  * at the current depth.
1972  *
1973  * In particular, find the subset of build->options that is of
1974  * the following form
1975  *
1976  *      schedule_domain -> type[depth]
1977  *
1978  * and return the corresponding domain, after eliminating inner dimensions
1979  * and divs that depend on the current dimension.
1980  *
1981  * Note that the domain of build->options has been reformulated
1982  * in terms of the internal build space in embed_options,
1983  * but the position is still that within the current code generation.
1984  */
1985 __isl_give isl_set *isl_ast_build_get_option_domain(
1986         __isl_keep isl_ast_build *build,
1987         enum isl_ast_build_domain_type type)
1988 {
1989         const char *name;
1990         isl_space *space;
1991         isl_map *option;
1992         isl_set *domain;
1993         int local_pos;
1994
1995         if (!build)
1996                 return NULL;
1997
1998         name = option_str[type];
1999         local_pos = build->depth - build->outer_pos;
2000
2001         space = isl_ast_build_get_space(build, 1);
2002         space = isl_space_from_domain(space);
2003         space = isl_space_add_dims(space, isl_dim_out, 1);
2004         space = isl_space_set_tuple_name(space, isl_dim_out, name);
2005
2006         option = isl_union_map_extract_map(build->options, space);
2007         option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2008
2009         domain = isl_map_domain(option);
2010         domain = isl_ast_build_eliminate(build, domain);
2011
2012         return domain;
2013 }
2014
2015 /* Extract the separation class mapping at the current depth.
2016  *
2017  * In particular, find and return the subset of build->options that is of
2018  * the following form
2019  *
2020  *      schedule_domain -> separation_class[[depth] -> [class]]
2021  *
2022  * The caller is expected to eliminate inner dimensions from the domain.
2023  *
2024  * Note that the domain of build->options has been reformulated
2025  * in terms of the internal build space in embed_options,
2026  * but the position is still that within the current code generation.
2027  */
2028 __isl_give isl_map *isl_ast_build_get_separation_class(
2029         __isl_keep isl_ast_build *build)
2030 {
2031         isl_ctx *ctx;
2032         isl_space *space_sep, *space;
2033         isl_map *res;
2034         int local_pos;
2035
2036         if (!build)
2037                 return NULL;
2038
2039         local_pos = build->depth - build->outer_pos;
2040         ctx = isl_ast_build_get_ctx(build);
2041         space_sep = isl_space_alloc(ctx, 0, 1, 1);
2042         space_sep = isl_space_wrap(space_sep);
2043         space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2044                                                 "separation_class");
2045         space = isl_ast_build_get_space(build, 1);
2046         space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2047         space = isl_space_map_from_domain_and_range(space, space_sep);
2048
2049         res = isl_union_map_extract_map(build->options, space);
2050         res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2051         res = isl_map_coalesce(res);
2052
2053         return res;
2054 }
2055
2056 /* Eliminate dimensions inner to the current dimension.
2057  */
2058 __isl_give isl_set *isl_ast_build_eliminate_inner(
2059         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2060 {
2061         int dim;
2062         int depth;
2063
2064         if (!build)
2065                 return isl_set_free(set);
2066
2067         dim = isl_set_dim(set, isl_dim_set);
2068         depth = build->depth;
2069         set = isl_set_detect_equalities(set);
2070         set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2071
2072         return set;
2073 }
2074
2075 /* Eliminate unknown divs and divs that depend on the current dimension.
2076  *
2077  * Note that during the elimination of unknown divs, we may discover
2078  * an explicit representation of some other unknown divs, which may
2079  * depend on the current dimension.  We therefore need to eliminate
2080  * unknown divs first.
2081  */
2082 __isl_give isl_set *isl_ast_build_eliminate_divs(
2083         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2084 {
2085         int depth;
2086
2087         if (!build)
2088                 return isl_set_free(set);
2089
2090         set = isl_set_remove_unknown_divs(set);
2091         depth = build->depth;
2092         set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2093
2094         return set;
2095 }
2096
2097 /* Eliminate dimensions inner to the current dimension as well as
2098  * unknown divs and divs that depend on the current dimension.
2099  * The result then consists only of constraints that are independent
2100  * of the current dimension and upper and lower bounds on the current
2101  * dimension.
2102  */
2103 __isl_give isl_set *isl_ast_build_eliminate(
2104         __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2105 {
2106         domain = isl_ast_build_eliminate_inner(build, domain);
2107         domain = isl_ast_build_eliminate_divs(build, domain);
2108         return domain;
2109 }
2110
2111 /* Replace build->single_valued by "sv".
2112  */
2113 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2114         __isl_take isl_ast_build *build, int sv)
2115 {
2116         if (!build)
2117                 return build;
2118         if (build->single_valued == sv)
2119                 return build;
2120         build = isl_ast_build_cow(build);
2121         if (!build)
2122                 return build;
2123         build->single_valued = sv;
2124
2125         return build;
2126 }