1/* 2 * Copyright 2011 INRIA Saclay 3 * Copyright 2012-2013 Ecole Normale Superieure 4 * 5 * Use of this software is governed by the MIT license 6 * 7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, 8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, 9 * 91893 Orsay, France 10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France 11 */ 12 13#include <isl_band_private.h> 14#include <isl_schedule_private.h> 15 16#undef BASE 17#define BASE band 18 19#include <isl_list_templ.c> 20 21isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band) 22{ 23 return band ? isl_union_pw_multi_aff_get_ctx(band->pma) : NULL; 24} 25 26__isl_give isl_band *isl_band_alloc(isl_ctx *ctx) 27{ 28 isl_band *band; 29 30 band = isl_calloc_type(ctx, isl_band); 31 if (!band) 32 return NULL; 33 34 band->ref = 1; 35 36 return band; 37} 38 39/* Create a duplicate of the given band. The duplicate refers 40 * to the same schedule and parent as the input, but does not 41 * increment their reference counts. 42 */ 43__isl_give isl_band *isl_band_dup(__isl_keep isl_band *band) 44{ 45 int i; 46 isl_ctx *ctx; 47 isl_band *dup; 48 49 if (!band) 50 return NULL; 51 52 ctx = isl_band_get_ctx(band); 53 dup = isl_band_alloc(ctx); 54 if (!dup) 55 return NULL; 56 57 dup->n = band->n; 58 dup->zero = isl_alloc_array(ctx, int, band->n); 59 if (band->n && !dup->zero) 60 goto error; 61 62 for (i = 0; i < band->n; ++i) 63 dup->zero[i] = band->zero[i]; 64 65 dup->pma = isl_union_pw_multi_aff_copy(band->pma); 66 dup->schedule = band->schedule; 67 dup->parent = band->parent; 68 69 if (!dup->pma) 70 goto error; 71 72 return dup; 73error: 74 isl_band_free(dup); 75 return NULL; 76} 77 78/* We not only increment the reference count of the band, 79 * but also that of the schedule that contains this band. 80 * This ensures that the schedule won't disappear while there 81 * is still a reference to the band outside of the schedule. 82 * There is no need to increment the reference count of the parent 83 * band as the parent band is part of the same schedule. 84 */ 85__isl_give isl_band *isl_band_copy(__isl_keep isl_band *band) 86{ 87 if (!band) 88 return NULL; 89 90 band->ref++; 91 band->schedule->ref++; 92 return band; 93} 94 95/* If this is not the last reference to the band (the one from within the 96 * schedule), then we also need to decrement the reference count of the 97 * containing schedule as it was incremented in isl_band_copy. 98 */ 99void *isl_band_free(__isl_take isl_band *band) 100{ 101 if (!band) 102 return NULL; 103 104 if (--band->ref > 0) 105 return isl_schedule_free(band->schedule); 106 107 isl_union_pw_multi_aff_free(band->pma); 108 isl_band_list_free(band->children); 109 free(band->zero); 110 free(band); 111 112 return NULL; 113} 114 115int isl_band_has_children(__isl_keep isl_band *band) 116{ 117 if (!band) 118 return -1; 119 120 return band->children != NULL; 121} 122 123__isl_give isl_band_list *isl_band_get_children( 124 __isl_keep isl_band *band) 125{ 126 if (!band) 127 return NULL; 128 if (!band->children) 129 isl_die(isl_band_get_ctx(band), isl_error_invalid, 130 "band has no children", return NULL); 131 return isl_band_list_dup(band->children); 132} 133 134int isl_band_n_member(__isl_keep isl_band *band) 135{ 136 return band ? band->n : 0; 137} 138 139/* Is the given scheduling dimension zero distance within the band and 140 * with respect to the proximity dependences. 141 */ 142int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos) 143{ 144 if (!band) 145 return -1; 146 147 if (pos < 0 || pos >= band->n) 148 isl_die(isl_band_get_ctx(band), isl_error_invalid, 149 "invalid member position", return -1); 150 151 return band->zero[pos]; 152} 153 154/* Return the schedule that leads up to this band. 155 */ 156__isl_give isl_union_map *isl_band_get_prefix_schedule( 157 __isl_keep isl_band *band) 158{ 159 isl_union_set *domain; 160 isl_union_pw_multi_aff *prefix; 161 isl_band *a; 162 163 if (!band) 164 return NULL; 165 166 prefix = isl_union_pw_multi_aff_copy(band->pma); 167 domain = isl_union_pw_multi_aff_domain(prefix); 168 prefix = isl_union_pw_multi_aff_from_domain(domain); 169 170 for (a = band->parent; a; a = a->parent) { 171 isl_union_pw_multi_aff *partial; 172 173 partial = isl_union_pw_multi_aff_copy(a->pma); 174 prefix = isl_union_pw_multi_aff_flat_range_product(partial, 175 prefix); 176 } 177 178 return isl_union_map_from_union_pw_multi_aff(prefix); 179} 180 181/* Return the schedule of the band in isolation. 182 */ 183__isl_give isl_union_pw_multi_aff * 184isl_band_get_partial_schedule_union_pw_multi_aff(__isl_keep isl_band *band) 185{ 186 return band ? isl_union_pw_multi_aff_copy(band->pma) : NULL; 187} 188 189/* Return the schedule of the band in isolation. 190 */ 191__isl_give isl_union_map *isl_band_get_partial_schedule( 192 __isl_keep isl_band *band) 193{ 194 isl_union_pw_multi_aff *sched; 195 196 sched = isl_band_get_partial_schedule_union_pw_multi_aff(band); 197 return isl_union_map_from_union_pw_multi_aff(sched); 198} 199 200__isl_give isl_union_pw_multi_aff * 201isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band); 202 203/* Return the schedule for the given band list. 204 * For each band in the list, the schedule is composed of the partial 205 * and suffix schedules of that band. 206 */ 207__isl_give isl_union_pw_multi_aff * 208isl_band_list_get_suffix_schedule_union_pw_multi_aff( 209 __isl_keep isl_band_list *list) 210{ 211 isl_ctx *ctx; 212 int i, n; 213 isl_space *space; 214 isl_union_pw_multi_aff *suffix; 215 216 if (!list) 217 return NULL; 218 219 ctx = isl_band_list_get_ctx(list); 220 space = isl_space_alloc(ctx, 0, 0, 0); 221 suffix = isl_union_pw_multi_aff_empty(space); 222 n = isl_band_list_n_band(list); 223 for (i = 0; i < n; ++i) { 224 isl_band *el; 225 isl_union_pw_multi_aff *partial; 226 isl_union_pw_multi_aff *suffix_i; 227 228 el = isl_band_list_get_band(list, i); 229 partial = isl_band_get_partial_schedule_union_pw_multi_aff(el); 230 suffix_i = isl_band_get_suffix_schedule_union_pw_multi_aff(el); 231 suffix_i = isl_union_pw_multi_aff_flat_range_product( 232 partial, suffix_i); 233 suffix = isl_union_pw_multi_aff_add(suffix, suffix_i); 234 235 isl_band_free(el); 236 } 237 238 return suffix; 239} 240 241/* Return the schedule for the given band list. 242 * For each band in the list, the schedule is composed of the partial 243 * and suffix schedules of that band. 244 */ 245__isl_give isl_union_map *isl_band_list_get_suffix_schedule( 246 __isl_keep isl_band_list *list) 247{ 248 isl_union_pw_multi_aff *suffix; 249 250 suffix = isl_band_list_get_suffix_schedule_union_pw_multi_aff(list); 251 return isl_union_map_from_union_pw_multi_aff(suffix); 252} 253 254/* Return the schedule for the forest underneath the given band. 255 */ 256__isl_give isl_union_pw_multi_aff * 257isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band) 258{ 259 isl_union_pw_multi_aff *suffix; 260 261 if (!band) 262 return NULL; 263 264 if (!isl_band_has_children(band)) { 265 isl_union_set *domain; 266 267 suffix = isl_union_pw_multi_aff_copy(band->pma); 268 domain = isl_union_pw_multi_aff_domain(suffix); 269 suffix = isl_union_pw_multi_aff_from_domain(domain); 270 } else { 271 isl_band_list *list; 272 273 list = isl_band_get_children(band); 274 suffix = 275 isl_band_list_get_suffix_schedule_union_pw_multi_aff(list); 276 isl_band_list_free(list); 277 } 278 279 return suffix; 280} 281 282/* Return the schedule for the forest underneath the given band. 283 */ 284__isl_give isl_union_map *isl_band_get_suffix_schedule( 285 __isl_keep isl_band *band) 286{ 287 isl_union_pw_multi_aff *suffix; 288 289 suffix = isl_band_get_suffix_schedule_union_pw_multi_aff(band); 290 return isl_union_map_from_union_pw_multi_aff(suffix); 291} 292 293/* Call "fn" on each band (recursively) in the list 294 * in depth-first post-order. 295 */ 296int isl_band_list_foreach_band(__isl_keep isl_band_list *list, 297 int (*fn)(__isl_keep isl_band *band, void *user), void *user) 298{ 299 int i, n; 300 301 if (!list) 302 return -1; 303 304 n = isl_band_list_n_band(list); 305 for (i = 0; i < n; ++i) { 306 isl_band *band; 307 int r = 0; 308 309 band = isl_band_list_get_band(list, i); 310 if (isl_band_has_children(band)) { 311 isl_band_list *children; 312 313 children = isl_band_get_children(band); 314 r = isl_band_list_foreach_band(children, fn, user); 315 isl_band_list_free(children); 316 } 317 318 if (!band) 319 r = -1; 320 if (r == 0) 321 r = fn(band, user); 322 323 isl_band_free(band); 324 if (r) 325 return r; 326 } 327 328 return 0; 329} 330 331/* Internal data used during the construction of the schedule 332 * for the tile loops. 333 * 334 * sizes contains the tile sizes 335 * scale is set if the tile loops should be scaled 336 * tiled collects the result for a single statement 337 * res collects the result for all statements 338 */ 339struct isl_band_tile_data { 340 isl_multi_val *sizes; 341 isl_union_pw_multi_aff *res; 342 isl_pw_multi_aff *tiled; 343 int scale; 344}; 345 346/* Given part of the schedule of a band, construct the corresponding 347 * schedule for the tile loops based on the tile sizes in data->sizes 348 * and add the result to data->tiled. 349 * 350 * If data->scale is set, then dimension i of the schedule will be 351 * of the form 352 * 353 * m_i * floor(s_i(x) / m_i) 354 * 355 * where s_i(x) refers to the original schedule and m_i is the tile size. 356 * If data->scale is not set, then dimension i of the schedule will be 357 * of the form 358 * 359 * floor(s_i(x) / m_i) 360 * 361 */ 362static int multi_aff_tile(__isl_take isl_set *set, 363 __isl_take isl_multi_aff *ma, void *user) 364{ 365 struct isl_band_tile_data *data = user; 366 isl_pw_multi_aff *pma; 367 int i, n; 368 isl_val *v; 369 370 n = isl_multi_aff_dim(ma, isl_dim_out); 371 372 for (i = 0; i < n; ++i) { 373 isl_aff *aff; 374 375 aff = isl_multi_aff_get_aff(ma, i); 376 v = isl_multi_val_get_val(data->sizes, i); 377 378 aff = isl_aff_scale_down_val(aff, isl_val_copy(v)); 379 aff = isl_aff_floor(aff); 380 if (data->scale) 381 aff = isl_aff_scale_val(aff, isl_val_copy(v)); 382 isl_val_free(v); 383 384 ma = isl_multi_aff_set_aff(ma, i, aff); 385 } 386 387 pma = isl_pw_multi_aff_alloc(set, ma); 388 data->tiled = isl_pw_multi_aff_union_add(data->tiled, pma); 389 390 return 0; 391} 392 393/* Given part of the schedule of a band, construct the corresponding 394 * schedule for the tile loops based on the tile sizes in data->sizes 395 * and add the result to data->res. 396 */ 397static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff *pma, void *user) 398{ 399 struct isl_band_tile_data *data = user; 400 401 data->tiled = isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma)); 402 403 if (isl_pw_multi_aff_foreach_piece(pma, &multi_aff_tile, data) < 0) 404 goto error; 405 406 isl_pw_multi_aff_free(pma); 407 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, 408 data->tiled); 409 410 return 0; 411error: 412 isl_pw_multi_aff_free(pma); 413 isl_pw_multi_aff_free(data->tiled); 414 return -1; 415} 416 417/* Given the schedule of a band, construct the corresponding 418 * schedule for the tile loops based on the given tile sizes 419 * and return the result. 420 */ 421static isl_union_pw_multi_aff *isl_union_pw_multi_aff_tile( 422 __isl_take isl_union_pw_multi_aff *sched, 423 __isl_keep isl_multi_val *sizes) 424{ 425 isl_ctx *ctx; 426 isl_space *space; 427 struct isl_band_tile_data data = { sizes }; 428 429 ctx = isl_multi_val_get_ctx(sizes); 430 431 space = isl_union_pw_multi_aff_get_space(sched); 432 data.res = isl_union_pw_multi_aff_empty(space); 433 data.scale = isl_options_get_tile_scale_tile_loops(ctx); 434 435 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched, 436 &pw_multi_aff_tile, &data) < 0) 437 goto error; 438 439 isl_union_pw_multi_aff_free(sched); 440 return data.res; 441error: 442 isl_union_pw_multi_aff_free(sched); 443 isl_union_pw_multi_aff_free(data.res); 444 return NULL; 445} 446 447/* Extract the range space from "pma" and store it in *user. 448 * All entries are expected to have the same range space, so we can 449 * stop after extracting the range space from the first entry. 450 */ 451static int extract_range_space(__isl_take isl_pw_multi_aff *pma, void *user) 452{ 453 isl_space **space = user; 454 455 *space = isl_space_range(isl_pw_multi_aff_get_space(pma)); 456 isl_pw_multi_aff_free(pma); 457 458 return -1; 459} 460 461/* Extract the range space of "band". All entries in band->pma should 462 * have the same range space. Furthermore, band->pma should have at least 463 * one entry. 464 */ 465static __isl_give isl_space *band_get_range_space(__isl_keep isl_band *band) 466{ 467 isl_space *space; 468 469 if (!band) 470 return NULL; 471 472 space = NULL; 473 isl_union_pw_multi_aff_foreach_pw_multi_aff(band->pma, 474 &extract_range_space, &space); 475 476 return space; 477} 478 479/* Construct and return an isl_multi_val in the given space, with as entries 480 * the first elements of "v", padded with ones if the size of "v" is smaller 481 * than the dimension of "space". 482 */ 483static __isl_give isl_multi_val *multi_val_from_vec(__isl_take isl_space *space, 484 __isl_take isl_vec *v) 485{ 486 isl_ctx *ctx; 487 isl_multi_val *mv; 488 int i, n, size; 489 490 if (!space || !v) 491 goto error; 492 493 ctx = isl_space_get_ctx(space); 494 mv = isl_multi_val_zero(space); 495 n = isl_multi_val_dim(mv, isl_dim_set); 496 size = isl_vec_size(v); 497 if (n < size) 498 size = n; 499 500 for (i = 0; i < size; ++i) { 501 isl_val *val = isl_vec_get_element_val(v, i); 502 mv = isl_multi_val_set_val(mv, i, val); 503 } 504 for (i = size; i < n; ++i) 505 mv = isl_multi_val_set_val(mv, i, isl_val_one(ctx)); 506 507 isl_vec_free(v); 508 return mv; 509error: 510 isl_space_free(space); 511 isl_vec_free(v); 512 return NULL; 513} 514 515/* Tile the given band using the specified tile sizes. 516 * The given band is modified to refer to the tile loops and 517 * a child band is created to refer to the point loops. 518 * The children of this point loop band are the children 519 * of the original band. 520 * 521 * If the scale tile loops option is set, then the tile loops 522 * are scaled by the tile sizes. If the shift point loops option is set, 523 * then the point loops are shifted to start at zero. 524 * In particular, these options affect the tile and point loop schedules 525 * as follows 526 * 527 * scale shift original tile point 528 * 529 * 0 0 i floor(i/s) i 530 * 1 0 i s * floor(i/s) i 531 * 0 1 i floor(i/s) i - s * floor(i/s) 532 * 1 1 i s * floor(i/s) i - s * floor(i/s) 533 */ 534int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes) 535{ 536 isl_ctx *ctx; 537 isl_band *child; 538 isl_band_list *list = NULL; 539 isl_union_pw_multi_aff *sched = NULL, *child_sched = NULL; 540 isl_space *space; 541 isl_multi_val *mv_sizes; 542 543 if (!band || !sizes) 544 goto error; 545 546 ctx = isl_vec_get_ctx(sizes); 547 child = isl_band_dup(band); 548 list = isl_band_list_alloc(ctx, 1); 549 list = isl_band_list_add(list, child); 550 if (!list) 551 goto error; 552 553 space = band_get_range_space(band); 554 mv_sizes = multi_val_from_vec(space, isl_vec_copy(sizes)); 555 sched = isl_union_pw_multi_aff_copy(band->pma); 556 sched = isl_union_pw_multi_aff_tile(sched, mv_sizes); 557 558 child_sched = isl_union_pw_multi_aff_copy(child->pma); 559 if (isl_options_get_tile_shift_point_loops(ctx)) { 560 isl_union_pw_multi_aff *scaled; 561 scaled = isl_union_pw_multi_aff_copy(sched); 562 if (!isl_options_get_tile_scale_tile_loops(ctx)) 563 scaled = isl_union_pw_multi_aff_scale_multi_val(scaled, 564 isl_multi_val_copy(mv_sizes)); 565 child_sched = isl_union_pw_multi_aff_sub(child_sched, scaled); 566 } 567 isl_multi_val_free(mv_sizes); 568 if (!sched || !child_sched) 569 goto error; 570 571 child->children = band->children; 572 band->children = list; 573 child->parent = band; 574 isl_union_pw_multi_aff_free(band->pma); 575 band->pma = sched; 576 isl_union_pw_multi_aff_free(child->pma); 577 child->pma = child_sched; 578 579 isl_vec_free(sizes); 580 return 0; 581error: 582 isl_union_pw_multi_aff_free(sched); 583 isl_union_pw_multi_aff_free(child_sched); 584 isl_band_list_free(list); 585 isl_vec_free(sizes); 586 return -1; 587} 588 589/* Internal data structure used inside isl_union_pw_multi_aff_drop. 590 * 591 * "pos" is the position of the first dimension to drop. 592 * "n" is the number of dimensions to drop. 593 * "res" accumulates the result. 594 */ 595struct isl_union_pw_multi_aff_drop_data { 596 int pos; 597 int n; 598 isl_union_pw_multi_aff *res; 599}; 600 601/* Drop the data->n output dimensions starting at data->pos from "pma" 602 * and add the result to data->res. 603 */ 604static int pw_multi_aff_drop(__isl_take isl_pw_multi_aff *pma, void *user) 605{ 606 struct isl_union_pw_multi_aff_drop_data *data = user; 607 608 pma = isl_pw_multi_aff_drop_dims(pma, isl_dim_out, data->pos, data->n); 609 610 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma); 611 if (!data->res) 612 return -1; 613 614 return 0; 615} 616 617/* Drop the "n" output dimensions starting at "pos" from "sched". 618 */ 619static isl_union_pw_multi_aff *isl_union_pw_multi_aff_drop( 620 __isl_take isl_union_pw_multi_aff *sched, int pos, int n) 621{ 622 isl_space *space; 623 struct isl_union_pw_multi_aff_drop_data data = { pos, n }; 624 625 space = isl_union_pw_multi_aff_get_space(sched); 626 data.res = isl_union_pw_multi_aff_empty(space); 627 628 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched, 629 &pw_multi_aff_drop, &data) < 0) 630 data.res = isl_union_pw_multi_aff_free(data.res); 631 632 isl_union_pw_multi_aff_free(sched); 633 return data.res; 634} 635 636/* Drop the "n" dimensions starting at "pos" from "band". 637 */ 638static int isl_band_drop(__isl_keep isl_band *band, int pos, int n) 639{ 640 int i; 641 isl_union_pw_multi_aff *sched; 642 643 if (!band) 644 return -1; 645 if (n == 0) 646 return 0; 647 648 sched = isl_union_pw_multi_aff_copy(band->pma); 649 sched = isl_union_pw_multi_aff_drop(sched, pos, n); 650 if (!sched) 651 return -1; 652 653 isl_union_pw_multi_aff_free(band->pma); 654 band->pma = sched; 655 656 for (i = pos + n; i < band->n; ++i) 657 band->zero[i - n] = band->zero[i]; 658 659 band->n -= n; 660 661 return 0; 662} 663 664/* Split the given band into two nested bands, one with the first "pos" 665 * dimensions of "band" and one with the remaining band->n - pos dimensions. 666 */ 667int isl_band_split(__isl_keep isl_band *band, int pos) 668{ 669 isl_ctx *ctx; 670 isl_band *child; 671 isl_band_list *list; 672 673 if (!band) 674 return -1; 675 676 ctx = isl_band_get_ctx(band); 677 678 if (pos < 0 || pos > band->n) 679 isl_die(ctx, isl_error_invalid, "position out of bounds", 680 return -1); 681 682 child = isl_band_dup(band); 683 if (isl_band_drop(child, 0, pos) < 0) 684 child = isl_band_free(child); 685 list = isl_band_list_alloc(ctx, 1); 686 list = isl_band_list_add(list, child); 687 if (!list) 688 return -1; 689 690 if (isl_band_drop(band, pos, band->n - pos) < 0) { 691 isl_band_list_free(list); 692 return -1; 693 } 694 695 child->children = band->children; 696 band->children = list; 697 child->parent = band; 698 699 return 0; 700} 701 702__isl_give isl_printer *isl_printer_print_band(__isl_take isl_printer *p, 703 __isl_keep isl_band *band) 704{ 705 isl_union_map *prefix, *partial, *suffix; 706 707 prefix = isl_band_get_prefix_schedule(band); 708 partial = isl_band_get_partial_schedule(band); 709 suffix = isl_band_get_suffix_schedule(band); 710 711 p = isl_printer_print_str(p, "("); 712 p = isl_printer_print_union_map(p, prefix); 713 p = isl_printer_print_str(p, ","); 714 p = isl_printer_print_union_map(p, partial); 715 p = isl_printer_print_str(p, ","); 716 p = isl_printer_print_union_map(p, suffix); 717 p = isl_printer_print_str(p, ")"); 718 719 isl_union_map_free(prefix); 720 isl_union_map_free(partial); 721 isl_union_map_free(suffix); 722 723 return p; 724} 725