gcc/graphite-optimize-isl.c

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