isl_band.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_band_private.h>
  12 #include <isl_schedule_private.h>
  13 #include <isl_list_private.h>
  14
  15 isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band)
  16 {
  17         return band ? isl_union_pw_multi_aff_get_ctx(band->pma) : NULL;
  18 }
  19
  20 __isl_give isl_band *isl_band_alloc(isl_ctx *ctx)
  21 {
  22         isl_band *band;
  23
  24         band = isl_calloc_type(ctx, isl_band);
  25         if (!band)
  26                 return NULL;
  27
  28         band->ref = 1;
  29
  30         return band;
  31 }
  32
  33 /* Create a duplicate of the given band.  The duplicate refers
  34  * to the same schedule and parent as the input, but does not
  35  * increment their reference counts.
  36  */
  37 __isl_give isl_band *isl_band_dup(__isl_keep isl_band *band)
  38 {
  39         int i;
  40         isl_ctx *ctx;
  41         isl_band *dup;
  42
  43         if (!band)
  44                 return NULL;
  45
  46         ctx = isl_band_get_ctx(band);
  47         dup = isl_band_alloc(ctx);
  48         if (!dup)
  49                 return NULL;
  50
  51         dup->n = band->n;
  52         dup->zero = isl_alloc_array(ctx, int, band->n);
  53         if (!dup->zero)
  54                 goto error;
  55
  56         for (i = 0; i < band->n; ++i)
  57                 dup->zero[i] = band->zero[i];
  58
  59         dup->pma = isl_union_pw_multi_aff_copy(band->pma);
  60         dup->schedule = band->schedule;
  61         dup->parent = band->parent;
  62
  63         if (!dup->pma)
  64                 goto error;
  65
  66         return dup;
  67 error:
  68         isl_band_free(dup);
  69         return NULL;
  70 }
  71
  72 /* We not only increment the reference count of the band,
  73  * but also that of the schedule that contains this band.
  74  * This ensures that the schedule won't disappear while there
  75  * is still a reference to the band outside of the schedule.
  76  * There is no need to increment the reference count of the parent
  77  * band as the parent band is part of the same schedule.
  78  */
  79 __isl_give isl_band *isl_band_copy(__isl_keep isl_band *band)
  80 {
  81         if (!band)
  82                 return NULL;
  83
  84         band->ref++;
  85         band->schedule->ref++;
  86         return band;
  87 }
  88
  89 /* If this is not the last reference to the band (the one from within the
  90  * schedule), then we also need to decrement the reference count of the
  91  * containing schedule as it was incremented in isl_band_copy.
  92  */
  93 void *isl_band_free(__isl_take isl_band *band)
  94 {
  95         if (!band)
  96                 return NULL;
  97
  98         if (--band->ref > 0)
  99                 return isl_schedule_free(band->schedule);
 100
 101         isl_union_pw_multi_aff_free(band->pma);
 102         isl_band_list_free(band->children);
 103         free(band->zero);
 104         free(band);
 105
 106         return NULL;
 107 }
 108
 109 int isl_band_has_children(__isl_keep isl_band *band)
 110 {
 111         if (!band)
 112                 return -1;
 113
 114         return band->children != NULL;
 115 }
 116
 117 __isl_give isl_band_list *isl_band_get_children(
 118         __isl_keep isl_band *band)
 119 {
 120         if (!band)
 121                 return NULL;
 122         if (!band->children)
 123                 isl_die(isl_band_get_ctx(band), isl_error_invalid,
 124                         "band has no children", return NULL);
 125         return isl_band_list_dup(band->children);
 126 }
 127
 128 int isl_band_n_member(__isl_keep isl_band *band)
 129 {
 130         return band ? band->n : 0;
 131 }
 132
 133 /* Is the given scheduling dimension zero distance within the band and
 134  * with respect to the proximity dependences.
 135  */
 136 int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos)
 137 {
 138         if (!band)
 139                 return -1;
 140
 141         if (pos < 0 || pos >= band->n)
 142                 isl_die(isl_band_get_ctx(band), isl_error_invalid,
 143                         "invalid member position", return -1);
 144
 145         return band->zero[pos];
 146 }
 147
 148 /* Return the schedule that leads up to this band.
 149  */
 150 __isl_give isl_union_map *isl_band_get_prefix_schedule(
 151         __isl_keep isl_band *band)
 152 {
 153         isl_union_set *domain;
 154         isl_union_pw_multi_aff *prefix;
 155         isl_band *a;
 156
 157         if (!band)
 158                 return NULL;
 159
 160         prefix = isl_union_pw_multi_aff_copy(band->pma);
 161         domain = isl_union_pw_multi_aff_domain(prefix);
 162         prefix = isl_union_pw_multi_aff_from_domain(domain);
 163
 164         for (a = band->parent; a; a = a->parent) {
 165                 isl_union_pw_multi_aff *partial;
 166
 167                 partial = isl_union_pw_multi_aff_copy(a->pma);
 168                 prefix = isl_union_pw_multi_aff_flat_range_product(partial,
 169                                                                    prefix);
 170         }
 171
 172         return isl_union_map_from_union_pw_multi_aff(prefix);
 173 }
 174
 175 /* Return the schedule of the band in isolation.
 176  */
 177 __isl_give isl_union_pw_multi_aff *
 178 isl_band_get_partial_schedule_union_pw_multi_aff(__isl_keep isl_band *band)
 179 {
 180         return band ? isl_union_pw_multi_aff_copy(band->pma) : NULL;
 181 }
 182
 183 /* Return the schedule of the band in isolation.
 184  */
 185 __isl_give isl_union_map *isl_band_get_partial_schedule(
 186         __isl_keep isl_band *band)
 187 {
 188         isl_union_pw_multi_aff *sched;
 189
 190         sched = isl_band_get_partial_schedule_union_pw_multi_aff(band);
 191         return isl_union_map_from_union_pw_multi_aff(sched);
 192 }
 193
 194 __isl_give isl_union_pw_multi_aff *
 195 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band);
 196
 197 /* Return the schedule for the given band list.
 198  * For each band in the list, the schedule is composed of the partial
 199  * and suffix schedules of that band.
 200  */
 201 __isl_give isl_union_pw_multi_aff *
 202 isl_band_list_get_suffix_schedule_union_pw_multi_aff(
 203         __isl_keep isl_band_list *list)
 204 {
 205         isl_ctx *ctx;
 206         int i, n;
 207         isl_space *space;
 208         isl_union_pw_multi_aff *suffix;
 209
 210         if (!list)
 211                 return NULL;
 212
 213         ctx = isl_band_list_get_ctx(list);
 214         space = isl_space_alloc(ctx, 0, 0, 0);
 215         suffix = isl_union_pw_multi_aff_empty(space);
 216         n = isl_band_list_n_band(list);
 217         for (i = 0; i < n; ++i) {
 218                 isl_band *el;
 219                 isl_union_pw_multi_aff *partial;
 220                 isl_union_pw_multi_aff *suffix_i;
 221
 222                 el = isl_band_list_get_band(list, i);
 223                 partial = isl_band_get_partial_schedule_union_pw_multi_aff(el);
 224                 suffix_i = isl_band_get_suffix_schedule_union_pw_multi_aff(el);
 225                 suffix_i = isl_union_pw_multi_aff_flat_range_product(
 226                                 partial, suffix_i);
 227                 suffix = isl_union_pw_multi_aff_add(suffix, suffix_i);
 228
 229                 isl_band_free(el);
 230         }
 231
 232         return suffix;
 233 }
 234
 235 /* Return the schedule for the given band list.
 236  * For each band in the list, the schedule is composed of the partial
 237  * and suffix schedules of that band.
 238  */
 239 __isl_give isl_union_map *isl_band_list_get_suffix_schedule(
 240         __isl_keep isl_band_list *list)
 241 {
 242         isl_union_pw_multi_aff *suffix;
 243
 244         suffix = isl_band_list_get_suffix_schedule_union_pw_multi_aff(list);
 245         return isl_union_map_from_union_pw_multi_aff(suffix);
 246 }
 247
 248 /* Return the schedule for the forest underneath the given band.
 249  */
 250 __isl_give isl_union_pw_multi_aff *
 251 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band)
 252 {
 253         isl_union_pw_multi_aff *suffix;
 254
 255         if (!band)
 256                 return NULL;
 257
 258         if (!isl_band_has_children(band)) {
 259                 isl_union_set *domain;
 260
 261                 suffix = isl_union_pw_multi_aff_copy(band->pma);
 262                 domain = isl_union_pw_multi_aff_domain(suffix);
 263                 suffix = isl_union_pw_multi_aff_from_domain(domain);
 264         } else {
 265                 isl_band_list *list;
 266
 267                 list = isl_band_get_children(band);
 268                 suffix =
 269                     isl_band_list_get_suffix_schedule_union_pw_multi_aff(list);
 270                 isl_band_list_free(list);
 271         }
 272
 273         return suffix;
 274 }
 275
 276 /* Return the schedule for the forest underneath the given band.
 277  */
 278 __isl_give isl_union_map *isl_band_get_suffix_schedule(
 279         __isl_keep isl_band *band)
 280 {
 281         isl_union_pw_multi_aff *suffix;
 282
 283         suffix = isl_band_get_suffix_schedule_union_pw_multi_aff(band);
 284         return isl_union_map_from_union_pw_multi_aff(suffix);
 285 }
 286
 287 /* Call "fn" on each band (recursively) in the list
 288  * in depth-first post-order.
 289  */
 290 int isl_band_list_foreach_band(__isl_keep isl_band_list *list,
 291         int (*fn)(__isl_keep isl_band *band, void *user), void *user)
 292 {
 293         int i, n;
 294
 295         if (!list)
 296                 return -1;
 297
 298         n = isl_band_list_n_band(list);
 299         for (i = 0; i < n; ++i) {
 300                 isl_band *band;
 301                 int r = 0;
 302
 303                 band = isl_band_list_get_band(list, i);
 304                 if (isl_band_has_children(band)) {
 305                         isl_band_list *children;
 306
 307                         children = isl_band_get_children(band);
 308                         r = isl_band_list_foreach_band(children, fn, user);
 309                         isl_band_list_free(children);
 310                 }
 311
 312                 if (!band)
 313                         r = -1;
 314                 if (r == 0)
 315                         r = fn(band, user);
 316
 317                 isl_band_free(band);
 318                 if (r)
 319                         return r;
 320         }
 321
 322         return 0;
 323 }
 324
 325 /* Internal data used during the construction of the schedule
 326  * for the tile loops.
 327  *
 328  * sizes contains the tile sizes
 329  * scale is set if the tile loops should be scaled
 330  * tiled collects the result for a single statement
 331  * res collects the result for all statements
 332  */
 333 struct isl_band_tile_data {
 334         isl_vec *sizes;
 335         isl_union_pw_multi_aff *res;
 336         isl_pw_multi_aff *tiled;
 337         int scale;
 338 };
 339
 340 /* Given part of the schedule of a band, construct the corresponding
 341  * schedule for the tile loops based on the tile sizes in data->sizes
 342  * and add the result to data->tiled.
 343  *
 344  * If data->scale is set, then dimension i of the schedule will be
 345  * of the form
 346  *
 347  *      m_i * floor(s_i(x) / m_i)
 348  *
 349  * where s_i(x) refers to the original schedule and m_i is the tile size.
 350  * If data->scale is not set, then dimension i of the schedule will be
 351  * of the form
 352  *
 353  *      floor(s_i(x) / m_i)
 354  *
 355  */
 356 static int multi_aff_tile(__isl_take isl_set *set,
 357         __isl_take isl_multi_aff *ma, void *user)
 358 {
 359         struct isl_band_tile_data *data = user;
 360         isl_pw_multi_aff *pma;
 361         int i, n;
 362         isl_int v;
 363
 364         n = isl_multi_aff_dim(ma, isl_dim_out);
 365         if (isl_vec_size(data->sizes) < n)
 366                 n = isl_vec_size(data->sizes);
 367
 368         isl_int_init(v);
 369         for (i = 0; i < n; ++i) {
 370                 isl_aff *aff;
 371
 372                 aff = isl_multi_aff_get_aff(ma, i);
 373                 isl_vec_get_element(data->sizes, i, &v);
 374
 375                 aff = isl_aff_scale_down(aff, v);
 376                 aff = isl_aff_floor(aff);
 377                 if (data->scale)
 378                         aff = isl_aff_scale(aff, v);
 379
 380                 ma = isl_multi_aff_set_aff(ma, i, aff);
 381         }
 382         isl_int_clear(v);
 383
 384         pma = isl_pw_multi_aff_alloc(set, ma);
 385         data->tiled = isl_pw_multi_aff_union_add(data->tiled, pma);
 386
 387         return 0;
 388 }
 389
 390 /* Given part of the schedule of a band, construct the corresponding
 391  * schedule for the tile loops based on the tile sizes in data->sizes
 392  * and add the result to data->res.
 393  */
 394 static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff *pma, void *user)
 395 {
 396         struct isl_band_tile_data *data = user;
 397
 398         data->tiled = isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma));
 399
 400         if (isl_pw_multi_aff_foreach_piece(pma, &multi_aff_tile, data) < 0)
 401                 goto error;
 402
 403         isl_pw_multi_aff_free(pma);
 404         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res,
 405                                                                 data->tiled);
 406
 407         return 0;
 408 error:
 409         isl_pw_multi_aff_free(pma);
 410         isl_pw_multi_aff_free(data->tiled);
 411         return -1;
 412 }
 413
 414 /* Given the schedule of a band, construct the corresponding
 415  * schedule for the tile loops based on the given tile sizes
 416  * and return the result.
 417  */
 418 static isl_union_pw_multi_aff *isl_union_pw_multi_aff_tile(
 419         __isl_take isl_union_pw_multi_aff *sched, __isl_keep isl_vec *sizes)
 420 {
 421         isl_ctx *ctx;
 422         isl_space *space;
 423         struct isl_band_tile_data data = { sizes };
 424
 425         ctx = isl_vec_get_ctx(sizes);
 426
 427         space = isl_union_pw_multi_aff_get_space(sched);
 428         data.res = isl_union_pw_multi_aff_empty(space);
 429         data.scale = isl_options_get_tile_scale_tile_loops(ctx);
 430
 431         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched,
 432                                                 &pw_multi_aff_tile, &data) < 0)
 433                 goto error;
 434
 435         isl_union_pw_multi_aff_free(sched);
 436         return data.res;
 437 error:
 438         isl_union_pw_multi_aff_free(sched);
 439         isl_union_pw_multi_aff_free(data.res);
 440         return NULL;
 441 }
 442
 443 /* Tile the given band using the specified tile sizes.
 444  * The given band is modified to refer to the tile loops and
 445  * a child band is created to refer to the point loops.
 446  * The children of this point loop band are the children
 447  * of the original band.
 448  */
 449 int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes)
 450 {
 451         isl_ctx *ctx;
 452         isl_band *child;
 453         isl_band_list *list = NULL;
 454         isl_union_pw_multi_aff *sched;
 455
 456         if (!band || !sizes)
 457                 goto error;
 458
 459         ctx = isl_vec_get_ctx(sizes);
 460         child = isl_band_dup(band);
 461         list = isl_band_list_alloc(ctx, 1);
 462         list = isl_band_list_add(list, child);
 463         if (!list)
 464                 goto error;
 465
 466         sched = isl_union_pw_multi_aff_copy(band->pma);
 467         sched = isl_union_pw_multi_aff_tile(sched, sizes);
 468         if (!sched)
 469                 goto error;
 470
 471         child->children = band->children;
 472         band->children = list;
 473         child->parent = band;
 474         isl_union_pw_multi_aff_free(band->pma);
 475         band->pma = sched;
 476
 477         isl_vec_free(sizes);
 478         return 0;
 479 error:
 480         isl_band_list_free(list);
 481         isl_vec_free(sizes);
 482         return -1;
 483 }
 484
 485 __isl_give isl_printer *isl_printer_print_band(__isl_take isl_printer *p,
 486         __isl_keep isl_band *band)
 487 {
 488         isl_union_map *prefix, *partial, *suffix;
 489
 490         prefix = isl_band_get_prefix_schedule(band);
 491         partial = isl_band_get_partial_schedule(band);
 492         suffix = isl_band_get_suffix_schedule(band);
 493
 494         p = isl_printer_print_str(p, "(");
 495         p = isl_printer_print_union_map(p, prefix);
 496         p = isl_printer_print_str(p, ",");
 497         p = isl_printer_print_union_map(p, partial);
 498         p = isl_printer_print_str(p, ",");
 499         p = isl_printer_print_union_map(p, suffix);
 500         p = isl_printer_print_str(p, ")");
 501
 502         isl_union_map_free(prefix);
 503         isl_union_map_free(partial);
 504         isl_union_map_free(suffix);
 505
 506         return p;
 507 }