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
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "backend.h"
  40 #include "cfghooks.h"
  41 #include "tree.h"
  42 #include "gimple.h"
  43 #include "fold-const.h"
  44 #include "gimple-iterator.h"
  45 #include "tree-ssa-loop.h"
  46 #include "cfgloop.h"
  47 #include "tree-data-ref.h"
  48 #include "graphite-poly.h"
  49 #include "params.h"
  50 #include "dumpfile.h"
  51
  52 static isl_union_set *
  53 scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
  54 {
  55   int i;
  56   poly_bb_p pbb;
  57   isl_space *space = isl_set_get_space (scop->context);
  58   isl_union_set *res = isl_union_set_empty (space);
  59
  60   FOR_EACH_VEC_ELT (scop->bbs, i, pbb)
  61     res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
  62
  63   return res;
  64 }
  65
  66 /* getTileMap - Create a map that describes a n-dimensonal tiling.
  67
  68    getTileMap creates a map from a n-dimensional scattering space into an
  69    2*n-dimensional scattering space. The map describes a rectangular tiling.
  70
  71    Example:
  72      scheduleDimensions = 2, parameterDimensions = 1, tileSize = 32
  73
  74     tileMap := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
  75                          t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
  76                          t1 % 32 = 0 and t1 <= s1 < t1 + 32}
  77
  78    Before tiling:
  79
  80    for (i = 0; i < N; i++)
  81      for (j = 0; j < M; j++)
  82         S(i,j)
  83
  84    After tiling:
  85
  86    for (t_i = 0; t_i < N; i+=32)
  87      for (t_j = 0; t_j < M; j+=32)
  88         for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
  89           for (j = t_j; j < t_j + 32; j++)        |   Known that M % 32 = 0
  90             S(i,j)
  91    */
  92
  93 static isl_basic_map *
  94 getTileMap (isl_ctx *ctx, int scheduleDimensions, int tileSize)
  95 {
  96   int x;
  97   /* We construct
  98
  99      tileMap := [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 = isl_space_alloc (ctx, 0, scheduleDimensions,
 105                                       scheduleDimensions * 3);
 106   isl_basic_map *tileMap = isl_basic_map_universe (isl_space_copy (Space));
 107
 108   isl_local_space *LocalSpace = isl_local_space_from_space (Space);
 109
 110   for (x = 0; x < scheduleDimensions; x++)
 111     {
 112       int sX = x;
 113       int tX = x;
 114       int pX = scheduleDimensions + x;
 115       int aX = 2 * scheduleDimensions + x;
 116
 117       isl_constraint *c;
 118
 119       /* sX = aX * tileSize; */
 120       c = isl_equality_alloc (isl_local_space_copy (LocalSpace));
 121       isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 1);
 122       isl_constraint_set_coefficient_si (c, isl_dim_out, aX, -tileSize);
 123       tileMap = isl_basic_map_add_constraint (tileMap, c);
 124
 125       /* pX = sX; */
 126       c = isl_equality_alloc (isl_local_space_copy (LocalSpace));
 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       tileMap = isl_basic_map_add_constraint (tileMap, c);
 130
 131       /* tX <= pX */
 132       c = isl_inequality_alloc (isl_local_space_copy (LocalSpace));
 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       tileMap = isl_basic_map_add_constraint (tileMap, c);
 136
 137       /* pX <= tX + (tileSize - 1) */
 138       c = isl_inequality_alloc (isl_local_space_copy (LocalSpace));
 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, tileSize - 1);
 142       tileMap = isl_basic_map_add_constraint (tileMap, c);
 143     }
 144
 145   /* Project out auxiliary dimensions.
 146
 147      The auxiliary dimensions are transformed into existentially quantified ones.
 148      This reduces the number of visible scattering dimensions and allows Cloog
 149      to produces better code.  */
 150   tileMap = isl_basic_map_project_out (tileMap, isl_dim_out,
 151                                        2 * scheduleDimensions,
 152                                        scheduleDimensions);
 153   isl_local_space_free (LocalSpace);
 154   return tileMap;
 155 }
 156
 157 /* getScheduleForBand - Get the schedule for this band.
 158
 159    Polly applies transformations like tiling on top of the isl calculated value.
 160    This can influence the number of scheduling dimension. The number of
 161    schedule dimensions is returned in the parameter 'Dimension'.  */
 162 static bool DisableTiling = false;
 163
 164 static isl_union_map *
 165 getScheduleForBand (isl_band *Band, int *Dimensions)
 166 {
 167   isl_union_map *PartialSchedule;
 168   isl_ctx *ctx;
 169   isl_space *Space;
 170   isl_basic_map *TileMap;
 171   isl_union_map *TileUMap;
 172
 173   PartialSchedule = isl_band_get_partial_schedule (Band);
 174   *Dimensions = isl_band_n_member (Band);
 175
 176   if (DisableTiling)
 177     return PartialSchedule;
 178
 179   /* It does not make any sense to tile a band with just one dimension.  */
 180   if (*Dimensions == 1)
 181     {
 182       if (dump_file && dump_flags)
 183         fprintf (dump_file, "not tiled\n");
 184       return PartialSchedule;
 185     }
 186
 187   if (dump_file && dump_flags)
 188     fprintf (dump_file, "tiled by %d\n",
 189              PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 190
 191   ctx = isl_union_map_get_ctx (PartialSchedule);
 192   Space = isl_union_map_get_space (PartialSchedule);
 193
 194   TileMap = getTileMap (ctx, *Dimensions,
 195                         PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
 196   TileUMap = isl_union_map_from_map (isl_map_from_basic_map (TileMap));
 197   TileUMap = isl_union_map_align_params (TileUMap, Space);
 198   *Dimensions = 2 * *Dimensions;
 199
 200   return isl_union_map_apply_range (PartialSchedule, TileUMap);
 201 }
 202
 203 /* Create a map that pre-vectorizes one scheduling dimension.
 204
 205    getPrevectorMap creates a map that maps each input dimension to the same
 206    output dimension, except for the dimension DimToVectorize. DimToVectorize is
 207    strip mined by 'VectorWidth' and the newly created point loop of
 208    DimToVectorize is moved to the innermost level.
 209
 210    Example (DimToVectorize=0, ScheduleDimensions=2, VectorWidth=4):
 211
 212    | Before transformation
 213    |
 214    | A[i,j] -> [i,j]
 215    |
 216    | for (i = 0; i < 128; i++)
 217    |    for (j = 0; j < 128; j++)
 218    |      A(i,j);
 219
 220      Prevector map:
 221      [i,j] -> [it,j,ip] : it % 4 = 0 and it <= ip <= it + 3 and i = ip
 222
 223    | After transformation:
 224    |
 225    | A[i,j] -> [it,j,ip] : it % 4 = 0 and it <= ip <= it + 3 and i = ip
 226    |
 227    | for (it = 0; it < 128; it+=4)
 228    |    for (j = 0; j < 128; j++)
 229    |      for (ip = max(0,it); ip < min(128, it + 3); ip++)
 230    |        A(ip,j);
 231
 232    The goal of this transformation is to create a trivially vectorizable loop.
 233    This means a parallel loop at the innermost level that has a constant number
 234    of iterations corresponding to the target vector width.
 235
 236    This transformation creates a loop at the innermost level. The loop has a
 237    constant number of iterations, if the number of loop iterations at
 238    DimToVectorize can be devided by VectorWidth. The default VectorWidth is
 239    currently constant and not yet target specific. This function does not reason
 240    about parallelism.  */
 241 static isl_map *
 242 getPrevectorMap (isl_ctx *ctx, int DimToVectorize,
 243                  int ScheduleDimensions,
 244                  int VectorWidth)
 245 {
 246   isl_space *Space;
 247   isl_local_space *LocalSpace, *LocalSpaceRange;
 248   isl_set *Modulo;
 249   isl_map *TilingMap;
 250   isl_constraint *c;
 251   isl_aff *Aff;
 252   int PointDimension; /* ip */
 253   int TileDimension;  /* it */
 254   isl_val *VectorWidthMP;
 255   int i;
 256
 257   /* assert (0 <= DimToVectorize && DimToVectorize < ScheduleDimensions);*/
 258
 259   Space = isl_space_alloc (ctx, 0, ScheduleDimensions, ScheduleDimensions + 1);
 260   TilingMap = isl_map_universe (isl_space_copy (Space));
 261   LocalSpace = isl_local_space_from_space (Space);
 262   PointDimension = ScheduleDimensions;
 263   TileDimension = DimToVectorize;
 264
 265   /* Create an identity map for everything except DimToVectorize and map
 266      DimToVectorize to the point loop at the innermost dimension.  */
 267   for (i = 0; i < ScheduleDimensions; i++)
 268     {
 269       c = isl_equality_alloc (isl_local_space_copy (LocalSpace));
 270       isl_constraint_set_coefficient_si (c, isl_dim_in, i, -1);
 271
 272       if (i == DimToVectorize)
 273         isl_constraint_set_coefficient_si (c, isl_dim_out, PointDimension, 1);
 274       else
 275         isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
 276
 277       TilingMap = isl_map_add_constraint (TilingMap, c);
 278     }
 279
 280   /* it % 'VectorWidth' = 0  */
 281   LocalSpaceRange = isl_local_space_range (isl_local_space_copy (LocalSpace));
 282   Aff = isl_aff_zero_on_domain (LocalSpaceRange);
 283   Aff = isl_aff_set_constant_si (Aff, VectorWidth);
 284   Aff = isl_aff_set_coefficient_si (Aff, isl_dim_in, TileDimension, 1);
 285
 286   VectorWidthMP = isl_val_int_from_si (ctx, VectorWidth);
 287   Aff = isl_aff_mod_val (Aff, VectorWidthMP);
 288   Modulo = isl_pw_aff_zero_set (isl_pw_aff_from_aff (Aff));
 289   TilingMap = isl_map_intersect_range (TilingMap, Modulo);
 290
 291   /* it <= ip */
 292   c = isl_inequality_alloc (isl_local_space_copy (LocalSpace));
 293   isl_constraint_set_coefficient_si (c, isl_dim_out, TileDimension, -1);
 294   isl_constraint_set_coefficient_si (c, isl_dim_out, PointDimension, 1);
 295   TilingMap = isl_map_add_constraint (TilingMap, c);
 296
 297   /* ip <= it + ('VectorWidth' - 1) */
 298   c = isl_inequality_alloc (LocalSpace);
 299   isl_constraint_set_coefficient_si (c, isl_dim_out, TileDimension, 1);
 300   isl_constraint_set_coefficient_si (c, isl_dim_out, PointDimension, -1);
 301   isl_constraint_set_constant_si (c, VectorWidth - 1);
 302   TilingMap = isl_map_add_constraint (TilingMap, c);
 303
 304   return TilingMap;
 305 }
 306
 307 static bool EnablePollyVector = false;
 308
 309 /* getScheduleForBandList - Get the scheduling map for a list of bands.
 310
 311    We walk recursively the forest of bands to combine the schedules of the
 312    individual bands to the overall schedule. In case tiling is requested,
 313    the individual bands are tiled.  */
 314 static isl_union_map *
 315 getScheduleForBandList (isl_band_list *BandList)
 316 {
 317   int NumBands, i;
 318   isl_union_map *Schedule;
 319   isl_ctx *ctx;
 320
 321   ctx = isl_band_list_get_ctx (BandList);
 322   NumBands = isl_band_list_n_band (BandList);
 323   Schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));
 324
 325   for (i = 0; i < NumBands; i++)
 326     {
 327       isl_band *Band;
 328       isl_union_map *PartialSchedule;
 329       int ScheduleDimensions;
 330       isl_space *Space;
 331
 332       Band = isl_band_list_get_band (BandList, i);
 333       PartialSchedule = getScheduleForBand (Band, &ScheduleDimensions);
 334       Space = isl_union_map_get_space (PartialSchedule);
 335
 336       if (isl_band_has_children (Band))
 337         {
 338           isl_band_list *Children;
 339           isl_union_map *SuffixSchedule;
 340
 341           Children = isl_band_get_children (Band);
 342           SuffixSchedule = getScheduleForBandList (Children);
 343           PartialSchedule = isl_union_map_flat_range_product (PartialSchedule,
 344                                                               SuffixSchedule);
 345           isl_band_list_free (Children);
 346         }
 347       else if (EnablePollyVector)
 348         {
 349           for (i = ScheduleDimensions - 1 ;  i >= 0 ; i--)
 350             {
 351 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 352               if (isl_band_member_is_coincident (Band, i))
 353 #else
 354               if (isl_band_member_is_zero_distance (Band, i))
 355 #endif
 356                 {
 357                   isl_map *TileMap;
 358                   isl_union_map *TileUMap;
 359
 360                   TileMap = getPrevectorMap (ctx, i, ScheduleDimensions, 4);
 361                   TileUMap = isl_union_map_from_map (TileMap);
 362                   TileUMap = isl_union_map_align_params
 363                     (TileUMap, isl_space_copy (Space));
 364                   PartialSchedule = isl_union_map_apply_range
 365                     (PartialSchedule, TileUMap);
 366                   break;
 367                 }
 368             }
 369         }
 370
 371       Schedule = isl_union_map_union (Schedule, PartialSchedule);
 372
 373       isl_band_free (Band);
 374       isl_space_free (Space);
 375     }
 376
 377   return Schedule;
 378 }
 379
 380 static isl_union_map *
 381 getScheduleMap (isl_schedule *Schedule)
 382 {
 383   isl_band_list *BandList = isl_schedule_get_band_forest (Schedule);
 384   isl_union_map *ScheduleMap = getScheduleForBandList (BandList);
 385   isl_band_list_free (BandList);
 386   return ScheduleMap;
 387 }
 388
 389 static isl_stat
 390 getSingleMap (__isl_take isl_map *map, void *user)
 391 {
 392   isl_map **singleMap = (isl_map **) user;
 393   *singleMap = map;
 394
 395   return isl_stat_ok;
 396 }
 397
 398 static void
 399 apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
 400 {
 401   int i;
 402   poly_bb_p pbb;
 403
 404   FOR_EACH_VEC_ELT (scop->bbs, i, pbb)
 405     {
 406       isl_set *domain = isl_set_copy (pbb->domain);
 407       isl_union_map *stmtBand;
 408       isl_map *stmtSchedule;
 409
 410       stmtBand = isl_union_map_intersect_domain
 411         (isl_union_map_copy (schedule_map),
 412          isl_union_set_from_set (domain));
 413       isl_union_map_foreach_map (stmtBand, getSingleMap, &stmtSchedule);
 414       isl_map_free (pbb->transformed);
 415       pbb->transformed = stmtSchedule;
 416       isl_union_map_free (stmtBand);
 417     }
 418 }
 419
 420 static const int CONSTANT_BOUND = 20;
 421
 422 bool
 423 optimize_isl (scop_p scop)
 424 {
 425
 426   isl_schedule *schedule;
 427 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 428   isl_schedule_constraints *schedule_constraints;
 429 #endif
 430   isl_union_set *domain;
 431   isl_union_map *validity, *proximity, *dependences;
 432   isl_union_map *schedule_map;
 433
 434   domain = scop_get_domains (scop);
 435   dependences = scop_get_dependences (scop);
 436   dependences = isl_union_map_gist_domain (dependences,
 437                                            isl_union_set_copy (domain));
 438   dependences = isl_union_map_gist_range (dependences,
 439                                           isl_union_set_copy (domain));
 440   validity = dependences;
 441
 442   proximity = isl_union_map_copy (validity);
 443
 444 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 445   schedule_constraints = isl_schedule_constraints_on_domain (domain);
 446   schedule_constraints
 447         = isl_schedule_constraints_set_proximity (schedule_constraints,
 448                                                   proximity);
 449   schedule_constraints
 450         = isl_schedule_constraints_set_validity (schedule_constraints,
 451                                                  isl_union_map_copy (validity));
 452   schedule_constraints
 453         = isl_schedule_constraints_set_coincidence (schedule_constraints,
 454                                                     validity);
 455 #endif
 456
 457   isl_options_set_schedule_max_constant_term (scop->ctx, CONSTANT_BOUND);
 458   isl_options_set_schedule_maximize_band_depth (scop->ctx, 1);
 459 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 460   isl_options_set_schedule_serialize_sccs (scop->ctx, 1);
 461 #else
 462   isl_options_set_schedule_fuse (scop->ctx, ISL_SCHEDULE_FUSE_MIN);
 463 #endif
 464   isl_options_set_on_error (scop->ctx, ISL_ON_ERROR_CONTINUE);
 465
 466 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
 467   schedule = isl_schedule_constraints_compute_schedule(schedule_constraints);
 468 #else
 469   schedule = isl_union_set_compute_schedule (domain, validity, proximity);
 470 #endif
 471
 472   isl_options_set_on_error (scop->ctx, ISL_ON_ERROR_ABORT);
 473
 474   if (!schedule)
 475     return false;
 476
 477   schedule_map = getScheduleMap (schedule);
 478
 479   apply_schedule_map_to_scop (scop, schedule_map);
 480
 481   isl_schedule_free (schedule);
 482   isl_union_map_free (schedule_map);
 483
 484   return true;
 485 }
 486
 487 #endif  /* HAVE_isl */