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