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