isl_band.c

   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
  21 isl_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 (!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;
  73 error:
  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  */
  99 void *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
 115 int 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
 134 int 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  */
 142 int 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 *
 184 isl_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 *
 201 isl_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 *
 208 isl_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 *
 257 isl_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  */
 296 int 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  */
 339 struct isl_band_tile_data {
 340         isl_vec *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  */
 362 static 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_int v;
 369
 370         n = isl_multi_aff_dim(ma, isl_dim_out);
 371         if (isl_vec_size(data->sizes) < n)
 372                 n = isl_vec_size(data->sizes);
 373
 374         isl_int_init(v);
 375         for (i = 0; i < n; ++i) {
 376                 isl_aff *aff;
 377
 378                 aff = isl_multi_aff_get_aff(ma, i);
 379                 isl_vec_get_element(data->sizes, i, &v);
 380
 381                 aff = isl_aff_scale_down(aff, v);
 382                 aff = isl_aff_floor(aff);
 383                 if (data->scale)
 384                         aff = isl_aff_scale(aff, v);
 385
 386                 ma = isl_multi_aff_set_aff(ma, i, aff);
 387         }
 388         isl_int_clear(v);
 389
 390         pma = isl_pw_multi_aff_alloc(set, ma);
 391         data->tiled = isl_pw_multi_aff_union_add(data->tiled, pma);
 392
 393         return 0;
 394 }
 395
 396 /* Given part of the schedule of a band, construct the corresponding
 397  * schedule for the tile loops based on the tile sizes in data->sizes
 398  * and add the result to data->res.
 399  */
 400 static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff *pma, void *user)
 401 {
 402         struct isl_band_tile_data *data = user;
 403
 404         data->tiled = isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma));
 405
 406         if (isl_pw_multi_aff_foreach_piece(pma, &multi_aff_tile, data) < 0)
 407                 goto error;
 408
 409         isl_pw_multi_aff_free(pma);
 410         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res,
 411                                                                 data->tiled);
 412
 413         return 0;
 414 error:
 415         isl_pw_multi_aff_free(pma);
 416         isl_pw_multi_aff_free(data->tiled);
 417         return -1;
 418 }
 419
 420 /* Given the schedule of a band, construct the corresponding
 421  * schedule for the tile loops based on the given tile sizes
 422  * and return the result.
 423  */
 424 static isl_union_pw_multi_aff *isl_union_pw_multi_aff_tile(
 425         __isl_take isl_union_pw_multi_aff *sched, __isl_keep isl_vec *sizes)
 426 {
 427         isl_ctx *ctx;
 428         isl_space *space;
 429         struct isl_band_tile_data data = { sizes };
 430
 431         ctx = isl_vec_get_ctx(sizes);
 432
 433         space = isl_union_pw_multi_aff_get_space(sched);
 434         data.res = isl_union_pw_multi_aff_empty(space);
 435         data.scale = isl_options_get_tile_scale_tile_loops(ctx);
 436
 437         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched,
 438                                                 &pw_multi_aff_tile, &data) < 0)
 439                 goto error;
 440
 441         isl_union_pw_multi_aff_free(sched);
 442         return data.res;
 443 error:
 444         isl_union_pw_multi_aff_free(sched);
 445         isl_union_pw_multi_aff_free(data.res);
 446         return NULL;
 447 }
 448
 449 /* Tile the given band using the specified tile sizes.
 450  * The given band is modified to refer to the tile loops and
 451  * a child band is created to refer to the point loops.
 452  * The children of this point loop band are the children
 453  * of the original band.
 454  *
 455  * If the scale tile loops option is set, then the tile loops
 456  * are scaled by the tile sizes.  If the shift point loops option is set,
 457  * then the point loops are shifted to start at zero.
 458  * In particular, these options affect the tile and point loop schedules
 459  * as follows
 460  *
 461  *      scale   shift   original        tile            point
 462  *
 463  *      0       0       i               floor(i/s)      i
 464  *      1       0       i               s * floor(i/s)  i
 465  *      0       1       i               floor(i/s)      i - s * floor(i/s)
 466  *      1       1       i               s * floor(i/s)  i - s * floor(i/s)
 467  */
 468 int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes)
 469 {
 470         isl_ctx *ctx;
 471         isl_band *child;
 472         isl_band_list *list = NULL;
 473         isl_union_pw_multi_aff *sched = NULL, *child_sched = NULL;
 474
 475         if (!band || !sizes)
 476                 goto error;
 477
 478         ctx = isl_vec_get_ctx(sizes);
 479         child = isl_band_dup(band);
 480         list = isl_band_list_alloc(ctx, 1);
 481         list = isl_band_list_add(list, child);
 482         if (!list)
 483                 goto error;
 484
 485         sched = isl_union_pw_multi_aff_copy(band->pma);
 486         sched = isl_union_pw_multi_aff_tile(sched, sizes);
 487
 488         child_sched = isl_union_pw_multi_aff_copy(child->pma);
 489         if (isl_options_get_tile_shift_point_loops(ctx)) {
 490                 isl_union_pw_multi_aff *scaled;
 491                 scaled = isl_union_pw_multi_aff_copy(sched);
 492                 if (!isl_options_get_tile_scale_tile_loops(ctx))
 493                         scaled = isl_union_pw_multi_aff_scale_vec(scaled,
 494                                                         isl_vec_copy(sizes));
 495                 child_sched = isl_union_pw_multi_aff_sub(child_sched, scaled);
 496         }
 497         if (!sched || !child_sched)
 498                 goto error;
 499
 500         child->children = band->children;
 501         band->children = list;
 502         child->parent = band;
 503         isl_union_pw_multi_aff_free(band->pma);
 504         band->pma = sched;
 505         isl_union_pw_multi_aff_free(child->pma);
 506         child->pma = child_sched;
 507
 508         isl_vec_free(sizes);
 509         return 0;
 510 error:
 511         isl_union_pw_multi_aff_free(sched);
 512         isl_union_pw_multi_aff_free(child_sched);
 513         isl_band_list_free(list);
 514         isl_vec_free(sizes);
 515         return -1;
 516 }
 517
 518 /* Internal data structure used inside isl_union_pw_multi_aff_drop.
 519  *
 520  * "pos" is the position of the first dimension to drop.
 521  * "n" is the number of dimensions to drop.
 522  * "res" accumulates the result.
 523  */
 524 struct isl_union_pw_multi_aff_drop_data {
 525         int pos;
 526         int n;
 527         isl_union_pw_multi_aff *res;
 528 };
 529
 530 /* Drop the data->n output dimensions starting at data->pos from "pma"
 531  * and add the result to data->res.
 532  */
 533 static int pw_multi_aff_drop(__isl_take isl_pw_multi_aff *pma, void *user)
 534 {
 535         struct isl_union_pw_multi_aff_drop_data *data = user;
 536
 537         pma = isl_pw_multi_aff_drop_dims(pma, isl_dim_out, data->pos, data->n);
 538
 539         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma);
 540         if (!data->res)
 541                 return -1;
 542
 543         return 0;
 544 }
 545
 546 /* Drop the "n" output dimensions starting at "pos" from "sched".
 547  */
 548 static isl_union_pw_multi_aff *isl_union_pw_multi_aff_drop(
 549         __isl_take isl_union_pw_multi_aff *sched, int pos, int n)
 550 {
 551         isl_space *space;
 552         struct isl_union_pw_multi_aff_drop_data data = { pos, n };
 553
 554         space = isl_union_pw_multi_aff_get_space(sched);
 555         data.res = isl_union_pw_multi_aff_empty(space);
 556
 557         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched,
 558                                                 &pw_multi_aff_drop, &data) < 0)
 559                 data.res = isl_union_pw_multi_aff_free(data.res);
 560
 561         isl_union_pw_multi_aff_free(sched);
 562         return data.res;
 563 }
 564
 565 /* Drop the "n" dimensions starting at "pos" from "band".
 566  */
 567 static int isl_band_drop(__isl_keep isl_band *band, int pos, int n)
 568 {
 569         int i;
 570         isl_union_pw_multi_aff *sched;
 571
 572         if (!band)
 573                 return -1;
 574         if (n == 0)
 575                 return 0;
 576
 577         sched = isl_union_pw_multi_aff_copy(band->pma);
 578         sched = isl_union_pw_multi_aff_drop(sched, pos, n);
 579         if (!sched)
 580                 return -1;
 581
 582         isl_union_pw_multi_aff_free(band->pma);
 583         band->pma = sched;
 584
 585         for (i = pos + n; i < band->n; ++i)
 586                 band->zero[i - n] = band->zero[i];
 587
 588         band->n -= n;
 589
 590         return 0;
 591 }
 592
 593 /* Split the given band into two nested bands, one with the first "pos"
 594  * dimensions of "band" and one with the remaining band->n - pos dimensions.
 595  */
 596 int isl_band_split(__isl_keep isl_band *band, int pos)
 597 {
 598         isl_ctx *ctx;
 599         isl_band *child;
 600         isl_band_list *list;
 601
 602         if (!band)
 603                 return -1;
 604
 605         ctx = isl_band_get_ctx(band);
 606
 607         if (pos < 0 || pos > band->n)
 608                 isl_die(ctx, isl_error_invalid, "position out of bounds",
 609                         return -1);
 610
 611         child = isl_band_dup(band);
 612         if (isl_band_drop(child, 0, pos) < 0)
 613                 child = isl_band_free(child);
 614         list = isl_band_list_alloc(ctx, 1);
 615         list = isl_band_list_add(list, child);
 616         if (!list)
 617                 return -1;
 618
 619         if (isl_band_drop(band, pos, band->n - pos) < 0) {
 620                 isl_band_list_free(list);
 621                 return -1;
 622         }
 623
 624         child->children = band->children;
 625         band->children = list;
 626         child->parent = band;
 627
 628         return 0;
 629 }
 630
 631 __isl_give isl_printer *isl_printer_print_band(__isl_take isl_printer *p,
 632         __isl_keep isl_band *band)
 633 {
 634         isl_union_map *prefix, *partial, *suffix;
 635
 636         prefix = isl_band_get_prefix_schedule(band);
 637         partial = isl_band_get_partial_schedule(band);
 638         suffix = isl_band_get_suffix_schedule(band);
 639
 640         p = isl_printer_print_str(p, "(");
 641         p = isl_printer_print_union_map(p, prefix);
 642         p = isl_printer_print_str(p, ",");
 643         p = isl_printer_print_union_map(p, partial);
 644         p = isl_printer_print_str(p, ",");
 645         p = isl_printer_print_union_map(p, suffix);
 646         p = isl_printer_print_str(p, ")");
 647
 648         isl_union_map_free(prefix);
 649         isl_union_map_free(partial);
 650         isl_union_map_free(suffix);
 651
 652         return p;
 653 }