gcc/graphite-optimize-isl.c

   1 /* A scheduling optimizer for Graphite
   2    Copyright (C) 2012-2016 Free Software Foundation, Inc.
   3    Contributed by Tobias Grosser <tobias@grosser.es>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #define USES_ISL
  22
  23 #include "config.h"
  24
  25 #ifdef HAVE_isl
  26
  27 #include "system.h"
  28 #include "coretypes.h"
  29 #include "backend.h"
  30 #include "cfghooks.h"
  31 #include "tree.h"
  32 #include "gimple.h"
  33 #include "fold-const.h"
  34 #include "gimple-iterator.h"
  35 #include "tree-ssa-loop.h"
  36 #include "cfgloop.h"
  37 #include "tree-data-ref.h"
  38 #include "params.h"
  39 #include "dumpfile.h"
  40 #include "graphite.h"
  41
  42 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  43 /* isl 0.15 or later.  */
  44
  45 /* get_schedule_for_node_st - Improve schedule for the schedule node.
  46    Only Simple loop tiling is considered.  */
  47
  48 static __isl_give isl_schedule_node *
  49 get_schedule_for_node_st (__isl_take isl_schedule_node *node, void *user)
  50 {
  51   if (user)
  52     return node;
  53
  54   if (isl_schedule_node_get_type (node) != isl_schedule_node_band
  55       || isl_schedule_node_n_children (node) != 1)
  56     return node;
  57
  58   isl_space *space = isl_schedule_node_band_get_space (node);
  59   unsigned dims = isl_space_dim (space, isl_dim_set);
  60   isl_schedule_node *child = isl_schedule_node_get_child (node, 0);
  61   isl_schedule_node_type type = isl_schedule_node_get_type (child);
  62   isl_space_free (space);
  63   isl_schedule_node_free (child);
  64
  65   if (type != isl_schedule_node_leaf)
  66     return node;
  67
  68   if (dims <= 1 || !isl_schedule_node_band_get_permutable (node))
  69     {
  70       if (dump_file && dump_flags)
  71         fprintf (dump_file, "not tiled\n");
  72       return node;
  73     }
  74
  75   /* Tile loops.  */
  76   space = isl_schedule_node_band_get_space (node);
  77   isl_multi_val *sizes = isl_multi_val_zero (space);
  78   long tile_size = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
  79   isl_ctx *ctx = isl_schedule_node_get_ctx (node);
  80
  81   for (unsigned i = 0; i < dims; i++)
  82     {
  83       sizes = isl_multi_val_set_val (sizes, i,
  84                                      isl_val_int_from_si (ctx, tile_size));
  85       if (dump_file && dump_flags)
  86         fprintf (dump_file, "tiled by %ld\n", tile_size);
  87     }
  88
  89   node = isl_schedule_node_band_tile (node, sizes);
  90   node = isl_schedule_node_child (node, 0);
  91
  92   return node;
  93 }
  94
  95 /* get_schedule_map_st - Improve the schedule by performing other loop
  96    optimizations. _st ending is for schedule tree version of this
  97    function (see get_schedule_map below for the band forest version).
  98
  99    Do a depth-first post-order traversal of the nodes in a schedule
 100    tree and apply get_schedule_for_node_st on them to improve the schedule.
 101   */
 102
 103 static __isl_give isl_union_map *
 104 get_schedule_map_st (__isl_keep isl_schedule *schedule)
 105 {
 106
 107   schedule = isl_schedule_map_schedule_node_bottom_up (schedule,
 108                                                        get_schedule_for_node_st,
 109                                                        NULL);
 110   isl_union_map *schedule_map = isl_schedule_get_map (schedule);
 111   return schedule_map;
 112 }
 113 #else
 114
 115 /* get_tile_map - Create a map that describes a n-dimensonal tiling.
 116
 117    get_tile_map creates a map from a n-dimensional scattering space into an
 118    2*n-dimensional scattering space. The map describes a rectangular tiling.
 119
 120    Example:
 121      SCHEDULE_DIMENSIONS = 2, PARAMETER_DIMENSIONS = 1, TILE_SIZE = 32
 122
 123     tile_map := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
 124                          t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
 125                          t1 % 32 = 0 and t1 <= s1 < t1 + 32}
 126
 127    Before tiling:
 128
 129    for (i = 0; i < N; i++)
 130      for (j = 0; j < M; j++)
 131         S(i,j)
 132
 133    After tiling:
 134
 135    for (t_i = 0; t_i < N; i+=32)
 136      for (t_j = 0; t_j < M; j+=32)
 137         for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
 138           for (j = t_j; j < t_j + 32; j++)        |   Known that M % 32 = 0
 139             S(i,j)
 140   */
 141
 142 static isl_basic_map *
 143 get_tile_map (isl_ctx *ctx, int schedule_dimensions, int tile_size)
 144 {
 145   /* We construct
 146
 147      tile_map := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
 148                         s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
 149                         s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}
 150
 151      and project out the auxilary dimensions a0 and a1.  */
 152   isl_space *space
 153     = isl_space_alloc (ctx, 0, schedule_dimensions, schedule_dimensions * 3);
 154   isl_basic_map *tile_map = isl_basic_map_universe (isl_space_copy (space));
 155
 156   isl_local_space *local_space = isl_local_space_from_space (space);
 157
 158   for (int x = 0; x < schedule_dimensions; x++)
 159     {
 160       int sX = x;
 161       int tX = x;
 162       int pX = schedule_dimensions + x;
 163       int aX = 2 * schedule_dimensions + x;
 164
 165       isl_constraint *c;
 166
 167       /* sX = aX * tile_size; */
 168       c = isl_equality_alloc (isl_local_space_copy (local_space));
 169       isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 1);
 170       isl_constraint_set_coefficient_si (c, isl_dim_out, aX, -tile_size);
 171       tile_map = isl_basic_map_add_constraint (tile_map, c);
 172
 173       /* pX = sX; */
 174       c = isl_equality_alloc (isl_local_space_copy (local_space));
 175       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
 176       isl_constraint_set_coefficient_si (c, isl_dim_in, sX, -1);
 177       tile_map = isl_basic_map_add_constraint (tile_map, c);
 178
 179       /* tX <= pX */
 180       c = isl_inequality_alloc (isl_local_space_copy (local_space));
 181       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
 182       isl_constraint_set_coefficient_si (c, isl_dim_out, tX, -1);
 183       tile_map = isl_basic_map_add_constraint (tile_map, c);
 184
 185       /* pX <= tX + (tile_size - 1) */
 186       c = isl_inequality_alloc (isl_local_space_copy (local_space));
 187       isl_constraint_set_coefficient_si (c, isl_dim_out, tX, 1);
 188       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, -1);
 189       isl_constraint_set_constant_si (c, tile_size - 1);
 190       tile_map = isl_basic_map_add_constraint (tile_map, c);
 191     }
 192
 193   /* Project out auxiliary dimensions.
 194
 195      The auxiliary dimensions are transformed into existentially quantified
 196      ones.
 197      This reduces the number of visible scattering dimensions and allows isl
 198      to produces better code.  */
 199   tile_map =
 200       isl_basic_map_project_out (tile_map, isl_dim_out,
 201                                  2 * schedule_dimensions, schedule_dimensions);
 202   isl_local_space_free (local_space);
 203   return tile_map;
 204 }
 205
 206 /* get_schedule_for_band - Get the schedule for this BAND.
 207
 208    Polly applies transformations like tiling on top of the isl calculated
 209    value.
 210    This can influence the number of scheduling dimension. The number of
 211    schedule dimensions is returned in DIMENSIONS.  */
 212
 213 static isl_union_map *
 214 get_schedule_for_band (isl_band *band, int *dimensions)
 215 {
 216   isl_union_map *partial_schedule;
 217   isl_ctx *ctx;
 218   isl_space *space;
 219   isl_basic_map *tile_map;
 220   isl_union_map *tile_umap;
 221
 222   partial_schedule = isl_band_get_partial_schedule (band);
 223   *dimensions = isl_band_n_member (band);
 224
 225   /* It does not make any sense to tile a band with just one dimension.  */
 226   if (*dimensions == 1)
 227     {
 228       if (dump_file && dump_flags)
 229         fprintf (dump_file, "not tiled\n");
 230       return partial_schedule;
 231     }
 232
 233   if (dump_file && dump_flags)
 234     fprintf (dump_file, "tiled by %d\n",
 235              PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 236
 237   ctx = isl_union_map_get_ctx (partial_schedule);
 238   space = isl_union_map_get_space (partial_schedule);
 239
 240   tile_map = get_tile_map (ctx, *dimensions,
 241                            PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 242   tile_umap = isl_union_map_from_map (isl_map_from_basic_map (tile_map));
 243   tile_umap = isl_union_map_align_params (tile_umap, space);
 244   tile_umap = isl_union_map_coalesce (tile_umap);
 245   *dimensions = 2 * *dimensions;
 246
 247   return isl_union_map_apply_range (partial_schedule, tile_umap);
 248 }
 249
 250
 251 /* get_schedule_for_band_list - Get the scheduling map for a list of bands.
 252
 253    We walk recursively the forest of bands to combine the schedules of the
 254    individual bands to the overall schedule.  In case tiling is requested,
 255    the individual bands are tiled.  */
 256
 257 static isl_union_map *
 258 get_schedule_for_band_list (isl_band_list *band_list)
 259 {
 260   int num_bands, i;
 261   isl_union_map *schedule;
 262   isl_ctx *ctx;
 263
 264   ctx = isl_band_list_get_ctx (band_list);
 265   num_bands = isl_band_list_n_band (band_list);
 266   schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));
 267
 268   for (i = 0; i < num_bands; i++)
 269     {
 270       isl_band *band;
 271       isl_union_map *partial_schedule;
 272       int schedule_dimensions;
 273       isl_space *space;
 274
 275       band = isl_band_list_get_band (band_list, i);
 276       partial_schedule = get_schedule_for_band (band, &schedule_dimensions);
 277       space = isl_union_map_get_space (partial_schedule);
 278
 279       if (isl_band_has_children (band))
 280         {
 281           isl_band_list *children = isl_band_get_children (band);
 282           isl_union_map *suffixSchedule
 283             = get_schedule_for_band_list (children);
 284           partial_schedule
 285             = isl_union_map_flat_range_product (partial_schedule,
 286                                                 suffixSchedule);
 287           isl_band_list_free (children);
 288         }
 289
 290       schedule = isl_union_map_union (schedule, partial_schedule);
 291
 292       isl_band_free (band);
 293       isl_space_free (space);
 294     }
 295
 296   return isl_union_map_coalesce (schedule);
 297 }
 298
 299 static isl_union_map *
 300 get_schedule_map (isl_schedule *schedule)
 301 {
 302   isl_band_list *band_list = isl_schedule_get_band_forest (schedule);
 303   isl_union_map *schedule_map = get_schedule_for_band_list (band_list);
 304   isl_band_list_free (band_list);
 305   return schedule_map;
 306 }
 307 #endif
 308
 309 static isl_stat
 310 get_single_map (__isl_take isl_map *map, void *user)
 311 {
 312   isl_map **single_map = (isl_map **)user;
 313   *single_map = map;
 314   return isl_stat_ok;
 315 }
 316
 317 static void
 318 apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
 319 {
 320   int i;
 321   poly_bb_p pbb;
 322
 323   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 324     {
 325       isl_set *domain = isl_set_copy (pbb->domain);
 326       isl_map *stmt_schedule;
 327
 328       isl_union_map *stmt_band
 329         = isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
 330                                           isl_union_set_from_set (domain));
 331       stmt_band = isl_union_map_coalesce (stmt_band);
 332       isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
 333       isl_map_free (pbb->transformed);
 334       pbb->transformed = isl_map_coalesce (stmt_schedule);
 335       isl_union_map_free (stmt_band);
 336     }
 337 }
 338
 339 static isl_union_set *
 340 scop_get_domains (scop_p scop)
 341 {
 342   int i;
 343   poly_bb_p pbb;
 344   isl_space *space = isl_set_get_space (scop->param_context);
 345   isl_union_set *res = isl_union_set_empty (space);
 346
 347   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 348     res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
 349
 350   return res;
 351 }
 352
 353 static const int CONSTANT_BOUND = 20;
 354
 355 /* Compute the schedule for SCOP based on its parameters, domain and set of
 356    constraints.  Then apply the schedule to SCOP.  */
 357
 358 bool
 359 optimize_isl (scop_p scop)
 360 {
 361   int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
 362   int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
 363   if (max_operations)
 364     isl_ctx_set_max_operations (scop->isl_context, max_operations);
 365   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
 366
 367   isl_union_set *domain = scop_get_domains (scop);
 368   scop_get_dependences (scop);
 369   scop->dependence
 370     = isl_union_map_gist_domain (scop->dependence, isl_union_set_copy (domain));
 371   scop->dependence
 372     = isl_union_map_gist_range (scop->dependence, isl_union_set_copy (domain));
 373   isl_union_map *validity = isl_union_map_copy (scop->dependence);
 374   isl_union_map *proximity = isl_union_map_copy (validity);
 375
 376   isl_options_set_schedule_max_constant_term (scop->isl_context, CONSTANT_BOUND);
 377   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 378 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 379   /* isl 0.15 or later.  */
 380   isl_options_set_schedule_serialize_sccs (scop->isl_context, 0);
 381   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 382   isl_options_set_schedule_max_constant_term (scop->isl_context, 20);
 383   isl_options_set_schedule_max_coefficient (scop->isl_context, 20);
 384   isl_options_set_tile_scale_tile_loops (scop->isl_context, 0);
 385   isl_options_set_coalesce_bounded_wrapping (scop->isl_context, 1);
 386   isl_options_set_ast_build_exploit_nested_bounds (scop->isl_context, 1);
 387   isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1);
 388 #else
 389   isl_options_set_schedule_fuse (scop->isl_context, ISL_SCHEDULE_FUSE_MIN);
 390 #endif
 391
 392   isl_schedule *schedule
 393     = isl_union_set_compute_schedule (domain, validity, proximity);
 394   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);
 395
 396   isl_ctx_reset_operations (scop->isl_context);
 397   isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
 398   if (!schedule || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
 399     {
 400       if (dump_file && dump_flags)
 401         fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n",
 402                  max_operations);
 403       if (schedule)
 404         isl_schedule_free (schedule);
 405       return false;
 406     }
 407
 408   /* Attach the schedule to scop so that it can be used in code generation.
 409      schedule freeing will occur in code generation.  */
 410   scop->schedule = schedule;
 411
 412 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 413   /* isl 0.15 or later.  */
 414   isl_union_map *schedule_map = get_schedule_map_st (schedule);
 415 #else
 416   isl_union_map *schedule_map = get_schedule_map (schedule);
 417 #endif
 418   apply_schedule_map_to_scop (scop, schedule_map);
 419
 420   isl_union_map_free (schedule_map);
 421   return true;
 422 }
 423
 424 #endif /* HAVE_isl */