isl_ast_build.c

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