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