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