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 /* Return the number of scheduling dimensions in the band.
 146  */
 147 int isl_schedule_band_n_member(__isl_keep isl_schedule_band *band)
 148 {
 149         return band ? band->n : 0;
 150 }
 151
 152 /* Is the given scheduling dimension coincident within the band and
 153  * with respect to the coincidence constraints?
 154  */
 155 int isl_schedule_band_member_get_coincident(__isl_keep isl_schedule_band *band,
 156         int pos)
 157 {
 158         if (!band)
 159                 return -1;
 160
 161         if (pos < 0 || pos >= band->n)
 162                 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
 163                         "invalid member position", return -1);
 164
 165         return band->coincident[pos];
 166 }
 167
 168 /* Mark the given scheduling dimension as being coincident or not
 169  * according to "coincident".
 170  */
 171 __isl_give isl_schedule_band *isl_schedule_band_member_set_coincident(
 172         __isl_take isl_schedule_band *band, int pos, int coincident)
 173 {
 174         if (!band)
 175                 return NULL;
 176         if (isl_schedule_band_member_get_coincident(band, pos) == coincident)
 177                 return band;
 178         band = isl_schedule_band_cow(band);
 179         if (!band)
 180                 return NULL;
 181
 182         if (pos < 0 || pos >= band->n)
 183                 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
 184                         "invalid member position",
 185                         isl_schedule_band_free(band));
 186
 187         band->coincident[pos] = coincident;
 188
 189         return band;
 190 }
 191
 192 /* Is the schedule band mark permutable?
 193  */
 194 int isl_schedule_band_get_permutable(__isl_keep isl_schedule_band *band)
 195 {
 196         if (!band)
 197                 return -1;
 198         return band->permutable;
 199 }
 200
 201 /* Mark the schedule band permutable or not according to "permutable"?
 202  */
 203 __isl_give isl_schedule_band *isl_schedule_band_set_permutable(
 204         __isl_take isl_schedule_band *band, int permutable)
 205 {
 206         if (!band)
 207                 return NULL;
 208         if (band->permutable == permutable)
 209                 return band;
 210         band = isl_schedule_band_cow(band);
 211         if (!band)
 212                 return NULL;
 213
 214         band->permutable = permutable;
 215
 216         return band;
 217 }
 218
 219 /* Return the schedule space of the band.
 220  */
 221 __isl_give isl_space *isl_schedule_band_get_space(
 222         __isl_keep isl_schedule_band *band)
 223 {
 224         if (!band)
 225                 return NULL;
 226         return isl_multi_union_pw_aff_get_space(band->mupa);
 227 }
 228
 229 /* Return the schedule of the band in isolation.
 230  */
 231 __isl_give isl_multi_union_pw_aff *isl_schedule_band_get_partial_schedule(
 232         __isl_keep isl_schedule_band *band)
 233 {
 234         return band ? isl_multi_union_pw_aff_copy(band->mupa) : NULL;
 235 }
 236
 237 /* Multiply the partial schedule of "band" with the factors in "mv".
 238  * Replace the result by its greatest integer part to ensure
 239  * that the schedule is always integral.
 240  */
 241 __isl_give isl_schedule_band *isl_schedule_band_scale(
 242         __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
 243 {
 244         band = isl_schedule_band_cow(band);
 245         if (!band || !mv)
 246                 goto error;
 247         band->mupa = isl_multi_union_pw_aff_scale_multi_val(band->mupa, mv);
 248         band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
 249         if (!band->mupa)
 250                 return isl_schedule_band_free(band);
 251         return band;
 252 error:
 253         isl_schedule_band_free(band);
 254         isl_multi_val_free(mv);
 255         return NULL;
 256 }
 257
 258 /* Divide the partial schedule of "band" by the factors in "mv".
 259  * Replace the result by its greatest integer part to ensure
 260  * that the schedule is always integral.
 261  */
 262 __isl_give isl_schedule_band *isl_schedule_band_scale_down(
 263         __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
 264 {
 265         band = isl_schedule_band_cow(band);
 266         if (!band || !mv)
 267                 goto error;
 268         band->mupa = isl_multi_union_pw_aff_scale_down_multi_val(band->mupa,
 269                                                                 mv);
 270         band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
 271         if (!band->mupa)
 272                 return isl_schedule_band_free(band);
 273         return band;
 274 error:
 275         isl_schedule_band_free(band);
 276         isl_multi_val_free(mv);
 277         return NULL;
 278 }
 279
 280 /* Given the schedule of a band, construct the corresponding
 281  * schedule for the tile loops based on the given tile sizes
 282  * and return the result.
 283  *
 284  * If the scale tile loops options is set, then the tile loops
 285  * are scaled by the tile sizes.
 286  *
 287  * That is replace each schedule dimension "i" by either
 288  * "floor(i/s)" or "s * floor(i/s)".
 289  */
 290 static isl_multi_union_pw_aff *isl_multi_union_pw_aff_tile(
 291         __isl_take isl_multi_union_pw_aff *sched,
 292         __isl_take isl_multi_val *sizes)
 293 {
 294         isl_ctx *ctx;
 295         int i, n;
 296         isl_val *v;
 297         int scale;
 298
 299         ctx = isl_multi_val_get_ctx(sizes);
 300         scale = isl_options_get_tile_scale_tile_loops(ctx);
 301
 302         n = isl_multi_union_pw_aff_dim(sched, isl_dim_set);
 303         for (i = 0; i < n; ++i) {
 304                 isl_union_pw_aff *upa;
 305
 306                 upa = isl_multi_union_pw_aff_get_union_pw_aff(sched, i);
 307                 v = isl_multi_val_get_val(sizes, i);
 308
 309                 upa = isl_union_pw_aff_scale_down_val(upa, isl_val_copy(v));
 310                 upa = isl_union_pw_aff_floor(upa);
 311                 if (scale)
 312                         upa = isl_union_pw_aff_scale_val(upa, isl_val_copy(v));
 313                 isl_val_free(v);
 314
 315                 sched = isl_multi_union_pw_aff_set_union_pw_aff(sched, i, upa);
 316         }
 317
 318         isl_multi_val_free(sizes);
 319         return sched;
 320 }
 321
 322 /* Replace "band" by a band corresponding to the tile loops of a tiling
 323  * with the given tile sizes.
 324  */
 325 __isl_give isl_schedule_band *isl_schedule_band_tile(
 326         __isl_take isl_schedule_band *band, __isl_take isl_multi_val *sizes)
 327 {
 328         band = isl_schedule_band_cow(band);
 329         if (!band || !sizes)
 330                 goto error;
 331         band->mupa = isl_multi_union_pw_aff_tile(band->mupa, sizes);
 332         if (!band->mupa)
 333                 return isl_schedule_band_free(band);
 334         return band;
 335 error:
 336         isl_schedule_band_free(band);
 337         isl_multi_val_free(sizes);
 338         return NULL;
 339 }
 340
 341 /* Replace "band" by a band corresponding to the point loops of a tiling
 342  * with the given tile sizes.
 343  * "tile" is the corresponding tile loop band.
 344  *
 345  * If the shift point loops option is set, then the point loops
 346  * are shifted to start at zero.  That is, each schedule dimension "i"
 347  * is replaced by "i - s * floor(i/s)".
 348  * The expression "floor(i/s)" (or "s * floor(i/s)") is extracted from
 349  * the tile band.
 350  *
 351  * Otherwise, the band is left untouched.
 352  */
 353 __isl_give isl_schedule_band *isl_schedule_band_point(
 354         __isl_take isl_schedule_band *band, __isl_keep isl_schedule_band *tile,
 355         __isl_take isl_multi_val *sizes)
 356 {
 357         isl_ctx *ctx;
 358         isl_multi_union_pw_aff *scaled;
 359
 360         if (!band || !sizes)
 361                 goto error;
 362
 363         ctx = isl_schedule_band_get_ctx(band);
 364         if (!isl_options_get_tile_shift_point_loops(ctx)) {
 365                 isl_multi_val_free(sizes);
 366                 return band;
 367         }
 368         band = isl_schedule_band_cow(band);
 369         if (!band)
 370                 goto error;
 371
 372         scaled = isl_schedule_band_get_partial_schedule(tile);
 373         if (!isl_options_get_tile_scale_tile_loops(ctx))
 374                 scaled = isl_multi_union_pw_aff_scale_multi_val(scaled, sizes);
 375         else
 376                 isl_multi_val_free(sizes);
 377         band->mupa = isl_multi_union_pw_aff_sub(band->mupa, scaled);
 378         if (!band->mupa)
 379                 return isl_schedule_band_free(band);
 380         return band;
 381 error:
 382         isl_schedule_band_free(band);
 383         isl_multi_val_free(sizes);
 384         return NULL;
 385 }
 386
 387 /* Drop the "n" dimensions starting at "pos" from "band".
 388  *
 389  * We apply the transformation even if "n" is zero to ensure consistent
 390  * behavior with respect to changes in the schedule space.
 391  */
 392 __isl_give isl_schedule_band *isl_schedule_band_drop(
 393         __isl_take isl_schedule_band *band, int pos, int n)
 394 {
 395         int i;
 396
 397         if (pos < 0 || n < 0 || pos + n > band->n)
 398                 isl_die(isl_schedule_band_get_ctx(band), isl_error_internal,
 399                         "range out of bounds",
 400                         return isl_schedule_band_free(band));
 401
 402         band = isl_schedule_band_cow(band);
 403         if (!band)
 404                 return NULL;
 405
 406         band->mupa = isl_multi_union_pw_aff_drop_dims(band->mupa,
 407                                                         isl_dim_set, pos, n);
 408         if (!band->mupa)
 409                 return isl_schedule_band_free(band);
 410
 411         for (i = pos + n; i < band->n; ++i)
 412                 band->coincident[i - n] = band->coincident[i];
 413
 414         band->n -= n;
 415
 416         return band;
 417 }