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