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