schedule.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  * Copyright 2021      Sven Verdoolaege
   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  */
  11
  12 #include <ctype.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15
  16 #include <isl/val.h>
  17 #include <isl/aff.h>
  18 #include <isl/set.h>
  19 #include <isl/map.h>
  20 #include <isl/constraint.h>
  21 #include <isl/union_set.h>
  22 #include <isl/union_map.h>
  23
  24 #include "grouping.h"
  25 #include "schedule.h"
  26
  27 /* Add parameters with identifiers "ids" to "set".
  28  */
  29 static __isl_give isl_set *add_params(__isl_take isl_set *set,
  30         __isl_keep isl_id_list *ids)
  31 {
  32         int i, n;
  33         unsigned nparam;
  34
  35         n = isl_id_list_n_id(ids);
  36
  37         nparam = isl_set_dim(set, isl_dim_param);
  38         set = isl_set_add_dims(set, isl_dim_param, n);
  39
  40         for (i = 0; i < n; ++i) {
  41                 isl_id *id;
  42
  43                 id = isl_id_list_get_id(ids, i);
  44                 set = isl_set_set_dim_id(set, isl_dim_param, nparam + i, id);
  45         }
  46
  47         return set;
  48 }
  49
  50 /* Equate the dimensions of "set" starting at "first" to
  51  * freshly created parameters with identifiers "ids".
  52  * The number of equated dimensions is equal to the number of elements in "ids".
  53  */
  54 static __isl_give isl_set *parametrize(__isl_take isl_set *set,
  55         int first, __isl_keep isl_id_list *ids)
  56 {
  57         int i, n;
  58         unsigned nparam;
  59
  60         nparam = isl_set_dim(set, isl_dim_param);
  61
  62         set = add_params(set, ids);
  63
  64         n = isl_id_list_n_id(ids);
  65         for (i = 0; i < n; ++i)
  66                 set = isl_set_equate(set, isl_dim_param, nparam + i,
  67                                         isl_dim_set, first + i);
  68
  69         return set;
  70 }
  71
  72 /* Given a parameter space "space", create a set of dimension "len"
  73  * of which the dimensions starting at "first" are equated to
  74  * freshly created parameters with identifiers "ids".
  75  */
  76 __isl_give isl_set *parametrization(__isl_take isl_space *space,
  77         int len, int first, __isl_keep isl_id_list *ids)
  78 {
  79         isl_set *set;
  80
  81         space = isl_space_set_from_params(space);
  82         space = isl_space_add_dims(space, isl_dim_set, len);
  83         set = isl_set_universe(space);
  84
  85         return parametrize(set, first, ids);
  86 }
  87
  88 /* Load and return a schedule from a file called "filename".
  89  */
  90 static __isl_give isl_schedule *load_schedule(isl_ctx *ctx,
  91         const char *filename)
  92 {
  93         FILE *file;
  94         isl_schedule *schedule;
  95
  96         file = fopen(filename, "r");
  97         if (!file) {
  98                 fprintf(stderr, "Unable to open '%s' for reading\n", filename);
  99                 return NULL;
 100         }
 101         schedule = isl_schedule_read_from_file(ctx, file);
 102         fclose(file);
 103
 104         return schedule;
 105 }
 106
 107 /* Save the schedule "schedule" to a file called "filename".
 108  * The schedule is printed in block style.
 109  */
 110 static void save_schedule(__isl_keep isl_schedule *schedule,
 111         const char *filename)
 112 {
 113         FILE *file;
 114         isl_ctx *ctx;
 115         isl_printer *p;
 116
 117         if (!schedule)
 118                 return;
 119
 120         file = fopen(filename, "w");
 121         if (!file) {
 122                 fprintf(stderr, "Unable to open '%s' for writing\n", filename);
 123                 return;
 124         }
 125         ctx = isl_schedule_get_ctx(schedule);
 126         p = isl_printer_to_file(ctx, file);
 127         p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_BLOCK);
 128         p = isl_printer_print_schedule(p, schedule);
 129         isl_printer_free(p);
 130         fclose(file);
 131 }
 132
 133 /* Compute a schedule on the domain of "sc" that respects the schedule
 134  * constraints in "sc", without trying to combine groups of statements.
 135  */
 136 __isl_give isl_schedule *ppcg_compute_non_grouping_schedule(
 137         __isl_take isl_schedule_constraints *sc, struct ppcg_options *options)
 138 {
 139         if (options->debug->dump_schedule_constraints)
 140                 isl_schedule_constraints_dump(sc);
 141         return isl_schedule_constraints_compute_schedule(sc);
 142 }
 143
 144 /* Compute a schedule on the domain of "sc" that respects the schedule
 145  * constraints in "sc".
 146  *
 147  * "schedule" is a known correct schedule that is used to combine
 148  * groups of statements if options->group_chains is set.
 149  */
 150 __isl_give isl_schedule *ppcg_compute_schedule(
 151         __isl_take isl_schedule_constraints *sc,
 152         __isl_keep isl_schedule *schedule, struct ppcg_options *options)
 153 {
 154         if (options->group_chains)
 155                 return ppcg_compute_grouping_schedule(sc, schedule, options);
 156         return ppcg_compute_non_grouping_schedule(sc, options);
 157 }
 158
 159 /* Obtain a schedule, either by reading it form a file
 160  * or by computing it using "compute".
 161  * Also take care of saving the computed schedule and/or
 162  * dumping the obtained schedule if requested by the user.
 163  */
 164 __isl_give isl_schedule *ppcg_get_schedule(isl_ctx *ctx,
 165         struct ppcg_options *options,
 166         __isl_give isl_schedule *(*compute)(void *user), void *user)
 167 {
 168         isl_schedule *schedule;
 169
 170         if (options->load_schedule_file) {
 171                 schedule = load_schedule(ctx, options->load_schedule_file);
 172         } else {
 173                 schedule = compute(user);
 174                 if (options->save_schedule_file)
 175                         save_schedule(schedule, options->save_schedule_file);
 176         }
 177         if (options->debug->dump_schedule)
 178                 isl_schedule_dump(schedule);
 179
 180         return schedule;
 181 }
 182
 183 /* Mark all dimensions in the band node "node" to be of "type".
 184  */
 185 __isl_give isl_schedule_node *ppcg_set_schedule_node_type(
 186         __isl_take isl_schedule_node *node, enum isl_ast_loop_type type)
 187 {
 188         int i, n;
 189
 190         n = isl_schedule_node_band_n_member(node);
 191         for (i = 0; i < n; ++i)
 192                 node = isl_schedule_node_band_member_set_ast_loop_type(node, i,
 193                                                         type);
 194
 195         return node;
 196 }
 197
 198 /* Does "tile" represent a trivial lattice tile, i.e.,
 199  * one with size 1 in all directions?
 200  */
 201 static isl_bool lattice_is_trivial(__isl_keep isl_fixed_box *tile)
 202 {
 203         isl_bool trivial;
 204         isl_val *val_one;
 205         isl_multi_val *size;
 206         isl_multi_val *zero, *one;
 207
 208         size = isl_fixed_box_get_size(tile);
 209         zero = isl_multi_val_sub(isl_multi_val_copy(size),
 210                                  isl_multi_val_copy(size));
 211         val_one = isl_val_one(isl_fixed_box_get_ctx(tile));
 212         one = isl_multi_val_add_val(zero, val_one);
 213         trivial = isl_multi_val_plain_is_equal(size, one);
 214         isl_multi_val_free(size);
 215         isl_multi_val_free(one);
 216
 217         return trivial;
 218 }
 219
 220 /* Given that the elements of "set" lie on a (rectangular) lattice
 221  * with tile "tile", scale it down such that the origin of the result
 222  * corresponds to "tile".
 223  *
 224  * The lattice is of the form
 225  *
 226  *      offset + size j
 227  *
 228  * Plug this into "set" to obtain a set in terms of "j"
 229  * with j = 0 corresponding to offset in "set".
 230  */
 231 static __isl_give isl_set *scale_down_set(__isl_keep isl_fixed_box *tile,
 232         __isl_take isl_set *set)
 233 {
 234         isl_space *space;
 235         isl_multi_val *size;
 236         isl_multi_aff *offset;
 237         isl_multi_aff *id;
 238         isl_multi_aff *to_lattice;
 239
 240         size = isl_fixed_box_get_size(tile);
 241         offset = isl_fixed_box_get_offset(tile);
 242         space = isl_multi_aff_get_space(offset);
 243         id = isl_space_identity_multi_aff_on_domain(isl_space_copy(space));
 244         offset = isl_multi_aff_insert_domain(offset, space);
 245         to_lattice = isl_multi_aff_scale_multi_val(id, size);
 246         to_lattice = isl_multi_aff_add(to_lattice, offset);
 247         set = isl_set_preimage_multi_aff(set, to_lattice);
 248
 249         return set;
 250 }
 251
 252 /* Given that the schedule values of the band node "node"
 253  * lie on a (rectangular) lattice with tile "tile",
 254  * scale it down such that the values corresponding to "tile"
 255  * are mapped to the origin.
 256  * "domain" is the (universe) domain reaching "node".
 257  *
 258  * The lattice is of the form
 259  *
 260  *      offset + size j
 261  *
 262  * Subtract offset and scale down by size.
 263  */
 264 static __isl_give isl_schedule_node *scale_down_band(
 265         __isl_keep isl_fixed_box *tile, __isl_take isl_schedule_node *node,
 266         __isl_keep isl_union_set *domain)
 267 {
 268         isl_multi_val *size;
 269         isl_multi_aff *offset;
 270         isl_multi_union_pw_aff *mupa;
 271
 272         size = isl_fixed_box_get_size(tile);
 273         offset = isl_multi_aff_neg(isl_fixed_box_get_offset(tile));
 274         domain = isl_union_set_copy(domain);
 275         mupa = isl_multi_union_pw_aff_multi_aff_on_domain(domain, offset);
 276         node = isl_schedule_node_band_shift(node, mupa);
 277         node = isl_schedule_node_band_scale_down(node, size);
 278
 279         return node;
 280 }
 281
 282 /* Try and shift the given band node to the origin after
 283  * potentially scaling it down first.
 284  *
 285  * In particular, obtain the set of schedule values and
 286  * first check if they lie on a non-trivial (rectangular) lattice.
 287  * If so, scale down both the band node and the set.  Then
 288  * compute the element-wise minimal value, which may
 289  * depend on the parameters.
 290  * If this results in any piecewise expressions,
 291  * then do not perform any shifting as that may
 292  * very well make the resulting code more complicated.
 293  * Otherwise shift the band by the opposite of this minimal value.
 294  */
 295 static __isl_give isl_schedule_node *scale_down_and_shift_to_origin(
 296         __isl_take isl_schedule_node *node)
 297 {
 298         isl_bool is_multi_aff, trivial;
 299         isl_space *space;
 300         isl_union_set *domain, *range;
 301         isl_union_map *partial;
 302         isl_set *min_domain;
 303         isl_set *set;
 304         isl_multi_pw_aff *min;
 305         isl_multi_aff *min_ma, *shift;
 306         isl_multi_union_pw_aff *mupa;
 307         isl_fixed_box *tile;
 308
 309         partial = isl_schedule_node_band_get_partial_schedule_union_map(node);
 310         domain = isl_schedule_node_get_domain(node);
 311         range = isl_union_set_apply(isl_union_set_copy(domain), partial);
 312         space = isl_schedule_node_band_get_space(node);
 313         set = isl_union_set_extract_set(range, space);
 314         isl_union_set_free(range);
 315         domain = isl_union_set_universe(domain);
 316
 317         tile = isl_set_get_lattice_tile(set);
 318         trivial = lattice_is_trivial(tile);
 319         if (trivial < 0) {
 320                 node = isl_schedule_node_free(node);
 321         } else if (!trivial) {
 322                 set = scale_down_set(tile, set);
 323                 node = scale_down_band(tile, node, domain);
 324         }
 325         isl_fixed_box_free(tile);
 326
 327         min = isl_set_min_multi_pw_aff(set);
 328         min_domain = isl_multi_pw_aff_domain(isl_multi_pw_aff_copy(min));
 329         min = isl_multi_pw_aff_gist(min, min_domain);
 330         is_multi_aff = isl_multi_pw_aff_isa_multi_aff(min);
 331         if (is_multi_aff < 0 || !is_multi_aff) {
 332                 isl_union_set_free(domain);
 333                 isl_multi_pw_aff_free(min);
 334                 if (is_multi_aff < 0)
 335                         return isl_schedule_node_free(node);
 336                 return node;
 337         }
 338
 339         min_ma = isl_multi_pw_aff_as_multi_aff(min);
 340         shift = isl_multi_aff_neg(min_ma);
 341         mupa = isl_multi_union_pw_aff_multi_aff_on_domain(domain, shift);
 342         node = isl_schedule_node_band_shift(node, mupa);
 343
 344         return node;
 345 }
 346
 347 /* Tile "node" with tile sizes "sizes", but first try and shift the band
 348  * to the origin.
 349  * Tiling a band that does not start at the origin is likely
 350  * to result in initial partial tiles.
 351  */
 352 __isl_give isl_schedule_node *ppcg_tile(__isl_take isl_schedule_node *node,
 353         __isl_take isl_multi_val *sizes)
 354 {
 355         node = scale_down_and_shift_to_origin(node);
 356         return isl_schedule_node_band_tile(node, sizes);
 357 }