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   *dimensions = 2 * *dimensions;
 245
 246   return isl_union_map_apply_range (partial_schedule, tile_umap);
 247 }
 248
 249
 250 /* get_schedule_for_band_list - Get the scheduling map for a list of bands.
 251
 252    We walk recursively the forest of bands to combine the schedules of the
 253    individual bands to the overall schedule.  In case tiling is requested,
 254    the individual bands are tiled.  */
 255
 256 static isl_union_map *
 257 get_schedule_for_band_list (isl_band_list *band_list)
 258 {
 259   int num_bands, i;
 260   isl_union_map *schedule;
 261   isl_ctx *ctx;
 262
 263   ctx = isl_band_list_get_ctx (band_list);
 264   num_bands = isl_band_list_n_band (band_list);
 265   schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));
 266
 267   for (i = 0; i < num_bands; i++)
 268     {
 269       isl_band *band;
 270       isl_union_map *partial_schedule;
 271       int schedule_dimensions;
 272       isl_space *space;
 273
 274       band = isl_band_list_get_band (band_list, i);
 275       partial_schedule = get_schedule_for_band (band, &schedule_dimensions);
 276       space = isl_union_map_get_space (partial_schedule);
 277
 278       if (isl_band_has_children (band))
 279         {
 280           isl_band_list *children = isl_band_get_children (band);
 281           isl_union_map *suffixSchedule
 282             = get_schedule_for_band_list (children);
 283           partial_schedule
 284             = isl_union_map_flat_range_product (partial_schedule,
 285                                                 suffixSchedule);
 286           isl_band_list_free (children);
 287         }
 288
 289       schedule = isl_union_map_union (schedule, partial_schedule);
 290
 291       isl_band_free (band);
 292       isl_space_free (space);
 293     }
 294
 295   return schedule;
 296 }
 297
 298 static isl_union_map *
 299 get_schedule_map (isl_schedule *schedule)
 300 {
 301   isl_band_list *bandList = isl_schedule_get_band_forest (schedule);
 302   isl_union_map *schedule_map = get_schedule_for_band_list (bandList);
 303   isl_band_list_free (bandList);
 304   return schedule_map;
 305 }
 306 #endif
 307
 308 static isl_stat
 309 get_single_map (__isl_take isl_map *map, void *user)
 310 {
 311   isl_map **single_map = (isl_map **)user;
 312   *single_map = map;
 313   return isl_stat_ok;
 314 }
 315
 316 static void
 317 apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
 318 {
 319   int i;
 320   poly_bb_p pbb;
 321
 322   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 323     {
 324       isl_set *domain = isl_set_copy (pbb->domain);
 325       isl_map *stmt_schedule;
 326
 327       isl_union_map *stmt_band
 328         = isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
 329                                           isl_union_set_from_set (domain));
 330       isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
 331       isl_map_free (pbb->transformed);
 332       pbb->transformed = stmt_schedule;
 333       isl_union_map_free (stmt_band);
 334     }
 335 }
 336
 337 static isl_union_set *
 338 scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
 339 {
 340   int i;
 341   poly_bb_p pbb;
 342   isl_space *space = isl_set_get_space (scop->param_context);
 343   isl_union_set *res = isl_union_set_empty (space);
 344
 345   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 346     res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
 347
 348   return res;
 349 }
 350
 351 static const int CONSTANT_BOUND = 20;
 352
 353 /* Compute the schedule for SCOP based on its parameters, domain and set of
 354    constraints.  Then apply the schedule to SCOP.  */
 355
 356 bool
 357 optimize_isl (scop_p scop)
 358 {
 359   int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
 360   int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
 361   if (max_operations)
 362     isl_ctx_set_max_operations (scop->isl_context, max_operations);
 363   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
 364
 365   isl_union_set *domain = scop_get_domains (scop);
 366   scop_get_dependences (scop);
 367   scop->dependence
 368     = isl_union_map_gist_domain (scop->dependence, isl_union_set_copy (domain));
 369   scop->dependence
 370     = isl_union_map_gist_range (scop->dependence, isl_union_set_copy (domain));
 371   isl_union_map *validity = isl_union_map_copy (scop->dependence);
 372   isl_union_map *proximity = isl_union_map_copy (validity);
 373
 374   isl_options_set_schedule_max_constant_term (scop->isl_context, CONSTANT_BOUND);
 375   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 376 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 377   /* isl 0.15 or later.  */
 378   isl_options_set_schedule_serialize_sccs (scop->isl_context, 0);
 379   isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
 380   isl_options_set_schedule_max_constant_term (scop->isl_context, 20);
 381   isl_options_set_schedule_max_coefficient (scop->isl_context, 20);
 382   isl_options_set_tile_scale_tile_loops (scop->isl_context, 0);
 383   isl_options_set_coalesce_bounded_wrapping (scop->isl_context, 1);
 384   isl_options_set_ast_build_exploit_nested_bounds (scop->isl_context, 1);
 385   isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1);
 386 #else
 387   isl_options_set_schedule_fuse (scop->isl_context, ISL_SCHEDULE_FUSE_MIN);
 388 #endif
 389
 390   isl_schedule *schedule
 391     = isl_union_set_compute_schedule (domain, validity, proximity);
 392   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);
 393
 394   isl_ctx_reset_operations (scop->isl_context);
 395   isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
 396   if (!schedule || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
 397     {
 398       if (dump_file && dump_flags)
 399         fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n",
 400                  max_operations);
 401       if (schedule)
 402         isl_schedule_free (schedule);
 403       return false;
 404     }
 405
 406   /* Attach the schedule to scop so that it can be used in code generation.
 407      schedule freeing will occur in code generation.  */
 408   scop->schedule = schedule;
 409
 410 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 411   /* isl 0.15 or later.  */
 412   isl_union_map *schedule_map = get_schedule_map_st (schedule);
 413 #else
 414   isl_union_map *schedule_map = get_schedule_map (schedule);
 415 #endif
 416   apply_schedule_map_to_scop (scop, schedule_map);
 417
 418   isl_union_map_free (schedule_map);
 419   return true;
 420 }
 421
 422 #endif /* HAVE_isl */