isl_schedule_band.c

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