gcc/graphite-optimize-isl.c

   1 /* A scheduling optimizer for Graphite
   2    Copyright (C) 2012-2015 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 #include "config.h"
  22
  23 #ifdef HAVE_isl
  24 /* Workaround for GMP 5.1.3 bug, see PR56019.  */
  25 #include <stddef.h>
  26
  27 #include <isl/constraint.h>
  28 #include <isl/set.h>
  29 #include <isl/union_set.h>
  30 #include <isl/map.h>
  31 #include <isl/union_map.h>
  32 #include <isl/schedule.h>
  33 #include <isl/band.h>
  34 #include <isl/aff.h>
  35 #include <isl/options.h>
  36 #include <isl/ctx.h>
  37
  38 #include "system.h"
  39 #include "coretypes.h"
  40 #include "backend.h"
  41 #include "cfghooks.h"
  42 #include "tree.h"
  43 #include "gimple.h"
  44 #include "fold-const.h"
  45 #include "gimple-iterator.h"
  46 #include "tree-ssa-loop.h"
  47 #include "cfgloop.h"
  48 #include "tree-data-ref.h"
  49 #include "graphite-poly.h"
  50 #include "params.h"
  51 #include "dumpfile.h"
  52
  53 static isl_union_set *
  54 scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
  55 {
  56   int i;
  57   poly_bb_p pbb;
  58   isl_space *space = isl_set_get_space (scop->context);
  59   isl_union_set *res = isl_union_set_empty (space);
  60
  61   FOR_EACH_VEC_ELT (scop->bbs, i, pbb)
  62     res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
  63
  64   return res;
  65 }
  66
  67 /* get_tile_map - Create a map that describes a n-dimensonal tiling.
  68
  69    get_tile_map creates a map from a n-dimensional scattering space into an
  70    2*n-dimensional scattering space. The map describes a rectangular tiling.
  71
  72    Example:
  73      SCHEDULE_DIMENSIONS = 2, PARAMETER_DIMENSIONS = 1, TILE_SIZE = 32
  74
  75     tile_map := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
  76                          t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
  77                          t1 % 32 = 0 and t1 <= s1 < t1 + 32}
  78
  79    Before tiling:
  80
  81    for (i = 0; i < N; i++)
  82      for (j = 0; j < M; j++)
  83         S(i,j)
  84
  85    After tiling:
  86
  87    for (t_i = 0; t_i < N; i+=32)
  88      for (t_j = 0; t_j < M; j+=32)
  89         for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
  90           for (j = t_j; j < t_j + 32; j++)        |   Known that M % 32 = 0
  91             S(i,j)
  92   */
  93
  94 static isl_basic_map *
  95 get_tile_map (isl_ctx *ctx, int schedule_dimensions, int tile_size)
  96 {
  97   /* We construct
  98
  99      tile_map := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
 100                         s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
 101                         s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}
 102
 103      and project out the auxilary dimensions a0 and a1.  */
 104   isl_space *space
 105     = isl_space_alloc (ctx, 0, schedule_dimensions, schedule_dimensions * 3);
 106   isl_basic_map *tile_map = isl_basic_map_universe (isl_space_copy (space));
 107
 108   isl_local_space *local_space = isl_local_space_from_space (space);
 109
 110   for (int x = 0; x < schedule_dimensions; x++)
 111     {
 112       int sX = x;
 113       int tX = x;
 114       int pX = schedule_dimensions + x;
 115       int aX = 2 * schedule_dimensions + x;
 116
 117       isl_constraint *c;
 118
 119       /* sX = aX * tile_size; */
 120       c = isl_equality_alloc (isl_local_space_copy (local_space));
 121       isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 1);
 122       isl_constraint_set_coefficient_si (c, isl_dim_out, aX, -tile_size);
 123       tile_map = isl_basic_map_add_constraint (tile_map, c);
 124
 125       /* pX = sX; */
 126       c = isl_equality_alloc (isl_local_space_copy (local_space));
 127       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
 128       isl_constraint_set_coefficient_si (c, isl_dim_in, sX, -1);
 129       tile_map = isl_basic_map_add_constraint (tile_map, c);
 130
 131       /* tX <= pX */
 132       c = isl_inequality_alloc (isl_local_space_copy (local_space));
 133       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
 134       isl_constraint_set_coefficient_si (c, isl_dim_out, tX, -1);
 135       tile_map = isl_basic_map_add_constraint (tile_map, c);
 136
 137       /* pX <= tX + (tile_size - 1) */
 138       c = isl_inequality_alloc (isl_local_space_copy (local_space));
 139       isl_constraint_set_coefficient_si (c, isl_dim_out, tX, 1);
 140       isl_constraint_set_coefficient_si (c, isl_dim_out, pX, -1);
 141       isl_constraint_set_constant_si (c, tile_size - 1);
 142       tile_map = isl_basic_map_add_constraint (tile_map, c);
 143     }
 144
 145   /* Project out auxiliary dimensions.
 146
 147      The auxiliary dimensions are transformed into existentially quantified
 148      ones.
 149      This reduces the number of visible scattering dimensions and allows isl
 150      to produces better code.  */
 151   tile_map =
 152       isl_basic_map_project_out (tile_map, isl_dim_out,
 153                                  2 * schedule_dimensions, schedule_dimensions);
 154   isl_local_space_free (local_space);
 155   return tile_map;
 156 }
 157
 158 /* get_schedule_for_band - Get the schedule for this BAND.
 159
 160    Polly applies transformations like tiling on top of the isl calculated
 161    value.
 162    This can influence the number of scheduling dimension. The number of
 163    schedule dimensions is returned in DIMENSIONS.  */
 164
 165 static isl_union_map *
 166 get_schedule_for_band (isl_band *band, int *dimensions)
 167 {
 168   isl_union_map *partial_schedule;
 169   isl_ctx *ctx;
 170   isl_space *space;
 171   isl_basic_map *tile_map;
 172   isl_union_map *tile_umap;
 173
 174   partial_schedule = isl_band_get_partial_schedule (band);
 175   *dimensions = isl_band_n_member (band);
 176
 177   /* It does not make any sense to tile a band with just one dimension.  */
 178   if (*dimensions == 1)
 179     {
 180       if (dump_file && dump_flags)
 181         fprintf (dump_file, "not tiled\n");
 182       return partial_schedule;
 183     }
 184
 185   if (dump_file && dump_flags)
 186     fprintf (dump_file, "tiled by %d\n",
 187              PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 188
 189   ctx = isl_union_map_get_ctx (partial_schedule);
 190   space = isl_union_map_get_space (partial_schedule);
 191
 192   tile_map = get_tile_map (ctx, *dimensions,
 193                            PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 194   tile_umap = isl_union_map_from_map (isl_map_from_basic_map (tile_map));
 195   tile_umap = isl_union_map_align_params (tile_umap, space);
 196   *dimensions = 2 * *dimensions;
 197
 198   return isl_union_map_apply_range (partial_schedule, tile_umap);
 199 }
 200
 201
 202 /* get_schedule_for_band_list - Get the scheduling map for a list of bands.
 203
 204    We walk recursively the forest of bands to combine the schedules of the
 205    individual bands to the overall schedule.  In case tiling is requested,
 206    the individual bands are tiled.  */
 207
 208 static isl_union_map *
 209 get_schedule_for_band_list (isl_band_list *band_list)
 210 {
 211   int num_bands, i;
 212   isl_union_map *schedule;
 213   isl_ctx *ctx;
 214
 215   ctx = isl_band_list_get_ctx (band_list);
 216   num_bands = isl_band_list_n_band (band_list);
 217   schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));
 218
 219   for (i = 0; i < num_bands; i++)
 220     {
 221       isl_band *band;
 222       isl_union_map *partial_schedule;
 223       int schedule_dimensions;
 224       isl_space *space;
 225
 226       band = isl_band_list_get_band (band_list, i);
 227       partial_schedule = get_schedule_for_band (band, &schedule_dimensions);
 228       space = isl_union_map_get_space (partial_schedule);
 229
 230       if (isl_band_has_children (band))
 231         {
 232           isl_band_list *children = isl_band_get_children (band);
 233           isl_union_map *suffixSchedule
 234             = get_schedule_for_band_list (children);
 235           partial_schedule
 236             = isl_union_map_flat_range_product (partial_schedule,
 237                                                 suffixSchedule);
 238           isl_band_list_free (children);
 239         }
 240
 241       schedule = isl_union_map_union (schedule, partial_schedule);
 242
 243       isl_band_free (band);
 244       isl_space_free (space);
 245     }
 246
 247   return schedule;
 248 }
 249
 250 static isl_union_map *
 251 get_schedule_map (isl_schedule *schedule)
 252 {
 253   isl_band_list *bandList = isl_schedule_get_band_forest (schedule);
 254   isl_union_map *schedule_map = get_schedule_for_band_list (bandList);
 255   isl_band_list_free (bandList);
 256   return schedule_map;
 257 }
 258
 259 static isl_stat
 260 get_single_map (__isl_take isl_map *map, void *user)
 261 {
 262   isl_map **single_map = (isl_map **)user;
 263   *single_map = map;
 264   return isl_stat_ok;
 265 }
 266
 267 static void
 268 apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
 269 {
 270   int i;
 271   poly_bb_p pbb;
 272
 273   FOR_EACH_VEC_ELT (scop->bbs, i, pbb)
 274     {
 275       isl_set *domain = isl_set_copy (pbb->domain);
 276       isl_map *stmt_schedule;
 277
 278       isl_union_map *stmt_band
 279         = isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
 280                                           isl_union_set_from_set (domain));
 281       isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
 282       isl_map_free (pbb->transformed);
 283       pbb->transformed = stmt_schedule;
 284       isl_union_map_free (stmt_band);
 285     }
 286 }
 287
 288 static const int CONSTANT_BOUND = 20;
 289
 290 /* Compute the schedule for SCOP based on its parameters, domain and set of
 291    constraints.  Then apply the schedule to SCOP.  */
 292
 293 bool
 294 optimize_isl (scop_p scop)
 295 {
 296 #ifdef HAVE_ISL_CTX_MAX_OPERATIONS
 297   int old_max_operations = isl_ctx_get_max_operations (scop->ctx);
 298   int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
 299   if (max_operations)
 300     isl_ctx_set_max_operations (scop->ctx, max_operations);
 301 #endif
 302   isl_options_set_on_error (scop->ctx, ISL_ON_ERROR_CONTINUE);
 303
 304   isl_union_set *domain = scop_get_domains (scop);
 305   isl_union_map *dependences = scop_get_dependences (scop);
 306   dependences
 307     = isl_union_map_gist_domain (dependences, isl_union_set_copy (domain));
 308   dependences
 309     = isl_union_map_gist_range (dependences, isl_union_set_copy (domain));
 310   isl_union_map *validity = dependences;
 311   isl_union_map *proximity = isl_union_map_copy (validity);
 312
 313 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 314   isl_schedule_constraints *schedule_constraints;
 315   schedule_constraints = isl_schedule_constraints_on_domain (domain);
 316   schedule_constraints
 317     = isl_schedule_constraints_set_proximity (schedule_constraints,
 318                                               proximity);
 319   schedule_constraints
 320     = isl_schedule_constraints_set_validity (schedule_constraints,
 321                                              isl_union_map_copy (validity));
 322   schedule_constraints
 323     = isl_schedule_constraints_set_coincidence (schedule_constraints,
 324                                                 validity);
 325 #endif
 326
 327   isl_options_set_schedule_max_constant_term (scop->ctx, CONSTANT_BOUND);
 328   isl_options_set_schedule_maximize_band_depth (scop->ctx, 1);
 329 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 330   isl_options_set_schedule_serialize_sccs (scop->ctx, 1);
 331 #else
 332   isl_options_set_schedule_fuse (scop->ctx, ISL_SCHEDULE_FUSE_MAX);
 333 #endif
 334
 335 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 336   isl_schedule *schedule
 337     = isl_schedule_constraints_compute_schedule (schedule_constraints);
 338 #else
 339   isl_schedule *schedule
 340     = isl_union_set_compute_schedule (domain, validity, proximity);
 341 #endif
 342
 343   isl_options_set_on_error (scop->ctx, ISL_ON_ERROR_ABORT);
 344
 345 #ifdef HAVE_ISL_CTX_MAX_OPERATIONS
 346   isl_ctx_reset_operations (scop->ctx);
 347   isl_ctx_set_max_operations (scop->ctx, old_max_operations);
 348   if (!schedule || isl_ctx_last_error (scop->ctx) == isl_error_quota)
 349     {
 350       if (dump_file && dump_flags)
 351         fprintf (dump_file, "ISL timed out at %d operations\n",
 352                  max_operations);
 353       if (schedule)
 354         isl_schedule_free (schedule);
 355       return false;
 356     }
 357 #else
 358   if (!schedule)
 359     return false;
 360 #endif
 361
 362   isl_union_map *schedule_map = get_schedule_map (schedule);
 363   apply_schedule_map_to_scop (scop, schedule_map);
 364
 365   isl_schedule_free (schedule);
 366   isl_union_map_free (schedule_map);
 367   return true;
 368 }
 369
 370 #endif /* HAVE_isl */