isl_schedule_band.c

   1 /*
   2  * Copyright 2013-2014 Ecole Normale Superieure
   3  * Copyright 2014      INRIA Rocquencourt
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege,
   8  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   9  * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
  10  * B.P. 105 - 78153 Le Chesnay, France
  11  */
  12
  13 #include <isl/schedule_node.h>
  14 #include <isl_schedule_band.h>
  15 #include <isl_schedule_private.h>
  16
  17 isl_ctx *isl_schedule_band_get_ctx(__isl_keep isl_schedule_band *band)
  18 {
  19         return band ? isl_multi_union_pw_aff_get_ctx(band->mupa) : NULL;
  20 }
  21
  22 /* Return a new uninitialized isl_schedule_band.
  23  */
  24 static __isl_give isl_schedule_band *isl_schedule_band_alloc(isl_ctx *ctx)
  25 {
  26         isl_schedule_band *band;
  27
  28         band = isl_calloc_type(ctx, isl_schedule_band);
  29         if (!band)
  30                 return NULL;
  31
  32         band->ref = 1;
  33
  34         return band;
  35 }
  36
  37 /* Return a new isl_schedule_band with partial schedule "mupa".
  38  * First replace "mupa" by its greatest integer part to ensure
  39  * that the schedule is always integral.
  40  * The band is not marked permutable and the dimensions are not
  41  * marked coincident.
  42  */
  43 __isl_give isl_schedule_band *isl_schedule_band_from_multi_union_pw_aff(
  44         __isl_take isl_multi_union_pw_aff *mupa)
  45 {
  46         isl_ctx *ctx;
  47         isl_schedule_band *band;
  48
  49         mupa = isl_multi_union_pw_aff_floor(mupa);
  50         if (!mupa)
  51                 return NULL;
  52         ctx = isl_multi_union_pw_aff_get_ctx(mupa);
  53         band = isl_schedule_band_alloc(ctx);
  54         if (!band)
  55                 goto error;
  56
  57         band->n = isl_multi_union_pw_aff_dim(mupa, isl_dim_set);
  58         band->coincident = isl_calloc_array(ctx, int, band->n);
  59         band->mupa = mupa;
  60
  61         if (band->n && !band->coincident)
  62                 return isl_schedule_band_free(band);
  63
  64         return band;
  65 error:
  66         isl_multi_union_pw_aff_free(mupa);
  67         return NULL;
  68 }
  69
  70 /* Create a duplicate of the given isl_schedule_band.
  71  */
  72 __isl_give isl_schedule_band *isl_schedule_band_dup(
  73         __isl_keep isl_schedule_band *band)
  74 {
  75         int i;
  76         isl_ctx *ctx;
  77         isl_schedule_band *dup;
  78
  79         if (!band)
  80                 return NULL;
  81
  82         ctx = isl_schedule_band_get_ctx(band);
  83         dup = isl_schedule_band_alloc(ctx);
  84         if (!dup)
  85                 return NULL;
  86
  87         dup->n = band->n;
  88         dup->coincident = isl_alloc_array(ctx, int, band->n);
  89         if (band->n && !dup->coincident)
  90                 return isl_schedule_band_free(dup);
  91
  92         for (i = 0; i < band->n; ++i)
  93                 dup->coincident[i] = band->coincident[i];
  94         dup->permutable = band->permutable;
  95
  96         dup->mupa = isl_multi_union_pw_aff_copy(band->mupa);
  97         if (!dup->mupa)
  98                 return isl_schedule_band_free(dup);
  99
 100         return dup;
 101 }
 102
 103 /* Return an isl_schedule_band that is equal to "band" and that has only
 104  * a single reference.
 105  */
 106 __isl_give isl_schedule_band *isl_schedule_band_cow(
 107         __isl_take isl_schedule_band *band)
 108 {
 109         if (!band)
 110                 return NULL;
 111
 112         if (band->ref == 1)
 113                 return band;
 114         band->ref--;
 115         return isl_schedule_band_dup(band);
 116 }
 117
 118 /* Return a new reference to "band".
 119  */
 120 __isl_give isl_schedule_band *isl_schedule_band_copy(
 121         __isl_keep isl_schedule_band *band)
 122 {
 123         if (!band)
 124                 return NULL;
 125
 126         band->ref++;
 127         return band;
 128 }
 129
 130 /* Free a reference to "band" and return NULL.
 131  */
 132 __isl_null isl_schedule_band *isl_schedule_band_free(
 133         __isl_take isl_schedule_band *band)
 134 {
 135         if (!band)
 136                 return NULL;
 137
 138         if (--band->ref > 0)
 139                 return NULL;
 140
 141         isl_multi_union_pw_aff_free(band->mupa);
 142         free(band->coincident);
 143         free(band);
 144
 145         return NULL;
 146 }
 147
 148 /* Are "band1" and "band2" obviously equal?
 149  */
 150 int isl_schedule_band_plain_is_equal(__isl_keep isl_schedule_band *band1,
 151         __isl_keep isl_schedule_band *band2)
 152 {
 153         int i;
 154
 155         if (!band1 || !band2)
 156                 return -1;
 157         if (band1 == band2)
 158                 return 1;
 159
 160         if (band1->n != band2->n)
 161                 return 0;
 162         for (i = 0; i < band1->n; ++i)
 163                 if (band1->coincident[i] != band2->coincident[i])
 164                         return 0;
 165         if (band1->permutable != band2->permutable)
 166                 return 0;
 167
 168         return isl_multi_union_pw_aff_plain_is_equal(band1->mupa, band2->mupa);
 169 }
 170
 171 /* Return the number of scheduling dimensions in the band.
 172  */
 173 int isl_schedule_band_n_member(__isl_keep isl_schedule_band *band)
 174 {
 175         return band ? band->n : 0;
 176 }
 177
 178 /* Is the given scheduling dimension coincident within the band and
 179  * with respect to the coincidence constraints?
 180  */
 181 int isl_schedule_band_member_get_coincident(__isl_keep isl_schedule_band *band,
 182         int pos)
 183 {
 184         if (!band)
 185                 return -1;
 186
 187         if (pos < 0 || pos >= band->n)
 188                 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
 189                         "invalid member position", return -1);
 190
 191         return band->coincident[pos];
 192 }
 193
 194 /* Mark the given scheduling dimension as being coincident or not
 195  * according to "coincident".
 196  */
 197 __isl_give isl_schedule_band *isl_schedule_band_member_set_coincident(
 198         __isl_take isl_schedule_band *band, int pos, int coincident)
 199 {
 200         if (!band)
 201                 return NULL;
 202         if (isl_schedule_band_member_get_coincident(band, pos) == coincident)
 203                 return band;
 204         band = isl_schedule_band_cow(band);
 205         if (!band)
 206                 return NULL;
 207
 208         if (pos < 0 || pos >= band->n)
 209                 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
 210                         "invalid member position",
 211                         isl_schedule_band_free(band));
 212
 213         band->coincident[pos] = coincident;
 214
 215         return band;
 216 }
 217
 218 /* Is the schedule band mark permutable?
 219  */
 220 int isl_schedule_band_get_permutable(__isl_keep isl_schedule_band *band)
 221 {
 222         if (!band)
 223                 return -1;
 224         return band->permutable;
 225 }
 226
 227 /* Mark the schedule band permutable or not according to "permutable"?
 228  */
 229 __isl_give isl_schedule_band *isl_schedule_band_set_permutable(
 230         __isl_take isl_schedule_band *band, int permutable)
 231 {
 232         if (!band)
 233                 return NULL;
 234         if (band->permutable == permutable)
 235                 return band;
 236         band = isl_schedule_band_cow(band);
 237         if (!band)
 238                 return NULL;
 239
 240         band->permutable = permutable;
 241
 242         return band;
 243 }
 244
 245 /* Return the schedule space of the band.
 246  */
 247 __isl_give isl_space *isl_schedule_band_get_space(
 248         __isl_keep isl_schedule_band *band)
 249 {
 250         if (!band)
 251                 return NULL;
 252         return isl_multi_union_pw_aff_get_space(band->mupa);
 253 }
 254
 255 /* Return the schedule of the band in isolation.
 256  */
 257 __isl_give isl_multi_union_pw_aff *isl_schedule_band_get_partial_schedule(
 258         __isl_keep isl_schedule_band *band)
 259 {
 260         return band ? isl_multi_union_pw_aff_copy(band->mupa) : NULL;
 261 }
 262
 263 /* Multiply the partial schedule of "band" with the factors in "mv".
 264  * Replace the result by its greatest integer part to ensure
 265  * that the schedule is always integral.
 266  */
 267 __isl_give isl_schedule_band *isl_schedule_band_scale(
 268         __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
 269 {
 270         band = isl_schedule_band_cow(band);
 271         if (!band || !mv)
 272                 goto error;
 273         band->mupa = isl_multi_union_pw_aff_scale_multi_val(band->mupa, mv);
 274         band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
 275         if (!band->mupa)
 276                 return isl_schedule_band_free(band);
 277         return band;
 278 error:
 279         isl_schedule_band_free(band);
 280         isl_multi_val_free(mv);
 281         return NULL;
 282 }
 283
 284 /* Divide the partial schedule of "band" by the factors in "mv".
 285  * Replace the result by its greatest integer part to ensure
 286  * that the schedule is always integral.
 287  */
 288 __isl_give isl_schedule_band *isl_schedule_band_scale_down(
 289         __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
 290 {
 291         band = isl_schedule_band_cow(band);
 292         if (!band || !mv)
 293                 goto error;
 294         band->mupa = isl_multi_union_pw_aff_scale_down_multi_val(band->mupa,
 295                                                                 mv);
 296         band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
 297         if (!band->mupa)
 298                 return isl_schedule_band_free(band);
 299         return band;
 300 error:
 301         isl_schedule_band_free(band);
 302         isl_multi_val_free(mv);
 303         return NULL;
 304 }
 305
 306 /* Given the schedule of a band, construct the corresponding
 307  * schedule for the tile loops based on the given tile sizes
 308  * and return the result.
 309  *
 310  * If the scale tile loops options is set, then the tile loops
 311  * are scaled by the tile sizes.
 312  *
 313  * That is replace each schedule dimension "i" by either
 314  * "floor(i/s)" or "s * floor(i/s)".
 315  */
 316 static isl_multi_union_pw_aff *isl_multi_union_pw_aff_tile(
 317         __isl_take isl_multi_union_pw_aff *sched,
 318         __isl_take isl_multi_val *sizes)
 319 {
 320         isl_ctx *ctx;
 321         int i, n;
 322         isl_val *v;
 323         int scale;
 324
 325         ctx = isl_multi_val_get_ctx(sizes);
 326         scale = isl_options_get_tile_scale_tile_loops(ctx);
 327
 328         n = isl_multi_union_pw_aff_dim(sched, isl_dim_set);
 329         for (i = 0; i < n; ++i) {
 330                 isl_union_pw_aff *upa;
 331
 332                 upa = isl_multi_union_pw_aff_get_union_pw_aff(sched, i);
 333                 v = isl_multi_val_get_val(sizes, i);
 334
 335                 upa = isl_union_pw_aff_scale_down_val(upa, isl_val_copy(v));
 336                 upa = isl_union_pw_aff_floor(upa);
 337                 if (scale)
 338                         upa = isl_union_pw_aff_scale_val(upa, isl_val_copy(v));
 339                 isl_val_free(v);
 340
 341                 sched = isl_multi_union_pw_aff_set_union_pw_aff(sched, i, upa);
 342         }
 343
 344         isl_multi_val_free(sizes);
 345         return sched;
 346 }
 347
 348 /* Replace "band" by a band corresponding to the tile loops of a tiling
 349  * with the given tile sizes.
 350  */
 351 __isl_give isl_schedule_band *isl_schedule_band_tile(
 352         __isl_take isl_schedule_band *band, __isl_take isl_multi_val *sizes)
 353 {
 354         band = isl_schedule_band_cow(band);
 355         if (!band || !sizes)
 356                 goto error;
 357         band->mupa = isl_multi_union_pw_aff_tile(band->mupa, sizes);
 358         if (!band->mupa)
 359                 return isl_schedule_band_free(band);
 360         return band;
 361 error:
 362         isl_schedule_band_free(band);
 363         isl_multi_val_free(sizes);
 364         return NULL;
 365 }
 366
 367 /* Replace "band" by a band corresponding to the point loops of a tiling
 368  * with the given tile sizes.
 369  * "tile" is the corresponding tile loop band.
 370  *
 371  * If the shift point loops option is set, then the point loops
 372  * are shifted to start at zero.  That is, each schedule dimension "i"
 373  * is replaced by "i - s * floor(i/s)".
 374  * The expression "floor(i/s)" (or "s * floor(i/s)") is extracted from
 375  * the tile band.
 376  *
 377  * Otherwise, the band is left untouched.
 378  */
 379 __isl_give isl_schedule_band *isl_schedule_band_point(
 380         __isl_take isl_schedule_band *band, __isl_keep isl_schedule_band *tile,
 381         __isl_take isl_multi_val *sizes)
 382 {
 383         isl_ctx *ctx;
 384         isl_multi_union_pw_aff *scaled;
 385
 386         if (!band || !sizes)
 387                 goto error;
 388
 389         ctx = isl_schedule_band_get_ctx(band);
 390         if (!isl_options_get_tile_shift_point_loops(ctx)) {
 391                 isl_multi_val_free(sizes);
 392                 return band;
 393         }
 394         band = isl_schedule_band_cow(band);
 395         if (!band)
 396                 goto error;
 397
 398         scaled = isl_schedule_band_get_partial_schedule(tile);
 399         if (!isl_options_get_tile_scale_tile_loops(ctx))
 400                 scaled = isl_multi_union_pw_aff_scale_multi_val(scaled, sizes);
 401         else
 402                 isl_multi_val_free(sizes);
 403         band->mupa = isl_multi_union_pw_aff_sub(band->mupa, scaled);
 404         if (!band->mupa)
 405                 return isl_schedule_band_free(band);
 406         return band;
 407 error:
 408         isl_schedule_band_free(band);
 409         isl_multi_val_free(sizes);
 410         return NULL;
 411 }
 412
 413 /* Drop the "n" dimensions starting at "pos" from "band".
 414  *
 415  * We apply the transformation even if "n" is zero to ensure consistent
 416  * behavior with respect to changes in the schedule space.
 417  */
 418 __isl_give isl_schedule_band *isl_schedule_band_drop(
 419         __isl_take isl_schedule_band *band, int pos, int n)
 420 {
 421         int i;
 422
 423         if (pos < 0 || n < 0 || pos + n > band->n)
 424                 isl_die(isl_schedule_band_get_ctx(band), isl_error_internal,
 425                         "range out of bounds",
 426                         return isl_schedule_band_free(band));
 427
 428         band = isl_schedule_band_cow(band);
 429         if (!band)
 430                 return NULL;
 431
 432         band->mupa = isl_multi_union_pw_aff_drop_dims(band->mupa,
 433                                                         isl_dim_set, pos, n);
 434         if (!band->mupa)
 435                 return isl_schedule_band_free(band);
 436
 437         for (i = pos + n; i < band->n; ++i)
 438                 band->coincident[i - n] = band->coincident[i];
 439
 440         band->n -= n;
 441
 442         return band;
 443 }
 444
 445 /* Reset the user pointer on all identifiers of parameters and tuples
 446  * in "band".
 447  */
 448 __isl_give isl_schedule_band *isl_schedule_band_reset_user(
 449         __isl_take isl_schedule_band *band)
 450 {
 451         band = isl_schedule_band_cow(band);
 452         if (!band)
 453                 return NULL;
 454
 455         band->mupa = isl_multi_union_pw_aff_reset_user(band->mupa);
 456         if (!band->mupa)
 457                 return isl_schedule_band_free(band);
 458
 459         return band;
 460 }
 461
 462 /* Align the parameters of "band" to those of "space".
 463  */
 464 __isl_give isl_schedule_band *isl_schedule_band_align_params(
 465         __isl_take isl_schedule_band *band, __isl_take isl_space *space)
 466 {
 467         band = isl_schedule_band_cow(band);
 468         if (!band || !space)
 469                 goto error;
 470
 471         band->mupa = isl_multi_union_pw_aff_align_params(band->mupa, space);
 472         if (!band->mupa)
 473                 return isl_schedule_band_free(band);
 474
 475         return band;
 476 error:
 477         isl_space_free(space);
 478         isl_schedule_band_free(band);
 479         return NULL;
 480 }
 481
 482 /* Compute the pullback of "band" by the function represented by "upma".
 483  * In other words, plug in "upma" in the iteration domains of "band".
 484  */
 485 __isl_give isl_schedule_band *isl_schedule_band_pullback_union_pw_multi_aff(
 486         __isl_take isl_schedule_band *band,
 487         __isl_take isl_union_pw_multi_aff *upma)
 488 {
 489         band = isl_schedule_band_cow(band);
 490         if (!band || !upma)
 491                 goto error;
 492
 493         band->mupa =
 494                 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(band->mupa,
 495                                                                         upma);
 496         if (!band->mupa)
 497                 return isl_schedule_band_free(band);
 498
 499         return band;
 500 error:
 501         isl_union_pw_multi_aff_free(upma);
 502         isl_schedule_band_free(band);
 503         return NULL;
 504 }
 505
 506 /* Compute the gist of "band" with respect to "context".
 507  * In particular, compute the gist of the associated partial schedule.
 508  */
 509 __isl_give isl_schedule_band *isl_schedule_band_gist(
 510         __isl_take isl_schedule_band *band, __isl_take isl_union_set *context)
 511 {
 512         if (!band || !context)
 513                 goto error;
 514         if (band->n == 0) {
 515                 isl_union_set_free(context);
 516                 return band;
 517         }
 518         band = isl_schedule_band_cow(band);
 519         if (!band)
 520                 goto error;
 521         band->mupa = isl_multi_union_pw_aff_gist(band->mupa, context);
 522         if (!band->mupa)
 523                 return isl_schedule_band_free(band);
 524         return band;
 525 error:
 526         isl_union_set_free(context);
 527         isl_schedule_band_free(band);
 528         return NULL;
 529 }