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_int 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         isl_int_init(stride);
1124
1125         isl_ast_build_get_stride(build, pos, &stride);
1126         aff = isl_ast_build_get_offset(build, pos);
1127         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1128         aff = isl_aff_mod(aff, stride);
1129         set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1130
1131         isl_int_clear(stride);
1132
1133         return set;
1134 }
1135
1136 /* Return the expansion implied by the stride and offset at the current
1137  * depth.
1138  *
1139  * That is, return the mapping
1140  *
1141  *      [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1142  *              -> [i_0, ..., i_{d-1}, s * i_d + offset(i),  i_{d+1}, ...]
1143  *
1144  * where s is the stride at the current depth d and offset(i) is
1145  * the corresponding offset.
1146  */
1147 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1148         __isl_keep isl_ast_build *build)
1149 {
1150         isl_space *space;
1151         isl_multi_aff *ma;
1152         int pos;
1153         isl_aff *aff, *offset;
1154         isl_int stride;
1155
1156         if (!build)
1157                 return NULL;
1158
1159         pos = isl_ast_build_get_depth(build);
1160         space = isl_ast_build_get_space(build, 1);
1161         space = isl_space_map_from_set(space);
1162         ma = isl_multi_aff_identity(space);
1163
1164         if (!isl_ast_build_has_stride(build, pos))
1165                 return ma;
1166
1167         isl_int_init(stride);
1168         offset = isl_ast_build_get_offset(build, pos);
1169         isl_ast_build_get_stride(build, pos, &stride);
1170         aff = isl_multi_aff_get_aff(ma, pos);
1171         aff = isl_aff_scale(aff, stride);
1172         aff = isl_aff_add(aff, offset);
1173         ma = isl_multi_aff_set_aff(ma, pos, aff);
1174         isl_int_clear(stride);
1175
1176         return ma;
1177 }
1178
1179 /* Add constraints corresponding to any previously detected
1180  * stride on the current dimension to build->domain.
1181  */
1182 __isl_give isl_ast_build *isl_ast_build_include_stride(
1183         __isl_take isl_ast_build *build)
1184 {
1185         isl_set *set;
1186
1187         if (!build)
1188                 return NULL;
1189         if (!isl_ast_build_has_stride(build, build->depth))
1190                 return build;
1191         build = isl_ast_build_cow(build);
1192         if (!build)
1193                 return NULL;
1194
1195         set = isl_ast_build_get_stride_constraint(build);
1196
1197         build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1198         build->generated = isl_set_intersect(build->generated, set);
1199         if (!build->domain || !build->generated)
1200                 return isl_ast_build_free(build);
1201
1202         return build;
1203 }
1204
1205 /* Information used inside detect_stride.
1206  *
1207  * "build" may be updated by detect_stride to include stride information.
1208  * "pos" is equal to build->depth.
1209  */
1210 struct isl_detect_stride_data {
1211         isl_ast_build *build;
1212         int pos;
1213 };
1214
1215 /* Check if constraint "c" imposes any stride on dimension data->pos
1216  * and, if so, update the stride information in data->build.
1217  *
1218  * In order to impose a stride on the dimension, "c" needs to be an equality
1219  * and it needs to involve the dimension.  Note that "c" may also be
1220  * a div constraint and thus an inequality that we cannot use.
1221  *
1222  * Let c be of the form
1223  *
1224  *      h(p) + g * v * i + g * stride * f(alpha) = 0
1225  *
1226  * with h(p) an expression in terms of the parameters and outer dimensions
1227  * and f(alpha) an expression in terms of the existentially quantified
1228  * variables.  Note that the inner dimensions have been eliminated so
1229  * they do not appear in "c".
1230  *
1231  * If "stride" is not zero and not one, then it represents a non-trivial stride
1232  * on "i".  We compute a and b such that
1233  *
1234  *      a v + b stride = 1
1235  *
1236  * We have
1237  *
1238  *      g v i = -h(p) + g stride f(alpha)
1239  *
1240  *      a g v i = -a h(p) + g stride f(alpha)
1241  *
1242  *      a g v i + b g stride i = -a h(p) + g stride * (...)
1243  *
1244  *      g i = -a h(p) + g stride * (...)
1245  *
1246  *      i = -a h(p)/g + stride * (...)
1247  *
1248  * The expression "-a h(p)/g" can therefore be used as offset.
1249  */
1250 static int detect_stride(__isl_take isl_constraint *c, void *user)
1251 {
1252         struct isl_detect_stride_data *data = user;
1253         int i, n_div;
1254         isl_int v, gcd, stride, a, b, m;
1255
1256         if (!isl_constraint_is_equality(c) ||
1257             !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
1258                 isl_constraint_free(c);
1259                 return 0;
1260         }
1261
1262         isl_int_init(a);
1263         isl_int_init(b);
1264         isl_int_init(v);
1265         isl_int_init(m);
1266         isl_int_init(gcd);
1267         isl_int_init(stride);
1268
1269         isl_int_set_si(gcd, 0);
1270         n_div = isl_constraint_dim(c, isl_dim_div);
1271         for (i = 0; i < n_div; ++i) {
1272                 isl_constraint_get_coefficient(c, isl_dim_div, i, &v);
1273                 isl_int_gcd(gcd, gcd, v);
1274         }
1275
1276         isl_constraint_get_coefficient(c, isl_dim_set, data->pos, &v);
1277         isl_int_gcd(m, v, gcd);
1278         isl_int_divexact(stride, gcd, m);
1279         isl_int_divexact(v, v, m);
1280
1281         if (!isl_int_is_zero(stride) && !isl_int_is_one(stride)) {
1282                 isl_aff *aff;
1283
1284                 isl_int_gcdext(gcd, a, b, v, stride);
1285
1286                 aff = isl_constraint_get_aff(c);
1287                 for (i = 0; i < n_div; ++i)
1288                         aff = isl_aff_set_coefficient_si(aff,
1289                                                          isl_dim_div, i, 0);
1290                 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
1291                 isl_int_neg(a, a);
1292                 aff = isl_aff_scale(aff, a);
1293                 aff = isl_aff_scale_down(aff, m);
1294                 data->build = set_stride(data->build, stride, aff);
1295         }
1296
1297         isl_int_clear(stride);
1298         isl_int_clear(gcd);
1299         isl_int_clear(m);
1300         isl_int_clear(v);
1301         isl_int_clear(b);
1302         isl_int_clear(a);
1303
1304         isl_constraint_free(c);
1305         return 0;
1306 }
1307
1308 /* Check if the constraints in "set" imply any stride on the current
1309  * dimension and, if so, record the stride information in "build"
1310  * and return the updated "build".
1311  *
1312  * We compute the affine hull and then check if any of the constraints
1313  * in the hull imposes any stride on the current dimension.
1314  *
1315  * We assume that inner dimensions have been eliminated from "set"
1316  * by the caller.  This is needed because the common stride
1317  * may be imposed by different inner dimensions on different parts of
1318  * the domain.
1319  */
1320 __isl_give isl_ast_build *isl_ast_build_detect_strides(
1321         __isl_take isl_ast_build *build, __isl_take isl_set *set)
1322 {
1323         isl_basic_set *hull;
1324         struct isl_detect_stride_data data;
1325
1326         if (!build)
1327                 goto error;
1328
1329         data.build = build;
1330         data.pos = isl_ast_build_get_depth(build);
1331         hull = isl_set_affine_hull(set);
1332
1333         if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1334                 data.build = isl_ast_build_free(data.build);
1335
1336         isl_basic_set_free(hull);
1337         return data.build;
1338 error:
1339         isl_set_free(set);
1340         return NULL;
1341 }
1342
1343 struct isl_ast_build_involves_data {
1344         int depth;
1345         int involves;
1346 };
1347
1348 /* Check if "map" involves the input dimension data->depth.
1349  */
1350 static int involves_depth(__isl_take isl_map *map, void *user)
1351 {
1352         struct isl_ast_build_involves_data *data = user;
1353
1354         data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1355         isl_map_free(map);
1356
1357         if (data->involves < 0 || data->involves)
1358                 return -1;
1359         return 0;
1360 }
1361
1362 /* Do any options depend on the value of the dimension at the current depth?
1363  */
1364 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1365 {
1366         struct isl_ast_build_involves_data data;
1367
1368         if (!build)
1369                 return -1;
1370
1371         data.depth = build->depth;
1372         data.involves = 0;
1373
1374         if (isl_union_map_foreach_map(build->options,
1375                                         &involves_depth, &data) < 0) {
1376                 if (data.involves < 0 || !data.involves)
1377                         return -1;
1378         }
1379
1380         return data.involves;
1381 }
1382
1383 /* Construct the map
1384  *
1385  *      { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1386  *
1387  * with "space" the parameter space of the constructed map.
1388  */
1389 static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1390         int pos)
1391 {
1392         isl_constraint *c;
1393         isl_basic_map *bmap1, *bmap2;
1394
1395         space = isl_space_set_from_params(space);
1396         space = isl_space_add_dims(space, isl_dim_set, 1);
1397         space = isl_space_map_from_set(space);
1398         c = isl_equality_alloc(isl_local_space_from_space(space));
1399         c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1400         c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1401         bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1402         c = isl_constraint_set_constant_si(c, 1);
1403         bmap2 = isl_basic_map_from_constraint(c);
1404
1405         bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1406         bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1407
1408         return isl_basic_map_union(bmap1, bmap2);
1409 }
1410
1411 static const char *option_str[] = {
1412         [atomic] = "atomic",
1413         [unroll] = "unroll",
1414         [separate] = "separate"
1415 };
1416
1417 /* Update the "options" to reflect the insertion of a dimension
1418  * at position "pos" in the schedule domain space.
1419  * "space" is the original domain space before the insertion and
1420  * may be named and/or structured.
1421  *
1422  * The (relevant) input options all have "space" as domain, which
1423  * has to be mapped to the extended space.
1424  * The values of the ranges also refer to the schedule domain positions
1425  * and they therefore also need to be adjusted.  In particular, values
1426  * smaller than pos do not need to change, while values greater than or
1427  * equal to pos need to be incremented.
1428  * That is, we need to apply the following map.
1429  *
1430  *      { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1431  *        unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1432  *        separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1433  *        separation_class[[i] -> [c]]
1434  *              -> separation_class[[i] -> [c]] : i < pos;
1435  *        separation_class[[i] -> [c]]
1436  *              -> separation_class[[i + 1] -> [c]] : i >= pos }
1437  */
1438 static __isl_give isl_union_map *options_insert_dim(
1439         __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1440 {
1441         isl_map *map;
1442         isl_union_map *insertion;
1443         enum isl_ast_build_domain_type type;
1444         const char *name = "separation_class";
1445
1446         space = isl_space_map_from_set(space);
1447         map = isl_map_identity(space);
1448         map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1449         options = isl_union_map_apply_domain(options,
1450                                                 isl_union_map_from_map(map));
1451
1452         if (!options)
1453                 return NULL;
1454
1455         map = construct_insertion_map(isl_union_map_get_space(options), pos);
1456
1457         insertion = isl_union_map_empty(isl_union_map_get_space(options));
1458
1459         for (type = atomic; type <= separate; ++type) {
1460                 isl_map *map_type = isl_map_copy(map);
1461                 const char *name = option_str[type];
1462                 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1463                 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1464                 insertion = isl_union_map_add_map(insertion, map_type);
1465         }
1466
1467         map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1468         map = isl_map_set_tuple_name(map, isl_dim_in, name);
1469         map = isl_map_set_tuple_name(map, isl_dim_out, name);
1470         insertion = isl_union_map_add_map(insertion, map);
1471
1472         options = isl_union_map_apply_range(options, insertion);
1473
1474         return options;
1475 }
1476
1477 /* Insert a single dimension in the schedule domain at position "pos".
1478  * The new dimension is given an isl_id with the empty string as name.
1479  *
1480  * The main difficulty is updating build->options to reflect the
1481  * extra dimension.  This is handled in options_insert_dim.
1482  *
1483  * Note that because of the dimension manipulations, the resulting
1484  * schedule domain space will always be unnamed and unstructured.
1485  * However, the original schedule domain space may be named and/or
1486  * structured, so we have to take this possibility into account
1487  * while performing the transformations.
1488  */
1489 __isl_give isl_ast_build *isl_ast_build_insert_dim(
1490         __isl_take isl_ast_build *build, int pos)
1491 {
1492         isl_ctx *ctx;
1493         isl_space *space, *ma_space;
1494         isl_id *id;
1495         isl_multi_aff *ma;
1496
1497         build = isl_ast_build_cow(build);
1498         if (!build)
1499                 return NULL;
1500
1501         ctx = isl_ast_build_get_ctx(build);
1502         id = isl_id_alloc(ctx, "", NULL);
1503         space = isl_ast_build_get_space(build, 1);
1504         build->iterators = isl_id_list_insert(build->iterators, pos, id);
1505         build->domain = isl_set_insert_dims(build->domain,
1506                                                 isl_dim_set, pos, 1);
1507         build->generated = isl_set_insert_dims(build->generated,
1508                                                 isl_dim_set, pos, 1);
1509         build->pending = isl_set_insert_dims(build->pending,
1510                                                 isl_dim_set, pos, 1);
1511         build->strides = isl_vec_insert_els(build->strides, pos, 1);
1512         build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1513         ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1514         ma_space = isl_space_set_from_params(ma_space);
1515         ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1516         ma_space = isl_space_map_from_set(ma_space);
1517         ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1518         build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1519         ma = isl_multi_aff_identity(ma_space);
1520         build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1521         build->options = options_insert_dim(build->options, space, pos);
1522
1523         if (!build->iterators || !build->domain || !build->generated ||
1524             !build->pending || !build->values ||
1525             !build->strides || !build->offsets || !build->options)
1526                 return isl_ast_build_free(build);
1527
1528         return build;
1529 }
1530
1531 /* Scale down the current dimension by a factor of "m".
1532  * "umap" is an isl_union_map that implements the scaling down.
1533  * That is, it is of the form
1534  *
1535  *      { [.... i ....] -> [.... i' ....] : i = m i' }
1536  *
1537  * This function is called right after the strides have been
1538  * detected, but before any constraints on the current dimension
1539  * have been included in build->domain.
1540  * We therefore only need to update stride, offset and the options.
1541  */
1542 __isl_give isl_ast_build *isl_ast_build_scale_down(
1543         __isl_take isl_ast_build *build, isl_int m,
1544         __isl_take isl_union_map *umap)
1545 {
1546         isl_aff *aff;
1547         isl_int v;
1548         int depth;
1549
1550         build = isl_ast_build_cow(build);
1551         if (!build || !umap)
1552                 goto error;
1553
1554         depth = build->depth;
1555
1556         isl_int_init(v);
1557         if (isl_vec_get_element(build->strides, depth, &v) < 0)
1558                 build->strides = isl_vec_free(build->strides);
1559         isl_int_divexact(v, v, m);
1560         build->strides = isl_vec_set_element(build->strides, depth, v);
1561         isl_int_clear(v);
1562
1563         aff = isl_multi_aff_get_aff(build->offsets, depth);
1564         aff = isl_aff_scale_down(aff, m);
1565         build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1566         build->options = isl_union_map_apply_domain(build->options, umap);
1567         if (!build->strides || !build->offsets || !build->options)
1568                 return isl_ast_build_free(build);
1569
1570         return build;
1571 error:
1572         isl_union_map_free(umap);
1573         return isl_ast_build_free(build);
1574 }
1575
1576 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1577  * If an isl_id with such a name already appears among the parameters
1578  * in build->domain, then adjust the name to "c%d_%d".
1579  */
1580 static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1581         __isl_keep isl_ast_build *build)
1582 {
1583         int i;
1584         isl_id_list *names;
1585
1586         names = isl_id_list_alloc(ctx, n);
1587         for (i = 0; i < n; ++i) {
1588                 isl_id *id;
1589
1590                 id = generate_name(ctx, first + i, build);
1591                 names = isl_id_list_add(names, id);
1592         }
1593
1594         return names;
1595 }
1596
1597 /* Embed "options" into the given isl_ast_build space.
1598  *
1599  * This function is called from within a nested call to
1600  * isl_ast_build_ast_from_schedule.
1601  * "options" refers to the additional schedule,
1602  * while space refers to both the space of the outer isl_ast_build and
1603  * that of the additional schedule.
1604  * Specifically, space is of the form
1605  *
1606  *      [I -> S]
1607  *
1608  * while options lives in the space(s)
1609  *
1610  *      S -> *
1611  *
1612  * We compute
1613  *
1614  *      [I -> S] -> S
1615  *
1616  * and compose this with options, to obtain the new options
1617  * living in the space(s)
1618  *
1619  *      [I -> S] -> *
1620  */
1621 static __isl_give isl_union_map *embed_options(
1622         __isl_take isl_union_map *options, __isl_take isl_space *space)
1623 {
1624         isl_map *map;
1625
1626         map = isl_map_universe(isl_space_unwrap(space));
1627         map = isl_map_range_map(map);
1628
1629         options = isl_union_map_apply_range(
1630                                 isl_union_map_from_map(map), options);
1631
1632         return options;
1633 }
1634
1635 /* Update "build" for use in a (possibly nested) code generation.  That is,
1636  * extend "build" from an AST build on some domain O to an AST build
1637  * on domain [O -> S], with S corresponding to "space".
1638  * If the original domain is a parameter domain, then the new domain is
1639  * simply S.
1640  * "iterators" is a list of iterators for S, but the number of elements
1641  * may be smaller or greater than the number of set dimensions of S.
1642  * If "keep_iterators" is set, then any extra ids in build->iterators
1643  * are reused for S.  Otherwise, these extra ids are dropped.
1644  *
1645  * We first update build->outer_pos to the current depth.
1646  * This depth is zero in case this is the outermost code generation.
1647  *
1648  * We then add additional ids such that the number of iterators is at least
1649  * equal to the dimension of the new build domain.
1650  *
1651  * If the original domain is parametric, then we are constructing
1652  * an isl_ast_build for the outer code generation and we pass control
1653  * to isl_ast_build_init.
1654  *
1655  * Otherwise, we adjust the fields of "build" to include "space".
1656  */
1657 __isl_give isl_ast_build *isl_ast_build_product(
1658         __isl_take isl_ast_build *build, __isl_take isl_space *space)
1659 {
1660         isl_ctx *ctx;
1661         isl_vec *strides;
1662         isl_set *set;
1663         isl_multi_aff *embedding;
1664         int dim, n_it;
1665
1666         build = isl_ast_build_cow(build);
1667         if (!build)
1668                 goto error;
1669
1670         build->outer_pos = build->depth;
1671
1672         ctx = isl_ast_build_get_ctx(build);
1673         dim = isl_set_dim(build->domain, isl_dim_set);
1674         dim += isl_space_dim(space, isl_dim_set);
1675         n_it = isl_id_list_n_id(build->iterators);
1676         if (n_it < dim) {
1677                 isl_id_list *l;
1678                 l = generate_names(ctx, dim - n_it, n_it, build);
1679                 build->iterators = isl_id_list_concat(build->iterators, l);
1680         }
1681
1682         if (isl_set_is_params(build->domain))
1683                 return isl_ast_build_init(build, space);
1684
1685         set = isl_set_universe(isl_space_copy(space));
1686         build->domain = isl_set_product(build->domain, isl_set_copy(set));
1687         build->pending = isl_set_product(build->pending, isl_set_copy(set));
1688         build->generated = isl_set_product(build->generated, set);
1689
1690         strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1691         strides = isl_vec_set_si(strides, 1);
1692         build->strides = isl_vec_concat(build->strides, strides);
1693
1694         space = isl_space_map_from_set(space);
1695         build->offsets = isl_multi_aff_align_params(build->offsets,
1696                                                     isl_space_copy(space));
1697         build->offsets = isl_multi_aff_product(build->offsets,
1698                                 isl_multi_aff_zero(isl_space_copy(space)));
1699         build->values = isl_multi_aff_align_params(build->values,
1700                                                     isl_space_copy(space));
1701         embedding = isl_multi_aff_identity(space);
1702         build->values = isl_multi_aff_product(build->values, embedding);
1703
1704         space = isl_ast_build_get_space(build, 1);
1705         build->options = embed_options(build->options, space);
1706
1707         if (!build->iterators || !build->domain || !build->generated ||
1708             !build->pending || !build->values ||
1709             !build->strides || !build->offsets || !build->options)
1710                 return isl_ast_build_free(build);
1711
1712         return build;
1713 error:
1714         isl_ast_build_free(build);
1715         isl_space_free(space);
1716         return NULL;
1717 }
1718
1719 /* Does "aff" only attain non-negative values over build->domain?
1720  * That is, does it not attain any negative values?
1721  */
1722 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
1723         __isl_keep isl_aff *aff)
1724 {
1725         isl_set *test;
1726         int empty;
1727
1728         if (!build)
1729                 return -1;
1730
1731         aff = isl_aff_copy(aff);
1732         test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
1733         test = isl_set_intersect(test, isl_set_copy(build->domain));
1734         empty = isl_set_is_empty(test);
1735         isl_set_free(test);
1736
1737         return empty;
1738 }
1739
1740 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1741  */
1742 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
1743 {
1744         isl_int v;
1745         int has_stride;
1746
1747         if (!build)
1748                 return -1;
1749
1750         isl_int_init(v);
1751         isl_vec_get_element(build->strides, pos, &v);
1752         has_stride = !isl_int_is_one(v);
1753         isl_int_clear(v);
1754
1755         return has_stride;
1756 }
1757
1758 /* Given that the dimension at position "pos" takes on values
1759  *
1760  *      f + s a
1761  *
1762  * with a an integer, return s through *stride.
1763  */
1764 int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
1765         isl_int *stride)
1766 {
1767         if (!build)
1768                 return -1;
1769
1770         isl_vec_get_element(build->strides, pos, stride);
1771
1772         return 0;
1773 }
1774
1775 /* Given that the dimension at position "pos" takes on values
1776  *
1777  *      f + s a
1778  *
1779  * with a an integer, return f.
1780  */
1781 __isl_give isl_aff *isl_ast_build_get_offset(
1782         __isl_keep isl_ast_build *build, int pos)
1783 {
1784         if (!build)
1785                 return NULL;
1786
1787         return isl_multi_aff_get_aff(build->offsets, pos);
1788 }
1789
1790 /* Is the dimension at position "pos" known to attain only a single
1791  * value that, moreover, can be described by a single affine expression
1792  * in terms of the outer dimensions and parameters?
1793  *
1794  * If not, then the correponding affine expression in build->values
1795  * is set to be equal to the same input dimension.
1796  * Otherwise, it is set to the requested expression in terms of
1797  * outer dimensions and parameters.
1798  */
1799 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
1800         int pos)
1801 {
1802         isl_aff *aff;
1803         int involves;
1804
1805         if (!build)
1806                 return -1;
1807
1808         aff = isl_multi_aff_get_aff(build->values, pos);
1809         involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
1810         isl_aff_free(aff);
1811
1812         if (involves < 0)
1813                 return -1;
1814
1815         return !involves;
1816 }
1817
1818 /* Plug in the known values (fixed affine expressions in terms of
1819  * parameters and outer loop iterators) of all loop iterators
1820  * in the domain of "umap".
1821  *
1822  * We simply precompose "umap" with build->values.
1823  */
1824 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
1825         __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
1826 {
1827         isl_multi_aff *values;
1828
1829         if (!build)
1830                 return isl_union_map_free(umap);
1831
1832         values = isl_multi_aff_copy(build->values);
1833         umap = isl_union_map_preimage_domain_multi_aff(umap, values);
1834
1835         return umap;
1836 }
1837
1838 /* Is the current dimension known to attain only a single value?
1839  */
1840 int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
1841 {
1842         if (!build)
1843                 return -1;
1844
1845         return build->value != NULL;
1846 }
1847
1848 /* Simplify the basic set "bset" based on what we know about
1849  * the iterators of already generated loops.
1850  *
1851  * "bset" is assumed to live in the (internal) schedule domain.
1852  */
1853 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
1854         __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1855 {
1856         if (!build)
1857                 goto error;
1858
1859         bset = isl_basic_set_preimage_multi_aff(bset,
1860                                         isl_multi_aff_copy(build->values));
1861         bset = isl_basic_set_gist(bset,
1862                         isl_set_simple_hull(isl_set_copy(build->domain)));
1863
1864         return bset;
1865 error:
1866         isl_basic_set_free(bset);
1867         return NULL;
1868 }
1869
1870 /* Simplify the set "set" based on what we know about
1871  * the iterators of already generated loops.
1872  *
1873  * "set" is assumed to live in the (internal) schedule domain.
1874  */
1875 __isl_give isl_set *isl_ast_build_compute_gist(
1876         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1877 {
1878         if (!build)
1879                 goto error;
1880
1881         set = isl_set_preimage_multi_aff(set,
1882                                         isl_multi_aff_copy(build->values));
1883         set = isl_set_gist(set, isl_set_copy(build->domain));
1884
1885         return set;
1886 error:
1887         isl_set_free(set);
1888         return NULL;
1889 }
1890
1891 /* Simplify the map "map" based on what we know about
1892  * the iterators of already generated loops.
1893  *
1894  * The domain of "map" is assumed to live in the (internal) schedule domain.
1895  */
1896 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
1897         __isl_keep isl_ast_build *build, __isl_take isl_map *map)
1898 {
1899         if (!build)
1900                 goto error;
1901
1902         map = isl_map_gist_domain(map, isl_set_copy(build->domain));
1903
1904         return map;
1905 error:
1906         isl_map_free(map);
1907         return NULL;
1908 }
1909
1910 /* Simplify the affine expression "aff" based on what we know about
1911  * the iterators of already generated loops.
1912  *
1913  * The domain of "aff" is assumed to live in the (internal) schedule domain.
1914  */
1915 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
1916         __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
1917 {
1918         if (!build)
1919                 goto error;
1920
1921         aff = isl_aff_gist(aff, isl_set_copy(build->domain));
1922
1923         return aff;
1924 error:
1925         isl_aff_free(aff);
1926         return NULL;
1927 }
1928
1929 /* Simplify the piecewise affine expression "aff" based on what we know about
1930  * the iterators of already generated loops.
1931  *
1932  * The domain of "pa" is assumed to live in the (internal) schedule domain.
1933  */
1934 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
1935         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1936 {
1937         if (!build)
1938                 goto error;
1939
1940         pa = isl_pw_aff_pullback_multi_aff(pa,
1941                                         isl_multi_aff_copy(build->values));
1942         pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
1943
1944         return pa;
1945 error:
1946         isl_pw_aff_free(pa);
1947         return NULL;
1948 }
1949
1950 /* Simplify the piecewise multi-affine expression "aff" based on what
1951  * we know about the iterators of already generated loops.
1952  *
1953  * The domain of "pma" is assumed to live in the (internal) schedule domain.
1954  */
1955 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
1956         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1957 {
1958         if (!build)
1959                 goto error;
1960
1961         pma = isl_pw_multi_aff_pullback_multi_aff(pma,
1962                                         isl_multi_aff_copy(build->values));
1963         pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
1964
1965         return pma;
1966 error:
1967         isl_pw_multi_aff_free(pma);
1968         return NULL;
1969 }
1970
1971 /* Extract the schedule domain of the given type from build->options
1972  * at the current depth.
1973  *
1974  * In particular, find the subset of build->options that is of
1975  * the following form
1976  *
1977  *      schedule_domain -> type[depth]
1978  *
1979  * and return the corresponding domain, after eliminating inner dimensions
1980  * and divs that depend on the current dimension.
1981  *
1982  * Note that the domain of build->options has been reformulated
1983  * in terms of the internal build space in embed_options,
1984  * but the position is still that within the current code generation.
1985  */
1986 __isl_give isl_set *isl_ast_build_get_option_domain(
1987         __isl_keep isl_ast_build *build,
1988         enum isl_ast_build_domain_type type)
1989 {
1990         const char *name;
1991         isl_space *space;
1992         isl_map *option;
1993         isl_set *domain;
1994         int local_pos;
1995
1996         if (!build)
1997                 return NULL;
1998
1999         name = option_str[type];
2000         local_pos = build->depth - build->outer_pos;
2001
2002         space = isl_ast_build_get_space(build, 1);
2003         space = isl_space_from_domain(space);
2004         space = isl_space_add_dims(space, isl_dim_out, 1);
2005         space = isl_space_set_tuple_name(space, isl_dim_out, name);
2006
2007         option = isl_union_map_extract_map(build->options, space);
2008         option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2009
2010         domain = isl_map_domain(option);
2011         domain = isl_ast_build_eliminate(build, domain);
2012
2013         return domain;
2014 }
2015
2016 /* Extract the separation class mapping at the current depth.
2017  *
2018  * In particular, find and return the subset of build->options that is of
2019  * the following form
2020  *
2021  *      schedule_domain -> separation_class[[depth] -> [class]]
2022  *
2023  * The caller is expected to eliminate inner dimensions from the domain.
2024  *
2025  * Note that the domain of build->options has been reformulated
2026  * in terms of the internal build space in embed_options,
2027  * but the position is still that within the current code generation.
2028  */
2029 __isl_give isl_map *isl_ast_build_get_separation_class(
2030         __isl_keep isl_ast_build *build)
2031 {
2032         isl_ctx *ctx;
2033         isl_space *space_sep, *space;
2034         isl_map *res;
2035         int local_pos;
2036
2037         if (!build)
2038                 return NULL;
2039
2040         local_pos = build->depth - build->outer_pos;
2041         ctx = isl_ast_build_get_ctx(build);
2042         space_sep = isl_space_alloc(ctx, 0, 1, 1);
2043         space_sep = isl_space_wrap(space_sep);
2044         space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2045                                                 "separation_class");
2046         space = isl_ast_build_get_space(build, 1);
2047         space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2048         space = isl_space_map_from_domain_and_range(space, space_sep);
2049
2050         res = isl_union_map_extract_map(build->options, space);
2051         res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2052         res = isl_map_coalesce(res);
2053
2054         return res;
2055 }
2056
2057 /* Eliminate dimensions inner to the current dimension.
2058  */
2059 __isl_give isl_set *isl_ast_build_eliminate_inner(
2060         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2061 {
2062         int dim;
2063         int depth;
2064
2065         if (!build)
2066                 return isl_set_free(set);
2067
2068         dim = isl_set_dim(set, isl_dim_set);
2069         depth = build->depth;
2070         set = isl_set_detect_equalities(set);
2071         set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2072
2073         return set;
2074 }
2075
2076 /* Eliminate unknown divs and divs that depend on the current dimension.
2077  *
2078  * Note that during the elimination of unknown divs, we may discover
2079  * an explicit representation of some other unknown divs, which may
2080  * depend on the current dimension.  We therefore need to eliminate
2081  * unknown divs first.
2082  */
2083 __isl_give isl_set *isl_ast_build_eliminate_divs(
2084         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2085 {
2086         int depth;
2087
2088         if (!build)
2089                 return isl_set_free(set);
2090
2091         set = isl_set_remove_unknown_divs(set);
2092         depth = build->depth;
2093         set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2094
2095         return set;
2096 }
2097
2098 /* Eliminate dimensions inner to the current dimension as well as
2099  * unknown divs and divs that depend on the current dimension.
2100  * The result then consists only of constraints that are independent
2101  * of the current dimension and upper and lower bounds on the current
2102  * dimension.
2103  */
2104 __isl_give isl_set *isl_ast_build_eliminate(
2105         __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2106 {
2107         domain = isl_ast_build_eliminate_inner(build, domain);
2108         domain = isl_ast_build_eliminate_divs(build, domain);
2109         return domain;
2110 }
2111
2112 /* Replace build->single_valued by "sv".
2113  */
2114 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2115         __isl_take isl_ast_build *build, int sv)
2116 {
2117         if (!build)
2118                 return build;
2119         if (build->single_valued == sv)
2120                 return build;
2121         build = isl_ast_build_cow(build);
2122         if (!build)
2123                 return build;
2124         build->single_valued = sv;
2125
2126         return build;
2127 }